密码学的演变历史(1).ppt

《密码学的演变历史(1).ppt》由会员分享，可在线阅读，更多相关《密码学的演变历史(1).ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Cryptography and Network SecurityChapter 2 Classical Encryption TechniquesFourth Editionby William StallingsLecture slides by 杨寿保http:/202.38.64.11/syang/cryptoclassSeptember 2007University of Science and Technology of China(USTC)Part OneSymmetric CiphersPart OneSymmetric CiphersuRoad Map for Part O

2、nenChp.2,Classical Encryption TechniquesnChp.3,Block Cipher and the Data Encryption StandardnChp.4,Finite FieldsnChp.5,Advanced Encryption StandardnChp.6,More on Symmetric CiphersnChp.7,Confidentiality Using Symmetric Encryption1/2/20232Cryptography and Network Security-2Chapter 2 Chapter 2 Classica

3、l Encryption TechniquesClassical Encryption TechniquesuMany savages at the present day regard their names as vital parts of themselves,and therefore take great pains to conceal their real names,lest these should give to evil-disposed persons a handle by which to injure their owners.The Golden Bough,

4、Sir James George Frazer1/2/20233Cryptography and Network Security-2密码学的演变历史密码学的演变历史(1)(1)u1918,William Friedmans The Index of Coincidence and its Applications in Cryptographyu Edward Hebern,Rotor Machine for 50 Years.u1949,Claude Shannons The Communication Theory of Secrecy System,成为理论基础u1949-1967，C

5、ryptographic Literature was barrenu1971,IBM:Luciffer Cipher,128位密钥作分组加密nby team led by Horst Feistelnused 64-bit data blocks with 128-bit keyu1975,Diffie-Hellman,A New Direction in Cryptography,首次提出适应网络保密通信的公开密钥思想，揭开现代密码学研究的序幕，具有划时代的意义u1976-1977，美国国家标准局正式公布实施DES，Data Encryption Standard1/2/20234Cryp

6、tography and Network Security-2密码学的演变历史密码学的演变历史(2)(2)u19771978，Rivest,Shamir,Adelman 第一次提出公开密钥密码系统的实现方法RSAu1981，成立International Association for Cryptology Researchu1985，ElGamal 提出概率密码系统 ElGamal方法u19901992，Lai Xuejia and James:IDEA,The International Data Encryption Algorithmu2000,AES,Advanced Encrypt

7、ion Standard1/2/20235Cryptography and Network Security-2uCryptology(保密学)，源自希腊语(Greek)Krypts:hidden;logos:word,是密码学和密码处理过程的研究。uCryptography:The Science and Study of Secret Writing，密码编码学uCryptanalysis:The Science and Study of Secret Breaking，密码破译学uCipher:A secret method of writing 加密方法uEncipher(enciph

8、erment),encryption:将明文转换成密文的过程uDecipher(decipherment),decryption:将密文还原成明文的过程uPlaintext(cleartext):原始的可读数据，明文uCiphertext(Cryptogram):加密后的不可解读之文件，密文uKey:密钥，对加密与解密过程进行控制的参数uE(m):Encryption Transformation 加密变换uD(c):Decryption Transformation 解密变换密码学基本术语密码学基本术语 TerminologiesTerminologies1/2/20236Cryptogra

9、phy and Network Security-2u什么是密码？简单地说它就是一组含有参数K的变换E。设已知消息m，通过变换Ek得密文C，即，这个过程称为加密，E为加密算法，k不同，密文C亦不同。传统的保密通信机制：EncipherPlaintextCiphertextKeysDecipherC=Ek(m)发方：m收方：mkk（公共信道）加密E解密D（秘密信道）简单加密系统模型简单加密系统模型1/2/20237Cryptography and Network Security-2uTheoretical Security(or Perfect Security)and Practical S

10、ecure(or Computationally Secure)u理论安全，或无条件安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-time Pad，不实用。u实际安全，或计算上安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行（Computationally Infeasible）。理论安全和实际安全理论安全和实际安全1/2/

