密钥密码学（三）(3）https://developer.aliyun.com/article/1508613
18.9.3 模拟退火
模拟退火是一种流行的优化技术，主要是因为它很容易实现。你从搜索空间中的一个随机点开始，并查看附近的一个点。如果那个解更好，那么以概率 B 移动到该点。如果那个解更差，那么以概率 W 移动到该点。
模拟退火的定义特征是在搜索过程中改变概率。最初，你设定拒绝好解的机会或接受坏解的机会相当高。比如，你拒绝 40%的更好解，接受 30%的更差解，即 B = .6 和 W = .3。然后在一段时间后，比如 1000 步之后，你会降低拒绝好解的概率。也许在第二阶段，你拒绝更好解的 20%，接受更差解的 15%。再过一段时间，比如再 2000 步之后，你可能只开始拒绝更好解的 10%，接受更差解的 7%。
这个过程被称为模拟退火，因为它类似于金属热处理中的热退火过程，在这个过程中，金属首先被加热直到发光，然后非常缓慢地冷却。这改变了金属的结晶结构，减少了其硬度，增加了其韧性和延展性，使其更容易加工。在模拟退火中，拒绝更好解和接受更差解的高初始概率类似于金属的高温状态，而这些概率的逐渐降低则类似于金属的缓慢冷却。对模拟退火的描述通常提到概率逐步降低的几个阶段称为降温。
让我传授一些我在模拟退火中的经验：
- 过于缓慢是不值得的。每个阶段的接受/拒绝率应该在前一率的 1/2 到 2/3 之间。例如，第一阶段是 40%，然后 20%，10%，5%，3%。或者，从 40%开始，然后 25%，15%，10%，6%，4%，最后 2.5%。
- 通常五个阶段就足够了。
- 以 50%的接受率开始是浪费时间的。从 60%到 75%之间开始。
- 将接受率降到 0% 是得不偿失的。如果最后一个阶段接受了 2% 到 3% 的更差的解决方案，你将获得更大的改进。
- 当什么都不发生时停止。你可能计划在每个阶段进行 1000 次试验，但如果你已经进行了 100 次尝试而没有改变，就停止吧。
- 让百分比取决于改进的大小。例如，在第一阶段，你可以接受改进分数为 1% 的变化的 60%，改进分数为 2% 的变化的 75%，改进分数为 3% 或更多的变化的 90%。
- 实验。每个优化问题都是不同的。尝试改变阶段的数量、每个阶段的试验次数、改变概率的速率、步长和改进程度与接受率之间的关系。
爬山、千山万峰和模拟退火技术可以自由组合，产生各种混合方法。
18.10 量子模拟退火
有几种提议的方法可以利用量子计算机进行模拟退火。这些方法利用量子现象如叠加来并行执行许多搜索。然而，每次试验都需要在选择的点上评估目标函数。量子计算机不适用于评估表达式。到目前为止，尚无方法可以通过量子手段并行评估这些函数。量子计算机可以利用传统计算机来评估表达式，但这将失去并行性。到目前为止，量子搜索还没有显示出比传统计算机搜索更快的改进。
18.11 量子因式分解
RSA 公钥密码系统的强度取决于大整数因式分解的难度。给定两个大整数 A 和 B，将它们相乘得到乘积 AB 是很容易的，但要反向执行这个过程并确定大整数的因子则非常困难。对一个大数进行因式分解的难度与计算离散对数（第 16.3 节）的难度相同，并且使用许多相同的技术。
这种安全性可能会被用于因式分解大数的 Shor 算法突破。这是第一个量子算法，由 MIT 的 Peter Shor 在 1994 年发明。如果该算法能够成功地用于大整数，那么 RSA 必须被放弃，或者模数必须变得更大，也许是数百万位。到目前为止，使用 Shor 算法，2001 年将数字 15 因式分解为 3×5，2012 年将数字 21 因式分解为 3×7。按照这个速度，我们可以期待到 2023 年左右将数字 35 因式分解为 5×7。
开个玩笑，Shor 算法对 RSA 安全性的真正威胁可能要几十年后才会出现。
18.12 超级计算机
量子计算机并不是为了评估表达式而制造的——至少目前不是。但让我们假设这只是一个技术问题。假设将来会有混合计算机，结合了超级计算机的计算能力和量子计算机的并行性。让我们称这些为超级计算机。
桑德拉今天可以做些什么来为艾米莉拥有超级计算机的时代做准备？我们可以从我们击败格罗弗算法的方式中获得启示（第 18.6 节）。我们扩大了密钥的大小，超过了算法的能力。这在超级计算机上也是可行的。我们可以增加计算机需要处理的未知数的数量，超出您估计超级计算机可能具有的任何能力。让我们看看这两个方面，替换和随机数生成。
这些算法将需要极其庞大的加密密钥。让我们简单地接受，在未来存在超级计算机的世界中，这样巨大的密钥将是可管理的。
18.12.1 替换
如果一个替换没有通过某种数学规则定义，那么它可以通过一个替换表来定义。表中的每个条目是桑德拉知道但艾米莉不知道的值。每个表条目可以被视为数学意义上的一个变量。最初，每个变量可以取任何值。如果艾米莉学到了其中一些值，那么对其他变量的选择就会变得更加狭窄，但最初任何字符都可以替换为任何其他字符。
桑德拉的目标是压倒超级计算机的能力。一个通用的多表密码手动使用 26×26 的表格，但计算机使用 256×256 的表格。这提供了 2¹⁶，或者 65,536 个未知值。然而，并没有理由限制表格中的行数为 256。如果艾米莉有一个超级计算机，那么桑德拉也有一个速度快、内存大的计算机是合理的。桑德拉可以使用 1024 行带有 10 位密钥的表格，或者使用 4096 行带有 12 位密钥的表格，甚至使用 65536 行带有 16 位密钥的表格。这需要 2²⁴ = 16,777,216 字节的内部存储空间用于替换表，远远在当前个人计算机的容量范围内。此外，对于 8 位替换使用 16 位密钥提供了非常理想的冗余性。让我们称这个 2²⁴元素的表格为Tab24。Tab24 的每一行都有自己的混合密钥。如果这个混合密钥有 256 位，那么整个表格就有 256×65536 = 16,777,216 位密钥。
对于桑德拉来说，使用完整的双字母频率表也是可行的。一个 256×256 的双字母频率表，使用 8 位密钥选择一行（实际上是一层），需要 2²⁵ = 33,554,432 字节的内部存储空间。同样，这在今天是可行的。如果表格有 65536 层和 16 位密钥，那么将需要一个更大的计算机。
但请记住，这些替换表必须保密，并且必须是完全随机的。即使它们是由某种算法生成的，也必须绝对超出艾米莉的超级计算机确定生成器的初始状态和参数的能力。请参阅第 13.13 节了解一些相关方法。
18.12.2 随机数
第 13.13 节的方法是一个很好的起点，但要制作一个能经得起超级计算机考验的伪随机数生成器，我们将第 13.11 节的选择生成器概念与第 13.15 节的刷新生成器技术相结合。
超级生成器 UG（发音为 HUGE-ee）使用三个数组，A、B 和 C。数组 A 和 B 各包含 65,536 个条目，每个条目都是 24 位整数。数组 C 包含 2²⁴，即 16,777,216 个条目，每个条目都是 8 位整数。这 3 个数组可以从自然照片中初始化，如第 13.14.2 节所述。桑德拉和里瓦必须有相同的数组。生成器在每个周期中产生一个 8 位输出。第 n 个周期包括以下步骤：
- 计算 x = (A[n]+A[n-103]+A[n-1071]) mod 16777216，并将 A[n]替换为 x。
- 减少 x = x mod 65536，并设置 y = B[x]。
该周期内 UG 生成器的输出是 C[y]。 - 将 B[x]替换为(B[x]+B[x-573]+B[x-2604]) mod 16777216。
- 将 C[y]替换为(C[y]+C[y-249]+C[y-16774]) mod 256。
下标根据需要在模 65536 或模 16777216 下循环。103、1071、…、16774 这些滞后值并没有什么特别之处。我没有测试这些值是否产生特别长的周期。有了如此巨大的种子数组，即使是退化周期也会非常长。你可以使用第 13.1 节的任何组合函数，比如madd，或者第 13.14.1 节的滞后线性加法。
当你刷新这些随机数时，第 13.14 节的两种方法在你的对手拥有超级计算机时不足以使用，但它们可以结合起来制作一个强大的刷新函数。每次刷新时，你将需要一个包含 65,536 个或更多 24 位整数的新随机数组 R。让 A、B、C 和 R 的长度分别为 L[A]、L[B]、L[C]和 L[R]。
这里 a = ⌊L[C]/L[R]⌋-1。符号⌊L[C]/L[R]⌋，读作“L[C]/L[R]的底”，表示不超过 L[C]/L[R]的最大整数。例如，⌊8/3⌋是 2，⌊9/3⌋是 3。使用 C[an]而不是 C[n]的效果是将 R 的字节均匀分布在 C 数组中。
这两个步骤应该重复 3 次或更多次。如常，下标循环。
顺便说一句，C 数组的大小不一定必须是 2 的幂。L[C]可以是，例如，77,777,777，这种情况下 A、B 和 R 数组需要包含模 77777777 的整数，而模 16777216 将在上述计算中被 77777777 替换。对于 L[C]的大小的唯一限制是您希望使用的存储量以及分发如此大密钥的实际情况。
这两种技术，替换和随机数生成，可以结合起来制作任意数量的块和流密码，可以抵御超级计算机。接下来的两节介绍了每种类型的一种密码。
18.12.3 超替代密码 US-A
写这一节时的一个巨大诱惑是指定一个巨大的块大小，比如 65,536 甚至 16,777,216 字节。然而，仅仅因为在超级计算机时代加密必须改变，并不意味着消息的类型会改变。少于 100 个字符的消息仍然很常见，将这样的消息填充到 65,536 字节或更大的块大小将是极其低效的。
让我们将样本超替代密码称为US-A。US-A 密码以 32 字节或 256 位的块为单位运行。每个块中的 32 字节交替地被视为 32 个单独的字节和一个 16×16 位的位数组。US-A 密码有 15 轮，每轮包括 3 个步骤：替换、行置换和翻转数组。15 轮后跟着最后的替换步骤。
16 个替换步骤使用 Tab24 替换表，每个字符需要 16 个密钥位，每轮总共需要 16×32 = 512 位，或者 15 轮加上最后的替换需要 8192 位。每个 15 轮中的第二阶段是对每一行进行置换。这可能只是行的循环移位，每行只需要 4 位，因此每轮需要 64 位，总共 960 位。
对于位置换的更强选项是拥有一个置换表，比如 256 个不同的置换，比如密钥置换（第 7.6 节）。16×16 位矩阵的每一行将被单独置换。每行置换将由 16 个十六进制数字指定，比如5A3F1E940B2D68C7，意味着第一个位将移到位置 5，第二个位移到位置 A，即 10，依此类推。每行的置换将由一个 8 位密钥从表中选择，每轮需要 8×16 = 128 位，或者 15 轮总共需要 1920 位。
每轮的第三阶段是翻转位数组，即交换(i,j)处的位和(j,i)处的位。这在第 11.7 节中有描述，并且在第 11.2.3 节中给出了翻转数组的快速方法。这个阶段没有密钥。
让我们将所有 3 个阶段结合起来。US-A 密码需要 8192 位用于替换密钥，以及，比如说，1920 位用于密钥转置，总共是 10,112 位密钥。这远远不足以抵御超级计算机所需的 65,536 位。不用担心。别忘了，替换使用了 Tab24 表格，为了混合其 65,536 行，使用了 16,777,216 位密钥，更不用提用于混合置换表的比特数了。
为了额外的强度，我建议使用明文到明文（模式 PP）分块链接（第 11.10 节）与 US-A 密码。
18.12.4 超流密码 US-B
第 18.11.1 节的 Tab24 替换和第 18.11.2 节的伪随机数生成器可以结合起来制作一个强度极高的流密码。称其为US-B密码。US-B 在加密之前使用一个预处理步骤使明文具有随机外观。假设消息为 M，其长度为 L[M]。预加密步骤为
额外的 16 次循环迭代用于对消息的前 16 个字符进行双重哈希处理。这一步骤并不增加密码强度，但却使 Emily 很难辨认出她找到了正确的密钥。
每个 16 位字符密钥 K[n] 由随机数发生器生成的两个连续输出字节 x 和 y 组合而成，即 256x+y。（或者，你可以将 C 数组设为 16 位整数，但这会使所需存储空间翻倍。）密钥 K[n] 被用来在 Tab24 替换表中对消息字符 M[n] 进行加密，形式为 Tab24(K[n],M[n])。也就是说，M[n] 的替代字符取自表格的第 K[n] 行。
你可能会认出这是使用大型表格和随机密钥的通用多字母密码。请记住，法国人称多字母密码为不可破译的密码。使用 UG 超生成器，US-B 多字母密码最终在超级计算机时代也是不可破译的。我们已经实现了不可破解的加密。
附录 A：娱乐页面
这个图表中有四个独立的密码，从 S1 到 S4。每个密码都是一个简单的单表替换。你的任务是识别类型，比如摩斯码，然后解决它。每个密码都以标准英文书写，使用大写字母，不带空格或标点符号。每个密码长度介于 75 到 90 个字母之间。所有密码都从左上角单元格开始。前 3 个密码从左到右跨越行读取。最后一个密码按照顺时针方向沿着边界读取。
所有方法都在这本书中描述了。唯一的区别是视觉呈现方式。你需要确定每个密码中哪些特征是相关的，比如高度、宽度、位置或颜色。你可以按照本书其他地方隐藏的说明提交你的答案以获取学分。
这里有一些额外的有趣密码，使用了一些最流行的业余爱好者密码。这些密码是标准英文，带有一些专有名词。按照惯例，字母被分组为五个，不论周期。如果你想要更多类似的密码，可以考虑加入美国密码协会，网址为cryptogram.org。你可以按照本书其他地方隐藏的说明提交你的答案以获取学分。你可以在www.contestcen.com/crypt.htm找到更多要解决的密码。
F1：Belaso 密码（第 5.8.1 节）
F2：维吉尼亚密码（第 5.8.2 节）
F3：栏式置换（第 7.2 节）
F4：Playfair 密码（第 9.2 节）
F5：Bifid 密码（第 9.6 节）
区块大小为 7，主题是园艺。
F6：一次性密码本（第十四章）
对于消息中的每个字母，都生成一个随机数。如果这个数字是偶数，就对字母加上 X 对 26 取模，否则对 Y 对 26 取模。
当然，一次性密码本不是一种业余爱好者密码。我把它包括在内是为了说明一些一次性密码本密码在实践中是可以被破解的。你能看出如何找到 X 和 Y 的值而不尝试所有 676 种组合吗？
F7：通用多表密码（第 5.9.3 节）
为了增加乐趣，还有来自几种语言的字符，并且使用了超过 26 个字符。然而，每个字母表只包含了 26 个不同的字符，并且消息是标准英文。
附录 B：挑战
这些密码图被呈现给读者作为挑战。 方法未给出。 您的任务是确定方法并解决密码图。 提供了足够的材料，以便已确定方法的有经验的业余爱好者可以解决它。 在所有情况下，语言都是英语。 文本读起来正常且符合语法。 没有特别努力来扭曲标准英语字母频率或联系频率。
这些都是单步密码。 没有混合方法，比如将替换与置换相结合。 这些挑战密码被评为三级。
C1: 挑战 #1
这是一种纸笔密码。 明文由 250 个大写字母组成，没有单词间隔或标点符号。
C2: 挑战 #2
这个密码可以手工解密，但使用一些计算机辅助来管理十六进制表示会更容易。 明文由混合大小写的 200 个字符组成，带有单词间隔和标点符号。
C3: 挑战 #3
这个密码可以手工加密和解密。 明文由 180 个大写字母组成，没有单词间隔或标点符号。
第十九章：总结
这本书介绍了大约 140 种不同的密码，以及无数的变体。这可能会使一些读者困惑。他们可能只想知道一件事：“对我来说什么是最好的密码？”这个问题很复杂，因为这本书是为如此广泛的读者群体而设计的。在这个结语中，我希望提供一些有用的答案。
儿童：这里有几种儿童可以理解和使用的密码。他们可以使用简单的替换密码，尤其是凯撒密码。儿童特别喜欢字母被图片或符号替换的密码，比如🙂☽♡⚇⚓🎾🧙☼◈☆。儿童也喜欢路径置换。青少年可能会喜欢列置换和贝拉索密码。
爱好者：爱好者可能会喜欢与朋友交换密码，挑战彼此解密。最适合这样做的密码是简单替换、多表替换、自动密钥、流动密钥、Playfair、双密码、对角双密码、三密码、双方密码、路径置换、列置换、巴泽里斯和分数莫尔斯。
我鼓励爱好者加入美国密码协会，www.cryptogram.org，在那里他们可以提交他们的密码供其他会员解决，并解决其他会员提交的密码。他们的网页www.cryptogram.org/resource-area/cipher-types/列出了他们接受的密码类型。
开发者：想要开发或发明自己的密码的人会在这里找到许多方法，这些方法可以以无数种方式组合。字母可以被其他字母替换，或者被固定长度或可变长度的比特组、莫尔斯符号、任何数制的数字或数学环的元素替换。所有这些都可以进行置换和重新分组。组可以再次被替换、压缩、乘以大整数或矩阵，转换为其他数制，或者链接在一起。一些组的部分可以用来加密其他组的部分。
加密服务提供商：提供加密通信服务的公司通常使用自己的专有算法。他们可以使用开发者刚列出的任何技术，但他们必须确保他们的密码符合第十二章的所有标准。密码应该有大块和长密钥。它应该是高度非线性的，具有良好的扩散和饱和度。
如果服务提供商使用标准算法如 3DES 或 AES，那么标准密码应该在前后都加上一个有密钥的秘密替换或秘密置换。
银行业务：银行和金融公司被要求在所有通信中使用 AES，以便它们可以相互之间以及与美联储、证券交易委员会、国税局和其他政府机构进行信息交换。银行还广泛使用公钥密码学来建立加密密钥以及进行身份验证和验证。
军事和外交：美国军方和国务院根据 NSA 规定被强制使用 256 位 AES。这具有法律效力。这在个人电脑、笔记本电脑甚至带有 AES 芯片或 AES 软件的智能手机上完成。然而，军方和情报机构在可能计算机和手机无法工作的地方和条件下操作，或者一个配备 AES 的手机可能会引起怀疑或违法。在许多国家，拥有任何形式的密码设备、文献或工作成果都是非法的。此外，外国军队和外交团体可能会对来自 NSA 或受 NSA 监管的供应商的任何 AES 硬件或软件表示不信任。
由于这些原因，军队和情报机构都备有代码和密码来支持他们的电子加密设备。适用于战斗条件的手写密码包括对角线双字母密码、TwoSquare+1、Two Square ripple 和 Playfair TwoSquare。另一个想法是使用双字母密码或 Two Square，然后是逐块置换。
大文件：对于非常大的文件，使用流密码比块密码要快得多。您可以生成一系列伪随机数，并将其与数据文件组合以模拟一次性密码本。您可以使用 Xorshift、FRand 或 Gen5 进行 PRNG，并且可以使用xors、adds或poly进行组合功能。或者，您可以同时使用 GenX 进行生成和组合。
