Encryption-I

1、95-752:4-1Encryption - I95-752:4-2Definitions Plaintext: easy to understand form(original message) Ciphertext: difficult to understand form Encryption: encoding (plaintext - ciphertext) Decryption: decoding(ciphertext - plaintext) Cryptology: study of encryption Cryptography: use of encryption Crypt

2、analysis: breaking encryption95-752:4-3Cryptanalysts Role Break single message Recognize patterns to create decryption method Find general weakness in encryption algorithm95-752:4-4Breakable Encryption Feasible given time and data Brute force usually impractical Estimates based on current technology

3、 Just because the underlying scheme is based on a hard problem doesnt mean that the cryptanalyst will attempt to solve it that way95-752:4-5Cryptanalysts tools Letter frequency data Prefix/suffix lists Letter pair/triple lists Common pattern lists95-752:4-6Encryption Algorithm Transformation:C=E(P)P

4、=D(C)P=D(E(P) Keyed adds security even if algorithm is knownSymmetric: C=E(k,P) P=D(k,C)Asymmetric: C=E(k1,P) P=D(k2,C)95-752:4-7Character Representation Enumeration cyclic Y+3=B (24+3=1 with wrapping) Modulus Arithmetic 0 mod 26 = 0 1 mod 26 = 1 26 mod 26 = 0 27 mod 26 = 1A B C D E X Y ZA B C01234

5、23 24 25 01295-752:4-8Caesar Cipher Julius Caesar Gallic Wars Shift of three characters P= “PROFESSIONAL COURTESY”C=“SURIHVVLRQDO GRXUWHVB” Easy to use in the field Pattern is easy to spot and breakABCDEFGHIJKLMNOPQRSTUVWXYZDEFGH IJKLMNOPQRSTUVWXYZABC95-752:4-9Cryptanalysis of Caesar Cipher Obvious

6、break between words Double letters easy to spot Repeating letter patterns Small words easy to peg C=“WKLV LV WRR HDVB”THIS IS TOO _S_ small words THIS IS TOO EASY spot shift of 3 95-752:4-10Keyed Monoalphabetic Ciphers Key Permutation (key has no repeating letters) Multiplicative Modulus (key is mul

7、tiplier) f(i) = (3*i) mod 26 f(K) = 3*10 mod 26 = 4 = EABCDEFGHIJKLMNOPQRSTUVWXYZKEYABCDFGHIJLMNO PQRSTUVW XZABCDEFGHIJKLMNOPQRSTUVWXYZADGJMPSVYBEHKNQTWZCFILORUX95-752:4-11Monoalphabetic Ciphers Can be done by direct table lookup (easy in field) Time to encrypt/decrypt varies directly with length Be

8、trayed by letter frequencies95-752:4-12Example Ciphertext:HQFUBSWLRQLVDPHDQVRIDWWDLWLWJVHFXUHFRPSXWDWLRQRYHULQVHFXUHFKDQQHOVEBXVLQJHQFUBSWLRQZHGLVXLVHWHKPHVVDJH Plaintext:ENCRYPTIONISAMEANSOFATTAINGSECURECOMPUTATIONOVERINSECURECHANNELSBYUSINGENCRYPTIONWEDISGUISETHEMESSAGE95-752:4-13Letter Frequencie

9、s English vowel frequencies Ciphertext frequencies (104 letters)VowelAEIOUpercent7.49 14.0 6.67 7.37 3.0VowelAEIOUpercent00.96 0.96 0.96 4.81LetterHLVQWpercent13.5 11.5 9.62 9.62 8.6595-752:4-14Cryptoquote ZJ ZJZON CZYYZQP VKQVYK LDN D JQQYZLRORZPE, ZP ZL LOZYY D JQQYZLR ORZPE. - DPDOQYK JADPIKSept

10、11, 2003 Pittsburgh Tribune-Review95-752:4-15Security of Monoalphabetic Ciphers Are they secure? 26! Possible ciphers Modern computers 10 years to brute force NO! In long message letter frequencies betray text95-752:4-16Meaningful ObservationsAn encryption based on a hard problem is not secure just

11、because of the difficulty of the problemAn encryption algorithm must be regular- this is its weaknessA security measure must be strong enough to keep out the attacker only for the life of the data95-752:4-17Polyalphabetic Ciphers Flatten frequency distributions Conceal letter pairs Conceal prefixes/

12、suffixes Example: (using multiplicative modulus)Odd positions use: f(i)=(3*i) mod 26Even positions use: f(i)=(5*i)+13) mod 2695-752:4-18Vigenere Tableaux95-752:4-19Using Vigenere TableauxOne method:Choose a keyBreak text into groups of five charactersWrite key in repeating fashionUse letter of key t

