1296.3 Page 1296.3:Algorithms in the Real WorldCryptography 1 and 2296.3 Page 2Cryptography OutlineIntroduction: terminology, cryptanalysis, security Primitives: one-way functions, trapdoors, …Protocols: digital signatures, key exchange, ..Private-Key Algorithms: Rijndael, DESPublic-Key Algorithms: Knapsack, RSA, El-Gamal, …Case Studies: Kerberos, Digital Cash296.3 Page 3Cryptography OutlineIntroduction:– terminology – cryptanalytic attacks– securityPrimitives: one-way functions, trapdoors, …Protocols: digital signatures, key exchange, ..Private-Key Algorithms: Rijndael, DESPublic-Key Algorithms: Knapsack, RSA, El-Gamal, …Case Studies: Kerberos, Digital Cash296.3 Page 4Some TerminologyCryptography – the general termCryptology – the mathematicsEncryption – encoding (but sometimes used as general term)Cryptanalysis – breaking codesSteganography – hiding messagesCipher – a method or algorithm for encrypting or decrypting2296.3 Page 5More DefinitionsPrivate Key or Symmetric: Key1= Key2Public Key or Asymmetric: Key1 ∫ Key2Key1or Key2is public depending on the protocolEncryptionDecryptionKey1Key2CyphertextEk(M) = CDk(C) = MOriginal PlaintextPlaintext296.3 Page 6Cryptanalytic AttacksC = ciphertext messagesM = plaintext messagesCiphertext Only:Attacker has multiple Cs but does not know the corresponding Ms Known Plaintext: Attacker knows some number of (C,M) pairs.Chosen Plaintext: Attacker chooses M and is given C.Chosen Ciphertext: Attacker chooses C and is given M.296.3 Page 7What does it mean to be secure?Unconditionally Secure: Encrypted message cannot be decoded without the keyShannon showed in 1943 that key must be as long as the message to be unconditionally secure – this is based on information theoryA one time pad – xor a random key with a message (Used in 2ndworld war)Security based on computational cost: it is computationally “infeasible” to decode a message without the key.No (probabilistic) polynomial time algorithm can decode the message. 296.3 Page 8The CastAlice – initiates a message or protocolBob - second participantTrent – trusted middlemanEve – eavesdropperMallory – malicious active attackerTrentAlice BobEveMallory3296.3 Page 9Cryptography OutlineIntroduction: terminology, cryptanalysis, security Primitives:– one-way functions– one-way trapdoor functions– one-way hash functionsProtocols: digital signatures, key exchange, ..Private-Key Algorithms: Rijndael, DESPublic-Key Algorithms: Knapsack, RSA, El-Gamal, …Case Studies: Kerberos, Digital Cash296.3 Page 10Primitives: One-Way Functions(Informally): A functionY = f(x)is one-way if it is easy to compute y from x but “hard” to compute x from yBuilding block of most cryptographic protocolsAnd, the security of most protocols rely on their existence.Unfortunately, not known to exist. This is true even if we assume P π NP.296.3 Page 11One-way functions: possible definition1. F(x) is polynomial time2. F-1(x) is NP-hardWhat is wrong with this definition?296.3 Page 12One-way functions:better definitionFor most x no single PPT (probabilistic polynomial time) algorithm can compute x given yRoughly: at most a fraction 1/|x|kinstances x are easy for any k and as |x| -> ∞This definition can be used to make the probability of hitting an easy instance arbitrarily small.4296.3 Page 13Some examples (conjectures)Factoring:x = (u,v)y = f(u,v) = u*v If u and v are prime it is hard to recover them from y.Discrete Log: y = gxmod pwhere p is prime and g is a “generator” (i.e., g1, g2, g3, … generates all values < p).DES with known message m: y = DESx(m)This would assume a family of DES functions of increasing key size (for asymptotics) 296.3 Page 14One-way functions in public-key protocolsy = ciphertext m = plaintext k = public keyConsider: y = Ek(m) (i.e., f = Ek)Everyone knows k and thus fEk(m) needs to be easyEk-1(y) should be hardOtherwise eavesdropper could decrypt y.But what about the intended recipient, who should be able to decrypt y?296.3 Page 15One-way functions in private-key protocolsy = ciphertext m = plaintext k = keyIs y = Ek(m) (i.e. f = Ek)a one-way function with respect to y and m?What do one-way functions have to do with private-key protocols?296.3 Page 16One-way functions in private-key protocolsy = ciphertext m = plaintext k = keyHow abouty = Ek(m) = E(k,m) = Em(k) (i.e. f = Em)should this be a one-way function?In a known-plaintext attack we know a (y,m) pair.The m along with E defines fEm(k) needs to be easyEm-1(y) should be hardOtherwise we could extract the key k.5296.3 Page 17One-Way Trapdoor FunctionsA one-way function with a “trapdoor”The trapdoor is a key that makes it easy to invert the function y = f(x)Example: RSA (conjecture)y = xemod nWhere n = pq (p, q, prime, p, q, e random)p or q or d (where ed = 1 mod (p-1)(q-1)) can be used as trapdoorsIn public-key algorithmsf(x) = public key (e.g., e and n in RSA)Trapdoor = private key (e.g., d in RSA)296.3 Page 18One-way Hash FunctionsY = h(x) where– y is a fixed length independent of the size of x. In general this means h is not invertible since it is many to one.– Calculating y from x is easy– Calculating any x such that y = h(x) give y is hardUsed in digital signatures and other protocols.296.3 Page 19Cryptography OutlineIntroduction: terminology, cryptanalysis, security Primitives: one-way functions, trapdoors, …Protocols: – digital signatures– key exchangePrivate-Key Algorithms: Rijndael, DESPublic-Key Algorithms: Knapsack, RSA, El-Gamal, …Case Studies: Kerberos, Digital Cash296.3 Page 20ProtocolsOther protocols:– Authentication– Secret sharing– Timestamping services– Zero-knowledge proofs– Blind signatures– Key escrow– Secure elections– Digital cashImplementation of the protocol is often the weakest point in a security system.6296.3 Page 21Protocols: Digital SignaturesGoals:1. Convince recipient that message was actually sent by a trusted source2. Do not allow repudiation, i.e., that’s not my signature.3. Do not allow tampering with the message without invalidating the signatureItem 2 turns out to be really hard to do296.3 Page 22Using private keys– ka is a secret key shared by Alice and Trent– kb is a secret key shared by Bob and Trentsig is a note from Trent saying that Alice “signed” it.To prevent repudiation Trent needs to keep m or at least h(m) in a databaseTrentAlice BobEka(m) Ekb(m + sig)296.3 Page 23Using Public