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 I0° Key Size(bits) Keys Time required at I encryption/us encryptions 32 232=43x10P 231 us=35.8 minutes 2. 15 milliseconds 24=72x1010 255 us=1142 year 10.01 hours 128 2128=34x103 As=5.4x10-years 5. 108years (8 2108=37x10 2161s=59×10yca 59 x 10years 26 characters 26!=4x10~6 64x10°ycas (permutation) 2x 106us =6.4x 10 years 6 復大软件学院 LiT
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 復大软件学院 LiT
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 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 8 復大软件学院 LiT
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
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 9 復大软件学院 LiT
LiJT 9 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
t Types of Cryptanalytic Attacks ciphertext only Encryption algorithm Ciphertext to be decoded known plaintext Encryption algorithm Ciphertext to be decoded One or more plaintext-ciphertext pairs formed with the secret key ° chosen plaintext Encryption algorithm Ciphertext to be decoded Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key 復大软件学院 LiT
LiJT 10 Types of Cryptanalytic Attacks • ciphertext only – Encryption algorithm – Ciphertext to be decoded • known plaintext – Encryption algorithm – Ciphertext to be decoded – One or more plaintext-ciphertext pairs formed with the secret key • chosen plaintext – Encryption algorithm – Ciphertext to be decoded – Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key