Introduction to Quantum Physics and Information Processing

Information and Communication 187

Example 9.3.3. The popular RSA encryption scheme [59], invented in 1978

by Rivest, Shamir, and Adleman at MIT, is a public key system based on

the prime factorization of a large number N . While the system is not truly

unbreakable, its strength lies in the fact that the private key is computationally

hard to generate though the generation of the public key is easy.

The steps B follows to generate his public and private keys are as follows:

1. Randomly selects two large primes p, q.

2. Computes N = pq.

3. Randomly selects a small odd a coprime to (p − 1)(q − 1) = r.

4. Picks b such that ab mod r = 1.

5. Public key: N