对RSA算法的理解

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

• 有两个较大的素数p和q(大于100¹⁰⁰)

• 让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 = P^e (mod n)

公钥为(e,n)

解密是就计算：

P = C^d (mod n)

私钥为(d,n)

Q:举个例子？

A:例如p=3,q=11,n=33,z=20,e=3,d=7

C = P³ (mod 33) = 2³ (mod 33) = 8

P = C⁷ (mod 33) = 8⁷ (mod 33) = 2