6.042/18.] Mathematics for Computer Science February 25, 2005 Srini devadas and Eric Lehman Notes for recitation 7 1 RSA In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a highly secure cryp- tosystem(called RSa)based on number theory. Despite decades of attack, no significant weakness has been found (Well, none that you and me would know.)Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted message need not meet beforehand to agree on a secret key. Rather, the receiver has both a secret key, which she guards closely, and a public key, which she distributes as widely as possible. To send her a message, one encrypts using her widely-distributed public key. Then she decrypts the message using her closely-held private key. The use of such a pub- lic key cryptography system allows you and Amazon, for example, to engage in a secure transaction without meeting up beforehand in a dark alley to exchange a key RSA Public-Key Encryption Beforehand The receiver creates a public key and a secret key as follows 1. Generate two distinct primes, p and q 2. Let n=p 3. Select an integer e such that gcd(e, (p-1(q-1)=1 The public key is the pair(e, n). This should be distributed widely 4. Compute d such that de= 1(mod (p-1)(q-1)) The secret key is the pair(d, n). This should be kept hidde Encoding The sender encrypts message m to produce musing the public key n n rem n Decoding The receiver decrypts message m back to message m using the secret key n) rem n6.042/18.062J Mathematics for Computer Science February 25, 2005 Srini Devadas and Eric Lehman Notes for Recitation 7 1 RSA In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman proposed a highly secure cryp￾tosystem (called RSA) based on number theory. Despite decades of attack, no significant weakness has been found. (Well, none that you and me would know. . .) Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted message need not meet beforehand to agree on a secret key. Rather, the receiver has both a secret key, which she guards closely, and a public key, which she distributes as widely as possible. To send her a message, one encrypts using her widely­distributed public key. Then she decrypts the message using her closely­held private key. The use of such a pub￾lic key cryptography system allows you and Amazon, for example, to engage in a secure transaction without meeting up beforehand in a dark alley to exchange a key. RSA Public­Key Encryption Beforehand The receiver creates a public key and a secret key as follows. 1. Generate two distinct primes, p and q. 2. Let n = pq. 3. Select an integer e such that gcd(e, (p − 1)(q − 1)) = 1. The public key is the pair (e, n). This should be distributed widely. 4. Compute d such that de ≡ 1 (mod (p − 1)(q − 1)). The secret key is the pair (d, n). This should be kept hidden! Encoding The sender encrypts message m to produce m� using the public key: m� e = m rem n. Decoding The receiver decrypts message m� back to message m using the secret key: m = (m� ) d rem n