用RSA进行加解密和数字签名

RSA加解密过程

1.选择一对素数p,q

2.n=p*q

3.φ(n)=(n-1)(q-1)

4.找e(加密秘钥encrypt)，使e与φ(n)互质且 1<e<φ(n)

5.计算d(解密密钥decrypt)，d * e ≡ 1 mod φ(n)， ≡为互余符号，即 (d * e) mod φ(n)= 1

6.公钥(e,n) 私钥(d,n)

7.设明文m，密文c，明文加密，密文c = m^e mod n

8.密文解密，明文m = c^d mod n

例：e=3 p=5 q=11 m=14

解：n=p*q=55 φ(n)=(n-1)(q-1)=40

3*d mod 40=1 d=27

公钥(n,e)=(55,3) 得到密文c=m^e mod 55=14^3 mod 55=49

私钥(n,d)=(55,27) 得到明文m=c^d mod 55=49^27 mod 55=14

RSA数字签名过程

RSA签名的过程是使用私钥对消息加密，验证过程是使用公钥进行解密验签

依据 ≡ m (mod n)，以及杂凑计算 消息m 的摘要 h = H(m)。签名计算 s = mod n

h：消息m的短指纹。

s：签名者的签名

基本RSA签名生成 输入：RSA公钥(n, e) 、RSA私钥d、明文m

输出：签名s

过程：

1.计算 h = H(m)，其中 H 是一个杂凑函数

2.计算 s = mod n

3.返回s

基本RSA签名验证 输入：(n，e)，消息m，签名s

输出：验签通过？

过程：

1.计算 h = H(m)

2.由于验签是计算 s = mod n，则 = mod n ≡ h mod n，则 h’= mod n

3.若 h’= h 验签通过

例：e=5 p=5 q=7 h=2

解：n=p*q=35 φ(n)=(n-1)(q-1)=24

5*d mod 24=1 d=5

私钥(n,d)=(35,5) 得到签名s=h^d mod 35=2^5 mod 35=32

公钥(n,e)=(55,3) 验证签名h=s^e mod 35=32^5 mod 35=2