Rsa

Posted by SunQH Blog on October 11, 2019

RSA

RSA 是一种广泛使用的非对称加密算法。非对称加密包含三个部分: 公钥和私钥的生成,使用公钥加密数据,使用私钥解密数据。

  • 乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
  • 甲方获取乙方的公钥,然后用它对信息加密。
  • 乙方得到加密后的信息,用私钥解密。

公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。

下面用两个不相等的质数 p 和 q 来说明生成过程:

img

密钥的生成

Step 1: 随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)

Step 2: 计算p和q的乘积n \(n = 61×53 = 3233\) Step 3: 计算n的欧拉函数φ(n)。

欧拉函数:

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

\(φ(n) = (p-1)(q-1) = 60 \times 52 = 3120\) Step 4: 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质

爱丽丝就在1到3120之间,随机选择了17。

从条件可以看出,如果 φ(n) 可以分解为两个整数相乘,且其中一个是 e, 那么这样的 e 就不满足要求 (不互质)。

例如,请问 e = 15 是否可以使用? \(because \ gcd(15, 3120) \ is \ not \ 1 \\ gcd(15, 3120) = 15\) 显然,e=15是不能使用的

Step 5: 计算e对于φ(n)的模反元素d。

所谓“模反元素”就是指有一个整数d,可以使得ed被 φ(n) 除的余数为1 \(d = e^{-1} \ mod \ φ(n) = 17^{-1} \ mod \ 3120 =2753\) Step 6: 将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

下面就可以使用公钥和私钥进行加密通信了

加密:

加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或 unicode 值),且m必须小于n。

所谓”加密”,就是算出下式的c: \(m^e ≡ c \ (mod \ n)\) 爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式: \(e = 17, \ m = 65 \\ encryption \ = \ (m^e) \% n = (65^{17} \ \% \ 3233) \ = 2790\)

解密

解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立: \(c^d ≡ m \ (mod \ n) \\ decryption \ = \ (c^d)\%n = (2790^{2753}) \%3233 = 65\)