清茶一盏公杯斟茗

上下运杯，左右轻斟

公杯，私茗，香满阑

清茶，浓茶，甘润田

然君闻几何？

要谈谈RSA加密算法，不妨先聊聊密码学的发展历史和密码学的历程。

密码学早在公元前400多年就已经产生，人类使用密码的历史几乎与使用文字的时间一样长，密码学的发展大致可以分为 3 个阶段: 1949 年之前的古典密码学阶段; 1949 年至 1975 年密码学成为科学的分支; 1976 年以后对称密钥密码算法得到进一步发展，产生了密码学的新方向—公钥密码学。1976 年，W.Diffie 和 M.Hellman 在发表的文章“密码学的新方向”中首次公开提出了公钥密码( Public-key Cryptography) 的概念。公钥密码的提出实现了加密密钥和解密密钥之间的独立，解决了对称密码体制中通信双方必须共享密钥的问题，在密码学界具有划时代的意义。^1^

密码学的历史非常悠久，但是密码学的发展速度并不是非常迅速，直到信息时代的到来以及网络空间安全面临着巨大的威胁，密码学得到了前所未有的飞速发展，RSA公钥密码就是其中的代表。密码学中研究的对象有大致三类：

对称密码
非对称密码
协议

而RSA密码属于非对称密码，公钥密码。RSA也是现代密码学的代表性的内容部分，那么非常经典的RSA密码就是一个什么样的密码呢？

首先，要搞清楚什么是RSA密码：

RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。

1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。

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

RSA加密算法就是三个人提出的一个非对称加密的算法，是一种公钥算法。RSA加密算法进行加密的信息具有良好的安全性和可靠性，正确地使用RSA加密算法可以应对互联网上的大多数针对密码进行的攻击。

RSA加密算法的具体内容是什么呢？

（这里借鉴一下阮一峰的个人博客进行说明）^3^

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

（2）甲方获取乙方的公钥，然后用它对信息加密。

（3）乙方得到加密后的信息，用私钥解密。

这是非对称加密的总体流程，简单来说就是公钥加密，私钥解密的算法模式。而RSA加密算法就是公钥算法中的代表性的算法，这经典算法的基本原理还是比较简单易懂的。

RSA加密算法需要一点点的数学基础，也可以说是数论基础。

数学基础

模运算：模运算也可以说是用取余的运算方式

$$ a \equiv b(mod; m)$$

这是最简单的模运算公式，也可以使用简单的Python语法实现：

b = a % m # python语言中%可以进行取余运算

整数环：模运算的延申，无论模运算中的数怎么加减乘除都在模的一个整数环中。

在数论的概念中，模运算主要是针对自然数进行的研究，模运算也是如此。可以把整数环想象成一个钟表，钟表有12个数字，无论怎么加减乘除钟表的数字，指针始终都指在钟表的环中。

这里用简单的数学语言进行表示：

$$ a + c\equiv e(mod;12)$$

$$ a \cdot c\equiv f(mod;12)$$

当然也可以使用Python语法进行表示：

e = (a+c) % 12
f = (a*c) % 12

欧拉函数：求小于该数的素数个数多少的问题的最佳解决方案。

欧拉函数也是数论里面比较重要的概念，欧拉函数的特点使得RSA加密算法有良好的加密性和安全性。

在讲欧拉函数之前，先阐述一下素数的概念：

素数也叫质数，素数就是只能被1和自身整除的数

互素也叫互质，如果两个数的最大公因数是1，那么则称这两个数是互素的

什么是欧拉函数呢？

欧拉函数一般使用 φ(n) 表示，一般来说是分为两种情况的：

（1） n是一个素数：

$$ \varphi (n)= n-1$$

（2）n不是一个素数，但是n是两个素数的乘积：

$$ \varphi (n) = (p-1) \cdot (q-1) $$

这就是欧拉函数，和欧拉函数一起使用的还有一个欧拉定理：

在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:

$$ a ^{\varphi(n)} \equiv 1(mod; n) $$

这些大致就是欧拉函数和欧拉定理的大致内容，都是规律性的总结，在RSA算法中加以使用就可以了。

模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。^3^

这里可以使用数学语言进行解释一下：

