RSA加密

质数

质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。

来自 https://zh.wikipedia.org/wiki/%E8%B4%A8%E6%95%B0

互质

互质是公约数只有1的两个整数,叫做互质整数。

欧拉

在数论中,对正整数n,欧拉函数phi(n)是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。

来自 https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

1
2
3
4
5
例如 11 的欧拉:

比11小且与11互质的正整数有: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

所以phi(11) = 10 = 11-1

由上例子同时可知, 质数的欧拉是他本身减1: phi(N) = N - 1
同时 歐拉函數是積性函數,即是说若m,n互質,則 phi(mn) = phi(m)phi(n)

模反元素

模逆元也称为模倒数,或者模逆元。<- 模反元素
如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。这时,b就叫做a的“模反元素”。

1
如3关于20的模反元素是7,(3*7)%20=1

https://zh.wikipedia.org/wiki/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0

欧拉定理

在数论中,欧拉定理(也称费马-欧拉定理或欧拉phi函数定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素(即gcd(a,n)=1),则
a^phi(n) = 1 (mod n)
即 a^phi(n)与1在模n下同余。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。

gcd: greatest common divisor(最大公约数)

RSA

  1. 隨意選擇兩個大的質數 p和q,p不等于q,计算N=pq.
  2. 求N的欧拉,r = phi(N) = phi(q) x phi(p) = (p-1)(q-1)
  3. 选择一个小于r的整数e,使e与r互质。並求得e关于r的模反元素,命名为d。
  4. (N,e)是公钥,(N,d)是私钥。
  5. 加密原文m, 得到密文 x = (m^e)%N
  6. 解密公式为 m = (x^d)%N
    只能加密比N小的数字,比N大的数字无法加密。

eg:

1
2
3
4
5
6
7
8
9
10
选择两个质数3,11。
计算得到N=3*11=33
计算N的欧拉,r=phi(N)=phi(3)*phi(11)=(3-1)(11-1)=20
选择一个小于的r且与r互质的整数3,求得3关于20的模反元素7
得到公钥(33,3),私钥(33,7)

加密:
加密数字24,(24^3)%33 = 30, 获得加密后的密文 30
解密:
对密文30解密,(30^7)%33 = 24, 获得解密后的明文24