Number Theory Part 2

This post covers more of the number theory I found useful for understanding the basics of public key cryptography. I've covered Fermat's little Theorem, Euler's Theorem, e^th roots, and discrete logarithms. Once this stuff is covered you should be able to learn how encryption systems like RSA and ElGamal work, and be able to understand key exchange protocols like Diffie-Hellman.

Fermat's Little Theorem

Don't get this confused with Fermat's Last Theorem, which states that there are no positive integers a, b, and c, such that aⁿ+bⁿ = cⁿ for any n value greater than 2.

Fermat's Little Theorem is used in RSA and states that if p is a prime number and a is any integer, then the result of a^p-a will be congruent to the value of p. It is therefore a useful method of checking for primality (it's necessary, but not sufficient).

It can be shown in modulo arithmetic as:

a^p = a (mod p)

Using the values a = 3, p = 5

35 = 243
 = 243 (mod 5)  = 3
 = 35 = 3 (mod 5)

Fermat's Little Theorem can also be used to calculate the modular multiplicative inverse. Remember that the inverse of a value x is represented as x^-1 and that multiplying it by x results in 1. If a isn't divisible by p, then the theorem is equivalent to:

a^p-1 = 1 (mod p)

Using the values a = 3, p = 5

35-1
 = 34 = 81
 = 81 mod 5 = 1

Because a^p-1 = 1 (mod p), we can determine the inverse of a (or a^-1 if you like) to be a^p-2 (mod p), because a^p-2 (mod p)*a^p (mod p) results in a^p-1 (mod p) which is 1 mod p. Although this is a viable method of calculating the modular multiplicative inverse, the GCD approach is used more commonly because it's faster and doesn't require information about the group order.

Here's an example:

a*ap-2 = 1 (mod p)

using values a = 3, p = 7

3*(37-2)
 = 3*(35)  = 729
 = 729 (mod 7) = 1

So the inverse of 3 modulo 7 (3-1 mod 7) is: 35 (mod 7) = 5
a*a-1 (mod p) → 3*5 = 15 (mod 7) = 1
3-1 (mod 7) = 5

Euler's Theorem

Fermat's Little Theorem is great, but it only applies to prime numbers. This is where Euler's Theorem comes in (or the Fermat-Euler Theorem). Euler developed Fermat's Little Theorem further so it would apply to all integers, not just primes. The result is a more general theorem and one that is an important part of RSA.

The theorem states:

If a and n are co-prime then the result of aϕ(n) = 1 (mod n)

Here, ϕ represents the Phi function (or Euler's totient Function). This function returns the number of invertible elements in the set of Zn. From number theory part 1, we know that the set of invertible elements contains all values in Zn that are co-prime to n, and is represented as Zn*. So we could have said ϕ(n) returns the cardinality of the set Zn*.

The value returned by this function is the group order of Zn*. Knowing the group order is important because it allows us to calculate the private key in RSA. Note, since the value n in RSA is equal to the product of two primes p and q, the group order is equal to p-1*q-1 since Zp* = Zp \ {0} and |Zp*| = p-1.

Eth root

Calculating the e^th root for some value c, is the process of finding a value x in Zp* such that x^e = c (mod p). It's usually shown as c^1/e.

Since we raise the plaintext message m to the public exponent e modulo n in the RSA cryptosystem, an adversary could calculate the plain text by performing the e^th roots on some arbitrary number modulo n. However, no efficient solution exists to calculate the e^th root for keys greater than 1024 bits. This is the reason the RSA cryptosystem is considered secure, and is the reason that most of our encrypted packets sent over the internet would be vulnerable if an efficient solution did exist (the Wikipedia article has more to say on it).

71/3 = 6 in Z11

Let's break it down. We want to find some value x, such that x3 = 7 (mod 11).

 63 = 216
 216 mod 11 = 7

So the eth root of 7 (mod 11) is 6.

Discrete Logarithm

The discrete logarithm assumption is the reason the Diffie-Hellman key exchange is successful at keeping secret keys secret over an unsecured network. Without this important security feature, it would be possible for an adversary to calculate the secret keys by listening to the packets sent during key exchange. Wolfram explain this nicely.

Here’s the gist of it:
The discrete logarithm is some value x such that bx (mod n) = a

In the Diffie-Hellman key exchange, two parties, Alice and Bob, have the private keys a and b, respectively. They raise some integer g to their private key modulo p (g^{secret key} (mod p)), and then send the result over an unsecured network to the other party. After both parties have sent this value, they then can compute a shared secret key ((g^b)^a (mod p) for Alice, and (g^a)^b (mod p) for Bob, both resulting in the same value).

Because we know that computing the discrete logarithm for large numbers is too difficult (it's a computationally intractable problem) we can say that, even though an adversary has access to g^a (mod p) and g^b (mod p) they will be unable to calculate g^ab (mod p).

Further Reading

Page 34 of "A Computational Introduction to Number Theory and Algebra - Victor Shoup" for more information on Euler's and Fermat's Theorems - (Free PDF here)

Wolfram have a concise definition of the discrete logarithm

Wikipedia's articles on the RSA problem and the Diffie-Hellman problem are useful