族谱网 头条 人物百科

维吉尼亚密码

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:1571
转发:0
评论:0
历史南军曾使用过的密码盘的仿制品,目前实物只有五件存世。多表密码最早在1467年左右由莱昂·巴蒂斯塔·阿尔伯蒂提出,他使用了一个金属密码盘来切换密码表,只是这个系统只能做些有限的转换。后来1508年时,约翰尼斯·特里特米乌斯《隐写术》(Steganographia)中发明的表格法(tabularecta)成为了维吉尼亚密码的关键部分。然而当时此方法只能对密码表做一些简单的、可预测的切换。这一加密技术也称为特里特米乌斯密码。这一方法真正出现是在吉奥万·巴蒂斯塔·贝拉索于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的算术》中。他以特里特米乌斯的表格法为基础,同时引入了密钥的概念。布莱斯·德·维吉尼亚于1586年亨利三世时期发明了更为简单却又更有效的自动密钥密码(autokeycipher)。之后,19世纪时贝拉索的方法被误认为是由维吉尼亚首先发明的。大卫·卡恩在《破译者(TheCodebr...

历史

维吉尼亚密码

南军曾使用过的密码盘的仿制品,目前实物只有五件存世。

多表密码最早在1467年左右由莱昂·巴蒂斯塔·阿尔伯蒂提出,他使用了一个金属密码盘来切换密码表,只是这个系统只能做些有限的转换。后来1508年时,约翰尼斯·特里特米乌斯《隐写术》(Steganographia)中发明的表格法(tabula recta)成为了维吉尼亚密码的关键部分。然而当时此方法只能对密码表做一些简单的、可预测的切换。这一加密技术也称为特里特米乌斯密码。

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

布莱斯·德·维吉尼亚于1586年亨利三世时期发明了更为简单却又更有效的自动密钥密码(autokey cipher)。之后,19世纪时贝拉索的方法被误认为是由维吉尼亚首先发明的。大卫·卡恩在《破译者(The Codebreakers)》中对此表示遗憾,他写道“历史忽略了这一重要贡献,将其归功于维吉尼亚,虽然他对此并不知道”。

由于破译的难度很高,维吉尼亚密码也因此获得了很高的声望。知名作家、数学家查尔斯·路特维奇·道奇森(笔名路易斯·卡罗)在其1868年所编、收于一儿童杂志的《字母表密码(The Alphabet Cipher)》中称其是不可破译的。1917年,《科学美国人》将维吉尼亚密码称为“无法被转化的”。 然而,维吉尼亚密码却配不上这样的称号。查尔斯·巴贝奇完成了破译的工作,但他没有将此发表。 之后,弗里德里希·卡西斯基(Friedrich Kasiski)于19世纪完全破解并发表了他的方法。甚至在此之前,一些资深密码分析家在16世纪就能偶尔将其破解。

维吉尼亚密码足够地易于使用使其能够作为战地密码。 例如,美国南北战争期间南军就使用黄铜密码盘生成维吉尼亚密码。北军则经常能够破译南军的密码。战争自始至终,南军主要使用三个密钥,分别为“Manchester Bluff(曼彻斯特的虚张声势)”、“Complete Victory(完全的胜利)”以及战争后期的“Come Retribution(报应来临)”。

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

描述

维吉尼亚密码

用来加密解密的维吉尼亚表格

在一个凯撒密码中,字母表中的每一字母都会作一定的偏移,例如偏移量为3时, A 就转换为了 D 、 B 转换为了 E ……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。

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

例如,假设明文为:

选择某一关键词并重复而得到密钥,如关键词为 LEMON 时,密钥为:

对于明文的第一个字母 A ,对应密钥的第一个字母 L ,于是使用表格中 L 行字母表进行加密,得到密文第一个字母 L 。类似地,明文第二个字母为 T ,在表格中使用对应的 E 行进行加密,得到密文第二个字母 X 。以此类推,可以得到:

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

用数字0-25代替字母 A - Z ,维吉尼亚密码的加密文法可以写成同余的形式:

解密方法则能写成:

密码破译

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

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

卡西斯基试验

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

卡西斯基试验是基于类似 the 这样的常用单词有可能被同样的密钥字母进行加密,从而在密文中重复出现。例如,明文中不同的 CRYPTO 可能被密钥 ABCDEF 加密成不同的密文:

此时明文中重复的元素在密文中并不重复。然而,如果密钥相同的话,结果可能便为(使用密钥 ABCD ):

此时卡西斯基试验就能产生效果。对于更长的段落此方法更为有效,因为通常密文中重复的片段会更多。如通过下面的密文就能破译出密钥的长度:

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

弗里德曼试验

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

其中,观察概率为

其中, c 是指字母表的长度(英文为26), N 指文本的长度, n 1 到 n c 是指密文的字母频率,为整数。

此方法只是一种估计,会随着文本长度的增加而更为精确。在实践中,会尝试接近此估计的多个密钥长度。 一种更好的方法是将密文写成矩阵形式,其中列数与假定的密钥长度一致,将每一列的重合指数单独计算,并求得平均重合指数。对于所有可能的密钥长度,平均重合指数最高的最有可能是真正的密钥长度。 这样的试验可以作为卡西斯基试验的补充。

频率分析

一旦能够确定密钥的长度,密文就能重新写成多列,列数与密钥长度对应。这样每一列其实就是一个凯撒密码,而此密码的密钥(偏移量)则对应于维吉尼亚密码密钥的相应字母。与破译凯撒密码类似的方法,就能将密文破译。

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

变体

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

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

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

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

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

参见

博福特密码


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱

相关资料

展开
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 布莱斯·德·维吉尼亚
生平维吉尼亚出生于法国圣布尔善市(Saint-Pourçain-sur-Sioule)。17岁时开始了他的外交生涯,直至1570年退休。在职业生涯的前期,他曾作为一个初级秘书参加过沃木斯议会。24岁时,他来到讷韦尔担任一位公爵的秘书,直到1562该公爵的儿子也去世为止。他也担任过亨利三世(法兰西)的秘书。1549年、1566年他两次访问罗马执行外交任务。在这两次旅途中,他阅读了许多密码学书籍并与一些密码学家有过接触。当他于47岁退体时,他在巴黎向穷人捐出了一年的收入,共1000里弗尔。1596年,维吉尼亚由于喉癌去世。著作在其退休期间,他出版了超过20本书,其中包括:TraictédeCometesTraictédesChiffresouSecrètesManièresd"Escrire(1586年)Traic...
· 密码学
术语直到现代以前,密码学几乎专指加密算法:将普通信息(明文)转换成难以理解的数据(密文)的过程;解密算法则是其相反的过程:由密文转换回明文;加解密包含了这两种算法,一般加密即同时指称加密与解密的技术。加解密的具体运作由两部分决定:一个是算法,另一个是密钥。密钥是一个用于加解密算法的秘密参数,通常只有通信者拥有。历史上,密钥通常未经认证或完整性测试而被直接使用在加解密上。密码协议是使用密码技术的通信协议。近代密码学者多认为除了传统上的加解密算法,密码协议也一样重要,两者为密码学研究的两大课题。在英文中,“cryptography”和“cryptology”都可代表密码学,前者又称密码术。但更严谨地说,前者(cryptography)指密码技术的使用,而后者(cryptology)指研究密码的学科,包含密码术与密码分析。密码分析是研究如何破解密码学的学科。但在实际使用中,通常都称密码学(即cr...
· 密码分析
密码分析的历史密码分析和密码学是共同演化的。这从密码学史中可以看得很明显。总是有新的密码机被设计出来并取代已经被破解的设计,同时也总是有新的密码分析方法被发明出来以破解那些改进了的方案。事实上,密码和密码分析是同一枚硬币的正反两面:为了创建安全的密码,就必须考虑到可能的密码分析。经典密码分析尽管“密码分析”这个词是晚近出现的(1920年由WilliamFriedman(英语:William_Friedman)确立),但破解密码和密码机的方法却已经存在很久了。世界上最早的破解密码方法的文字记录可以追溯到九世纪阿拉伯通才AlKindi(英语:Abu_Yusuf_Yaqub_ibn_Ishaq_al-Sabbah_Al-Kindi)所著《破解密码信息》(AManuscriptonDecipheringCryptographicMessages),这篇文章论述了一个频率分析的方法。频率分析是破解经...
· 凯撒密码
例子恺撒密码的替换方法是通过排列明文和密文字母表,密文字母表示通过将明文字母表向左或向右移动一个固定数目的位置。例如,当偏移量是左移3的时候(解密时的密钥就是3):使用时,加密者查找明文字母表中需要加密的消息中的每一个字母所在位置,并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作,得到原来的明文。例如:恺撒密码的加密、解密方法还能够通过同余的数学方法进行计算。首先将字母用数字代替,A=0,B=1,...,Z=25。此时偏移量为n的加密方法即为:解密就是:历史和用途恺撒曾经使用这种密码与其将军们联系根据苏维托尼乌斯的记载,恺撒曾用此方法对重要的军事信息进行加密:“如果需要保密,信中便用暗号,也即是改变字母顺序,使局外人无法组成一个单词。如果想要读懂和理解它们的意思,得用第4个字母置换第一个字母,即以D代A,余此类推。”——苏维托尼乌斯,罗马十二帝王传同样,奥古斯都也...
· 经典密码
经典密码的类型经典密码大致上分为替换式密码和移项式密码。替换式密码代换密码是字母(或是字母群)作有系统的代换,直到讯息被替换成其它难以解读的字。凯撒密码凯撒密码是广为人知的代换密码。为了用凯撒密码法加密讯息,每个密码字母集中的字母将会被其位置的后3个字母替代。因此字母A将会被字母D替代、字母B将会被字母E替代、字母C将会被字母F替代等,最后,X、Y和Z将分别的被替代成A、B和C。另一种代换密码是使用关键字,你可以选择一个单字或是短词组并去除所有的空格和重复的字母,接着把它当作密码字母集的开头。最后记得去除掉关键字的字母把其它字母接续排序。例如,如果关键字是CIPHER,则密码字母表是这样写的:一般字母:abcdefghijklmnopqrstuvwxyz密码字母:cipherstuvwxyzabdfgjklmnoq维吉尼亚密码凯撒密码的例子是所有单字母替代式密码(英语:monoalphab...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信