第2章3-密码分析

密码分析密码学包括密码编码学和密码分析学两部分。密码编码学研究如何构造一个符合规定安全要求的密码系统，即如何设计相应的加密和解密算法、密钥和安全协议，使得密码系统能够达到所需要的安全性。

密码分析学是研究在不知道解密密钥和密码体制的情况下如何恢复明文的科学。这两部分既对立又统一，正是这两者的对立和统一推动了密码学的发展。密码分析目标密码分析的目的是寻找密码算法的弱点，并根据这些弱点对密码进行破译。攻击密码的目标有：1.完全攻破（TotalBreak）

发现密码系统所用的密钥，因此，所有密文均可破译，并且攻击者可以按照自己的需要产生假冒的密文；2.全局演绎（GlobalDeduction）

攻击者找到了解密算法的一个等价算法，无须密钥便可进行解密；3.局部演绎（LocalDeduction）发现一个或多个密文对应的明文，这将为发现实际使用的密钥提供线索；密码分析目标4.信息演绎（InformationDeduction）发现与实际使用的密钥或明文有关的信息，例如密钥的一部分，或明文的格式等。这些信息将有助于进行密钥分析。

5.算法辨别（algorithmdistinguishing）发现正在使用的密码的输出与随机置换的输出不同，它与密码侦察（cipherdetection）有密切关系。在密码侦察中可以区分出正在使用的是哪一种密码算法，这通常是进行其他密码分析的基础。密码分析的手段根据攻击者掌握的密码系统的信息，可以将对密码系统的攻击手段分成以下几种类型：1.唯密文攻击（CiphertextOnlyAttack）

攻击者只有一些用同一算法和同一密钥加密的密文，密码分析的任务是从这些密文尽可能多地恢复出明文，或者推导出密钥，即：已知：c1=Ek(m1)，c2=Ek(m2)，…，ci=Ek(mi)求：m1，m2，…，mi或k。2.已知明文攻击（KnownPlaintextAttack）

攻击者不仅能得到一些密文，而且能得到这些密文对应的明文。密码分析的任务是由此推导出密钥，或一个能解密任何新消息的算法，即：已知：m1，c1=Ek(m1)，m2，c2=Ek(m2),…,mi，ci=Ek(mi)；求：k或一个能由ci+1=Ek(mi+1)推出mi+1的算法。密码分析的手段3.选择明文攻击（ChosenPlaintextAttack）攻击者不仅能得到一些密文和对应的明文，而且能选择用于加密的明文。这种攻击比已知明文攻击更有力，因为攻击者可以选择一些特殊的明文进行加密，这些明文可以暴露出更多与密钥有关的信息。在这种条件下，密码分析的任务是推导出用于加密这些信息所用的密钥，或一个能将加密的新消息进行解密的算法，即：

已知：m1，c1=Ek(m1)，m2，c2=Ek(m2),…,mi，ci=Ek(mi)；其中，m1，m2，…，mi由攻击者选择；求：k或一个能由c推出m的算法D，使m=D(c)。

密码分析的手段4.选择密文攻击（ChosenCiphertextAttack)

攻击者可以选择不同的密文来解密，并能得到解密后的明文。例如，攻击者可以访问一台该密码系统的自动解密装置，产生任何密文对应的明文。攻击者的任务是推导出密钥，即：已知：c1，m1=Dk(c1)，c2，m2=Dk(c2)，

…，ci，mi=Dk(ci)；其中，c1，c2，…，ci由攻击者选择；求：k。密码分析的手段5.自适应选择明文攻击（AdaptiveChosenPlaintextAttack）这是选择明文攻击的特殊情况，密码分析者不仅能选择要加密的明文，而且还可以根据加密的结果对所选择的明文进行修正。即，攻击者选择明文m1并得到相应密文c1，然后根据c1选择明文m2并得到相应密文c2，…，根据cn-1选择mn并得到相应密文cn。这样交互得到的明文m1,m2,…,mn及其相应密文c1,c2,…,cn就是自适应选择明文，利用自适应选择明文对密码进行攻击就叫做自适应选择明文攻击。

