RSA

加密过程

1.选一对不相等且足够大的质数，p,q

2.计算p,q的乘积，n=p*q

3.计算n的欧拉函数，φ(n)=(p-1)*(q-1)

  • φ(n)=n-1

  • 若n=p*q，且p,q互质，则φ(n)=φ(p*q)=φ(p)*φ(q)

4.选一个与φ(n)互质的函数e，1<e<φ(n)

5.计算出e对于φ(n)的模反函数d，de mod φ(n)=1

  • e和φ(n)互质，那么一定可以找到一个整数d，使用ed-1被φ(n)整除，或者说ed除以φ(n)所得余数为1(ed-1==kφ(n) )

6.公钥，KU=(e,n)

7.私钥，KR=(d,n)

明文 M 加密 M^e mod n = C

密文 C 解密 C^d mod n =M