11、20238Cryptography and Network Security-2加密的基本概念加密的基本概念u密码体制 加密系统采用的基本工作方式称为密码体制。密码体制的基本要素是密码算法和密钥。密码算法是一些公式、法则或程序；密钥是密码算法中的控制参数。加密系统可以用数学符号来描述：SP,C,K,E,DP：明文空间 C：密文空间K：密钥空间 E：加密变换D：解密变换 kK，则有CEk(P)，PDk(C)Dk(Ek(P)，或者DkEk1，且EkDk1。1/2/20239Cryptography and Network Security-2u对称密码体制(Symmetric System,One

12、-key System,Private-key System)加密密钥和解密密钥相同，或者一个密钥可以从另一个导出，能加密就能解密，加密能力和解密能力是结合在一起的，开放性差。u非对称密码体制(Asymmetric System,Two-key System,Public-key System)加密密钥和解密密钥不相同，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。对称密码体制和非对称密码体制对称密码体制和非对称密码体制1/2/202310Cryptography and Network Security-2u如果经过加密所得到的密文仅与给定的密码算法和密钥有

13、关，与被处理的明文数据在整个明文中的位置无关，则称为分组密码体制。通常以大于等于64位的数据块为单位，加密得相同长度的密文。u如果密文不仅与最初给定的算法和密钥有关，同时也与明文位置有关(是所处位置的函数)，则称为序列密码体制。加密以明文比特为单位，以伪随机序列与明文序列模2加后，作为密文序列。序列密码体制和分组密码体制序列密码体制和分组密码体制1/2/202311Cryptography and Network Security-2u确定型密码体制和概率密码体制n确定型：当明文和密钥确定后，密文也就唯一地确定了。n概率型：当明文和密钥确定后，密文通过客观随机因素从一个密文集合中产生，密文形式

14、不确定，称为概率型密码体制。u单向函数型密码体制和双向变换型密码体制n单向函数型密码体制适用于不需要解密的场合，容易将明文加密成密文，如哈希函数；n双向变换型密码体制可以进行可逆的加密、解密变换。其他加密体制其他加密体制1/2/202312Cryptography and Network Security-2u加密算法的选择公开发表的加密算法、政府指定的加密算法、著名厂家产品、专家推荐的加密算法u通信信道的加密n链路加密点到点加密n高层连接加密端到端加密u存储数据的加密硬盘级加密和文件级加密加密的应用加密的应用1/2/202313Cryptography and Network Securit

15、y-2u现代密码学的基本原则n设计加密系统时，总是假定密码算法是可以公开的，需要保密的是密钥。一个密码系统的安全性不在算法的保密，而在于密钥，即Kerckhoff原则。u对加密系统的要求 n系统应该是实际上安全的(practical secure)，截获密文或已知明文密文对时，要决定密钥或任意明文在计算上是不可行的。n加密解密算法适用于密钥空间中的所有元素。n系统易于实现，使用方便。n系统的安全性不依赖于对加密体制或加密算法的保密，而依赖于密钥。n系统的使用不应使通信网络的效率过分降低。现代密码学基本原则现代密码学基本原则1/2/202314Cryptography and Network S

16、ecurity-2u对称加密系统由以下五部分组成:nPlaintext：明文nEncryption algorithm：加密算法nKey：密钥nCiphertext：密文nDecryption algorithm：解密算法u加密算法必须足够强大，使破译者不能仅根据密文破译消息u收发双方必须在某种安全的形式下获得密钥并必须保证密钥的安全2.12.1 对称密码的模型对称密码的模型1/2/202315Cryptography and Network Security-21/2/202316Cryptography and Network Security-2RequirementsRequireme

17、ntsuTwo requirements for secure use of symmetric encryption:na strong encryption algorithmna secret key known only to sender/receiverY=EK(X)X=DK(Y)uAssume encryption algorithm is knownuImplies a secure channel to distribute key1/2/202317Cryptography and Network Security-2Y=Ek(X)X=Dk(Y)1/2/202318Cryp

18、tography and Network Security-2u密码编码学(Cryptography)密码编码系统根据以下三个独立方面进行分类n用于将明文转换为密文的操作类型：替代和置换n所使用的密钥的数量：对称密码体制，单钥系统、秘密密钥系统非对称密码体制，双钥系统、公开密钥系统n明文的处理方式：分组加密和流加密u密码分析学(Cryptanalysis)n密码分析：试图破译密文得到明文或试图获得密钥的过程为密码分析，密码破译的策略取决于加密方法及可供破译者使用的信息。n穷举攻击：对密文尝试所有可能的密钥，直到把它转化为可读的有意义的明文，至少要尝试1/2可能的密钥。Cryptology Cr

19、yptology 密码学密码学1/2/202319Cryptography and Network Security-21/2/202320Cryptography and Network Security-2Cryptanalytic AttacksCryptanalytic Attacksuciphertext only nonly know algorithm&ciphertext,is statistical,know or can identify plaintext uknown plaintext nknow/suspect plaintext&ciphertextuchosen

20、 plaintext nselect plaintext and obtain ciphertextuchosen ciphertext nselect ciphertext and obtain plaintextuchosen text nselect plaintext or ciphertext to en/decrypt1/2/202321Cryptography and Network Security-2Brute Force SearchBrute Force SearchuAlways possible to simply try every key uMost basic

21、attack,proportional to key size uAssume either know/recognise plaintext1/2/202322Cryptography and Network Security-2u代换技术改变明文内容的表示形式，保持内容元素之间相对位置不变。单表替换如恺撒密码(Caesar Cipher)明文字母用密文中对应字母代替，例：明文字母表 Pp0,p1,pn-1密文字母表 Cc0,c1,cn-1密钥为正整数k，加密：i+k j(mod n)解密：j-k i(mod n)Caesar Cipher，加密：C=E(p)=(p+k)mod 26 解密：

22、p=D(C)=(C-k)mod 26,0A；1B；25Z2.2 2.2 代换技术代换技术(Substitution)(Substitution)1/2/202323Cryptography and Network Security-2Classical Substitution CiphersClassical Substitution CiphersuWhere letters of plaintext are replaced by other letters or by numbers or symbolsuOr if plaintext is viewed as a sequence

23、of bits,then substitution involves replacing plaintext bit patterns with ciphertext bit patternsuCaesar CiphernEarliest known substitution cipher by Julius Caesar nFirst attested use in military affairsnReplaces each letter by 3rd letter onmeet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWB1/2/

24、202324Cryptography and Network Security-2Caesar CipherCaesar CipheruWe can define transformation as:a b c d e f g h i j k l m n o p q r s t u v w x y zD E F G H I J K L M N O P Q R S T U V W X Y Z A B CuMathematically give each letter a numbera b c d e f g h i j k l m0 1 2 3 4 5 6 7 8 9 10 11 12n o

25、p q r s t u v w x y Z13 14 15 16 17 18 19 20 21 22 23 24 25uThen have Caesar cipher as:C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)1/2/202325Cryptography and Network Security-2Cryptanalysis of Caesar Cipher Cryptanalysis of Caesar Cipher u如果已知某给定密文是Caesar密码，穷举攻击是很容易实现的，因为只要简单地测试所有25种可能的密钥uCaesar密码的三个重要特征使

