第2讲-古典密码

1第二章古典密码郑洪英重庆大学计算机学院信息技术系《现代密码学》课程幻灯片E-mail:zhenghongy@2上节课内容复习明文、密文、密钥（概念）加密、解密（概念及函数的表示方法）密码体制加、解密密钥，加、解密函数破译攻击方法（穷举攻击中根据密钥量来推算攻击时间）3上节课补充内容－密码算法的分类保密内容受限制的（restricted)算法算法的保密性基于保持算法的秘密

基于密钥（key-based)的算法算法的保密性基于对密钥的保密4上节课补充内容－密码算法的分类密钥对称密码算法（symmetriccipher)

加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个，又称秘密密钥算法或单密钥算法

非对称密钥算法（asymmetriccipher)

加密密钥和解密密钥不相同，从一个很难推出另一个又称公开密钥算法（public-keycipher)。公开密钥算法用一个密钥进行加密,而用另一个进行解密。其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥。解密密钥必须保密,又称私人密钥（privatekey)，简称私钥5上节课补充内容－密码算法的分类明文处理方式分组密码（blockcipher)

将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。

流密码（streamcipher)

又称序列密码。序列密码每次加密一位或一字节的明文。6第二章古典密码学习本章目的：1.学习基本的密码编制原理;2.了解早期编制密码的基本方法;3.为进一步学习现代密码的编制打下基础。72.1古典密码中的基本加密运算单表密码体制：对于一个密码体制，如果明文字母对应的密文字母在密文中保持不变，则称其为单表密码体制；多表密码体制：如果明文中不同位置的同一明文字母在密文中对应的密文字母不同，则称其为多表密码体制。8加密运算1．简单加法密码

c=Ek(m)=(m+k)modq其中的加法都是模q加法．显然，简单加法密码的密钥量为q.2.乘法密码

c=Ek(m)=(mk)modq其中的乘法都是模q乘法.9加密运算3.简单仿射密码

c=Ek(m)=(k1+k2m)modq其中的加法和乘法都是模q加法和乘法.4.简单置换密码明文的字母保持相同，但顺序被打乱了。102.211

1.Caesar密码(凯撒密码)

这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。

英文字母被编码为该字母的序号

英文ABCD…XYZ

数字

0123…232425加密变换为：解密变换为：12例恺撒（Caesar）密码是k＝3的情况。即通过简单的向右移动源字母表3个字母则形成如下代换字母表若明文为：pleaseconfirmreceipt则密文为：SOHDVEFRQILUPUHFHLSW明文字母abcdefghijklm密文字母:DEFGHIJKLMNOPnopqrstuvwxyzQRSTUVWXYZABC13安全性分析移位密码是极不安全的（mod26），因为它可被穷举密钥搜索所分析：仅有26个可能的密钥，尝试每一个可能的加密密钥，直到一个有意义的明文串被获得。平均地说，一个明文在尝试26/2＝13解密规则后将显现出来。142.标准字头密码(又称密钥字密码)

这是一种置换密码,它利用一个密钥字来构造置换表。

如:

若选择cipher作为密钥字,则对应置换表为:明文ABCDEFGHIJKLMNOP…密文

CIPHERABDFGJKLMN…15例2.2密钥句子为：themessagewastransmittedanhourago。源字母表为：abcdefghijklmnopqrstuvwxyz

代换字母表为：THEMSAGWRNIDOUBCFJKLPQVXYZ明文：pleaseconfirmreceipt密文：CDSTKSEBUARJOJSESRCL16安全性分析置换密码的密钥是由26个字母的置换组成。这些置换的数目是26！，一个非常大的数。这样即使对现代计算机来说，穷举密钥搜索也是不可行的。然而，以后我们会看到，置换密码容易被其他的分析方法所破译。172.2.2几种典型的多表古典密码体制1.playfair密码英国陆军在第一次世界大战，美国陆军在第二次世界大战期间大量使用的一种二字母组代替密码。密钥由26个英文字母组成五阶方阵。加密时，首先在明文字母串的适当位置插入一些特定的字母，譬如字母q，使得明文字母串的长度为偶数，将明文串按两个字母一组进行分组。m1,m2同行：c1,c2在它们右边；

m1,m2同列：c1,c2在它们下边；

m1,m2不同行列：c1,c2是m1,m2

组成的长方形的另两个顶点；

明文由奇数个字母组成，则在明文后加一无效字母18cipherabdfgklmnoqstuvwxyz设密钥矩阵：P=明文为:playfaircipherwasactuallyinventedbywheatstone密文为Bsdwrbcaiphecfikqbhoqfksmxekzcmuhfdxyiifutuquf19若明文序列为:密钥序列为：则密文序列为:其中：这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)维几尼亚密码（Vigenere密码体制）当密钥的长度比明文短时，密钥可以周期性地重复使用，直至完成明文中每个字母的加密。20维几利亚密码的代替表为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e21例设m＝6，且密钥字是CIPHER,这相应于密钥。假定明文串是thiscryptosystemisnotsecure

首先将明文串转化为数字串，按6个一组分段，然后模26“加”上密钥字得：相应的密文串将是: VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。

22将对英文字母的加密变换改为：

当将明、密文空间均设为若明文序列为:密钥序列为：则密文序列为:其中：该密码称为维福特密码（Beaufort密码体制）此时解密变换与加密变换完全相同，也是：26mod)()(mk+25mEck-==23

如果将明、密文空间均改为将加密变换改为：若明文序列为：密钥序列为：则密文序列为：其中：这是众所周知的完全保密的密码体制这个密码就是著名的Vernam密码体制24Hill密码基本思想：将n个明文字母通过线性变换将它们转换为n个密文字母，解密时只需做一次逆变换，密钥就是变换矩阵25例假定密钥是现在我们加密明文july分为两个明文组（9，20）（相应于ju）和（11，24）（相应于ly）。计算如下：因此，july的加密是DELW。

26Hill密码271.单表代替的优缺点

优点:

明文字符的形态一般将面目全非

缺点:

明文字符相同,则密文字符也相同;

从而导致:(I)若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数;(II)明文的跟随关系反映在密文之中.

因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变282.多表代替的优缺点

优点:

只要

(1)多表设计合理,即每行中元素互不相同,每列中元素互不相同.(这样的表称为拉丁方表)(2)密钥序列是随机序列，即具有等概性和独立性。这个多表代替就是完全保密的。

等概性:各位置的字符取可能字符的概率相同；

独立性：在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。292.多表代替的优缺点密钥序列是随机序列意味着：（1）密钥