查看“︁维吉尼亚密码”︁的源代码

[[File:Vigenere.jpg|right|thumbnail|维吉尼亚密码以張子號[[布莱斯·德·维吉尼亚]]的名字来命名，然而其真正的发明者是[[莱昂·巴蒂斯塔·阿尔伯蒂]]。而维吉尼亚则发明过一种更强大的[[自动密钥密码]]。]]
'''维吉尼亚密码'''（{{lang-fr|Chiffre de Vigenère}}，又译'''维热纳尔密码'''）是使用一系列[[凯撒密码]]组成密码字母表的加密算法，属于[[多表密码]]的一种简单形式。

维吉尼亚密码曾多次被发明。该方法最早记录在[[吉奥万·巴蒂斯塔·贝拉索]]（ Giovan Battista Bellaso）于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》（[[意大利语]]：{{lang|it|La cifra del. Sig. Giovan Battista Bellaso}}）中。然而，后来在19世纪时被误传为是[[法国]]外交官[[布莱斯·德·维吉尼亚]]（Blaise De Vigenère）所创造，因此现在被称为“维吉尼亚密码”。

维吉尼亚密码以其简单易用而著称，同时初学者通常难以破解，因而又被称为“不可破译的密码”（[[法语]]：{{lang|fr|le chiffre indéchiffrable}}）。这也让很多人使用维吉尼亚密码来加密的目的就是为了将其破解。<ref>{{cite book|first=Laurence D.|last=Smith|year=1943|title=Cryptography the Science of Secret Writing: The Science of Secret Writing|chapter=Substitution Ciphers|editor=|others=|pages=81|publisher=Dover Publications|id=ISBN 048620247X}}</ref>


==历史==
[[File:Confederate cipher disk.jpg|thumb|[[美利坚联盟国|南军]]曾使用过的密码盘的仿制品，目前实物只有五件存世。]]
多表密码最早在1467年左右由意大利文艺复兴时期的建筑师、哲学家、密码学家[[莱昂·巴蒂斯塔·阿尔伯蒂|布萊特·巴蒂斯塔·阿尔伯蒂]]提出，他使用了一个金属密码盘来切换密码-{}-表，只是这个系统只能做些有限的转换。后来1508年时，德国的修道士、炼金术师、密码学家[[约翰尼斯·特里特米乌斯]]《隐写术》（Steganographia）中发明的[[表格法]]（tabula recta）成为了维吉尼亚密码的关键部分。然而当时此方法只能对密码-{}-表做一些简单的、可预测的切换。这一加密技术也称为[[特里特米乌斯密码]]。

这一方法真正出现是在[[吉奥万·巴蒂斯塔·贝拉索]]于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的算术》中。他以特里特米乌斯的表格法为基础，同时引入了[[密钥]]的概念。

[[布莱斯·德·维吉尼亚]]于1586年[[亨利三世 (法兰西)|亨利三世]]时期发明了更为简单却又更有效的[[自动密钥密码]]（autokey cipher）。之后，19世纪时贝拉索的方法被误认为是由维吉尼亚首先发明的。大卫·卡恩在《破译者（The Codebreakers）》中对此表示遗憾，他写道“历史忽略了这一重要贡献，将其归功于维吉尼亚，虽然他对此并不知道”。<ref name="KahnOrigin">{{cite book|first=Kahn|last=David|year=1999|title=The Codebreakers: The Story of Secret Writing|chapter=On the Origin of a Species|publisher=Simon & Schuster|isbn=0684831309}}</ref>

