Cryptography

Historical context: from simple ciphers to modern cryptography

Cryptography is about designing methods to keep information secret, authentic, and unaltered when others might be listening or tampering.

Historically, cryptography began with very simple number-based tricks:

• Caesar cipher: shift each letter a fixed number of positions in the alphabet (e.g. $A \mapsto D$, $B \mapsto E$, etc.). This can be described with modular arithmetic on numbers $0$–$25$.
• Substitution ciphers: replace each letter with another according to some secret rule.

These classical methods are easy to break with modern techniques, so modern cryptography relies heavily on number theory, especially on properties of integers and modular arithmetic that are hard to “undo” without special information.

In this chapter, we focus on the number-theoretic ideas that appear in cryptography and illustrate them using simple versions of real systems, especially RSA.

Basic goals of cryptography

Modern cryptography aims at several goals:

• Confidentiality: only intended recipients can read the message.
• Integrity: the message cannot be changed without detection.
• Authentication: you can verify who sent the message.
• Non-repudiation: a sender cannot plausibly deny having sent a particular message.

Number theory is especially central to confidentiality and authentication in many commonly used systems.

Symmetric vs public-key cryptography (number-theoretic perspective)

Cryptosystems can be grouped into two broad families.

Symmetric-key cryptography

Both parties share the same secret key. That key is used both to encrypt and to decrypt. Number theory is not always prominent here, but there are simple number-based examples.

A toy example: suppose the key is an integer $k$ and each letter $x$ (represented as $0$–$25$) is encrypted as
$$
E_k(x) \equiv x + k \pmod{26}.
$$
Decryption uses
$$
D_k(y) \equiv y - k \pmod{26}.
$$
This is just a more formal way of describing the Caesar cipher.

Real symmetric ciphers (like AES) do not rely directly on simple number-theoretic hardness; they use carefully designed bit-level operations and algebra over finite fields. Nevertheless, modular arithmetic and finite fields are foundational tools in their design and analysis.

Public-key (asymmetric) cryptography

Here each user has two keys:

• A public key, which anyone can know.
• A private key, which must be kept secret.

The keys are related mathematically, but in such a way that computing the private key from the public key is believed to be computationally hard without extra information.

Public-key cryptography is where elementary number theory plays a starring role. The most famous example is RSA, which is built from:

• Prime numbers.
• Modular arithmetic.
• Euler’s totient function and related ideas.

Core number-theoretic tools used in cryptography

We highlight some tools from number theory that appear repeatedly in cryptographic constructions.

Modular arithmetic as the basic “language”

Most cryptographic algorithms operate on integers modulo some number $n$:

• We write $a \equiv b \pmod{n}$ when $n$ divides $a-b$.
• Computations such as addition, multiplication, and exponentiation are taken “mod $n$”.

In cryptography, $n$ is often very large (hundreds or thousands of bits), and efficient computation of expressions like $a^b \bmod n$ is crucial.

Prime numbers and factorization

Many cryptosystems rely on the fact that:

• It is easy to multiply large primes.
• It appears to be very hard (for classical computers) to factor a large composite number into its prime factors.

For instance, given large primes $p$ and $q$, it is easy to compute
$$
n = p q.
$$
But given only $n$, no fast general algorithm is known that always finds $p$ and $q$ for very large $n$.

This asymmetry between easy and hard directions is exploited in RSA.

The Euclidean algorithm and modular inverses

Given integers $a$ and $n$, an integer $a^{-1}$ (a multiplicative inverse modulo $n$) is a number with
$$
a a^{-1} \equiv 1 \pmod{n}.
$$

Such an inverse exists precisely when $\gcd(a, n) = 1$, and it can be found efficiently using the extended Euclidean algorithm. This capability is essential in cryptography:

• In RSA, a private key is defined as a modular inverse of a certain exponent.
• In many protocols, computing $1/a \pmod{n}$ is as routine as division in ordinary arithmetic.

Euler’s totient function and Euler’s theorem

For a positive integer $n$, Euler’s totient function $\varphi(n)$ is the number of integers between $1$ and $n$ that are coprime to $n$.

