数论与RSA公钥密码体制¶
本教程使用Sage学习基本数论和RSA公钥密码体制。我们将介绍一些Sage命令来帮助我们执行基本的数论运算，例如最大公约数和Euler的phi函数。然后我们介绍了RSA密码系统，并使用Sage的内置命令通过RSA算法对数据进行加密和解密。请注意，本教程仅用于教学目的。有关密码学或各种密码系统的安全性的更多详细信息，请参阅诸如 [MenezesEtAl1996], [Stinson2006], 和 [TrappeWashington2006].
初等数论¶
我们首先回顾初等数论中的基本概念，包括素数、最大公约数、同余和欧拉φ函数的概念。介绍的数论概念和Sage命令将在后面介绍RSA算法时参考。
素数¶
公钥密码术使用了数论中的许多基本概念，如素数和最大公约数。正整数 n > 1 据说是 首要的 如果它的因子是唯一的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 是整数，而不是都是零。最大公约数 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 是 互质 （或相对最好的）到 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 是 一致的 到 b 模 n 并用
这个定义相当于说 n 除以 a 和 b ，即 n ;|; (a - b) . 因此 23 equiv 8 pmod{{5}} 因为当23和8都除以5时，我们得到了3的余数。命令 mod 允许我们计算这样一个余数：
sage: mod(23, 5)
3
sage: mod(8, 5)
3
欧拉φ函数¶
考虑从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] 是20的互质。没有显式生成列表
1 3 7 9 11 13 17 19
我们如何计算 [1, 20] 是20的互质吗？这就是欧拉φ函数派上用场的地方。让 n in ZZ 积极点。那么 欧拉φ函数 计算整数的数目 a 用 1 leq a leq n ，这样 gcd(a,n) = 1 . 这个数字用 varphi(n) . 欧拉的φ函数有时被称为欧拉的函数，因此得名 totient.sage 为了上面的Sage手稿。命令 euler_phi 实现Euler的phi函数。计算 varphi(20) 在不显式生成上述列表的情况下，我们继续如下操作：
sage: euler_phi(20)
8
如何保守秘密？¶
密码学 是隐藏数据的科学（有人可能会说是艺术）。想象一下我们正在给某人写一封机密电子邮件。写完邮件后，我们可以用两种方式之一发送。第一种，通常也很方便的方法是，只需按“发送”按钮，而不关心我们的电子邮件将如何发送。以这种方式发送电子邮件类似于将我们的机密信息写在明信片上，然后在不将明信片装入信封的情况下邮寄出去。任何能看到我们明信片的人都可以看到我们的留言。另一方面，在发送电子邮件之前，我们可以对机密信息进行置乱，然后按“发送”按钮。扰乱我们的信息类似于把明信片装在信封里。虽然不是100%安全，但至少我们知道，任何人想看我们的明信片必须打开信封。
用密码学的说法，我们的消息被称为 明文 . 对我们的信息进行置乱的过程称为 加密 . 加密我们的消息后，加密后的版本被调用 密文 . 从密文中，我们可以通过 解密 . 下图说明了加密和解密的过程。A 密码系统 由一对相关的加密和解密过程组成。
+ ---------+ 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 |
+----------------------------------------------------+
正式地，让
是英语字母表中的一组大写字母。再者，让
是美国信息交换标准代码（ASCII）的大写英文字母编码。然后上表明确地描述了映射 f: Sigma longrightarrow Phi . （对于熟悉ASCII的用户， f 实际上是 编码 要素 Sigma ，而不是加密的“置乱”过程 本身 ）对用字母表写的信息进行置乱 Sigma ，我们只需将消息的每个大写字母替换为其对应的ASCII编码。然而，上表中描述的加扰过程从密码学的角度讲几乎没有安全性，我们强烈反对在实践中使用它。
用两把钥匙保守秘密¶
Rivest，Shamir，Adleman（RSA）密码体制就是一个例子 公钥密码系统 . RSA使用 公钥 要加密消息和解密，使用相应的 私钥 . 我们可以分发我们的公钥，但出于安全原因，我们应该将私钥留给自己。加密和解密过程借鉴了初等数论的技术。以下算法改编自第165页，共页 [TrappeWashington2006]. 它概述了RSA加密和解密的过程。
选择两个素数 p 和 q 让 n = pq .
让 e in ZZ 积极地 gcd big( e, varphi(n) big) = 1 .
为计算值 d in ZZ 这样的话 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 被称为 梅森数 . 如果 p 是质数和 M_p = 2^p - 1 也是最好的 M_p 被称为 梅森素数 . 例如，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算法的第一步：
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] .
我们可以计算出价值 varphi(n) 通过调用sage函数 euler_phi(n) ，但是对于任意大的素数 p 和 q ，这可能需要大量的时间。实际上，一旦知道了私钥，就可以很快地从公钥中推导出私钥 varphi(n) 因此它是RSA密码体制安全性的重要组成部分 varphi(n) 不能在短时间内计算，如果 n 是已知的。另一方面，如果私钥可用，我们可以计算 varphi(n)=(p-1)(q-1) 在很短的时间内。
使用一个简单的编程循环，我们可以计算 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)}} 等于
在哪里？ k in ZZ . 从步骤1和步骤2中，我们已经知道 e 和 varphi(n) . 扩展的欧几里德算法允许我们计算 d 和 -k . 在Sage中，这可以通过命令完成 xgcd . 给定两个整数 x 和 y ， xgcd(x, y) 返回一个三元组 (g, s, t) 满足贝佐特的身份 g = gcd(x,y) = sx + ty . 计算了 d ，然后使用命令 mod(d*e, phi) 去检查一下 d*e 确实与1模同余 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)
/home/mvngu/<ipython console> in <module>()
/home/mvngu/usr/bin/sage-3.1.4/local/lib/python2.5/site-packages/sage/rings/integer.so
in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:9650)()
RuntimeError: exponent must be at most 2147483647
有一个技巧可以有效地进行模幂运算，称为重复平方法，参见第879页，共页 [CormenEtAl2001]. 假设我们要计算 a^b mod n . 首先，让 d mathrel{{mathop:}}= 1 并得到 b 说 (b_1, b_2, dots, b_k) 每一个 b_i in ZZ/2ZZ . 为了 i mathrel{{mathop:}}= 1, dots, k ，让 d mathrel{{mathop:}}= d^2 mod n 如果 b_i = 1 那就让 d mathrel{{mathop:}}= da mod n . 该算法在函数中实现 power_mod . 我们现在使用函数 power_mod 要加密我们的邮件：
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年7月25日：罗恩·埃文斯（UCSD数学系）报告了最大公约数的定义有误。修订后的定义纳入了他的建议。
2008年11月4日：Martin Albrecht（伦敦大学皇家霍洛威信息安全小组）、John Cremona（华威大学数学研究所）和William Stein（华盛顿大学数学系）回顾了本教程。他们的许多宝贵建议已纳入本文件。
参考文献¶
- CormenEtAl2001
T、 H.Cormen，C.E.Leiserson，R.L.Rivest和C.Stein。 算法概论 . 麻省理工学院出版社，美国，第二版，2001年。
- MenezesEtAl1996(1,2)
A、 J.Menezes，P.C.van Oorschot和S.A.Vanstone。 应用密码学手册 . CRC出版社，博卡拉顿，佛罗里达州，美国，1996年。
- Stinson2006(1,2)
D、 R.斯蒂森。 密码学：理论与实践 . 查普曼和霍尔/CRC，博卡拉顿，美国，第3版，2006年。
- TrappeWashington2006(1,2,3)
W、 特拉普和华盛顿特区。 密码理论概论 . 皮尔逊普伦蒂斯大厅，上鞍河，新泽西，美国，第二版，2006年。