To understand how HE schemes work, we will explore the RSA algorithm. First, we must review some essential mathematical concepts behind encryption schemes.
Number theory
Primes and factorization
The journey into number theory starts with the basic building blocks of integers and their relationships, such as divisibility and the idea of prime numbers.
Definition (Set of integers): The set of integers is denoted as \mathbb{Z} = {..., -2, -1, 0, 1, 2, ...}.
Definition (Divisibility): An integer a is said to divide an integer b if there exists an integer c such that b = a \cdot c. In this case, we write a \mid b.
For example, 6 \mid 18 holds because 18 = 6 \cdot 3. If a \nmid b, then a does not divide b.
Theorem (Division Algorithm): For any integers a and b > 0, there exist unique integers q (quotient) and r (remainder) such that:
a = q \cdot b + r, \quad 0 \leq r < b
For example, dividing 17 by 5 gives q = 3 and r = 2, as 17 = 3 \cdot 5 + 2.
Prime numbers are the building blocks of integers:
Definition (Integer primality): A number p > 1 is prime if its only divisors are 1 and p.
For instance, 7 is prime, while 12 is composite because 12 = 2 \cdot 6.
Theorem (Fundamental Theorem of Arithmetic): Every integer n > 1 can be written as a product of prime powers, and this factorization is unique up to the order of the factors:
n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}
where p_i are distinct primes, i and e_i are positive integers, and k is the number of distinct prime factors of n.
For example, 84 = 2^2 \cdot 3 \cdot 7 demonstrates this principle.
Remark: It is straightforward to compute the product of two large prime numbers p and q. However, the reverse operation, determining the original prime factors from their product n = p \cdot q, is computationally difficult. This difficulty arises from the lack of efficient algorithms for factorizing large integers. The best-known algorithms, such as the General Number Field Sieve (GNFS), have exponential time complexity for large inputs. This asymmetry makes factoring infeasible within a reasonable timeframe as the bit length of p and q increases. Moreover, the factors p and q are typically chosen to be large primes of similar bit length to avoid simple heuristics or optimizations. This problem is so significant that it has its own name, the Integer Factorization Problem (denoted $ [n] $), and it underpins the security of many public-key cryptosystems, including RSA, ensuring that decrypting or compromising encrypted data without the private key remains practically impossible.
Greatest common divisor
To explore relationships between numbers, we often need their greatest common divisor, e.g. to simplify a fraction or to synchronize cycles.
Definition (Greatest common divisor, GCD): The greatest common divisor of two integers a and b, denoted \gcd(a, b), is the largest integer dividing both a and b.
For example, \gcd(12, 18) = 6.
Definition (Relatively primality of integers): Two integers are relatively prime if their GCD is 1.
Finding the GCD is efficient with the Euclidean algorithm:
Theorem (Euclidean Algorithm): The GCD of two integers a and b, where at least one is nonzero, can be computed using the recursive relation:
\gcd(a, b) = \gcd(b, a \pmod{b}).
This recursive formula stems from the property of divisors:
\gcd(a, b) = \gcd(b, a - q \cdot b)
where q is the quotient when a is divided by b. Since a - q \cdot b = a \pmod{b}, the recursion simplifies to:
\gcd(a, b) = \gcd(b, r)
where r = a \pmod{b}.
For example, consider the integers 385 and 364. Using the Euclidean Algorithm:
\begin{aligned}
\gcd(385, 364) &= \gcd(364, 385 \pmod{364}) = \gcd(364, 21), \\
\gcd(364, 21) &= \gcd(21, 364 \pmod{21}) = \gcd(21, 7), \\
\gcd(21, 7) &= \gcd(7, 21 \pmod{7}) = \gcd(7, 0) = 7.
\end{aligned}
Thus, \gcd(385, 364) = 7.
The Euclidean Algorithm can be applied to any integers, positive or negative, as long as at least one of the integers is nonzero. The process uses the relationship \gcd(a, b) = \gcd(b, a \pmod{b}), where the modulus operation a \pmod{b} always returns a remainder r satisfying 0 \leq r < |b|. This means the algorithm effectively reduces to positive remainders during the recursion, even if a or b starts as a negative number.
Example with negative integers, \gcd(-48, 18):
\begin{aligned}
\gcd(-48, 18) &= \gcd(18, -48 \pmod{18}) = \gcd(18, 12), \\
\gcd(18, 12) &= \gcd(12, 18 \pmod{12}) = \gcd(12, 6), \\
\gcd(12, 6) &= \gcd(6, 12 \pmod{6}) = \gcd(6, 0) = 6.
\end{aligned}
The sign of the integers does not affect the result, as \gcd(-a, b) = \gcd(a, b).
The GCD is not only useful for determining divisibility but also plays a key role in finding linear combinations of integers. This is formalized in Bézout’s Identity:
Theorem (Bézout’s Identity): For any integers a and b, there exist integers x and y such that:
\gcd(a, b) = ax + by.
The integers x and y are called Bézout coefficients.
These coefficients are not unique; for any integer k, another pair (x', y') can be generated as:
\begin{aligned}
x' &= x + k \cdot \frac{b}{\gcd(a, b)}, \\
y' &= y - k \cdot \frac{a}{\gcd(a, b)}.
\end{aligned}
The Extended Euclidean Algorithm builds upon the Euclidean Algorithm to compute the Bézout coefficients x and y. It works by tracing back the remainders obtained during the GCD computation:
Algorithm (Extended Euclidean Algorithm):
Input integers a and b.
Initialize r_0, r_1, s_0, s_1, t_0, t_1, i:
- r_0 = a, r_1 = b
- s_0 = 1, s_1 = 0
- t_0 = 0, t_1 = 1
- i = 1.
While r_i \neq 0:
- Compute quotient q = r_{i-1} \div r_i
- r_{i+1} = r_{i-1} - q \times r_i
- s_{i+1} = s_{i-1} - q \times s_i
- t_{i+1} = t_{i-1} - q \times t_i
- i = i + 1.
Return GCD, x, and y where ax + by = \gcd(a,b):
- GCD = r_{i-1}
- (x,y) = (s_{i-1}, t_{i-1}).
Below it is shown how the Extended Euclidean Algorithm works step by step with a = 48 and b = 18:
Initialize:
- r_0 = 48, r_1 = 18
- s_0 = 1, s_1 = 0
- t_0 = 0, t_1 = 1
- i = 1.
First iteration (i = 1):
- q = r_0 \div r_1 = 48 \div 18 = 2 (quotient)
- r_2 = r_0 - q \times r_1 = 48 - 2 \times 18 = 12
- s_2 = s_0 - q \times s_1 = 1 - 2 \times 0 = 1
- t_2 = t_0 - q \times t_1 = 0 - 2 \times 1 = -2.
Second iteration (i = 2):
- q = r_1 \div r_2 = 18 \div 12 = 1
- r_3 = r_1 - q \times r_2 = 18 - 1 \times 12 = 6
- s_3 = s_1 - q \times s_2 = 0 - 1 \times 1 = -1
- t_3 = t_1 - q \times t_2 = 1 - 1 \times (-2) = 3.
Third iteration (i = 3):
- q = r_2 \div r_3 = 12 \div 6 = 2
- r_4 = r_2 - q \times r_3 = 12 - 2 \times 6 = 0
- s_4 = s_2 - q \times s_3 = 1 - 2 \times (-1) = 3
- t_4 = t_2 - q \times t_3 = -2 - 2 \times 3 = -8.
Since r_4 = 0, we stop and return:
- GCD = r_3 = 6
- x = s_3 = -1
- y = t_3 = 3.
Therefore:
- \gcd(48,18) = 6.
- The coefficients are x = -1 and y = 3.
- We can verify: 48 \times (-1) + 18 \times 3 = -48 + 54 = 6.
So the equation ax + by = \gcd(a,b) is satisfied: 48(-1) + 18(3) = 6.
This identity is critical in RSA for computing modular inverses, which rely on finding such coefficients.
Modular arithmetic
Modular arithmetic is the backbone of cryptographic systems like RSA, enabling secure and efficient encryption, decryption, and key exchange. By confining computations to equivalence classes, modular arithmetic limits operations to a manageable finite set of remainders \{0, 1, \dots, n-1\}. This reduction simplifies calculations with large numbers, allowing consistent and efficient arithmetic even when working with very large exponents or products, as is typical in cryptography. For example, modular exponentiation uses this confinement to ensure that intermediate computations remain bounded and practical, avoiding the inefficiencies of dealing with massive numbers directly.
Congruence
Definition (Congruence): For integers a, b, and n with n > 0, a is congruent to b modulo n, written a \equiv b \pmod{n}, if n \mid (a - b).
For example, 23 \equiv 8 \pmod{5} because 5 \mid (23 - 8).
This congruence partitions integers into congruence classes modulo n, grouping numbers that share the same remainder when divided by n. These equivalence classes reduce infinitely many integers to a manageable finite set.
Theorem (Equivalence relation): Congruence modulo n satisfies the three fundamental properties of an equivalence relation:
Reflexivity: a \equiv a \pmod{n}, since n \mid (a - a) = 0.
Symmetry: If a \equiv b \pmod{n}, then b \equiv a \pmod{n}, because n \mid (a - b) implies n \mid (b - a).
Transitivity: If a \equiv b \pmod{n} and b \equiv c \pmod{n}, then a \equiv c \pmod{n}, as n \mid (a - b) and n \mid (b - c) imply n \mid (a - c).
These properties ensure that modular arithmetic forms a consistent framework for mathematical operations.
Theorem (Congruence and remainders): From the Division Algorithm, we have r = a \pmod{b}, meaning a \equiv b \pmod{n} if and only if a and b share the same remainder when divided by n. Moreover, both a and b are congruent to that common remainder:
a \equiv b \pmod{n} \implies a \pmod{n} = b \pmod{n}.
This relationship provides a computational foundation for modular arithmetic.
Every integer modulo n can be uniquely represented by a remainder within a specific range. This principle is foundational to modular arithmetic, as it ensures that each congruence class has a single canonical representative. The following theorem formalizes this idea:
Theorem (Unique representation): For n \geq 2, every integer is congruent modulo n to exactly one element of the set \{0, 1, 2, \dots, n-1\}.
The notion of congruence naturally leads to the concept of a congruence class, which groups integers that share the same remainder when divided by n. These classes partition the set of integers into distinct subsets, each representing one equivalence class under congruence modulo n.
Definition (Congruence class): A congruence class modulo n, denoted [a]_n, is the set of integers equivalent to a \pmod{n}:
[a]_n = \{a + kn \mid k \in \mathbb{Z}\}.
These classes partition \mathbb{Z} into n disjoint subsets, which together form the set \mathbb{Z}_n, the set of equivalence classes modulo n. Each subset corresponds to a unique remainder in \{0, 1, \dots, n-1\}.
For example, modulo 3, the congruence classes are:
- [0]_3 = \{..., -3, 0, 3, 6, ...\},
- [1]_3 = \{..., -2, 1, 4, 7, ...\},
- [2]_3 = \{..., -1, 2, 5, 8, ...\}.
Thus, \mathbb{Z}_3 = \{[0]_3, [1]_3, [2]_3\}, representing all possible congruence classes modulo 3.
The concept of a congruence class provides a structured way to organize integers under modulo n. Each congruence class contains infinitely many integers that share the same modular properties. To simplify working with these classes, it is common to choose specific representatives for computations. The following definitions introduce the two most commonly used representatives:
Definition (Least positive representative): The least positive representative of a congruence class modulo n is the smallest nonnegative integer in the class, given by a \pmod{n}.
For example, consider modulo 5:
- For [7]_5, the least positive representative is 7 \pmod{5} = 2.
- For [-11]_5, the least positive representative is -11 \pmod{5} = 4.
Definition (Least magnitude representative): The least magnitude representative of a congruence class modulo n minimizes |r|, where -n/2 < r \leq n/2.
Again, for modulo 5:
- For [7]_5, the least magnitude representative is 2, as -5/2 < 2 \leq 5/2.
- For [-11]_5, the least magnitude representative is -1, as -5/2 < -1 \leq 5/2.
These representatives are key to simplifying modular arithmetic calculations and ensuring consistent results.
Addition and multiplication
In modular arithmetic, fundamental operations like addition and multiplication follow specific rules that maintain consistency within the modular system. These rules are formalized in the following theorem:
Theorem (Modular addition and multiplication): For integers a and b:
\begin{aligned}
(a + b) \pmod{n} &= ((a \pmod{n}) + (b \pmod{n})) \pmod{n}, \\
(a \cdot b) \pmod{n} &= ((a \pmod{n}) \cdot (b \pmod{n})) \pmod{n}.
\end{aligned}
When comparing \mathbb{Z} (integers) and \mathbb{Z}_n (integers modulo n), we find both similarities and key differences in their algebraic properties:
Similarities:
- Both have well-defined addition and multiplication operations.
- Zero has no multiplicative inverse in both systems.
- 1 (and -1 in \mathbb{Z} or its equivalent n-1 in \mathbb{Z}_n) always has a multiplicative inverse.
Differences:
- In \mathbb{Z}, only ±1 have multiplicative inverses.
- In \mathbb{Z}_n, any element a where \gcd(a,n)=1 has a multiplicative inverse.
- \mathbb{Z} is infinite, while \mathbb{Z}_n has exactly n elements.
- All operations in \mathbb{Z}_n are bounded by n, while operations in \mathbb{Z} can grow indefinitely.
This distinction in multiplicative inverses makes \mathbb{Z}_n particularly useful in applications like cryptography, where invertible elements are crucial for encryption and decryption operations.
Modular exponentiation
Modular exponentiation is a key operation in cryptography, enabling efficient computation of powers modulo a number. This operation is central to cryptographic systems like RSA, where large exponentiations are common.
Definition (Modular exponentiation): Modular exponentiation computes a^b \pmod{n}, where a is the base, b is the exponent, and n is the modulus.
Direct computation is impractical for large b, so efficient algorithms like square-and-multiply are used:
Algorithm (Right-to-left square-and-multiply algorithm):
Input integers a, b, and n where a is the base, b is the exponent, and n is the modulus.
Convert b to its binary representation:
Input integer b.
Initialize binary\_representation = [].
While b > 0: 1. Append b \\pmod{2} to binary\_representation 2. Update b = b // 2.
Initialize reversed\_representation = [].
For each bit in binary\_representation, starting from the last element, append the bit to reversed\_representation.
Initialize result = 1.
For each bit m in reversed\_representation:
- result = (result \cdot result) \pmod{n}.
- If m == 1, then result = (result \cdot a) \pmod{n}.
Return result, which is a^b \pmod{n}.
The alternative lef-to-right approach is obtained omitting steps 2.4 and 2.5, then computing step 4 on binary\_representation.
Let’s compute 3^{13} \pmod{7}:
Input integers a = 3, b = 13, and n = 7.
Initialize binary\_representation = [].
While b > 0:
- Append 13 \pmod{2} = 1, binary\_representation = [1].
- Update b = 13 // 2 = 6.
- Append 6 \pmod{2} = 0, binary\_representation = [1, 0].
- Update b = 6 // 2 = 3.
- Append 3 \pmod{2} = 1, binary\_representation = [1, 0, 1].
- Update b = 3 // 2 = 1.
- Append 1 \pmod{2} = 1, binary\_representation = [1, 0, 1, 1].
- Update b = 1 // 2 = 0.
reversed\_representation = [1, 1, 0, 1].
Initialize result = 1.
First iteration (m = 1):
- result = (result \cdot result) \pmod{7} = (1 \cdot 1) \pmod{7} = 1.
- result = (result \cdot a) \pmod{7} = (1 \cdot 3) \pmod{7} = 3.
Second iteration (m = 1):
- result = (result \cdot result) \pmod{7} = (3 \cdot 3) \pmod{7} = 2.
- result = (result \cdot a) \pmod{7} = (2 \cdot 3) \pmod{7} = 6.
Third iteration (m = 0):
- result = (result \cdot result) \pmod{7} = (6 \cdot 6) \pmod{7} = 1.
- No multiplication since m = 0.
Fourth iteration (m = 1):
- result = (result \cdot result) \pmod{7} = (1 \cdot 1) \pmod{7} = 1.
- result = (result \cdot a) \pmod{7} = (1 \cdot 3) \pmod{7} = 3.
We get result = 3, so 3^{13} \pmod{7} = 3.
Modular inverse
The modular inverse is a fundamental concept in number theory and cryptography. It is essential for solving modular equations, whose solution is determined within a given modulus n, meaning the values satisfy the equation in terms of congruence relations.
Definition (Modular inverse): The modular inverse of an integer a modulo n, denoted as a^{-1} \pmod{n}, is an integer x such that:
a^{-1} \pmod{n} = a \cdot x \equiv 1 \pmod{n}.
The modular inverse relies on several fundamental principles in number theory, including conditions for existence, efficient computation methods, and connections to primality tests. Below we will outline these key theorems, algorithms, and applications.
Theorem (Existence of modular inverse): An integer a has a modular inverse modulo n if and only if \gcd(a, n) = 1. If the modular inverse exists, it is unique modulo n.
A proof sketch can be given leveraging the Bézout’s Identity, because if \gcd(a, n) = 1, then there exist integers x and y such that:
ax + ny = 1.
Taking this equation modulo n, we get:
ax \equiv 1 \pmod{n}
proving that x is the modular inverse of a modulo n. The uniqueness follows from the properties of congruence classes.
The modular inverse can be computed using the Extended Euclidean Algorithm. This algorithm builds on the general method of finding GCD while also determining the coefficients that satisfy Bézout’s Identity. Here, it is specialized to calculate the modular inverse by assuming \gcd(a, n) = 1. The steps are given in the following algorithm:
Algorithm (Modular inverse via Extended Euclidean Algorithm):
Input integers a and n, where \gcd(a, n) = 1.
Initialize:
- r_0 = n, r_1 = a (remainder terms)
- Coefficients for n: s_0 = 1, s_1 = 0 (coefficients for n)
- Coefficients for a: t_0 = 0, t_1 = 1 (coefficients for a).
While r_1 \neq 0:
- q = \lfloor r_0 / r_1 \rfloor (quotient)
- r_2 = r_0 - q \cdot r_1
- s_2 = s_0 - q \cdot s_1
- t_2 = t_0 - q \cdot t_1
- r_0 = r_1, r_1 = r_2, s_0 = s_1, s_1 = s_2, t_0 = t_1, t_1 = t_2.
Return a^{-1} \pmod{n}: a^{-1} \pmod{n} = t_0 \pmod{n}.
Or defining a function EEA for the Extended Euclidean Algorithm as \text{EEA}: (a, b) \to (\gcd(a, b), x, y), where x is the Bézout coefficient for a:
Algorithm (Modular inverse via Extended Euclidean Algorithm):
Input integers a and n, where \gcd(a, n) = 1.
Call \text{EEA}: (a, n) \to (\gcd(a, n), x, y).
If \gcd(a, n) \neq 1 then return “No modular inverse exists”.
Return a^{-1} \pmod{n}: a^{-1} \pmod{n} = x \pmod{n}.
Fermat’s Little Theorem enables efficient computation of modular inverses and serves as a basis for primality testing:
Theorem (Fermat’s Little Theorem): If p is a prime number and a is an integer such that p \nmid a, then:
a^{p-1} \equiv 1 \pmod{p}.
To find the modular inverse, we rewrite a^{p-1} as:
a^{p-1} = a \cdot a^{p-2}
Substituting this into Fermat’s Little Theorem gives:
a \cdot a^{p-2} \equiv 1 \pmod{p}
By definition, the modular inverse a^{-1} satisfies:
a \cdot a^{-1} \equiv 1 \pmod{p}
Comparing this with the result above, we conclude that a^{p-2} must be the modular inverse of a modulo p;
a^{-1} \equiv a^{p-2} \pmod{p}.
This theorem provides a more efficient way to compute modular inverses when n is prime compared to the Extended Euclidean Algorithm.
Remark: By Fermat’s Little Theorem, for any integer a with \gcd(a,p)=1, we have
a^{p-1} \equiv 1 \pmod{p}.
The smallest positive exponent k such that a^k \equiv 1 \pmod{p} is called the order of a modulo p. This order always divides p-1, but it may be strictly smaller.
By Fermat’s Little Theorem, for any integer a such that p \nmid a:
a^{p-1} \equiv 1 \pmod{p}.
Assume, for contradiction, that there exists a smaller positive integer k < p-1 such that:
a^k \equiv 1 \pmod{p}.
If a^k \equiv 1 \pmod{p}, then we can write p-1 using the Division Algorithm:
p-1 = q \cdot k + r,
where q and r are integers, and 0 \leq r < k.
Substituting into a^{p-1}, this simplifies to:
a^{p-1} = a^{q \cdot k + r} = (a^k)^q \cdot a^r.
Since a^k \equiv 1 \pmod{p}, we get:
(a^k)^q \equiv 1^q \equiv 1 \pmod{p}.
Thus:
a^{p-1} \equiv a^r \pmod{p}.
By Fermat’s Little Theorem, a^{p-1} \equiv 1 \pmod{p}, so:
a^r \equiv 1 \pmod{p}.
However, r < k, contradicting the assumption that k is the smallest positive integer such that a^k \equiv 1 \pmod{p}. Hence, no such smaller k < p-1 exists, and p-1 must be the smallest exponent satisfying a^{p-1} \equiv 1 \pmod{p}.
Equivalently, if a^{p-1} \not\equiv 1 \pmod{p} for some a with \gcd(a, p) = 1, then p is composite. However, the converse of Fermat’s Little Theorem is not true: if a^{n-1} \equiv 1 \pmod{n} for all a with \gcd(a, n) = 1, then n is not necessarily a prime. In other words, Fermat’s Little Theorem is effective for disproving primality (when the congruence fails), it is insufficient for proving it.
Numbers that satisfy Fermat’s Little Theorem are defined as Carmichael numbers:
- 561: 561 = 3 \cdot 11 \cdot 17.
- 1105: 1105 = 5 \cdot 13 \cdot 17.
- 1729: 1729 = 7 \cdot 13 \cdot 19.
- 2465: 2465 = 5 \cdot 17 \cdot 29.
- 2821: 2821 = 7 \cdot 13 \cdot 31.
In 1994, it was proven by Alford, Granville, and Pomerance that there are infinitely many Carmichael numbers. However, they become increasingly sparse as numbers grow larger.
Defining the function \text{Square-and-multiply}: (a, b, n) \to a^b \pmod{n}, we can apply the following test for primality to n, choosing as many a as possible, where 1 < a < n:
Algorithm (Fermat primality test):
Input integers n and a.
Call \text{Square-and-multiply}: (a, n-1, n) \to a^{n-1} \pmod{n}.
If a^{n-1} \not\equiv 1 \pmod{n} then “n is composite” else “n is likely prime”.
As an alternative to Fermat primality test, there is a brute-force approach for determining whether a number n is prime by dividing n by smaller prime numbers up to \sqrt{n}:
Algorithm (Trial division primality test):
Input integer n > 1.
If n = 2, return “n is prime”.
If n \pmod{2} = 0, return “n is composite”.
For d where d = 2k + 1 and 1 \leq k \leq \lfloor \sqrt{n}/2 \rfloor:
- If n \pmod{d} = 0 then return “n is composite”.
Return “n is prime”.
The test involves at most \sqrt{n} divisions, making it computationally expensive for large n, having a time complexity of \mathcal{O}(\sqrt{n}), assuming that a single modulo operation is \mathcal{O}(1). The algorithm becomes more efficient when using a precomputed list of primes up to \sqrt{n}, skipping unnecessary checks for non-prime divisors.
For very large n, the size of n impacts the complexity of each modulo operation. If n has b bits, then the modulo operation takes \mathcal{O}(b^2) time using simple arithmetic or \mathcal{O}(b \log b) with optimized algorithms. In such cases, the overall complexity becomes \mathcal{O}(\sqrt{n} \cdot \text{modulo complexity}).
A more refined algorithm is the Miller-Rabin primality test, which is much faster and more robust than trial division and the basic Fermat test.
Euler’s theorem
Euler’s theorem is a fundamental result in number theory that generalizes Fermat’s little theorem. It provides a condition for modular exponentiation when the base and modulus are coprime.
Definition (Euler totient function): Let n be a positive integer, the Euler totient function, denoted as \phi(n), counts the number of positive integers less than n that are relatively prime to n:
\phi(n) = \lvert \{ a \in \mathbb{Z} : 1 \leq a < n, \gcd(a, n) = 1 \}\rvert
Properties of the Euler totient function:
If p is a prime number, then:
\phi(p) = p - 1.
If n has the prime factorization n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}, then \phi(n) is given by:
\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i} \right).
The totient function is multiplicative, meaning that if m and n are coprime, then:
\phi(mn) = \phi(m) \phi(n).
Theorem (Euler): Let a and n be coprime integers (i.e., \gcd(a, n) = 1). Then:
a^{\phi(n)} \equiv 1 \pmod{n}.
This theorem generalizes Fermat’s little theorem, which is a special case when n is prime, where \phi(p) = p - 1 and thus:
a^{p-1} \equiv 1 \pmod{p}.
Euler’s theorem is widely used in cryptographic algorithms, particularly in the RSA encryption scheme, where it is employed to compute modular inverses efficiently. The theorem allows us to find the modular inverse of a modulo n when \gcd(a, n) = 1, using:
a^{-1} \equiv a^{\phi(n) - 1} \pmod{n}.
For example, to compute 3^{\phi(25)} \pmod{25}:
First, calculate \phi(25):
\phi(25) = 25 \left( 1 - \frac{1}{5} \right) = 25 \times \frac{4}{5} = 20.
Then,
3^{20} \equiv 1 \pmod{25}.
Thus, using Euler’s theorem, we can directly conclude that any power of 3 raised to 20 will be congruent to 1 modulo 25.
Carmichael’s theorem
Carmichael’s theorem refines Euler’s theorem by defining the smallest exponent that guarantees modular exponentiation behaves predictably for all coprime bases. This exponent is given by the Carmichael function, denoted as \lambda(n).
Theorem (Carmichael): For a positive integer n, the Carmichael function \lambda(n) is defined as the exponent of the multiplicative group \mathbb{Z}_n^*. Equivalently, \lambda(n) is the smallest positive integer such that
a^{\lambda(n)} \equiv 1 \pmod{n}
for every a \in \mathbb{Z}_n^*.
This function provides a stricter condition than Euler’s theorem and guarantees that for any integer a coprime to n, the smallest exponent e for which a^e \equiv 1 \pmod{n} is always a divisor of \lambda(n). In other words, the values of e that satisfy this condition must be factors of \lambda(n). By definition, \lambda(n) is also always a divisor of \phi(n):
\lambda(n) \mid \phi(n).
To compute \lambda(n), we use the least common multiple (lcm) function, which determines the smallest positive integer that is divisible by a given set of numbers.
Definition (least common multiple): The lcm of two integers a and b, denoted as \operatorname{lcm}(a, b), is the smallest positive integer that is a multiple of both a and b:
\operatorname{lcm}(a, b) = \frac{|a \cdot b|}{\gcd(a, b)},
where \gcd(a, b) is the greatest common divisor of a and b.
This concept extends naturally to multiple integers, allowing for an efficient computation of \lambda(n) when n has multiple prime factors.
Example: consider n = 18, which has the prime factorization n = 2 \times 3^2 and we compute:
\lambda(2) = 1, \quad \lambda(3^2) = \phi(3^2) = 3.
Since n consists of relatively prime factors, we use the least common multiple:
\lambda(18) = \operatorname{lcm}(\lambda(2), \lambda(3^2)) = \operatorname{lcm}(1, 3) = 3.
This tells us that for any integer a coprime to 18, the smallest exponent satisfying a^e \equiv 1 \pmod{18} must be a multiple of 3.
To compute \lambda(n) efficiently for any integer n, we apply the following structured approach, which relies on prime power properties and the least common multiple:
If n is a power of a single prime, p^e, we compute \lambda(n) as follows:
- When p is an odd prime or e \leq 2, \lambda(p^e) is simply \phi(p^e), the Euler totient function.
- When p = 2 and e \geq 3, the exponent is halved:
\lambda(p^e) = \frac{1}{2} \phi(p^e).
This accounts for the behavior of powers of 2 in modular arithmetic, ensuring that exponentiation remains consistent with Carmichael’s theorem.
If n is a product of multiple pairwise relatively prime numbers n_1, n_2, ..., n_r, the Carmichael function is computed using the least common multiple:
\lambda(n) = \operatorname{lcm}(\lambda(n_1), ..., \lambda(n_r)).
This ensures that \lambda(n) is compatible with each individual modulus, making it the smallest exponent that satisfies a^{\lambda(n)} \equiv 1 \pmod{n} for all coprime bases a.
If n is given in its prime factorized form:
n = p_1^{e_1} p_2^{e_2} \dots p_r^{e_r},
then \lambda(n) is computed as:
\lambda(n) = \operatorname{lcm}(\lambda(p_1^{e_1}), ..., \lambda(p_r^{e_r})).
This approach ensures that we first compute \lambda for each prime power individually (using the prime power rule) and then combine the results using the least common multiple.
By following these structured steps, we can efficiently compute \lambda(n) for any integer n, making it a practical function for number theory and cryptographic applications.
Now, let’s introduce numbers that pass Fermat’s primality test despite being composite:
Definition (Carmichael number): a Carmichael number is a composite number n that satisfies:
a^{n-1} \equiv 1 \pmod{n},
for all a coprime to n.
A number is Carmichael if and only if \lambda(n) divides n - 1. For example, consider:
\lambda(1105) = \operatorname{lcm}(\lambda(5), \lambda(13), \lambda(17)) = \operatorname{lcm}(4, 12, 16) = 48.
Since 48 divides 1105 - 1 = 1104, this confirms that 1105 is a Carmichael number.
Carmichael numbers are important in cryptography because they can deceive certain primality tests, making them crucial in designing secure encryption algorithms.
Generators
A generator is a number that, when multiplied by itself multiple times (using modular arithmetic), cycles through many or all possible values before repeating. This cycle length is called the multiplicative order of the number. In simple terms, it tells us how long it takes for the number to “reset” back to 1 when repeatedly multiplied by itself modulo n.
For example, if we take 3 and multiply it repeatedly modulo 7:
\begin{align*}
3^1 &\equiv 3 \pmod{7}, \\
3^2 &\equiv 9 \equiv 2 \pmod{7}, \\
3^3 &\equiv 6 \pmod{7}, \\
3^4 &\equiv 4 \pmod{7}, \\
3^5 &\equiv 5 \pmod{7}, \\
3^6 &\equiv 1 \pmod{7}.
\end{align*}
Here, the number 3 cycles through all possible values before repeating, making it a generator modulo 7.
This concept is useful in cryptography because some security systems rely on the fact that finding how many times you need to multiply a number to get back to 1 (the order) is hard to figure out. This is used in encryption methods like Diffie-Hellman key exchange, which helps people securely share secret keys over public networks.
More formally:
Definition (Multiplicative order): given a positive integer n and an element a \in \mathbb{Z}_n^*, the multiplicative order of a, denoted as \operatorname{ord}_n(a), is the smallest integer e > 1 such that:
a^e \equiv 1 \pmod{n}.
Properties of the multiplicative order:
- The order of a always divides \phi(n), a consequence of Euler’s theorem.
- For any integer i, a^i \equiv 1 \pmod{n} if and only if \operatorname{ord}_n(a) \mid i.
Definition (Generator): an element g \in \mathbb{Z}_n^* is called a generator (or a primitive root) of \mathbb{Z}_n^* if its order is maximal, meaning:
\operatorname{ord}_n(g) = \phi(n).
This implies that g can produce all elements of \mathbb{Z}_n^* through exponentiation.
A generator a of \mathbb{Z}_n^* remains a generator under exponentiation if and only if the exponent i is chosen correctly, as stated in the following theorem.
Theorem (Generator preservation): if a is a generator of \mathbb{Z}_n^*, then for any integer i, the element b \equiv a^i \pmod{n} is also a generator of \mathbb{Z}_n^* if and only if:
\gcd(i, \phi(n)) = 1.
This property is essential in cryptographic protocols such as Diffie-Hellman key exchange, where security relies on the fact that, while it is easy to compute exponentiation modulo n, finding the original exponent i given only the result a^i \pmod{n} (a problem known as the discrete logarithm problem) is computationally difficult.
To illustrate the concept of a generator, consider \mathbb{Z}_{10}^*, which consists of the elements:
\mathbb{Z}_{10}^* = \{1, 3, 7, 9\}.
The totient function gives \phi(10) = 4, so a generator g must satisfy \operatorname{ord}_{10}(g) = 4.
Checking powers of 3 modulo 10:
3^1 \equiv 3 \pmod{10}, \quad 3^2 \equiv 9 \pmod{10}, \quad 3^3 \equiv 7 \pmod{10}, \quad 3^4 \equiv 1 \pmod{10}.
Since the order of 3 is 4, it is a generator of \mathbb{Z}_{10}^*.
Chinese Remainder Theorem
The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that provides a way to solve systems of simultaneous congruences when the moduli are pairwise relatively prime.
Theorem (Chinese Remainder): let n_1, n_2, \dots, n_k be pairwise relatively prime positive integers, then for any given integers r_1, r_2, \dots, r_k, the system of congruences:
x \equiv r_i \pmod{n_i}, \quad \text{for } i = 1, \dots, k,
has a unique solution modulo n = n_1 n_2 \cdots n_k.
The solution is given by:
x \equiv \sum_{i=1}^{k} r_i \cdot c_i \cdot m_i \pmod{n},
where m_i = \frac{n}{n_i} and c_i is the modular inverse of m_i modulo n_i, satisfying c_i m_i \equiv 1 \pmod{n_i}.
Solving systems with CRT algorithm:
- Compute n = n_1 n_2 \cdots n_k.
- For each i, compute m_i = n / n_i.
- Compute the modular inverse c_i \equiv m_i^{-1} \pmod{n_i}.
- Compute x = \sum_{i=1}^{k} r_i \cdot c_i \cdot m_i and reduce modulo n.
For example, solve the system:
x \equiv 4 \pmod{9}, \quad x \equiv 7 \pmod{13}, \quad x \equiv 2 \pmod{17}.
Since 9, 13, and 17 are pairwise relatively prime, we compute: - n = 9 \times 13 \times 17 = 1989. - m_1 = 1989/9 = 221, m_2 = 1989/13 = 153, m_3 = 1989/17 = 117. - Compute the modular inverses: - c_1 = 221^{-1} \equiv 4 \pmod{9}. - c_2 = 153^{-1} \equiv 12 \pmod{13}. - c_3 = 117^{-1} \equiv 10 \pmod{17}. - Compute x:
x \equiv (4 \times 4 \times 221 + 7 \times 12 \times 153 + 2 \times 10 \times 117) \pmod{1989}.
Evaluating, we find x \equiv 8776 \equiv 418 \pmod{1989}.
Thus, the unique solution modulo 1989 is x \equiv 418 \pmod{1989}.
This demonstrates the power of the CRT in reconstructing values from modular congruences.
Quadratic residues
Definition (Quadratic residue): a number a \in \mathbb{Z}_n^* is a quadratic residue modulo n if there exists an integer x such that:
a \equiv x^2 \pmod{n}.
Otherwise, a is called a quadratic non-residue modulo n.
This theorem allows us to efficiently determine whether a number is a quadratic residue:
Theorem(Euler’s criterion): Let p be an odd prime and a \in \mathbb{Z}_p^*. Then:
- If a is a quadratic residue modulo p:
a^{(p-1)/2} \equiv 1 \pmod{p}.
- If a is a quadratic non-residue modulo p:
a^{(p-1)/2} \equiv -1 \pmod{p}.
Definition (Legendre symbol): the Legendre symbol is a function that determines whether an integer a is a quadratic residue modulo an odd prime p; it is defined as:
\left( \frac{a}{p} \right) = \begin{cases}
0, & \text{if } p \mid a, \\
1, & \text{if } a \text{ is a quadratic residue modulo } p, \\
-1, & \text{if } a \text{ is a quadratic non-residue modulo } p.
\end{cases}
Using Euler’s criterion, we compute:
\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p}.
Then, we can state:
Theorem (Properties of the Legendre symbol): let p be an odd prime and a, b be integers, the Legendre symbol satisfies the following properties:
- \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p} (Euler’s criterion).
- If a \equiv b \pmod{p}, then \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right).
- \left( \frac{a \cdot b}{p} \right) = \left( \frac{a}{p} \right) \times \left( \frac{b}{p} \right) (Multiplicative property) .
- \left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}.
- If p and q are odd primes (Law of quadratic reciprocity) :
- If p \equiv 1 \pmod{4} or q \equiv 1 \pmod{4}, then \left( \frac{p}{q} \right) = \left( \frac{q}{p} \right).
- If p \equiv q \equiv 3 \pmod{4}, then \left( \frac{p}{q} \right) = -\left( \frac{q}{p} \right).
As an example, for p = 19, determine whether a = 11 is a quadratic residue:
11^{(19-1)/2} = 11^9 \equiv -1 \pmod{19}.
Since the result is -1, 11 is a quadratic non-residue modulo 19.
The Jacobi symbol generalizes the Legendre symbol for odd composite moduli:
Definition (Jacobi symbol):
\left( \frac{a}{n} \right) = \prod_{i=1}^{r} \left( \frac{a}{p_i} \right)^{e_i},
where n = p_1^{e_1} p_2^{e_2} \dots p_r^{e_r} is the prime factorization of n.
The Jacobi symbol shares properties with the Legendre symbol but does not definitively indicate whether a is a quadratic residue modulo n.
If n is an odd composite integer, determining whether a with \left( \frac{a}{n} \right) = 1 is a quadratic residue modulo n is called the Quadratic Residuosity Problem (QR). This problem is computationally difficult without knowing the factorization of n, linking it to cryptographic security.
The QP is central to probabilistic encryption schemes such as the Goldwasser-Micali cryptosystem, where the difficulty of distinguishing quadratic residues from non-residues provides semantic security. It is also relevant in zero-knowledge proofs and commitment schemes, where proving knowledge of a square root modulo n can be done without revealing the value itself. By leveraging the hardness of the QR problem, cryptographic systems can achieve stronger security guarantees, making it an essential tool in modern cryptography.
Higher-order residues
Definition (rth residue modulo): an integer a \in \mathbb{Z}_n^* is called an rth residue modulo n if there exists an integer x \in \mathbb{Z}_n^* such that:
a \equiv x^r \pmod{n}.
If no such x exists, then a is called an rth non-residue modulo n.
Lemma (Structure of higher-order residues): 1. The set of rth residues modulo n that are relatively prime to n forms a subgroup of \mathbb{Z}_n^*. 2. Each rth residue modulo n has the same number of rth roots.
Determining whether an element is an rth residue modulo n is known as the Higher Residuosity Problem (HRP). When n is composite and its factorization is unknown, this problem is computationally difficult, making it useful in cryptographic settings. A special case of the HRP occurs when r is replaced by n and n is replaced by n^2, where n = pq is a product of two distinct odd primes. This version is called the Composite Residuosity Problem (CRP) and is used in cryptographic protocols such as Paillier encryption.
Lemma (Residue completeness condition): if \gcd(r, \phi(n)) = 1, then every integer in \mathbb{Z}_n^* is an rth residue modulo n.
Residue classes
Definition (Residue class): For fixed integers r, n, y with y \in \mathbb{Z}_n^*, an element w \in \mathbb{Z}_n^* is said to belong to a residue class if it can be expressed as:
w \equiv y^m \cdot u^r \pmod{n},
for some integer m and some u \in \mathbb{Z}_n^*. The residue class of w is denoted as:
RC[m] = \{ w \in \mathbb{Z}_n^* : w \equiv y^m u^r \pmod{n} \text{ for some } u \in \mathbb{Z}_n^* \}.
In particular, RC[0] represents the set of rth residues modulo n.
Lemma (Addition and inversion in residue classes): 1. If w_1 \in RC[m_1] and w_2 \in RC[m_2], then w_1 \cdot w_2 \in RC[m_1 + m_2]. 2. If w \in RC[m], then w^{-1} \in RC[-m].
The problem of determining the residue class of a given w is conjectured to be computationally difficult and is known as the Residue Class Problem (RCP). A special case arises when n is composite, known as the Composite Residuosity Class Problem (CRP), forming the basis of secure cryptographic schemes.
A fundamental question in this context is determining the number of distinct rth roots a given residue has. This is particularly important in cryptographic applications, where knowing the structure of these roots can influence security guarantees. The following theorem establishes a precise condition under which an rth residue has exactly r distinct roots:
Theorem (Uniqueness and count of rth roots): Let y \in \mathbb{Z}_n^* be an rth residue modulo n. If r \mid \phi(n) and \gcd(r, \phi(n)/r) = 1, then y has exactly r distinct rth roots.
Residue classes provide a structured way to categorize elements of \mathbb{Z}_n^* based on their power relationships, enabling cryptographic operations such as trapdoor functions, which allow for efficient decryption while keeping encryption computationally difficult, and homomorphic encryption schemes, which enable computations on encrypted data without needing decryption. These concepts are foundational in privacy-preserving cryptographic protocols, such as the Paillier cryptosystem, which relies on the Composite Residuosity Problem for encryption, RSA-based voting schemes, which utilize quadratic residues for secure tallying, and homomorphic encryption frameworks like ElGamal encryption, which allow operations on encrypted data without decryption. These methods are crucial in secure voting systems, digital signatures, and confidential data processing.
Random number generators
In cryptographic applications, particularly homomorphic encryption, random numbers are essential for security. A function \text{RANDINT}(a, b) is defined to return a uniformly selected integer from the range [a, b]. Ensuring unpredictability in random numbers is a fundamental challenge in cryptographic design.
Random number generators (RNGs) are categorized into:
True Random Number Generators (TRNGs): Based on physical processes such as thermal noise or electronic circuit randomness, offering high security against prediction.
Deterministic Random Number Generators (DRNGs): Algorithmic methods that produce sequences from an initial seed, commonly used in cryptographic protocols.
A DRNGs is fast and efficient but can be predictable if its starting value (seed) is not chosen securely. In contrast, a TRNG relies on physical processes to generate randomness, making it more secure but often slower and requiring specialized hardware. To balance speed and security, many systems use a hybrid approach, where a TRNG provides an initial high-quality seed, and a DRNG expands it to generate more random values efficiently.
When generating a cryptographic key, it’s important to use a secure random number generator (RNG) to ensure unpredictability. A common approach is to use a Cryptographically Secure Pseudorandom Number Generator (CSPRNG), which expands a small amount of highly unpredictable data (called a seed) into a long sequence of random values.
A high-entropy seed means the initial data used to start the generator is difficult to guess, coming from unpredictable sources like hardware noise, mouse movements, or system timings.
One well-known approach is the Fortuna algorithm, a security-focused random number generator that works as follows:
Collect random data from multiple sources, such as user input timings, network activity, or hardware randomness.
Mix the collected data using a cryptographic hash function to update an internal state securely.
Generate random values using a block cipher (e.g., AES in counter mode) to ensure strong randomness.
Periodically refresh the seed to prevent attackers from predicting future random outputs.
This method ensures that even if part of the system state is exposed, the generated numbers remain secure and unpredictable.
For cryptographic security, DRNGs should satisfy:
Uniform distribution: ensuring statistical randomness.
Independence: ensuring no correlation between outputs.
Unpredictability: preventing attackers from inferring future values.
Secure choices for transition functions include cryptographic hash functions and block ciphers, ensuring resistance to attacks. Well-known cryptographic DRNGs include also:
These RNGs play a crucial role in encryption schemes, key generation, digital signatures, and secure multiparty computation.