26、我们可以采用穷举攻击分析方法n已知加密和解密算法n需测试的密钥只有25个n明文所用的语言是已知的，且其意义易于识别uE.g.break ciphertext GCUA VQ DTGCM1/2/202326Cryptography and Network Security-21/2/202327Cryptography and Network Security-2Cryptanalysis of Caesar CipherCryptanalysis of Caesar Cipheru如果明文所用语言不为我们所知，则明文输出不可识别，而且输入可能按某种方式经过缩写或压缩，则识别就更加困难uFor

27、example:1/2/202328Cryptography and Network Security-2MonoalphabeticMonoalphabetic Cipher Cipher 单表替代单表替代uRather than just shifting the alphabet uCould shuffle(jumble)the letters arbitrarily uEach plaintext letter maps to a different random ciphertext letter uHence key is 26 letters long Plain:abcdef

28、ghijklmnopqrstuvwxyz Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA 1/2/202329Cryptography and Network Security-2MonoalphabeticMonoalphabetic Cipher Security Cipher SecurityuNow have a total of 26!=4 x 1026 keys more than 400,000,000,000,000,00

29、0,000,000,0004x1026=400万亿亿 uWith so many keys,might think is secure uBut would be!WRONG!uProblem is language characteristics1/2/202330Cryptography and Network Security-2Language Redundancy and CryptanalysisLanguage Redundancy and CryptanalysisuHuman languages are redundant uE.g.th lrd s m shphrd shl

30、l nt wnt uLetters are not equally commonly used uIn English e is by far the most common letter,then T,R,N,I,O,A,S uOther letters are fairly rare uc.f.(比较)Z,J,K,Q,X uHave tables of single,double&triple letter frequencies 1/2/202331Cryptography and Network Security-2English Letter FrequenciesEnglish L

31、etter Frequencies1/2/202332Cryptography and Network Security-2Use in CryptanalysisUse in CryptanalysisuKey concept-monoalphabetic substitution ciphers do not change relative letter frequencies uDiscovered by Arabian scientists in 9th centuryuCalculate letter frequencies for ciphertextuCompare counts

32、/plots against known values uIf Caesar cipher look for common peaks/troughs npeaks at:A-E-I triple,NO pair,RST triplentroughs at:JK,X-ZuFor monoalphabetic must identify each letterntables of common double/triple letters help1/2/202333Cryptography and Network Security-2Example CryptanalysisExample Cr

33、yptanalysisuGiven ciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQuCount relative letter frequencies(see text)uGuess P&Z are e and tuGuess ZW is th and hence ZWP is theuProceeding with trial and error finally get:it w

34、as disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow1/2/202334Cryptography and Network Security-2PlayfairPlayfair Cipher CipheruNot even the large number of keys in a monoalphabetic cipher provides security uOne appr

