Elementary number theory in cryptography

A small transformation that can be undone

Suppose a classroom message is already represented by one of the integers 0 through 7. Transform x by multiplying by 3, adding 1, then keeping the remainder modulo 8. Message 2 becomes 3·2+1 = 7. To undo it, subtract 1 and multiply by 3 again: 3(7−1) = 18, whose remainder modulo 8 is 2.

That second multiplier works because 3·3 = 9 leaves remainder 1 modulo 8. The complete map below shows where every possible message goes. Predict whether two different messages can reach the same encoded number before revealing the inverse calculation.

Prepare the arithmetic and separate the three objects

Use the published Multiplication and division, Negative numbers and absolute value, and Powers, roots and the real number line lessons for products, signed differences and integer powers. Below, each needed fact about primes, common divisors and congruences is defined and proved before it is used.

A plaintext is the original message. A ciphertext is its transformed representation. A key specifies the transformation or its inverse. Here messages are integer representatives in a stated finite range. Turning a word, file or byte string into such numbers requires a separate encoding; two different texts must not accidentally be assigned the same representative.

Write ℤ for the integers. Write h | t if t = hk for an integer k, and h ∤ t otherwise. For a positive modulus N ≥ 2, x ≡ y (mod N) means N | (x−y). Each integer has one canonical residue in 0,…,N−1: divide with a remainder in that range. Congruence means equal residues, not equality of the original integers.

On a first reading, follow the reversible map and the small RSA calculation, then return to the integer-combination and prime-residue proofs. Keep the message-domain condition and the distinction between recovery and secrecy in view throughout.

An integer combination supplies the inverse

For an integer a and N ≥ 2, gcd(a,N) is the greatest positive integer dividing both. Such divisors exist and form a finite list because they divide N. The pair is coprime when this greatest common divisor is 1. An inverse of a modulo N is an integer u satisfying au ≡ 1 (mod N).

Euclidean division writes A = qB+r for nonnegative A and positive B, with 0 ≤ r < B. A common divisor of A,B divides B,r by subtracting qB; a common divisor of B,r divides A by adding qB. Repeating (A,B) → (B,r) preserves common divisors, and positive remainders strictly decrease until one is zero. The last nonzero value is the gcd.

Start with N = 0·a+1·N and |a| = s·a+0·N, where s is 1 for a ≥ 0 and −1 for a < 0. Every new remainder is the difference of two integer combinations, so the final gcd has form ua+vN with integer coefficients. For a = 0, the identity is N = 0·a+1·N. Thus the calculation supplies both the gcd and its integer-combination identity.

If the gcd is 1, ua+vN = 1 gives au ≡ 1, hence an inverse. If an inverse exists, au−1 is a multiple of N, so every common divisor of a,N divides 1; the gcd must be 1. Thus an inverse exists exactly for a coprime multiplier.

If gcd(a,N) = 1 and N | at, multiply ua+vN = 1 by t. Both terms of t = uat+vNt are multiples of N, so N | t. This cancellation argument will also justify the prime-residue proof below. Modular addition and multiplication preserve congruence because sums of divisible differences, and xy−x′y′ = y(x−x′)+x′(y−y′), remain divisible by N. Repeated multiplication gives the same rule for positive integer powers.

The multiplier decides whether an affine map is reversible

An affine residue map has form y ≡ ax+b (mod N), where a,b are fixed integers and x is canonical. If a has inverse u, decoding by x ≡ u(y−b) returns the input: u(ax+b−b) ≡ x. Each canonical ciphertext has exactly one canonical preimage. Conversely, equal outputs imply a(x−x′) ≡ 0, so cancellation gives equal canonical inputs.

If g = gcd(a,N) > 1, inputs 0 and N/g are distinct canonical residues with the same output. Their output difference is aN/g, a multiple of N because g divides a. This proves failure of unique decoding for every noncoprime multiplier, not merely for one drawing. The offset b cannot remove a collision.

For a = 2,b = 1,N = 8, messages 0 and 4 both encode as 1. No function receiving only ciphertext 1 can return both different originals. In the reversible a = 3 example, the complete outputs are 1,4,7,2,5,0,3,6: each residue appears once.

