超酷算法:分组密码与安全排列

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的,现在只是复制回来自己做个存档,jobbole链接在这。 作为开始,我假设你知道什么是排列,简单说就是按特定的顺序对序列进行洗牌。比如,值域1-10的排列为{5,2,1,6,8,4,3,9,7,10} 。一个安全的排列是攻击者即使有该排列的任意子集,都无法确定其它任何一个元素的顺序。这里有个简单的例子是使用一个安全加密的伪随机数生成器,用一个密钥作为种子,并用它来打乱你的序列。 如果你想生成一个非常非常大的排列,一个如此大的预计算和存储是不是不太现实?此外,你是否希望它是个安全序列?这里有个非常巧妙的方法,我们可以使用分组密码,使我们能够产生超过数值范围内的任何一个安全排列,而不必对它们进行预计算。 分组密码,没人不熟悉,它是密码学中一种常见的基础元素。它是由多块一定长度的密文组成,密文一般为64或128位的加密串。相同的密钥和相同的明文,它只可能生成相同的密文。超过一个块大小的信息使用一系列操作模式中的某一种方式加密,继而可以针对比单个块大许多的消息进行安全的加密和解密。使用分组密码加密,选择操作模式是至关重要的。为了能生成一个安全排列,无论如何,我们只打算每次加密单个块,所以我们不必担心操作模式。 如果你知道分组密码是如何运作的,你肯定能获得一个安全的排列。将给定长度的任意块(考虑下块的数量非常大的情况)用唯一的方式转换为另外一个块,且能将它再次转换回来。如果我们逐步加密更大的数字(1,2,3等等),我们保证能得到看上去随机的序列,只要不重复输入。这点很容易证明:假如它是重复的,那你会有两个输入数字被解码为同一个输出数字,这样就不可能有独一无二的解码。分组密码所持有的这些特性也正是对我们有用的特性。 你说,一切都挺好,但如果我想要一个不是2的幂次值域内的排列该如何?这里有个聪明的小技巧,就是取一个块长度略大于你想要的长度的分组密码,使用上面描述的方法,逐步加密序列中的更大数值,以产生排列中的元素。当加密后的值超出你想要的排列值域之外,只需再次加密。重复这样的方式直到你给到你想要的值域内的数值。同样,我们能保证分组密码的唯一性,并且我们也能保证(穷举方式)最终获得了一个理想值域内的数值。 很显然,在追寻这条路之前我们需要考虑一些因素。你要选择一个分组密码,是不是比你想生成的序列的值域要大,最好是2的幂次。密码值域和排列值域的比率确定了你运行的平均时间, 因此,如果密码是你排列的值域的四倍时,你就对每个值平均需要四次加密。这可能产生问题,因为大多数密码是64,128或者更多位。为了这个目的,我们找到适应性比较强的TEA加密算法,它很容易构造32,64,128或者更长位的变体,并且位操作在main主循环那很容易调整,也可产生4的幂次长度的密码,而无需将密码缩短至容易被暴力破解的长度。 另外值得一提的是,虽然这个技术的目的是生成非常大的安全排列,但对那些并不注重安全的排列同样有用 - 你的密钥可作为生成排列的随机种子。在许多情况下这种方法同样有帮助,基本上它是个映射函数可以用来索引排列的数值,这样你可以计算出该排列的任意子集的值。 最后,请记住,由于可能的排列数呈阶乘级增长,你的密钥空间肯定大大小于排列的数量。这个对于大多数应用可能并不重要,因为如此庞大的排列不可能一个个枚举过去。但是,如果你的密钥过短,它就有可能被攻击者利用枚举密钥的方式来找出可能生成的排列。 更新:Yossi Oren在评论里留了分优秀的论文连接。它涵盖了我的描述(当然更全面)。

January 16, 2015 · 1 min · HuangWei