Public-Key Cryptography

Classical cryptography uses a shared secret key. Both sender and receiver must know the same secret information in advance.

Public-key cryptography introduced a radically different idea:

encryption uses a public key,
decryption uses a private key.

Anyone may encrypt messages using the public key, but only the holder of the private key can decrypt them.

The RSA cryptosystem, introduced by entity[“people”,“Ron Rivest”,“American cryptographer”], entity[“people”,“Adi Shamir”,“Israeli cryptographer”], and entity[“people”,“Leonard Adleman”,“American computer scientist”], was the first widely practical public-key cryptosystem.

RSA relies fundamentally on arithmetic properties of prime numbers and modular exponentiation.

Modular Arithmetic Background

RSA operates in the ring

\mathbb{Z}/n\mathbb{Z}.

Arithmetic is performed modulo a composite integer

n=pq,

where $p$ and $q$ are large primes.

The key mathematical principle behind RSA is Euler’s theorem.

(a,n)=1,

then



a^{\varphi(n)}\equiv1\pmod n

where

\varphi(n)

is Euler’s totient function.

When

n=pq

with distinct primes,

\varphi(n)=(p-1)(q-1).

This theorem makes modular inversion through exponentiation possible.

Key Generation

RSA key generation proceeds as follows.

Step 1. Choose Two Large Primes

Select large distinct primes

p,q.

These primes must remain secret.

Step 2. Form the Modulus

Compute

n=pq.

The integer $n$ becomes part of the public key.

Step 3. Compute the Totient

Compute

\varphi(n)=(p-1)(q-1).

This value must remain secret because knowledge of $\varphi(n)$ essentially reveals the factorization of $n$ .

Step 4. Choose a Public Exponent

Choose an integer

e

satisfying

1<e<\varphi(n), \qquad (e,\varphi(n))=1.

Common choices include

65537.

Step 5. Compute the Private Exponent

Find

d

such that

ed\equiv1\pmod{\varphi(n)}.

Thus

d=e^{-1}\pmod{\varphi(n)}.

The public key is

(n,e),

while the private key is

d.

Encryption

Suppose a message is represented as an integer

m, \qquad 0\leq m<n.

Encryption computes the ciphertext

c

using modular exponentiation:

c\equiv m^e\pmod n.

The sender needs only the public key.

Efficient modular exponentiation algorithms make this practical even for extremely large integers.

Decryption

The receiver computes

m\equiv c^d\pmod n.

Substituting the encryption formula gives

m^{ed}\pmod n.

Since

ed\equiv1\pmod{\varphi(n)},

there exists an integer $k$ such that

ed=1+k\varphi(n).

Euler’s theorem then yields

$$ m^{ed}

m^{1+k\varphi(n)}

m(m^{\varphi(n)})^k \equiv m\pmod n. $$

Thus decryption recovers the original message.

Correctness of RSA

The correctness of RSA depends fundamentally on modular arithmetic and Euler’s theorem.

The system works because exponentiation by $e$ and exponentiation by $d$ are inverse operations modulo $n$ .

The algebraic structure of

(\mathbb{Z}/n\mathbb{Z})^\times

makes this inversion possible.

Example with Small Numbers

Real RSA systems use enormous primes, but a small example illustrates the mechanism.

Choose:

p=61, \qquad q=53.

Then

n=3233,

and

\varphi(n)=3120.

Choose

e=17.

Compute $d$ satisfying

17d\equiv1\pmod{3120}.

One obtains

d=2753.

Suppose the message is

m=123.

Encryption gives

c\equiv123^{17}\pmod{3233}.

Decryption computes

m\equiv c^{2753}\pmod{3233}.

The original message is recovered.

Real systems use integers hundreds or thousands of bits long.

Security of RSA

RSA security depends primarily on the difficulty of factoring large integers.

If an attacker factors

n=pq,

then:

$\varphi(n)$ becomes known,
the private exponent $d$ can be computed.

Thus breaking RSA reduces essentially to integer factorization.

No efficient classical algorithm for factoring large RSA moduli is currently known.

Padding Schemes

Raw RSA encryption is insecure.

Deterministic encryption leaks structural information and is vulnerable to chosen-message attacks.

Practical RSA therefore uses padding schemes such as:

OAEP,
PKCS standards,
probabilistic encodings.

Padding introduces randomness and prevents many attacks.

Modern cryptographic security depends critically on correct padding.

Digital Signatures

RSA also supports digital signatures.

Instead of encrypting with the public key, one signs with the private key:

s\equiv m^d\pmod n.

Verification uses the public exponent:

m\equiv s^e\pmod n.

This proves that the signer possessed the private key.

Digital signatures are fundamental in secure communication and authentication systems.

Chinese Remainder Optimization

Decryption can be accelerated using the Chinese remainder theorem.

Instead of computing modulo $n$ , one computes separately modulo:

p \quad\text{and}\quad q.

This substantially speeds up modular exponentiation.

Most practical RSA implementations use CRT optimization.

Attacks on RSA

Many attacks target poorly implemented RSA systems.

Examples include:

Attack Type	Idea
Factoring attack	Factor $n$
Timing attack	Measure execution time
Padding oracle	Exploit padding structure
Small exponent attack	Abuse weak parameter choices
Side-channel attack	Use physical leakage

Thus practical security depends on careful implementation as well as theoretical mathematics.

Quantum Threat

RSA is vulnerable to quantum algorithms.

Shor’s algorithm can factor integers in polynomial time on a sufficiently powerful quantum computer.

If large fault-tolerant quantum computers become practical, RSA would become insecure.

This motivates the development of post-quantum cryptography.

Practical Importance

RSA became one of the foundational systems of internet security.

Applications include:

HTTPS,
digital certificates,
email encryption,
secure authentication,
software signing.

Although newer systems such as elliptic curve cryptography often provide better efficiency, RSA remains historically and practically significant.

Conceptual Importance

RSA demonstrates how deep number theory can produce practical technology.

The system combines:

prime numbers,
modular arithmetic,
Euler’s theorem,
fast exponentiation,
computational complexity.

Its security relies not on secrecy of algorithms but on the presumed computational hardness of factorization.

RSA therefore represents one of the clearest and most influential connections between pure mathematics and modern digital infrastructure.

RSA Cryptosystem