13、o establish columnUse letter of plaintext to establish rowEncrypt by using intercept of row and column1.Decrypt by finding row with ciphertext in column95-752:4-20Vigenere Example Enciphering “Tale of Two Cities” using Key of “DICKENS”95-752:4-21Cryptanalysis of Polyalphabetic Ciphers Appears to be

14、more secure More complex, but not immune from breaking Two tools: Kasiski Method Index of coincidence95-752:4-22Repeated PatternsEnglish has regularities (letters, letter groups, words) that repeatObservations:If code uses n alphabets in cyclic rotation, and if a particular letter sequence appears k

15、 times in the plaintext, it will be encoded approximately k/n times from the same alphabetIf letter sequence is encoded the same way twice, key must have gone through a whole number of rotations and be back at the same point1.Distance between repeats is multiple of key length95-752:4-23Kasiski Metho

16、dIdentify repeated patterns of three or more lettersJot down starting position of each instanceCompute difference between starting pointsDetermine all factors of each differenceKey length is one of these factors95-752:4-24Example for Kasiski Method95-752:4-25Example of Kasiski MethodObserve “itwasth

17、e” is encrypted with the key “nsdicken” three timesStart DistanceFactors-63 (83-20)3,7,9,21,63 21(104-83)3,7,2120 length(“dickens”)=795-752:4-26Index of Coincidence Measure of variance between frequencies in distribution Divide message into pieces enciphered with same alphabet Measure variance of fr

18、equencies in distribution If measure approximates English alphabet, guess of number of alphabets is supportedAlphabets123510largeMeasure.068 .052 .047 .043 .042 .03895-752:4-27Perfect Cipher Flatten distributions to 0.038 Very large number of alphabets one time pad Large non-repeating keys on a pad

19、Each different, each used once and discarded Problems: Printing, distribution, storage95-752:4-28Use long nonrepeating sequence of numbers combined with plaintextCiphertext does not give away keyMethodUse binary of PXor binary of random number1. Produces binary cipher textVernam Cipher1 0 1 1 0 11 0

20、 1 1 1 10 0 0 0 1 095-752:4-29Cracking Random Numbers Computers use algorithms to create random numbers Multiplicative modulusri+1 = (a*ri+b) mod na, b, n carefully chosen; ri is initially seed Advantage: can reproduce series Disadvantage: long enough series may reveal seed, a, b, n95-752:4-30Known-

21、Text Attacks Messages dont have arbitrary content Memo, Subject, To, From, Date, Senders name, Receivers name Organizational terms May also have messages where entire text is known By comparing ciphertext with known plaintext, can find patterns in encryption95-752:4-31Transposition Ciphers Dont subs