Euler’s theorem says: if $\gcd(a, n) = 1$, then
$$
a^{\varphi(n)} \equiv 1 \pmod{n}.
$$

In cryptography, we use special cases such as:

• If $p$ is prime, then $\varphi(p) = p - 1$, and for $a \not\equiv 0 \pmod{p}$,
  $$
  a^{p-1} \equiv 1 \pmod{p}.
  $$
  This is also known as Fermat’s little theorem.

The security of RSA does not rely on Euler’s theorem being difficult; Euler’s theorem is a known identity. Instead, RSA’s security relies on the difficulty of certain related computational problems, such as factoring $n$ or finding $\varphi(n)$ when $n$ is given but its factorization is unknown.

RSA: a basic public-key cryptosystem

RSA is a widely known public-key scheme built directly on number-theoretic ideas. We present a simplified explanation to illustrate the connection with number theory.

Key generation (using primes and totients)

To create an RSA key pair, a user (say, Alice) does the following:

1. Choose two large primes $p$ and $q$.
2. Compute
   $$
   n = p q.
   $$
   The modulus $n$ will be part of both the public and private keys.
3. Compute Euler’s totient for $n$:
   $$
   \varphi(n) = (p-1)(q-1),
   $$
   using the fact that $p$ and $q$ are prime.
4. Choose a public exponent $e$ such that
   $$
   1 < e < \varphi(n)
   $$
   and $\gcd(e, \varphi(n)) = 1$.
5. Compute the private exponent $d$ as the modular inverse of $e$ modulo $\varphi(n)$:
   $$
   e d \equiv 1 \pmod{\varphi(n)}.
   $$

Then:

• Alice’s public key is $(n, e)$.
• Alice’s private key is $d$ (and knowledge of $p, q$ is also secret in practice).

The only obviously difficult step for an attacker is to determine $d$ from $(n, e)$ alone. That would typically require knowing $\varphi(n)$, which is easy to find if you know $p$ and $q$ (their product’s factorization), but believed hard otherwise.

Encryption and decryption (modular exponentiation)

To send a secret message, we work with integers modulo $n$.

• A message is converted to an integer $m$ with $0 \le m < n$ (by some agreed encoding).
• To encrypt, a sender (Bob) uses Alice’s public key:
  $$
  c \equiv m^e \pmod{n},
  $$
  obtaining a ciphertext $c$.
• To decrypt, Alice uses her private key:
  $$
  m \equiv c^d \pmod{n}.
  $$

The key property is that decryption recovers the original message:
$$
(m^e)^d \equiv m \pmod{n}.
$$

Why this works comes from Euler’s theorem and the way $d$ was chosen:

• Since $e d \equiv 1 \pmod{\varphi(n)}$, there exists an integer $k$ such that
  $$
  e d = 1 + k \varphi(n).
  $$
• Then
  $$
  m^{e d} = m^{1 + k \varphi(n)} = m \cdot m^{k \varphi(n)}.
  $$
• When $m$ is coprime to $n$ (which is usually arranged in practice),
  $m^{\varphi(n)} \equiv 1 \pmod{n}$ by Euler’s theorem, so
  $$
  m^{e d} \equiv m \cdot (1)^k \equiv m \pmod{n}.
  $$

This algebraic identity is straightforward, but reversing the process (finding $d$ without $p$ and $q$) is believed difficult.

A very small numerical RSA example

Real RSA uses very large primes; here is a tiny, insecure example purely to show the arithmetic.

1. Choose primes: $p = 5$, $q = 11$.
2. Compute $n = p q = 55$.
3. Compute $\varphi(n) = (5-1)(11-1) = 4 \cdot 10 = 40$.
4. Choose $e$ with $\gcd(e, 40) = 1$ and $1 < e < 40$. Let $e = 3$.
5. Find $d$ so that $e d \equiv 1 \pmod{40}$.
   We need d \equiv 1 \pmod{40}$. Trying small values,
   $$
   3 \cdot 27 = 81 \equiv 1 \pmod{40},
   $$
   so $d = 27$.

Public key: $(n, e) = (55, 3)$.

