RSA算法简介
RSA密码算法是美国麻省理工学院的Rivest、Shamir和Adleman三位学者于1978年提出的。RSA密码算法方案是唯一被广泛接受并实现的通用公开密码算法,目前已经成为公钥密码的国际标准。它是第一个既能用于数据如密,也能通用数字签名的公开密钥密码算法。在Internet中,电子邮件收、发的加密和数字签名软件PGP就采用了RSA密码算法。
RSA的理论基础
RSA的理论基础是大整数因数分解的困难性质。
RSA加解密过程
密钥生成
- 选取两个大素数p,q
- 计算n=p⋅q
- 计算欧拉函数 ϕ(n)=(p−1)⋅(q−1)
- 随机选取一个整数e(1<e<ϕ(n)),使满足gcd(e,ϕ(n))=1
- 由扩展欧几里得算法计算d使得e⋅d mod ϕ(n)=1
- 形成密钥对,其中公钥为(e,n),私钥为(d,n),p,q为秘密参数需要保密,不需要也可以销毁
加密过程
加密使用公钥(e,n)
设明文为m,则密文为c=me mod n
解密过程
解密使用私钥(d,n)
设密文为c,则明文为m=cd mod n
例题
设通信双方使用RSA加密体制,接收方的公开密钥(e,n)=(5,35),接收到的密文c=10,求明文m
p×q=n=35
p=5,q=7
ϕ(n)=(p−1)(q−1)=4×6=24
e=5
5⋅d mod ϕ(n)=1
5d=ϕ(n)⋅t+1=24t+1 ,(d,t∈N)
当t=1时,d=5
m=cd mod n=105 mod 35=5
选择p=7,q=17,e=5,试用RSA方法对明文m=19进行加密、解密运算
p=7,q=17
n=p⋅q=119
ϕ(n)=6×16=96
e=5
5∗d mod ϕ(n)=1
5∗d=96t+1
t=4,d=77
公钥(e,n)=(5,119)
私钥(d,n)=(77,119)
加密c=me mod n=195 mod 119=66
加密m=cd mod n=6677 mod 119=19
设Diffie-Hellman方法中,公用素数p=11,生成元等于2。若用户A的公钥SA=9,则A的私钥a为多少?如果用户B的公钥SB=3,则共享的密钥K为多少?