RSA算法简介

RSA密码算法是美国麻省理工学院的Rivest、Shamir和Adleman三位学者于1978年提出的。RSA密码算法方案是唯一被广泛接受并实现的通用公开密码算法，目前已经成为公钥密码的国际标准。它是第一个既能用于数据如密，也能通用数字签名的公开密钥密码算法。在Internet中，电子邮件收、发的加密和数字签名软件PGP就采用了RSA密码算法。

RSA的理论基础

RSA的理论基础是大整数因数分解的困难性质。

RSA加解密过程

密钥生成

  1. 选取两个大素数p,qp,q
  2. 计算n=p⋅qn=p \cdot q
  3. 计算欧拉函数 ϕ(n)=(p−1)⋅(q−1)\phi (n) = (p-1)\cdot(q-1)
  4. 随机选取一个整数e(1<e<ϕ(n))e(1 < e < \phi(n))，使满足gcd(e,ϕ(n))=1gcd(e,\phi(n))=1
  5. 由扩展欧几里得算法计算d使得e⋅d mod ϕ(n)=1e \cdot d \space mod \space \phi(n)=1
  6. 形成密钥对，其中公钥为(e,n)，私钥为(d,n),p,q为秘密参数需要保密，不需要也可以销毁

加密过程

加密使用公钥(e,n)

设明文为m，则密文为c=me mod nc=m^e \space mod \space n

解密过程

解密使用私钥(d,n)

设密文为c，则明文为m=cd mod nm=c^d \space mod \space n

例题

设通信双方使用RSA加密体制，接收方的公开密钥(e，n)=(5，35)，接收到的密文c=10，求明文m

p×q=n=35p\times q=n=35

p=5,q=7p=5, q=7

ϕ(n)=(p−1)(q−1)=4×6=24\phi(n)=(p-1)(q-1)=4\times 6 = 24

e=5e=5

5⋅d mod ϕ(n)=15 \cdot d \space mod \space \phi(n) = 1

5d=ϕ(n)⋅t+1=24t+1 ,(d,t∈N)5d=\phi(n)\cdot t+1=24t+1 \space,(d,t \in N)

当t=1t=1时，d=5d=5

m=cd mod n=105 mod 35=5m=c^d \space mod\space n = 10^5 \space mod \space 35 = 5

选择p=7，q=17，e=5，试用RSA方法对明文m=19进行加密、解密运算

p=7,q=17p=7, q=17

n=p⋅q=119n=p\cdot q=119

ϕ(n)=6×16=96\phi(n)=6 \times 16 = 96

e=5e=5

5∗d mod ϕ(n)=15*d \space mod \space \phi(n) = 1

5∗d=96t+15*d = 96t+1

t=4,d=77t=4, d=77

公钥(e,n)=(5,119)(e,n)=(5,119)

私钥(d,n)=(77,119)(d,n)=(77,119)

加密c=me mod n=195 mod 119=66c=m^e \space mod \space n=19^5 \space mod \space 119 = 66

加密m=cd mod n=6677 mod 119=19m=c^d \space mod \space n=66^77 \space mod \space 119 = 19

设Diffie-Hellman方法中，公用素数p=11,生成元等于2。若用户A的公钥SA=9，则A的私钥a为多少？如果用户B的公钥SB=3，则共享的密钥K为多少？