从零开始在 Python 中实现 RSA （第 1 部分）

我相信很多程序员，特别是 Web 开发人员都听说过 RSA 加密系统。RSA 是一个非对称密码系统，这意味着一个键用于加密，另一个键用于解密。

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

我见过很多文章，解释了不对称密码学的一般原则，但我没有看到任何易于理解这些算法后面数学背景的解释，所以我决定写这篇文章。

RSA 背后的数学解释

推荐看阮一峰大佬的：RSA算法原理（一）、RSA算法原理（二）

首先，正如我在上一段中提到的，要传输 RSA 加密的消息，您需要 2 个密钥。一个只能加密，一个可以解密。让我们把加密密钥表示为 “e” ，解密密钥将表示为 “d” ，消息将表示为 “m” 。RSA 背后的关键原理在于以下概念：
模反

$$(m^e)^d ≡ m \; (mod \; n)$$

如果正确选择这些数字，则很难找到 d、知道 e 和 n（如下所示）。

但首先，我们需要在数论中引入一些新概念。

• $a ≡ b \ (mod \ n) $表示存在一个整数 $x$ 使得 $a + nx = b$。更直观的解释是， $a/n$ 的结果等于 $b/n$ 的结果。
• $gcd(a, b)$ 是除 $a$ 和 $b$ 的最大数。
• $lcm(a, b)$ 是 $a$ 和 $b$ 的最小公倍数。
• $λ(n)$ 是一个数，使得 $x^λ(n) ≡ 1 (mod \ n)$ 对于任何 x 使得 $gcd(x, n) = 1$。由此您可以得出结论 $x^a ≡ x^b (mod \ n)$ 如果 $a ≡ b \ (mod \ λ(n))$。

生成密钥

让我们让 n = pq 其中 p 和 q 是 2 个素数。由于 λ§ = p - 1 和 λ(q) = q - 1（查找费马的小定理证明），λ(n) = (p - 1) * (q - 1)。

现在我们必须算出 ed ≡ 1（modλ（n））。e 可以是一些素数（通常是65537），d 可以使用扩展的欧几里德算法计算（将在代码部分中写入和解释）从等式 ed +xλ（n）= gcd（e，λ（n））（d和x是要计算的系数）。

(e, n) 用来加密 $(m^e) % n $;(d, n) 用来解密 $(m^d) \% n$

在计算出密钥之后，p 和 q 可以被丢弃。请注意，如果没有 p 和 q，找到 λ(n) 将意味着对 n 进行因式分解，对于经常使用的 n 高达 2^2048 的值，这不是一个容易解决的问题。

用 Python 实现 RSA 算法

首先列出程序及其步骤：

密钥生成：

• 找到 2 个随机素数 p 和 q
• 计算 n = p * q 和 λ(n) = (p - 1) * (q - 1)
• 使 e 等于某个素数，例如e = 35537
• 使用扩展欧拉算法从方程 ed + λ(n)x = gcd(e, λ(n)) = 1 计算 d（从这一点开始，我们将其称为 eucalg）

加密：

• 将消息分成多个部分（如果 n 为 2048 位，则为 256 位）
• 每个部分（表示为 m）被加密为 (m^e) % n

解密：

• 将消息分成多个部分，同上
• 每个部分（表示为 m）被解密为 (m^d) % n

扩展欧拉算法的实现

该算法依赖于这样一个事实，即如果 x 除以 a 和 b，则将有一对系数 (k, l)，使得：

$$a * k + b * l = x$$

该算法通过反复从更大的一个反复对较小的参数反复对较小的参数进行较小的参数来找到这些系数（和x），直到较小的一个变为0.而不是反复对减退，您可以计算出从a中减去的次数b（k = a //b）然后然后是副表集b * k。这种优化使算法在 $O（log max（a，b））$中运行，这更快。

以下是Python中算法的实现：

def eucalg(a, b):
	# make a the bigger one and b the lesser one
	swapped = False
	if a < b:
		a, b = b, a
		swapped = True
	# ca and cb store current a and b in form of
	# coefficients with initial a and b
	# a' = ca[0] * a + ca[1] * b
	# b' = cb[0] * a + cb[1] * b
	ca = (1, 0)
	cb = (0, 1)
	while b != 0:
		# k denotes how many times number b
		# can be substracted from a
		k = a // b
		# a  <- b
		# b  <- a - b * k
		# ca <- cb
		# cb <- (ca[0] - k * cb[0], ca[1] - k * cb[1])
		a, b, ca, cb = b, a-b*k, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
	if swapped:
		return (ca[1], ca[0])
	else:
		return ca

请注意，上面的函数可以为系数产生负数，所以如果发生这种情况，我们需要做的就是将 d 设置为 λ(n) - d。

用模实现快速求幂

有些人可能会建议使用（b ** e）％n，但这种方法不是很好的时光，因为b ** e尽管只有在过去的2000位左右或因此，但是只需要很大。该解决方案是在每个划分后计算模数的替代指数。

下面的指数实施具有对数时间复杂性。而不是从 1 到 e 和乘以 r（结果）by b，而不是从 b 的最高有效位触及 e 的最高有效位，并且在每个钻头处它确实 r = r * r + bit 。这是作用，因为如果R等于B ^ x并且您将位附加到x的末尾，则新 x 将是 x * 2 + bit。

def modpow(b, e, n):
	# find length of e in bits
	tst = 1
	siz = 0
	while e >= tst:
		tst <<= 1
		siz += 1
	siz -= 1
	# calculate the result
	r = 1
	for i in range(siz, -1, -1):
		r = (r * r) % n
		if (e >> i) & 1: r = (r * b) % n
	return r

密钥生成、加密和解密

密钥生成、加密和解密都在数学部分进行了解释，下面的代码只是实现.

def keysgen(p, q):
	n = p * q
	lambda_n = (p - 1) * (q - 1)
	e = 35537
	d = eucalg(e, lambda_n)[0]
	if d < 0: d += lambda_n
        # both private and public key must have n stored with them
	return {'priv': (d, n), 'pub': (e, n)}

def numencrypt(m, pub):
	return modpow(m, pub[0], pub[1])

def numdecrypt(m, priv):
	return modpow(m, priv[0], priv[1])

测试我们到目前为止的代码

我将代码存储到一个名为 rsa.py 的文件中，并在 Python shell 中运行以下命令：

>>> import rsa
>>> keys = rsa.keysgen(31337, 31357)
>>> keys
{'priv': (720926705, 982634309), 'pub': (35537, 982634309)}
>>> priv = keys['priv']
>>> pub = keys['pub']
>>> msg = 80087
>>> enc = rsa.numencrypt(msg, priv)
>>> enc
34604568
>>> dec = rsa.numdecrypt(enc, pub)
>>> dec
80087
>>> 

结论

使用本文中提供的代码，您可以写入所有核心部分。但您仍然需要一个随机的 Prime 发生器和明文加密（ Numencrypt 和 NumDecrypt 仅适用于尺寸小于 n 的数字 m ）。将在下一篇文章中写出。

原文链接：https://coderoasis.com/implementing-rsa-from-scratch-in-python/