《计算机安全保密第三讲》由会员分享，可在线阅读，更多相关《计算机安全保密第三讲（57页珍藏版）》请在金锄头文库上搜索。
1、计算机安全保密第三讲传统加密方法唐明 武汉大学计算机学院本次课的内容3.1 换位法 3.2 简单代替密码 3.3 同音代替密码 3.4 多表代替密码 3.5 多字母组代替密码3.1 换位法w 换位法按照一定的方法来重新排列字 符，通常是借助于某种几何图表来实 现。 w 加密过程分为两个步骤：将明文按照一定的路径写入图表中； 以某种路径从图表中取出字符构成密文 。明文写入图表密文取出图例：例1w 设明文DATA SECURITY写入一个34 的矩阵：1 234 DATA SECU R IT YAEIw 若按照2413的顺序将各列写 出，则密文为: ? AUYDSRTCT周期换位密码w 周期换位密
2、码：以一定的周期来变换明文 字符。 令Zd为从1到d的整数集合，f：Zd Zd为Zd上的 一个排列，密码的密钥由k(d，f) 给出。连续 的d个字符由f来加密。因此，明文信息：M m1mdmd+1m2d 被加密成密文为：Ek(M) mf(1)mf(d)md+f(1)md+f(d)解密为其逆操作。与列换位密码相比，周期换位密码用计算机实 现时效率更高。例2 w 设d4，f为i: 1234f(i):2413 w 则第1个明文字母在密文中被移到第3个位置，而第 2个明文字母被移到第一个位置，依此类推。 w 明文DATA SECURITY被加密为 M = DATA SECU RITYEk(M) = ?
3、（按行写入，列做移位操作，按行取出） D A T AS E C UR I T YAEIAUYDSRTCTAADT EUSC IYRTf-1(i)=?换位密码的破译w 换位密码中，密文中字母出现的频率 与明文中字母出现的频率相同，所以 密码员可以很容易的由此来判别换位 密码。 w 这种密码可以通过移动字母顺序的方 法来破译。 w 还可以参考双字母和三字母组合的出 现频率分布。图 3.1 双字母组出现频率分布 在某个包含 了67375个字 母的文件中 ，双字母组 合出现的概 率统计分布w 对于周期为d的换位密码，这d个字母 共有d!种可能组合。假设所有的密钥 出现的机会相等，则密钥的熵为 H(K)
4、=log2d!, w 使用Sterling的对d!的估计法，确定性 距离： dlog2(d/e)3.2u = 0.3dlog2(d/e)令D=3.2位/字母，设d=27，则d/e10，log2(d/e) 3.2 ，因此，u 27。3.2 简单代替密码w 有四种代替密码： 1. 简单代替密码 2. 同音代替密码 3. 多表代替密码 4. 多字母代替密码 w 简单代替密码将明文字母表中的每个 字母用密文字母表中相应的字母来代 替。3.2.1 简单代替密码的描述w 令A为n个字母的字母表a0，a1， an-1，则C为n个字母的字母表f(a0)， f(a1)， ，f(an-1)，其中f：AC为从 A中
5、的每个字母到C中的相应字母的一 对一映射。密码的密钥由C给出，或 者说，由函数 f 给出。 w 若明文信息为：M = m1，m2， ，则 密文为：Ek(M) = f(m1)f(m2)例3w 设f从标准的英语字母表A=A，B，C， ，Z映射到如下的密文字母表C：A：ABCDEFGH I J KLMNOP QR STUVWXYZC：HARPS I CODBEF G J KLMNQTUVWXYZ则明文INTELLIGENT被加密为：M=I N T E L L I G E N TEk(M)=？例3w 设f从标准的英语字母表A=A，B，C， ，Z映射到如下的密文字母表C：A：ABCDEFGH I J K
6、LMNOP QR STUVWXYZC：HARPS I CODBEF G J KLMNQTUVWXYZ则明文INTELLIGENT被加密为：M=I N T E L L I G E N TEk(M)=D J T S F F D C S J T3.2.1 简单代替密码的描述w 恺撒密码：基于移位字母表（有时也称为 直接标准字母表）的密码，将字母表的字 母右移K个位置，并对字母表长度做模运算 ，形式为：f(a) = (a+k) mod nn为字母表的长度，a为字母在字母表中的位置 。在标准英语字母表中，每个字母的位置如下： 0-A 1-B24-Y25-Z举例令k=3，n=26，明文：M=Message
7、，则密文为 ：因为凯撒曾使用过K=3的这种密码，所以叫做 凯撒密码。M e s s a g e = P h v v d j hw 基于标准字母表乘法的密码： f(a) = a k mod n，其中k和n为互素的。思考：如果k和n不互素，会出现什么问题 ？例w 令k = 7，A为标准的英语字母表，则有 ：A =ABC DEF GHI JKL MNO PQR STU VWX YZ C = AHO VCJ QXE LSZ GNU BIP WDK RYF MT 明文：INTELLIGENT 密文：ENDCZZEQCND仿射变换密码w 基于仿射变换的密码： f(a) = (ak1+k0) mod n 其
8、中：k1和n是互素的。w 利用t阶多项式变换可以生成高阶的变换。 高阶变换 f(a) = (atkt + at - 1kt 1 + + ak1 + k0) mod n 恺撒密码是0阶多项式变换，而仿射变换是一 阶多项式变换。兽栏密码有些代替密码使用非标准的密文字母表，如 兽栏密码。对课本P36的兽栏密码进行解密REMEMBER DEATH3.2.2 单字母频率分析w 简单代替密码可能很容易的通过使用单字母频率分 析法的只有密文的攻击来破译。w 基于移位字母表的密码通常易于破译，因为每个密 文字母与相应的明文字母的差为一个常数。w 基于仿射变换的密码：求解联立方程组 已知t个对应的明文字母mi和
9、密文字母ci(1i t) ，则(m1k1+k0) mod n=c1(mtk1+k0) mod n=ctw 例：明文：F(5), I(8)和L(11), 对应的密文为 ：M(12), S(18)和Y(24)。 (5k1+k0) mod 26 = 12(1) (8k1+k0) mod 26 = 18(2) (11k1+k0) mod 26 = 24(3)(2)-(1)得：3k1 mod 26 = 6 解得：k1=6 * 3-1 mod 26 = 6 * 9 mod 26 = 2 代入(1)，得：k0 = 2注意:得到的结果k0和k1 需要代入第三个方程 检验。图 3.3 单字母频率分布 某个文件中
10、 各字母的频 率分布图 3.4 以频率划分的字母 3.3 同音代替密码w 同音代替密码：将明文字母表中的每个字 母a映射到一系列密文字母f(a)，这些f(a)称 为同音字母。 一个明文信息M=m1m2被加密为C=c1c2,其中 ci是从f(mi)的集合中随机选取的。w 密文符号的相关分布会近似于平均，这可 以挫败频率分析，所以同音代替密码比简 单代替密码难破译得多。字母同音字母A 17 19 34 41 56 60 67 83I 08 22 53 65 88 90L 03 44 76N 02 09 15 27 32 40 59O 01 11 23 28 42 54 70 80P 33 91T
11、05 10 20 29 45 58 64 78 99M = P L A I N P I L O TC = 91 44 56 65 59 33 08 76 28 78Beale密码 P39C= 115 73 24 818 37 52 49 17 31 62 657 22 7 15 M= I have deposited(1) When, in the course of human events, it becomes necessary (11) For one people to dissolve the political bands which have (21) Connected t
12、hem with another, and to assume among the Powers (31) Of the earth the separate and equal station to which (41) The Laws of Nature and of Natures God entitle them, (51) A decent respect to the opinions of mankind requires that (61) They should declare the causes which impel them to the (71) separati
13、on. We hold these truths to be self-evident, that (81) All men are created equal, that they are endowed by (91) Their Creator with certain unalienable rights, that among (99) These are Life, Liberty, and the pursuit of Happiness.高阶同音代替密码E I L M SEILMS10 22 18 02 1112 01 25 05 2019 06 23 13 0703 16 0
14、8 24 1517 09 21 14 04M = S M I L EX = L I M E S C = f1f216 05 19 11213.4 多表代替密码w 多表代替密码：使用从明文字母到密文字母的多个 映射，每个映射是像简单代替密码中的一对一映射 。w 基于周期d的周期代替密码：给定d个密文字母表C1,Cd ，令 fi：A Ci为 从明文字母表A到密文字母表Ci（1i d）的映射 。 对明文信息：Mm1mdmd+1m2d 加密，有：Ek(M)f1(m1)fd(md)f1(md+1)fd(m2d)w 当d1时，密码为单表代替密码等价与简单代替密 码。3.4.1 Vigenre和Beaufo
15、rt密码w Vigenre密码是一种基于移位字母表的周期代替密 码，它的密钥K由一个字母序列来指定：kk1kd 。 其中： ki（i1，d）给出了第i个字母表的移动位数 ，即fi(a)(a+ki) mod n.w 例如：明文INTELLIGENT用密钥PLAY加密为： MINTE LLIG ENT KPLAY PLAY PLAEk(M)XYTC AMIE TYTw 例 设m6，且密钥字是CIPHER,这相应于密钥。 假定明文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按6个一组分段，然 后模26“加”上密钥字得：使用Vigenre表可以方便地进行加密和解密。相应的密文串将是: VPXZGIAXIVWPUBTTMJPWIZITWZT 解密过程与加密过程类似,不同的只是进行模26减,而不是
