Chapter-2-–-经典加密技术

1基本概念密码学(Cryptology):是研究信息系统安全保密的科学.密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.Chapter2–经典加密技术2明文（Plaintext）：消息的初始形式；密文（CypherText）：加密后的形式加密算法(EncryptionAlgorithm):对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm).解密算法(DecryptionAlgorithm):接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)密钥(Key):加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).基本概念3记：明文记为P且P为字符序列，P=[P1,P2,…,Pn]密文记为C,C=[C1,C2,…,Cn]明文和密文之间的变换记为C=E(P)及P=D(C)其中C表示密文，E为加密算法；P为明文，D为解密算法我们要求密码系统满足：P=D(E(P))·需要密钥的加密算法，记为：C=E(K,P),即密文消息同时依赖于初始明文和密钥的值。实际上，E是一组加密算法，而密钥则用于选择其中特定的一个算法。·加密与解密的密钥相同，即：P=D(K,E(K,P))·加密与解密的密钥不同，则：P=D(KD,E(KE,P))4保密内容密钥数量明文处理的方式密码编码系统分类保密内容·受限制的（restricted)算法算法的保密性基于保持算法的秘密·基于密钥（key-based)的算法算法的保密性基于对密钥的保密5对称密码算法（symmetriccipher)•加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个•又称秘密密钥算法或单密钥算法非对称密钥算法（asymmetriccipher)•加密密钥和解密密钥不相同，从一个很难推出另一个•又称公开密钥算法（public-keycipher)•公开密钥算法用一个密钥进行加密,而用另一个进行解密•其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥。解密密钥必须保密,又称私人密钥（privatekey)私钥，简称私钥密钥数量6分组密码（blockcipher)将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher)又称序列密码。序列密码每次加密一位或一字节的明文。明文处理方式72.1对称密码•又名：传统加密/单钥加密/私钥加密•发送方和接收方共享同一个密钥•几乎所有的经典加密算法都是这种类型•在70年代公钥密码体制被发明之前这是唯一的密码类型。（对称密码简化模型见书P16图2.1）8要求•对称密码要安全使用有两个要求:–加密算法足够强–密钥仅为发送者和接受者知道Y=EK(X)X=DK(Y)•加密算法是开放的,大家都知道.所以安全性取决于密钥•有安全的通道发放密钥.92.1.1密码编码学•特征:–所使用的加密运算——代换(替换)/置换–密钥数量——单密钥或私钥/两个密钥或公钥–处理明文的方法——分组/流2.1.2密码分析·试图破译单条消息·试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息·试图找到加密算法中的普遍缺陷（无须截取任何消息）10密码分析的条件与工具已知加密算法截取到明文、密文中已知或推测的数据项数学或统计工具和技术语言特性计算机技巧与运气攻击传统密码方法·密码分析学·穷举攻击11无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法安全性体现在：•破译的成本超过加密信息的价值•破译的时间超过该信息有用的生命周期•满足这两个条件:计算上是安全的更多定义12明文的字母由其它字母或数字或符号代替若该明文被视为一个比特序列，则替代涉及到用密文比特模式代替明文比特模式经典加密技术——替代13Caesar密码•已知最早的代换加密算法•由JuliusCaesar发明•首先用于军事中•Ci=E(Pi)=Pi+3•例子:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB恺撒密码的特点·单字母密码（简单替换技术）·简单，便于记忆·缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构14分析CaesarCipher•仅有26种可能替换–A映射到A,B,..Z•可以循环试验•使用bruteforcesearch•仅仅需要能认识明文即可•例如.解密ciphertext“GCUAVQDTGCM”（见书P27）15单表代换密码•不仅仅将字母移位•对字母进行无规则的重新排列•因此密钥是26字母长•任意替换：26！4x1026可能的key，大于56位DES的密钥空间。•基于语言统计规律仍可破译单表代换密码安全性·共有26!=4x10^26密钥·有这么多密钥应该安全了巴！·!!!WRONG!!!·问题是人类语言的统计特性16语言的冗余特性•人类语言是冗余的•例如thlrdsmshphrdshllntwnt•每个字母被使用的频率不相同•在英语中e是被用的最多的字母•接着是T,R,N,I,O,A,S•其他的字母用的很少•例如.Z,J,K,Q,X•有单个字母，两个字母和三个字母出现的频率表（见书P25）17密码分析学中的应用•单表替换不改变统计特性•由阿拉伯科学家在9世纪发现这个规律•计算密文中每个字母出现的频率•然后与已知的统计特性相比较•对于Caesar密码来说寻找最常出现的和最不常出现的字母–最常出现:A-E-I,NOpair,RSTtriple–最不常出现:JK,X-Z•对于单表替换要确认每个字母的对应关系–可以使用最常出现的那些单个字母，双字母对和三字母对。18解密例子•给定密文:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ•计算每个字母出现的相对频率•猜测P&Z对应eandt•假设ZW是th，因此ZWP就是the•继续试验可以得到下面的明文:itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow19E？---E—E-NEVERN-V-R福尔摩斯密码20Playfair密码•在单表替换中长密钥并没有提供足够的理想的安全性•增强安全性的一个途径是对多个字母组合进行加密•Playfair密码就是这样做的•由CharlesWheatstone在1854发明,但是由他的朋友BaronPlayfair名字命名Playfair密钥矩阵是一个由密钥决定的5X5矩阵：首先填入密钥，矩阵剩余部分填入其他的字母。例如.，使用密钥MONARCHYMONARCHYBDEFGIKLPQSTUVWXZ21Playfair密码的安全性•相对于单表替换密码来说安全性增强了•有26x26=676字母对•需要对676字母对进行分析•因此生成的密文更复杂•被广泛的使用的了很多年(例如.US&BritishmilitaryinWW1)•给定几百个密文就能被破解•因为他还是保留了明文的结构22多表代换密码•另一种增强安全性的方法是使用多表替换•破坏统计特性•使用相关的单表代换规则•用密钥选择决定使用那个代换表维吉尼亚密本加密举例：若我们选用明文为：Vigenereciphere，密钥则选用以上26个字母所组成的任一单词或词组如：radio。见下表：相同字母加密为不同的密文（如字母e）不同的字母加密为相同的密文（如字母H）明文Vigenereciphere密钥radioradioradio密文MIJMBVRHKWGHHZS2324AutokeyCipher•理想情况下密钥和明文一样长•Vigenère建议autokey加密•把密钥放在明文前面然后整体作为密钥•知道了密钥后先对前面几个字母解密•然后用解密结果再进行解密•还是有统计特性存在•例如给定密钥deceptive密钥:deceptivewearediscoveredsav明文:wearediscoveredsaveyourself密文:ZICVTWQNGKZEIIGASXSTSLVVWLA25一次一密•如果每次加密都用与明文一样长的真随机密钥，将是最安全的。•叫做一次一密•这是无法破解的！•原因？？•每个密钥只能用一次。•缺点？？置换密码·现在看看一种新的密码：置换密码·通过调整字母的顺序来保密·没有替换原有的字母26栅栏技术•按照对角线的顺序写入明文•按照行的顺序写出密文•例如.将明文写成:mematrhtgpryetefeteoaat•得到密文MEMATRHTGPRYETEFETEOAAT置换密码一种更复杂的方法，把明文按照给定的列数一行行的写入，然后根据密钥调整列Key:4312567Plaintext:attackpostponeduntiltwoamxyzCiphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ2728乘积密码•由于语言的统计特性使得使用替换或置换进行加密并不安全•可以交替的使用多种加密方式:–两种替换得到更复杂的替换结果–两种置换得到更复杂的置换结果–替换后再进行置换得到的结果相对更复杂！•这种思想是从经典密码到现代密码体制的桥梁！29转子机•在现代密码体制发明前转子机是最常见的乘积密码•二战中广泛使用–GermanEnigma,AlliedHagelin,JapanesePurple•implementedaverycomplex,varyingsubstitutioncipher•usedaseriesofcylinders,eachgivingonesubstitution,whichrotatedandchangedaftereachletterwasencrypted•with3cylindershave263=17576alphabets30隐写术•是加密的一种替代•在消息中隐藏信息–usingonlyasubsetofletters/wordsinalongermessagemarkedinsomeway–usinginvisibleink–hidinginLSBingraphicimageorsoundfile•缺点：–highoverheadtohiderelativelyfewinfobits