数论与RSA公钥密码体制¶
本教程使用Sage学习初等数论和RSA公钥密码系统。我们将介绍一些帮助我们执行基本数论运算的Sage命令，例如最大公约数和Euler‘s Phi函数。然后，我们介绍RSA密码系统，并使用Sage的内置命令通过RSA算法对数据进行加密和解密。请注意，有关RSA的本教程仅用于教学目的。有关密码学或各种密码系统的安全性的更多详细信息，请参阅专业文本，如 [MenezesEtAl1996], [Stinson2006], 和 [TrappeWashington2006].
初等数论¶
我们首先回顾了初等数论的基本概念，包括素数、最大公约数、同余和欧拉Phi函数的概念。当我们介绍RSA算法时，我们将在后面的部分中引用介绍的数论概念和Sage命令。
素数¶
公钥密码学使用数论中的许多基本概念，例如素数和最大公约数。正整数 n > 1 据说是 prime 如果它的因子只有1和它自己。在Sage中，我们可以使用以下命令获得前20个素数 primes_first_n **
sage: primes_first_n(20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
最大公约数¶
让我们 a 和 b 为整数，而不是两个都为零。然后是的最大公约数(GCD) a 和 b 是最大的正整数，它是两者的因子 a 和 b 。我们用 gcd(a,b) 来表示这一最大的积极因素。可以通过设置以下内容扩展此定义 gcd(0,0) = 0 。Sage使用 gcd(a, b) 表示…的GCD a 和 b 。任意两个不同素数的GCD是1，18和27的GCD是9。：：
sage: gcd(3, 59)
1
sage: gcd(18, 27)
9
如果 gcd(a,b) = 1 ，我们说 a 是 coprime (或相对质数)到 b 。特别是， gcd(3, 59) = 1 所以3等于59，反之亦然。
同余¶
当一个整数除以一个非零整数时，我们通常得到余数。例如，当23除以5时，我们得到的余数为3；当8被5整除时，余数又是3。同余的概念帮助我们描述这样一种情况，即两个整数除以非零整数后具有相同的余数。让我们 a,b,n in ZZ 以至于 n neq 0 。如果 a 和 b 除以后的余数相同 n ，那么我们就说 a 是 congruent 至 b 模数 n 并将这种关系表示为
This definition is equivalent to saying that n divides the
difference of a and b, i.e. n ;|; (a - b). Thus
23 equiv 8 pmod{5} because when both 23 and 8 are divided by 5, we
end up with a remainder of 3. The command mod allows us to
compute such a remainder:
sage: mod(23, 5)
3
sage: mod(8, 5)
3
欧拉Phi函数¶
考虑从1到20(包括1和20)的所有整数。列出所有从互质到20的整数。换句话说，我们想要找到这些整数 n ，在哪里 1 leq n leq 20 ，以便 gcd(n,20) = 1 。使用一点Sage编程即可轻松完成后一项任务：
sage: L = []
sage: for n in range(1, 21):
....: if gcd(n, 20) == 1:
....: L.append(n)
sage: L
[1, 3, 7, 9, 11, 13, 17, 19]
上面的编程语句可以保存到一个文本文件中，该文本文件名为 /home/mvngu/totient.sage ，按如下方式组织，以增强可读性。
L = []
for n in range(1, 21):
if gcd(n, 20) == 1:
L.append(n)
L
我们指的是 totient.sage 作为Sage脚本，就像人们会将包含Python代码的文件称为Python脚本一样。我们使用4个空格缩进，这是Sage和Python编程中的编码约定，而不是制表符。
该命令 load 可用于将包含我们的编程语句的文件读取到Sage中，并在加载文件内容后让Sage执行这些语句：
load("/home/mvngu/totient.sage")
[1, 3, 7, 9, 11, 13, 17, 19]
在后一个列表中，闭合区间中有8个整数 [1, 20] 如果不显式生成列表，
1 3 7 9 11 13 17 19
how can we compute the number of integers in [1, 20] that are
coprime to 20? This is where Euler's phi function comes in handy.
Let n in ZZ be positive. Then Euler's phi function counts the
number of integers a, with 1 leq a leq n, such that
gcd(a,n) = 1. This number is denoted by varphi(n). Euler's phi
function is sometimes referred to as Euler's totient function, hence
the name totient.sage for the above Sage script. The command
euler_phi implements Euler's phi function. To compute
varphi(20) without explicitly generating the above list, we proceed
as follows:
sage: euler_phi(20)
8
如何保守秘密？¶
Cryptography 是隐藏数据的科学(有些人可能会说它是艺术)。假设我们正在给某人写一封机密电子邮件。写完电子邮件后，我们可以用两种方式之一发送它。第一种方式，通常也是很方便的，就是简单地按下发送按钮，而不关心我们的电子邮件将如何发送。以这种方式发送电子邮件类似于将机密信息写在明信片上并邮寄，而不是将明信片装在信封中。任何可以访问我们明信片的人都可以看到我们的消息。另一方面，在发送电子邮件之前，我们可以对机密消息进行加扰，然后按下发送按钮。扰乱我们的邮件就像把明信片装在信封里一样。虽然不是100%安全，但至少我们知道，任何想要阅读我们的明信片的人都必须打开信封。
在密码学术语中，我们的消息被称为 plaintext 。对我们的消息进行加扰的过程称为 encryption 。在加密我们的消息之后，加扰版本被称为 ciphertext 。从密文中，我们可以通过以下方式恢复原始的解密消息 decryption 。下图说明了加密和解密的过程。一个 cryptosystem 由一对相关的加密和解密过程组成。
+ ---------+ encrypt +------------+ decrypt +-----------+
| plaintext| -----------> | ciphertext | -----------> | plaintext |
+----------+ +------------+ +-----------+
下表提供了一种非常简单的方法，可以对用英语编写的消息进行加扰，并且只使用大写字母，不包括标点符号。
+----------------------------------------------------+
| A B C D E F G H I J K L M |
| 65 66 67 68 69 70 71 72 73 74 75 76 77 |
+----------------------------------------------------+
| N O P Q R S T U V W X Y Z |
| 78 79 80 81 82 83 84 85 86 87 88 89 90 |
+----------------------------------------------------+
正式地，让
是英文字母表中的一组大写字母。此外，让我们
be the American Standard Code for Information Interchange (ASCII) encodings of the upper case English letters. Then the above table explicitly describes the mapping f: Sigma longrightarrow Phi. (For those familiar with ASCII, f is actually a common process for encoding elements of Sigma, rather than a cryptographic "scrambling" process per se.) To scramble a message written using the alphabet Sigma, we simply replace each capital letter of the message with its corresponding ASCII encoding. However, the scrambling process described in the above table provides, cryptographically speaking, very little to no security at all and we strongly discourage its use in practice.
用两把钥匙保守秘密¶
Rivest，Shamir，Adleman(RSA)密码系统是一种 public key cryptosystem 。RSA使用 public key 对消息进行加密，并使用相应的 private key 。我们可以分发我们的公钥，但出于安全原因，我们应该将私钥保密。加密和解密过程借鉴了初等数论中的技术。以下算法改编自的第165页 [TrappeWashington2006]. 它概述了RSA加密和解密过程。
选择两个素数 p 和 q 让我们 n = pq 。
Let e in ZZ be positive such that gcd big( e, varphi(n) big) = 1.
Compute a value for d in ZZ such that de equiv 1 pmod{varphi(n)}.
我们的公钥是这对 (n, e) 我们的私钥是三元组 (p,q,d) 。
对于任何非零整数 m < n 、加密 m 使用 c equiv m^e pmod{n} 。
解密 c 使用 m equiv c^d pmod{n} 。
接下来的两节将逐步介绍RSA算法，使用Sage生成公钥和私钥，并基于这些密钥执行加密和解密。
生成公钥和私钥¶
形式的正整数 M_m = 2^m - 1 被称为 Mersenne numbers 。如果 p 是质数，并且 M_p = 2^p - 1 也是质数，那么 M_p 被称为 Mersenne prime 。例如，31是质数， M_{31} = 2^{31} - 1 是梅森素数，可以使用以下命令进行验证 is_prime(p) 。此命令返回 True 如果它的论点 p 恰好是质数，否则返回 False 。根据定义，素数必须是正整数，因此 is_prime(-2) 退货 False 虽然我们知道2是素数。事实上，这个数字 M_{61} = 2^{61} - 1 也是梅森素数。我们可以利用 M_{31} 和 M_{61} 要完成RSA算法中的第1步，请执行以下操作：
sage: p = (2^31) - 1
sage: is_prime(p)
True
sage: q = (2^61) - 1
sage: is_prime(q)
True
sage: n = p * q ; n
4951760154835678088235319297
这里需要警告一句话。在上面的代码示例中，选择 p 和 q 作为Mersenne素数，并且彼此之间有如此多的数字相隔很远，从密码安全性的角度来看，这是一个非常糟糕的选择。但是，我们将使用上面选择的数值来 p 和 q 在本教程的其余部分中，请始终记住，选择它们仅用于教学目的。参考 [MenezesEtAl1996], [Stinson2006], 和 [TrappeWashington2006] 有关RSA安全性的深入讨论，或参考其他专业文本。
对于第2步，我们需要找到一个与互质的正整数 varphi(n) 。整数集在Sage模块中实现 sage.rings.integer_ring 。对整数的各种操作可以通过 ZZ.* 函数族。例如，命令 ZZ.random_element(n) 返回在闭合间隔内均匀分布的伪随机整数 [0, n-1] 。
We can compute the value varphi(n) by calling the sage function
euler_phi(n), but for arbitrarily large prime numbers p and q,
this can take an enormous amount of time. Indeed, the private key
can be quickly deduced from the public key once you know varphi(n),
so it is an important part of the security of the RSA cryptosystem that
varphi(n) cannot be computed in a short time, if only n is known.
On the other hand, if the private key is available, we can compute
varphi(n)=(p-1)(q-1) in a very short time.
使用一个简单的编程循环，我们可以计算 e 详情如下：
sage: p = (2^31) - 1
sage: q = (2^61) - 1
sage: n = p * q
sage: phi = (p - 1)*(q - 1); phi
4951760152529835076874141700
sage: e = ZZ.random_element(phi)
sage: while gcd(e, phi) != 1:
....: e = ZZ.random_element(phi)
...
sage: e # random
1850567623300615966303954877
sage: e < n
True
AS e 是一个伪随机整数，它的数值在每次执行 e = ZZ.random_element(phi) 。
计算的值的步骤 d 在RSA算法的第三步中，我们使用扩展的欧几里德算法。根据同余的定义， de equiv 1 pmod{varphi(n)} 相当于
where k in ZZ. From steps 1 and 2, we already know the numeric
values of e and varphi(n). The extended Euclidean algorithm
allows us to compute d and -k. In Sage, this can be accomplished
via the command xgcd. Given two integers x and y,
xgcd(x, y) returns a 3-tuple (g, s, t) that satisfies
the Bézout identity g = gcd(x,y) = sx + ty. Having computed a
value for d, we then use the command
mod(d*e, phi) to check that d*e is indeed congruent
to 1 modulo phi.
sage: n = 4951760154835678088235319297
sage: e = 1850567623300615966303954877
sage: phi = 4951760152529835076874141700
sage: bezout = xgcd(e, phi); bezout # random
(1, 4460824882019967172592779313, -1667095708515377925087033035)
sage: d = Integer(mod(bezout[1], phi)) ; d # random
4460824882019967172592779313
sage: mod(d * e, phi)
1
因此，我们的RSA公钥是
而我们对应的私钥是
加密和解密¶
假设我们要对消息进行加扰 HELLOWORLD 使用RSA加密。从上面的ASCII表中，我们的消息映射到ASCII编码的整数，如下所示。
+----------------------------------------+
| H E L L O W O R L D |
| 72 69 76 76 79 87 79 82 76 68 |
+----------------------------------------+
将最后一个表中的所有整数连接起来，我们的消息可以用整数表示
还有其他更安全的加密方法可以将我们的消息表示为整数。上述过程仅用于演示目的，我们强烈反对在实践中使用。在Sage中，我们可以获得消息的整数表示，如下所示：
sage: m = "HELLOWORLD"
sage: m = [ord(x) for x in m]; m
[72, 69, 76, 76, 79, 87, 79, 82, 76, 68]
sage: m = ZZ(list(reversed(m)), 100) ; m
72697676798779827668
为了加密我们的消息，我们引发 m 对……的力量 e 并降低了结果的模数 n 。该命令 mod(a^b, n) 第一次计算 a^b 然后对结果进行模约简 n 。如果指数 b 是一个“大”整数，比方说超过20位，那么以这种幼稚的方式执行模幂运算需要相当长的时间。暴力(或幼稚)模幂运算效率低下，当使用计算机执行时，可能会迅速消耗大量计算机内存或导致消息溢出。例如，如果我们使用以下命令执行朴素的模幂运算 mod(m^e, n) ，在哪里 m ， n 和 e 如上所述，我们将收到类似于以下内容的错误消息：
mod(m^e, n)
Traceback (most recent call last)
...<ipython console> in <module>()
.../sage/rings/integer.so
in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:9650)()
RuntimeError: exponent must be at most 2147483647
There is a trick to efficiently perform modular exponentiation, called
the method of repeated squaring, cf. page 879 of [CormenEtAl2001].
Suppose we want to compute a^b mod n. First, let
d mathrel{mathop:}= 1 and obtain the binary representation of b,
say (b_1, b_2, dots, b_k) where each b_i in ZZ/2ZZ. For
i mathrel{mathop:}= 1, dots, k, let
d mathrel{mathop:}= d^2 mod n and if b_i = 1 then let
d mathrel{mathop:}= da mod n. This algorithm is implemented in
the function power_mod. We now use the function power_mod to
encrypt our message:
sage: m = 72697676798779827668
sage: e = 1850567623300615966303954877
sage: n = 4951760154835678088235319297
sage: c = power_mod(m, e, n); c
630913632577520058415521090
因此， c = 630913632577520058415521090 是密文。为了恢复我们的明文，我们引发 c 对……的力量 d 并降低了结果的模数 n 。同样，我们在解密过程中通过重复平方使用模幂运算：
sage: m = 72697676798779827668
sage: c = 630913632577520058415521090
sage: d = 4460824882019967172592779313
sage: n = 4951760154835678088235319297
sage: power_mod(c, d, n)
72697676798779827668
sage: power_mod(c, d, n) == m
True
请注意，在最后一个输出中，值72697676798779827668与表示原始消息的整数相同。因此，我们恢复了我们的明文。
确认¶
2009年07月25日：加州大学伯克利分校数学系的罗恩·埃文斯在最大公约数的定义中出现了一个打字错误。修订后的定义纳入了他的建议。
2008年11月04日：马丁·阿尔布雷希特(伦敦大学皇家霍洛威信息安全小组)、约翰·克雷莫纳(华威大学数学研究所)和威廉·斯坦(华盛顿大学数学系)审阅了本教程。他们的许多宝贵建议都被纳入了这份文件。
目录学¶
科尔曼，C.E.Leiserson，R.L.Rivest，C.Stein。 Introduction to Algorithms 。麻省理工学院出版社，美国，2001年第2版。