Maths for Cryptography

Following are the basic mathematical elements required for an understanding of cryptography.

Primes and Coprimes

Basics

If you don't know what a prime is you probably shouldn't be doing this course.

$\pi\left(x\right)$ is the number of primes less than or equal to x.

For $x \geq 17$ this can be approximated by $${x \over ln x} < \pi\left(x\right) < 1.25506 \cdot {x \over ln x}$$

Coprimes

Integers $a, b$ are coprime or relatively prime if they have no common factors (nothing divides them both).

This is usually tested for using the Greatest Common Denominator algorithm (or gcd), where $coprime(a, b) \iff gcd(a, b) = 1$

Euler totient

$\phi\left(n\right)$ denotes how many natural numbers (positive integers) that are less than $n$ are coprime with $n$

$\phi\left(n\right)$ is known as the Euler Totient function

If we know the prime factors of $n$ then $\phi\left(n\right)$ can be calculated as $$\phi\left(n\right) = n\prod_{p} \left(1-{1\over p}\right)$$

where $p$ is a distinct prime factor of $n$

Smoothness

An integer $n$ is said to be $B-smooth$ for some $B$ (e.g. 50-smooth) if all of its prime factors are less than or equal to $B$

Note this generally means that $B$ is the lowest such number for $n$, meaning it is $n$'s largest prime factor but this is not always the case.

If $B$ is much smaller than $n$ then we tend to say "$n$ is smooth".

Importance

There exist quick algorithms for factoring smooth numbers, even when they are large, so one must avoid using smooth numbers in techniques that rely upon prime factorisation for security.

Modulo Arithmetic

The set $Z_n = \left\{0, ..., n-1\right\}$ contains the integers that can exist in a $mod\ n$ equation.

For example $Z_5 = \left\{0, 1, 2, 3, 4\right\}$

Each of the numbers $x$ in $Z_n$ can also be considered an equivalence class of all numbers that are congruent to $x$ ($mod\ n$).

Multiplicative inverse

If $a$ is in $Z_n$ then the multiplicative inverse of $a\ mod\ n$ is a unique $x\in Z_n$ such that $ax \equiv 1\ (mod\ n)$

$x$ only exists if $a$ and $n$ are coprime ($gcd\left(a, b\right) = 1$)

$Z^*_n$ consists of all numbers in $Z_n$ that are coprime with $n$.

It is important to note here that this includes $1$.

$Z^*_n$ is closed under multiplication and, as should be obvious, contains $\phi\left(n\right)$ elements.

If $n$ is prime then $Z^*_n = Z_n\backslash0$

(so $Z^*_n$ contains all non-zero elements of $Z_n$)

Fermat's Little Theorem

This can be stated in two ways:

This theorem can be used as a simple probabilistic primality test amongst other uses.

Euler's Theorem

If $a$ and $n$ are coprime then $$a^{\phi\left(n\right)} \equiv 1\ (mod\ n)$$

This theorem can be used to reduce large powers when working $mod\ n$ $$ 5^{79}\ mod\ 6 = (5^2 \times 5^2)^{19} \times 5^3 $$

as $5^2 = 25 \equiv 1\ mod\ 6$, this is $$\left(1 \times 1\right)^{19} \times 5^3 = 125 \equiv 5\ (mod\ 6)$$

In general if $x \equiv y\ (mod\ n)$ then $a^x \equiv a^y\ (mod\ n)$ or if $x$ and $y$ are equivalent $mod\ n$ then so is a number to the power of each.

Cyclic Groups

Order

For $a \in Z^*_n$ ($a$ is coprime with $n$ and $a < n$) the order of $a$ is that if you start with $t = 1$ and increment $t$ repeatedly, then the order of $a$ is the first value for $t$ for which $a^t \equiv 1\ (mod\ n)$

If this $a \geq 2$ and its order ($t$) is $\phi\left(n\right)$ then $Z^*_n$ is cyclic. This means that when you were raising $a$ to the incrementing $t$ you will have touched every element in $Z^*_n$ before reaching $t$.

Or equivalently every element in $Z^*_n$ is reachable from every other such element by simple exponentiation.

Such an $a$ is called a generator for $Z^*_n$ because one can create all of $Z^*_n$ from it. Note that not all $b \in $Z^*_b$ will be generators.

It turns out $Z^*_n$ is cyclic iff $n$ is either $2$, $4$, a power of an odd prime, or twice a power of an odd prime.

Discrete Logarithms

The discrete logarithm of $b$ with respect to $g$ (for some generator $g$) is the $x$ such that $g^x \equiv b\ (mod\ n)$.

There is an efficient algorithm for computing discrete logarithms in $Z^*_p$ if $p-1$ is smooth. I'm not entirely sure on this because the slides are ambiguous. They say "if $p-1$ has smooth factors" but factors are primes and primes aren't smooth? I'm also assuming $p$ is prime, otherwise it would be $n$.

Back to Computer Security