Basic Cryptography Terminology plaintext-the original message ciphertext-the coded message cipher-algorithm for transforming plaintext to ciphertext key info used in cipher known only to sender/receiver encipher (encrypt)-converting plaintext to ciphertext decipher(decrypt)-converting ciphertext to plaintext cryptography -study of encryption principles/methods cryptanalysis(codebreaking)-the study of principles/methods of deciphering ciphertext without knowing key cryptology -the field of both cryptography and cryptanalysis 11
11 Basic Cryptography Terminology plaintext - the original message ciphertext - the coded message cipher - algorithm for transforming plaintext to ciphertext key - info used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - converting ciphertext to plaintext cryptography - study of encryption principles/methods cryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key cryptology - the field of both cryptography and cryptanalysis
Cryptography Primitives:Encryption/Decryption function Symmetric Keys plaintext rypion ciphertext decryption plaintext key k key k Main Properties -Given plaintext and a key,it is computationally efficient to compute the ciphertext. 一( Given ciphertext and a key,it is computationally efficient to compute the plaintext. -But,given ciphertext without the key,it is computationally infeasible to compute the plaintext. -Keys are secret,but algorithms are public Any algorithm is hard to keep secret if used widely -Reverse engineering,social engineering Public examination helps to find flaws Military keeps algorithms secret is to avoid giving enemy good ideas 12
12 Cryptography Primitives: Encryption/Decryption function Symmetric Keys Main Properties ─ Given plaintext and a key, it is computationally efficient to compute the ciphertext. ─ Given ciphertext and a key, it is computationally efficient to compute the plaintext. ─ But, given ciphertext without the key, it is computationally infeasible to compute the plaintext. ─ Keys are secret, but algorithms are public ● Any algorithm is hard to keep secret if used widely – Reverse engineering, social engineering ● Public examination helps to find flaws ● Military keeps algorithms secret is to avoid giving enemy good ideas plaintext ciphertext plaintext encryption decryption key k key k
Types of Attacks on Encrypted Messages Ciphertext only: -Attacker knows:only ciphertext Known plaintext: -Attacker knows:(1)ciphertext,(2)one or more plaintext-ciphertext pairs formed with the key. ■( Chosen plaintext: -Attacker knows:(1)ciphertext,(2)plaintext messages chosen by the attacker, together with its corresponding ciphertext generated with the key. Chosen ciphertext: -Attacker knows:(1)ciphertext,(2)purported ciphertext chosen by attacker, together with its corresponding plaintext generated with the key. Chosen text -Attacker knows:(1)ciphertext,(2)plaintext messages chosen by the attacker, together with its corresponding ciphertext generated with the key,(3) purported ciphertext chosen by attacker,together with its corresponding plaintext generated with the key. 13
13 Types of Attacks on Encrypted Messages Ciphertext only: ─ Attacker knows: only ciphertext. Known plaintext: ─ Attacker knows: (1) ciphertext, (2) one or more plaintext-ciphertext pairs formed with the key. Chosen plaintext: ─ Attacker knows: (1) ciphertext, (2) plaintext messages chosen by the attacker, together with its corresponding ciphertext generated with the key. Chosen ciphertext: ─ Attacker knows: (1) ciphertext, (2) purported ciphertext chosen by attacker, together with its corresponding plaintext generated with the key. Chosen text ─ Attacker knows: (1) ciphertext, (2) plaintext messages chosen by the attacker, together with its corresponding ciphertext generated with the key, (3) purported ciphertext chosen by attacker, together with its corresponding plaintext generated with the key
Unconditional vs.Computational Security Unconditional security -No matter how much computer power is available,the cipher cannot be broken -The ciphertext provides insufficient information to uniquely determine the corresponding plaintext -Only one-time pad scheme qualifies Each message has a random key of the same length ●A simple XOR will work Brute-force search all keys does not work because multiple plausible plaintext ●Problems: -Key distribution and protection is difficult. Making large number of random keys is a significant task. Computational security -The cost of breaking the cipher exceeds the value of the encrypted info -The time required to break the cipher exceeds the useful lifetime of the info 14
14 Unconditional vs. Computational Security Unconditional security ─ No matter how much computer power is available, the cipher cannot be broken ─ The ciphertext provides insufficient information to uniquely determine the corresponding plaintext ─ Only one-time pad scheme qualifies ● Each message has a random key of the same length ● A simple XOR will work ● Brute-force search all keys does not work because multiple plausible plaintext ● Problems: – Key distribution and protection is difficult. – Making large number of random keys is a significant task. Computational security ─ The cost of breaking the cipher exceeds the value of the encrypted info ─ The time required to break the cipher exceeds the useful lifetime of the info
Brute Force Search Always possible to simply try every key Most basic attack,proportional to key size Assume attackers either know or recognise plaintext Key Size (bits) Number of Time required at 1 Time required at 106 Alternative Keys decryption/us decryptions/us 32 232=4.3×109 231μs =35.8 minutes 2.15 milliseconds 56 256=7.2×1016 255μs =1142 years 10.01 hours 128 2128=3.4×1038 2127μs =5.4×1024 5.4×1018 years years 168 2168=3.7×1050 2167μs =5.9×1036 5.9×1030 years years 26 characters 26!=4×1026 2×1026us=6.4×1012 6.4×106 years (permutation) years 15
15 Brute Force Search Key Size (bits) Number of Alternative Keys Time required at 1 decryption/µs Time required at 106 decryptions/µs 32 232 = 4.3 × 109 231 µs = 35.8 minutes 2.15 milliseconds 56 256 = 7.2 × 1016 255 µs = 1142 years 10.01 hours 128 2128 = 3.4 × 1038 2127 µs = 5.4 × 1024 years 5.4 × 1018 years 168 2168 = 3.7 × 1050 2167 µs = 5.9 × 1036 years 5.9 × 1030 years 26 characters (permutation) 26! = 4 × 1026 2 × 1026 µs = 6.4 × 1012 years 6.4 × 106 years Always possible to simply try every key Most basic attack, proportional to key size Assume attackers either know or recognise plaintext