维吉尼亚密码

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

 

为了生成密码,需要使用表格法。这一表格(如图1所示)包括了26行字母表,每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的,在过程中会不断地变换。
例如,假设明文为:
ATTACKATDAWN
选择某一关键词并重复而得到密钥,如关键词为LEMON时,密钥为:
LEMONLEMONLE
对于明文的第一个字母A,对应密钥的第一个字母L,于是使用表格中L行字母表进行加密,得到密文第一个字母L。类似地,明文第二个字母为T,在表格中使用对应的E行进行加密,得到密文第二个字母X。以此类推,可以得到:
明文:ATTACKATDAWN密钥:LEMONLEMONLE密文:LXFOPVEFRNHR
解密的过程则与加密相反。例如:根据密钥第一个字母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加密成不同的密文:
密钥:ABCDEF AB CDEFA BCD EFABCDEFABCD
明文:CRYPTO IS SHORT FOR CRYPTOGRAPHY
密文:CSASXT IT UKSWT GQU GWYQVRKWAQJB
此时明文中重复的元素在密文中并不重复。然而,如果密钥相同的话,结果可能便为(使用密钥ABCD):
密钥:ABCDAB CD ABCDA BCD ABCDABCDABCD
明文:CRYPTO IS SHORT FOR CRYPTOGRAPHY
密文:CSASTP KV SIQUT GQU CSASTPIUAQJB
此时卡西斯基试验就能产生效果。对于更长的段落此方法更为有效,因为通常密文中重复的片段会更多。如通过下面的密文就能破译出密钥的长度:
密文:DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD
其中,两个DYDUXRMH的出现相隔了18个字母。因此,可以假定密钥的长度是18的约数,即长度为18、9、6、3或2。而两个NQD则相距20个字母,意味着密钥长度应为20、10、5、4或2。取两者的交集,则可以基本确定密钥长度为2。
 

弗里德曼试验

弗里德曼试验由威廉·F·弗里德曼(William F. Friedman)于1920年代发明。他使用了重合指数(index of coincidence)来描述密文字母频率的不匀性,从而破译密码。

 

指目标语言中两个任意字母相同的概率(英文中为0.067),

 

指字母表中这种情况出现的概率(英文中为1/26=0.0385),从而密钥长度可以估计为:

 

其中,观察概率为

 

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

频率分析

一旦能够确定密钥的长度,密文就能重新写成多列,列数与密钥长度对应。这样每一列其实就是一个凯撒密码,而此密码的密钥(偏移量)则对应于维吉尼亚密码密钥的相应字母。与破译凯撒密码类似的方法,就能将密文破译。
柯克霍夫方法作为卡西斯基试验的改进,由奥古斯特·柯克霍夫(Auguste Kerckhoffs)提出。它将每一列的字母频率与转换后的明文频率相对应而得出每一列的密钥字母。一旦密钥中每一个字母都能确定,就能很简单地破译密文,从而得到明文。如果维吉尼亚字母表表格本身是杂乱而非按通常字母表顺序的话,那柯克霍夫方法就会无效,但卡西斯基试验和重复指数对于决定密钥长度仍旧是有效的。
 
/*** @description 维吉尼亚加密算法* @param {string} str 明文* @param {string} key 秘钥* @return {Boolean}*/
const encrypt = function (str, key) {const strArr = [];const keyArr = [];const res = [];for (let i = 0; i < str.length; i++) {strArr.push(str[i].charCodeAt() - 65);}for (let i = 0; i < key.length; i++) {keyArr.push(key[i].charCodeAt() - 65);}for (let i = 0; i < strArr.length; i++) {res.push(String.fromCharCode(((strArr[i] + keyArr[i % key.length]) % 26) + 65));}return res.join("");
};
console.log(encrypt("ATTACKATDAWN", "LEMONLEMONLE"));

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ulsteruni.cn/article/24337604.html

如若内容造成侵权/违法违规/事实不符,请联系编程大学网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

springboot学习

SpringBoot1 SpringBoot2 SpringBoot3 SpringBoot4 SpringBoot5 SpringBoot6 SpringBoot7 shiro 简介: 入门: 整合shiro 导包 写Controller 报错点击查看代码org.thymeleaf.exceptions.TemplateInputException: Error resolving template [index], template might not exist …

洛谷 P1656 炸铁路

题意:n个点,m条边,问有哪条边是去掉之后,会造成之前连通的点不再连通的?n <= 150, m <= 5000. 思路:连通算法有dfs+bool数组记录,或者dsu,感觉dsu更方便。m * n 不超过1e6,直接暴力。 class DisjointSet{ public:DisjointSet(int sz): sz_(sz){set_size_.assign…

Codegen方言介绍

Codegen方言介绍 主要介绍CodeGen过程中使用的Dialect(方言),以及对设计演变的一些观察。 介绍 对MLIR基础架构中CodeGen功能的简化概述,特别是LLVM项目代码库中可用的部分(upstream或intree)。虽然偶尔会提到LLVM项目代码库之外的MLIR用户,但没有被深入分析,只是为了说明…

结对项目:四则运算题目生成器

这个作业属于哪个课程 软件工程2024这个作业要求在哪里 结对项目这个作业的目标 学会两个人合作完成一个项目,了解如何分工合作Github地址:点击进入仓库 队员介绍成员姓名 学号杨文琦 3222004727韦兰健 3222004724一、PSP表格PSP2.1 Personal Software Process Stages 预估耗…

【EF Core】EFCore 8.0 -CodeFirst方式生成SQLite实体对象

EFCoreFirst使用流程 1、引入工具包Microsoft.EntityFrameworkCore.SqlServer 核心程序包,封装了关键的核心代码,使用EF必须引用这个包Microsoft.EntityFrameworkCore.Design 设计包,用于在命令行工具下EF Core开发的工具套件Microsoft.EntityFrameworkCore.Tools 用于数据库…

【EF core】模型可视化 EF Core Power Tools 【工具】

Visual Studio中的EF Core Power Tools 扩展来可视化模型。编程是个人爱好