Number Theory for Public Key Cryptography

• Number theory problems used in public key cryptography
• Need efficient ways of generating large prime numbers
• Definitions of hard computational problems are the base of crypto systems

Chinese Remainder Theorem (CRT)

Let $p$, $q$ be relatively prime.

Let $n = pq$ be the modulus.

Given integers $c_1$ and $c_2$ there exists a unique integer $0 \le x \lt n$ such that:

Where:

Condensed Equation:

Example

Find $x$ such that $x \equiv 5 \pmod 6$ and $x \equiv 33 \pmod {35}$:

• $c_1 = 5$ and $c_2 = 33$
• $p = 6$ and $q = 35$ are relatively prime so CRT can be used
• $n = 6 \cdot 35 = 210$

For $y_1$:

Make sure you replace $q$ with $q \bmod p$ (assuming $q \gt p$): otherwise instead of finding $5^{-1} \pmod 6$, you will find $6^{-1} \bmod{35}$.

For $y_2$:

Example 2

Find $x$ such that $x \equiv 5 \pmod{7}$ and $x \equiv 7 \pmod{10}$

$\mathrm{gcd}(7, 10) = 1$; $p$ and $q$ are relatively prime. Hence, CRT applies.

Hence $n = 7 \cdot 10 = 70$

Where:

• $y_1 \equiv 10^{-1} \pmod{7}$

  • As $(5 \cdot 10)^{-1} \equiv 1 \pmod{7}$, $y_1 = 5$

• $y_2 \equiv 7^{-1} \pmod{10}$

  • As $(3 \cdot 7)^{-1} \equiv 1 \pmod{10}$, $y_2 = 3$

Hence:

Test:

• $47 \bmod{7} = 42 + 5 = 5$ as required
• $47 \bmod{10} = 40 + 7 = 7$ as required

Euler Function

Given the positive integer $n$, the Euler function $\phi(n)$ denotes the number of positive integers less than $n$ and relatively prime to $n$.

e.g. $\phi(10) = 4$ as $\mathbb{Z}^{*}_{10} = \{ 1, 3, 7, 9 \}$.

Properties

$\phi(p) = p - 1$ where $p$ is prime.

$\phi(pq) = (p - 1)(q - 1)$ where $p$ and $q$ are distinct primes.

if $n = p_1^{e_1} \dots p_t^{e_t}$ where $p_i$ are distinct primes, then:

e.g. for $24 = 2^3 \cdot 3^1$, $\phi(24) = 2^2(2 - 1) \cdot 3^0(3 - 1) = 4 \cdot 2 = 8$

Fermat’s Theorem

Let $p$ be a prime; for any integer $a$ such that $1 \lt a \le p - 1$:

Euler’s Theorem

More general case of Fermat’s theorem.

If $\mathrm{gcd}(a, n) = 1$ (i.e. $a$ and $n$ coprime) then:

Primality Tests

Testing for primality by trial division not practical for large numbers.

There are many probabilistic methods, although these may fail in exceptional circumstances.

Agrawal, Saxena, Kayal 2002: polynomial time deterministic primality test, although still impractical.

Fermat Primality Test

Fermat’s little theorem: if $p$ is prime, $a^{p - 1} \mod p = 1$ for all $a$ such that $\mathrm{gcd}(a, p) = 1$.

If $a^{n - 1} \mod n \neq 1$, $n$ is NOT a prime.

The probability of failure can be reduced by repeating the test with different base values of $a$.

Given the number $n$ to test for primality and $k$, the number of times to run the test:

• Pick $a$ at random such that $1 \lt a \lt n - 1$
• If $a^{n - 1} \mod n \neq 1$, return $n$ as being composite. Otherwise, return probable prime
  • The powers can be reduced using the following properties:
    • $ab \bmod n = (a \bmod n)(b \bmod n) \bmod n$
    • $(a^m)^k \bmod n = (a^m \bmod n)^k \bmod n$

Some composite numbers such as $561$ and $1105$ are called Carmichael numbers; the Fermat primality test always returns these numbers as being probable primes.

Example

Check if $517$ is prime, running the test at most four times with values $a = 2, 3, 11, 17$.

$n - 1 = 517 - 1 = 516 = 43 \cdot 3 \cdot 2^2$

Using $a = 2$:

Hence it is composite, so we do not need to make further checks.

Miller-Rabin Test

Most widely used test for generating large prime numbers. It is guaranteed to detect composite numbers of the test is run sufficiently many times.

Modular square root of $1$: a number $x$ such that $x^2 \mod n = 1$. In other words, the root of the equation $x^2 - 1 \equiv (x - 1)(x + 1) \equiv 0 \pmod n$.

There are four square roots of $1$ when $n = pq$ (i.e. composite):

• Two are $1$ and $-1$
• Two are called non-trivial square roots of $1$

If $x$ is a non-trivial square root of $1$ then $\mathrm{gcd}(x - 1, n)$ is a non-trivial factor of $n$. Hence, $n$ must be composite.

Miller-Rabin Algorithm

Let $n$ and $u$ be odd and find $v$ such that $n - 1 = 2^v u$. Then:

