5.2.1 针对维吉尼亚密码的密码分析:理论部分

在历史上,有人声称维吉尼亚型密码,尤其是扰乱字母的版本“牢不可破”。然而事实上并非如此。如果 Eve 认识 Bob 和 Alice,她可能能够猜出部分密钥以降低攻击难度。(你知道有多少人使用自己的名字和生日的结合作为互联网上的密码么?)但即使没有幸运地猜测到密钥,十九世纪发展起来的基本统计方法也允许对维吉尼亚型密码进行直接的密码分析。为了简单起见,我们使用最初的维吉尼亚密码,即不扰乱表中的字母。

你可能想知道,为什么我们要花时间对维吉尼亚进行密码分析,现在已经没有人使用维吉尼亚密码来进行安全通信了。答案是,我们的论述主要是为了向大家介绍在密码分析中使用的统计工具。这建立在 1.1.1 一节中我们使用的频率表对简单替换密码进行密码分析的基础之上。在本节中,我们描述了用于对维吉尼亚进行密码分析的理论工具,在下一节中我们将这些工具应用于解密示例密文。如果在任何时候你发现本节中的理论比较晦涩难懂,那么转向 5.2.2 查看理论在实践中的应用可能会有所帮助。

对维吉尼亚密码进行密码分析的第一个目标是找到密钥的长度,有时也称为块长或周期。我们已经在 注5.14 中看到了如何通过在密文中寻找重复的片段来实现这一点。重点是,某些明文片段,如 the出现得相当频繁,而其他明文片段,如 ugw,出现得很少或根本不出现。在明文中出现的许多 the 中,有一定概率会和密钥的相同部分对齐。

于是我们引出了卡西斯基方法,这是一位名叫弗里德里希·卡西斯基(Friedrich Kasiski)的德国军官在1863年出版的《Die Geheimschriften und die Dechiffrir-kunst》一书中首次提出的。人们在密文中寻找重复的片段,并编制了一份重复片段之间的距离表。密钥长度可能会整除这些长度。当然,会有一定数量的重复纯粹是偶然发生的,但这些都是随机的,而来自重复明文片段的重复密文则总是可以被密钥长度整除。通常不难从这些数据中找出密钥长度。

还有另一种猜测密钥长度的方法,适用于单个字母,而不是由几个字母组成的片段。基本的想法可以追溯到英语字母的频率表(表1.3),它表明一些字母比其他字母更容易出现。假设现在你看到一个用维吉尼亚加密的密文,你猜它是用长度为5的关键字加密的。这意味着每五个字母都是用相同的移位加密的,所以如果你抽出每五个字符并将它们组成一个字符串,整个字符串都是用一个移位密码加密的。因此,字符串的字母频率看起来应该或多或少像英语中那样,有些字母更频繁,有些则不那么频繁。由第2、第7、第12、……个字母组成的新字符串也是如此。另一方面,如果你猜错了,并且密钥长度不是五,那么每五个字母组成的字符串应该或多或少是随机的,所以其中的字母频率应该与英语中的频率不同。

我们如何量化以下两种断言,以便区分它们

1. 字符串1的字母频率与表1.3中的相似(5.4)

2.字符串2的字母频率看起来或多或少是随机的。(5.5)

一种方法是使用以下工具:

定义:设  为一串长度为  的字符串。我们定义  的重合指数(index of coincidence)为在  中随机选取两个字母起为相同字母的概率,记作 

我们将推导一个重合指数的公式。首先,我们讲字母  分别映射到数字 。对于每个值 ,设  为字母  在字符串  中出现的频率。例如,如果字母  在字符串  上出现 23 次,则,因为在映射表中 

对于每个 ,我们有  个方法从该字母中取两个出来。所以加起来就是

另外,从字符串中,取两个字母的方法有  种。所以在字符串  中任意取两字母,这两个字母相同的概率,即  的重合指数

5.15 设有字符串 s = “A bird in hand is worth two in the bush.”
忽略其中的空格和标点, 共包含 30 个字符,下面是所有出现过的字母的频率表

5.2.1 针对维吉尼亚密码的密码分析:理论部分


那么根据 式5.6 的定义,上述字符串的重合指数为

我们回到前面的两个断言(5.4)和(5.5),假设  是由一串随机字符串组成的,那么  的概率就是 ,则期望的重合指数 。但是,如果  是由一串英文文本,我们期望每个字母的频率如表 1.3 所示。所以,如果  包含 10000 个字符,那么我们期望大约会有 815 个 A,大约有 144 个 B 等等。因此,英文文本的重合指数约为

