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

技术博客 (170) 2023-10-29 09:01:01

原文链接 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 = 2D=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;
 }
THE END

发表回复