1、第二章 信息保密技术2.1 古典密码古典密码2.2 分组加密技术分组加密技术2.3 公约加密技术公约加密技术2.4 流密码技术流密码技术2.5 电子信封技术电子信封技术2.6 信息隐藏技术信息隐藏技术密码学 密码学从应用角度可分为密码编码、密码分析两个分支，分别研究密码的编制和破译问题。密码学：n密码编码学n密码分析学密码系统应用参考模型在对称密码系统中，密钥的管理扮演着非常重要的角色。发送者接收者攻击者安全信道不安全信道消息M消息M密钥K密钥K密文C消息M消息M消息M发送者消息M发送者消息M密钥K发送者消息M密钥K发送者消息M安全信道密钥K发送者消息M密文C安全信道密钥K发送者消息M不安全信
2、道密文C安全信道密钥K发送者消息M不安全信道密文C安全信道密钥K发送者消息M密文C安全信道密钥K发送者消息M不安全信道密文C安全信道密钥K发送者消息M攻击者不安全信道密文C安全信道密钥K发送者消息M攻击者不安全信道密文C安全信道密钥K发送者消息M接收者攻击者不安全信道密文C安全信道密钥K发送者消息M接收者攻击者不安全信道密文C安全信道密钥K发送者消息M密钥K接收者攻击者不安全信道密文C安全信道密钥K发送者消息M消息M密钥K接收者攻击者不安全信道密文C安全信道密钥K发送者消息M2.1 古典密码古典密码 公元6年前的古希腊人使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的
3、信息纵写在上面，接着打开纸送给送信人。如果不知道棍子的宽度（这里作为密钥），不可能解密里面的内容。后来，罗马的军队用凯撒密码进行通信。古典密码是密码学的渊源，可用手工和机械操作来实现加解密，现在已很少采用了。2.1 古典密码古典密码1、代换密码通常，明文和密文由统一字母表构成。n加密时，通常将明文消息划分成长为L的消息单元，称为明文组。nL=1 单字母代换（流密码）将明文空间的元素（如字母、二元数据等）逐个进行加密，这种对明文消息加密的方式称为流密码。nL1 多码代换（分组密码）将明文分成固定长度的组，如64bit一组，用同一密钥 和算法对每一组加密，输出也是固定长度的密文。n根据加密过程中使
4、用代换表数目的多少n单表代换：对所有明文字母都用一种固定代换n 进行加密n多表代换：用一个以上的代换表进行加密n多字母代换单表代换密码单表代换密码（1）移位密码最著名的移位密码是凯撒密码。例：取k=3，明文字母和密文字母的对应关系为明文：abcdefghijklmnopqrstuvwxyz密文：DEFGHIJKLMNOPQRSTUVWXYZABC明文m=“caser cipher is a shift substitution”所对应的密文为c=“FDVHU FLSHU LV D VKLIW VXEVWLWXWLRO”单表代换密码单表代换密码补充：ROT13密码n建立在UNIX系统上的简单的加
5、密程序n在这种密码中，A被N代替，B被O代替，每一个字母是环移13所对应的字母。n用ROT13加密文件两遍便恢复出原始文件：P=ROT13(ROT13(P)nROT13并非为保密设计，它经常用在英特网电子邮件中隐藏特定的内容，以避免泄露一个难题的解答等。单表代换密码 wfeazw为密钥 排列后有26*25*24*1种选择，所以密钥有26！种，太复杂，不容易记忆。因此实际中密钥句子常被使用，密钥句子中的字母被依次填入密文字母表（重复的字母只用一次），没用的字母按自然顺序排列举例在后一页a b cx y zw f ea z w有26种选择有25种选择有24种选择(2)替换密码=a b cx y z
6、w f ea z w=有26种选择a b cx y zw f ea z w=有25种选择有26种选择a b cx y zw f ea z w=有24种选择有25种选择有26种选择a b cx y zw f ea z w=单表代换密码替换密码 P24例：密钥句子为studentteacherabcdefghijklmnopqrstuvwxyzstudenachrklmnopqrstuvwxyz 密钥 明文 I love you密文 h love you单表代换密码(3)仿射密码 y=ax+b(mod 26)a,bZ26 当a=1时，仿射密码移位密码 如果解密是可能的，必须要求仿射函数是双射的：对
7、任何y Z26,方程ax+by(mod 26)有唯一解。由数论可知，当且仅当gcd(a,26)=1,对每个y有唯一解。对于aZ26，gcd(a,26)=1的a只有12种选择，对于参数b没有要求，所以仿射密码有12*26种可能的密钥。因为：。多表代换密码n多表代换：以一系列（两个以上）代换表依次 对明文消息的字母进行代换的加密方法。n一次一密：对每个明文字母都采用不同的代换表 或密钥进行加密，称为一次一密密码 （理论上唯一不可破的密码）n周期多表代换：代换表个数有限，重复使用。实际应用中采用，例如维吉尼亚密码维吉尼亚密码（Vigenere密码）利用Vigenere表格进行加密，加密方法如下：n给
8、定一个单钥字母x和一个明文字母y，密文字母则在表格中x行y列的交叉点；n例如，明文为：we are discovered save yourself,若取单密钥为v，则加密时从密钥v开始，对应每个明文字母顺序向下取密钥，结果如下：明文：wearediscoveredsaveyourself密钥：vxyzabcdefghijklmnopqrstuv 密文：RAAPDDJUFSAKYMMCLHRMEKIKXFAn也可选取一个关键词重复成与明文同样长度作为密钥进行加密。若取关键词为deceptive，加密结果如下：明文：wearediscoveredsaveyourself密钥：deceptived
9、eceptivedeceptive 密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJVigenere密码的强度在于对每个明文字母有多个密文字密码的强度在于对每个明文字母有多个密文字母对应，因此该字母的频率信息是模糊的。母对应，因此该字母的频率信息是模糊的。Vigenere密码表格ABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABC
10、DEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHIKLMNOPQRSTUVWXYZABCDEFGHIJLMNOPQRSTUVWXYZABCDEFGHIJKMNOPQRSTUVWXYZABCDEFGHIJKLNOPQRSTUVWXYZABCDEFGHIJKLMOPQRSTUVWXYZABCDEFGHIJKLMNPQRSTUVWXYZABCDEFGHIJKLMNOQRSTUVWXYZABCDEFGHIJKLMNOPRSTUVWXYZABC
11、DEFGHIJKLMNOPQSTUVWXYZABCDEFGHIJKLMNOPQRTUVWXYZABCDEFGHIJKLMNOPQRSUVWXYZABCDEFGHIJKLMNOPQRSTVWXYZABCDEFGHIJKLMNOPQRSTUWXYZABCDEFGHIJKLMNOPQRSTUVXYZABCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWXZABCDEFGHIJKLMNOPQRSTUVWXY设密钥为 K，用多字母代换（L=2）对“love”进行加密。Xzda 每次对L1个字母进行代换。容易隐蔽和均匀化字母的自然频率，从而有利于抗统计分析明文x=
12、(x1,x2),密文y=(y1,y2)Y1=11x1+3x2Y2=8x1+7x211 83 7k=简记为y=xK，K为密钥线性代数：可用K-1来解密，x=yk-111 83 712 16=24X 26Z7 1823 11=11 83 7-111 83 722 5=4 d 1a11 83 7X1 x2=y1 y2练习设密钥为 ，用多字母代换（L=2）对“love”进行加密11 83 7k=设密钥为 ，用多字母代换（L=2）对“love”进行加密。xzwcLo12 16 x z11 83 712 16=24 26ve22 5 w c11 83 722 5=23 3多字母代换密码当m=1时，退化成单
13、字母仿射代换函数 y=ax当m=2时，如前例当m=3时，例如Hill密码 希尔密码当m3时，计算K-1没有有效的方法，所以大大限制了多字母代换密码 的广泛应用。Hill密码Hill密码Hill密码也是一种多字母替代密码，它由数学家Lester Hill于1929年研制成功。加密方法用向量或矩阵表示为C1C2C3K11 K12 K13K21 K22 K23K31 K32 K33P1P2P3=C1C2C3=K11 K12 K13K21 K22 K23K31 K32 K33C1C2C3=P1P2P3K11 K12 K13K21 K22 K23K31 K32 K33C1C2C3=或 C=KP 其中，C
14、和P是长度为3的列向量，分别表示密文和明文，K是3*3矩阵，表示加密密钥，加密操作要执行模26运算。11 83 7X1 x2=y1 y2例如，如果使用的加密密钥是K=17 17 521 18 21 2 2 19欲对明文pay more money进行加密，则现将明文按三个字母一组分组（不足三个时补字母x），然后每组字母求密文。该明文的前三个字母表示为pay=(15 0 24)，计算密文的过程如下 (15 0 24)K=(375 819 486)mod 26=(11 13 18)=LNS以此类推，可得密文为。?解密时使用逆矩阵K-1=对密文(11 13 18)T做运算K-1(11 13 18)T
15、 mod 26=(431 494 570)T=(15 0 24)T=pay Hill密码的强度在于完全隐藏了单字母的频率。LNS HDL EWM TRW2.1 古典密码古典密码 2、置换密码（换位密码）不改变明文字母，但通过重排而更改它们的位置。例如：矩阵变换密码、纵行换位密码矩阵变换加密:将明文中的字母按给定顺序安排在1个矩阵中，然后用另一种顺序选中矩阵的字母来产生密文，一般为列变换次序。如原列次序为1234，先列次序为2413矩阵变换加密给定一个置换：f=，根据给定的次序，按526413的列序重新排列，得到所以密文是 oerwntc ueks i yrt.解密过程正好相反，按序排列密文后，
16、通过列置换，再按行读取数据即可。123456526413如将明文network security按行排列在3*6矩阵中，如下所示：1 2 3 4 5 6n e t w o r k s e c u r i t y 5 2 6 4 1 3o e r w n tc u e k s i y r t纵行换位密码明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出。解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。Plaintext：COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE COMPUTERGR (10个为一组)APHICSMAY
17、B ESLOWBUTAT LEASTITSEX PENSIVECiphertext:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX换位密码对存储的要求很大，有时还要求特定的长度，因而比较麻烦，换位密码对存储的要求很大，有时还要求特定的长度，因而比较麻烦，因此代替密码（代换密码）较为常用。因此代替密码（代换密码）较为常用。破译Kerckhoff假设：攻击方知道所用的密码系统目标：设计一个在Kerckhoff假设下达到的安全系统移位密码极易破解，仅统计出最高频度字母再与明文字母表对应决定出位移量，就差不多得到正确解了。安全密码系统的一个必要条件必要条
18、件是密钥的空间必须足够大，使得穷举密钥搜索破译是不可能的。（非充分条件）2.2 分组加密技术2.2.1基本概念分组加密技术属于对称密码体制的范畴；分组密码的工作方式是将明文分成固定长度的组，如64bit为一组，用同一密钥和算法对每一组加密，输出也是固定长度的密文。n例如DES密码算法的输入为64bit，密钥长度为56bit，密文长度为64bit。设计分组密码算法的核心技术是：在相信复杂函数可以通过简单函数迭代若干次得到的原则下，利用简单圈函数等运算，充分利用非线性运算。n以DES算法为例，它采用美国国家安全的局设计的8个S-Box和P-置换，经过16圈迭代，最终产生64bit密文，每圈迭代使用
19、的48bit子密钥是由原始的56bit产生的。2.2 分组加密技术2.2.1标准算法的介绍nDES算法n国际数据加密算法IDEAnASE算法2.2 分组加密技术2.2.3分组密码的分析方法n完全可破译密码破译者可以确定该密码正在使用的密钥，则他可以象合法用户一样阅读所有的消息。（对于非对称密码，知道私钥）n部分可破译密码破译者仅能从所窃取的密文中恢复明文，却发现不了密钥。2.2 分组加密技术2.2.3分组密码的分析方法分组密码的攻击可分以下几类：n唯密文攻击n已知明文攻击n选择明文攻击n选择密文攻击2.3 公钥加密技术2.3.1 基本概念 一个加密系统的加密密钥和解密密钥是不一样的，不能又一个
20、推出另一个。公钥用于加密（公开的），私钥用于解密（保密的）。B的公钥用户A密文C非对称密码算法信息MB的私钥用户B信息M密文C非对称密码算法公开信道用户A信息M用户A信息M用户A非对称密码算法信息M用户A非对称密码算法信息M用户AB的公钥非对称密码算法信息M用户AB的公钥非对称密码算法信息M用户A密文CB的公钥非对称密码算法信息M用户A密文CB的公钥非对称密码算法信息M用户A公开信道密文CB的公钥非对称密码算法信息M用户A公开信道密文CB的公钥非对称密码算法信息M用户A密文C公开信道密文CB的公钥非对称密码算法信息M用户A密文C公开信道密文CB的公钥非对称密码算法信息M用户A非对称密码算法密文
21、C公开信道密文CB的公钥非对称密码算法信息M用户A解决了对称密码体制中的密钥管理难题，满足了开放系统的要求。解决了对称密码体制中的密钥管理难题，满足了开放系统的要求。2.3 公钥加密技术公钥加密技术的核心：运用了一种特殊的数学函数-单向陷门函数。Y=f(x)x=f-1(y)单向陷门函数:从一个方向求值是容易的，但其逆向计算却很困难。2.3 公钥加密技术定义1 设f是一个函数，如果对于任意给定的x，计算y，使得y=f(x)是容易计算的，但对于任意给定的y，计算x，使得x=f-1(y)是难解的。即求f的逆函数是难解的。称f是一个单向函数。定义2 设f是一个函数，t是与f有关的一个参数。对于任意给定
22、的x，计算y，使得y=f(x)是容易计算的。如果当不知道参数t时，求f的逆函数是难解的，但当知道参数t时，求f的逆函数是容易的。称f是一个单向陷门函数。参数t称为陷门。在公钥加密算法中，加密变换就是一个单向陷门函数，知道陷门的人很容易进行解密变换，而不知道陷门的人则无法有效地进行解密变换2.3 公钥加密技术数学难题-n不存在一个计算该问题的有效方法；n目前、以后足够时间内，求逆函数在计算上不可行时间长度难以忍受。绝对安全的密码经常给密钥管理带来非常大的压力。现在主流的编码思想是寻找密钥管理简单，且破译者利用现有资源无法在预定时间内破译的密码编码方法，这就是计算上安全的密码。根据单向陷门函数的思
23、想，学者们提出许多公钥加密的方法，都是基于复杂数学难题的。根据基于的数学难题，至少有以下三类系统目前被认为是安全和有效的：n大整数因子分解系统（代表性的有RSA）n椭圆曲线离散对数系统（ECC）n离散对数系统（代表性的有DSA）2.3 公钥加密技术2.3.2 RSA公钥密码算法RSA的安全性建立在两大数论难题上大数分解素性检测即：将两个大数相乘在计算上很容易实现，但将该乘积分解成两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。算法见教材 P45RSA公钥密码算法1、gcd函数：求最大公因数 例如 gcd(7,17)=1 gcd(16,12)=4 gcd(e,(n)=1表示e
24、和(n)互素，即最大公因数为12、欧拉函数(n)n(n)表示不超过n且与n互素的整数个数;n易证明当n=pq，p和q为不同的素数时，(pq)=(p-1)(q-1)例：求(15)小于15，且与15互素的整数个数 1,2,4,7,8,11,13,14 共有8个 (15)=8练习 求(35)提示：35=5*7，且5和7是素数 RSA公钥密码算法例 构造一个RSA算法如下：(1)选择两个素数 p=7 q=17(2)计算n=p*q=7*17=119(3)计算(n)=(7-1)(17-1)=96(4)选择一个e，它与(n)互素 5与96互素，e=5 e的选取很容易，所有大于的选取很容易，所有大于p和和q的
25、质数都可用的质数都可用(5)求出d，它小于(n)，且(d*e)mod 96=1 77*5=4*96+1 d=77 (6)公钥 Kp=5，119，私钥Ks=77，119RSA公钥密码算法公钥 Kp=5，119，私钥Ks=77，119假设明文m=19加密时，195(mod119)=66 得到密文C=66 解密时 6677(mod119)=19 得到明文m=19若从公钥Kp=5，119得到私钥，难点转换为分解5，119中的119为两个素数pq7*17求出素数，则可以得到(119)，就可以算出e，进而得到d.公钥公钥e,pq,私钥私钥d,pq练习：构造一个RSA算法，p=3，q=52.3 公钥加密技术
26、 公钥加密也允许采用这样的方式对加密信息进行签名，以便接受方能确定签名不是伪造的。假设A和B希望通过公开密钥加密方法进行数据传递，A和B分别公开加密算法也相应的密钥，但不公开解密算法和相应的密钥。A和B的加密算法分别是EA和EB，解密算法分别是DA和DB。EA和DA互逆，EB和DB互逆。若A要向B发送明文P，不是简单地发送EB(P),而是先对P施以其解密算法DA，在用加密算法EB对结果加密后发送出去，密文C为：C=EB(DA(P)B收到C后，先施以DB,再施以加密算法EA，得到明文P：P=EA(DB(C)=EA(DB(EB(DA(P)=EA(DA(P)/*DB与EB相互抵消*/=P /*DA与
27、EA相互抵消*/这样，B就确定报文是A发出的，因为只有加密过程利用了DA，用EA解密才能获得P，只有A才知道DA，没有人（包括B）可以伪造A的签名）2.3 公钥加密技术RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作，是被研究得最广的公钥算法。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。为了保证RSA的安全，就目前的需要，n的长度为1024-2048bit是比较合理的。除了指定n的大小外，为避免选取容易分解的整数n，还应该注意以下问题：nP和q的长度相差不能太多nP-1和q-1都应该包含大的素因子nP-1和q-1的最大公因子要尽可能小2.3 公钥加密技术2.3.3 ElGamal算法2.3.4 椭圆曲线算法2.4 流密码技术
