Introduction to Cryptography Slides PDF (LMAT2450)

Introduction to Cryptography François Koeune – Olivier Pereira with inputs from T. Peters Slides 01 UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01...

Introduction to Cryptography François Koeune – Olivier Pereira with inputs from T. Peters Slides 01 UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 1  Goal of the course Understand fundamental ▶ concepts, ▶ methods, and ▶ algorithms used to secure information, with an emphasis on the algorithmic and mathematical aspects. UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 2  Related courses at UCL Option in Cryptography and Information Security (EPL – DACS/ELEC/INFO/MAP) ▶ LELEC2348 — Information theory and coding – J. Louveaux, B. Macq, O. Pereira ▶ LELEC2760 — Secure electronic circuits and systems – F.-X. Standaert ▶ LELEC2770 — Privacy Enhancing Technologies – O. Pereira, F.-X. Standaert ▶ LINFO2144 — Secured systems engineering – A. Legay ▶ LINFO2347 — Computer System Security – R. Sadre ▶ LMAT2440 — Théorie des nombres – P.-E. Caprace, O. Pereira ▶ LMAT2450 — Cryptography – O. Pereira UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 3  Related courses at UCL Other related courses ▶ LELEC2870 — Machine Learning – J. Lee, M. Verleysen ▶ LINFO1341 — Computer networks – O. Bonaventure ▶ LINMA2111 — Discrete mathematics II : Algorithms and complexity – J.-C. Delvenne ▶ LEPL2210 — Ethics and ICT – A. Gosseries, O. Pereira UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 4  Class Organisation ▶ Lectures on Wednesday, 14:00 – 16:00 Exercises on Wednesday, 16:15 – 18:15 ▶ TAs: Antoine Legat, Alexis Vuille ▶ Examination: exercises. Slides and personal notes allowed Exam questions from past years often proposed as exercises UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 5  Syllabus Expected distribution: ▶ Introduction (1 lecture) ▶ Symmetric cryptography (4 lectures) ▶ Asymmetric cryptography and algorithmic number theory (5 lectures) ▶ Post-quantum cryptography (1 lecture) UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 6  Support Introduction to Modern Cryptography (3rd edition) by J. Katz and Y. Lindell – Chapman & Hall/CRC – 2021 http://www.cs.umd.edu/~jkatz/imc.html UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 7  Support Other references (see also Moodle): ▶ D. Stinson, Cryptography, Theory and Practice, 3rd edition, Chapman & Hall/CRC, 2005. ▶ N.P. Smart, Cryptography Made Simple, Springer, 2016. Free access within UCLouvain network. ▶ A.J. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, 1999. Free on http://www.cacr.math.uwaterloo.ca/hac/. ▶ D. Boneh, V. Shoup, A Graduate Course in Applied Cryptography, Free draft on http://toc.cryptobook.us/. ▶ S. Gabraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012, Extended version from author’s homepage. UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 8  Cryptography... COD defines cryptography as: “the art of writing or solving codes.” ▶ Certainly true until mid of 20th century ▶ Mostly used by armies and diplomats UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 9  Cryptography... today Used every day! UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 10  Cryptography... today Much more than encryption: ▶ authentication ▶ key exchange ▶ identification ▶ elections ▶ Yao millionaire’s problem ▶... From an art, cryptography became a science... UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 11  The message encryption problem Plain communication: E m A B Encrypted communication: E c m m A Enc Dec B UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 12  Message Encryption What is an encryption scheme? A triple ⟨Gen, Enc, Dec⟩ ▶ Gen probabilistically selects a key k ▶ Enc encrypts message m with key k, as c := Enck (m) ▶ Dec decrypts ciphertext c with key k as m := Deck (c) Remarks: ▶ same key is used for encryption and decryption: symmetric/private-key encryption ▶ correctness requirement: ∀k, m : m = Deck (Enck (m)) UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 13  Message Encryption An example: the Scytale (Greece, 7th century BC (?)) ▶ Gen defines the diameter of the cylinder (k := number of letters you can write on the circumference) ▶ Enc encrypts by transposing letters according to k ▶ Dec decrypts by performing the inverse transposition UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 14  Message Encryption Another example: the Caesar’s cipher (Rome, 1st c. BC) ▶ Shift letters (D → A, E → B, F → C,... , C → Z) ▶ Ex: HELLO → EBIIL ▶ Gen defines the extent k ∈ [0, 25] of the shift ▶ Enc encrypts by substituting letters, applying the right shift ▶ Dec decrypts by performing the inverse shift For more historical examples, see, e.g.,: http://www.apprendre-en-ligne.net/crypto/ UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 15  Cryptanalysis Cryptanalysis: art of code breaking/cracking Attacker model: 1. What should be considered as secret? Gen? Enc? Dec? k? 2. Which attack scenario? Eavesdropper? Chosen-plaintext?... ? UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 16  Cryptanalysis Attacker model: 1. What should be considered as secret? Gen? Enc? Dec? k? Kerckhoffs’ principle (1883): only the key should be secret See: http://www.petitcolas.net/fabien/kerckhoffs/ UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 17  Kerckhoffs’ principle UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 18  Kerckhoffs’ principle “Only the key should be secret.” – Why? 1. Keeping secrets is annoying: ▶ A key is easier to exchange secretly than a full system ▶ A key is easier to update in case of compromise ▶ One encryption scheme per pair of users is not manageable ▶ No need to kill the cryptographer 2. Public algorithms should be safer: ▶ Public algorithms can be scrutinized by friends ▶ Possibility to create standards ▶ No risk of code reverse-engineering 3. We can handle it... UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 19  Cryptanalysis Attacker model: 1. Which attack scenario? Depending on the context: 1. Passive: ▶ Ciphertext-only: you only see ciphertexts ▶ Known-plaintext: you see some plaintext/ciphertext pairs 2. Active: ▶ Chosen-plaintext: you can ask for the encryption of some messages ▶ Chosen-ciphertext: you can also ask for the decryption of some ciphertexts UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 20  Cryptanalysis Consider Caesar’s cipher, with: ▶ Public algorithms ▶ Ciphertext only How do we break it? ▶ Just try the 26 possible keys! Lesson: 1. Key space should not be explorable when messages are long... In practice: trying all keys should require at least 280 computational steps (280 ≈ 1000000000000000000000000) UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 21  Mono-alphabetic substitution Improvement on Caesar’s cipher: ▶ Not just a shift: take any permutation of the alphabet ▶ This is 26! ≈ 288 keys How do we break it? ▶ Sherlock Holmes did it! ▶ If you know the plaintext language, frequency analysis is possible... UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 22  Mono-alphabetic substitution Frequencies in English: UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 23  Mono-alphabetic substitution Frequencies in Spanish: UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 24  Mono-alphabetic substitution Improvement on Caesar’s cipher: ▶ Not just a shift: take any permutation of alphabet ▶ This is 26! ≈ 288 keys How do we break it? ▶ Just count the frequency of each symbol... Lesson: 2. Large key space is not enough! 3. We need something secure independently of message distribution UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 25  Vigenère cipher Another improvement on Caesar’s cipher: ▶ Instead of a constant shift, use different shifts according to position ▶ Key is a sequence of numbers in [0, 25] Example: ▶ Suppose key is ⟨2, 24, 5⟩ ▶ Cryptography is great Attnvjetvnjt gu bpgvr How do we break it? ▶ If you have enough ciphertext material... Make guesses on the key length, then make frequency analysis! UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 26  Historic ciphers Lessons: 4. We can keep playing like this for a long time... (See, e.g., D. Kahn, “The code-breakers” (Scribner) or J. Stern, “La science du secret” (Odile Jacob)) Can we do something else? ▶ In many cases: yes! UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 27  Modern Cryptography 1. Definitions 2. Assumptions 3. Proofs UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 28  Modern Cryptography: Definitions Definitions in cryptography: 1. What do we want to do? 2. Shall I use this scheme here? 3. Why choosing this scheme rather than that one? UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 29  Example of encryption What should the definition of security say for an encryption scheme? 1. Given any ciphertext, no adversary should be able to recover the key 2. Given any ciphertext, no adversary should be able to recover the plaintext 3. Given any ciphertext, no adversary should be able to recover any character of the plaintext 4. Given any ciphertext, no adversary should be able to recover any function of the plaintext Still need to define the adversarial model... UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 30  Modern Cryptography: Precise Assumptions Most schemes rely on computational assumptions ▶ Need to understand what we are trusting (challenges) ▶ Needed to write security proofs ▶ Useful for abstraction ▶ Useful for scheme comparison UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 31  Modern Cryptography: Proof of Security Relate schemes and definitions to assumptions ▶ Reductionist approach: if someone can break this scheme, (s)he is also able to falsify my assumption UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 32  Modern Cryptography: Definitions Limitations: Science vs. real world ▶ Check whether intuitive properties are guaranteed ▶ Compare with other definitions ▶ Compare with attack examples ▶ Use it during a few years... UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 33  Perfect encryption We just broke encryption schemes... but Shannon (1949): “perfect encryption is possible!” UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 34  Perfect encryption What is an encryption scheme? A triple ⟨Gen, Enc, Dec⟩ ▶ Gen probabilistically selects a key k ∈ K ▶ Enc encrypts message m ∈ M with key k, as c ← Enck (m) ▶ Dec decrypts ciphertext c ∈ C with key k as m := Deck (c) Remarks: ▶ Enc may be probabilisitic ▶ Deck (Enck (m)) = m, always ⇒ assume, wlog, Dec to be deterministic ▶ Assume |M| > 1 ▶ Assume M and C only contain messages and ciphertexts that may happen. UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 35  Perfect encryption Definition: ⟨Gen, Enc, Dec⟩ over message space M is perfectly secret if, for every probability distribution over M, every message m ∈ M, and every ciphertext c ∈ C: Pr[M = m|C = c] = Pr[M = m] Remarks: ▶ Probability distribution over M refers to distribution on messages ▶ Pr[M = m] is the probability that a message sampled according to that distribution takes the value m ▶ Pr[C = c] is the probability to obtain the ciphertext c when 1. Sampling a message according to the message distribution 2. Sampling a key according to Gen 3. Computing the ciphertext as the encryption of the message with that key UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 36  Perfect encryption Equivalent definition: ⟨Gen, Enc, Dec⟩ over message space M is perfectly secret if, for every probability distribution over M, every message m ∈ M, and every ciphertext c ∈ C: Pr[C = c|M = m] = Pr[C = c] Proof of equivalence: ▶ Use Bayes: Pr[C = c|M = m] = Pr[C = c] Pr[M=m|C =c]. Pr[C =c] (Bayes ⇒) Pr[M=m] = Pr[C = c] (Reorganize ⇒) Pr[M = m|C = c] = Pr[M = m] UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 37  Perfect encryption Equivalent definition: ⟨Gen, Enc, Dec⟩ over message space M is perfectly secret if, for every m0 , m1 ∈ M and every ciphertext c ∈ C: Pr[C = c|M = m0 ] = Pr[C = c|M = m1 ] Interpretation: ▶ It is impossible to distinguish the ciphertext corresponding to two plaintexts UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 38  Perfect encryption Equivalent definition... Given Π := ⟨Gen, Enc, Dec⟩, and adversary A, define the following experiment PrivKeav A,Π : 1. A outputs m0 , m1 ∈ M 2. Choose k ← K and b ← {0, 1}, and send Enck (mb ) to A 3. A outputs b ′ 4. Define PrivKeav A,Π := 1 iff b = b ′ UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 39  Perfect encryption (cont.) Equivalent definition: ⟨Gen, Enc, Dec⟩ over message space M is perfectly secret if for every adversary A: 1 Pr[PrivKeav A,Π = 1] = 2 Interpretation: ▶ Even if A chooses 2 messages, it cannot decide which of them has been encrypted UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 40  One-Time Pad The one-time pad is perfectly secret! ▶ Fix l > 0. M = K = C = {0, 1}l ▶ Gen selects uniformly in K ▶ Enck (m) := m ⊕ k ▶ Deck (c) := c ⊕ k Remarks: ▶ ⊕ denotes binary XOR (exclusive OR) ▶ Deck (Enck (m)) = m ⊕ k ⊕ k = m UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 41  One-Time Pad The one-time pad is perfectly secret! Proof: Fix any distribution over M, any m ∈ M and c ∈ C. Pr[C = c|M = m] = Pr[M ⊕ K = c|M = m] = Pr[m ⊕ K = c] 1 = Pr[K = m ⊕ c] = 2l = Pr[C = c|M = m′ ] for every m′ UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 42  One-Time Pad The one-time pad is perfectly secret! The one-time pad is not convenient to use... ▶ key needs to be as long as message! ▶ suppose m, m′ encrypted with k (m ⊕ k) ⊕ (m′ ⊕ k) = m ⊕ m′ A wins if it can play PrivKeav A,Π twice with same key! UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 43  Limits of Perfect Secrecy Suppose Π := ⟨Gen, Enc, Dec⟩ is s.t. |K| < |M|. Then Π is not a perfectly secret encryption scheme. Proof: Consider the uniform distribution on M and any c ∈ C. Define M(c) := {m : c = Enck (m) for some k ∈ K} We have |M(c)| ≤ |K| < |M| Therefore, ∃m∗ ∈ M − M(c), and 1 Pr[M = m∗ |C = c] = 0 ̸= = Pr[M = m∗ ] |M| UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 44  Conclusion Perfectly secret encryption schemes exist, but are difficult to use Can we do better? Shannon’s theory says: “no!” Under which assumptions? ▶ A has perfect information ▶ A has unbounded computational power Next week: What about bounded computational power? UCL Crypto Group Microelectronics Laboratory LMAT2450 - Slides 01 45