古典密码课件.ppt

1、第二章第二章 古典密码古典密码解放军信息工程大学电子技术学院二系解放军信息工程大学电子技术学院二系20052005年年3 3月月2 2日日应用密码学课程幻灯片（电院24队）第1页，共31页。lE-mail:lQQ:32874546lTel:38532(O)lAdr:1701第2页，共31页。上节课内容复习上节课内容复习第3页，共31页。保密内容保密内容l受限制的（受限制的（restricted)算法算法 算法的保密性基于保持算法的秘密算法的保密性基于保持算法的秘密l 基于密钥（基于密钥（key-based)的算法的算法 算法的保密性基于对密钥的保密算法的保密性基于对密钥的保密第4页，共31页。

2、密钥密钥l对称密码算法（对称密码算法（symmetric cipher)加密密钥和解密密钥相同，或实质上等同，即从一个易于加密密钥和解密密钥相同，或实质上等同，即从一个易于推 出 另 一 个，又 称 秘 密 密 钥 算 法 或 单 密 钥 算 法推 出 另 一 个，又 称 秘 密 密 钥 算 法 或 单 密 钥 算 法l 非对称密钥算法（非对称密钥算法（asymmetric cipher)加密密钥和解密密钥不相同，从一个很难推出另一个加密密钥和解密密钥不相同，从一个很难推出另一个 又称公开密钥算法（又称公开密钥算法（public-key cipher)。公开密钥算法用一个密钥进行加密公开密钥算

3、法用一个密钥进行加密,而用另一个进行解而用另一个进行解密其中的加密密钥可以公开密其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥。解密密钥必须保密，简称公钥。解密密钥必须保密,又称私人密钥又称私人密钥（private key)私钥，简称私钥私钥，简称私钥第5页，共31页。明文处理方式明文处理方式l分组密码（分组密码（block cipher)将明文分成固定长度的组，用同一密钥将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密和算法对每一块加密，输出也是固定长度的密文。文。l 流密码（流密码（stream cipher)又称序列密码。序

4、列密码每次加密一位又称序列密码。序列密码每次加密一位或一字节的明文。或一字节的明文。第6页，共31页。第二章第二章 古典密码古典密码n1.学习基本的密码编制原理;n2.了解早期编制密码的基本方法;n3.为进一步学习现代密码的编制打下基础。第7页，共31页。第8页，共31页。我们将重点介绍我们将重点介绍代替密码代替密码 第9页，共31页。一、单表代替密码：一、单表代替密码：利用预先设计的利用预先设计的固定固定代替规则代替规则,对明文对明文逐逐字符字符或或逐逐字符组字符组进行代替的密码进行代替的密码.字符组称为一个代替单位字符组称为一个代替单位.这里这里代替规则代替规则又称为又称为代替函数代替函数

5、、代替表代替表或或S S盒。盒。它的它的固定性固定性是指这个代替规则与是指这个代替规则与密钥因素密钥因素和和被加密的明文字符的被加密的明文字符的序号序号无关。无关。即即相同的相同的明文字符组产生明文字符组产生相同的相同的密文字符密文字符组组.第10页，共31页。例例1:1:汉字和符号的区位码汉字和符号的区位码(单表代替单表代替)第11页，共31页。例例2 2 以十进值数为代替单位的代替函数则明文则明文晨五点总攻晨五点总攻 先变换为区位码先变换为区位码 1931 4669 2167 5560 1505 再被加密成密文 4624 1996 8497 0095 4050单表代替的缺点:明文字符相同,

