信息论与编码 第7章 密码体制的安全性测度

第1章：概述第2章：信源熵第3章：信道容量第4章：信息率失真函数第5章：信源编码第6章：信道编码第7章：密码体制的安全性测度§7.1密码基本知识§7.2古典密码体制§7.3现代密码体制§7.4密码体制的安全性测度重要事件向科学轨道。1949年，香农发表了著名论文“密码体制的通信理论”。将密码推密码发展：手工密码简单器械密码机械密码机电密码电子密码现代分组密码公钥密码密码学密码编码学密码分析是破译密码的科学和技术是密码体制的设计学保密通信系统模型：图7.1.1明文空间P：全体明文的集合密文空间C：全体密文的集合密钥空间K：全体密钥的集合也可以用数学方式描述：123图7.1.1解密算法D：解密密钥控制的解密变换的集合加密算法E：4加密密钥控制的加密变换的集合5安全概念无条件安全计算安全密码分析攻击有6类惟密文攻击已知明文攻击选择明文攻击自适应选择明文攻击选择密文攻击选择密钥攻击分析方法数学方法边信道攻击数学方法穷举搜索统计分析逆向推理线性分析差分分析相关分析边信道攻击时间攻击能量攻击电磁攻击故障攻击§7.1密码基本知识§7.2古典密码体制§7.3现代密码体制§7.4密码体制的安全性测度加密基本思想代替换位单表密码凯撒密码密钥词组密码乘法密码仿射密码随机代替表7.2.1凯撒密码明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC1．凯撒密码【例7.2.1】明文：thisisabook密文：WKLVLVDERRN该算法表示为()(3)(mod26)kcEpp（7.2.1）c代表密文，p代表明文设密钥为TIME【例7.2.2】2．密钥词组密码明文abcdefghijklm密文TIMEABCDFGHJKnopqrstuvwxyzLNOPQRSUVWXYZ如果明文为code，则密文为MNEA明文密文多表密码普莱费尔密码维吉尼亚密码希尔密码博福特密码【例7.2.5】密钥是monarchy，则构造的字母矩阵如图7.2.1所示MONARCHYBDEFGI/JKLPQSTUVWXZ图7.2.1字母矩阵表1．普莱费尔密码加密算法：cipi+ki(mod26)（7.2.2）解密算法：piciki(mod26)（7.2.3）2．维吉尼亚密码该密码算法取m个连续的明文字母，并用m个密文字母代替若m3，该系统可以描述为1111122133(mod26)ckpkpkp（7.2.4）2211222233(mod26)ckpkpkp（7.2.5）3．希尔密码3311322333(mod26)ckpkpkp（7.2.6）这可以用列向量和矩阵表示为:123ccc111213212223313233kkkkkkkkk123ppp（7.2.7）或CKP（mod26）（7.2.8）例如考虑明文为keyworder，使用的加密密钥为:K61187145101621该明文的前三个字母被表示为向量（10424），运算结果为KMS换位密码【例7.2.8】明文为cryptographyisanappliedscience假设密钥是creny将明文按照密钥的长度逐行列出，如图7.2.3所示密钥14235cryptographyisanappliedscience图7.2.3换位表然后依照密钥决定的次序按列依次读出因此，密文为COHNIIYRIPDNPASPSCRGYAEETPALCE§7.1密码基本知识§7.2古典密码体制§7.3现代密码体制§7.4密码体制的安全性测度现代密码体制对称密码体制非对称密码体制消息摘要技术1.对称密码图7.3.1对称密码模型发送方通过加密算法根据输入的消息P和密钥K生成密文12[,,,]NCccc即()KCEP（7.3.1）接收方通过解密算法根据输入的密文C和密钥K恢复明文12[,,,]MPppp即()KPEC（7.3.2）1.1数据加密标准（DES）算法图7.3.2DES算法初始置换IP64位明文乘积变换末置换IP-1密钥产生64位密文64位明文L1=R0R0L0R1=L0⊕f(R0,K1)L15=R14L16=R15L2=R1R2=L1⊕f(R1,K2)R16=L15⊕f(R15,K16)R15=L14⊕f(R14,K15)64位密文+f+f+f初始置换IPIP-1k1k2k16图7.3.3DES加密过程图7.3.4一轮迭代的过程P盒换位1.23DES三重DES方法需要执行三次常规的DES加密步骤，但最常用的三重DES算法中仅仅用两个56位DES密钥1.3IDEAIDEA的密钥长度128位在目前技术条件下具有足够的安全强度是一种迭代分组加密算法分组长度64位，8轮迭代，还有一轮输出变换2.非对称密码公钥密码体制的提出图7.3.5非对称密码模型公钥密码体制的基本原理公钥密码体制加密的算法是基于单向陷门函数单向陷门函数是满足下列条件的函数f：给定x，计算yf(x)是容易的；给定y，计算x使y是困难的，即计算上相当花时间，已无实际意义；12)(1xf存在，已知时，对给定的任何y，若相应的x存在，则计算x使yf(x)是容易的。满足上述3个条件可实现公钥密码体制。3加密:()pKmCCEm（7.3.3）解密():()pssKKKEmCmmDCD（7.3.4）例如Alice欲发送信息给Bob，则保密通信为AliceBob()pKbCEm（7.3.5）Bob()()pssKKbKbEmDCDm（7.3.6）用公钥密码实现数字签名时，操作顺序与加密相反Alice向大家出示签名：Alice→ALL()sKaSDm（7.3.7）ALL()()sppKaKaKaDmESEm（7.3.8）RSA公钥密码体制RSA加密时，cme（modn）（7.3.9）RSA解密时，mcd（modn）（7.3.10）【例7.3.1】选p7，q17，计算RSA参数。则npq119，且(n)(p1)(q1)61696。取e5，则d77(577385496＋11mod96)公钥Kp（5，119），私钥Ks（77，7，17）m19进行加密，则cme(modn)195(mod119)66(mod119)接收者收到密文c66后，对其进行解密；mcd(modn)6677(mod119)19(mod119)§7.1密码基本知识§7.2古典密码体制§7.3现代密码体制§7.4密码体制的安全性测度1.完善保密性提取关于明文的信息：(;)()(/)IPCHPHPC(7.4.1)或从密文中提取密钥信息：(;)()(/)IKCHKHKC(7.4.2)(/)0HPCK(7.4.3)于是(;)()(/)()IPCKHPHPCKHP(7.4.4)(;)0IPC(7.4.9)当密钥空间大于明文空间，即()≥()HKHP(7.4.10)2.唯一解距离设给定N长密文序列12,,,NNCcccY其中Y为密文字母表根据条件熵的性质12112/,,,≤/,,,NNHKcccHKccc(7.4.11)随着N的增大，密钥疑义度减小。亦即截获的密文越多，从中提取的关于密钥的信息就越多。当疑义度减小到零，即(/)0HKC时(;)()(/)()IKCHKHKCHK(7.4.12)密钥被完全确定，从而实现破译。如果00()IHHP(7.4.13)代表明文信息变差，其中()HP和0H分别代表明文熵和明文最大熵，可以证明，唯一解距离00()HKVI(7.4.14)