Lecture 12, public-key cryptography and the RSA algorithm. In this chapter, the learning objectives are: To review public-key cryptography, to demonstrate that confidentiality and sender-authentication can be achieved simultaneously with public-key cryptography, to review the RSA algorithm for public-key cryptography,. | Lecture 12: Public-Key Cryptography and the RSA Algorithm Lecture Notes on “Computer and Network Security” by Avi Kak (kak@) February 28, 2016 11:34pm c 2016 Avinash Kak, Purdue University Goals: • To review public-key cryptography • To demonstrate that confidentiality and sender-authentication can be achieved simultaneously with public-key cryptography • To review the RSA algorithm for public-key cryptography • To present the proof of the RSA algorithm • To go over the computational issues related to RSA • To discuss the vulnerabilities of RSA • Perl and Python implementations for generating primes and for factorizing medium to large sized numbers CONTENTS Section Title Page Public-Key Cryptography 3 The Rivest-Shamir-Adleman (RSA) Algorithm for Public-Key Cryptography — The Basic Idea 8 The RSA Algorithm — Putting to Use the Basic Idea 12 How to Choose the Modulus for the RSA Algorithm 14 Proof of the RSA Algorithm 17 Computational Steps for Key Generation in RSA 21 Computational Steps for Selecting the Primes p and q 22 Choosing a Value for the Public Exponent e 24 Calculating the Private Exponent d 27 A Toy Example That Illustrates How to Set n, e, and d for a Block Cipher Application of RSA 28 Modular Exponentiation for Encryption and Decryption 34 An Algorithm for Modular Exponentiation 38 The Security of RSA — Vulnerabilities Caused by Lack of Forward Secrecy 42 The Security of RSA — Chosen Ciphertext Attacks 45 The Security of RSA — Vulnerabilities Caused by LowEntropy Random Numbers 51 The Security of RSA — The Mathematical Attack 55 Factorization of Large Numbers: The Old RSA Factoring Challenge 75 The Old RSA Factoring Challenge: Numbers Not Yet Factored 79 The RSA Algorithm: Some Operational Details 81 RSA: In Summary 92 Homework .