密码分析的方法

1.穷举法（ExhaustiveAttackMethod）

穷举法又称作强力攻击(Brute-forceattack)，是对截获的密文依次用各种可能的密钥去解密，直到得到有意义的明文为止。穷举攻击所花费的时间等于尝试次数乘以一次解密所需的时间。设可能的密钥数为n，尝试一个密钥去解密需要的时间为t，则穷举法平均需要(n×t)/2的时间攻破一个密码系统。因此，只要有足够多的计算资源（计算时间和存储容量），理论上穷举法总是可以成功的。但实际上，如果破译的代价大于可能获得的利益，或破译的时间超过该信息的有用期限，那么这样的破译是毫无意义的。因此，可以通过增大密钥量或加大加密算法的复杂性来对抗穷举攻击。密码分析的方法

2.分析法（AnalyticalAttackMethod）分析法分为确定性分析法和统计性分析法两种。确定性分析法是通过数学求解的方法，用数学关系式表示出所求的未知量（如密钥）与已知量（如密文或明文/密文对）的关系。已知量和未知量的关系由加密和解密算法决定，因此为了对抗确定性分析法的攻击，应选用具有坚实数学基础和足够复杂度的加解密算法。密码分析的方法

2.分析法（AnalyticalAttackMethod）

统计分析法是利用明文的已知统计特性来进行破译的方法。密码分析者对截获的密文进行统计分析，总结出它的统计规律，并与明文的统计规律进行对照比较，从中得到明文和密文的对应关系或变换信息。因此，为了对抗统计分析法的攻击，应设法使明文的统计特性不带入密文，这样密文中就没有明文的痕迹，从而不可能使用统计攻击方法。

古典密码分析系统的安全性和Kerckhoff

假设

安全性有两种标准：一种称为理论安全性或无条件安全性，另一种称为实际安全性。若具有无限的计算资源（例如时间、空间、设备和资金等）也无法破译某密码系统，则称该系统是理论上安全的。

例如，一次一密密码是理论上安全的。因为已经证明，无论具有多少资源一次一密密码都是不可破译的。实际安全性又分为计算安全性和可证明安全性两种。如果破译一个系统在原理上是可能的，但使用所有已知的算法和现有的计算工具不可能在适当的时间内完成破译所要求的计算量，则称该系统是计算上安全的；如果可以证明破译某系统的难度与解某数学难题等价，则称该系统是可证明安全的。

Kerckhoff基本条件1883年Kerckhoff提出系统应满足的6条基本条件：(1)系统即使不是理论上不可破的，至少也应该是实际上不可破的；(2)系统的保密性不依赖于对加密体制或算法的保密，而仅仅依赖于密钥的保密；(3)密钥应便于记忆、易于修改；(4)密文可用电报传送；(5)加密装置小巧、可由单人操作；(6)掌握系统既不需要了解繁复的规则，也不要求超人的智慧。这些规则是一个多世纪前提出的，但其中大部分原则至今仍然有用。特别是第二条是当今密码系统安全性的前提，通常称为Kerckhoff假设。Kerckhoff假设的重要性如果密码系统的安全性依赖于加密算法的保密，那么就很难开发通用的加密硬件和软件模块，不利于加密算法的优化、标准化和推广；

