医学-第2讲古典密码体制

2023/9/31应用密码学张仕斌万武南张金全孙宣东编著西安电子科技大学出版社二00九年十二月2023/9/32第2章古典密码体制2学时2023/9/33知识点：

隐写术

替换〔代替〕密码技术

换位密码技术

古典密码体制的平安性分析2023/9/341.隐写术2023/9/35诗情画意传“密语〞

水洗尘埃道未甞，甘于名利两相忘。

心怀六洞丹霞客，口诵三清紫府章。

十里采莲歌达旦，一轮明月桂飘香。

日高公子还相觅，见得山中好酒浆。洗尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆2023/9/36牛郎织女会佳期下弹琴又赋诗

寺静惟闻钟鼓響停始觉星斗移

多少黄冠归道观幾而作尽忘机

几时得到桃源洞彼仙人下象棋牛郎织女会佳期，月下弹琴又赋诗。

寺静惟闻钟鼓響，音停始觉星斗移。

多少黄冠归道观，见幾而作尽忘机。

几时得到桃源洞，同彼仙人下象棋。诗情画意传“密语〞2023/9/37王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。2023/9/38隐写术〔信息隐藏〕的另外一些例子悠扬琴声奏响“进军号角〞显微镜里传递情报魔术般的密写术网络与数字幽灵量子技术隐形传递信息2023/9/39隐写术的优点☆能够被某些人使用而不容易被发现他们间在进行秘密通信☆加密那么很容易被发现谁与谁在进行秘密通信，这种发现本身可能具有某种意义或作用2023/9/310隐写术的缺点☆形式简单但构造费时，要求有大量的开销来隐藏相对较少的信息☆一旦该系统的构造方法被发现，就会变得完全没有价值☆隐写术一般无稳健性2023/9/311替换密码技术是基于符号替换的密码技术，这种密码技术是以符号的置换来到达掩盖明文信息。这类密码技术有：单字符单表替换密码技术〔比方教材上：简单替代密码技术、多名码代替密码技术和多字母代替密码技术〕、单字符多表替换密码技术〔比方教材上：多表代替密码技术〕等。2.替换密码技术代替密码就是明文中每一个字符被替换成密文中的另外一个字符。古典密码技术根据其根本原理大体上可以分为两类：替换密码技术和换位密码技术。2023/9/312〔1〕单字符单表替换密码技术：单字符单表替换密码技术是对明文中的所有字符都使用一个固定的映射。典型的单字符单表替换密码技术有：①乘法密码技术设A={a0，a1，…，an-1}为明文字母表，B={b0，b1，…，bn-1}为密文字母表，单字符单表替换密码技术使用了A到B的映射关系：f：A→B，f(ai)=bj〔一般情况下，为保证加密的可逆性，f是一一映射〕将明文中的每一个字母替换为密文字母表中的一个字母。单字符单表替换密码技术的密钥就是映射f或密文字母表〔一般情况下明文字母表与密文字母表是相同的，这时的密钥就是映射f〕。2023/9/313乘法密码技术的加密变换：Ek〔ai〕=aj，j=ik〔modn〕，gcd〔k,n〕=1乘法密码技术的解密变换：Dk〔aj〕=ai，i=jk-1〔modn〕乘法密码技术的密钥是k。假设n是素数，那么有n-2个密钥〔k=1时加密变换是恒等变换，应该予以抛弃〕；假设n不是素数，那么有φ(n)-1个密钥〔其中φ(n)为欧拉函数的值〕。2023/9/314②移位替换密码技术：是最简单的一种替换密码。-移位密码的数学根底：假设a和b都是整数，m是一个固定的正整数。假设m整除a-b，即ma-b时，称整数a，b关于模m同余，记作ab(modm)假设m不能整除a-b，那么称a,b关于模m不同余。正整数m称为模数。明显地：29

5(mod8)101

3(mod7)-101

4(mod7)121，4关于模2不同余易知：a

b(modm)

a(

modm)

b(

modm)2023/9/315-模的同余性质：(1)自反性：aa(modm)(2)对称性：假设ab(modm),那么ba(modm)(3)传递性：假设ab(modm),bc(modm),那么ac(modm)(4)(a+b)(modm)a(modm)+b(modm)(5)(ab)(modm)a(modm)b(modm)(6)假设ab(modm)，cd(modm),那么l，kZ(整数集合),有lakclbkd(modm)，且acbd(modm)(7)设f(x)与g(x)分别是两个整系数多项式：f(x)=anxn+an-1xn-1+…+a,g(x)=bnxn+bn-1xn-1+…+b那么(ⅰ)假设ab(modm)，那么f(a)f(b)(modm)(ⅱ)假设ab(modm)，且akbk(modm)，k=0,…,n，那么f(a)g(b)(modm)2023/9/316

移位密码实质上是正整数m上模运算，特别用Zm={0,1,…,m-1}表示模m的剩余类，定义Zm上的加法和乘法，它完全类似于普通的实数域上的数的加法和乘法，不同的仅是运算结果是取模以后的余数。-定义〔移位密码算法〕:设P=C=K=Z26，对0k25,即kK,x,yZ26,定义加密函数：Ek(x)=(x+k)(mod26)解密函数：Dk(y)=(y-k)(mod26)2023/9/317加密变换为：Ek〔ai〕=aj，j=〔i+k〕〔modn〕，0<k<n解密变换为：Dk〔aj〕=ai，i=〔j-k〕〔modn〕=〔j+〔n-k〕〕〔modn〕由于i=〔j-k〕〔modn〕=〔i+k-k〕〔modn〕=i〔modn〕，所以解密与加密是可逆的。从解密变换中可以看出：Dk=En-k。2023/9/318移位替换密码技术的密钥是k，k唯一地确定了明文空间到密文空间的映射，故移位替换密码技术的密钥空间的元素个数为n-1。用密钥穷搜索方法很容易破译。

