Public-Key Cryptography and RSA Algorithm

Public-Key Cryptography and the RSA Algorithm pdf free download
MarthaKelly Profile Pic
Published Date:12-07-2017
Your Website URL(Optional)
Lecture 12: Public-Key Cryptography and the RSA Algorithm Lecture Notes on “Computer and Network Security” by Avi Kak ( February 16, 2017 3:12pm c 2017 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 • PerlandPythonimplementations forgeneratingprimesandfor factorizing medium to large sized numbersCONTENTS Section Title Page 12.1 Public-Key Cryptography 3 12.2 The Rivest-Shamir-Adleman (RSA) Algorithm for 8 Public-Key Cryptography — The Basic Idea 12.2.1 The RSA Algorithm — Putting to Use the Basic Idea 12 12.2.2 How to Choose the Modulus for the RSA Algorithm 14 12.2.3 Proof of the RSA Algorithm 17 12.3 Computational Steps for Key Generation in RSA 21 12.3.1 Computational Steps for Selecting the Primes p and q 22 12.3.2 Choosing a Value for the Public Exponent e 24 12.3.3 Calculating the Private Exponent d 27 12.4 A Toy Example That Illustrates How to Set n, e, and d 28 for a Block Cipher Application of RSA 12.5 Modular Exponentiation for Encryption and Decryption 34 12.5.1 An Algorithm for Modular Exponentiation 38 12.6 The Security of RSA — Vulnerabilities Caused by Lack 42 of Forward Secrecy 12.7 The Security of RSA — Chosen Ciphertext Attacks 45 12.8 The Security of RSA — Vulnerabilities Caused by Low- 51 Entropy Random Numbers 12.9 The Security of RSA — The Mathematical Attack 55 12.10 Factorization of Large Numbers: The Old RSA 75 Factoring Challenge 12.10.1 The Old RSA Factoring Challenge: Numbers Not Yet Factored 79 12.11 The RSA Algorithm: Some Operational Details 81 12.12 RSA: In Summary .... 92 12.13 Homework Problems 94 2Computer and Network Security by Avi Kak Lecture 12 12.1: PUBLIC-KEY CRYPTOGRAPHY • Public-key cryptography is also known as asymmetric-key cryp- tography,todistinguishitfromthesymmetric-keycryptography we have studied thus far. • Encryption and decryption are carried out usingtwo different keys. The two keys in such a key pair are referred to as the public key and theprivate key. • With public key cryptography, all parties interested in secure communications publish their public keys. As to how that is done depends on the protocol. In the SSH protocol, each server makes available through its port 22 the public key it has stored for your login id on the server. (See Section 12.10 for how an SSHD server acquires the public key that the server would associate with your login ID so that you can make a password-free connection with the server. In the context of the security made possible by the SSH protocol, the public key held by a server is commonly referred to as the server’s host key.) When a client, such as yourlaptop,wants to make aconnectionwith anSSHD server,itsends a connectionrequestto port22 of the server machine and the server makes its host key available automatically. On the other hand, in theSSL/TLSprotocol,anHTTPSwebservermakesitspublic keyavailablethroughacertificateofthe sortyou’llsee inthe nextlecture. Aswewillsee, thissolvesoneofthemost vexing problems associated with symmetric-key cryptography — the problem of key distribution. 3Computer and Network Security by Avi Kak Lecture 12 • PartyA, if wanting to communicateconfidentially with party B,canencryptamessageusingB’spubliclyavailablekey. Sucha communicationwouldonlybedecipherablebyB asonlyB would have access to the corresponding private key. This is illustrated by the top communication link in Figure 1. • Party A, if wanting to send an authenticated message to party B, would encrypt the message with A’s own private key. Since this message would only be decipherable with A’s pub- lic key, that would establish the authenticity of the message — meaning that A was indeed the source of the message. This is illustrated by the middle communication link in Figure 1. • The communication link at the bottom of Figure 1 shows how public-key encryption can be used to provide both confiden- tiality and authentication at the same time. Note again thatconfidentiality means that we want to protect a message from eavesdroppers andauthentication means that the recip- ient needs a guarantee as to the identity of the sender. • In Figure 1,A’s public and private keys are designatedPU and A PR . B’spublicandprivatekeysaredesignatedPU andPR . A B B • AsshownatthebottomofFigure1,let’ssaythatAwantstosend a message M to B with both authentication and confidentiality. 4Message Message Message Computer and Network Security by Avi Kak Lecture 12 Party A wants to send a message to Party B When only confidentiality is needed: Party A Party B A’s private key A’s public key B’s private key B’s public key PU PR PU PR A B B A Encrypt with PU Decrypt with PR B B When only authentication is needed: Party A Party B A’s private key A’s public key B’s private key B’s public key PU PR PU PR A B A B Encrypt with PR Decrypt with PU A A When both confidentiality and authentication are needed: Party A Party B A’s private key A’s public key B’s private key B’s public key PU PR PU PR A B B A Decrypt Decrypt Encrypt Encrypt with with PR PU with PR with PU B A A B Figure 1: This figure shows how public-key cryptography can be used for confidentiality, for digital signatures, and for both. (This figure is from Lecture 12 of “Computer and Network Security” by Avi Kak.) 5 Message Message MessageComputer and Network Security by Avi Kak Lecture 12 The processing steps undertaken by A to convert M into its encrypted form C that can be placed on the wire are: C = E(PU , E(PR , M)) B A where E() stands for encryption. The processing steps under- taken by B to recover M from C are M = D(PU , D(PR , C)) A B where D() stands for decryption. • ThesenderAencryptinghis/hermessagewithitsownprivatekey PR provides authentication. This step constitutes A putting A his/her digital signature on the message. Instead of applying the private key to the entire message, a sender may also “sign” a message by applying his/her private key to just a small block of data that is derived from the message to be sent. DIDYOUKNOW that you are required to digitally sign the software for your app before you can market it through the official Android application store Google Play? And did you know that Apple’s App Store has the same requirement? • The sender A further encrypting his/her message with the receiver’s public key PU providesconfidentiality. B 6Computer and Network Security by Avi Kak Lecture 12 • Of course, the price paid for achieving confidentiality and au- thentication at the same time is that now the message must be processedfour times in all for encryption/decryption. The mes- sage goes through two encryptions at the sender’s place and two decryptions at the receiver’s place. Each of these four steps in- volves separately the computationally complex public-key algorithm. •IMPORTANT: Note that public-key cryptography does not make obsolete the more traditional symmetric-key cryptography. Because of the greater computational overhead associated with public-key crypto systems, symmetric-key systems continue to be widely used for content encryption. However, public-key en- cryption has proved indispensable for key management, for dis- tributing the keys needed for the more traditional symmetrickey encryption/decryption of the content, for digital signature appli- cations, etc. 7Computer and Network Security by Avi Kak Lecture 12 12.2: THE RIVEST-SHAMIR-ADLEMAN (RSA) ALGORITHM FOR PUBLIC-KEY CRYPTOGRAPHY — THE BASIC IDEA • TheRSAalgorithm—namedafterRonRivest,Adi Shamir, and Leonard Adleman — is based on a property of positive integers that we describe below. •As a direct consequence of the Euler’s Theorem of Section 11.4 of Lecture 11, we can state that when a and n are relatively prime, in arithmetic operations m a mod n, the exponents behave modulo the totient φ(n)ofn. SeeSection11.3ofLecture11forthedefinitionofthetotientofanumber. Euler’s φ(n) theoremsaysthata ≡ 1 (modn)whenaandnarerelatively prime. Given an arbitrary exponent k, we may express it as k = k φ(n)+k for some values of k and k . Euler’s theorem 1 2 1 2 k k 2 implies: a mod n =a mod n. • For example, consider arithmetic modulo 15. As explained in Section 11.3 of Lecture 11, since 15 = 3× 5, we have φ(15) = 2×4 = 8forthetotientof15. Youcaneasilyverifythefollowing: 8Computer and Network Security by Avi Kak Lecture 12 7 4 3 (7+4)mod8 4 ·4 mod 15 = 4 mod 15 = 4 mod 15 = 64 mod 15 = 4 3 5 7 (3×5) mod8 (4 ) mod 15 = 4 mod 15 = 4 mod 15 = 4 Note that in both cases the base of the exponent, 4, is coprime to the modulus 15. • It follows from Euler’s theorem that given two exponents e and d such that one is the multiplicative inverse of the other modulo e×d e×d (mod φ(n)) φ(n), we have M ≡M ≡M (mod n). • Theresultshownabove,whichfollowsdirectlyfromEuler’stheo- rem, requires thatM andn be coprime. However,as will be shown in Section 12.2.3, when n is a product of two primespandq,thisresultappliestoallM, 0≤M n. In what follows, let’s now see how this property can be used for message encryption and decryption. • Considering arithmetic modulo n, let’s say that e is an integer that is coprime to the totient φ(n) of n. Further, say that d is the multiplicative inverse of e modulo φ(n). These definitions of the various symbols are listed below for convenience: n = a modulus for modular arithmetic 9Computer and Network Security by Avi Kak Lecture 12 φ(n) = the totient of n e = an integer that is relatively prime to φ(n) This guarantees that e will possess a multiplicative inverse modulo φ(n) d = an integer that is the multiplicative inverse of e modulo φ(n) • NowsupposewearegivenanintegerM,0≤M n, thatrepre- sentsourmessage,then wecantransformM intoanotherinteger C that will represent our ciphertext by the following modulo ex- ponentiation: e C = M modn At this point, it may seem rather strange that we would want to represent any arbitrary plaintext message by an integer. But, it is really not that strange. Let’s say you want a block cipher that encrypts 1024 bit blocks at a time. Every plaintext block can 1024 now be thought of as an integer M of value 0≤M≤ 2 −1. 10Computer and Network Security by Avi Kak Lecture 12 • We canrecover back M from C by the following modulo oper- ation d M = C modn since d e ed (mod φ(n)) (M ) (mod n) = M ≡ M (mod n) 11Computer and Network Security by Avi Kak Lecture 12 12.2.1: The RSA Algorithm — Putting to Use the Basic Idea • The basic idea described in the previous subsection can be used to create a confidential communication channel in the manner described here. • An individual A who wishes to receive messages confidentially will use the pair of integerse,n as his/her public key. At the same time, this individual can use the pair of integersd,n as the private key. The definitions of n, e, and d are as in the previous subsection. • AnotherpartyB wishingtosendamessageM toAconfidentially will encrypt M using A’s public keye,n to create ciphertext C. Subsequently, only A will be able to decrypt C using his/her private keyd,n. • IftheplaintextmessageM istoolong,B maychoosetouseRSA as ablock cipher for encrypting the message meant for A. As explained by our toy example in Section 12.4, when RSA is used as a block cipher, the block size is likely to be half the number of bitsrequiredtorepresentthemodulusn. Ifthemodulusrequired, say,1024bitsforitsrepresentation, messageencryptionwouldbe 12Computer and Network Security by Avi Kak Lecture 12 based on 512-bit blocks. While, in principle, RSA can certainly be used as a block cipher, in practice, on account of its excessive computational overhead, it is more likely to be used just for server authentication and for exchanging a secret session key. A session key generated with the help of RSA-based encryption can subsequently be used for content encryption using symmetric-key cryptography based on, say, AES. • The important theoretical question here is as to what conditions if any must be satisfied by the modulusn for thisM→C→M transformation to work? 13Computer and Network Security by Avi Kak Lecture 12 12.2.2: How to Choose the Modulus for the RSA Algorithm • With the definitions of d and e as presented in Section 12.2, the modulus n must be selected in such a manner that the following is guaranteed:   e d ed M ) ≡ M ≡ M (mod n) e We want this guarantee because C = M modm is the en- crypted form of the message integerM and decryption is carried d out by C modn. • It was shown by Rivest, Shamir, and Adleman that we have this guarantee when n is a product of two prime numbers: n = p×q for some prime p and prime q (1) • The above factorization is needed because the proof of the algo- rithm,presented inthenextsubsection, depends onthefollowing two properties of primes and coprimes: 1. Iftwointegerspandq arecoprimes(meaning,relativelyprime to each other), the following equivalence holds for any two integers a and b: 14Computer and Network Security by Avi Kak Lecture 12 a ≡ b (mod p) and a ≡ b (mod q) ⇔ a ≡ b (mod pq) (2) This equivalence follows from the fact a≡ b (mod p) im- plies a−b = k p for some integer k . But since we also 1 1 have a≡b (mod q) implying a−b =k q, it must be the 2 case that k = k ×q for some k . Therefore, we can write 1 3 3 a−b =k ×p×q, which establishes the equivalence. (Note 3 that this argument breaks down if p and q have common fac- tors other than 1.) We will use this property in the next subsection to arrive at Equation (11) from the partial results in Equations (9) and (10). 2. Inadditiontoneedingpandq tobecoprimes,wealsowant pandqtobeindividuallyprimes. Itisonlywhenpand q are individually prime that we can decompose the totient of n into the product of the totients of p and q. That is φ(n) = φ(p)×φ(q) = (p−1)×(q−1) (3) See Section 11.3 of Lecture 11 for a proof of this. We will use this property to go from Equation (5) to Equation (6) in the next subsection. • So that the cipher cannot be broken by an exhaustive search for the prime factors of the modulus n, it is important that both p and q be very large primes. Finding the prime factors of 15Computer and Network Security by Avi Kak Lecture 12 a large integeris computationally harder than deter- mining its primality. • We also need to ensure that n is not factorizable by one of the modern integer factorization algorithms. More on that later in these notes. 16Computer and Network Security by Avi Kak Lecture 12 12.2.3: Proof of the RSA Algorithm • Weneedtoprovethatwhennisaproductoftwoprimespandq, then, in arithmetic modulo n, the exponents behave modulo the totientofn. Wewillprovethisassertionindirectlybyestablishing that when an exponent d is chosen as a mod φ(n) multiplicative inverse of another exponent e, then the following will always be e×d true M ≡M (modn). • UsingthedefinitionsofdandeaspresentedinSection12.2,since the integerd is the multiplicative inverse of the integere modulo the totient φ(n), we obviously have e×d ≡ 1 (mod φ(n)) (4) This implies that there must exist an integer k so that e×d − 1 ≡ 0 (mod φ(n)) = k×φ(n) (5) • It must then obviously be the case that φ(n) is a divisor of the expressione×d− 1. Butsinceφ(n) = φ(p)×φ(q),thetotients 17Computer and Network Security by Avi Kak Lecture 12 φ(p) and φ(q) must also individually be divisors of e×d − 1. That is φ(p) (e×d − 1) and φ(q) (e×d − 1) (6) The notation ‘’ to indicate that its left argument is a divisor of the right argument was first introduced at the end of Section 5.1 in Lecture 5. • Focusing on the first of these assertions, sinceφ(p) is a divisor of e×d − 1, we can write e×d − 1 = k φ(p) = k (p − 1) (7) 1 1 for some integer k . 1 • Therefore, we can write for any integer M: e×d e×d− 1 + 1 k (p− 1) 1 M modp = M modp = M ×M modp (8) • Now we have two possibilities to consider: Since p is a prime, it must be the case that either M and p are coprimes or that M is a multiple of p. 18Computer and Network Security by Avi Kak Lecture 12 – Let’s first consider the case when M and p are coprimes. By Fermat’sLittleTheorem(presented in Section 11.2ofLecture 11), since p is a prime, we have p− 1 M ≡ 1 (mod p) Since this conclusion obviously extends to any power of the left hand side, we can write k (p− 1) 1 M ≡ 1 (mod p) Substituting this result in Equation (8), we get e×d M modp = M modp (9) – Now let’s consider the case when the integer M is a multiple of the primep. Now obviously,M modp = 0. Thiswill also k be true for M raised to any power. That is, M modp = 0 for any integer k. Therefore, Equation (9) will continue to be true even in this case. • From the second assertion in Equation (6), we can draw an iden- tical conclusion regarding the other factor q of the modulus n: e×d M modq = M modq (10) 19Computer and Network Security by Avi Kak Lecture 12 • WeestablishedinSection12.2.2that,whenpandq arecoprimes, for any integers a and b if we have a≡b (mod p) and a≡b (mod q), then it must also be the case that a≡ b (mod pq). ApplyingthisconclusiontothepartialresultsshowninEquations (9) and (10), we get e×d M modn = M modn (11) 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.