研究笔记 · 加密学 在Ron Rivest的RC2密码的密钥调度中，256个数字据说来源于π，但该方法从未公开。使用π的数字作为骰子进行卡片洗牌可以准确复制RC2的两个表。概述 RFC 2268指出，RC2的密钥调度中的256字节表PITABLE是“基于PI的数字”，但没有给出方法，而同一文档中的第二个表没有提及任何来源。使用π的小数数字作为随机源的Fisher–Yates洗牌完全复制了这两个表：每次抽取读取正好三个数字，任何可能偏向结果的抽取都会被丢弃。PITABLE从第一位3开始；第二个表在四位数字后开始。Rivest的MD2哈希使用相同的洗牌方法，但每次抽取时读取的数字数量不定，这可能是为什么这个联系未被发现。这很可能是原始制作表的方式，尽管Rivest如何得出这个规则并没有记录。1996年，RSA数据安全公司的工程师在公开场合提出了这个问题；经过广泛搜索没有找到更早的公开答案。这个结果与RC2的安全性无关。1 问题 RC2是一种区块密码，Ron Rivest在1980年代末设计。为了将密钥转换为更长的内部密钥，它实际上用于加密，传递每个字节通过一个固定的表：以混合顺序排列的数字0到255。每个RC2的实现都携带相同的256个数字。这样的表在原则上可以隐藏设计者的弱点。密码学家通过从公共常数（如π）导出这些表并展示导出过程来防止这种怀疑，这样任何人都可以重建表并确认没有手工选择。这些被称为“无袖之高”的数字，只有在导出过程公开时才能让人放心。RC2命名了它的常数但从未给出其导出。Rivest的规范RFC 2268称该表为“基于PI数字的‘随机’字节数组”，并且没有说明方法。1 当1996年密码代码泄露时，拥有RC2的RSA数据安全公司的工程师在公开场合列出了如何判断该表是否来自π的问题。2 没有回答，某些实现（如LibTomCrypt）仍保留泄露代码中的注释：“可能某种方式衍生自π”。3 , 4 第5节讲述了这段历史。本笔记提供了一个精确复制该表的构造。2 答案 将256张编号为0到255的卡片按顺序排列。依次取每张卡片，从第二张到最后一张，将其与一个随机选择的卡片交换，随机选择的卡片位置在当前卡片位置之前或相同。这就是Fisher–Yates洗牌，是公平洗牌的标准方式，并不秘密。未公开的是随机性来自何处。当骰子为π的小数数字时，可以精确复制表，每次抽取读取正好三个数字，从第一个3开始。图1演示了第一步。洗牌，逐步进行 洗牌 217 120 249 196 25 221 181 237 公布 217 120 249 196 25 221 181 237 显示十进制的256个位置中的前八个。所有256个匹配。该动画需要JavaScript。第一步是：读取314，因此卡片1与位置314模2 = 0的卡片交换；读取159，因此卡片2与位置159模3 = 0的卡片交换；读取265，因此卡片3与位置265模4 = 1的卡片交换；依此类推。图1。构造的前九步，然后是结果。在每一步中，下一个三个数字的π决定最新卡片的位置：在可用位置数量上除以得到的余数。精确写出，构造是 算法1。丢弃步骤保持抽取的公平。当可用位置的数量不能均匀地除以1,000时，落在最高值中的抽取（例如在有240个位置时落在960到999之间的抽取）将被丢弃，读取三个新数字。整个洗牌过程中，共发生了21次这种情况，其中两次发生在π的第762位小数，这被称为费曼点的一连串六个9。a 总共洗牌使用了828个数字。算法1。PITABLE的构造 输入：d = 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, …（π的小数数字） rand (n)：循环 x ← 下一三个数字的d // 0…999 如果x < n·⌊1000 / n⌋：返回x mod n // 否则丢弃x S ← [0, 1, …, 255] 对于i ← 2到256：j ← rand (i) 交换S[j], S[i − 1] 返回S // = PITABLE 为什么它可能一直隐藏。2014年，Rivest确认他的MD2哈希使用相同的洗牌构建π表。5 但是MD2根据每次抽取需要的数字读取尽可能少的数字：选择10个位置时一个数字，选择100个时两个数字，超过100时三个数字。应用于RC2，MD2的确切规则与256个条目中的1匹配，不比随机情况更好，因此显而易见的测试会建议这些表不相关。所需的唯一更改是在每次都读取三个数字。3 验证 算法1以256个位置的所有256个位置重现RFC 2268的PITABLE。图2在您的浏览器中运行它，以及五个可信的替代方案，并比较每个输出与发布的结果。