RSA加密算法

2018年10月18日 0 作者 snowysong@live.com
阅读需要1分钟

0x00.所需概念&公式

  • Phi函数(欧拉函数):欧拉函数是小于或等于n的正整数中与n互质的数的数目(φ(1)=1)。此函数以其首名研究者欧拉命名(Euler’s totient function),它又称为Euler’s totient function、φ函数、欧拉商数等。e.g:φ(8)=4,因为1,3,5,7均和8互质,φ(7)=6,因为1,2,3,4,5,6,均和7互质。
  • 素数(质数):素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。
  • 模指数运算有一个整数m,以n为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做模运算。e.g:10 mod 3=1;26 mod 6=2;28 mod 2 =0。
  • 素数的Phi函数:所有素数的Phi函数均可用:φ(n)=n-1 计算。e.g:φ(7)=7-1=6,φ(11)=11-1=10,当一个数可以用两个互质的数表示时,其Phi值可用:φ(A*B)=φ(A)*φ(B)计算。e.g:φ(21)=φ(3)*φ(7)=2*6=12,21的质数有1,2,4,5,8,10,11,13,16,17,19,20共12个。
  • ≡:是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。

0x01.演示

步骤 示例
step 1  选择一对素数p,q p=3,q=11
step 2 计算n=p*q n=3*11=33
step 3 计算φ(n) φ(n)=φ(p)*φ(q)
∴(3-1)*(11-1)=20
step 4 找一个与φ(n)互质的正整数e,且1<e<φ(n) 令e=3
step 5 计算d,使d*e≡1 mod φ(n)⇒d*e mod φ(n)=1 mod φ(n)=1 d*3 mod 20=1 mod 20=1
∴d=7
step 6 公钥(e,n),私钥(d,n) 带入可得:公钥(3,33),私钥(7,33)
step 7 明文为M,密文为C
加密公式:C≡M^e mod n
e.g:明文M=25,加密后密文C(即对明文数字25进行加密)
C≡M^e mod n
⇒C mod n=M^e mod n
⇒C mod 33=25^3 mod 33=16
⇒C=16
step 8 解密公式:M≡C^d mod n e.g:密文C=16,解密后明文M(即对密文数字16进行解密)
M≡C^d mod n
⇒M mod n=C^d mod n
⇒M mod 33=16^7 mod 33=25
⇒M=25

0 0 vote
Article Rating