0.0385 和 0.0685 虽然看起来差值不大,但是却提供了区分这两种断言的工具:

1、 如果 ,则  有可能是经过或未经过移位的英文文本。(5.7)

2、如果 ,则  有可能是随机字符串。(5.8)

当然, 的值并不百分之百准确,特别如果  相当短的时候。但(5.7)和(5.8)的寓意是, 的值越大,则  就越有可能是英文文本,或者被某种简单的移位、替换密码加密,而 

的值越小, 就越有可能是随机字符串。
现在假设 Eve 截获了一条消息 ,她认为该消息是使用维吉尼亚密码加密的,并想确认该密钥的的长度 。她的第一步是将字符串  分成  个片段 
中  由从第一个字母开始的每  个字母组成, 由从第二个字母开始第  个字母构成,以此类推,如果我们记 ,那么

注意到,如果Eve的猜测是正确的,并且密钥的长度为 ,那么每个  都由使用相同移位加密的字符组成,因此尽管它们不会解密成的明文(请记住是文本的第  个字母),但它们的字母的词频将符合英语。另一方面,如果 Eve 的猜测不正确,那么字符串很可能是随机的。

因此对于每一个 k,Eve 尝试计 
并观察其是否接近 0.068 或者是 0.038,直到对于某个 k 都很大,(比 0.06大),那么这个k很可能就是正确的块长。

现在我们假设 Eve 已经使用 Kasiski 测试或重合指数确定了密钥的长度为 。下一步是将字符串 相互比较。她用来比较不同字符串的工具被称为拟重合指数。一般的想法是, 个字符串中的每一个都使用不同的移位密码进行了加密。如果串  偏移了 ,串 偏移了 ,那么当  中的符号偏移了额外的量  时,我们会期望 的频率与  的频率最匹配。于是我们引出了一下定义。

定义,设有字符串  和  ,我们定义它们的拟重合指数  为:从 和  中各取一个字母,它们是相同字母的概率。

我们设  为  中第  个字母出现的频率,相同的再定义一个 。那么从两个字符串中取出一个字母为第  个字母的概率分别为  和 。于是我们得到了拟重合指数  的公

5.16 设我们有两个字符串 

s = “A bird in hand is worth two in the bush,”

t = “A stitch in time saves nine.”

根据式  我们计算  的拟重合指数为 

拟重合指数和重合指数非常相似的性质。例如,同断言(5.7)和(5.8)。 的值可用于确认猜测的移位量是否正确。因此,如果使用相同的简单替换密码对两个字符串  和  进行加密,则  往往很大,这是由于英文中每个字母出现频率不均匀的原因。另一方面,如果使用不同的替换密码对  和  进行加密,则它们彼此之间没有关系,并且 的值将小得多。

我们回到 Eve 对维吉尼亚密码的攻击上。现在他知道密钥的长度  了并将密文分成  块,,每一块都进行了相同的移位 ,下一步,Eve 将对  块尝试进行不同的移位,即 。当 ,那么  将和  则相当于进行了相同的移位加密,此时它们的  的值将会很大,否则  的值就很小。

理论成立,实践开始,Eve 计算拟重合指数

然后建表,并在表中挑出大的值(比0.065大),每个值都意味

是我们有了一个关于变量 的方程组。在实践中,方程组中的某些方程是误导项,但经过一定试错,Eve 最终会得到值 ,满足

因此,如果密钥从  开始,那么第二个字母就是  再移位 ,第三个字母就是  再移位 ,以此类推。如果密钥从  开始,那么第二个字母就是  再移位 ,第三个字母就是  再移位 ,以此类推。所以 Eve 尝试所有的 26 中可能的字母,然后对密文尝试进行解密。通过查看 26 种解密后字符串的前面部分内容,Eve 很容易判断哪个是正确的密钥。

注 5.17 我们之前注意到,在明文中出现的许多字母中,有一定比例的单词将与密钥的相同部分对齐。事实证明,这种对齐发生的频率要比人们想象的要高得多。这是 “生日悖论” 的一个例子,该悖论说,人群中有两人有相同的生日的概率非常高。我们将在 5.4 一节中讨论生日悖论及其在密码学中的许多应用。

       

原文始发于微信公众号(山石网科安全技术研究院):5.2.1 针对维吉尼亚密码的密码分析:理论部分

版权声明:admin 发表于 2022年11月11日 上午10:44。
转载请注明:5.2.1 针对维吉尼亚密码的密码分析:理论部分 | CTF导航

相关文章

暂无评论

暂无评论...