RSA详细解析
RSA详细解析
AiY0u
RSA 是一种广泛使用的非对称加密算法，在现代密码学中占据重要地位
RSA 算法基于数论中的大整数分解问题，该问题的核心是：将一个极大的合数分解为其质因数的乘积，在计算上极其困难（目前没有高效的多项式时间算法）
作为一种非对称加密算法，RSA的加密和解密分别使用公钥和私钥来进行
RSA 的密钥生成过程
- 选择两个不同的大质数 p 和 q。
- 计算 n = p×q，n 作为公钥和私钥的一部分，是一个大合数，并且每个用户使用的n都应该是独一无二且难以分解的
- 计算欧拉函数 φ(n) = (p-1)×(q-1)。
- 选择一个整数 e 作为公钥的指数，满足 1 <e < φ(n) 且 e 与 φ(n) 互质。
- 计算 e 在模 φ(n) 下的逆元 d，即 d 满足 (e×d) ≡ 1 mod φ(n)，d 作为私钥的指数。
- 公钥为 (e, n)，私钥为 (d, n)，其中 p、q 和 φ(n) 需要保密（它们是陷门信息的核心）。
后面写了为什么私钥要这样构建
RSA 的加密与解密过程
- 加密：发送方用接收方的公钥 (e, n) 对明文 m（需满足 m < n）进行加密，计算密文 c = m^e mod n。
- 解密：接收方用自己的私钥 (d, n) 对密文 c 进行解密，计算明文 m = c^d mod n。
正向计算（加密）利用公钥很容易完成，而反向计算（在没有私钥的情况下从密文破解明文）需要分解大整数 n，这在计算上几乎不可行
这就是一种陷门函数，即正向简单逆向困难
那有个问题，我们定义了加密公式c = m^e mod n，那解密为什么是这样子解密呢？
来看推导：
（后面n大小写写串哩，但应该不至于看不懂）
RSA签名
在传递信息时，我们需要验证消息的完整性（未被篡改）和发送者身份（确认消息来自声称的发送者）
这就需要用到RSA签名(RSA Signatures)
原理
倘若我现在要向别人发送信息message，那么我先将他转化为长整型m，使用公钥(e0,N0)加密产生密文c，对方拿到密文c之后使用私钥(d0,N0)解密。
这一流程就是标准的加密流程
然后我们还需要把m哈希以后得到H(m),使用我自己的私钥(d1,N1)对它加密产生密文S，对方拿到密文S后使用公钥(e1,N1)解密，然后对方可以直接哈希刚刚获取的m得h(m)，只需对照是否h(m) = H(m)
如果是，那显然这段信息是由私钥(d1,N1)的持有者发来的，且m并未遭到修改
可以画流程图：
RSA加密指数的理想选择
RSA的公钥e需要满足e与 φ(n)互质 ，常见的选择是65537。
e的最好选择其实是使用该有限乘法群的生成元(尤其是最小生成元)，
最小生成元的
阶数最大，提高安全性
数值最小，提升运算速度
引入dp、dq提升运算速率
在获得d以后
我们让dp = d mod (p-1) dq = d mod (q-1)
令m1 = c^dp mod p ; m2 = c^dq mod q
同时计算q⁻¹ (mod p)
之后有
1 | h = (m1-m2) mod p |
经由这样的运算，我们避免了直接计算c^d (因为d的数字规模很大，所以该幂运算消耗的时间较长)
计算量减少约 4 倍，且m1和m2的计算可以并行进行
接下来是上述步骤的数学推导：
根据
m ≡ cᵈ mod n 且 n = p*q，由中国剩余定理可将m投影到modp和modq上，存在m1、m2：
m1 ≡ cᵈ mod p ; m2 ≡ cᵈ mod q使得
m ≡ m1 mod p ; m ≡ m2 mod q设d = k(p-1) + dp
由费马小定理（
aᴾ⁻¹ ≡ 1 mod P)cᵈ ≡ cᵏ⁽ᵖ⁻¹⁾⁺ᵈᵖ ≡ cᵏ⁽ᵖ⁻¹⁾ * cᵈᵖ ≡ cᵈᵖ mod p这样就实现了降幂
替换1中结果：
m1 ≡ cᵈᵖ mod p ; m2 ≡ cᵈᵖ mod q有
m = t*q + m2t*q + m2 ≡ m1 mod p移项后，两边同时乘q⁻¹
t ≡ (m1 - m2)*q⁻¹ mod p至此，只需要计算
1
2
3h = (m1-m2) mod p
t = h*q⁻¹ mod p
m = m2 + t*q得到明文
