《第03讲古典密码》由会员分享，可在线阅读，更多相关《第03讲古典密码（37页珍藏版）》请在金锄头文库上搜索。
1、BESTI密 码 学 第3讲2007年9月26日密码体制的形式定义称五元集合(,)为一个密码体制，其中，复习 明文m -明文空间 密文c -密文空间密钥k=(ke ,kd )ke是加密密钥,kd是解密密钥-密钥空间Eke Eke :可逆且由ke控制-加密算法空间Dkd Dkd :可逆且由kd控制-解密算法空间重要原则：对中每个密钥k=(ke ,kd ), Eke和Dkd互为逆变换。MME EKKD DC C明文空间明文空间密文空间密文空间加密算法空加密算法空 间间解密算法空解密算法空 间间密钥空间密钥空间Ekec =c =Eke(m(m) )c c. .mm. .k kd dk ke e发 方
2、收 方m =m =Dkd(c(c) )Dkd复习密码体制定义示意图本讲内容本讲内容第2章 古典密码代替密码单表代替密码多表代替密码移位密码单置换移位密码多置换移位密码乘积密码重点难点-设计与分析对正整数q ，设，X 是明文空间的字母表，Y 是密文空间的字母表。本课默认：明文空间为X或Xn=(m1m2mn) miX 密文空间为Y或Yn=(c1c2cn) ciY XY Xn Ynkke kd (单钥密码体制)的情况。是在模 q 加法和乘法下的交换环。 是在模 q 下的乘法群。约 定字母nopqrstuvwxyz 数字13141516171819202122232425字母abcdefghijklm
3、 数字0123456789101112约 定对英文字母表A a,b,c, ,z和 ,约定 A 中的字母与Z26中数字的对应关系如下表：在不会引起异议的情况下，字母与数字混合使用。代替密码例1： X = Y = K =0,1,2, ,q-1 = ZqEk: c=（m+k）mod 26 , mZq, cZq, kZq Dk: m=（c - k）mod 26 , mZq, cZq, kZq明文：d i s c r i m i n a t i o n i s a s e r i o u s p r o b l e m密文：g l v f u l p l q d wl r q l v d v h u l
4、 r x v s u r e o h p密钥： 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3密钥：2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 2 密文： f l w e u mCaesar密表dazwcbayxwvutsrqponmlkjihgfe密文字母zyxvutsrqponmlkjihgfedcb明文字母明文字母a b cd e fg h ijk lm n o p q rstu v w x y z密文字母2c d ef g h ijk
5、lm n o p q rstu v w x y z a b密文字母3d e fg h ijk lm n o p q rstu v w x y z a b c密文字母4e f gh ijk lm n o p q rstu v w x y z a b c d在A =a,b,c, ,z 上，加解密例子如下：代代 替替单表代替单表代替( (加密过程中仅用加密过程中仅用1 1张表，即张表，即1 1个密钥个密钥k k) )多表代替多表代替( (加密过程中使用加密过程中使用d d张表，即张表，即d d 个密钥个密钥k k1 1k k2 2k kd d ) )多多 表表 代代 替替一次一密代替一次一密代替（d
6、 d= =报文字母长度，且每个报文字母长度，且每个k ki i是从密钥空间中随机选取的）是从密钥空间中随机选取的）周期代替周期代替( (d d报文字母组长度，周期的应用报文字母组长度，周期的应用d d张表张表) )代替密码的分类明文： m1 m2 m3 密文： c1 c2 c3 密钥: k1 k2 k3 Ek1Ek3Ek2移位密码例2: Xn= m=(m1m2mn) miZq Yn= c = ( c1c2cn )ci Zq =Xn=Sn（n元对称群）对每个置换 p Sn，设 是其逆置换。则有Ep: c=Ep(m)=Ep(m1m2mn)=(mp(1)mp(2)mp(n)D : m=D (c)=D
7、 (c1c2cn)=(c (1)c (2)c (n)明文：discri minati onisas erious proble m密文： cisrid aintim sniaso oriuse brolep 密钥: p=(423561) p=(423561) p=(423561) p=(423561) p=(423561)密钥: p1=(423561) p2=(526413) p1=(423561) p2=(526413) p1=(423561)密文： cisrid tiiamn sniaso ursoei brolep 取n6，并将Zq变换为A =a,b,c,x,y,z，有以下例子：即为书P
8、6的 换位密码密钥: p-1=(623145) p-1=(623145) p-1=(623145) p-1=(623145) p-1=(623145)密钥: p1-1=(623145) p21=(526413) p1-1=(623145) p2-1=(526413) p1-1=(623145)加密解密移 位单单置换移位( (加密过程中仅用一个置换加密过程中仅用一个置换 p）多多置换移位( (加密过程中使用多个置换加密过程中使用多个置换p1 1 p2 2 pd d ) )多多置换 移 位一次一密一次一密移位（d d= =报文字母组长度，且每个报文字母组长度，且每个p pi i 是从密钥空间中随机
9、选取的）是从密钥空间中随机选取的）周期周期移位（d d报文字母组长度报文字母组长度, ,周期的应用周期的应用d d个置换）个置换）移位密码的分类明文： m1 m2 m3 密文： c1 c2 c3 密钥: p1 p2 p3 Ep 1Ep 3Ep 2古典密码的分类古典密码移位密码代替密码 多表代替密码单表代替密码一次一密代替密码周期代替密码一次一密移位密码周期移位密码单置换移位密码多置换移位密码小结小结单表代替密码的构造单表代替密码的构造构造单表代替密码的关键是如何构造一张明密代替表。设X=Y=a,b,c, ,z =A =字母表密钥字法首先选择一便于记忆的字母串作为密钥字，然后如下形 成明密代替表
10、：去掉重复字母，依次列出密钥字中各字母， 再依次列出字母表中其余的字母。特点：便于记忆, 但密钥量|K|比较小。明文字母ab c d e fg h ijk lm n o p q rstuv w x y z密文字母d isc rm n a to b e fg h jk lp q uv w x y z若密钥字为：discrimination明文字母ab c d e fg h ijk lm n o p q rstuv w x y z密文字母明文字母ab c d e fg h ijk lm n o p q rstuv w x y z密文字母d isc rm n a to明文字母a b cd e fg
11、h ijk lm n o p q rstuv w x y z密文字母讨论1：对以上两种方法进行讨论：1. 方法(1)是方法(2)的一种，方法(1)的密钥便于记忆，方 法(2)的保密性最好。2. 方法(2)即是书中P5的置换密码，q26。3. 按方法(2),当Xn=Yn= 时,即是书中P6的广义置换密码。4. 书中P7的Playfaie密码是当X2=Y2= (a,a),(b,b), ,(z,z) 时方法(2)的特例。单表代替密码的构造单表代替密码的构造洗牌法就是将写有每个英文字母的26张纸牌打乱次序后重新排 列形成密文字母行的排列。特点：密钥空间K由26个英文字母的所有可能的全排列构成密钥量|K
12、|=26!，密钥不容易被猜测,但不便于记忆。d e ro k n lc z h m sty fu a b q ixw p g v jPlayfair密码体制: 1、构造一个 55 的密钥矩阵（j等同于i）； 2、插入特殊字母如q,使明文每两个不同的字母为一组； 3、按下述方法加密：两字母在同一行，密文取靠近右端的字母；两字母在同一列，密文取靠近下方的字母；不在同行同列，密文取矩形对角的字母；明文： pl ay fa ir密文：bs dw rb ca 单表代替密码的构造单表代替密码的构造仿射法X=Y= 0,1,2, ,q-1 = Zq c=Ek(m)=(k1+k2m) mod q , mZq其中
13、，k=(k1,k2)为密钥；为使加密算法有逆，必要且只要 (k2,q)=1,由此，Ek的逆如下： m=Dk(c)=(k2)-1(c-k1 ) mod q , cZq特点：便于用计算机实现。密钥量：K=(k1,k2)|k1,k2Zq , (k2,q)=1,(k1,k2)(0,1)当q=26时，|K|=1226-1=311，比较小。讨论2：对以上方法进行讨论：1. 当k2=1,即为书中P4的加法密码；2. 当k1=0,即为书中P4的乘法密码。单表代替密码的构造单表代替密码的构造广义仿射法（可视为向量运算） 单表代替密码的构造单表代替密码的构造密钥量:, 是 上的不同的n阶可逆方阵的个数。 讨论3：
14、对以上方法进行讨论：当 =0向量，q=26,H换为K时，即为书P11的Hill密码体制：思考题：当 和 H 如何选取时，即可简化为书P5的简单加法密码、简单乘法密码和简单仿射密？多表代替密码的构造多表代替密码的构造例3.维吉尼亚(Vigenere)密码(见书P.9)加密算法： ci = mi + ki（mod 26）解密算法： mi = ci ki（mod 26） mi,ci, ki Z26多表代替密码的构造多表代替密码的构造abcdefghijklmnopqrstuvwxyZa 0ABCDEFGHIJKLMNOPQRSTUVWXYZb 1BCDEFGHIJKLMNOPQRSTUVWXYZAc 2CDEFGHIJKLMNOPQRSTUVWXYZABd 3DEFGHIJKLM