1. Pick $a$ at random such that $1 \lt a \lt n - 1$
2. Set $b = a^u \mod n$
3. If $b = 1$, return probable prime
4. For $j = 0$ to $v - 1$:
   • If $b = -1$, return probable prime
   • Else, set $b = b^2 \mod n$
5. Return composite

If the test returns probable prime, $n$ may be composite.

If $n$ is composite then then test returns probable prime with at most a probability of $0.25$.

As the algorithm is run $k$ times, it outputs probable prime when $n$ is composite with a probability of no more than $0.25^k$.

In practice, the error probability is smaller: when $a$ is given the first seven primes, the smallest composite the algorithm returns as being a probable prime is $341,550,071,728,321$

Why The Miller-Rabin Test Works

Given a random $a$ such that $0 \lt a \lt n - 1$, with $n - 1$ being equal to $2^v u$.

Hence, $b$ can be given the values $\{ a^u \mod n, a^{2u} \mod n, \dots, a^{2^{v}u} \mod n \}$.

Each number on the sequence is the square of the previous number (modulo $n$).

If $n$ is prime, $a^{2^v u} \mod n = a^{n - 1} = 1$ (Fermat’s theorem). Hence:

• Either $a^u \mod n = 1$ OR
• There is a square root of $1$ somewhere in the sequence whose value is $-1$ (which is equal to $n - 1$

If a non-trivial square root of $1$ is found, $n$ must be composite.

Example

Let $n = 1729$ (a Charmichael number)

$n - 1 = 1728 = 64 \times 27 = 2^6 \times 27$. Hence, $v = 6$, $u = 27$.

1. Choose $a = 2$
2. $b = 2^{27} \bmod{1729} = 645$
3. $b \neq 1$ so:
   • $b = 645^2 \bmod n = 1065$
   • $b = 1065^2 \bmod n = 1$
   • $b = 1^2 \bmod n = 1$
   • $\dots$
   • Hence, $b = -1 = n - 1$ will never occur
   • Hence, $n$ must be composite

NB: $1064$ is a non-trivial square root of $1$ modulo $1729$: $\mathrm{gcd}(1729, 1064) = 133$ is a factor of $1729$.

Example 2

Let $n = 17$.

$n - 1 = 16 = 2^vu$.

$16 = 2^5$ and $u$ must be odd. Hence, the only valid values are $u = 1$ and $v = 5$.

Let $1 < a < n - 1$ be a prime. Pick $a = 3$:

• $b = a^u \bmod n = 3^1 \bmod{17} = 3$
• This is not $1$ so:
• Repeat up to $v = 5$ times:
  • $b = 3^2 \bmod{17} = 9$
  • $b = 9^2 \bmod{17} = 13$
  • $b = 13^2 \bmod{17} = 16 = -1$

Hence, $17$ is a probable prime. Repeat for other values of $a$ until satisfied.

Generation of Large Primes

1. Choose a random odd integer $n$ of the same number of bits as the required prime
2. Test if $r$ is divisible by any of a small list of primes
3. If not:
   • Apply the Miller-Rabin test five random or fixed based values of $a$
   • If $r$ fails any test, set $r = r + 2$ and return to step 2

This incremental method does not produce completely random primes. If this is an issue start from step 1 if $r$ is found to be composite.

Basic Complexity Theory

Two aspects:

• Algorithmic complexity: how long does it to take to run a particular algorithm
• Problem complexity: how long does it to take to run the best known algorithm for the given problem

Express this complexity using ‘big O’ notation; in terms of the space and time required to solve the problem for a given size.

Hard Problems

Integer factorization: given an integer of $m$ bits, find its prime factors.

Discrete logarithm problem (base 2): given a prime $p$ of $m$ bits and an integer $0 \lt y \lt p$, find $x$ such that $y = 2^x \mod p$

There are no known polynomial algorithms to solve the problems; the best known algorithms are sub-exponential.

Factorization Problem

Trial by division: exponential time algorithm

Some fast methods exist, although they only apply to integers with particular properties.

Bets known general method: number field sieve, a sub-exponential algorithm.

As $n = pq$, $n$ is large even with small keys; brute force search of 128-bit AES keys takes roughly the same computational effort as factorization of a 3072-bit number with two factors of roughly equal size.

Discrete Logarithm Problem

Given a prime $p$ and generator $g$ of $\mathbb{Z}_p^*$, the discrete logarithm is:

Given $y \in \mathbb{Z}_p^*$, find $x$ such that $y = g^x \bmod p$.

(i.e. find the power given the remainder)

This can be written as $x = log_g(y) \pmod p$.

If $p$ is large enough, the problem is hard. Given the same length, the security level is equal RSA (and hence should be at least 2048 bits).

Example

Find $x$ such that $2^x = 3 \bmod 5$:

Hence $x = 3$.

Example 2

Find the discrete logarithm of the number $4$ with regard to base $2$ for the modulus $p = 7$.

i.e. solve $2^x = 4 \bmod 7$.

There is a cycle with powers of $2$ modulo $7$ taking on the values $2, 4, 1$. Hence, $x = 2$.