第2章密码学基础分析解析

《信息系统安全》第2章密码学基础2.1密码学基础知识2.2古典替换密码2.3对称密钥密码2.4公开密钥密码2.5消息认证《信息系统安全》密码的起源•古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。•古希腊的斯巴达人曾将军事情报刻在普通的木板上，用石蜡填平，收信的一方只要用火烤热木板，融化石蜡后，就可以看到密信。《信息系统安全》•密码学用于通信的另一个记录是斯巴达人于公元前400年应用锥形指挥棒在军官间传递秘密信息。《信息系统安全》我国古代的藏头诗、藏尾诗、漏格诗•《水浒传》“吴用智赚玉麒麟”一回中的诗卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。•明代怪杰徐文长：平湖一色万顷秋，湖光渺渺水长流。秋月圆圆世间少，月好四时最宜秋。《信息系统安全》•王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。•王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。《信息系统安全》密码学应用例子•在1962年的古巴导弹危机中,苏美剑拔弩张,形势严峻。据悉，美国人心生一计，故意用能被苏联截收、破译的密码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁晓夫。•1994年,美国的情报机构通过截获国际电讯得知，法国与沙特阿拉伯正在进行一笔数亿美元的军火交易，美国先行一步从法国人手中抢下了这笔大生意。《信息系统安全》2.1密码学基础知识2.1.1引言密码学（Cryptology）是研究密码编制、密码破译和密钥管理的一门综合性应用科学。+密码编码学（Cryptography）密码分析学（Cryptanalytics）《信息系统安全》伪装信息，使未授权者不能理解它的真实含义。所谓伪装就是对信息进行一组可逆的数学变换。伪装前的原始信息称为明文（PlainText）,伪装后的信息称为密文（CipherText），伪装的过程称为加密（Encrypt）。去掉伪装还原明文的过程称为解密（Decrypt）。加密在加密密钥（Key）的控制下进行。解密在解密密钥的控制下进行。用于对数据加密的一组数学变换称为加密算法。用于对密文解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。密码的基本思想《信息系统安全》•明文（plaintext)：信息的原始形式，一般是信息的基本单元（字母、数字或符号等）的有限排列；•密文（cipher)：明文经过加密以后的结果形式•加密变换(encryption)：从明文到密文的变换过程•解密变换(decryption)：从密文还原成明文的过程•加密算法：对明文进行加密时采用的一组规则。•解密算法：对密文进行解密时采用的一组规则。•密钥（key)：用于加解密变换的关键信息，视其用于加解密而分别称为加密密钥与解密密钥；《信息系统安全》2.1.2密码体制加密函数E作用于明文M得到密文C，用数学表示为：E（M）=C.相反地，解密函数D作用于C产生MD（C）=M.先加密后再解密消息，原始的明文将恢复出来，下面的等式必须成立：D（E（M））=M《信息系统安全》明文明文加密算法解密算法信道CMMC攻击者加密钥解密钥密钥K＝Ke,KdKeKd《信息系统安全》2.1.3密码分类（1）古典密码密码学还不是科学,而是艺术出现一些密码算法和加密设备简单的密码分析手段出现主要特点：数据的安全基于算法的保密古典密码的加密方法一般是代换与置换，使用手工或机械变换的方式实现。《信息系统安全》•古典密码的代表密码体制主要有：–单表代替密码：Caesar密码；–多表代替密码：Playfair密码、Hill密码、Vigenere密码；–转轮密码：著名的Enigma密码，第二次世界大战中使用过。（1）古典密码《信息系统安全》20世纪早期的密码机《信息系统安全》2.1.3密码分类（2）对称密钥密码传统密码/常规密码/私钥密码/单钥密码发送方和接收方共享一个共同的密钥所有的传统密码算法都是私钥密码20世纪70年代以前私钥密码是唯一类型至今仍广泛应用对称密钥密码指加密过程和解密过程使用同一个密钥来完成。《信息系统安全》对称密钥密码模型《信息系统安全》•按照加密方式不同，对称密钥密码体制被分为–流密码（StreamCipher）（或称序列密码）–分组密码（BlockCipher）–区别是：流密码是将明文消息按字符逐位加密；分组密码是将明文消息先进行分组，再逐组加密。《信息系统安全》常用的密码分析攻击种类已知：C1=EK（P1），C2=EK（P2），，CI=EK（Pi）推导出：P1，P2，，Pi；K或找出一个算法从Ci+1=EK（Pi+1）推出Pi+1（1）唯密文攻击密码分析者有一些都用同一加密算法加密的密文，密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。《信息系统安全》（2）已知明文攻击密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），，Pi，Ci=Ek（Pi）推导出：密钥k，或从Ci+1=Ek（Pi+1）推出Pi+1的算法。《信息系统安全》（3）选择明文攻击分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），，Pi，Ci=Ek（Pi）其中P1，P2，，Pi是由密码分析者选择的。推导出：密钥k，或从Ci+1=Ek（Pi+1）推出Pi+1的算法。《信息系统安全》（4）自适应选择明文攻击这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加了密的明文。而在自适应选择密文攻击中，他可选取较小的明文块，然后再基于第一块的结果选择另一明文块，以此类推。《信息系统安全》（5）选择密文攻击密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。（6）选择密钥攻击这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。这种方法有点奇特和晦涩，不是很实际，在此不作介绍。《信息系统安全》2.2古典替换密码2.2.1简单代替密码代替密码就是明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。简单代替密码就是明文的一个字符用相应的一个密文字符代替。《信息系统安全》（1）移位密码“恺撒密码”据传是古罗马恺撒大帝用来保护重要军情的加密系统。它是一种替代密码，通过将字母按顺序推后起3位起到加密作用，如将字母A换作字母D，将字母B换作字母E。据说恺撒是率先使用加密函的古代将领之一，因此这种加密方法被称为恺撒密码。假如有这样一条指令：RETURNTOROME用恺撒密码加密后就成为：UHWXUAWRURPH《信息系统安全》•替代密码(substitutioncipher)的原理可用一个例子来说明。abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesarcipherFDHVDUFLSKHU明文密文明文a变成了密文D《信息系统安全》（2）乘数密码乘数密码的加密变换为Ek(m)=k*mmodq,gcd(k,q)=1这种密码也称采样密码，是将明文字母表按序号每隔k位取出一个字母排列而成密文（字母表首尾相连）。显然，当(k,q)=1，即k与q互素时才是一一对应的。《信息系统安全》为什么必须互素？素数也叫质数。一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除的数。若N个整数的最大公因数是1，则称这N个整数互质。例如8,10的最大公因数是2，不是1，因此不是整数互质。7,10,13的最大公因数是1，因此这是整数互质，也称为互素。《信息系统安全》Ek(m)=k*mmodq,gcd(k,q)=1以英文字母为例q为26，假设k=130=13*2mod26=13*4mod26=……m可以为任何2的倍数，导致无法解密为什么必须互素？《信息系统安全》选k=9，则由明文密文字母对应表明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文：AJSBKTCLUDMVENWFOXGPYHQZIR于是对明文：Multiplicativercipher有密文：EYVPUFVUSAPUHKSUFLKX。《信息系统安全》（3）仿射密码加法和乘法相结合，移位密码和乘数密码的结合。Ek(m)=(k1m+k2)modq其中，(k1,q)=1,以［k1,k2］表示密钥。当k2=0时就得到乘数密码，当k1=1时就得到位移密码，q=26时可能的密钥数为26×12-1=311个。k1取值范围（1，3，5，7，9，11，15，17，19，21，23，25）《信息系统安全》（4）基于统计的密码分析简单代替密码由于使用从明文到密文的单一映射，所以明文字母的单字母出现频率分布与密文中相同，可以很容易地通过使用字母频率分析法进行只有密文的攻击。《信息系统安全》2.2.2多表代替密码多表代替密码是一系列（两个以上）代换表依次对明文信息的字母进行代换的加密方法。令明文字母表为Zq，令π=(π1,π2,…)为代换序列，明文字母序列为m=m1,m2,…,则相应的密文字母序列为c=Ek(m)=π(m)=π1(m),π2(m),…，若π为非周期的无限序列，则相应的密码为非周期多表代换密码，否则，为周期多表代换密码。一次一密密码《信息系统安全》维吉尼亚是法国的密码专家，以他的名字命名的维吉尼亚密码加密算法是多表密码的典型代表。代表：Vigenère密码维吉尼亚密码•加密方式一：数学公式计算–设明文P=p1p2…pn，密钥k=k1k2…kn，密文C=c1c2…cn•加密：ci=pi+ki(mod26)，=1，2，…，n；–说明：若明文长度大于n，则k重复使用。《信息系统安全》•加密方式二：查表法（密钥k，明文P）——密文C34《信息系统安全》Vigenère密码例子•加密过程：–P＝“encodeanddecode”，k＝“mykey”字母序号encodeanddecode明文编码P=4132143401333421434密钥编码k=122410424122410424122410424加密C=1637121827162423727162624728模运算111102密文C=QLMSBQYXHBQAYHC35《信息系统安全》Vigenère密码例子•解密过程：–C＝“QLMSBQYXHBQAYHC”，k＝“mykey”字母序号123456789101112131415密文编码C=161112181162423711602472密钥编码k=122410424122410424122410424加密C=4-13214-2340133-234-24143-22模运算133324密文解码C=encodeanddecode36《信息系统安全》Vigenère密码的安全性强度在于：每个明文字母对应着多个密文字母，明、密文字母不是一一对应关系字母的统计规律进一步降低Vigenère本人建议：密钥与明文一样长Vigenère代换表中的每一行就是一Caesar密码37《信息系统安全》Vigenère密码分析•攻击：–首先作单表代换假设，用频率分析方法–然后猜测Vigenère密钥关键字长度•密钥