Cryptography

Cryptography: Modular Arithmetic

Topics

Introduction

In modular arithmetic, integer numbers "wrap around" upon reaching a certain value called the modulus. An example is in the 12-hour clock. If the time is 7:00 now, then 8 hours later it will be 3:00 because 7 + 8 = 15, 15 - 12 = 3.

Congruence

Modular arithmetic is based on the congruence relation. Two numbers a and b are congruent modulo n if their difference a − b is an integer multiple of n. This is written as

a ≡ b (mod n).

(1)

The arithmetic operations like addition and multiplication are carried over to the respective congruences, e.g.
if

a₁ ≡ b₁ (mod n).

a₂ ≡ b₂ (mod n).

then

a₁ ⋅ a₂ ≡ b₁ ⋅ b₂ (mod n)

k⋅ a₁ ≡ k ⋅ b₁ (mod n).

In general, we cannot cancel a common multiplicative factor from a congruence. For example, it is:

7 ⋅ 2 ≡ 12 ⋅ 2 (mod 10) = 4

but after cancelling 2 we get:

7 ≢ 12 (mod 10).

However, if k is coprime with n then it can be cancelled:

k ⋅ a ≡ k ⋅ b (mod n)

(2a)

implies

a ≡ b (mod n)

(2b)

Eq. (2a) says that n divides k ⋅ a - k ⋅ b = k ⋅ (a -b). Since n and k have no common multiplicative factors, n must divide a - b, so eq. (2b) follows.

The following useful property will be applied in the public key cryptography. If

(3a)

a ≡ b (mod n)

(3b)

a ≡ b (mod m)

and n and m are coprime, then

a ≡ b (mod m ⋅ n)

(4)

The proof is easy but tricky. Equations (3) can be written as

a - b = k₁ ⋅ n = k₂ ⋅ m

(5)

for some integers k₁ and k₂. Because n and m are coprime we know from the Bézout's idententity that there exist numbers x and y such that

1 = n ⋅ x + m ⋅ y

(6)

We multiply eq. (6) by a - b and substitute the expressions (5):

a - b = (a - b) ⋅ n ⋅ x + (a - b) ⋅ m ⋅ y

= k₂ ⋅ m ⋅ n ⋅ x + k₁ ⋅ n ⋅ m ⋅ y

= (k₂ ⋅ x + k₁ ⋅ y) ⋅ (m ⋅ n)

So, a - b is a multiple of n · m and the eq. (4) follows.

Integers modulo `n`

When we compute (mod n) it is sufficient to consider only the numbers 0, 1, .. n-1 because all other numbers are reduced to them via the congruence relation. The set of these "residues" Z_n is a mathematical structure called a ring. A ring provides the operations of addition and multiplication with the usual properties. It does not provide division. However, in the special case when n = prime p each number a in Z⁺_p = {1, .. p-1} has also an inverse with respect to multiplication that is denoted a^-1

a ⋅ a^-1 ≡ 1 (mod p) for a ≢ 0 (mod p)

(7)

because gcd(a, p) = 1. The inverse a^-1 can be computed using the Extended Euclidean Algorithm. So, the set Z_p provides also division and is a mathematical field, denoted by F_p or GF(p) (GF for Galois Field).

Fermat's Little Theorem

If p is a prime number and a is a natural number, a ≢ 0 (mod p), then

a^p-1 ≡ 1 (mod p).

(8)

Proof: consider the numbers

1⋅a, 2⋅a, 3⋅a, ... (p-1)⋅a

(9)

all (mod p). These numbers are different because if it were

k₁ ⋅ a = k₂ ⋅ a (mod p)

we could cancel a since a and p are coprime and get

k₁ = k₂

So, these p-1 numbers correspond to the numbers

1, 2, 3, ... (p-1)

(10)

in some order. Consequently the product of the numbers (9) equals the product of the numbers (10):

a^p-1 ⋅ (p-1)! ≡ 1 ⋅ (p-1)! (mod p)

Now we may cancel (p-1)! in GF(p) and get equation (8).

A simple corollary from equation (8) is:

a^p ≡ a (mod p) for every a

(11)

Euler's Φ Function

Euler's generalization of Fermat's Little Theorem is that for any modulus n

a^Φ(n) ≡ 1 (mod n)

(12)

provided that a and n are relatively prime. Here, Φ(n) is the count of numbers 0, 1, .. n-1 that are relatively prime to n. The proof is analogous to the proof of the Fermat's theorem. Notice that the Fermat's theorem is a special case of the Euler's theorem, because Φ(p) = p - 1 for a prime p.

The Euler's Φ function satisfies the following relation for coprime m and n (without proof):

Φ(n ⋅ m) = Φ(n) ⋅ Φ(m)

(13)