《古典密码学》ppt课件

1、第2章 古典密码学2.1古典密码学体制2.1.1定义和分类一个密码系统Cryptosystem是一个五元组P,C,K,E,D)满足条件：1P是能够明文的有限集；明文空间2C是能够密文的有限集；密文空间3K是一切能够密钥构成的有限集；密钥空间4恣意 ,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密、解密函数，满足 。 Kk EekDdkCPek:PCdk:Pxxxedkk,)(这里xxAlice加密解密密钥源平安信道窃听者OscarkyBob适用密码体系每个加密函数和每个解密函数该当能有效地被计算。 即使看到密文串y，窃听者Oscar确定所用的密钥k或明文串x是不可行的。知密文串y的情

2、况下试图计算密钥k的过程称为密码分析Cryptanalysis。 古典密码学分类 代换Substitution密码和置换Permutation密码 2.1.2 代换密码 将明文字母表笼统地表示为一个整数集 。在加密时通常将明文音讯划分生长为L的音讯单元，称为明文组，以m表示，如 。 m也称作L报文，它可以看作是定义在 上的随机变量 这时明文空间 。密文字母表笼统表示成整数集 。密文单元或组为 。c是定义在 上的随机变量。密文空间 。普通地，明文和密文由同一字母表构成。代换密码可以看作是从 到 的映射。L1时，称作单字母代换，也称作流密码Stream cipher。L1时，称作多字母代换，亦称分

3、组密码Block cipher。 1, 1 , 0qZq10 ,),(110LlZqmmmmmlLLqZ10 ,),(110LlZmmmmmLZZZZqlLqqqLq个LqZP 1, 1 , 0qZq10 ,)(,(110LlZcLccccqlL个）LqZLqZC LqZLqZ1. 单表代换密码单表代换密码 单表代换密码是对明文的一切字母都用单表代换密码是对明文的一切字母都用一个固定的明文字母表到密文字母表的一个固定的明文字母表到密文字母表的映射，即映射，即 。令明。令明文文 ,那么相应地密文那么相应地密文为为 。 qqZZf:10mmm )()()(1010mfmfccmec 几类简单的单表

4、代换密码 移位密码Shift Cipher 设 定义 且 ,250,26kZKCP对26mod)(kxxek26,26mod)(Zyxkyydk例例21 恺撒恺撒Caesar密码是密码是k3的情况。即经过简单的向右的情况。即经过简单的向右挪动源字母表挪动源字母表3个字母那么构成如下代换字母表个字母那么构成如下代换字母表 假设明文为：假设明文为： please confirm receipt那么密文为：那么密文为：SOHDVE FRQILUP UHFHLSW :abcdefghijklm:DEFGHIJKLMNOPno p q rs tu v w x y zQR S T U V W X Y Z

5、A B C 平安性分析 移位密码是极不平安的mod26，由于它可被穷举密钥搜索所分析：仅有26个能够的密钥，尝试每一个能够的加密规那么，直到一个有意义的明文串被获得。平均地说，一个明文在尝试26/213解密规那么后将显现出来。 交换密码 设 ，密钥空间K由一切能够的26个符号0，1，.，25的置换组成。对每一个置换 ，定义 那么 ， 其中 的逆置换。 26ZCP)()(xxe)()(1yyd是1 例例2.2 密钥句子为：密钥句子为：the message was transmitted an hour ago 。 源字母表为：源字母表为： a b c d e f g h i j k l m n

6、 o p q r s t u v w x y z 代换字母表为：代换字母表为：THEMSAGWRNIDOUBCFJKLPQVXYZ 明文：明文：please confirm receipt 密文：密文：CDSTKS EBUARJO JSESRCL 平安性分析 交换密码的密钥是由26个字母的置换组成。这些置换的数目是26！，超越，一个非常大的数。这样即使对现代计算机来说，穷举密钥搜索也是不可行的。然而，以后我们会看到，交换密码容易被其他的分析方法所破译。 仿射密码 设 ，且 对 ，定义 且 26ZCP1)26,gcd(:),(2626aZZbaKKbak),(26mod)(baxxe26mod)

7、()(1byaydk),(26Zyx例例2.3 假定假定 ， ，加密函数，加密函数为为 ，那么相应的解密函数，那么相应的解密函数为为 ，其中一切的运算都是在，其中一切的运算都是在 中。容易验中。容易验证证 。 加密明文加密明文hot。 首先转化这三个字母分别为数字首先转化这三个字母分别为数字7，14和和19。然后加密。然后加密密文串为密文串为AGX。 )3 , 7(k1526mod7137)(xxek1915)3(15)(yyydk26Zxxxxdxedkkk194519)37(15)37()();26(mod6230333191477GXA 多表代换密码 多表代换密码是以一系列两个以上代换表

8、依次对明文音讯的字母进展代换的加密方法。 令明文字母表为 ， 为代换序列，明文字母序列 ，那么相应的密文字母序列为 。qZ),(21fff 21xxx )()()()(2211xfxfxfxeck 假设f是非周期的无限序列，那么相应的密码称为非周期多表代换密码。这类密码，对每个明文字母都采用不同的代换表或密钥进展加密，称作一次一密密码One-time pad cipher,这是一种实际上独一不可破的密码 。 有名的多表代换密码有Vigenre、Beaufort、Running-Key、Vernam和转轮机Rotor machine等密码。 Vigenre密码 设m是某固定的正整数，定义 ，对一

9、个密钥 ，我们定义 且 一切的运算都在 中。 mZKCP)(26),(21mkkkk),(),(221121mmmkkxkxkxxxxe),(),(221121mmmkkykykyyyyd26Z例例 2.4 设设m6，且密钥字是，且密钥字是CIPHER,这相应于密钥。假定明这相应于密钥。假定明文串是文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按首先将明文串转化为数字串，按6个一组分段，然后模个一组分段，然后模26“加上密钥字得：加上密钥字得：相应的密文串将是相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加

10、密过程类似解密过程与加密过程类似,不同的只是进展模不同的只是进展模26减减,而不是模而不是模26加。加。 86252315211747158217218871915222182301747158224181419152491219191211747158218812419181982582215174715822418191413192522158241720 多字母代换密码Polygram substitution cipherHill 密码 设m是某个固定的正整数， ，又设 ；对恣意 ，定义 ， 那么 。 其中一切的运算都是在 中进展。 mZCP)(2626ZmmK可逆阵，Kk xkxek

11、)(1)( ykydk26Z 例例 2.5 假定密钥是，那么。如今我们加密明文假定密钥是，那么。如今我们加密明文july 分为两个明文组分为两个明文组9，20相应于相应于ju和和11，24相应于相应于ly。计算如下：。计算如下： 因此，因此，july的加密是的加密是DELW。 )4 , 3()14072,6099(73811)20, 9( 2.1.3置换密码Permutation Cipher 设m是某个固定的整数。 ，且由一切 的置换组成。对一个密钥 即一个置换，定义 ， 其中， 。 mZCP)(26m, 2 , 1),(),()()2()1(21mmxxxxxxe),(),()()2()1

12、(21111mmyyyyyyd的逆置换是1例例 2.6 假定假定m6，密钥是以下置，密钥是以下置换换 ： ； 那么逆置换那么逆置换 为：为： 。 给出明文给出明文 shesellsseashellsbytheseashore. 首先把明文分为首先把明文分为6个字母一组：个字母一组： shesel lsseas hellsb ythese ashore . 每六个字母按重排，得密文：每六个字母按重排，得密文： EESLSHSALSESLSHBLEHSYEETHRAEOS 用用 类似地解密。类似地解密。 24615365432114251636543211 平安性分析 Hill密码解密等价于用逆置

13、换 的置换密码解密。 122 古典密码体制分析 Kerckhoff假设：攻击方知道所用的密码系统。 简单的单表代换密码，如移位密码，仅统计标出最高频度字母再与明文字母表字母对应决议出移位量，就差不多得到正确解了。也很容易用穷举密钥搜索来破译。 普通的仿射密码，多思索几个密文字母统计表与明文字母统计表的匹配关系也不难解出。 结论：一个密码系统是平安的一个必要条件是密钥空间必需足够大，使得穷举密钥搜索破译是不可行的。 唯密文攻击法分析单表和多表代换密码是可行的。 但用唯密文攻击法分析多字母代换密码如Hill密码是比较困难的。分析多字母代换多用知明文攻击法。 2.2.1 单表代换密码分析 例例 2.

14、7 假设从仿射密码获得的密文为：假设从仿射密码获得的密文为：FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 仅有仅有57个密文字母，但足够分析仿射密码。个密文字母，但足够分析仿射密码。最高频的密文字母是：最高频的密文字母是：R(8次次)，D6次，次，E，H，K各五次，各五次，F，S，V各四次。各四次。开场，我们可以假定开场，我们可以假定R是是e的加密的加密且且D是是t的加密，由于的加密，由于e和和t分别是分别是两个最常见的字母。数值化后，两个最常见的字母。数值化后，我们有我们有 。回想加密函数回想加密函数 。所以得到两个含两个

15、未知量的所以得到两个含两个未知量的线性方程组：线性方程组： 表表2.3 26个英文字母的概率分布个英文字母的概率分布字母概率字母概率A0.082N0.067B0.015O0.075C0.028P0.019D0.043Q0.001E0.127R0.060F0.022S0.063G0.020T0.091H0.061U0.028I0.070V0.010J0.002W0.023K0.008X0.001L0.040Y0.020M0.024Z0.0013)19(17)4(kkee且baxxek)(319174baba 这个系统有独一的解 。但这是一个非法的密钥，由于 。所以我们假设有误。 我们下一个猜测能

16、够是R是e的加密，E是t的加密。得 ，又是不能够的。继续假定R是e的加密且K是t的加密。这产生了 ，至少是一个合法的密钥。剩下的事是计算相应于k3，5的解密函数，然后解密密文看能否得到了有意义的英文串。容易证明这是一个有效的密钥。 最后的密文是： algorithms are quite general definitions of arithmetic processes )(19, 626Zba12)26,gcd(a8a5, 3ba2.2.2 多表代换密码分析 分析Vigenre密码的方法: Kasiski测试法 假设用给定的m个密钥表周期地对明文字母加密，那么当明文中有两个一样字母组在明

17、文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必一样。但反过来，假设密文中出现两个一样的字母组，它们所对应的明文字母组未必一样，但一样的能够性很大。假设我们将密文中一样的字母组找出来，并对其一样字母数综合研讨，找出它们的一样字母数的最大公因子，就有能够提取出有关密钥字的长度m的信息。 例子： 明文：REQUESTS ADDITIONAL TEST 密钥：TELEXTEL EXTELEXTEL EXTE密钥：CAVKTBLT EUQWSWJGEA LTBL一个给定密文包含以下反复的序列，且有间隔：由于3是出现最频繁的因子，所以密文的周期最有能够是3。 字母序列距离PQA150

18、=252 3RET42=723FRT10=25ROPY81=34DER57=193RUN117=1332 重合指数法Coincidence Index 设一门言语由n个字母构成，每个字母发生的概率为 ，那么重合指数是指其中两个随机元素一样的概率，记为 。 判别文本是用单表还是用多表代换加密。 提供对两个不同密文的洞察力 。 nipi1niipCI12niiiLLxxCI1) 1(/ ) 1( Chi 测试测试 比较两个频率分布比较两个频率分布 ，决议能否同样或不同，决议能否同样或不同的代换被采用的代换被采用 简化多表代换为单表代换简化多表代换为单表代换 niiiqp1例：明文：EXECUTE

19、THESE COMMANDS密钥：RADIORA DIORA DIORADIO密文：VXHKIKE WPSJE FWADAQLG VOVTLKVKYVJVTFDDREUJRADIO09121723RADIOVXHKIKEWPSJEFWADAQLG 例2.8 在相距很短的时间间隔内我们收到了两段密文： 密文1：k o o m m a c o m o q e g l x x m q c c k u e y f c u ry l y l i g z s x c z v b c k m y o p n p o g d g i a zt x d d i a k n v o m x h i e m r d

20、 e z v x b m z r n lz a y q i q x g k k k p n e v h o v v b k k t c s s e pk g d h x y v j m r d k b c j u e f m a k n t d r x b ie m r d p r r j b x f q n e m x d r l b c j h p z t v vi x y e t n i i a w d r g n o m r z r r e i k i o x r us x c r e t v密文 2：z a o z y g y u k n d w p i o u o r i y r h h b z x r