Reversibility alone is not secrecy. An observer who knows this affine key can compute the same inverse; even an unknown tiny key can be exhausted. A cipher that operates independently on repeated symbols also preserves repeated-symbol patterns. These facts concern the stated classroom map, not a claim that every cryptographic method is an affine cipher.

A public exponent and a decoding exponent have different roles

Choose two distinct positive primes p,q. A prime is an integer greater than 1 whose only positive divisors are 1 and itself. Set N = pq and T = (p−1)(q−1). Choose positive integers e,d with ed ≡ 1 (mod T). A coprime e,T admits such a d by the integer-combination identity. This convenient exponent condition is sufficient for our recovery proof, rather than a claim that it is the only possible decoding exponent. T is the product of the two prime decrements; the proof below explains why this choice works.

The arithmetic encryption rule sends a canonical message m to the canonical ciphertext c ≡ m^e (mod N). Decoding sends c to r ≡ c^d (mod N). The public pair is (N,e); the intended receiver retains the decoding exponent d. Our teaching tables expose all these tiny values so that the mathematics can be checked.

Take p = 3,q = 11. Then N = 33,T = 20. With e = 3, Euclidean divisions give 20 = 6·3+2, 3 = 1·2+1 and 2 = 2·1+0. Back substitution gives 1 = 3−(20−6·3) = 7·3−20. Therefore d = 7 works and ed = 21 = 1+20.

Message 7 encrypts to 7³ = 343 = 10·33+13, so c = 13. Decoding by the seventh power returns 7, as the next exact calculation shows. This one success is an example; the later proof must also cover every other message, including 0 and multiples of 3 or 11.

Keep intermediate residues small

Repeated squaring calculates a power without first writing the huge integer power. For 13^7 modulo 33, 13² = 169 ≡ 4 and 13⁴ ≡ 4² = 16. Since 7 = 4+2+1, combine 16·4·13: first 16·4 = 64 ≡ 31, then 31·13 = 403 ≡ 7. Every reduction is justified by the congruence product rule.

The tables record powers with exponents 1,2,4,… and identify which contributions are included. An available repeated square is not automatically a factor in the final product. All exponents in this lesson are positive, including the zero-message case 0^e = 0. No undefined 0⁰ or negative-power step is used.

Multiplication permutes the nonzero residues of a prime

Let p be prime and suppose p ∤ a. Their gcd is 1, because a positive common divisor of p is either 1 or p and the latter is excluded. Multiply the residues 1,2,…,p−1 by a modulo p. None becomes 0: cancellation from p | aj would force p | j, impossible for 1 ≤ j < p.

No two outputs coincide. If aj ≡ ak, cancellation gives j ≡ k; their canonical ranges force j = k. There are p−1 different nonzero outputs and only p−1 possible nonzero residues, so they are exactly 1,2,…,p−1 in some order. This is a permutation: an ordering that uses each element once.

Let F = 1·2···(p−1), the product also written (p−1)!. Each factor has an inverse modulo p, so their inverse product is an inverse of F. The output product is congruent to a^(p−1)F by multiplication, and is congruent to F because it is a reordered copy of the same factors. Multiplying by the inverse of F gives a^(p−1) ≡ 1 (mod p). This proves Fermat’s little theorem with its required prime and nonzero-residue conditions.

For a = 3,p = 7, the outputs are 3,6,2,5,1,4. They use every nonzero residue exactly once, so 3⁶ ≡ 1 modulo 7. If the modulus is composite, those conditions may fail: for a = 2,N = 8, output 0 occurs, other outputs collide and 2⁷ ≡ 0 rather than 1. The theorem does not assert the prime-exponent rule for arbitrary composite moduli.

Handle divisible messages before combining the prime checks

For distinct primes p,q and positive e,d with ed = 1+kT, T = (p−1)(q−1), the integer k is nonnegative because ed ≥ 1 and T > 0. Decoding an encrypted message is congruent to (m^e)^d = m^(ed) modulo N. We will prove m^(ed) ≡ m separately modulo each prime.

