学号:16030140019
姓名: 莫益彰
【嵌牛导读】:凯撒密码是一种简单的加密方法,即将文本中的每一个字符都位移相同的位置。如选定位移3位:
原文:a b c
密文:d e f
由于出现了字母频度分析,凯撒密码变得很容易破解,因此人们在单一恺撒密码的基础上扩展出多表密码,称为“维吉尼亚”密码。
【嵌牛鼻子】密码学,计算机安全。
【嵌牛提问】维吉尼亚怎么破解,8位维吉尼亚是否可破?维吉尼亚算法的时间复杂度?
【嵌牛正文】
维吉尼亚密码的加密
维吉尼亚密码由凯撒密码扩展而来,引入了密钥的概念。即根据密钥来决定用哪一行的密表来进行替换,以此来对抗字频统计。假如以上面第一行代表明文字母,左面第一列代表密钥字母,对如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
当选定RELATIONS作为密钥时,加密过程是:明文一个字母为T,第一个密钥字母为R,因此可以找到在R行中代替T的为K,依此类推,得出对应关系如下:
密钥:RE LA TI ONS RE LA TION SR ELA TIONSREL
明文:TO BE OR NOT TO BE THAT IS THE QUESTION
密文:KS ME HZ BBL KS ME MPOG AJ XSE JCSFLZSY
图解加密过程:
在维吉尼亚(Vigenère)的密码中,发件人和收件人必须使用同一个关键词(或者同一文字章节),这个关键词或文字章节中的字母告诉他们怎么样才能前后改变字母的位置来获得该段信息中的每个字母的正确对应位置。
维吉尼亚密码的破解
维吉尼亚密码分解后实则就是多个凯撒密码,只要知道密钥的长度,我们就可以将其分解。
如密文为:ABCDEFGHIJKLMN
如果我们知道密钥长度为3,就可将其分解为三组:
组1:A D G J N
组2:B E H K
组3:C F I M
分解后每组就是一个凯撒密码,即组内的位移量是一致的,对每一组即可用频度分析法来解密。
所以破解维吉尼亚密码的关键就是确定密钥的长度。
确定密钥长度
确定密钥长度主要有两种方法,Kasiski 测试法相对简单很多,但Friedman 测试法的效果明显优于Kasiski 测试法。
Kasiski 测试法
在英文中,一些常见的单词如the有几率被密钥的相同部分加密,即原文中的the可能在密文中呈现为相同的三个字母。
在这种情况下,相同片段的间距就是密文长度的倍数。
所以我们可以通过在密文中找到相同的片段,计算出这些相同片段之间的间距,而密钥长度理论上就是这些间距的公约数。
然后我们需要知道重合指数(IC, index of coincidence)的概念。
重合指数表示两个随机选出的字母是相同的的概率,即随机选出两个A的概率+随机选出两个B的概率+随机选出两个C的概率+……+随机选出两个Z的概率。
对英语而言,根据上述的频率表,我们可以计算出英语文本的重合指数为
P(A)^2 + P(B)^2+……+P(Z)^2 = 0.65
利用重合指数推测密钥长度的原理在于,对于一个由凯撒密码加密的序列,由于所有字母的位移程度相同,所以密文的重合指数应等于原文语言的重合指数。
据此,我们可以逐一计算不同密钥长度下的重合指数,当重合指数接近期望的0.65时,我们就可以推测这是我们所要找的密钥长度。
举例来说,对密文ABCDEABCDEABCDEABC
首先测试密钥长度=1,对密文ABCDEABCDEABCDEABC统计每个字符出现的次数:
A: 4 B: 4 C: 4 D:3 E:3
那么对于该序列的重合指数就为:(4/18)^2 + (4/18)^2 + (4/18)^2 +(3/18)^2 +(3/18)^2 != 0.65
然后测试密钥长度=2,将密文ABCDEABCDEABCDEABC分解为两组:
组1:A C E B D A C E B
组2:B D A C E B D A C
我们知道如果密钥长度真的是2,那么组1,组2都是一个凯撒密码。对组1组2分别计算重合指数。
如果组1的重合指数接近0.65,组2的重合指数也接近0.65,那么基本可以断定密钥长度为2。
在知道了密钥长度n以后,就可将密文分解为n组,每一组都是一个凯撒密码,然后对每一组用字母频度分析进行解密,和在一起就能成功解密凯撒密码。
上文已经说到,自然语言的字母频度是一定的。字母频度分析就是将密文的字母频度和自然语言的自然频度排序对比,从而找出可能的原文。
根据苏维托尼乌斯的记载,恺撒曾用此方法对重要的军事信息进行加密: 如果需要保密,信中便用暗号,也即是改变字母顺序,使局外人无法组成一个单词。如果想要读懂和理解它们的意思,得用第4个字母置换第一个字母,即以D代A,余此类推。
同样,奥古斯都也使用过类似方式,只不过他是把字母向右移动一位,而且末尾不折回。每当他用密语写作时,他都用B代表A,C代表B,其余的字母也依同样的规则;用A代表Z。
扩展资料:
密码的使用最早可以追溯到古罗马时期,《高卢战记》有描述恺撒曾经使用密码来传递信息,即所谓的“恺撒密码”,它是一种替代密码,通过将字母按顺序推后起3位起到加密作用,如将字母A换作字母D,将字母B换作字母E。因据说恺撒是率先使用加密函的古代将领之一,因此这种加密方法被称为恺撒密码。这是一种简单的加密方法,这种密码的密度是很低的,只需简单地统计字频就可以破译。 现今又叫“移位密码”,只不过移动的为数不一定是3位而已。
参考资料来源:百度百科-凯撒密码
经典密码由于规律性很强,通常很容易被破解。许多经典密码可单单经由密文而破解,所以它们容易受到唯密文攻击法攻击(ciphertext-only attack)。有些经点密码(像是凯撒密码)的金钥个数有限,所以这类密码可以使用暴力破解尝试所有的金钥。替代式密码有比较大的金钥数,但是容易被频率分析,因为每个密码字母各代表了一个明文字母。Polyalphabetic密码,像是维琼内尔密码使用多个替换防止了简单的频率分析,然而,更先进的技术Kasiski examination就可用来破解这类密码。
另一方面,现代密码的设计可以承受更强大的ciphertext-only attacks。一个优秀的现代密码必须保证广泛潜在的攻击,包括known-plaintext attack和chosen-plaintext attack以及chosen-ciphertext attack。对于密码破解者来说,应不能够找到关键,即使他知道明文和对应的密码文、即是他可以选择明文或密码文。经典密码再也不能满足这些强大的标准,因此,有兴趣者再也不拿它来作安全应用了。
经典密码大致上分为替代式密码和移位式密码,具体原理看下面加粗字体
凯撒密码是广为人知的替代式密码。为了用凯撒密码法加密讯息,每个密码字母集中的字母将会被其位置的后3个字母替代。因此字母A将会被字母D替代、字母B将会被字母E替代、字母C将会被字母F替代等,最后,X、Y和Z将分别的被替代成A、B和C。
例如,"WIKIPEDIA"将被加密成"ZLNLSHGLD"。凯撒把字母向后移"3"位,但其他数字也可照著作。
另一种替代式密码是使用关键字,你可以选择一个单字或是短词组并去除所有的空格和重复的字母,接着把它当作密码字母集的开头。最后记得去除掉关键字的字母把其它字母接续排序。
移位式密码,它们字母本身不变,但它们在讯息中顺序是依照一个定义明确的计划改变。许多移位式密码是基于几何而设计的。一个简单的加密(也易被破解),可以将字母向右移1位。
例如,明文"Hello my name is Alice."将变成"olleH ym eman si ecilA."。密码棒(scytale)也是一种运用移位方法工具。
一个移位式密码的具体例子columnar cipher.先选择一个关键字,把原来的讯息由左而右、由上而下依照关键字长度转写成长方形。接着把关键字的字母依照字母集顺序编号,例如A就是1、B就是2、C就是3等。例如,关键字是CAT,明文是THE SKY IS BLUE,则讯息应该转换成这样:
C A T 3 1 20 T H E S K Y I S B L U E最后把讯息以行为单位,依照编号大小调换位置。呈现的应该是A行为第一行、C行为第二行、T行为第三行。然后就可以把讯息"The sky is blue"转写成HKSUTSILEYBE。
经典密码的破译
经典密码由于规律性很强,通常很容易被破解。许多经典密码可单单经由密文而破解,所以它们容易受到唯密文攻击法攻击(ciphertext-only attack)。
有些经典密码(像是凯撒密码)的金钥个数有限,所以这类密码可以使用暴力破解尝试所有的金钥。替代式密码有比较大的金钥数,但是容易被频率分析,因为每个密码字母各代表了一个明文字母。
另一方面,现代密码的设计可以承受更强大的ciphertext-only attacks。一个优秀的现代密码必须保证广泛潜在的攻击,包括known-plaintext attack和chosen-plaintext attack以及chosen-ciphertext attack。
对于密码破解者来说,应不能够找到关键,即使他知道明文和对应的密码文、即是他可以选择明文或密码文。经典密码再也不能满足这些强大的标准,因此,有兴趣者再也不拿它来做安全应用了。
以上内容参考 百度百科-经典密码
凯撒密码II通过查询动态密码表,把凯撒单词加密成一些密文数字。
在人类历史上,对信息保护的需求与对信息本身的需求一样久远。第一个用于加密和解密文本的编码方式是凯撒密码。由于原始的凯撒密码较简单,较易被破解。随着考古的进展,人们发现了升级版的凯撒密码II。
如果请你使用现有动态密码表,加密一些单词。你要处理m个操作,操作分成两种:Astringinteger:增加一条凯撒单词string到凯撒密文数字integer的映射规则,如果先前已经有关于这个string的规则,那么用该规则替换原规则。Qstring:查询单词string所对应的最新密文数字。
凯撒密码作为一种最为古老的对称加密体制,在古罗马的时候都已经很流行,他的基本思想是:通过把字母移动一定的位数来实现加密和解密。例如,如果密匙是把明文字母的位数向后移动三位,那么明文字母B就变成了密文的E,依次类推,X将变成A,Y变成B,Z变成C,由此可见,位数就是凯撒密码加密和解密的密钥。 它是一种代换密码。据说恺撒是率先使用加密函的古代将领之一,因此这种加密方法被称为恺撒密码。 在密码学中,恺撒密码(或称恺撒加密、恺撒变换、变换加密)是一种最简单且最广为人知的加密技术。它是一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。这个加密方法是以恺撒的名字命名的,当年恺撒曾用此方法与其将军们进行联系。恺撒密码通常被作为其他更复杂的加密方法中的一个步骤,例如维吉尼亚密码。恺撒密码还在现代的ROT13系统中被应用。但是和所有的利用字母表进行替换的加密技术一样,恺撒密码非常容易被破解,而且在实际应用中也无法保证通信安全。