6、则密文字符也相同9,2,1,09,2,1,0:S105,4,8,2,1,0,9,7,3,6S假设明文 0 1 2 3 4 5 6 7 8 9密文 5 4 8 2 1 0 9 7 3 6即代替表为即代替表为:第12页，共31页。qkmmEckmod)()(加密变换加密变换:1,2,1,0qZq 例例3 3 加法密码加法密码 选定选定常数常数 q 和和 k.明文空间明文空间=密文空间密文空间=qkccDmkmod)()(脱密变换脱密变换：其中其中 读作读作 n 模模q,它是它是n n被被q q除后所得的余数除后所得的余数.如如18 mod7=4 18 mod7=4 上述加法称为上述加法称为模模q加

7、加.qn mod第13页，共31页。90,10mod)3()(3mmmEc加密变换为加密变换为：特别地特别地,若取若取q=10 和和 k=3,则则脱密变换为脱密变换为：90,10mod)3()(3cccDm 此时此时,明文明文:晨五点总攻晨五点总攻 变换为区位码变换为区位码1931 4669 2167 5560 1505后就被加密成密文4264 7992 5490 8893 4838 缺点:密文差=明文差10mod)(10mod)3()3(10mod)3(10mod)3(21212121mmmmmmcc第14页，共31页。(凯撒密码)这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3

8、。英文字母被编码为该字母的序号 英文 A B C D X Y Z 数字 0 1 2 3 23 24 25250,26mod)3()(3mmmEc加密变换为加密变换为：脱密变换为脱密变换为：250,26mod)3()(3cccDm第15页，共31页。这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。如如:若选择cipher作为密钥字,则对应代替表为:明文明文 A B C D E F G H I J K L M N O P A B C D E F G H I J K L M N O P 密文密文 C I P H E RC I P H E R A B D F G J K L M

9、 N A B D F G J K L M N 第16页，共31页。10mod)()(kmmEck例例4 4：加密变换为加密变换为:二、多表代替密码二、多表代替密码 根据密钥的指示，来选择加密时使用的单表的根据密钥的指示，来选择加密时使用的单表的方法，称为方法，称为多表代替多表代替密码。密码。但但 k 不再是固定常数而是密钥。不再是固定常数而是密钥。加密算法：加密算法：明明 文：文：晨晨 五五 点点 总总 攻攻明文序列：明文序列：1931 4669 2167 5560 1505密钥序列：密钥序列：4321 5378 4322 3109 11074321 5378 4322 3109 1107密文

10、序列：密文序列：5252 9937 6489 8669 26025252 9937 6489 8669 2602若密钥序列是随机的若密钥序列是随机的,该密码就是该密码就是绝对安全绝对安全的的.随机随机就是指序列的信号相互就是指序列的信号相互独立独立且且等概等概分布分布.第17页，共31页。26mod)()(kmmEck将对英文字母的加密变换改为：将对英文字母的加密变换改为：当将明、密文空间均改为当将明、密文空间均改为25,2,1,026Z这个密码就是一个著名的古典密码体制：这个密码就是一个著名的古典密码体制：维几尼亚密码维几尼亚密码（VigenereVigenere密码体制）密码体制）,21t

11、mmm若若明文序列明文序列为为:,21tkkk密钥序列密钥序列为：为：,21tccc则则密文序列密文序列为为:其中：其中：26mod)()(iiikikmmEci这也是序列密码的一般加密形式这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)第18页，共31页。维维几几利利亚亚密密码码的的代代替替表表为为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e第19页，共31页。26mod)()(mkmEck将对英文字母的加密变换改为：将对英文字母的加密变换改为：当将明、密文空间均设为当将明、密文空间均设为25,2,1,026Z,21tmmm若若明文序列明文序列为为:,21tk

12、kk密钥序列密钥序列为：为：,21tccc则则密文序列密文序列为为:其中：其中：26mod)()(iiikimkmEci该密码称为该密码称为维福特密码维福特密码（BeaufortBeaufort密码体制）密码体制）此时脱密变换与加密变换完全相同，也是：此时脱密变换与加密变换完全相同，也是：26mod)()(ckcEmk第20页，共31页。如果将明、密文空间均改为如果将明、密文空间均改为1,02Z将加密变换改为：将加密变换改为：kmkmmEck定义2mod)()(,21tmmm若若明文序列明文序列为为：,21tkkk密钥序列密钥序列为：为：,21tccc则则密文序列密文序列为：为：其中：其中：i

13、iikikmmEci)(这是众所周知的完全保密的密码体制这是众所周知的完全保密的密码体制这个密码就是著名的这个密码就是著名的VernamVernam密码体制密码体制第21页，共31页。代替密码的安全性分析代替密码的安全性分析 1.单表代替的优缺点单表代替的优缺点 优点优点:明文字符的形态一般将面目全非明文字符的形态一般将面目全非 缺点缺点:(A)明文的位置不变明文的位置不变;(B)明文字符明文字符相同相同,则则密文字符密文字符也相同也相同;从而导致从而导致:(I)若明文字符若明文字符e被加密成密文字符被加密成密文字符a,则明文中则明文中e的出现次数就是密文中字符的出现次数就是密文中字符a的出现

14、次数的出现次数;(II)明文的跟随关系反映在密文之中明文的跟随关系反映在密文之中.因此因此,明文字符的统计规律就完全暴露在密文明文字符的统计规律就完全暴露在密文字符的统计规律之中字符的统计规律之中.形态变但位置不变形态变但位置不变第22页，共31页。e：出现的频率约为0.127t，a，o，i，n，s，h，r：出现的频率约在0.06到0.09之间d，l：的出现频率约为0.04c，u，m，w，f，g，y，p，b：的出现频率约在0.015到0.028之间v，k，j，x，q，z：出现的频率小于0.01第23页，共31页。l例：例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUD

15、BMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ第24页，共31页。代替密码的安全性分析代替密码的安全性分析 2.多表代替的优缺点多表代替的优缺点 优点优点:只要只要 (1)多表设计合理多表设计合理,即每行中元互不相同即每行中元互不相同,每列中元每列中元互不相同互不相同.(这样的表称为拉丁方表这样的表称为拉丁方表)(2)密钥序列是随机序列密钥序列是随机序列，即具有等概性和独立，即具有等概性和独立性。性。这个多表代替就是完全保密的。这个多表代替就是完全保密的。等概性等概性:各位

16、置的字符取可能字符的概率相同；各位置的字符取可能字符的概率相同；独立性：独立性：在其它所有字符都知道时，也判断不出在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。未知的字符取哪个的概率更大。第25页，共31页。代替密码的安全性分析代替密码的安全性分析 2.多表代替的优缺点多表代替的优缺点 密钥序列是随机序列意味着：密钥序列是随机序列意味着：（1）密钥序列不能周期重复；）密钥序列不能周期重复；（2）密钥序列必须与明文序列等长；）密钥序列必须与明文序列等长；（3）这些序列必须在通信前分配完毕；）这些序列必须在通信前分配完毕；（4）大量通信时不实用；）大量通信时不实用；（5）分配密钥和

17、存储密钥时安全隐患大。）分配密钥和存储密钥时安全隐患大。缺点：缺点：周期较短时可以实现唯密文攻击。周期较短时可以实现唯密文攻击。解决方案：解决方案：密钥序列有少量真随机的数按固定密钥序列有少量真随机的数按固定的算法生成，只要它很像随机序列即可。这种序列的算法生成，只要它很像随机序列即可。这种序列称为伪随机序列。称为伪随机序列。第26页，共31页。移移 位位 密密 码码 对明文字符或字符组的进行对明文字符或字符组的进行位置移动位置移动的密码的密码 例例：设：设明文明文为：为：解放军电子技术学院解放军电子技术学院移位方式：移位方式：S9=2,5,7,3,4,8,9,1,6即即:第第 i 个密文汉字

18、就是第个密文汉字就是第S i个明文汉字个明文汉字.则则密文密文为为放子术军电学院解技放子术军电学院解技移位也是现代密码中必用的一种编码技术移位也是现代密码中必用的一种编码技术 第27页，共31页。移位密码的安全性分析移位密码的安全性分析 1.移位密码的优缺点移位密码的优缺点 优点优点:明文字符的位置发生变化明文字符的位置发生变化;缺点缺点:(A)明文字符的形态不变明文字符的形态不变;从而导致从而导致:(I)密文字符密文字符e的出现频次的出现频次也是明文字符也是明文字符e的出现的出现次数次数;有时直接可破有时直接可破!(如密文字母全相同如密文字母全相同)目前也有现成的破译方法目前也有现成的破译方法.移位密码优缺点总结移位密码优缺点总结:位置变位置变但但形态不变形态不变.代替密码优缺点总结代替密码优缺点总结:形态变形态变但但位置不变位置不变.第28页，共31页。结论结论:将代替密码和移位密码轮番使用,必然可以发挥各自的长处,克服对方的缺点!必然可以设计出安全的密码体制!这就是现代密码的设计思想!第29页，共31页。下节课的内容下节课的内容第30页，共31页。作业:P21 第2.1题.第31页，共31页。