Gambling with Secrets: 8/8 (RSA Encryption)

Alice generates a public key she distributes freely like an open lock, keeping a corresponding private key secret that alone can decrypt messages encrypted with the public key.

Alice decrypts Bob’s ciphertext C by using her private key d to compute M = C^d mod n, recovering the original message through her secret trapdoor.

Bob encrypts his message M to Alice by using her public key (n, e) to compute ciphertext C through modular exponentiation, creating a locked message only Alice’s private key can open.

Euler’s totient function φ(n) counts how many integers between 1 and n share no common factors with n, providing the critical value Alice needs for calculating her RSA private key.

Euler’s theorem establishes the relationship between the totient function and modular exponentiation that enables RSA’s encrypt-decrypt cycle to recover original messages.

RSA’s security relies entirely on the computational difficulty of factoring large semiprimes—products of two primes—a problem that has remained unsolved efficiently for thousands of years.

Alice generates her RSA key pair by selecting a small public exponent e and computing the corresponding private exponent d using her secret knowledge of φ(n).

Alice computes the RSA modulus n by multiplying her two secret primes p and q, creating the public parameter defining the modular arithmetic space for all RSA operations.

Alice begins RSA key generation by selecting two large random prime numbers of similar size, which she multiplies to create the public modulus n forming the foundation of her key pair.

Ron Rivest, Adi Shamir, and Leonard Adleman independently rediscovered public-key encryption in 1977, creating RSA—the algorithm that became the most widely deployed cryptographic system in history.

Cryptographers design trapdoor functions where computing the output proves easy for anyone, but reversing the process remains computationally infeasible except for those possessing secret trapdoor information.