如果密码系统的安全性依赖于攻击者不知道系统的密码体制，那么这种假设早晚会失败。因为密码分析者会不断地对你的系统进行攻击、反汇编你的代码、逆向设计你的算法等等，破译算法只是时间和金钱问题，密码发展史上这样的例子屡见不鲜；(3)如果系统的安全取决于算法的保密，那么一旦有机构退出所建立的保密系统（这种情况总是会发生的），整个系统就彻底崩溃了。这时必须更换整个系统的软件和硬件，重新建立新的安全保密体制，不但增加了不必要的开销，而且使人对系统安全性的基础缺乏信心。反之，如果系统的安全仅取决于密钥的保密，那么在这种情况下只需更换密钥，而不需要修改系统的任何硬件和软件；实践证明，最好的算法是那些已经公开、并经过世界上最好的密码分析家们多年攻击仍无法攻破的算法。因此，在进行密码分析时，总是假定Kerckhoff假设成立，即密码算法是公开的，所谓破译密码就是破译它的密文或求出它的密钥。单表替代密码的分析

在单表替代密码中，各种密钥字的使用都是可能的，因此，26种不同排列的字符变换表作为密表都是可能的。

26！～4×1026即使使用计算机用穷举法来破译单表替代密码也是不可能的。但事实上，有许多方法可以不必穷尽各种可能的密钥即可破译单表替代密码。猜测法在单表替代密码中，明文字母与密文字母一一对应，因此，变换后词的长度不会变化，词中的重复模式也不会发生改变。这样一来，短词、有重复模式的单词、以及常用的起始和结尾字母都会给出字符替代的线索。例如，英语中字母少的词是相当少的：二个字母组成的常用单词只有am,is,to,be,we,of等；三个字母组成的常用单词也只有and,you,she，any等。一种猜测方法就是在密文相应的地方用已知的少字母的词来替代，然后试图在密文其它地方进行相同的替代。另一种常用的猜测方法是查看密文中的重复模式，具有某些重复模式的词是很少的，一旦发现这种模式，将使得猜测的范围大为缩小。最后，常见的词的起始和结尾字母也给猜测提供很多线索。用猜测法破译下面的密文消息WKLVPHVVDJHLVQRWKDUGWREUHDN具有xyy模式的最普通的词是“see”和“too”，其它可能性较小的是“add”，“odd”，和“off”。若WRR是see，那么密文中的另一个词WR就是se。因为不存在se这个词，所以这种猜测不正确。但若WRR是too，那么WR就是to，这看来十分合理。于是用t替代W，o替代R。WRRWR用猜测法破译下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt--------------ottoo----to-----

“-ot”，它可能是“cot”，“dot”，“got”，“hot”,“lot”,“not”,“pot”,“rot”或“tot”。联系到它后面的一个单词是“too”，理想的选择应该是“not”，于是用n替代Q。这一替代并没有给出更多的线索，因为密文中Q只出现了一次。WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-------------nottoo----to-----

用猜测法破译下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-------------nottoo----to-----

短词“LV”，它也是“WKLV”这个词的末尾。可以用作单词，又可以是一般词的末尾的两个字母最可能的是“so”,”is”,”in”等。so不可能，因为“t-so”这种形式不象是什么词。由于前面假设Q是n，所以“in”也被排除。于是在所有的地方都用“is”替代“LV”，得到：WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-is-------isnottoo----to-----

用猜测法破译下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-is-------isnottoo----to-----

密文字母正好距离其明文字母三个位置！该密码系统可能是k=3的凯撒密码。推理得明文为：thismessageisnottoohardtobreak（“该消息不难破译”）这是一个有意义的英语句子，可以认为这就是该密文所代表的明文。因此，密码已被破译。这里描述的密码分析是特设的，用的是基于猜测的演绎法，而不是固定的原理和规则，但这种基于猜测的演绎法也可以用于其它密文的破译。如果预先建立一个常用短词、词头、词尾和特殊模式的表，并用计算机进行各种匹配，则可以大大提高破译的速度。单表古典密码的统计分析原理：明文的统计规律在密文中能够反映出来，故信息泄露大。多表古典密码的统计分析原理：密钥相同时，相同的明文对应相同的密文。统计分析法英文字母频度明文的统计规律26个英文字母：e

12%t---a---o---i---n---s---h---r

6%--9%d---l

4%c---u---m---w---f---g---y---p---b