$$ a \cdot b \equiv 1(mod;m) $$

就是两个数进行模乘法运算得到的结果是1的两个数互为模反元素，也叫逆元。

在这个等式中，可以说a是b的逆元，也可以说是b是a的逆元。

最后一个数学概念：单向函数，公钥加密算法的核心原理

单向函数就是由x求y简单，而由y求x比较困难的函数叫做单向函数：

$$ y = f(x) $$

$$ x = f^{-1}(y) $$

由于单向函数概念的出现，使得公钥加密私钥解密成为现实。

可是单向函数只是使加密变得容易，而并没有使解密变得容易。于是一个陷门的概念提出使公钥加密私钥解密的加密算法模式真正的变成现实。

什么是陷门呢？

陷门的概念就好比网络安全的后门，单向函数解密不是非常困难嘛，而陷门就是一个特殊的数值可以使单向函数进行解密变得简单。于是陷门就可以作为私钥进行解密。

RSA公钥加密算法的数学知识大致就是这些了。

下面，来聊一聊RSA公钥加密算法的具体过程。

RSA加密算法

首先随机选择两个不相等的素数p和q
计算p和q的乘积n
计算n的欧拉函数发φ(n)
随机选择一个整数e，e满足的条件是：1<e<φ(n)
计算e对于φ(n)的模反元素d
将n和e封装成公钥，将n和d封装成私钥

具体流程用数学的语言描述：

$$ 1. \quad p , q$$

$$ 2. \quad p\cdot q = n $$

$$ 3. \quad \varphi (n) $$

$$ 4. \quad 1<e<\varphi (n) $$

$$ 5. \quad e \cdot d \equiv 1 (mod; \varphi (n)) $$

$$ 6. \quad (n , e) , (n , d) $$

当然也可使用python语句进行设计：4

import gmpy2
import gmpy2
from gmpy2 import mpz
import binascii

rs = gmpy2.random_state()

#生成大素数（0-2^1024位）
def create_prime():
    p = gmpy2.mpz_urandomb(rs,1024)         #随机生成一个0~2^1024位的数
    while not gmpy2.is_prime(p):            #判断生成的数是否是素数
        p = gmpy2.mpz_urandomb(rs,1024)     
    return p

#生成密钥e,d
def get_e_d(phi):
    e = gmpy2.mpz_random(rs,phi)            
    while gmpy2.gcd(e,phi) != 1:
        e = gmpy2.mpz_random(rs,phi)        #随机生成一个0~phi的,与phi互素的数
    d = gmpy2.invert(e,phi)                 #生成d
    return e,d

#rsa加密
def encrypt(plain_text,e,n):
    m = mpz(binascii.hexlify(plain_text.encode('utf-8')), 16)
    cipher_text = gmpy2.powmod(m,e,n)
    return cipher_text

#rsa解密
def decrypt(cipher_text,d,n):
    m = gmpy2.powmod(cipher_text,d,n)
    plain_text = binascii.unhexlify(format(m, 'x')).decode('utf-8')
    return plain_text

if __name__ == '__main__':
    p = create_prime()
    q = create_prime()
    n = p * q
    phi = (p-1)*(q-1)
    e,d = get_e_d(phi)
    plain_text = input("请输入明文：")
    cipher_text = encrypt(plain_text,e,n)
    print("RSA加密后的密文是：%x"%cipher_text)
    plain_text1 = decrypt(cipher_text,d,n)
    print("RSA解密后的明文是：{}".format(plain_text1))

RSA的加密流程非常简单，只需要大致记忆就可以对RSA算法流程非常清晰，而且明了于心。同时，也会出现一些疑问，这么安全的加密算法会有什么样的漏洞会在CTF比赛中让CTF选手进行攻击呢？

无论再安全的算法，都有可以破解的漏洞存在，“没有绝对安全的系统”。时代在进步，密码学算法也在一步一步的提升，下一篇将揭示RSA公钥密码的常见攻击手段。

参考

闲聊到此为止，来喝杯茶可好？

清茶一盏 公杯斟茗

清茶一盏 公杯斟茗

数学基础

RSA加密算法

参考

清茶一盏公杯斟茗

清茶一盏公杯斟茗