第二章密码技术简介

第二章密码技术简介 someslidesbyLawrieBrown 一 现代密码学基本概念 1949仙农 保密系统的通信理论 1976Diffie和Hellman 密码学新方向 W DiffieandM E Hellman NewDirectrionsinCryptography IEEETransactiononInformationTheory V IT 22 No 6 Nov1976 PP 644 6541977美国公布实施 数据加密标准DES 一 基本知识术语 密码学密码编码学密码分析学明文密文算法密钥加密解密破译 plaintext theoriginalmessageciphertext thecodedmessagecipher algorithmfortransformingplaintexttociphertextkey infousedincipherknownonlytosender receiverencipher encrypt convertingplaintexttociphertextdecipher decrypt recoveringciphertextfromplaintextcryptography studyofencryptionprinciples methodscryptanalysis codebreaking thestudyofprinciples methodsofdecipheringciphertextwithoutknowingkeycryptology thefieldofbothcryptographyandcryptanalysis 密码通信系统模型 密码体制 它是一个五元组 M C K E D 满足条件 1 M是可能明文的有限集 明文空间 2 C是可能密文的有限集 密文空间 3 K是一切可能密钥构成的有限集 密钥空间 4 任意k K 有一个加密算法和相应的解密算法 使得和分别为加密解密函数 满足dk ek m m 这里m M 注 1 Alice要将明文M在不安全信道上发给Bob 设M m1m2 mn 其中mi M Alice用加密算法Ek作ci ek mi 1 i n结果的密文是C c1c2 cn 在信道上发送 Bob收到后解密 mi dk ci 得到明文M m1m2 mn2 加密函数ek必须是单射函数 就是一对一的函数 3 若M C 则ek为一个置换 4 好的密钥算法是唯密钥而保密的 5 若Alice和Bob在一次通信中使用相同的密钥 那么这个加密体制为对称的 否则称为非对称的 SymmetricCipherModel Requirements tworequirementsforsecureuseofsymmetricencryption astrongencryptionalgorithmasecretkeyknownonlytosender receiverY EK X X DK Y assumeencryptionalgorithmisknownimpliesasecurechanneltodistributekey Algorithm Key WHICHSHOUDBESECRET SecuritydependsonthesecrecyoftheAlgorithmnotthesecrecyoftheKeyBecause Cryptography cancharacterizeby typeofencryptionoperationsusedsubstitution transposition productnumberofkeysusedsingle keyorprivate two keyorpublicwayinwhichplaintextisprocessedblock stream 古典密码 古典密码 以字符为基本加密单元现代密码 以信息块为基本加密单元置换代换移位代换乘数密码线形同余密码 单表代换多表代换 1 置换密码 nowconsiderclassicaltranspositionorpermutationciphersthesehidethemessagebyrearrangingtheletterorderwithoutalteringtheactuallettersusedcanrecognisethesesincehavethesamefrequencydistributionastheoriginaltext RailFencecipher writemessagelettersoutdiagonallyoveranumberofrowsthenreadoffcipherrowbyroweg writemessageoutas mematrhpryetefeteatgivingciphertextMEMATRHTGPRYETEFETEOAATPlaintext meetmeafterparty 藏头诗 徐文长七言绝句 平湖一色万顷秋 湖光渺渺水长流 秋月圆圆世间少 月好四时最宜秋 RowTranspositionCiphers amorecomplexschemewritelettersofmessageoutinrowsoveraspecifiednumberofcolumnsthenreorderthecolumnsaccordingtosomekeybeforereadingofftherowsKey 3421567Plaintext attackpostponeduntiltwoamxyzCiphertext TTNAAPTMTSUOAODWCOIXKNLYPETZ 2 经典代换密码 wherelettersofplaintextarereplacedbyotherlettersorbynumbersorsymbolsorifplaintextisviewedasasequenceofbits thensubstitutioninvolvesreplacingplaintextbitpatternswithciphertextbitpatterns 凯撒密码 earliestknownsubstitutioncipherbyJuliusCaesarfirstattesteduseinmilitaryaffairs 高卢 replaceseachletterby3rdletteronexample meetmeafterthepartyPHHWPHDIWHUWKHSDUWB 1 移位代换 加法代换 candefinetransformationas abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCmathematicallygiveeachletteranumberabcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425thenhaveCaesarcipheras C Ek m m k mod 26 m Dk C C k mod 26 2 乘法代换 C Ek m mkmod 26 m Dk C Ck 1mod 26 eg 7 3mod 26 217 1 mod26 15 for7 15mod 26 121 15mod 26 3 3 线性同余 仿射 密码C Ek m mk1 k0 mod 26 例子 设k 7 3 注意到7 1 mod26 15 加密函数是ek x 7x 3 相应的解密函数是dk y 15 y 3 15y 19 易见dk ek x dk 7x 3 15 7x 3 19 x 45 19 x mod26 若加密明文 hot 首先转换字母h o t成为数字7 14 19 然后加密 解密 多表代换 维吉尼亚密码 simplestpolyalphabeticsubstitutioncipheristheVigen reCiphereffectivelymultiplecaesarcipherskeyismultipleletterslongK k1k2 kdithletterspecifiesithalphabettouseuseeachalphabetinturnrepeatfromstartafterdlettersinmessagedecryptionsimplyworksinreverse Example writetheplaintextoutwritethekeywordrepeatedaboveituseeachkeyletterasacaesarcipherkeyencryptthecorrespondingplaintextletteregusingkeyworddeceptivekey deceptivedeceptivedeceptiveplaintext wearediscoveredsaveyourselfciphertext ZICVTWQNGRZGVTWAVZHCQYGLMGJ AutokeyCipher ideallywantakeyaslongasthemessageVigen reproposedtheautokeycipherwithkeywordisprefixedtomessageaskeyknowingkeywordcanrecoverthefirstfewlettersusetheseinturnontherestofthemessagebutstillhavefrequencycharacteristicstoattackeg givenkeydeceptivekey deceptivewearediscoveredsavplaintext wearediscoveredsaveyourselfciphertext ZICVTWQNGKZEIIGASXSTSLVVWLA One TimePad ifatrulyrandomkeyaslongasthemessageisused thecipherwillbesecurecalledaOne Timepadisunbreakablesinceciphertextbearsnostatisticalrelationshiptotheplaintextsinceforanyplaintext anyciphertextthereexistsakeymappingonetoothercanonlyusethekeyoncethoughhaveproblemofsafedistributionofkey RotorMachines beforemodernciphers rotormachinesweremostcommonproductcipherwerewidelyusedinWW2GermanEnigma AlliedHagelin JapanesePurpleimplementedaverycomplex varyingsubstitutioncipherusedaseriesofcylinders eachgivingonesubstitution whi