RSA Algorithm

Introduction

The RSA cryptosystem, named after its inventors Rivest, Shamir, and Adleman, is one of the first practical public-key encryption systems. Its security rests on the computational difficulty of factoring large integers—a problem that has resisted efficient solution for centuries.

In RSA, the encryption key can be made public without compromising security, because decryption requires knowledge of the prime factorization of a large number. This asymmetry between easy multiplication and hard factorization is the mathematical foundation of the system.

Understanding RSA requires familiarity with modular arithmetic, Euler's theorem, and the Chinese Remainder Theorem. These number-theoretic tools combine elegantly to create a practical and secure encryption method.

Mathematical Prerequisites

Euler's Totient Function

Euler's totient function ϕ(n) counts the integers from 1 to n that are coprime to n For a prime p

ϕ(p)=p−1

For the product of two distinct primes n=p*q

ϕ*(p*q)=ϕ(p)*ϕ(q)=(p−1)*(q−1)

Euler's Theorem

Euler's theorem generalizes Fermat's Little Theorem. If gcd(a,n)=1 then:

aϕ(n)≡1*(mod(n))

This theorem is the key to RSA: it allows us to compute inverses of exponents modulo ϕ(n)

Key Generation

RSA key generation proceeds as follows:

Choose two large distinct prime numbers p and q In practice, these are typically 1024 bits or larger each.

Compute the modulus n=p*q This will be part of both public and private keys.

Compute Euler's totient: ϕ(n)=(p−1)*(q−1)

Choose a public exponent e such that 1<e<ϕ(n) and gcd(e,ϕ(n))=1. Common choices are e=65537=2+1 or e=3.

Compute the private exponent d as the modular inverse of e modulo ϕ(n)

e*d≡1*(mod(ϕ(n)))

The public key is (n,e) and the private key is (n,d) The primes p and q must be kept secret and can be discarded after computing d.

Encryption and Decryption

Encryption

To encrypt a message m (represented as an integer with 0≤m<n ), compute the ciphertext:

c=me*mod(n)

This operation uses only the public key. Anyone can encrypt messages to the key owner.

Decryption

To decrypt the ciphertext c compute:

m=cd*mod(n)

This requires the private key. Only the key owner can decrypt.

Correctness Proof

We must verify that decryption recovers the original message: cd≡m*(mod(n))

Substituting c=me

cd=(me)d=m(e*d)

Since e*d≡1*(mod(ϕ(n))) we can write e*d=1+k*ϕ(n) for some integer k Thus:

m(e*d)=m(1+k*ϕ(n))=m⋅(mϕ(n))k

If gcd(m,n)=1 Euler's theorem gives mϕ(n)≡1*(mod(n)) so:

m(e*d)≡m⋅1≡m*(mod(n))

The case when gcd(m,n)≠1 (i.e., m is divisible by p or q can be handled separately using the Chinese Remainder Theorem, confirming that decryption works for all valid messages.

Security of RSA

The security of RSA relies on the difficulty of the integer factorization problem. Given n=p*q finding p and q is believed to be computationally infeasible for sufficiently large primes.

If an attacker could factor n they could compute ϕ(n) and then find d from e The best known classical algorithms for factoring have sub-exponential but super-polynomial complexity.

The number field sieve, the fastest known classical algorithm, factors an nbit integer in approximately:

O*(exp(c⋅n(1/3)*(ln(n))(2/3)))

For 2048-bit keys, this is astronomically large. However, Shor's quantum algorithm can factor in polynomial time, making RSA vulnerable to future quantum computers.

Efficient Computation

Modular Exponentiation

Computing me*mod(n) directly is infeasible for large exponents. Instead, we use repeated squaring (binary exponentiation). Express e in binary and compute successive squares modulo n.

This reduces the number of multiplications from e to O*((log_)(e)) making encryption and decryption practical.

Chinese Remainder Theorem Optimization

Decryption can be accelerated using the Chinese Remainder Theorem. Since n=p*q we compute:

(m_p)=c(d*mod((p−1)))*mod(p),(m_q)=c(d*mod(q−1))*mod(q)

Then combine using CRT. Since computations modulo p and q involve numbers half the size, this is about 4 times faster than direct computation modulo n.

Digital Signatures

RSA can also create digital signatures. To sign a message m the signer computes:

s=md*mod(n)

Anyone can verify the signature using the public key:

m=se*mod(n)

Only the private key holder can produce valid signatures, but anyone can verify them. In practice, we sign a hash of the message rather than the message itself.

Summary

RSA is a public-key cryptosystem based on the difficulty of factoring large integers. Key generation involves choosing primes p,q computing n=p*q and ϕ(n)=(p−1)*(q−1) then finding e and d with e*d≡1*(mod(ϕ(n)))

Encryption computes c=me*mod(n) decryption computes m=cd*mod(n) Euler's theorem guarantees correctness. RSA also enables digital signatures by reversing the roles of e and d.