第十六章：三次通行协议
本章内容包括
- 基于指数的三次通行协议
- 基于矩阵乘法的三次通行协议
- 基于双边矩阵乘法的三次通行协议
第 2.2 节和第 2.3 节描述了现代密码学分为 3 个分支，即秘密密钥、公钥和个人密钥。到目前为止，本书仅描述了秘密密钥密码学的方法。公钥密码学在许多书中有描述，因此这里不会涉及。本章将讨论个人密钥密码学，这是密码学的较不为人知的第三个分支。个人密钥密码学有时被称为无密钥密码学，因为各方不需要传输或共享任何密钥。
个人密钥密码学的基本概念是，两个通信者 Sandra 和 Riva 各自有自己的个人密钥。这个密钥永远不会被传输或与任何其他人共享，甚至不会与彼此共享，因此没有可能通过窃听、拦截广播或任何其他形式的窃听来了解任何个人密钥。个人密钥密码学的巨大优势是你不需要提前设置任何东西。不需要有任何秘密、安全的通道来交换密钥。消息可以在公共通道上交换。不需要密钥服务器或其他基础设施。
个人密钥密码学是通过三次通行协议实现的，该协议是由以色列魏茨曼学院的阿迪·沙米尔于大约 1975 年发明的。为了说明这种方法，我想出了一个小故事：
曾经有一位国王爱上了邻国的女王。为了追求女王，国王希望送她一颗珍贵的宝石。国王有一个坚固的保险箱和一个防拆锁。但是他怎么能送钥匙呢？如果信使既有钥匙又有保险箱，他就可以打开箱子并偷走宝石。国王可以用第二位信使送钥匙，但他担心两位信使会在途中相遇并一起偷走宝石。女王提出了一个巧妙的解决方案。
国王会在保险箱上放上他的锁，并将其发送给王后。然后她会添加自己的锁，并带着两把锁把保险箱送回来。国王然后用自己的钥匙取下他的锁，并只带着王后的锁把保险箱送回来。然后她可以用自己的钥匙打开箱子并拿到宝石。
这里的两把锁代表两个加密，两把钥匙代表相应的解密。消息将使用发送者的加密函数加密，发送给接收者，使用接收者的加密函数加密，发送回发送者，使用发送者的解密函数解密，发送回接收者并使用接收者的解密函数解密。这意味着消息发送了 3 次，因此称为三次通行协议。
*****让我们来分解一下。假设消息是 M，Sandra 的加密和解密函数分别是 S 和 S’，Riva 的加密和解密函数分别是 R 和 R’。在第一次传递中，Sandra 用她的加密函数 S 加密消息 M 并将 SM 发送给 Riva。在第二次传递中，Riva 用她自己的加密函数 R 加密消息 SM 并将双重加密消息 RSM 发送回 Sandra。在第三次传递中，Sandra 将她的解密函数 S’应用于消息 RSM 以获得 S’RSM。这旨在去除 S 加密。只有当 R 和 S 可交换，或者 S’和 R 可交换时，才能实现这一点。这意味着 S’RSM = RS’SM = RM。这使得 Riva 可以去除她的加密并读取消息。
因此，为了使这个三次传递方案起作用，我们需要找到一个可交换的加密函数，或者两个彼此可交换的加密函数。我能立刻想到 3 个可交换的加密函数：加法、乘法和异或。很容易想象出一种加密方式，其中密钥与消息长度相同，加密包括逐字节将密钥加到消息中，或将消息字节乘以密钥字节，或将消息与密钥进行异或。这些都是一次性密码的简单形式。
这些都不安全。如果 Emily 设法获取所有三条加密消息，她可以轻松地去除加密。如果函数是加法，那么 3 条消息分别是 M+S、M+S+R 和 M+R。如果 Emily 将第一条和第三条消息相加，然后减去第二条消息，她会得到(M+S)+(M+R)-(M+S+R) = M。结果正是 M。当加密函数是乘法时，同样的方法也适用。3 条消息分别是(M×S)、(M×R)和(M×S×R)。再次进行(M×S)×(M×R)÷(M×S×R)运算得到 M。当加密函数是异或时，找到 M 甚至更简单，因为异或是其自身的逆运算。只需将 3 条加密消息进行异或运算，结果就是原始消息，(M⊕S)⊕(M⊕R)⊕(M⊕S⊕R) = M。
可交换的两个加密函数是替换和置换。这些也是不安全的。由于 Emily 会看到置换前后的消息，她可以轻易确定置换。
所需的是一对可交换的加密函数 S 和 R，使得即使 Emily 拥有 SM、RSM 和 RM，她也无法确定 M。
16.1 Shamir 的方法
Shamir 解决这个问题的方法是使用指数。设 p 是一个大素数，比如在 300 到 600 位十进制数字范围内。Sandra 将选择一个加密指数 s。相应的解密指数是 s’，使得 ss’≡1 (mod p-1)。这是根据费马小定理得出的，如果 0s)r = M^(sr) = M^(rs) = (Mr)s。
Sandra 计算(M^s mod p)并将其发送给 Riva。Riva 计算(M^(sr) mod p)并将其发送回 Sandra。Sandra 计算(M^(srs)’ mod p) = (M^r mod p)并将其发送回 Riva，最终 Riva 计算(M^(rr)’ mod p) = M，这就是原始消息。这种方法被认为是安全的，因为确定 s 或 r 需要解决离散对数问题。正如第 14.4 节所讨论的，这个问题被认为在计算上是困难的。目前没有已知的可计算的算法。
这种方法非常慢。所有这些大数的指数运算和模数减少需要大量计算。下一节描述了一种解决方案的尝试。
16.2 Massey-Omura
Massey-Omura方法是由 ETH Zurich 的 James Massey 和 UCLA 的 Jim K. Omura 于 1982 年发明的。（他的名字在专利上列为 Jimmy Omura。他是我在 MIT 的同学，尽管我不记得他。）Massey-Omura 系统与 Shamir 系统本质上相同，只是模数的形式为 2^k。这意味着模 2^k 的余数可以通过简单地取数字的低 k 位来计算。这比计算模 p 的余数要快得多，后者基本上是通过使用这些 300 到 600 位数字进行长除法来完成的。
哪种方法更快的问题在几年来一直在计算机协会（ACM）和电气电子工程师学会（IEEE）的出版物中激烈讨论。
16.3 离散对数
Diffie-Hellman 密钥交换、Shamir 三次协议和 Massey-Omura 方法的安全性都取决于解决离散对数问题的难度。解决这个问题的三种流行算法是穷举枚举，适用于 10¹²，Daniel Shanks 的 baby-step giant-step 算法，适用于 10¹⁸，以及 John Pollard 的 rho 算法，适用于 10²²。然而，我们需要一个适用于 10³⁰⁰的算法。为了让人们对离散对数问题的困难有所了解，让我们看看一个解决它的复合方法。这不是你可以在家用个人电脑完成的事情。这需要一个具有大量存储空间的大型计算机，或者一个由许多个人合作工作的网络。或者，你可以跳过这一部分，只是接受离散对数问题是困难的。
16.3.1 对数
首先考虑在计算机出现之前人们如何计算普通对数。一种方法是取一个数字 b = 1.000001，费力地计算它的连续幂。你会发现 b⁶⁹³¹⁴⁸是最接近 2 的幂，而 b²³⁰²⁵⁸⁶是最接近 10 的幂。然后你会知道 log10 几乎是 693148/2302586，即 0.3010302。正确值是 0.3010300，所以这种方法给出了一个很好的近似值。
您可以在一个环中进行相同的操作，比如取模某个素数 p。假设桑德拉发送消息 6 模 13，里瓦返回消息 7 模 13。艾米莉想知道里瓦使用了什么指数进行加密。与其使用 1.000001 的幂，不如使用模 13 的一个原根，比如 2。由于模数较小，艾米莉可以轻松列举出模 13 的所有 2 的幂。
现在艾米莉知道桑德拉发送了 2⁵，里瓦回复了 2¹¹。所以 (2⁵)r≡2(5r)≡2¹¹ (mod 13)。这意味着 5r≡11 (mod 12)。您可以在脑海中解决这个问题。只需想想 11+12 = 23，23+12 = 35。由于 35 是 5 的倍数，即 5×7，这意味着 r 必须是 7。您可以用手计算器检查，6⁷ = 279936≡7 (mod 13)。桑德拉发送了 6，里瓦回复了 7，所以这是正确的。
16.3.2 素数的幂
艾米莉通过穷举法可以找到一种搜索方法，但是当 p 很大时，这种方法行不通。让我们尝试约翰·波拉德的ρ 算法中的一个思想。第一步是生成模 p 的多个幂序列，并寻找重复项。艾米莉可以同时使用多个原根进行这样的操作，每个核心一个原根。现在我们来把它加倍。如果 b 是模 p 的一个原根，她可以在一个处理器上计算出 b²、b³、b⁴、b⁵… (mod p)，在另一个处理器上计算出 b²、b⁴、b⁸、b¹⁶… (mod p)。这给了艾米莉每个使用的原根两个单独的幂序列。
除了原根，艾米莉还可以直接检查。桑德拉发送 SM，里瓦回复 RSM。艾米莉可以生成序列 (SM)²、(SM)³、(SM)⁴、(SM)⁵… 和 (SM)²、(SM)⁴、(SM)⁸、(SM)¹⁶…，以及 RSM 的类似序列。这给了艾米莉另外四个幂序列。
除了这些有序的幂序列之外，她还可以生成一些无序的序列。这些通常被称为随机游走或醉汉游走。一种方法是对生成的最后一个幂进行平方，然后将其乘以之前的某一个幂。艾米莉可以随机选择早期的幂，或者她可以使用列表的中间元素。例如，假设她已经有了幂 x、x²、x⁴、x⁸ 和 x¹⁶。对于下一个幂，她可以对 x¹⁶ 进行平方得到 x³²，然后乘以，比如说，x² 得到 x³⁴。对于下一个幂，她会对 x³⁴ 进行平方得到 x⁶⁸，然后再乘以另一个列表元素，比如说 x⁸，得到 x⁷⁶。依此类推。
艾米莉可以生成另一种随机游走，使用 2 或 3 个基本素数。每个基本素数应该是一个原根。从这些素数的乘积开始。要生成下一个乘积，她会随机选择其中一个素数并将其乘以。艾米莉拥有的序列越多，她就越快地开始得到结果。
16.3.3 崩溃
好了，现在艾米莉有了所有这些序列。然后呢？她在两个列表上寻找相同的数字。这被称为碰撞或崩溃。假设她发现 3¹⁷²⁹⁶⁴≡103⁴²⁹⁸⁷⁵⁵ (mod p)。通过解决同余式 172964r≡4298755 (mod p-1)，这使得她能够将 103 表示为 3 的幂（模 p）。该方法在第 15.4 节中描述。一旦她积累了足够的崩溃，她就可以建立一个链，例如 RSM≡19^a, 19≡773^b, 773≡131^c, … , 103y≡(SM)z。将所有指数模 p-1 相乘，她将得到 RSM≡(SM)^r (mod p)。这个指数 r 就是瑞娃的加密函数。艾米莉破解了密码！
这并不像听起来那么简单。当 p 是一个 300 位数素数时，她需要大约 10¹⁵⁰个这样的幂才能开始看到任何崩溃。如果艾米莉有 100 万个处理器，每秒产生 100 万个这样的幂，她可能每年就可以生成 3×10¹⁹个。这意味着她需要大约 10¹³⁰年才能开始看到任何结果，直到她能建立这样一个链为止。此外，它将需要 10¹⁵⁰个字节的存储的倍数。
16.3.4 因式分解
不是每次生成新的幂时都要搜索崩溃，艾米莉可以尝试对其在模 p 下的残留进行因式分解。假设她成功地对 97^a (mod p)的残余进行了因式分解，并找到了 97a≡11b29c83d (mod p)。她可以解这个同余式得到 97。设模 p-1 的 a 的乘法逆元为 a’。将同余式提升至 a’次幂。97(aa)'≡97≡(11b29c83d)^a’ (mod p)。将所有指数相乘并将它们减去模 p-1，结果是 97≡11e29f83^g (mod p)，其中 e、f 和 g 是一些值。（如果 p 有 300 位数字，实际值可能长达 300 位数字。）一旦她得到了一个质数基的表达式，比如说 97，在所有已经有和以后会找到的因式乘积中都可以替换这个值。
艾米莉将无法对每个幂的残留进行因式分解。对一个 300 位数进行因式分解非常困难，也就是说非常耗时。最好的策略是选择一个固定的质数基集 F(B)，比如说所有小于 B = 10⁶的质数，或者也许是所有小于 B = 10⁷的质数。F(B)被称为因子基。尝试仅使用因子基中的质数对每个幂进行因式分解。可以用这种方式进行因式分解的数字称为B-平滑。随着数字变大，B-平滑数字的比例会变得越来越小。在 300 位数中，B-平滑数很少见。当艾米莉找到每个因子时，数字的未因式分解部分就会减少。如果她已经尝试了基础集中的所有质数，数字的一些未因式分解部分仍然存在，她就不应再尝试进一步因式分解它。放弃这个幂并继续下一个幂会更有效率。
这就是 Emily 必须做的事情：继续生成产品并对它们对 p 取余的结果进行因式分解。仅保留 B-smooth 数字并丢弃其余。检查 B-smooth 数字中的崩溃情况。每次发现崩溃时，解决乘积中最大质数的同余式，以便需要越来越少的基本质数来表示每个乘积。她可以保留一个或多个专用于此任务的处理器。
假设 q^n 是一个质数的幂，并且其模 p 的剩余为 x。尝试使用基本集 B 中的质数因式分解 x。如果 x 不是 B-smooth，则尝试因式分解数 x+p，x+2p，x+3p，…。因式分解一个 301 位数或 302 位数的数并不比因式分解一个 300 位数的数更难。设置一个固定数量的这样的尝试，比如说，对于每个剩余设置 10 次尝试。
当她生成这些幂时，她需要特别强调 SM 和 RSM。记住，这个练习的目标是找到指数 r，使得(SM)^r≡RSM (mod p)。她在将 SM 和 RSM 都表示为基本质数的幂之前是无法做到的。首先，她应该开发出多个 SM 和 RSM 幂的序列。一旦她成功找到这样的表达式，她就会寻找表达式中尚未用较小质数的幂表示的质数。接下来重点放在这些质数上。继续直到 SM 和 RSM 都表示为单一质数的幂。她现在可以使用第 15.3.2 节的方法找到 r。
16.3.5 估算
假设她使用了 10⁶ 个基本质数，也就是说，质数达到了 B = 15,485,863。要将所有这些表示为单一质数将需要 10⁶ 个同余式。存储这些需要一个 10⁶×10⁶ 的指数矩阵。矩阵最初是稀疏的，但随着解决方案的进展而变得稠密，因此稀疏矩阵技术将不会有益。每个指数是一个 300 位数。这需要大约 10¹⁵字节，或 1 个petabyte的存储空间。截至撰写本文时（2022 年 3 月），世界上最大的超级计算机是位于奥克里奇国家实验室的 Summit 计算机，拥有 2.76 petabytes 的可寻址存储空间。
显然，运行时间取决于找到 B-smooth 数字需要多长时间。B-smooth 数字的密度由 de Bruijn 函数Ψ(p,B)给出，它给出了小于 p 的 B-smooth 整数的数量。这由荷兰数学家尼古拉斯·戈弗特·德布鲁因研究过。Ψ(x,x^(1/u))的值由精算师卡尔·迪克曼发明的迪克曼函数ρ(u)近似，其中ρ(u)是迪克曼函数。迪克曼函数ρ(u)由 u^(-u)近似。在这种情况下，x = 10³⁰⁰和 x^(1/u) = 15,485,863，所以 u = 41.725。因此，大约需要大约 41.725^(41.725) = 4.08×10⁶⁷次尝试才能找到每个 B-smooth 数字。
总的来说，将需要超过 10⁷³ 次尝试来找到 10⁶ 个 B-平滑幂。对每个数字进行因数分解可能需要多达 10⁶ 次试除，因此总共需要 10⁷⁹ 次试除。由于数字有 300 位，每次试除将需要 300 倍的操作。总共是 10⁸² 次操作。这比崩溃法的 10¹⁵⁰ 有了巨大的改进，但对于当前的计算机仍然是不可及的。
这表明对于可预见的未来，300 位数字已经足够了，也许可以维持 20 到 30 年。随着量子计算机的发展，这可能会改变，但目前 300 位数字是安全的。
16.4 矩阵三次传输协议
用于三次传递算法的 Shamir 和 Massey-Omura 方法都使用了指数运算。三次传递算法的另一种方法是使用矩阵。我们之前已经见过这种情况，比如 Hill 密码，第 15.1 节。消息被分成块。每个块被视为模 256 的整数向量。这个向量被一个模 256 的可逆方阵左乘或右乘。对于三次传递版本，Sandra 将有一个用于加密的矩阵 S 和其逆矩阵 S’，而 Riva 将有一个加密矩阵 R 和解密矩阵 R’。这些矩阵不是在模 256 整数上，而是在一个 256 个元素的环R上，消息的字符被视为该环的元素。假设消息块为 M，所以 Sandra 发送 SM 给 Riva，Riva 将 RSM 返回给 Sandra，Sandra 使用 S’ 解密以获得 S’RSM = RM。现在 Riva 可以使用 R’ 解密它，即 R’RM = M。
棘手的部分是使 S’RSM = RM。矩阵乘法不可交换，所以 Sandra 和 Riva 需要选择彼此可交换的特殊矩阵 S 和 R。明确地说，S 和 R 不是可交换矩阵。如果你随机选择一个矩阵 X，几乎可以肯定 SX ≠ XS 和 RX ≠ XR。这是一个重要的观点，所以让我重复一遍，S 和 R 不是可交换矩阵。它们不与大多数其他矩阵可交换。它们彼此可交换。
16.4.1 可交换矩阵族
Sandra 和 Riva 需要大量的这些矩阵，这样 Emily 就不能简单地尝试它们所有。这意味着他们需要一个大的可交换矩阵族Ғ，从中选择每个消息块的矩阵。
注意Ғ是一个可交换的矩阵族，而不是一组可交换的矩阵。重要的是要理解，可交换的是矩阵族，而不是矩阵本身。Ғ中几乎所有的矩阵都不可交换。它们彼此可交换，但与其他矩阵不可交换。
构造可交换矩阵族的最简单方法是从任意可逆矩阵 F 开始，并取其幂，F⁰、F¹、F²、F³、…，其中 F⁰ 是单位矩阵 I，而 F¹ = F。将 F 称为Ғ族的生成矩阵。
Sandra 和 Riva 每个消息块都需要使用不同的矩阵，否则 Emily 可能会在已知明文的足够消息块 M[i] 的情况下解出线性方程组 R(SM[i]) = RSM[i]。
16.4.2 乘法阶
要使Ғ族变得更大，你需要找到或构造一个具有很高乘法阶的生成矩阵 F。也就是说，需要找到一个最小的整数 n > 0，使得 F^n = I，至少要大于 10^（25），但最好更大。如果矩阵 F 是可逆的，这样的 n 总是存在的，并且 F 的乘法逆 F’ 是 F^(n-1)。在第 15.8 节中给出了一种寻找可逆矩阵的方法。确定 F 的乘法阶有点艺术性。显然，一直计算 F 的连续幂直到 F^n = I 是不可行的，特别是当 n > 10^（25）时。但这是可以做到的。
要找到乘法阶，从 1×1 矩阵开始，即环元素。查看这些元素的乘法阶。这些可以通过枚举轻松找到，因为 n 的最大可能值是 255。可能的值是 2、3、7、15、31、63、127 和 255。更大矩阵的乘法阶往往是这些值的倍数。
假设环元素的乘法阶恰好是 2、7 和 31。当你尝试 2×2 矩阵时，首先将每个矩阵 A 提升到单元素阶的某个倍数，比如 2⁴7²31 = 24304。然后枚举 B = A²⁴³⁰⁴ 的幂。假设你发现 B⁵² = I。你现在可以确定 A 的乘法阶 m 能够整除 x = 24304×52 = 2⁶7²13×31，且是 2⁶13 的倍数。接下来应该尝试 A^(x/7) 和 A^(x/31) 看看它们是否为 I。如果 A^(x/7) 是 I，那么你就尝试 A^(x/49)。在这种情况下，最高的乘法阶可能是 2⁶7×13×31。
接下来你要处理 3×3 矩阵。如果除了 2、3、7、13 和 31 之外，2×2 矩阵的乘法阶中没有其他质因数出现，那么一个好的起始指数可能是 x = 2⁸7²13²31²。枚举 B = A^x 的连续幂，并重复缩小指数的过程。随着矩阵变大，乘法阶可能会增加一个无法通过枚举找到的因子。在这种情况下，你将需要猜测新的可能出现的质因数。
注意乘法阶序列中出现的模式。这需要一些侦探工作。例如，假设出现了 2³-1、2⁶-1、2⁹-1 和 2¹²-1。你不会直接看到这些，因为它们不全是质数。2⁶-1 = 63 = 3²7，2⁹-1 = 511 = 7×73 和 2¹²-1 = 4095 = 3²5×7×13。所以在质因数中找到 13 是指向“真正”因数可能是 2¹²-1 的线索，而找到 73 则强烈表明 2⁹-1 是一个因数。如果出现了 2³-1、2⁶-1、2⁹-1 和 2¹²-1，你应该期待很快出现 2¹⁵-1。如果这些全部出现，它们都可以被 7 整除，所以乘法阶将被 7⁴ 整除。
16.4.3 最大阶
艾米莉在这一切中的目标是尽可能地扩大家族Ғ，这样她和里娃就有很多选择来选择他们的矩阵 S 和 R。一个有用的技巧是观察因子集合之间的乘法阶数差异。例如，如果 A 的乘法阶数为 19m，B 的乘法阶数为 23m，那么 AB 的乘法阶数很可能是 19×23m=437m。如果这不起作用，那么 A’B 或 AB’可能具有乘法阶数 437m。
如果可能的话，桑德拉应该选择一个生成矩阵 F，其乘法阶数具有一个大素数因子，比如m > 1 0 35 m > 10^{35}m>1035，以防止 Silver-Pohlig-Hellman 攻击（第 14.4 节）。桑德拉需要对各种n nn进行因式分解2 n − 1 2^n-12n−1，找到具有大素数因子的那些，并尝试用逐渐增大的矩阵找到一个乘法阶数可被其中一个2 n − 1 2^n-12n−1整除的生成矩阵。
16.4.4 艾米莉的攻击
假设桑德拉已经选择了 F 和Ғ，并且她已经向里娃发送了一条消息。由于桑德拉和里娃正在通过公共信道进行通信，比如互联网，假设艾米莉知道 F、Ғ、SM、RSM 和 RM。她的目标是找到 R 或 S，所以她有两次机会。让我们集中讨论艾米莉如何找到 R。艾米莉知道关于 R 的两件事。首先，她知道 SM 和 RSM 的值，这给了她 n 个线性方程，这些方程是关于 R 的n 2 n²n2个未知元素的。其次，她知道 R 在家族Ғ中，所以它必须与 F 交换，即 RF = FR。如果环R是可交换的，那么这给了她 n(n-1)个关于 R 的n 2 n²n2个元素的附加线性方程。
这有效的原因是矩阵方程 RF = FR 的左侧产生了形式为r f r frf的项，其中r rr是 R 的未知元素，f ff是 F 的已知元素。右侧产生了形式为f r f rfr的项。由于环是可交换的，左侧项r f r frf可以转换为形式f r f rfr，并与右侧项组合形成线性方程。
在n 2 n²n2个未知数的n 2 n²n2个线性方程中解决这些线性方程并找到R RR似乎很容易。但事实并非如此。回顾第 15.3.1 节，我们知道有强同余和弱同余。对于任何不是素数的有限环上的线性方程，情况也是如此。环大小有多少素因子，就有多少潜在的弱方程。在当前情况下，环大小为2 8 2⁸28，有 8 个素因子，所以许多线性方程很可能是弱方程。如果环R选择得当，矩阵的典型大小可能是 30×30，或者 128×128，甚至 256×256，如果环的选择不佳。即使选择了合适的环，即使一半的方程是强的，你也会期望至少有2 450 2^{450}2450个解集合的 30×30=900 个方程。实际上，解的数量要多得多，因为可能有 4、8 或甚至 16 个解的方程。
Emily 有个好消息。Emily 可以解决 R’ 而不是 R，而她得到的那 2⁴⁵⁰ 或更多的解中的任何一个都将是 R 的有效逆，让她通过 R’RM = M 获得消息。
密钥密码学（三）(2)https://developer.aliyun.com/article/1508611
