Note: This isn't a blog post; I wrote it for UBC's CPSC 436S (cybersecurity) course when I got to TA it in 2024. It was put here to test the MathML-generating abilities of the script that compiles this site. Since it also works as a general page about the basics of cryptography-related math, it lives here now.
Unfortunately, the UBC computer science curriculum doesn't include much discrete math, apart from the intro in CPSC 121. This page will try to fill in the gap. It will present much more math than is required for CPSC 436S, both for your understanding of asymmetric cryptography, and hopefully to also show that the math itself is interesting.
Modern cryptography depends on the existence of one-way functions. Informally speaking, these are functions where finding the output from an input is easy (can be done in polynomial time), but finding the input given an output is hard.
You might find it concerning that no one knows if one-way functions actually exist. If someone did prove they exist, then we would know P != NP. We do the next best thing by using things that look like one-way functions and praying. The two hopefully-one-way functions we cover in class are:
The above terminology will need some explaining. Along with relevant definitions and notation, this page offers:
Recall that a prime number is an integer greater than 1 which can't be factored further; its only divisors are one and itself.
For any number, we can get its list of prime factors by repeated division. Let $f$ be a function that does this, which takes a positive integer and produces an orderless array of its prime factors, so $f(12)=f({2}^{2}\cdot 3)=\{2,2,3\}$.
It is clear that every list of prime numbers corresponds to exactly one product (multiply them all together and you'll get the same result every time). Notably, the reverse is also true: every number corresponds to exactly one unordered list of factors. This uniqueness of a number's prime factorization is known as the fundamental theorem of arithmetic. If you are familiar with the term, we can say our function $f$ is a bijection between the positive integers and the set of unordered lists of primes.
Every whole positive number* $x$ is either prime (i.e. $f(x)$ has length 1) or composite ($f(x)$ has length $\ge 2$). Two numbers are coprime or relatively prime if they share no factors at all.
*When we're talking about multiplication, 1 is a more of a no-op than a number, so it doesn't count as a number for this sentence. It is neither composite nor prime; you can think of $f(1)$ to have length 0. More on 1 being the identity of multiplication later.
To do anything interesting with our numbers, we need to define the rules they should follow.
Roughly speaking, a field is a set where math ($+,-,\times ,\xf7$) works in the usual way. Precisely, a field is a set $S$ along with two functions $+$ ("addition") and $\cdot $ ("multiplication") where the following rules hold:
Usually these rules are combined for brevity, but we'll keep the list long so we can choose ones to cross out later. If all of these are true for your choices of $S,+,\cdot $, then you have yourself a field!
No.
Number 9. There is no integer $x$ such that $3\cdot x=1$, so 3 has no multiplicative inverse in $\mathbb{Z}$.
Yes.
By defining all the rules we needed to do arithmetic, we can find another field to do arithmetic in. The field we define next will also get us closer to a real explanation of the discrete log problem mentioned above.
Sort the set of all integers into 5 buckets (congruence classes) depending on the result of taking the integer modulo 5. We can denote $[1]$ to mean the congruence class 1 goes in, so $[1]=[6]=[-4]$ and
Then by defining addition as $[a]+[b]=[a+b]$ and multiplication as $[a]\cdot [b]=[a\cdot b]$, all rules hold! (proof of 0-8 left as an exercise to the reader).
The least intuitive thing here is finding the multiplicative inverse of each congruence class. If we were dealing with the rational numbers, finding this inverse is as easy as swapping the numerator and denominator. In ${\mathbb{Z}}_{5}=\{[0],[1],[2],[3],[4]\}$, the multiplicative identity is $[1]$, and we can see $[1]\cdot [1]=[1]$, $[2]\cdot [3]=[6]=[1]$, and $[4]\cdot [4]=[16]=[1]$, so we know ${[1]}^{-1}=[1]$ ${[2]}^{-1}=[3]$, ${[3]}^{-1}=2$, and ${[4]}^{-1}=[4]$. So everything but $[0]$ is invertible. This means ${\mathbb{Z}}_{5}$ along with modular addition and multiplication is indeed a field.
pow(x, -1, p)
will find the inverse of
x
mod p
.
${[1]}^{-1}=[1]$
${[2]}^{-1}=[4]$ and ${[4]}^{-1}=[2]$
${[3]}^{-1}=[5]$ and ${[5]}^{-1}=[3]$
${[6]}^{-1}=[6]$
since (${[-1]}^{2}=[1]$)
$[-0]=[0]$
$[-1]=[6]$ and $[-6]=1$
$[-2]=[5]$ and $[-5]=2$
$[-3]=[4]$ and $[-4]=3$
Yes. This is a property we get as a reward for defining rules.
Another fun property of fields: given a natural number $n$, there is either exactly one or zero finite fields with $n$ elements (having order $n$). This is not true of other mathematical objects; for example, there can be many dissimilar groups of the same order. The finite field of size $n$ exists if and only if $n$ is a prime power: $n={p}^{k}$ for some prime $p$ and positive integer $k$. Since there is only one finite field of a given order, we call it "the Galois field of order ${p}^{k}$ " or $GF({p}^{k})$. Simple modular math allows us to understand fields where $k=1$.
When we do math in ${\mathbb{Z}}_{n}=\{[0],[1],\mathrm{\dots}[n-1]\}$ with non-prime $n$, we run into issues with invertibility. Take ${\mathbb{Z}}_{10}$ and attempt to find the multiplicative inverse of $[2]$: no matter what, $[2]$ makes the product even, so getting to $[1]$ is impossible. So ${\mathbb{Z}}_{10}$ isn't a field, but the remaining properties are worth noting.
Since we're talking about modular arithmetic, this will be true anyway, but we don't need commutative multiplication in a ring (for example, the set of 2x2 matrices with integer entries form a non-commutative ring).
Yes.
$[0]$ (of course), $[2]$, $[4]$, $[6]$, $[8]$, $[5]$.
If we choose a non-prime $n$ for ${\mathbb{Z}}_{n}=\{[0],[1],\mathrm{\dots}[n-1]\}$, we don't get a field, but we still get a ring as a participation medal.
You might notice something in common between the troublesome elements of ${\mathbb{Z}}_{10}$ with no multiplicative inverse: they share common factors with 10. The invertible elements, on the other hand, are coprime to 10. This count of coprime-to-$n$ numbers that are smaller than $n$ is denoted by $\phi (n)$, where $\phi $ is Euler's totient function. This function is quick to calculate, but only if we know the factors of $n$.
The only numbers that share factors with $p$ are multiples of $p$, which are too big to be counted by the totient. Hence $\phi (p)$ is $p-1$.
$\phi ({p}^{k})={p}^{k}-{p}^{k-1}$.
There are $pq-1$ numbers less than $pq$. $p-1$ of these are multiples of $q$ (so $q$, $2q$, ..., $(p-1)q$), and similarly, $q-1$ multiples of $p$. They are coprime, so no overlap between their multiples until $pq$. So $\phi (pq)=(pq-1)-(p-1)-(q-1)=(p-1)(q-1)$.
By removing the non-invertible numbers (including 0) from ${\mathbb{Z}}_{n}$, we can reinstate rule 9, but we need to ignore addition, or else we could produce a sum that is one of our removed elements (breaking rule 0). Our result ${\mathbb{Z}}_{n}^{*}$ has $\phi (n)$ elements and is something called a group.
As with rings, we don't need commutativity for a group, but since we're talking about integers modulo $n$, our multiplication is commutative. Commutative groups are usually called abelian.
Usually when you see an introduction to groups, they'll provide a non-abelian example like the group of rotations and reflections of a polygon (${D}_{n}$), the 2x2 matrices with real-number entries and nonzero determinant ($GL(2,\mathbb{R})$), the group of moves on the rubik's cube, etc.
We call ${\mathbb{Z}}_{n}^{*}$ "the multiplicative group of integers modulo $n$." It is a handy piece of notation that specifies both the operation and the set we're working with. Our example ${\mathbb{Z}}_{10}^{*}$ would contain $\phi (10)=4$ elements: $[1],[3],[7]$, and $[9]$.
Yes! The field rules give us two copies of the group rules, one using addition, and one using multiplication over the nonzero elements. A short definition of a field is "a set that is an abelian group under +, where nonzero elements are an abelian group under $\cdot $, and the distributive law holds," which would be a pretty unhelpful definition to put at the top of this page.
Fix $g$ and $x$ in some group. What integer $a$ makes ${g}^{a}=x$? In the group ${\mathbb{Z}}_{p}^{*}$, there is no easy way to find $a$ (assuming $p$ was chosen well).
Diffie-Hellman key exchange works in any group where finding the discrete log is hard. In 436S, we only discuss it using the group ${\mathbb{Z}}_{p}^{*}$, but elliptic curve Diffie-Hellman uses a group obtained from points on an elliptic curve in a finite field. RSA operates in the group of integers mod $pq$ under multiplication (so ${\mathbb{Z}}_{pq}^{*}$).
${\mathbb{Z}}_{p}$ is also a field. We can just find the multiplicative inverse of $g$ in the field, which is quick to do, and then pick $a={g}^{-1}x$.
A cyclic group has an additional rule: There must be some element in the set (usually given the letter $g$) such that $$\{g,{g}^{2},{g}^{3},\mathrm{\dots}\}=\{g,(g\cdot g),(g\cdot g\cdot g),\mathrm{\dots}\}=S$$ We say $g$ generates the whole group. Angle brackets denote the set of every possible combination (using $\cdot $) of the items inside, where $\u27e8x,y,z\u27e9$ is read as "the group generated by $x$, $y$, and $z$." If a group $G$ is cyclic, then $G$ = $\u27e8g\u27e9$.
Groups in general are not necessarily cyclic. For example, we can make a group of 2-bit binary numbers with XOR as the "multiplication". This is a group, but no 2-bit binary number generates all of them through repeated XORs: $\u27e800\u27e9=\{00\}$, $\u27e801\u27e9=\{01,00\}$, $\u27e810\u27e9=\{10,00\}$, $\u27e811\u27e9=\{00,11\}$
Back to our multiplicative groups over the integers, we may find ourselves wanting a generator of ${\mathbb{Z}}_{n}^{*}$, (e.g. for the Diffie-Hellman parameter $g$). In this particular kind of group, a generator is called a primitive root modulo $n$ (but we'll stick with "generator" for now). Interestingly:
{$[3]$, $[{3}^{2}]=[9]$, $[{3}^{3}]=[7]$, $[{3}^{4}]=[1]$}. So ${\mathbb{Z}}_{10}^{*}=\u27e8[3]\u27e9$, meaning $[3]$ generates the group.
No. $\u27e8[9]\u27e9=\{[9],[1]\}$, which is not equal to ${\mathbb{Z}}_{10}^{*}=\{[1],[3],[7],[9]\}$
Yes. $[1]$ is in the group (by rule 8), so if it's not in $\u27e8g\u27e9$, then $g$ doesn't properly generate the group.
(You could also argue that the inverse ${g}^{-1}$ is in the group somewhere, so ${g}^{-1}={g}^{b}$ for some $b$. Then we loop back when we hit ${g}^{1+b}=g\cdot {g}^{b}=g\cdot {g}^{-1}=[1]$.)
Since $[{3}^{6}]=[1]$, we can take any $[{3}^{a}]$ and pick $b$ such that $a+b=$ some multiple of 6. Then $[{3}^{b}]$ is the inverse of $[{3}^{a}]$.
$[{3}^{1}]\cdot [{3}^{5}]=[1]$, so $[3]$ and $[5]$ are inverses
$[{3}^{2}]\cdot [{3}^{4}]=[1]$, so $[2]$ and $[4]$ are inverses
$[{3}^{3}]\cdot [{3}^{3}]=[1]$, so $[6]$ is its own inverse
and, of course, $[{3}^{6}]=[1]$ is its own inverse.
Here is an example of finding generators of ${\mathbb{Z}}_{17}^{*}$ by brute force. Can you spot any patterns?
# [[pow(g, i, 17) for i in range(1, 17)] for g in range(1, 17)] i=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | generator? g= ----------------------------------------------------------------+----------- 1 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] | 2 [2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9, 1] | 3 [3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1] | yes 4 [4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13, 1] | 5 [5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1] | yes 6 [6, 2, 12, 4, 7, 8, 14, 16, 11, 15, 5, 13, 10, 9, 3, 1] | yes 7 [7, 15, 3, 4, 11, 9, 12, 16, 10, 2, 14, 13, 6, 8, 5, 1] | yes 8 [8, 13, 2, 16, 9, 4, 15, 1, 8, 13, 2, 16, 9, 4, 15, 1] | 9 [9, 13, 15, 16, 8, 4, 2, 1, 9, 13, 15, 16, 8, 4, 2, 1] | 10 [10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12, 1] | yes 11 [11, 2, 5, 4, 10, 8, 3, 16, 6, 15, 12, 13, 7, 9, 14, 1] | yes 12 [12, 8, 11, 13, 3, 2, 7, 16, 5, 9, 6, 4, 14, 15, 10, 1] | yes 13 [13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4, 1] | 14 [14, 9, 7, 13, 12, 15, 6, 16, 3, 8, 10, 4, 5, 2, 11, 1] | yes 15 [15, 4, 9, 16, 2, 13, 8, 1, 15, 4, 9, 16, 2, 13, 8, 1] | 16 [16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1] |
It would be very useful if the pattern of ones in the right-hand column held true for any element of any ${\mathbb{Z}}_{n}^{*}$; that would allow huge exponents to be reduced (modulo 16 in this case).
Not only is it true (for coprime $a$ and $n$), but we now have enough tools to prove it! Let ${\mathbb{Z}}_{n}^{*}$ be cyclic with generator $g$, so the whole group can be written as a list (call it ${L}_{1}$) $${\mathbb{Z}}_{n}^{*}={L}_{1}=\{g,{g}^{2},{g}^{3},\mathrm{\dots}{g}^{\phi (n)}\}$$ We know all the group's elements are in ${L}_{1}$, just in an unknown order. (recall the elements are $[1],[2],\mathrm{\dots},[n-1]$ minus any terms not coprime to $n$). Let $a$ be any element of the group. Notice that the list $${L}_{2}=\{ag,a{g}^{2},a{g}^{3},\mathrm{\dots}a{g}^{\phi (n)}\}$$ is some permutation of ${L}_{1}$: multiplication is invertible, so we can't multiply two different things by $a$ and get the same thing out. Then, since the lists contain the same elements, and we are in a commutative group, the products of all elements in the list remains the same: $$\text{Prod}({L}_{2})=\text{Prod}({L}_{1})$$ $$\prod _{i=1}^{\phi (n)}a{g}^{i}=\prod _{i=1}^{\phi (n)}{g}^{i}$$ Factoring all the $a$ terms out, we get: $${a}^{\phi (n)}\prod _{i=1}^{\phi (n)}{g}^{i}=\prod _{i=1}^{\phi (n)}{g}^{i}$$ Finally, multiplying both sides by the inverse of ${\prod}_{i=1}^{\phi (n)}{g}^{i}$ (which is just some member of the group, and with your knowledge of how inverses work, you might know which one): $${a}^{\phi (n)}=[1]\phantom{\rule{0.949em}{0ex}}(modn)$$ which is exactly Euler's theorem. $\mathrm{\square}$
Fermat's little theorem follows straight from Euler's by substituting prime $p$ for $n$: $${a}^{p-1}=[1]\phantom{\rule{0.949em}{0ex}}(modp)$$ So we know that, no matter what element we pick from the multiplicative group modulo $n$, raising it to the $\phi (n)$ (the size of the group) will give us 1.
The proof above is handy because it doesn't require any definitions beyond what we already have. Admittedly, it doesn't provide much intuition as to why.
Then (with some details intentionally left out) Euler's theorem is Lagrange's theorem applied to the group ${\mathbb{Z}}_{n}^{*}$ and the subgroup $\u27e8a\u27e9$.
%
operator, which is a different thing (and even this operator can refer
to different things; try calculating (-1 % 5)
in python, and
again into your browser console.) (mod $n$) is a statement about the world
we're living in when reading something like $1\equiv 100$ (mod $n$).
If you would like to learn more, The Joy of Cryptography is a wonderful and well-written undergraduate-level textbook. It teaches cryptography along with the underlying math, has sane notation, and is freely available online. See chapters 0.1, 0.2, 0.4, 13.1, and 14.1 for things relevant to this webpage.