实验介绍:
一个密钥(公钥)是公开的,另一个密钥(私钥)必须保密,且由公钥求解私钥的计算是不可行的。
RSA
1选取质数p和q(pq不可公开)
2计算n=pq,φ(n)=(p-1)(q-1)
3随机选取整数e作为公钥,要求1<e<φ(n),e和φ(n)互质
如果不互质,就没有逆元,算不出私钥。
4计算私钥d,怎么计算呢,使用欧几里得算法先算出e在φ(n)下的逆元,再求e逆元在modφ(n)下的值。
举例:p=43,q=59,n=pq=43x59=2537.
φ(n)=(p-1)(q-1)=42x58=2436
选取e=13,满足1<e<φ(n),e和φ(n)互质,ed=1modφ(n)
d=937
加密
解密
私信发python代码