由于破译的难度很高，维吉尼亚密码也因此获得了很高的声望。知名作家、数学家查尔斯·路特维奇·道奇森（笔名[[路易斯·卡罗]]）在其1868年所编、收于一儿童杂志的《字母表密码（The Alphabet Cipher）》中称其是不可破译的。1917年，《[[科学美国人]]》将维吉尼亚密码称为“无法被转化的”。<ref>{{cite book|first=Lars R.|last=Knudsen|year=1998|title=State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures |url=https://archive.org/details/stateartappliedc00pren|chapter=Block Ciphers—a survey|editor=Bart Preneel and Vincent Rijmen|others=|pages=[https://archive.org/details/stateartappliedc00pren/page/n35 29]|publisher=Springer|isbn=3540654747|location=Berlin ; London}}</ref>然而，维吉尼亚密码却配不上这样的称号。[[查尔斯·巴贝奇]]完成了破译的工作，但他没有将此发表。<ref name="Singh">{{cite book|first=Simon|last=Singh|year=1999|title=The Code Book|chapter=Chapter 2: Le Chiffre Indéchiffrable|editor=|pages=63–78|publisher=[[Anchor Books#Divisions and Imprints|Anchor Books]], [[Random House]]|isbn=0-385-49532-3}}</ref>之后，[[弗里德里希·卡西斯基]]（Friedrich Kasiski）于19世纪完全破解并发表了他的方法。甚至在此之前，一些资深密码分析家在16世纪就能偶尔将其破解。<ref name="KahnOrigin" />

维吉尼亚密码足够地易于使用使其能够作为战地密码。<ref>[http://www.vectorsite.net/ttcode_03.html#m2 Codes, Ciphers, & Codebreaking] {{Wayback|url=http://www.vectorsite.net/ttcode_03.html#m2 |date=20051205013154 }}（The Rise Of Field Ciphers）</ref>例如，美国[[南北战争]]期间[[美利坚联盟国|南军]]就使用黄铜密码盘生成维吉尼亚密码。[[美利坚合众国|北军]]则经常能够破译南军的密码。战争自始至终，南军主要使用三个密钥，分别为“Manchester Bluff（曼彻斯特的虚张声势）”、“Complete Victory（完全的胜利）”以及战争后期的“Come Retribution（报应来临）”。

[[吉尔伯特·维尔南]]（Gilbert Vernam）曾试图对已被破译的密码进行修补（于1918年创造了维尔南-维吉尼亚密码），然而这终究无济于事。不过维尔南的发明最终促成了[[一次性密码本]]的诞生，这是一种理论上不可破译的密码。

==描述==
[[File:Vigenère square.svg|right|thumbnail|300px|用来加密解密的维吉尼亚表格]]
在一个[[凱撒密碼]]中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，<tt>A</tt>就转换为了<tt>D</tt>、<tt>B</tt>转换为了<tt>E</tt>……而维吉尼亚密码则是由一些偏移量不同的凯撒密码组成。

为了生成密码，需要使用[[表格法]]。这一表格包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。

例如，假设[[明文]]为：
 <tt>ATTACKATDAWN</tt>

选择某一关键词并重复而得到密钥，如关键词为<tt>LEMON</tt>时，密钥为：
 <tt>LEMONLEMONLE</tt>

对于明文的第一个字母<tt>A</tt>，对应密钥的第一个字母<tt>L</tt>，于是使用表格中<tt>L</tt>行字母表进行加密，得到[[密文]]第一个字母<tt>L</tt>。类似地，明文第二个字母为<tt>T</tt>，在表格中使用对应的<tt>E</tt>行进行加密，得到密文第二个字母<tt>X</tt>。以此类推，可以得到：
 -{}-
 明文：<tt>ATTACKATDAWN</tt>
 密钥：<tt>LEMONLEMONLE</tt>
 密文：<tt>LXFOPVEFRNHR</tt>

解密的过程则与加密相反。例如：根据密钥第一个字母<tt>L</tt>所对应的<tt>L</tt>行字母表，发现密文第一个字母<tt>L</tt>位于<tt>A</tt>列，因而明文第一个字母为<tt>A</tt>。密钥第二个字母<tt>E</tt>对应<tt>E</tt>行字母表，而密文第二个字母<tt>X</tt>位于此行<tt>T</tt>列，因而明文第二个字母为<tt>T</tt>。以此类推便可得到明文。

用数字0-25代替字母<tt>A</tt>-<tt>Z</tt>，维吉尼亚密码的加密文法可以写成[[同余]]的形式：
:<math>C_i \equiv P_i + K_i \pmod {26}</math>

解密方法则能写成：
:<math>P_i \equiv C_i - K_i \pmod {26}</math>

==密码破译==
对包括维吉尼亚密码在内的所有多表密码的破译都是以[[字母频率]]为基础的，但直接的[[频率分析]]却并不适用。例如，如果<tt>P</tt>是密文中出现次数最多的字母，则<tt>P</tt>很有可能对应<tt>E</tt>（前提是明文的语言为[[英语]]）。原因在于<tt>E</tt>是英语中使用频率最高的字母。然而，由于在维吉尼亚密码中，<tt>E</tt>可以被加密成不同的密文，因而简单的频率分析在这里并没有用。

破译维吉尼亚密码的关键在于它的密钥是循环重复的。如果我们知道了密钥的长度，那密文就可以被看作是交织在一起的[[凯撒密码]]，而其中每一个都可以单独破解。使用卡西斯基试验和弗里德曼试验来得到密钥的长度。

===卡西斯基试验===
[[弗里德里希·卡西斯基]]于1863年首先发表了完整的维吉尼亚密码的破译方法，称为卡西斯基试验（Kasiski examination）。早先的一些破译都是基于对于明文的认识、或者使用可识别的词语作为密钥。而卡西斯基的方法则没有这些限制。然而，在此之前，已经有人意识到了这一方法。1854年，英国数学家、发明家兼机械工程师[[查尔斯·巴贝奇]]受到斯维提斯（John Hall Brock Thwaites）在《艺术协会杂志》（Journal of the Society of the Arts）上声称发明了“新密码”的激励，从而破译了维吉尼亚密码。巴贝奇发现斯维提斯的密码只不过是维吉尼亚密码的一个变种而已，而斯维提斯则向其挑战，让他尝试破译用两个不同长度的密钥加密的密文。巴贝奇成功地进行了破译，得到的明文是[[丁尼生]]所写的诗《罪恶的想象》（The Vision of Sin），使用的密钥则是丁尼生妻子的名字Emily（艾米莉）。巴贝奇从未对他的方法进行过解释 。在对巴贝奇生前笔记的研究中发现，早在1846年巴贝奇就使用了这一方法，与后来卡西斯基发表的方法相同。<ref>Franksen, O. I. 1985 Mr. Babbage's Secret: the Tale of a Cipher-And APL. Prentice Hall</ref>

卡西斯基试验是基于类似<tt>the</tt>这样的常用单词有可能被同样的密钥字母进行加密，从而在密文中重复出现。例如，明文中不同的<tt>CRYPTO</tt>可能被密钥<tt>ABCDEF</tt>加密成不同的密文：
 -{}-
 密钥：<tt>ABCDEF AB CDEFA BCD EFABCDEFABCD</tt>
 明文：<tt>'''CRYPTO''' IS SHORT FOR '''CRYPTO'''GRAPHY</tt>
 密文：<tt>'''CSASXT''' IT UKSWT GQU '''GWYQVR'''KWAQJB</tt>

此时明文中重复的元素在密文中并不重复。然而，如果密钥相同的话，结果可能便为（使用密钥<tt>ABCD</tt>）：
 -{}-
 密钥：<tt>ABCDAB CD ABCDA BCD ABCDABCDABCD</tt>
 明文：<tt>'''CRYPTO''' IS SHORT FOR '''CRYPTO'''GRAPHY</tt>
 密文：<tt>'''CSASTP''' KV SIQUT GQU '''CSASTP'''IUAQJB</tt>

此时卡西斯基试验就能产生效果。对于更长的段落此方法更为有效，因为通常密文中重复的片段会更多。如通过下面的密文就能破译出密钥的长度：
 -{}-
 密文：<tt>'''DYDUXRMH'''TVDV'''NQD'''QNW'''DYDUXRMH'''ARTJGW'''NQD'''</tt>

其中，两个<tt>DYDUXRMH</tt>的出现相隔了18个字母。因此，可以假定密钥的长度是18的约数，即长度为18、9、6、3或2。而两个<tt>NQD</tt>则相距20个字母，意味着密钥长度应为20、10、5、4或2。取两者的[[交集]]，则可以基本确定密钥长度为2。

===弗里德曼试验===
弗里德曼试验由威廉·F·弗里德曼（William F. Friedman）于1920年代发明。他使用了[[重合指数]]（index of coincidence）来描述密文字母频率的不匀性，从而破译密码。<math>\kappa_p</math>指目标语言中两个任意字母相同的概率（英文中为0.067），<math>\kappa_r</math>指字母表中这种情况出现的概率（英文中为1/26=0.0385），从而密钥长度可以估计为：
:<math>{\kappa_p-\kappa_r}\over{\kappa_o-\kappa_r}</math>

其中，观察概率为
:<math>\kappa_o=\frac{\sum_{i=1}^{c}n_i(n_i -1)}{N(N-1)}</math>

其中，''c''是指字母表的长度（英文为26），''N''指文本的长度，''n''<sub>1</sub>到''n''<sub>''c''</sub>是指密文的字母频率，为整数。

此方法只是一种估计，会随着文本长度的增加而更为精确。在实践中，会尝试接近此估计的多个密钥长度。<ref>{{cite book |editor=Henk C.A. van Tilborg |title=Encyclopedia of Cryptography and Security |url=https://archive.org/details/encyclopediacryp00tilb_600 |publisher=Springer |edition=First |id=ISBN 038723473X |pages=[https://archive.org/details/encyclopediacryp00tilb_600/page/n121 115] |year=2005}}</ref> 一种更好的方法是将密文写成矩阵形式，其中列数与假定的密钥长度一致，将每一列的重合指数单独计算，并求得平均重合指数。对于所有可能的密钥长度，平均重合指数最高的最有可能是真正的密钥长度。<ref>{{cite journal | author=Mountjoy, Marjorie | title= The Bar Statistics | journal=NSA Technical Journal | year=1963 | volume=VII | issue=2,4}}  Published in two parts.</ref> 这样的试验可以作为卡西斯基试验的补充。

===频率分析===
{{main|频率分析}}
一旦能够确定密钥的长度，密文就能重新写成多列，列数与密钥长度对应。这样每一列其实就是一个[[凯撒密码]]，而此密码的密钥（偏移量）则对应于维吉尼亚密码密钥的相应字母。与破译凯撒密码类似的方法，就能将密文破译。

柯克霍夫方法作为卡西斯基试验的改进，由[[奥古斯特·柯克霍夫]]（Auguste Kerckhoffs）提出。它将每一列的字母频率与转换后的明文频率相对应而得出每一列的密钥字母。一旦密钥中每一个字母都能确定，就能很简单地破译密文，从而得到明文。如果维吉尼亚字母表表格本身是杂乱而非按通常字母表顺序的话，那柯克霍夫方法就会无效，但卡西斯基试验和重复指数对于决定密钥长度仍旧是有效的。

==变体==
维吉尼亚密码的变体[[滚动密钥密码]]也曾一度被认为是不可破译的。这种变体的密钥与密文的长度一致，因此卡西斯基试验和弗里德曼试验即变得无效。1920年，弗里德曼首先发现了此方法的弱点。由于滚动密钥密码的密钥是一段真实的语言，因而破译者便能了解密钥文本的统计信息，而这种信息也会反映到密文当中。

如果密钥是完全随机、与明文的长度一致且只使用过一次，维吉尼亚密码理论上是不可破译的。然而，这种情况下密钥本身而非密文便成了关键，这被称为[[一次性密码本]]。

维吉尼亚本人确实发明了一种更强的维吉尼亚密码变体——[[自动密钥密码]]。巴贝奇所破译的其实是这种自动密钥密码，而卡西斯基则通常被认为是首先发表了破译固定密钥多表密码的方法。

还有一种简单的变体使用维吉尼亚的解码方法进行加密，同时使用维吉尼亚的加密方法进行解密，这被称为变异博福特密码。此方法与[[弗朗西斯·博福特]]创造的[[博福特密码]]不同，后者虽然也与维吉尼亚密码相似，但使用了修改过的加密方式和表格，是一种[[对等加密]]。

维吉尼亚密码-{}-表面上的强度并没能使其在[[欧洲]]得到广泛使用。由Gronsfeld伯爵所创造的Gronsfeld密码基本与维吉尼亚密码相同，不过它只使用10个不同的密码字母表（对应字母0到9）。Gronsfeld密码的强度很高，这是因为它的密钥并不是一个单词，但缺点在于字母表数量过少。尽管如此，Gronsfeld密码仍在德国和整个欧洲有着广泛的应用。

== 参考文献 ==
{{Reflist}}

== 参见 ==
* [[博福特密码]]

{{Cryptography navbox|classical}}

[[Category:古典密码]]
[[Category:流密码]]