RSA加密&签名

加密&解密

1. 任选两个不同质数p和q,计算乘积 N = p*q, r = (p - 1)*(q - 1)

2. 任选一个模数e，满足(r,e) = 1

   确定公钥:
   $$
   <N, e>
   $$

   确定私钥d:(d满足)
   $$
   <N, d>:: de = xr+1，x为常数
   $$

3. 销毁除公钥和私钥外所有数据，公开公钥，仔细保存私钥

4. 加密步骤：明文m(必须 < N),密文c

   $$
   m^e mod N = c
   $$

5. 解密步骤：

   $$
   c^d mod N = m
   $$

签名&验签

签名

1. 计算Hash

   $$
   h = hash(msg)
   $$

2. 对h进行加密得到签名结果s

   $$
   s = h^d mod N
   $$

验证签名

1. 计算Hash

   $$
   h = hash(msg)
   $$

2. 对密文解密得到h1

   $$
   h1 = s^e mod N
   $$

3. h = h1则签名验证成功

示例

1. 任选两个质数11,17,计算成绩N = 187,r = 160

2. 选取一个模数e = 3

   公钥： (187, 3)

   私钥： (187, 107)

3. 加密 m = 49

   计算密文
   $$
   c = 49^3 mod 187 = 26
   $$

4. 解密

   计算明文
   $$
   m = 26^{107} mod 187 = 49
   $$

5. 签名

   假设hash(msg) = 5
   $$
   s = 5^{107} mod 187 = 113
   $$

6. 验签

   $$
   h1 = 113^3 mod 187 = 5
   $$

安全性分析

一般的破解方法是将N因式分解为互不相同质数，然后按以上步骤暴力枚举。所以破解难度与极大值因数分解难度等价。