kasiski法的来源,历史,基本原理,加解密方法并举例说明

Question

kasiski法的来源,历史,基本原理,加解密方法并举例说明

Answer 1

一、背景
公元16世纪晚期,法国外交官维吉尼亚（Vigenere）提出著名的维吉尼亚方阵密表和维吉尼亚密码(Vigenerecypher),这是一种多表加密的替代密码.Vigenere密码的出现,使得先前对单表置换用的简单频率分析方法失效.
公元1863年,普鲁士少校卡西斯基（Kasiski）提出了Kasiski法,此方法从密钥的长度着手破解Vigenere密码.
二、基本思想
通常,用Vigenere密码加密,明文中的相同字母在密文中不会对应相同的字母.但是,如果两个相同字母序列间距正好是密钥长度的倍数时,也可能产生相同的密文序列.寻找重复出现的字母序列,并求其长度的过程被称为Kasiski试验,即Kasiski法.
Kasiski法在解密Vigenere密码时,利用的是多表体系的弱点：相同的明文字母组,在明文序列中间隔的字母数为d（d是密钥的长度）的倍数时,则明文字母组对应的密文字母组也必相同.反之则不一定,但相同的概率很大.如果将密文中相同字母组找出来,并对其间隔的距离进行研究,找出它们的最大公因子,则该因子是密钥长度的概率是较大的.
三、基本原理
基于Kasiski法的基本思想,Kasiski法测试过程如下：首先对密文中任意两个紧邻字符的出现位置进行统计,然后记下它们各次间出现的间隔.然后写出这些间隔对应数字的因数,最后对这些因数进行统计,一般来说,次数出现最多的几个因数极有可能就是密钥字符串的长度.其依据是,对于两个连续出现的字符在这次与下次出现的间隔极有可能是采用相同密钥加密形成的,从而这之间的间隔也极有可能就是密钥长度的倍数.
一般在使用Kasiski法测试密钥长度时,先搜索长度至少为3的相同的密文段,记录这些相同密文段到起始点之间的距离；假如得到如下几个距离X1,X2,…,猜测密钥长度m为这些Xi的最大公因子的因子.
四、应用步骤
1、在密文中标出重复的三个或多个字符结构；
2、对每一个字符结构,记下结构的起始位置；
3、计算相邻的起始点的距离；
4、对每个距离求出所有因数；
5、若使用多字母替换密码,则密钥的长度为步骤4种出现的某一因数；
五、应用举例
明文：we are discovered save yourself
密钥：deceptive
加密算法：Vigenere算法
密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ
1、在密文中标出重复的字符结构——VTW；
2、两个字符结构的起始位置分别为4和13；
3、两个起始点的距离是9；
4、9的因数有3和9；
5、根据步骤4出现的因数,确定密钥的可能长度是3位或9位.