35、oach to improving security was to encrypt multiple letters uThe Playfair Cipher is an example invented by Charles Wheatstone in 1854,but named after his friend Baron Playfair 1/2/202335Cryptography and Network Security-2PlayfairPlayfair Key Matrix Key MatrixuA 5X5 matrix of letters based on a keywor

36、d uFill in letters of keyword(no duplicates)uFill rest of matrix with other lettersuEg.using the keyword MONARCHYMONARCHYBDEFGI/JKLPQSTUVWXZ1/2/202336Cryptography and Network Security-2Encrypting and DecryptingEncrypting and DecryptinguPlaintext encrypted two letters at a time:1.if a pair is a repea

37、ted letter,insert a filler like X,eg.balloon encrypts as ba lx lo on 2.if both letters fall in the same row,replace each with letter to right(wrapping back to start from end),eg.“ar encrypts as RM 3.if both letters fall in the same column,replace each with the letter below it(again wrapping to top f

38、rom bottom),eg.“mu encrypts to CM 4.otherwise each letter is replaced by the one in its row in the column of the other letter of the pair,eg.“hs encrypts to BP,and“ea to IM or JM(as desired)1/2/202337Cryptography and Network Security-2Security of the Security of the PlayfairPlayfair Cipher CipheruSe

39、curity much improved over monoalphabeticuSince have 26 x 26=676 digrams uWould need a 676 entry frequency table to analyse(verses 26 for a monoalphabetic)and correspondingly more ciphertext uIt was widely used for many years(eg.US&British military in WW1)uIt can be broken,given a few hundred letters

40、 since still has much of plaintext structure 1/2/202338Cryptography and Network Security-2PolyalphabeticPolyalphabetic Ciphers CiphersuAnother approach to improving security is to use multiple cipher alphabets,called polyalphabetic substitution ciphers uIt makes cryptanalysis harder with more alphab

41、ets to guess and flatter frequency distribution uUse a key to select which alphabet is used for each letter of the message uUse each alphabet in turn uRepeat from start after end of key is reached 1/2/202339Cryptography and Network Security-2VigenreVigenre Cipher CipheruSimplest polyalphabetic subst

42、itution cipher is the Vigenre Cipher,which is effectively multiple caesar ciphers uKey is multiple letters long K=k1 k2.kd uith letter specifies ith alphabet to use uUse each alphabet in turn uRepeat from start after d letters in messageuDecryption simply works in reverse 1/2/202340Cryptography and

43、Network Security-2ExampleExampleuWrite the plaintext out uWrite the keyword repeated above ituUse each key letter as a caesar cipher key uEncrypt the corresponding plaintext letterue.g.using keyword deceptivekey:deceptivedeceptivedeceptiveplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGV

44、TWAVZHCQYGLMGJ1/2/202341Cryptography and Network Security-2AidsAidsuSimple aids can assist with en/decryption uA Saint-Cyr Slide is a simple manual aid na slide with repeated alphabet nline up plaintext A with key letter,eg C nthen read off any mapping for key letter uCan bend round into a cipher di

45、sk or expand into a Vigenre Tableau(see text Table 2.3)1/2/202342Cryptography and Network Security-21/2/202343Cryptography and Network Security-2Security of Security of VigenreVigenre Ciphers CiphersuHave multiple ciphertext letters for each plaintext letteruHence letter frequencies are obscured but

46、 not totally lostuStart with letter frequenciesnsee if look monoalphabetic or notuIf not,then need to determine number of alphabets,since then can attach each1/2/202344Cryptography and Network Security-2KasiskiKasiski Method MethoduMethod developed by Babbage/Kasiski uRepetitions in ciphertext give

47、clues to period uSo find same plaintext an exact period apart which results in the same ciphertext uOf course,could also be random flukeuE.g.repeated“VTW”in previous example suggests size of 3 or 9uThen attack each monoalphabetic cipher individually using same techniques as before1/2/202345Cryptogra

48、phy and Network Security-2AutokeyAutokey Cipher CipheruIdeally want a key as long as the messageuVigenre proposed the autokey cipher with keyword is prefixed to message as keyuKnowing keyword can recover the first few letters uUse these in turn on the rest of the messageuBut still have frequency cha

49、racteristics to attack uE.g.given key deceptivekey:deceptivewearediscoveredsavplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA1/2/202346Cryptography and Network Security-2One-Time PadOne-Time PaduIf a truly random key as long as the message is used,the cipher will be secur

50、e,called a One-Time paduIs unbreakable since ciphertext bears no statistical relationship to the plaintextuSince for any plaintext&any ciphertext there exists a key mapping one to otheruCan only use the key once thoughuHave problem of safe distribution of key1/2/202347Cryptography and Network Securi