1Cryptography, brieflyJohn Mitchell802.11b slides from Dan BonehCryptographyu Is• Tremendous tool• Basis for many security mechanismsu Is not• The solution to all security problems• Secure unless implemented properly• Secure if used improperlyu Encryption scheme:• functions to encrypt, decrypt data• key generation algorithmu Secret vs. public key• Public key: publishing key does not reveal key-1• Secret key: more efficient; can have key = key-1u Hash function• map text to short hash; ideally, no collisionsu Signature scheme• functions to sign data and confirm signatureBasic Concepts in CryptographyCryptosystemu A cryptosystem consists of five parts• A set P of plaintexts• A set C of ciphertexts• A set K of keys• A pair of functions encrypt: K ¥ P Æ C decrypt: K ¥ C Æ P such that for every key kŒK and plaintext pŒP decrypt(k, encrypt(k, p)) = p OK def’n for now, but doesn’t include key generation or prob encryption.2Primitive example: shift cipheru Shift letters using mod 26 arithmetic• Set P of plaintexts {a, b, c, … , x, y, z}• Set C of ciphertexts {a, b, c, … , x, y, z}• Set K of keys {1, 2, 3, … , 25}• Encryption and decryption functions encrypt(key, letter) = letter + key (mod 26) decrypt(key, letter) = letter - key (mod 26)u Example encrypt(3, stanford) = vwdqirugEvaluation of shift cipheru Advantages• Easy to encrypt, decrypt• Ciphertext does look garbledu Disadvantages• Not very good for long sequences of English words– Few keys -- only 26 possibilities– Regular pattern• encrypt(key,x) is same for all occurrences of letter x• can use letter-frequency tables, etcLetter frequency in Englishu Five frequency groups [Beker and Piper] E has probability 0.12 TAOINSHR have probability 0.06 - 0.09 DL have probability ~ 0.04CUMWFGYPB have probability 0.015 - 0.028 VKJXQZ have probability < 0.01Possible to break letter-to-letter substitution ciphers.• 1400: Arabs did careful analysis of words in Koran• 1500: realized that letter-frequency could break substitution ciphersOne-time padu Secret-key encryption scheme (symmetric)• Encrypt plaintext by xor with sequence of bits• Decrypt ciphertext by xor with same bit sequenceu Scheme for pad of length n• Set P of plaintexts: all n-bit sequences• Set C of ciphertexts: all n-bit sequences• Set K of keys: all n-bit sequences• Encryption and decryption functions encrypt(key, text) = key ⊕ text (bit-by-bit) decrypt(key, text) = key ⊕ text (bit-by-bit)3Evaluation of one-time padu Advantages• Easy to compute encrypt, decrypt from key, text• As hard to break as possible– This is an information-theoretically secure cipher– Given ciphertext, all possible plaintexts are equally likely,assuming that key is chosen randomlyu Disadvantage• Key is as long as the plaintext– How does sender get key to receiver securely? Idea can be combined with pseudo-random generators ...What is a “secure” cryptosystem?u Idea• If enemy intercepts ciphertext, cannot recover plaintextu Issues in making this precise• What else might your enemy know?– The kind of encryption function you are using– Some plaintext-ciphertext pairs from last year– Some information about how you choose keys• What do we mean by “cannot recover plaintext” ?– Ciphertext contains no information about plaintext– No efficient computation could make a reasonable guessInformation-theoretic securityu Remember conditional probability...• Random variables X, Y, …• Conditional probability P(X=x|Y=y)– Probability that X takes value x, given that Y=y13542P(even) = 1/2P(even| red) = 2/36Information-theoretic securityu Ciphertext gives no info about plaintext Prob(1 is for Land) = Prob(1 is for Sea) assuming that all keys are equally likelyKey Plaintext CiphertextH Land 1H Sea 2T Land 2T Sea 1u Cryptosystem is info-theoretically secure if P(Plaintext=p | Ciphertext=c) = P(Plaintext=p)4In practice ...u Information-theoretic security is possible• Shift cipher, one-time pad are info-secureu But not practical• Keys would be long• No public-key systemu Therefore• Cryptosystems in use are either– Just found to be hard to crack, or– Based on computational notion of securityExample cryptosystemsu Feistel constructions• Iterate a “scrambling function”• Example: DES, …, AES (Rijndael)u Complexity-based cryptography• Multiplication, exponentiation are “one-way”functions• Examples: RSA, El Gamal, elliptic curve systems,...Feistel networksu Many block algorithms are Feistel networks• Examples– DES, Lucifer, FREAL, Khufu, Khafre, LOKI, GOST, CAST,Blowfish, …, AES• Standard form for– Iterating a function f on parts of a message– Producing invertible transformationFeistel networku Scheme requires• Function f(Ri-1 ,Ki)• Computation for Ki– e.g., permutation of key Ku Advantage• Systematic calculation– Easy if f is table, etc.• Invertible if Ki known– Get Ri-1 from Li– Compute f(R i-1 ,Ki)– Compute Li-1 by ⊕L i-1R i-1R iL if⊕K iDivide n-bit input in half and repeat5Data Encryption Standardu Developed at IBM, widely usedu Feistel structure• Permute input bits• Repeat application of a S-box function• Apply inverse permutation to produce outputu Appears to work well in practice• Efficient to encrypt, decrypt• Not provably secureu Improvements• Triple DES, AES (Rijndael)Review: Complexity ClassesAnswer in polynomial spacemay need exhaustive searchIf yes, can guess and check inpolynomial timeAnswer in polynomial time, withhigh probabilityAnswer in polynomial timecompute answer directlyPBPPNPPSpaceeasyhardOne-way functionsu A function f is one-way if it is• Easy to compute f(x), given x• Hard to compute x, given f(x), for most xu Examples (we believe)• f(x) = divide bits x = y@z and multiply f(x)=y*z• f(x) = 3x mod p, where p is prime• f(x) = x3 mod pq, where p,q are primes with |p|=|q|One-way trapdooru A function f is one-way trapdoor if• Easy to compute f(x), given x• Hard to compute x, given f(x), for most x• Extra “trapdoor” information makes it easy tocompute x from f(x)u Example (we believe)• f(x) = x3 mod pq, where p,q are primes with |p|=|q|• Compute cube root using (p-1)*(q-1)6u Trapdoor function
View Full Document
Unlocking...