Brute Force Search always possible to simply try every key most basic attack, proportional to key size assume either know or recognise plaintext Number of Alternative Time required at 10 Key Size(bits) Ke eys Time required at I encryption/us encryptions 232=43x10° 23I Hs =35.8 minutes 2. 15 milliseconds 26⑧ 2=72x1010 2sps =114] years 10.01 hours 212=34x103 2127 Hs =54 1024years 5.4 x 108 years 2108=37x10 2167s=59×10ycas 59 x 100years 26 characters 26!=4xl026 (permutation) 2x1030ps=64x102yes 64xl0° years 6 復大辱软件学院 LiJT
LiJT 6 Brute Force Search • always possible to simply try every key • most basic attack, proportional to key size • assume either know or recognise plaintext
er Monoalphabetic Cipher Security now have a total of 26! 4 x 1026 keys with so many keys, might think is secure but would be ! wrong!!! problem is language characteristics 復大辱软件学院 LiJT
LiJT 7 Monoalphabetic Cipher Security • now have a total of 26! = 4 x 1026 keys • with so many keys, might think is secure • • but would be !!!WRONG!!! • problem is language characteristics
o Example Cryptanalysis given ciphertext UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZ SHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ count relative letter frequencies(see text) guess P&z are e and t guess ZW is th and hence ZWP is the proceeding with trial and error finally get it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow 8 復大辱软件学院 LiJT
LiJT 8 Example Cryptanalysis • given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ • count relative letter frequencies (see text) • guess P & Z are e and t • guess ZW is th and hence ZWP is the • proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow
2 Use in Cryptanalysis key concept-monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in gtn century calculate letter frequencies for ciphertext compare counts/plots against known values if Caesar cipher look for common peaks/troughs peaks at: A-E-I triple, No pair, RST triple troughs at: JK, X-Z for monoalphabetic must identify each letter tables of common double/triple letters help 復大辱软件学院 LiJT
LiJT 9 Use in Cryptanalysis • key concept - monoalphabetic substitution ciphers do not change relative letter frequencies • discovered by Arabian scientists in 9th century • calculate letter frequencies for ciphertext • compare counts/plots against known values • if Caesar cipher look for common peaks/troughs – peaks at: A-E-I triple, NO pair, RST triple – troughs at: JK, X-Z • for monoalphabetic must identify each letter – tables of common double/triple letters help
More Definitions unconditional security no matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext computational security given limited computing resources(eg time needed for calculations is greater than age of universe), the cipher cannot be broken Unconditional security would be nice, but the only known such cipher is the one-time pad (later) For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher. 復大辱软件学院 LiST
LiJT 10 More Definitions • unconditional security – no matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uniquely determine the corresponding plaintext • computational security – given limited computing resources (eg. time needed for calculations is greater than age of universe), the cipher cannot be broken • Unconditional security would be nice, but the only known such cipher is the one-time pad (later). – For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher