第三讲-古典密码

网络信息安全陈羽中yzchen1979@163.com密码系统分类密码系统的几种分类:按执行的操作替换(substitution)与置换(permutation)按密钥的数量

单密钥(对称密钥)与双密钥(公开密钥)按明文处理方式

流密码(streamcipher)与分组密码(blockcipher)古典密码基于字符的密码替换（substitutioncipher)：就是明文中的每一个字符被替换成密文中的另一个字符,接收者对密文做反向替换就可以恢复出明文置换(permutationcipher):又称换位密码（transpositioncipher)：明文的字母保持相同，但顺序被打乱了替换密码单字母替换密码（simplesubstitutioncipher),又称单字母密码(monoalphabeticcipher):明文的一个字符用相应的一个密文字符代替。多字母替换密码（ployalphabeticcipher)：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。单字母替换密码一.恺撒密码

E(p)=(p+3)mod26

明文:abcdefghijklmnopqrstuvwxyz

密文:defghijklmnopqrstuvwxyzabc

例子:

明文：meetmeaftertheparty

密文：phhwphdiwhowkhsduwb给定加密的消息: phhwphdiwhowkhsduwb由于加解密算法已知可能尝试的密钥只有２6个明文的语言已知通过强力攻击得到明文：meetmeaftertheparty.

移位密码很容易受到唯密文攻击单字母替换密码分析单字母替换密码(续)二.密钥短语密码1.选择密钥并删除重复字母.2.在明文的字母表下方从左往右写下处理的后的密钥,然后再写剩余的字母即得密文字母表.

如密钥短语密码为:hello->helo

明文:abcdefghijklmnopqrstuvwxyz

密文:heloabcdfgijkmnpqrstuvwxyz任意的单表替换密码:

明文:abcdefghijklmnopqrstuvwxyz

密文:sdvjkltioxcfawqzupyreghbam例子:crypt=>VPNZR密钥空间为26!>4*1026通过字母的使用频率破译对单表替换密码的统计分析攻击例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ统计分析攻击单一字母替换容易被攻破，因为反映了原来字母表的频率数据分配给每个字母的符号数正比于该字母的相对频率，则单字母的频率信息就会完全被淹没对明文的多个字母加密使用多表替换多表替换密码多表替换密码:以一系列（两个以上）替换表依此对明文消息的字母进行替换的方法非周期多表替换密码：替换表是非周期的无限序列,密钥和明文长度相同周期多表替换密码：替换表个数有限，重复使用。维吉尼亚密码(1858)是一种多表移位替换密码:设d为一固定的正整数，d个移位替换表=（1，2,…d)由密钥序列K＝（k1,k2,…,kd)给定，第i+td个明文字母由表i决定，即密钥ki决定

ek(xi+td)=(xi+td+ki)modq=y

dk(yi+td)=(yi+td-ki)modq=x替换表维吉尼亚密码(1858)例子:q=26,x=polyalphabeticcipher, K=RADIO密钥字为RADIO,则相应密钥为(17,0,3,8,14)明文x=polyalphabeticcipher密钥k=RADIORADIORADIORADIO密文y=GOOJOCPKTPNTLKQZPKMFPlayfair:将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。5×5变换矩阵的生成:I与J视为同一字符(取CIPHER作为密钥) CIPHE RABDF GKLMN OQSTU VWXYZ多字母替换密码-Playfair多字母替换密码-Playfair明文的分组balloonballoon分组规则：1、相同字母在同一分组时：在该分组两个字母之间插入字母X，对明文重新进行分组2、分组只有一个字母时：若发现情况1并进行调整后，最后一个分组仍然只有一个字母，在最后加入字母X。balloonbalxloon多字母替换密码-Playfair加密规则:按成对字母加密1)若明文对在矩阵中是同行关系：将这对字母均向右移一格,如有字母在右边界，则移动到同行左边首字母。

heEC2)若明文对在矩阵中是同列关系：将这对字母均向下移一格。若有字母在下边界，则移动到同列首字母。

dmMT3)其他情况取交叉:ktMQODTRPlayfair密码以前面的5×5变换矩阵(cipher)为例

CIPHE RABDF GKLMN OQSTU VWXYZ (1)balloonbalxloondbspgsug (2)bookbookrsqg (3)fillfilxlxaespspPlayfair有26X26=676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息Playfair密码分析仿射密码用形如e(x)=ax+b(mod26),a∈Z26,b∈Z26的加密函数的加密算法称为仿射密码，这类加密函数称为仿射函数。(a=1时为移位密码)(1)：要求解唯一的充要条件是gcd(a,26)=1(2)：从(1)可知,当且仅当a与26互素时，加密变换才是一一映射的，因此a的选择有11种：

a=3,5,7,9,11,15,17,19,21,23,25密钥空间大小12x26=312种！仿射密码算法定义设P=C=Z26,K={(a,b)∈Z26*Z26|gcd(a,26)=1},对k=(a,b)∈K,定义:ek(x)=ax+b(mod26)dk(y)=a-1(y-b)(mod26)x,y∈Z26加密函数取形式为e(x)=ax(mod26),a∈Z26要求唯一解的充要条件是gcd(a,26)=1该算法描述为：设P=C=Z26，K={a∈Z26|gcd(a,26)=1},对k=a∈K,定义:ek(x)=ax(mod26)dk(y)=a-1(y)(mod26)x,y∈Z26仿射密码-乘数密码算法乘数密码算法例子例子:a=9,

ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX乘数密码分析:对于乘数密码，当且仅当a与２６互素时，加密变换才是一一映射的，因此a的选择有１１种：

a=3,5,7,9,11,15,17,19,21,23,25

可能尝试的密钥只有1１个例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3,相应的解密函数是dk(y)=15(y-3)=15y-19,易见

dk(ek(x)）=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：（二)Hill密码（1929）基于矩阵的线性变换:K是一个m*m矩阵,在Z26上可逆,即存在K-1使得:KK-1=I(在Z26)对每一个k∈K,定义ek(x)=xK(mod26)dk(y)=yK-1(mod26)明文与密文都是m元的向量(x1,x2…,xm);(y1,y2,…,ym)Hill密码例子：当m=2时，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

K

若K=,可得K-1=若对明文july加密，分成2个元素（j,u),(l,y),分别对应于（9,20）,（11,24）,有（9,20）＝（99＋60,72＋140）＝（3,4）

且(11,24)

＝(121＋72,88＋168)＝（11,22）于是对july加密的结果为DELW。Hill密码为了解密，计算

且因此，得到了正确的明文“july”一次一密方案-Vernam密码1918年，GillbertVernam建议密钥采用与明文一样长并且没有统计关系的密钥内容(随机生成)，他采用的是二进制数据:加密：Ci=Pi

Ki解密：Pi=Ci

Ki核心：构造和消息一样长的随机密钥

一次一密方案绝对安全但不实用，需要以某种安全的方法将与消息长度相等的密钥传送给接收方，以允许解密。而且，密钥只使用一次，然后就被丢弃，增加了密钥管理问题媒体访问接入协议中使用了一次一密古典密码安全性分析单表替换：字母频度、重复字母模式、字母结合方式的统计特性不变多表替换：明文统计特性通过多表替换被隐藏古典密码安全性分析假设从仿射密码获得的密文为FMXVEDKAPIIFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH.试破解该密文。统计各字母频率，R出现8次，D出现6次，E,H,K各出现5次，F,S,V各出现4次假定R(17)是e(4)的加密，D(3)是t(19)的加密，得a=6,b=19假定R是e的加密，E是t的加密,得a=8,b=11假定R是e的加密，K是t的加密，得a=3,b=5