Private key: $d = 27$.

Suppose our message is $m = 7$.

• Encrypt:
  $$
  c \equiv 7^3 \pmod{55}.
  $$
  Compute ^2 = 49$, then ^3 = 7 \cdot 49 = 343$.
  3 \div 55 = 6$ remainder $, so
  $$
  c \equiv 13 \pmod{55}.
  $$
• Decrypt:
  $$
  m \equiv 13^{27} \pmod{55}.
  $$

To compute $13^{27} \pmod{55}$ efficiently, one uses repeated squaring and reduces modulo $55$ at each step. After carrying out the reductions (details omitted here), the result is
$$
13^{27} \equiv 7 \pmod{55},
$$
recovering the original message $m = 7$.

The whole procedure is just modular exponentiation, guided by number-theoretic identities.

In practice:

• $p$ and $q$ would be hundreds or thousands of bits long.
• $n$ could have 2048 or more bits.
• Efficient algorithms for modular exponentiation (using repeated squaring) make encryption and decryption feasible even with large numbers.

Hard problems underlying cryptography

The security of many cryptosystems is based on the assumption that certain number-theoretic problems are computationally hard for large inputs.

Relevant examples:

• Integer factorization problem: Given $n = p q$ with large primes $p, q$, find $p$ and $q$.
• Discrete logarithm problem (in some group): Given $g$ and $h$, find $x$ such that
  $$
  g^x = h
  $$
  (with the equation interpreted in a group, such as modulo a large prime).

RSA relies (in practice) on the hardness of factoring large $n$. Other systems, like Diffie–Hellman key exchange and some digital signature schemes, rely on the hardness of discrete logarithms in modular arithmetic or related structures.

The connection to number theory is direct:

• These problems are stated in the language of primes, modular exponentiation, and multiplicative groups.
• Number-theoretic algorithms are used both in constructing the schemes and in attacking them.

Simple number-theoretic authentication ideas

Beyond confidentiality, number theory also supports authentication and digital signatures.

A rough idea (simplified, inspired by RSA signatures):

• To “sign” a message represented by an integer $m$, a user with private key $d$ computes
  $$
  s \equiv m^d \pmod{n}.
  $$
• Anyone with the public key $(n, e)$ can verify the signature by checking whether
  $$
  s^e \equiv m \pmod{n}.
  $$

This works because of the same exponentiation identity used in RSA decryption. In practice, additional steps (like hashing) are included to make signatures secure and efficient, but the arithmetic core is again modular exponentiation with large integers.

Here, number theory ensures:

• Only someone who knows $d$ can create $s$ with the right property.
• Everyone can verify the property using the public key.

Other number-theoretic cryptographic constructions (overview)

Beyond RSA, number theory appears in many other cryptographic settings, including:

• Diffie–Hellman key exchange: uses exponentiation modulo a large prime (or in other groups) to allow two parties to agree on a shared secret over an insecure channel.
• Elliptic curve cryptography (ECC): builds groups from points on elliptic curves over finite fields; the security relies on versions of the discrete logarithm problem.
• Hash functions and pseudorandom generators (in some designs): use modular arithmetic and exponentiation to produce outputs that appear random and are hard to reverse.

While the exact structures differ, they all share a reliance on:

• Arithmetic in finite structures (like $\mathbb{Z}/n\mathbb{Z}$ or finite fields).
• The existence of operations that are easy to perform but hard to invert without special information.

Limits and future directions

Cryptography based on classical number theory (like RSA and many discrete-log systems) is believed to be vulnerable to quantum computers running algorithms that can efficiently factor integers or compute discrete logarithms.

This has motivated work on post-quantum cryptography, where new systems are designed to rely on different hard problems. However:

• Number theory still plays a conceptual and technical role.
• Understanding modular arithmetic, primes, and related topics remains essential for understanding both classic and modern cryptographic designs.

In summary, cryptography is one of the most important real-world applications of number theory. Ideas such as primes, modular arithmetic, Euler’s theorem, and multiplicative inverses are not just theoretical curiosities; they are the mathematical engines behind secure communication in the modern world.