the algorithmic core of RSA

RSA is the famous public-key scheme that lets anyone send you a secret using a key you publish openly, while only you can read it with a key you keep private. Stripped of protocol details, its core is a small recipe of modular arithmetic: you pick two large primes, derive a public exponent and a private exponent, and then encryption and decryption are each a single modular exponentiation. What makes it secure is a gap between two computational problems — multiplying primes is easy, but factoring their product back apart is believed to be hard.

Here is the arithmetic core. (1) Pick two large primes p and q (found using Miller-Rabin), and set n = p*q. (2) Compute phi = (p-1)*(q-1). (3) Choose a public exponent e coprime to phi (often 65537). (4) Compute the private exponent d as the modular inverse of e mod phi, using the extended Euclidean algorithm — so e*d = 1 mod phi. The public key is (n, e); the private key is d. To encrypt a message m (a number less than n), compute c = m^e mod n by fast modular exponentiation. To decrypt, compute m = c^d mod n. The reason decryption recovers the message is that (m^e)^d = m^(e*d) = m mod n, which follows from e*d = 1 mod phi together with Euler's/Fermat's theorem about exponents modulo n. Every step you need — generating primes, finding the inverse, exponentiating — is one of the number-theoretic algorithms in this field, which is why RSA is a perfect capstone for them.

Its security rests on an honest asymmetry, and it is important to state it carefully. Computing the public key is easy, and an attacker who could factor n = p*q into p and q could recompute phi and hence d and break the scheme — so RSA's safety depends on factoring large numbers being infeasible with known algorithms. That is a believed hardness assumption, not a proven theorem: no one has published a fast classical factoring algorithm, but none has been proven impossible either, and a large quantum computer running Shor's algorithm would factor efficiently and break RSA. This entry is about the arithmetic core only; real RSA also needs padding schemes and careful key handling, without which the textbook version is insecure — never deploy raw textbook RSA.