Modulo p, first handle p | m. Both m and m^(ed) have residue 0 because ed is positive. Otherwise Fermat’s theorem gives m^(p−1) ≡ 1. Since ed = 1+k(q−1)(p−1), write m^(ed) = m·(m^(p−1))^(k(q−1)); its residue is m. If that last exponent is zero, its base is nonzero and its value is 1. The same two-case argument works modulo q.

To combine the checks, let D = m^(ed)−m. We know p | D and q | D. Write D = pt. The distinct primes p,q are coprime, so cancellation from q | pt gives q | t. Thus pq | D, proving m^(ed) ≡ m (mod N). The two independent prime checks therefore determine the residue modulo their product.

Both the original message m and recovered representative r lie in 0,…,N−1. Congruence in that range forces equality, so r = m. It follows that encryption is a permutation of all N canonical messages: equal ciphertexts would decode to equal originals. The proof covers multiples of either prime and zero, as well as coprime messages.

In the model N = 33,e = 3,d = 7, message 3 is divisible by 3 but still returns correctly; message 11 uses the zero case modulo 11, and 0 uses both zero cases. The complete table verifies all 33 exact instances. The general proof, rather than this finite verification alone, establishes recovery for every admissible distinct-prime pair.

A collision or one failed message exposes an invalid rule

With N = 33 and e = 2, messages 1 and 32 both encrypt to 1 because 32 ≡ −1 and (−1)² = 1. Here gcd(2,20) = 2, so no inverse exponent modulo 20 exists. No decoder acting on that ciphertext alone can recover both originals.

Keeping e = 3 but choosing d = 3 gives ed = 9, which is not congruent to 1 modulo 20. Message 7 encrypts to 13 but the proposed decoder gives 13³ = 2197 ≡ 19 modulo 33. Some inputs, such as 0 or 1, still return; those successes do not establish all-message recovery.

Distinct primes are also essential for the stated theorem. If p = q = 3, N = 9 and the copied product T = (3−1)² = 4, choosing e = 5,d = 1 gives ed ≡ 1 modulo that T. Yet message 3 encrypts to 3⁵ ≡ 0 modulo 9 and decodes to 0. The two checks modulo 3 cannot imply divisibility by 9. This example is deliberately outside the distinct-prime key definition.

A recovery proof answers one question about the system

The all-message proof establishes correctness: the intended decoding rule reverses the arithmetic map. It does not establish that an observer cannot recover the message. Knowing p,q supplies T and then d by Euclidean division. Factoring 33 is immediate, so this particular public-key example conceals nothing from someone who inspects its tiny table.

Raw exponentiation is deterministic: equal message representatives give equal ciphertexts with the same key. For a small known message set, an observer can encrypt every candidate using the public key and compare with the intercepted ciphertext. The present table is precisely such a complete comparison.

It also preserves multiplication of representatives. If c₁ ≡ m₁^e and c₂ ≡ m₂^e, then c₁c₂ ≡ (m₁m₂)^e modulo N. For our key, 2 encrypts to 8 and 3 encrypts to 27. Their ciphertext product 216 has residue 18, which is also the encryption of 6. This useful arithmetic identity is not a message-integrity guarantee.

Actual RSA encryption schemes combine the exponentiation primitive with specified message encoding and padding. For example, RSAES-OAEP includes a random seed in its encoding. This lesson implements neither that scheme nor a digital-signature protocol. Larger numbers alone would not turn its bare residue maps into a complete secure system.

Predict reversibility, then inspect every row

Compare the affine collision with the invertible affine map, then examine valid RSA arithmetic, a wrong private exponent, an even public exponent and a repeated-prime countercase. Predict whether the selected message returns and whether that result applies to every message in the table.

For the prime example, predict whether multiplication can reach zero or duplicate an output. Every displayed map lists its whole finite domain; the formulas and proofs state exactly which conclusions extend beyond those cases.

Worked examples

Try it yourself

1. Encode message 5 under y ≡ 3x+1 (mod 8), then decode the result.

   Show the answer and reasoning

   5 encodes to 0, and decoding gives 3(0−1) ≡ 5 modulo 8.

   3·5+1 = 16 has residue 0. Negative −3 has canonical residue 5, so ciphertext zero need not mean the original was zero.

