 |
| 维吉尼亚密码 |
维吉尼亚密码的发明者是法国人BlaisedeVigenère。
维吉尼亚密码引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。 维吉尼亚密码的密钥空间大小为26m，所以即使m的值很小，使用穷尽密钥搜索方法也需要很长的时间。例如，当m=5时，密钥空间大小超过1.1*107，这样的密钥量已经超出了使用手算进行穷尽搜索的能力范围（当然使用计算机另当别论）。
特点编辑本段回目录
人们在单一恺撒密码的基础上扩展出多表密码，称为“维吉尼亚”密码。它是由16世纪法国亨利三世王朝的布莱瑟·维吉尼亚发明的，其特点是将26个恺撒密表合成一个，见下表：
A B C D F G H I J K L M N O P Q R S T U V W X Y Z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
密钥
维吉尼亚密码引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。假如以上面第一行代表明文字母，左面第一列代表密钥字母，对如下明文加密：
TO BE OR NOT TO BE THAT IS THE QUESTION
当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推，得出对应关系如下：
密钥:RELAT IONSR ELATI ONSRE LATIO NSREL
明文:TOBEO RNOTT OBETH ATIST HEQUE STION
密文:KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
维吉尼亚密码的演变
历史上以维吉尼亚密表为基础又演变出很多种加密方法，其基本元素无非是密表与密钥，并一直沿用到二战以后的初级电子密码机上。
公元16世纪晚期，想要获得更高的保密度的人获得了一种设计更加精细的密码表。法国外交家BlaisedeVigenère发明了一种方法来对同一条信息中的不同字母用不同的密码进行加密。这样，同样的E在一个位置可能被M所取代，而在另一个位置的E则有可能以K的面目出现。这样，就可以防止任何人利用频率分析法解密该条信息。
维热纳尔密码表
ABCDEFGHIJKLMNOPQRSTUVWXYZ
AABCDEFGHIJKLMNOPQRSTUVWXYZ
BBCDEFGHIJKLMNOPQRSTUVWXYZA
CCDEFGHIJKLMNOPQRSTUVWXYZAB
DDEFGHIJKLMNOPQRSTUVWXYZABC
EEFGHIJKLMNOPQRSTUVWXYZABCD
FFGHIJKLMNOPQRSTUVWXYZABCDE
GGHIJKLMNOPQRSTUVWXYZABCDEF
HHIJKLMNOPQRSTUVWXYZABCDEFG
IIJKLMNOPQRSTUVWXYZABCDEFGH
JJKLMNOPQRSTUVWXYZABCDEFGHI
KKLMNOPQRSTUVWXYZABCDEFGHIJ
LLMNOPQRSTUVWXYZABCDEFGHIJK
MMNOPQRSTUVWXYZABCDEFGHIJKL
NNOPQRSTUVWXYZABCDEFGHIJKLM
OOPQRSTUVWXYZABCDEFGHIJKLMN
PPQRSTUVWXYZABCDEFGHIJKLMNO
QQRSTUVWXYZABCDEFGHIJKLMNOP
RRSTUVWXYZABCDEFGHIJKLMNOPQ
SSTUVWXYZABCDEFGHIJKLMNOPQR
TTUVWXYZABCDEFGHIJKLMNOPQRS
UUVWXYZABCDEFGHIJKLMNOPQRST
VVWXYZABCDEFGHIJKLMNOPQRSTU
WWXYZABCDEFGHIJKLMNOPQRSTUV
XXYZABCDEFGHIJKLMNOPQRSTUVW
YYZABCDEFGHIJKLMNOPQRSTUVWX
ZZABCDEFGHIJKLMNOPQRSTUVWXY
在维热纳尔（Vigenère）的密码中，发件人和收件人必须使用同一个关键词（或者同一文字章节），这个关键词或文字章节中的字母告诉他们怎么样才能前后改变字母的位置来获得该段信息中的每个字母的正确对应位置。比如如果关键字“BIG”被使用了，发件人将把信息按三个字母的顺序排列。第一个三字母单词的第一个字母将应当向前移动一个位置（因为B是排在A后面的字母），第二个字母需要向后移动8位（I是A后面第8个字母），而第三个字母需要向前移动6位（G是A后面第6个字母）。然后，文字就可以按下面的顺序来进行加密了：
未加密文字：THEBUTCHERTHEBAKERANDTHECANDLESTICKMAKER。（屠夫、面包师和蜡烛匠）。
关键密钥：BIGBIGBIGBIGBIGBIGBIGBIGBIGBIGBIGBIGBIGB
加密文字：UPKCCZDPKSBNFJGLMXBVJUPKDITETKTBODSSBSKS
如果知道“BIG”就是密钥，收件人就可以很容易地通过相应的位置改变字母位置，从而译出经过加密的文字。
很多年以来，维热纳尔（Vigenère）密码都被认为是不可破解的，但查尔斯·巴贝奇（CharlesBabbage），一个独立的英国富人在19世纪50年代向人们展示了事实并非如此。顺便提一句，这个人也因为其在计算机科学领域方面所进行的先锋性工作而被世人所熟悉。巴贝奇（Babbage）通过寻找重复的字母段破解了这个密码系统。当然，维热纳尔密码的优势在于这种密码被假定为它将不同位置的字母进行不同的加密。比如同一段文字中的“THE”可能在前面表现为“UPK”，但在后面则被表现为“BNF”。同样，象“AKER”这样的字母也会被进行不同的加密。但是，第一个和第三个“THE”都会被编码为“UPK”。第一个“THE”中的“T”会用“B”来进行编码，而第三个“THE”中的“T”也同样是用“B”来编码。发生这种情况是因为第三个“THE”是排在第一个“THE”后面第21个字母，而3字密钥BIG会在重复7次之后又回到了最开始。在任何比密钥要长得多的加密信息中，都会不可避免地出现类似这样的重复。而一个解密者应该如何才能揭示加密文件的真正面目呢？比如，如果加密文字“UPK”出现了两次，中间隔着21个字母，那么他就可以推断出密钥的长度是21的整除数。或者换种说法，他可以推断出21是密钥的倍数。（约数或称除数是一个数字被除之后不会有余数。比如21的除数就是1、3、7和21。）如果获得了足够多类似的线索，解密者就可以知道密钥的确切长度。一旦他知道了密钥长度，他就可以对加密信息进行日常频率分析。注意，数学在解密工作中总是放在首位的：解密者首先会计算出密钥的长度，这步工作甚至是在他要考虑密钥的具体内容是什么之前所要做的。
巴贝奇的独具创意的技巧开创了一片密码术的新田地，并且将数学工具引入到了以前被认为专属于文字学的领域之中。即使一种编密码系统没有明确地使用数学，但其中隐藏的格式却通常需要以数学的方式进行整理。
自从频率分析法出现后，单字母替换密码完全失去了效用。因此，密码编码者想方设法去编一种更强大的密码。一些编码者对单字母替换密码做了一些改动，如在编码过程中，加入一些特殊的字符，或者令一些字母不代表另一个字母，而是代表一种程式，譬如是代表空格，代表删去前一个字母，代表换行等。但这一切起的作用并不大，聪明的破译师仍然能在里面找到许许多多破译密码的线索。直到有一天，佛罗伦萨的里昂巴蒂斯特·阿尔伯提提出了一种多字母替换密码，即是用两个或两个以上的密码表交替使用来进行加密，如：
明码表ABCDEFGHIJKLMNOPQRSTUVWXYZ
密码表1QWERTYUIOPASDFGHKJLZXCVBNM
密码表2EKPRJBDNCVOUHTYWZXMLASFIGQ
第一个密码表加密第一个字母，第二个密码表加密第二个字母，第一个密码表又加密第三个字母，不断地重复......那么：
明文FOREST
密文YYJJLL
这样，按原来的方法进行频率分析就没有什么作用了。这只是两个密码表时的情况，如果用三个，四个或以上的密码表后，破译就显得非常非常困难。即使是这样，阿尔伯提未能把他的理念发展成一个完整的系统。这个任务当然由后人完成了。经过几个人的努力，最后，维热纳尔终于将其完善了。他编出了一个系统而有效的密码。那就是维热纳尔密码，其主要构成是维热纳尔方阵：
abcdefghijklmnopqrstuvwxyz
1BCDEFGHIJKLMNOPQRSTUVWXYZA
2CDEFGHIJKLMNOPQRSTUVWXYZAB
3DEFGHIJKLMNOPQRSTUVWXYZABC
4EFGHIJKLMNOPQRSTUVWXYZABCD
5FGHIJKLMNOPQRSTUVWXYZABCDE
6GHIJKLMNOPQRSTUVWXYZABCDEF
7HIJKLMNOPQRSTUVWXYZABCDEFG
8IJKLMNOPQRSTUVWXYZABCDEFGH
9JKLMNOPQRSTUVWXYZABCDEFGHI
10KLMNOPQRSTUVWXYZABCDEFGHIJ
11LMNOPQRSTUVWXYZABCDEFGHIJK
12MNOPQRSTUVWXYZABCDEFGHIJKL
13NOPQRSTUVWXYZABCDEFGHIJKLM
14OPQRSTUVWXYZABCDEFGHIJKLMN
15PQRSTUVWXYZABCDEFGHIJKLMNO
16QRSTUVWXYZABCDEFGHIJKLMNOP
17RSTUVWXYZABCDEFGHIJKLMNOPQ
18STUVWXYZABCDEFGHIJKLMNOPQR
19TUVWXYZABCDEFGHIJKLMNOPQRS
20UVWXYZABCDEFGHIJKLMNOPQRST
21VWXYZABCDEFGHIJKLMNOPQRSTU
22WXYZABCDEFGHIJKLMNOPQRSTUV
23XYZABCDEFGHIJKLMNOPQRSTUVW
24YZABCDEFGHIJKLMNOPQRSTUVWX
25ZABCDEFGHIJKLMNOPQRSTUVWXY
26ABCDEFGHIJKLMNOPQRSTUVWXYZ
它的明码表后有26个密码表，每个表相对前一个发生一次移位。如果只用其中某一个进行加密，那么只是简单的恺撒移位密码。但用方阵中不同的行加密不同的字母，它就是一种强大的密码了。加密者可用第7行来加密第一个字母，再用第25行来加密第二个字母，然后根据第8行来加密第三个字母等。
现在来试一下，就用关键词FOREST来加密Bettertodowellthantosaywell.
关键词FORESTFORESTFORESTFORESTFOR
明文bettertodowellthantosaywell
密文GSKXWKYCUSOXQZKLSGYCJEQPJZC
（看第5行，F开头，明文是b，要用G来加密；第14行，O开头，明文是e，要用S来加密，如此类推......）
维热纳尔密码既克服了频率分析，又具有数目众多的密钥。发送者和接收者可使用字典里任一个单词，或单词组合，或虚构的词作为关键词。它提供了很好的安全保障，但它的复杂性，却令其等到19世纪才流行起来。不过，也是在19世纪，查尔斯·巴比奇－－－一个性情古怪的天才将其破译了。让我们来看看解密的过程：
首先，破译的第一步就是寻找密文中出现超过一次的字母。有两种情况可能导致这样的重复发生。最有可能的是明文中同样的字母序列使用密钥中同样的字母加了密；另外还有一种较小的可能性是明文中两个不同的字母序列通过密钥中不同部分加了密，碰巧都变成了密文中完全一样的序列。假如我们限制在长序列的范围内，那么第二种可能性可以很大程序地被排除，这种情况下，我们多数考虑到4个字母或4个以上的重复序列。
破译的第二步是确定密钥的长度，又看看这一段先：
关键词FORESTFORESTFORESTFORESTFOR
明文bettertodowellthantosaywell
密文GSKXWKYCUSOXQZKLSGYCJEQPJZC
第一个YC出现后到第二个YC的结尾一共有12个字母（USOXQZKLSGYC）
那么密钥的长度应是12的约数－－－1，2，3，4，6，12之中的一个（其中，1可排除）。
如下面的密文：
ISWZPNQCKMYYYJKAYYEZFFSWEESSPGZXQAHF
ISWZPNQCKMTVYJOACVEHAESAZRLTPQIZMXOT
QSWMCVUDSIJGGDEUWAZRSFXWILKUEJQLDACB
GDLYJXMYLMDQKZMPLDILQEMWFSWDPAZEZQNW
DYWDZXFSAEEAZJDUELVPTMCEKWSEEFURZFSW
DPXACQAFKMXWAWVEZFSDBGDLAYUQXGDPEKWS
EEFURZFSWDPOUEZKZMYLQNPQQDEMJTQYGUVA
ZOGRWAWPVUEQAFJQJGGCOMJZAHQAFKTJDKAD
MNWPJGGCWKPKAYEQZZPTVKZMQGWDVFAHLTLL
USSPXAZPGZJGGOSDWAZRKAEZQCWKZMMCWITL
TEZMEDAZCAYQAFJRLUQLKUQQAFJQYWHPJTFJ
FLKUQQAFJQYWHPJPZOZDZMWDUMWFSWAYWRZJ
KZMISGBTFOSEEJGGDGREDKMMFDMDPARQJAHF
UDKTZOZEZQYAITDXVFAHLTLLKZMMCWZZVDPS
YPJ
在里面重复序列有ISWZPNQCKM，BGDL，SEEFURZFSWDP，
JGGC，LKUQQAFJQYWHPJ，VFAHLTLL等；
如果每个重复间隔都能被3整除，关键词应该有三个字母。
下一步，仍旧是频率分析，不过，因为关键词有三个字母，我们应分为三组进行。把第1，4，7，10，13......个字母分为一组，称之为L1，把第2，5，8，11，14......个字母又分为一组，称之为L2，余下的归另一组，称之为L3。那么每一组有169个字母。
现在先做一个标准频率分布表：
用169乘以各个字母的标准百分比，如字母A，169*8.2%＝14。
那么由标准频率：
A:8.2N:6.7
B:1.5O:7.5
C:2.8P:1.9
D:4.3Q:0.1
E:12.7R:6.0
F:2.2S:6.3
G:2.0T:9.1
H:6.1U:2.8
I:7.0V:1.0
J:0.2W:2.4
K:0.8X:0.2
L:4.0Y:2.0
M:2.4Z:0.1
得到标准个数：
A:14N:11
B:3O:13
C:5P:3
D:7Q:0
E:21R:10
F:4S:11
G:3T:15
H:10U:5
I:12V:2
J:0W:4
K:1X:0
L:7Y:3
M:4Z:0
然后，统计L1的169个字母出现的次数，有：
A:22N:1
B:1O:1
C:0P:5
D:10Q:16
E:10R:5
F:9S:2
G:7T:7
H:2U:14
I:9V:1
J:0W:1
K:11X:2
L:0Y:5
M:14Z:14
又作出L1的图表（histogram），与标准图表对比一下。标准频率和L1的频率都有峰值，平稳期和低谷。它们之间的区别在于相互错开了一些位置，比较两者应该可以寻找出最显著的特征。例如，看L1图表中A－F这一段，A的峰值过后是低谷，特别是C没有出现，然后是一段平稳期，这与标准频率中的O－T这一段相像；标准频率中，O的前面I－N这一段和L1中U－Z一段也大致吻合；又看看，L1中，J和L的缺失应该就是标准频率中X和Z的缺失，M－Q这一段应就是标准频率中A－E这一段。这就暗示着L1的密码表是由M，N，O，P......开始的。把L1的图表向左平移12个单位再与标准频率对比，整体来说差不多。由此可知，关键词的第一个字母是M。（注意，一些误差是在所难免的，如K替换Y，两图表比较起来好像不很符合，但整体来说是差不多的，我们就可忽略过去。）
继续下来，统计L2中169个字母出现的次数，可以确定关键词的第二个字母是L。
最后，用同样的方法可确定关键词的第三个字母是S。
至此，得到整个关键词是MLS。
再用维热纳尔方阵将密文翻译过来，得到明文：
Wheneversangmysongs
Onthestageonmyown
Wheneversaidmywords
Wishingtheywouldbeheard
Isawyousmilingatme
Wasitrealorjustmyfantasy
You'dalwaysbethereinthecorner
Ofthistinylittlebar
Mylastnighthereforyou
Sameoldsongsjustoncemore
Mylastnightherewithyou
Maybeyesmaybeno
Ikindoflikedityou'reyourway
Howyoushylyplacedyoureyesonme
Ohdidyoueverknow
ThatIhadmineonyou
Darlingsothereyouare
Withthatlookonyourface
Asifyou'reneverhurt
Asifyou'reneverdown
ShallIbetheoneforyou
Whopinchesyousoftlybutsure
Iffrownisshownthen
Iwillknowthatyouarenodreamer
技巧编辑本段回目录
1.A－E段，U－Z段以及O－T段的特征比较显著，可先从这些方面着手；
2.如果一些字符串出现的频率较多，不妨猜猜，特别要注意THE，-ING等的出现；
3.要留意那些图表中没有出现的字母，很多时候也会是突破点，如X与Z的空缺。
相关分类编辑本段回目录
相关词条编辑本段回目录
参考文献编辑本段回目录
《密码编码和密码分析：原理与方法》 2001-09-01 机械工业出版社
《编码理论(第二版)》 2007年9月 西安电子科技大学出版社
《密码编码学与网络安全-原理实践(英文版)(第四版)》 2006年7月1日 电子工业出版社
《编码密码学》 1992年12月 人民邮电出版社
