MATA02H3 Lecture Notes - Lecture 5: Euclidean Algorithm, Public-Key Cryptography, Ron Rivest

• School: UTSC
• Department: Mathematics
• Course: MATA02H3
• Professor: Parnesh Grover

Document Summary

All classical ciphers, including shift ciphers, are private key cryptosystems. Knowing the encryption key allows one to quickly determine the decryption key. All parties who wish to communicate using a private key cryptosystem must share the key and keep it a secret. In public key cryptosystems, first invented in the 1970s, knowing how to encrypt a message does not help one to decrypt the message. Therefore, everyone can have a publicly known encryption key. The only key that needs to be kept secret is the decryption key. The rsa cryptosystem: ronald rivest, adi shamir, and leonard adelman (from. Suppose public key is (e, n) and her decryption key is d, so ed 1. If somehow we compute the factorization n = pq, then we can compute (n) = (p 1)(q 1) and hence compute d. thus, if we can factor n then we can break the corresponding rsa public-key cryptosystem.