③

密钥字密码技术：它利用一个密钥字来构造替换作为密钥。④仿射密码技术：是加法密码技术和乘法密码技术的结合体。2023/9/319

k，b为该算法的密钥。当b=0时，仿射密码技术退化为乘法密码技术，当k=1时，仿射密码退化为移位替换密码技术。2023/9/320〔2〕单字符多表替换密码技术：单字符多表替换密码技术在平安性方面比单字符单表替换密码技术高。单字符多表替换密码技术是用一系列〔两个以上〕替换表依次对明文的字母进行替换的加密方法。假设明文字母表为Zq，替换表序列为L=L1L2…，明文字母序列为m=m1m2…，那么相应的密文序列为c=L(m)=L1(m1)L2(m2)…。如果替换序列是非周期的无限序列，那么相应的密码技术为非周期多表代替密码技术，它对每个明文都采用了不同的替换表进行加密，也称为一次一密密码技术，它是一种理论上不可破译的密码技术。因为单字符单表替换密码技术中明文的字母与密文中的字母是一一对应的，明文中的字母统计特性在明文中没有得到改变，因此单字符单表替换密码技术很容易破译。

而在实际应用中采用的都是周期多表替换密码技术，只使用了有限的替换表，替换表被重复使用以完成对明文的加密。例如周期为d，那么替换表序列为：L=L1L2…LdL1L2…Ld…。

当d=1时，单字符多表替换密码技术退化为单字符单表替换密码技术。

2023/9/321单字符多表替换密码技术有很多，典型的有：

①Vigenere〔费杰尔或维吉尼亚〕密码技术

定义：设m是一个正整数。设M=C=K=(Z26)m，(Z26m=Z26

Z26

…

Z26表示Z26的m次直积)。对于

k=(k1,k2,…km)

K，定义：加密函数：Ek(x1,x2,…xm)=(x1+k1,…,xm+km)(mod26)解密函数：Dk(y1,y2,…ym)=(y1-k1,…,ym-km)(mod26)

Vigenere密码技术本质上是一种多表简单加法密码技术Vigenere密码技术循环地使用每一个替换表完成明文字母到密文字母的转换。维吉尼亚密码一次加密m个明文字母。2023/9/322mm-具体的加密过程：设密钥K=k1k2…km，明文与密文字母表中均包含了n个字母。又设明文m=m1m2…，密文为c=c1c2…，那么ci=mi+ki〔modn〕，其中m为正整数。当密钥的长度比明文短时，密钥可以周期性地重复使用，直至完成明文中的每个字母的加密。2023/9/323②Vernam〔弗纳姆〕密码技术其加密方法是，将明文和密钥分别表示成二进制序列，再把它们按位进行模二加法。设明文m=m1m2…，密钥k=k1k2…，其中mi，ki∈GF(2)，i≥1，则密文c=c1c2…，其中ci=miki

。这里为模二加法。

③Hill〔希尔〕密码技术它实际上是仿射密码技术的特例。其根本加密思想是将明文分组〔如n个明文字母〕通过线性变换将它们转换为n个密文字母的加密算法。解密时只需做一次逆变换即可。密钥就是变换矩阵。2023/9/3242023/9/325换位密码技术本质上就是一种置换密码技术，但它置换的不是字符，而是书写的位置。换位密码技术的数学表达式可以表示成：设明文为：m=m1m2…，则密文c=c1c2…，ci=，i=1，2，…，n。其中置换表为：

3.换位密码技术Hill密码技术可以较好地抗击统计分析攻击，但在面对明文的攻击就很容易被破译，特别是在密钥矩阵行数的情况下。因此，Hill密码技术并不平安。2023/9/326例子：明文：cryptographyisanappliedscience密钥：encry密文：yripdncohniirgyaeepaspsctpalce2023/9/327为了保护信息的保密性，抗击密码分析，保密系统应当满足下述要求：①系统即使达不到理论上是不可破的，也应当为实际上不可破的。就是说，从截获的密文或某些的明文密文对，要决定密钥或任意明文在计算上是不可行的。②系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原那么。③加密和解密算法适用于所有密钥空间中的元素。④系统便于实现和使用。2023/9/328威胁古典密码平安的因素：频率分析考虑最可能的字母及单词重复结构分析持久性、组织性、创造性和运气明文且易于识别2023/9/329频率分析攻击由于任何自然语言都有自己的统计规律，对于古典密码来说，密文中还保存了明文的统计特征，因此可以使用统计方法〔频率分析〕进行攻击。英文中的统计〔频率〕是有规律的：①每个单字母中E出现频率最高，其次是T、A、O、I、N、SH、R等，V、K、J、X、Q、Z最低。②双字母频率最高的有TH、HE，它们出现的频率小于IN、ER等。③还有THE，ING等其他规律。2023/9/330常见的三字母组合：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH等。常见的双字母组合：TH、HE、IN、ER、RE、AN、ON、EN、AT；2023/9/3312023/9/332频率分析攻击的一般方法：第一步：对密文中出现的各个字母进行出现