第3章 古典密码学

第2章 古典密码技术

古典密码技术 古典密码体制 定义和分类 代换密码 置换密码 单表替代密码分析 对Hill密码的已知明文分析1

古典密码的统计分析

隐写术

我画蓝江水悠悠， 爱晚亭上枫叶愁。 秋月溶溶照佛寺， 香烟袅袅绕经楼.

第2章 古典密码技术

2.1.1 定义和分类

密码体制的要素

明文：发送方将要发送的消息 密文：明文被变换成看似无意义的随机消息 加密：明文变换成密文的过程称为加密 解密：密文恢复出原明文的过程称为解密 加密算法：对明文进行加密时所采用的一组 规则 解密算法：对密文进行解密时所采用的一组 规则 加密和解密算法的操作通常都是在一组密钥 控制下进行的，分别称为加密密钥和解密密 钥4

第2章 古典密码技术

定义2.1 一个密码系统(Cryptosystem)是一个五元 组(P, C, K, E, D)满足条件：(1)P是可能明文的有限集；(明文空间)

(2)C是可能密文的有限集；(密文空间)(3)K是一切可能密钥组成的有限集；(密钥空间) (4)对于k∈K,有一个加密算法 ek∈E 和相应的 解密算法dk∈D ,使得

ek:P→C 和 dk:C →P 分别为加密、解密函数，满足dk(ek(x))=x,这里 x∈ P

第 2章

古典密码技术

对称密码是一种加解密使用相同密钥的密码体 制 应用密码体系应满足的特性 每个加密函数和每个解密函数都应当能有效的被 计算(密码的易用性)

即使看到密文串y,窃听者Oscar确定所用的密钥 k或明文串x是计算上不可行的(安全性) 已知密文串y的情况下试图计算密钥k或x的过程 称为密码分析(Cryptanalysis)

密码分析包含基于算法性质的分析和穷举密钥 分析6

第2章 古典密码技术

古典密码的分类 代换密码(Substitution)

置换密码(Permutation)

代换密码：将明文元素(字符、比特) 映射成密文的元素 置换密码：将明文元素的位置进行系统 的置换

代换密码(替代密码)

代换是古典密码中用到的最基本的处理技巧之一； 将明文字母表抽象的表示为一个整数集Zq={0, 1,… q-1}。 代换密码就是用密文位串代替明文位串 代换密码是指先建立一个代换表，加密时将需要加 密的明文依次通过查表，替换为相应的字符，明文 字符被逐个替换后，生成无任何意义的字符串，即 密文，代换密码的密钥就是其替换表； 根据密码算法加解密时使用代换表多少的不同，代 换密码又可分为单表代换密码和多表代换密码。 多表替代密码的密码算法加解密时使用多个替换表

单表代换密码

密码算法加解密时使用一个固定的代换

表；加密变 换过程就是将明文中的每一个字母替换为密文字母 表的一个字母 Caesar密码：26个英文字母与整数0, 1, …, 25一 一对应：

加密变换: c=E(3,p)=(p + 3) (mod 26) 解密变换: p=D(3,c)=(c - 3) (mod 26)

D将Caesar密码一般化，取任意的整数k作为密钥:加密变换: c=E(k,p)=(p + k) (mod 26) 解密变换: p=D(k,c)=(c – k) (mod 26)9

一般单表代换密码

Caesar密码密钥数量过少； 一般单表替代密码的原理是以26个英文字母集合上 的一个置换π为密钥构造代换表，对明文消息中的每 个字母依次进行变换。 例：设置换π的对应关系如下： abcdefghi jklmnopqrstuvwxyz qwertyuiopasdf ghjklzx cvbnm 试用单表替代密码以π为密钥对明文消息message 加密，然后写出逆置换 ，并对密文解密。 解：密文消息为： π(m)π(e)π(s)π(s)π(a)π(g)π(e)=dtllqut10

一般单表代换密码

一般单表替代密码算法特点： 密钥空间K很大，|K|=26!=4×1026 ,破译者穷 举搜索计算不可行，1微秒试一个密钥，遍历全部 密钥需要1013 年。 移位密码体制是替换密码体制的一个特例，它仅含 26个置换做为密钥空间。 密钥π不便记忆，通常会采用密钥短语密码：选用 一个英文短语或单词串作为密钥，去掉其中重复的 字母得到一个无重复字母的字符串，然后再将字母 表中的其它字母依次写于此字母串后，就可构造出 一个字母替代表。

仿射密码

仿射密码是一种线性变换。仿射密码的明文空间和 密文空间与移位密码相同，但密钥空间为 K={(k1 ,k2)| k1,k2∈Z26,gcd(k1,26)=1};对任意 m∈M,c∈C,k = (k1,k2)∈K,定义加密变换和 相应的解密变换为： c = ek (m) = k1 m +k2 (mod 26) m = dk (c) = k1-1 (c-k2) (mod 26) 例:选择k1=11,k2=6,明文是“sorcery”的仿射 密码加解密。

多表代换密码

单表替代密码表现出明文中单字母出现的频 率分布与密文中相同 多表代换密码是以一系列(两个以上)代换 表依次对明文消息的字母进行代换的加密方 法 多表替代密码使用从明文字母到密文字母的 多个映射来隐藏单字母出现的频率分布

多表代换密码

1. 维吉尼亚密码：最古老而且最著名的多表代换密码 体制之一，与位移密码体制相似，但维吉尼亚密码的 密钥是动态周期变化的。 该密码体制有一个参数n。在加解密时，按n个字母 一组进行变换。 加密变换定义如下： 设密钥 k=(k1,k2,…,kn), 明文m=(m1,m2,…,mn): e(k, m)=(c1,c2,…,cn), 其中ci=(mi + ki)(mod26),i =1,2,…,n 对密文 c=(c1,c2,…,cn), 解密变换为： d(k, c)=(m1,m2,…,mn), 其中 mi=(ci -ki)(mod26),i =1,2,…,n14

维吉尼亚密码

例：设密钥k =cipher,明文消息appliedcryptosystem,试 用维吉尼亚密

码对其进行加密，然后再进行解密。 解：由密钥k=cipher,得n=6,密钥对应的数字序列为 (2, 8,15,7,4,17)。然后将明文按每6个字母进行分组，并转 换这些明文字母为相应的数字，再用模26加上对应密钥数字， 其加密过程如表2.3所示。表2.3 密钥为cipher的维吉尼亚密码加密过程

密文为：cxtsmvfkgftkqanzxvo。 解密使用相同的密钥，但用模26的减法代替模26加法，这里 不再赘述。15

多表代换密码

2. 希尔(Hill)密码 Hill密码算法的基本思想是将 n个明文字母通过线性变换，将 它们转换为n个密文字母。解密只需做一次逆变换即可。 算法的密钥 K={Z26 上的 n*n 可逆矩阵 } ,明文 M 与密文 C 均 为n维向量，加密和解密变换分别为： C=K*M(mod 26); M=K-1*C(mod 26) 其中，K–1为K在模26上的逆矩阵：KK–1 =K–1K=I (mod 26) 这里 I 为单位矩阵。 a1,1 定理2.1:假设A= a 2,1

行列式： det A a1,1a2,2 a1,2a2,1 是可逆的，那么： 1 1

a1,2 a2,2 是一个Z26上的2×2矩阵，它的

a2,2 a1,2 A (det A) mod 26 a2,1 a1,1 16