公钥加密算法的基石：大素数

发表于   |   分类于 ，

素数，又称质数，我们在小数数学课上就已经学习到其概念：是指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

素数的概念简单至极，但对其的研究，却是数学家们终其一生的目的。当然，本篇文章不是讨论数学中对素数的研究，而是素数在现代密码学中的应用。

RSA定理基础

RSA公钥加密算法就是素数的一个典型应用。RSA为非对称加密，其加密与解密使用了不同的密钥。而对称加密是加密解密过程使用同一个密钥，更详细的读者可自行搜索。

RSA定理

在 RSA算法中，最基础的一个定理就是RSA定理，描述如下：

若P和Q是两个相素数，另有正整数R和M，其中M的值与(P-1)*(Q-1)的值互质，并使得(R*M) mod (P-1)*(Q-1)=1。有正整数A,且A<P*Q，设：

C=A^R mod P*Q

B=C^M mod P*Q

则有： A=B
mod表示取余运算

RSA算法的基础操作步骤：

  • 生成公钥和私钥
    1. 随意选择两个大的素数P和Q，P不等于Q
    2. 将P和Q两个素数相乘得到一个整数N，即 N=P*Q
    3. 将P,Q分别减1，再相乘，得到一个整数T，即 T=(P-1)*(Q-1)
    4. 选择一个整数E，作为一个密钥，使E与T互质（即E与T的最大公约数为1），并且E必须小于T
    5. 根据公式 D*E mode T = 1，计算出D的值，作为另一个密钥。
    6. 通过以上步骤计算得出N，E，D这3个数据，其中 (N, E) 作为公钥，(N, D) 作为私钥（当然，公钥和私钥可以互换）
    7. 生成公钥和私钥后，就可以将公钥对外公布了
  • 用公钥加密信息
    发送信息的一方收到公钥PK后，就可以通过公钥PK对数据进行加密，加密步骤如下：其中M为明文，加密后得到密文为C，公钥为 (N, E)
    • 明文： M
    • 加密： M^E mod N = C
    • 密文： C
  • 用私钥解密信息
    接收方持有私钥(N, D)，在接收到密文C后，即可通过私钥进行解密，得到明文M。过程如下：
    • 密文： C
    • 解密： C^D mod N = M
    • 明文： M

RSA算法实践

下面我们手动选两个数，进行RSA算法的实践，看看这里面计算的奥秘。

  1. 生成公钥和私钥

    1
    2
    3
    4
    5
    6
    7
    8
    取 P=7, Q=11
    则 N=P*Q=7*11=77
       T=(P-1)*(Q-1)=6*10=60
    取 E=7
    由 D*E mod T = 1
       D*7 mod 60 = 1
    得 D=43
    则： 公钥(77, 7)，私钥(77,43)

  2. 加密

    1
    2
    3
    4
    5
    6
    计算过程：
    明文：  M=2
    加密：  C=M^E mod N
            =2^7 mod 77
            = 51
    密文： 51

  3. 解密
    收到密文30后，通过私钥(77, 43)进行解密，过程：

    1
    2
    3
    4
    5
    6

    密文：   C=51
    解密：   M=C^D mod N
             =51^43 mod 77
             =2

从上面计算过程来看，我们使用的是最小的素数，7和11，计算过程中涉及到很大的幂运算(51^43)，结果是一个非常大的数。在实际应用中，P,Q要取很大值的素数，则得到的N,D,E值也很大，所以运算时的中间结果也很大，程序语言中提供的基本数据类型没办法使用，这里我在计算时使用的是BigNumber库计算的。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。
– 选自 维基百科

至此，RSA算法中如何用素数进行加密解密计算已完成，以上内容均从《程序员的数学思维修炼》一书中摘录，有兴趣的同学可以看看这本书，作为程序员，还是有必要了解一下基础数学知识。