第2章密码学概论

实验一 循环移位密码
实验原理：将明文中的每个字母用引字符在字母表中后面第 个字母替 实验原理：将明文中的每个字母用引字符在字母表中后面第k个字母替 它的加密过程可以表示为下面函数： 代。它的加密过程可以表示为下面函数： E(m)=(m+k) mod n 其中， 为明文字母在字母表中的位置数 为明文字母在字母表中的位置数； 为字母表中的字母个数 为字母表中的字母个数； 其中， m为明文字母在字母表中的位置数；n为字母表中的字母个数； k为密钥；E(m)为密文字母在字母表中对应的位置数。 为密钥； 为密文字母在字母表中对应的位置数。 为密钥 为密文字母在字母表中对应的位置数 同理可得解密过程。 同理可得解密过程。 实验内容：根据实验原理，自己创建明文信息，并选择一个密钥， 实验内容：根据实验原理，自己创建明文信息，并选择一个密钥，编 写循环移位密码算法的实现程序，实现加密和解密操作。 写循环移位密码算法的实现程序，实现加密和解密操作。要求上述 密码算法最后的实现程序提供加密和解密两个接口： 密码算法最后的实现程序提供加密和解密两个接口：int encrypt() 和 int decrypt()。当加密或者解密成功时返回 。当加密或者解密成功时返回CRYPT_OK, 失败时返 回CRYPT_ERROR。 。
比如，M＝data security，K＝best，首先将M分解成长为4 的序列 data secu rity，每一节利用K进行加密得到密文 C＝ EK(M)＝eelt tiun smlr 注：维吉尼亚密码是多表替换体制，分析起来更困难。 密钥空间大，如当m=5时，密钥空间所含密钥的数量 是>1.1×107
4、加密（encryption） 由明文变换成密文的伪装过程。 5、解密（decryption） 将密文还原成明文的变换过程。 6、密码算法（algorithm/cipher） 将明文变换为密文或将密文还原成明文所使用的一组 公式或者法则，它规定了明文与密文之间的交换方法。
受限制（restricted）的算法、基于密钥的算法
2.替换密码体制 替换密码体制
• 设P=C=Z/(26)，K是由26个符号0，1,..,25的所有可能 置换组成。任意 π ∈K ，定义 eπ (x) = π (x) = y且 d π(y)=π-1(y)=x, π-1是π的逆置换。 注： 1*. 置换π的表示：
0 1 2 3 L 23 24 25 π = 0' 1' 2' 3' L 23' 24' 25'
Bob收到后解密：xi=dk(yi) 得到明文X=x1 x2… xn .。
2*.加密函数ek必须是单射函数，就是一对一的函数。 3*.若P=C，则ek为一个置换。 4*.好的密钥算法是唯密钥而保密的。 5*.若Alice和Bob在一次通信中使用相同的密钥，那 么这个加密体制为对称的，否则称为非对称的。
7、加密通信的模型 Oscar Alice x k 密钥源 y x
Байду номын сангаас
加密机
解密机
Bob
安全信道
密码学的目的：Alice和Bob两个人在不安全的信道上进行 密码学的目的 通信，而破译者Oscar不能理解他们通信的内容。
• 定义 (密码体制）它是一个五元组（P,C,K,E,D)满足条件： 定义: 密码体制 密码体制） （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间） *（4）任意 k∈K ,有一个加密算法 ek ∈E 和相应的解密算法 dk ∈D ，使得 ek : P → C 和 dk : C →P 分别为加密解密函 数，满足 d k (ek ( x)) = x, 这里, x ∈ P 。 注：1*.Alice要将明文Ｘ在不安全信道上发给Bob，设X=x1 xi ∈P x2… xn , 其中 , Alice用加密算法ek作yi=ek(xi) 1≤ i≤ n 结果的密文是 Y=y1y2….yn ,在信道上发送，
二、经典密码体制
移位密码 替换密码 维吉尼亚密码 Hill密码
1.移位密码体制 1.移位密码体制
• 设P=C=K=Z/(26),对 k∈K ,定义 ek (x) = x + k(mod 26) = y ∈C 同时dk(y)=y-k (mod 26) 注1*：26个英文字母与模26剩余类集合{0,….,25}建立一一对应： ABCDE F G H I J K L M NO PQRS TUVWX Y Z
c1 c2
（Mod 26 ） K－1 = 15 20 （Mod 26 ） 17 9
K•K－1 ＝E ＝
密码分析
• 假设破译者Oscar是在已知密码体制的前提下来破译Bob 使用的密钥。这个假设称为Kerckhoff原则。最常见的破 解类型如下： 1.唯密文攻击：Oscar具有密文串y. 2.已知明文攻击: Oscar具有明文串x和相应的密文y. 3.选择明文攻击：Oscar可获得对加密机的暂时访问，因 此他能选择明文串x并构造出相应的密文串y。 4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y， 并构造出相应的明文x. 5.这一切的目的在于破译出密钥 破译出密钥
破解举例
• 例3.1 已知下面的密文是由单表代换产生的： UZQSOVUOHXMOPVGPOZPEVSGZWSZ OPFPESXUDBMETSXAIZVUEPHZHMDZS HZOWSFPAPPDTSVPQUZWYMXUZUHS XEPYEPOPDZSZUFPOMBZWPFUPZHMDJ UDTMOHMQ，试破译该密文 • 首先统计密文中字母出现的频率，然后与 英文字母出现频率比较。密文中字母的相 对频率统计如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2*.当k=3时，为Caesar密码： 若密文：PHHW PH DIWHO WKH WRJD SDUWB 明文： meet me after the toga party
英文字母中单字母出现的频率
• 单字母按照出现频率的大小可以分为下面5类： (1) e：出现的频率大约为0.127 (2) t, a, o, I, n, s, h, r：出现的频率大约在0.06-0.09之间 (3) d, l：出现的频率约为0.04 (4) c, u, m, w, f, g, y, p, b：出现的频率大约在0.015-0.028 之间 (5) v, k, j, x, q, z：出现的频率小于0.01 • 双字母和三字母组合都有现成的统计数据，常见的双字母 组合和三字母组合统计表能够帮助破解密文。 • 频率最高的30个双字母（按照频率从大到小排列）： th he in er an re ed on es st en at to nt ha nd ou ea ng as or ti is et it ar te se hi of • 频率最高的20个3字母（按照频率从大到小排列）： the ing and her ere ent tha nth was eth for dth hat she ion int his sth ers ver
• • • k11 k12 … k1d k21 k22 … k2d • • • kd1 kd2 … kdd ..
x1 x2 xd
• • •
＝
（mod n）
c1＝（k11x1＋k12 x2＋…＋k1dxd ） mod n .. .. …………………………… cd＝（kd1x1＋kd2 x2＋…＋kddxd ） mod n
例子：当 m=2时，明文元素x=(x1,x2), 密文元素c=(c1, c2)， 11 3 用密钥 K= 8 7 来加密明文july。
• 事实上ci为x1,x2的线性组合，c1=11x1+3x2;c2=8x1+7x2， 一般，将取m×m的矩阵K作为我们的密钥：有
k11 k12 k21 k22 y=(y1, y2,…, ym,)= M M k k m1 m2
2*密钥空间K很大，|K|=26! ≈ 4×1026，破译者穷举搜索是 不行的，然而，可由统计的方式破译它。 3*移位密码体制是替换密码体制的一个特例，它仅含26 个置换做为密钥空间
3.维吉尼亚密码 3.维吉尼亚密码 (Vigenere)
由于英文字母中各字母出现的频度早已有人进行过统计工作， 所以根据字母频度表可以很容易对替换密码进行破译。替换密码 是对所有的明文字母都用一个固定的代换进行加密，因而称为单 表代换密码。为了抗击字母频度分析，随后产生了多表代换密码。 维吉尼亚密码是一种最著名的多表移位代替密码。 • 设m为一固定的正整数，定义P=C=K=(Z/(26))m,对一个密钥K＝ （ k1,k2,…,km),定义 ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y dk(y1,y2,…,ym)= (x1-k1,x2-k2,…,xm-km) =x 这里的所有的运算都是在（mod 26)中进行的。
• 将统计结果与图3.3进行比较，可以猜测密文中P 与Z可能是e和t，密文中的S,U,O,M出现频率比较 高，可能与明文字母中出现频率相对较高的a, o, I, n, s, h, r这些字母对应 • 密文中出现频率很低的几个字母C,K,L,N,R,I,J可能 与明文字母中出现频率较低的字母v, k, j, x, q, z对 应。就这样边试边改，最后得到明文如下： • it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow • 在尝试过程中，如果同时使用双字母和三字母的 统计规律，那么更容易破译密文。如上面的密文 中出现最多的双字母是ZW，它可能对应明文双字 母出现频率较大的th，那么ZWP就可能是the，这 样就更容易试出明文。