2. For y ≡ 2x+5 (mod 8), give two distinct messages with the same ciphertext.

   Show the answer and reasoning

   Messages 0 and 4 both encode to 5.

   The second integer output is 2·4+5 = 13 ≡ 5. Changing the offset preserves the difference 8 between those outputs.

3. Explain why 1 = 7·3−20 gives d = 7 for the N = 33,e = 3 example.

   Show the answer and reasoning

   It gives 3·7 ≡ 1 modulo 20, where 20 = (3−1)(11−1).

   The required inverse concerns the prime-decrement product, not modulus 33. The equality also verifies that 3 and 20 are coprime.

4. Compute the encryption of message 11 under e = 3,N = 33. Does the all-message proof apply?

   Show the answer and reasoning

   11 encrypts to 11 and recovers to 11. Yes, the proof includes it.

   11³ = 1331 = 40·33+11. Modulo 11 the zero branch applies; modulo 3 the nonzero branch applies. A shared factor with N does not exclude the message.

5. Can you use the stated prime theorem to infer 2⁷ ≡ 1 modulo 8? What is its actual residue?

   Show the answer and reasoning

   No: 8 is composite, and 2⁷ ≡ 0 modulo 8.

   The theorem requires a prime modulus and a multiplier not divisible by that prime. Replacing p with any positive integer is an unjustified change.

6. In the proof modulo prime p, why is cancelling F = 1·2···(p−1) justified?

   Show the answer and reasoning

   Every factor is nonzero modulo p and has an inverse; multiplying those inverses gives an inverse of F.

   No factor is divisible by p. The cancellation is multiplication by an existing inverse, not ordinary division by a residue without a condition.

7. With N = 33,e = 3,d = 3, message 7 encrypts to 13. What does the proposed decoder return?

   Show the answer and reasoning

   It returns 19, so the message is not recovered.

   13³ = 2197 = 66·33+19. Here ed = 9 is not congruent to 1 modulo 20; correct recovery of some other messages is not an all-message proof.

8. If distinct primes p,q both divide D, why does pq divide D?

   Show the answer and reasoning

   Write D = pt. Since q divides pt and p,q are coprime, cancellation gives q | t, so D is a multiple of pq.

   The integer-combination cancellation proof supplies the needed step. Repeating the same prime would not satisfy the coprimality condition.

9. If you silently reduce original integers 7 and 40 modulo 33 before encrypting, can the decoder distinguish them?

   Show the answer and reasoning

   No. Both reduce to canonical representative 7 and therefore have the same ciphertext.

   The all-message recovery statement concerns the stated input range 0,…,32. A separate encoding must preserve information about longer or out-of-range originals.

10. An observer knows that a message is one of 0,…,32 and knows the public key (33,3). Does the recovery proof prevent a candidate-table comparison?

    Show the answer and reasoning

    No. The observer can encrypt all 33 candidates and compare their ciphertexts.

    For this admissible arithmetic key the map is a permutation, so each matching ciphertext identifies one candidate. Correctness and secrecy are different claims.

11. Messages 2 and 3 encrypt to 8 and 27 under N = 33,e = 3. Compare the ciphertext product with the encryption of 6.

    Show the answer and reasoning

    8·27 ≡ 18 modulo 33, and 6³ ≡ 18 modulo 33.

    Exponentiation preserves multiplication of representatives. This identity is a property of the raw primitive, not an authentication or integrity proof.

What to carry forward

• An integer message domain and a reversible representation must be stated before arithmetic encryption can recover the original.
• An affine map is reversible exactly when its multiplier is coprime to the modulus; an offset cannot remove collisions.
• Integer combinations provide modular inverses and justified cancellation.
• Prime multiplication permutes all nonzero residues, proving the prime-exponent theorem with its conditions.
• Distinct-prime RSA arithmetic with ed ≡ 1 modulo (p−1)(q−1) recovers every canonical message, including zero and noncoprime messages.
• Repeated squaring preserves exact residues without constructing huge ordinary powers.
• Correct recovery, large numbers and raw exponentiation alone do not establish a secure encryption scheme.