1.5%--2.8%v—k---j---x---q---z

<1%明文的统计规律

双字母集的统计特性频率高的前30个双字母组，按其出现频率的高低顺序排列如下：

thheineranreedones

stenattonthand

oueangasortiisetitar

tesehiof明文的统计规律

三字母集的统计特性。

频率高的前20个三字母组，按其出现频率高低顺序排列如下：

theingandherereent

thanthwasethfordthhatsheioninthissth

ers

ver

明文的统计规律

高维字母集的统计特性。有超过50%的英语单词以e,s,d,t

为结尾字母；有约50%的单词以t,a,s,w

为起始字母。对于单表替代密码，由于明文字母和密文字母一一对应，因此，利用自然语言中的字母频率特征，将密文中和自然语言中频率相近的字符对应起来就有可能打开破译密码的缺口。字符出现的频率越不均匀，密文的保密性就越低。

汉字中单音节出现频率最常用，出现频率在百分之一以上的有14个音节，它们是：deshiyi

buyouzhileji

zhe

woyenli

ta

dao的是一不有之了机这我们里他到次常用音节有33个，它们是：zhong

zi

guo

shang

gemenheweiyedagongjian

jiu

xiang

zhu

lai

sheng

di

zai

ni

xiao

ke

yao

wu

yu

jie

jin

chan

zuo

jia

xian

quan

shuo

从三亿汉字的母体材料中，抽样二千五百万字进行双音节词词频统计，结果是：频率在一万次以上的双音节词有33个：我们三万次以上可以他们二万次以上进行没有工作人民生产这个发展就是问题国家中国这样革命自己不能由于这些所以因此作用一般什么如果情况必须方法因为主要要求社会汉字中双音节词出现频率代换密码分析举例频度分析W->e模式分析X->tB->h猜猜猜tS->?t_->?猜猜猜猜猜猜猜猜猜利用英语单字母频率表

破译密文：HQFUBSWLRQLVDPHDQVRIDWWDLQLQJVHFXUHFRPSXWDWLRQRYHULQVHFXUHFKDQQHOVEBXVLQJHQFUBSWLRQZHGLVJXLVHWKHPHVVDJHVRWKDWHYHGLIWKHWNDQVPLVVLRQLVGLYHUWHGHKHPHVVDJHZLOOQRWEHUHYHDOHG可以认定这种加密用的是k=3的凯撒密码。按此推测可得明文为：encryptionisameansofattainingsecurecomputationoverinsecurechannelsbyusingencryptionwedisguisethemessagesothatevenifthetransmissionisdivertedthemessagewillnotberevealed有意义的明文消息，因此，猜测是正确的。

多表古典密码的统计分析步骤1：首先确定密钥的长度：利用Kasiski测试法和重合指数法(indexofcoincidence)步骤2：确定具体的密钥内容：交互重合指数法卡西斯基法的基本思想是：若明文消息用n个密表循环加密，那么两个相同的字母组合在明文序列中间隔的字母数为n的倍数时，这两个明文字母组对应的密文字母组必然相同。反之，密文中两个相同的字母组对应的明文字母组不一定相同，只有2个字符的密文字母组的重复可能是偶然的，但字母组的字符数超过2个时，它们对应的明文相同可以说是肯定无疑的。

Kasiski测试法：Kasiski（卡西斯基法

）于1863年提出在英语中，词尾-th、-ing、-ion、-tion、-ation；词头im-、in-、un-、re-；模式-eek-、-oot-、-our-以及象of、and、to、with、are等词经常不成比例的频繁出现，所以在密文中重复的字母组是容易找到的。如果把密文中重复的字母组找出来，分析相同字母组之间的字符数，求出它们的公因子，就有可能提取多表替代密码所用的密表数（密钥长度）的信息。