22、titute characters, permute them Spartans used rods of fixed diameter and strips of parchment Write across the wrappings Read ciphertext along the wrappings (works great with #2 pencils) In modern terms, use a matrix95-752:4-32Columnar Transposition Ciphers Key is number of columns in matrix, order o

23、f columns Ciphertext: TSHAI HAORT IGWTI SEARO ITCAN SOONW ASLSO MHUPR EOMOK SWNSSTHISISAMESSAGETOSHOWHOWACOLUMNARTRANSPOSITIONWORKS95-752:4-33Analysis of Columnar Transposition Simple, but effective Work per character is constant, total proportional to message length Requires whole message in encryp

24、tion buffer Letter frequency looks like monoalphabetic cipher Use digram and trigram frequency tables95-752:4-34Breaking Columnar Transposition Problem: Which columns areadjacent Break into strips and look for digrams & trigrams95-752:4-35Double Transpositions Use two columnar transpositions one

25、 after the other, different numbers of columns First transposition breaks up doubled letters Second transposition breaks up short strings and reinforces first transposition Still monoalphabetic letter frequency More difficult to decrypt95-752:4-36Combination Ciphers Mix substitution and permutation

26、ciphers Substitution for confusion of information Permutation for diffusion of information Done right, each supports the other All modern ciphers are combinations95-752:4-37Answer to Cryptoquote IF FIFTY MILLIONPEOPLE SAY A FOOLISHTHING, IT IS STILL A FOOLISH THING.- ANATOLE FRANZE95-752:4-38Automat

27、ed Ciphers Stream Ciphers: encrypt data as it comes fast low error propagation information not diffused susceptible to modification and insertion Block Ciphers: encrypt data in fixed-size blocks Slower Larger error propagation Information may be diffused harder to modify or insert into blocks95-752:

28、4-39Data Encryption Standards 1972 NBS issues call for proposals 1974 IBM responds with “l(fā)ucifer” (DEA) 1976 DES adopted 1986 DES re-certification denied 1997 NIST issues call for AES proposals 1999 5 submissions selected as finalists 2001 Rijndahl algorithm selected95-752:4-40DES Overview Combinati

29、on cipher 16 rounds of combined substitution and transposition Plaintext encrypted in 64-bit blocks Keys are 56 bits long (plus 8 error bits) Uses only arithmetic and logical operations on 64-bit numbers95-752:4-41DES ModesAll modes: same key and algorithm encrypts and decrypts ECB Electronic code b

30、ook / Native mode CBC Cipher-block chaining OFB Output feedback CFB Cipher feedback95-752:4-42DES Algorithms Crypting algorithm method of encryption or decryption Key scheduling algorithm method of generating pieces of key needed for each round of crypting algorithm Parts: Permutation boxes (p-boxes

31、) Substitution boxes (s-boxes) exclusive OR (x-or)95-752:4-43Permutation Boxes Used as invertible initial and final disguise of information Fixed permutations at binary level95-752:4-44Substitution Boxes Confusion and non-linearity Interpret bits as numbers, pull replacement from table 6-bit input,

32、4-bit output first and last bit pick row of table middle four bits pick column of table elements of table are 4-bit numbers Not invertible Rationale for values is still secret95-752:4-45S-Box Values95-752:4-46DES CycleCrypting algorithm feeds 32 bits to cycleSubject block to Permutation Expansion, c

33、onverting 32 bits to 48 bitsXOR expanded block with 48 bits from key to make pre-S blockApply S boxBreak pre-S block into 8 six-bit chunksProcess each chunk through s-box in parallelResult is 32-bit post-S blockpost-S fed into final permutation to produce 32-bit cycle result95-752:4-47Crypting Algor

34、ithmInput 64 bits of plaintextRearrange by initial permutation p-boxSplit blocktwo 32-bit halves (left and right)save copy of right half as R0leave left half aloneFeed right to DES CycleXOR left with cycle result to be new rightR0 becomes new leftRepeat 3-6 sixteen timesSubmit final block to inverse of initial permutation95-752:4-48Key Scheduling Algorithm Combination of shifts and permutation Shifts are determined from table Permutation selects 48 of 56 bits Produces 16 different slices from key Slices are normally computed before crypting95-752:4-49DES Weaknesses Brute force attacks some