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

素数,又称质数,我们在小数数学课上就已经学习到其概念:是指在大于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算法中如何用素数进行加密解密计算已完成,以上内容均从《程序员的数学思维修炼》一书中摘录,有兴趣的同学可以看看这本书,作为程序员,还是有必要了解一下基础数学知识。