Kasiski测试法寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为d1,d2,…,di，若令密钥字的长度为m，则m=gcd(d1,d2,…,di)。定理1若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明文段对应的密文一定相同。反之则不然。若密文中出现两个相同的密文段(密文段的长度m>2)，则它们对应的明文（及密钥）将以很大的概率相同。Kasiski测试法设下列密文是用Vigenere密码加密得到的，求加密的密表数：CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE

Kasiski测试法CHR出现在5次，MND出现在2个地方Kasiski测试法于是密表数最可能是5个卡西斯基法确定密钥长度的步骤总结如下：（1）找出三个或更多字符的重复模式；（2）记录每个具体模式每次出现的开始位置；（3）计算连续两次具体模式起点之间的差数；（4）确定每种差数的所有因子；（5）若用的是多表替代密码。那么密钥长度将可能是（4）中因子计算中出现最多的那个因子的值。思考：以多大的概率成立？

P(X1=X2|Y1=Y2)=1-P(X1!=X2;K1!=K2|Y1=Y2)由于密钥是等概独立的，每个密钥出现的概率为1/26，这相当于求满足X1+K1=X2+K2(mod26)的K1和K2出现的概率。若K1和K2中均有m个字母，且m>=3，则P(X1=X2|Y1=Y2)重合指数法(indexofcoincidence)：Wolfefriendman于1920年提出用多密表加密时，用的密表越多密文字母出现的频率越平均。因此，计算密文字母的分布与平均分布的方差，可以得到有关密表数的信息。重合指数法(indexofcoincidence)1.粗糙度（roughness）设proba是消息中字母a出现的概率，probb是b出现的概率，…，probz是z出现的概率。由于可能出现的字母只有a,b,…,z，故有：proba

+probb+…+probz

=1。

如果在消息集合S中，各个字母出现的概率相等，即消息中字母的分布是完全均匀的分布，那么有：proba+probb+…+probz=1/26≈0.0384。重合指数法(indexofcoincidence)1.粗糙度（roughness）定义

设消息集合S中，proba是消息中字母a出现的概率，probb是b出现的概率，…，probz是z出现的概率,令：变量Var

称为集合S的粗糙度。Var反映了消息集合中字母出现频率的分布与均匀分布的不一致性。正常英语字母的出现频率作为概率,则可求出正常英语的粗糙度Var=0.0296。由此可知，如果求得一个密文字母集的粗糙度接近0.0296，则该密文集可能是用一个密表加密而得到的。反之，如果求得的粗糙度明显比0.0296小，则该密文集可能是用多个密表加密而得到的。加密的密表数越多，密文集的粗糙度越小。因此，可以用粗糙度来判断一个密文集是否是用一个密表加密得到的。如果注意到粗糙度的后一项是一常数，那么计算也可以判断一个密文集是否是用一个密表加密得到的：若=0.0384+0.0296=0.068,则是用一个密表加密的；反之，则不是用一个密表加密的。

的物理意义是从密文中任意取出二个字符是相同字母的概率。通常密文的长度有限，无法求出各字母出现的概率，只能计算它们出现的频率，为此引入重合指数的概念。进一步判断密钥字的长度是否为

m=gcd(d1,d2,…,di).

定义1设X=x1x2…xn是一个长度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用表示。重合指数法(indexofcoincidence)定理1设英文字母A，B,…，Z在X中出现的次数分别为：f0,f1,…,f25则从X中任意选取两个字母相同的概率为证明在X中任意选取两个字母共有种选取的可能；在X中的每个相同的字母中选取两个元素共有种选取的可能。故易证。证毕。注意：（1）当密表数在1-3时，随着密表的增加IC值迅速下降，但是它的变化幅度在密表更多时逐渐变小。因此，从平均密文字母的分布来说，用三个密表就足够了。（2）当用的密表数很少时，重合指数能很好地预测密表的多少,但对大量的密表就不能直接利用多密表时的IC值来判别密表数，但可以利用重合指数法来判别所作的猜测是否能够成立。已知每个英文字母出现的期望概率，分别记为p0,p1,…,p25，那么X中两个元素相同的概率为：

