RSA加密算法中的公钥和密钥

原文链接 mp.weixin.qq.com/s/r7H82DC8L…

title: RSA加密算法中的公钥密钥 date: 2023-08-26 23:38:31 tags: '密码技术,读书笔记'

密钥对

在昨天的文章RSA加密算法中提到了两个关键词——公钥、私钥。并且我们知道了，RSA 的加密就是求“明文的E次方 mod N”，解密是求“密文的D次方 mod N”。那么公式中的E、D、N这三个数就是生成的密钥对。

这三个数字肯定不是随随便便就拿来用的，那样的话加密也太容易被激活成功教程了。它们有自己的生成方式。

RSA密钥对的生成

我们先来简单陈述一下RSA密钥对的生成步骤，这其中涉及到了一些数学原理，暂时现不用知道什么意思。因为我也一知半解

1. 选择两个大的随机的质数 p 和 q
2. p 和 q进行乘法运算得到的值就是 N，这个N 就是公钥和私钥mod的那个N
3. 计算 φ(n)， φ(n)= (p-1)*(q-1),其中φ是欧拉函数。暂时先不用知道什么是欧拉函数
4. 现在来计算E，E 的计算规则是大于1但是小于 φ(n) 并且与 φ(n)互为质数。这个E就是公钥中的次幂数，暂时先不用知道什么是质数
5. 现在来计算D，我们现在已经计算出来了公钥，E 和 N，那么D的计算规则需要满足以下条件：(E * D) % φ(N) = 1。为什么非要满足这个公式呢？因为只要数字D满足上述条件，通过E 和 N 进行加密的数据就可以通过D 和 N 进行解密

经过上述五个步骤，我们已经成功按照规则生成了RSA 的公钥和私钥，现在来详细解释一下让我们迷糊的名词和公式符号

1. 选择两个互质的数字，p 和 q。什么是质数呢？

   1. 质数：质数（Prime number）是指大于1且只能被1和自身整除的正整数。换句话说，质数没有除了1和它本身之外的其他正因数。例如：2，3，5，7
   2. 那为什么要选择质数呢？根据上面的解释我们可以看出来质数因为只能被1和本身整出，所以质数只有两个因数，那就是1 和 本身，换句话说就是质数的分解是唯一的，换句话说就是每个正整数都可以唯一地分解为质数的乘积，这被称为唯一质因数分解定理。
   3. 什么是互为质数：是指这两个整数的最大公因数（最大公约数）为1，即它们没有除了1以外的公共正因数。

2. 第三步中提到了一个函数符号——φ(n)。这个φ符号表示：“欧拉函数”。那什么是“欧拉函数”？

   1. 欧拉函数 φ是以欧拉命名的一个数论函数。它表示对于一个正整数m,在小于等于m的正整数中与m互质的正整数的个数。（维基百科）

   2. (n)代表了一个正整数n。φ(n) 合起来表达的意思是：对于给定的正整数n，计算小于等于n并且与n本身互为质数的正整数个数。上面这两句话读起来很难理解，每个字都认识，但是连起来的意思总觉得模模糊糊。下面举个例子：

      1. 当 n =10 ，φ(n) = 4。为什么呢？因为：小于等于10的正整数有:1,2,3,4,5,6,7,8,9,10

         其中与10互质的有:1,3,7,9。所以 φ(n) = 4。

   现在上述步骤中难以理解的公式和名词都解释了， 我们尝试来生成一个RSA 的密钥对。

实践一下，生成一个RSA的密钥对

按照步骤我们应该先选择两个大的随机的质数， 这里我们选择p = 3, q = 13

第二步中N = p * q ，则N = 3 *13 = 39

第三步骤计算：φ(n)= (p-1)*(q-1) ，把p = 3, q = 13代入到公式中计算得出φ(n)= 24.这表示当N等于39的时候，与39互质的整数的个数是24。现在我们知道φ(n)=24，那么就可以计算第四步骤中的E

E的计算规则是大于1但是小于 φ(n) 并且与 φ(n)互为质数。公式表示就是 1 < E < φ(n) , 我们知道了φ(n) = 24，所以E 这个数字的取值范围就是 1、5、7、11、13、17 ....我们可以看出有很多数字，但是并不是都满足条件，我们选择11这个数字作为E 的值。

到此，我们已经计算出了E = 11 ，N = 24。这两个数字将作为我们的公钥。

因为N这个数字公钥私钥都会用到，所以接下来我们只需要计算D就可以了。

第五步中D的计算公式为：(E * D) % φ(N) = 1，E = 11，D 未知，φ(N) = 24。经过计算得出：D = 23

计算过程如下：

“

我们想要找到一个值 D，使得以下方程成立： (E * D) % φ(N) = 1；好像是废话

1. 使用扩展欧几里德算法计算 11 和24的最大公约数（GCD）：

   要求求解D的值。
   
   具体计算步骤如下:
   
   计算11与24的最大公约数 gcd(11,24) = 1
   因为gcd(11,24)=1,所以方程有解
   使用扩展欧几里得算法求11对24的模反元素D:
   设:r0 = 24
   
   r1 = 11
   r2 = r0 % r1 = 24 % 11 = 2
   
   递归计算:
   r3 = r1 % r2 = 11 % 2 = 1
   
   r4 = r2 % r3 = 2 % 1 = 0
   
   得到:r3 = gcd(11,24) = 1
   
   所以11对24的模反元素是r2的值,即:
   
   D = 2
   
   将D=2代入原方程验证: (11 * 2) mod 24 = 22
   结果不是1,所以D≠2。
   
   继续递归计算:
   r5 = r3 % r4 = 1 % 0 = 1
   
   r6 = r4 % r5 = 0 % 1 = 0
   
   得到:r5 = gcd(11,24) = 1
   
   所以11对24的模反元素是r4的值,即:
   
   D = 23
   
   重新验证: (11 * 23) mod 24 = 1
   综上,在给定的方程 11 * D mod 24 = 1 中,D=23。
   

我自己按照维基百科的方法计算了三遍，都不对，最后求助了GPT。😆

”

现在我们终于把公钥私钥都计算完了。

公钥：E = 11 ， N = 39

私钥：D = 23 , N = 39

加密一波试试

我们现在是用自己计算出来的公钥加密一段数字试试，RSA 的明文规则是小于N 的数，所以。我们取明文为8。代入加密公式：密文 = 明文E mod N 8 11 mod 39 = 5， 得到密文为5

将 20 代入到解密公式：明文 = 密文D mod N 5 23 mod 39 = 8, 得到明文为8

计算过程

    /**      * 上述代码首先初始化了基数 datai，指数 ED 和模数 N，然后定义了一个变量 result 存储计算结果。      * 接着，代码使用一个 for 循环，循环次数为指数的值。在每次循环中，都会将 result 乘以基数，      * 然后对模数取模，以此来实现 (a*b)%c = (a%c * b%c)%c 这个公式。最后，代码打印出结果。      * @param datai      * @param ED      * @param N      * @return      */
private static long mod(int data, int ED, int N) {
   long result = 1;
   for (int j = 0; j < i1; j++) {
     result = result * i % i2;
   }
   return result;
 }