Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 68 ยท Number Theory

Number Theory in Cryptography

See Fermat's little theorem, the Chinese remainder theorem, toy RSA, a Diffie-Hellman exchange and the Luhn and ISBN checksums, all with tiny numbers in Python.

Modular arithmetic looks like a classroom curiosity until you notice what it makes possible: two strangers can agree on a secret over a public channel, and anyone can lock a message that only one person can open. These ideas rest on a few theorems about remainders. In this lesson you will meet those theorems and run miniature versions of the famous algorithms.

Everything here is for learning only. Toy examples use tiny numbers and no padding, so they can be broken in an instant. Never use code from this lesson to protect real data; use a vetted library such as the ones in your language's standard cryptography package.

You will need Modular Arithmetic and the extended Euclidean algorithm from GCD, LCM and the Euclidean Algorithm.

Fermat's little theorem

If p is prime and p does not divide a, then

a^(pโˆ’1) โ‰ก 1 (mod p)

Multiplying all of 1, 2, ..., p โˆ’ 1 by a just shuffles them modulo p, so the products of both lists are equal and a^(pโˆ’1) must be 1. A useful consequence is that a^(pโˆ’2) is the modular inverse of a when p is prime.

The theorem gives a quick test for compositeness: if you find a coprime to n with a^(nโˆ’1) โ‰ข 1, then n is not prime. The converse fails. Some composite numbers, called Carmichael numbers, pass the test for every coprime base. The smallest is 561 = 3 ยท 11 ยท 17.

Python Fermat's little theorem and its exceptions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All twelve powers equal 1 as the theorem promises. The Carmichael list below 2,000 is 561, 1105 and 1729. Base 3 shows a different result for 561 only because gcd(3, 561) = 3, so 3 is not coprime to 561 and the theorem makes no claim there.

The Chinese remainder theorem

An old puzzle asks for a number that leaves remainder 2 when divided by 3, 3 when divided by 5, and 2 when divided by 7. The Chinese remainder theorem (CRT) says that if the moduli mโ‚, mโ‚‚, ..., m_k are pairwise coprime, then the system x โ‰ก rโ‚ (mod mโ‚), ..., x โ‰ก r_k (mod m_k) has exactly one solution modulo M = mโ‚ ยท mโ‚‚ ยทยทยท m_k.

The proof is constructive. Suppose x already satisfies the first i equations modulo M_i. To add the next equation x โ‰ก r (mod m), look for x + M_iยทt with t chosen so that the new congruence holds: t โ‰ก (r โˆ’ x) ยท M_iโปยน (mod m). The inverse exists because M_i and m are coprime.

Python Solving a system with CRT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solution is 23, unique modulo 105. CRT lets a program split work on a huge modulus into independent work on small ones, and it speeds up RSA decryption in real implementations.

Toy RSA

RSA is a public-key system: anyone can encrypt with a public key, but only the holder of a private key can decrypt. The recipe has five steps.

  1. Pick two distinct primes p and q and compute n = p ยท q.
  2. Compute ฯ† = (p โˆ’ 1)(q โˆ’ 1).
  3. Choose an exponent e coprime to ฯ†. This pair (n, e) is the public key.
  4. Compute d = eโปยน mod ฯ† with the extended Euclid algorithm. The pair (n, d) is the private key.
  5. Encrypt a number m < n as c = m^e mod n; decrypt as m = c^d mod n.

Why does it work? Since e ยท d โ‰ก 1 (mod ฯ†), we have e ยท d = 1 + kยทฯ†, and Euler's generalization of Fermat's theorem says m^ฯ† โ‰ก 1 (mod n) for m coprime to n, which gives (m^e)^d = m ยท (m^ฯ†)^k โ‰ก m. (It also holds for m not coprime to n, by CRT and Fermat on each prime.)

Security comes from the difficulty of recovering p and q from n when the primes are hundreds of digits long. With p = 61 and q = 53 anyone can factor 3233 in a blink.

Python RSA with tiny primes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With n = 3233 the private exponent is 2753 and the message 65 encrypts to 2790. Encrypting each letter separately, as in the second half, is a toy shortcut that real systems never use, because identical letters give identical ciphertexts and patterns leak. The last lines show the weakness: trial division breaks the key at once.

A Diffie-Hellman exchange

Diffie-Hellman lets two people create a shared secret while talking in public. They agree on a prime P and a base g. Alice picks a secret a and sends A = g^a mod P; Bob picks a secret b and sends B = g^b mod P. Alice computes B^a mod P and Bob computes A^b mod P, and both equal g^(ab) mod P. An eavesdropper sees P, g, A, B but would need to solve the discrete logarithm problem (find a from g^a mod P) to learn the secret. For large P no fast method is known.

Key exchange in public

Agree openly A prime P and a base g.
Keep secrets Alice keeps a, Bob keeps b.
Send powers g^a and g^b travel in public.
Same key Both get g^(ab) mod P.
1 / 2
Python Diffie-Hellman with P = 23

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both sides end with the shared value 2. The last lines show why real prime sizes matter: with P = 23 there are only 23 exponents to try.

Checksums: Luhn and ISBN

Not every use of number theory is about secrecy. A checksum is an extra digit that catches typing mistakes. The Luhn algorithm, used on payment card numbers, doubles every second digit from the right (subtracting 9 if the result exceeds 9), adds everything up, and requires the total to be divisible by 10. It detects any single wrong digit and most swaps of neighbours. An ISBN-10 book number uses a weighted sum: with weights 10, 9, ..., 1 the total must be divisible by 11, and the symbol X stands for 10 in the last place.

These are error-detecting codes, not security: they are public and anyone can compute a valid number. A cryptographic hash such as SHA-256 is different in kind: it maps any input to a fixed-size fingerprint that is easy to compute but practically impossible to reverse, and changing one letter of the input changes the output completely.

Python Luhn, ISBN and a hash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Changing the last digit of the card number makes luhn_ok fail, and one flipped letter in "hello" produces an unrelated SHA-256 prefix (2cf24dba5fb0a30e versus fdd7585e08c4e2af).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does Fermat's little theorem say for a prime p and a not divisible by p?

    The theorem states a^(p-1) = 1 (mod p). Equivalently, a^(p-2) is the inverse of a.
  2. 2. Why is 561 interesting?

    561 = 3 * 11 * 17 is the smallest Carmichael number, so the Fermat test alone cannot prove primality.
  3. 3. The Chinese remainder theorem guarantees a unique solution modulo M when the moduli are:

    When the moduli are pairwise coprime, the system has exactly one solution modulo their product.
  4. 4. In RSA, which values make up the public key?

    The public key is (n, e). The private exponent d, and the primes p and q, must stay secret.
  5. 5. Why is the Diffie-Hellman example with P = 23 not secure?

    With a tiny P the discrete logarithm can be found by brute force. Real systems use enormous primes.

Summary

  • Fermat's little theorem: a^(pโˆ’1) โ‰ก 1 (mod p) for prime p and a coprime to p; Carmichael numbers like 561 fool the converse.
  • The Chinese remainder theorem solves systems of congruences with pairwise coprime moduli, and pow(M, -1, m) makes it a few lines of code.
  • RSA encrypts with m^e mod n and decrypts with c^d mod n, where d is the inverse of e modulo (p โˆ’ 1)(q โˆ’ 1).
  • Diffie-Hellman agrees on g^(ab) mod P; its security relies on the discrete logarithm problem for large P.
  • Luhn and ISBN checksums catch typing errors; cryptographic hashes are a different tool. Toy code is never for real security.

Next: Sequences and Summations, the start of the chapter on sums and recurrences.