这篇文章上次修改于 211 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

RSA是一种公钥加密算法,选择公钥和密匙的要求有:

  • 有两个较大的素数p和q(大于100100)
  • 让n = pq、z = (p-1)(q-1)
  • 选择d与z互质(互质是公约数只有1的两个整数,叫做互质整数)
  • 选择e,e要满足e*d = 1(mod z)

       Q:什么是e*d = 1(mod z)?
       A:同余关系,a = b(mod n)可以解释为a与b二数的差值(即a-b)是n的整数倍数
       例如:25 = 10(mod 5),25-10=15,15除以5可以得到整数
       同理e*d = 1(mod z)为e*d-1的值除以z可以得到整数
    

加密时就计算:
C = Pe (mod n)
公钥为(e,n)
解密是就计算:
P = Cd (mod n)
私钥为(d,n)

Q:举个例子?
A:例如p=3,q=11,n=33,z=20,e=3,d=7
C = P3 (mod 33) = 23 (mod 33) = 8
P = C7 (mod 33) = 87 (mod 33) = 2