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 |