=0.065

对于英文的一个随机字母串，每个英文字母出现的期望概率均为1/26，则在X中任意选取两个元素相同的概率为=0.038.根据Kasiski测试法得到的m，可以将密文Y按照下列形式排列：表1将Y排列成m行n/m列的形式，设m=0(modn)若m确实是密钥的长度，则上述矩阵中的每一行都是由同一个密钥ki加密得到，这说明每一行即是一个单表代替，这时计算每一行的重合指数，应该更接近0.065；若m不是密钥的长度，则上述矩阵中的每一行不是由同一个密钥ki加密得到，这说明每一行是一个等概随机的字母串（对密文的要求），这时计算每一行的重合指数，应该更接近0.038。验证刚才的例子于是密表数最可能是5个例用重合指数法来进一步核实该例

中的密文是用5个密表加密而成的。重复模式卡西斯基法已经推测该密文是由5个密表加密而成的,为了证实这一猜测,可将上述密文按下列方式分成5组判断每个组是否都是用一个密表加密的。如果每一组都是用一个密表加密而成的，那么每一组的重合指数都应该接近0.068。分别计算它们的IC得：IC(S1)=0.063,IC(S2)=0.068,IC(S3)=0.069,IC(S4)=0.061和IC(S5)=0.072。这些值都与0.068很接近，因此，间接地证明了该维吉尼亚密码的密钥长度为5。单字符多表替代密码的分析步骤从以上例子可以归纳多表替代密码的分析过程如下：（1）用卡西斯基法预测加密密表的可能数目，如果没有出现比较有规律的数，那么该密码可能不是简单的多表替代密码；（2）计算整个密文的重合指数确认第一步的预测；（3）通过（1）和（2）得到了有希望的密表数，因而可以把密文分成适当的子集，分别计算每个子集的重合指数，以确定每个子集确实是单表密码；（4）用猜测法或统计法分析每个子集，求出明文。若明文有意义，则该多表替代密码的密文已被破译。用交互重合指数确定密钥的具体内容定义设X=x1x2…xn和Y=y1y2…yn，是两个长度分别为n和n’的字母串。X和Y的交互重合指数(mutualindexofcoincidence)定义为X中的一个随机元素与Y中的一个随机元素相同的概率，记为

fi和f‘i为字母出现频率计算表1中的任意两行之间的交互重合指数中的一个随机元素与中的一个随机元素同为字母h(0<=h<26)的概率为

则称为和之间的相对位移(relativeshift)，用表示。由于计算具体密钥内容当相对位移不为0时，重合指数的取值范围[0.031,0.045]当相对位移为0时，重合指数取值为0.065。可以统计每两行中英文字母出现的概率f0,f1,…,f25

和f’0,f’1,…,f’25记为以g作密钥进行加法加密得到的密文，并穷举计算得到若

，则应该接近0.065；若不然，应该接近[0.031,0.045]中的某个值。K1+i,i=0,……,25K1-k2=5计算具体密钥内容的复杂度分析

这样可以得到任意两行之间的相对位移。给定某一行，猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。刚才的例子继续的值共有260个，计算结果列于下表，找出的值接近0.068的（i,j）对，如果对于给定的（i，j）只有一个值接近0.068，则g就是i和j对应的相对位移，即：ki−kj=g在表中共有6个满足该条件的值，这些值说明y1和y2的相对位移是9；y1和y5的相对位移是16；y2和y3的相对位移是13；y2和y5的相对位移是7；y3和y5的相对位移是20以及y4和y5的相对位移是11。这样就得到了未知数k1,k2,k3,k4,和k的6个方程：密钥形式为：经过对密钥的穷尽搜索（最多26次,），确定密钥为：JANET用密钥JANET解密Thealmondtreewasintentativeblossom.Thedayswerelonger,oftenendingwithmagnificenteveningsofcorrugat