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.

Discrete math for cryptography

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.

Computational hardness (as motivation)

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:

Primes and factoring

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 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 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.

Fields

Roughly speaking, a field is a set where math ( + , , × , ÷ ) works in the usual way. Precisely, a field is a set S along with two functions + ("addition") and ("multiplication") where the following rules hold:

  1. Closure: The given operations on elements of S should never "escape" the set. a + b is in S and a b is in S for any a and b in S .
  2. Distributive property: distributes over + , so a ( b + c ) = a b + a c
  3. Addition is associative: ( a + b ) + c = a + ( b + c ) for every choice of a , b , c in S .
  4. Addition is commutative: a + b = b + a for every a , b in S
  5. Additive identity: There is some element (call it I + ) in S where adding it is a no-op. That is, a + I + = a for any a in S . You may recognize I + to be 0 in familiar fields.
  6. Additive inverse: For any a in S , there is an "inverse" element a such that adding it brings you back to the identity: a + ( a ) = I +
  7. Multiplication is also associative
  8. Multiplication is also commutative
  9. Multiplicative identity: There is some I in S such that I a = a for any a in S . You may recognize this to be 1 in familiar fields.
  10. Multiplicative inverse: For any a in S with the exception of a = I + , there is an "inverse" element a 1 in S such that a a 1 = I

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 , + , , then you have yourself a field!

Exercises
Is = { , 1 , 0 , 1 , 2 , } (with normal addition and multiplication) a field?

No.

Which rule does it break from above?

Number 9. There is no integer x such that 3 x = 1 , so 3 has no multiplicative inverse in .

Is (the rational numbers) under normal addition and multiplication a field?

Yes.

Finite fields and modular arithmetic

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

[ 0 ] = { 5 , 0 , 5 , 10 , }
[ 1 ] = { 4 , 1 , 6 , 11 , }
[ 2 ] = { 3 , 2 , 7 , 12 , }
[ 3 ] = { 2 , 3 , 8 , 13 , }
[ 4 ] = { 1 , 4 , 9 , 14 , }

Then by defining addition as [ a ] + [ b ] = [ a + b ] and multiplication as [ a ] [ b ] = [ a 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 5 = { [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] } , the multiplicative identity is [ 1 ] , and we can see [ 1 ] [ 1 ] = [ 1 ] , [ 2 ] [ 3 ] = [ 6 ] = [ 1 ] , and [ 4 ] [ 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 5 along with modular addition and multiplication is indeed a field.

Side note Finding multiplicative inverses in larger fields can be done in polynomial time using the extended Euclidean algorithm. If you're using a newer version of Python, pow(x, -1, p) will find the inverse of x mod p.

Exercises
What are all the multiplicative inverses in 7 ?

[ 1 ] 1 = [ 1 ]
[ 2 ] 1 = [ 4 ] and [ 4 ] 1 = [ 2 ]
[ 3 ] 1 = [ 5 ] and [ 5 ] 1 = [ 3 ]
[ 6 ] 1 = [ 6 ] since ( [ 1 ] 2 = [ 1 ] )

What are all the additive inverses in 7 ?

[ 0 ] = [ 0 ]
[ 1 ] = [ 6 ] and [ 6 ] = 1
[ 2 ] = [ 5 ] and [ 5 ] = 2
[ 3 ] = [ 4 ] and [ 4 ] = 3

(rhetorical question) The elements of n seem to pair up very nicely; every element has a unique inverse. Are the additive and multiplicative inverses always like this?

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 G F ( p k ) . Simple modular math allows us to understand fields where k = 1 .

When we do math in n = { [ 0 ] , [ 1 ] , [ n 1 ] } with non-prime n , we run into issues with invertibility. Take 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 10 isn't a field, but the remaining properties are worth noting.

Rings

A ring is a set S and two operations + , where the following rules hold:
  1. Closure: The given operations on elements of S should never "escape" the set. a + b is in S and a b is in S for any a and b in S .
  2. Distributive property: distributes over + , so a ( b + c ) = a b + a c
  3. Addition is associative: ( a + b ) + c = a + ( b + c ) for every choice of a , b , c in S .
  4. Addition is commutative: a + b = b + a for every a , b in S
  5. Additive identity: There is some element (call it I + ) in S where adding it is a no-op. That is, a + I + = a for any a in S .
  6. Additive inverse: For any a in S , there is an "inverse" element a such that adding it brings you back to the identity: a + ( a ) = I +
  7. Multiplication is associative
  8. Multiplication is commutative (click to see note)

    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).

  9. Multiplicative identity: There is some I in S such that I a = a for any a in S .
  10. Multiplicative inverse: For any a in S with the exception of a = I + , there is an "inverse" element a 1 in S such that a a 1 = I
Exercises
Is = { , 1 , 0 , 1 , 2 , } (with normal addition and multiplication) a ring?

Yes.

Which elements of 10 have no multiplicative inverse?

[ 0 ] (of course), [ 2 ] , [ 4 ] , [ 6 ] , [ 8 ] , [ 5 ] .

If we choose a non-prime n for n = { [ 0 ] , [ 1 ] , [ n 1 ] } , we don't get a field, but we still get a ring as a participation medal.

More modular arithmetic: Euler's Totient

You might notice something in common between the troublesome elements of 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 φ ( n ) , where φ is Euler's totient function. This function is quick to calculate, but only if we know the factors of n .

Exercises
What is φ ( p ) for some prime p ?

The only numbers that share factors with p are multiples of p , which are too big to be counted by the totient. Hence φ ( p ) is p 1 .

What is φ ( p k ) for some prime p and k 1 ? (Hint: how many multiples of p are less than p k ?)

φ ( p k ) = p k p k 1 .

What is φ ( p q ) where p and q are different primes?

There are p q 1 numbers less than p q . p 1 of these are multiples of q (so q , 2 q , ..., ( p 1 ) q ), and similarly, q 1 multiples of p . They are coprime, so no overlap between their multiples until p q . So φ ( p q ) = ( p q 1 ) ( p 1 ) ( q 1 ) = ( p 1 ) ( q 1 ) .

By removing the non-invertible numbers (including 0) from 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 n * has φ ( n ) elements and is something called a group.

Groups

A group is a set S with one operation, , ("multiplication") where the following rules hold:
  1. Closure: The given operations on elements of S should never "escape" the set. a + b is in S and a b is in S for any a and b in S .
  2. Distributive property: distributes over + , so a ( b + c ) = a b + a c
  3. Addition is associative: ( a + b ) + c = a + ( b + c ) for every choice of a , b , c in S .
  4. Addition is commutative: a + b = b + a for every a , b in S
  5. Additive identity: There is some element (call it I + ) in S where adding it is a no-op. That is, a + I + = a for any a in S .
  6. Additive inverse: For any a in S , there is an "inverse" element a such that adding it brings you back to the identity: a + ( a ) = I +
  7. Multiplication is associative
  8. Multiplication is commutative (click to see note)

    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 ( G L ( 2 , ) ), the group of moves on the rubik's cube, etc.

  9. Multiplicative identity: There is some I in S such that I a = a for any a in S .
  10. Multiplicative inverse: For any a in S with the exception of a = I + , there is an "inverse" element a 1 in S such that a a 1 = I

We call 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 10 * would contain φ ( 10 ) = 4 elements: [ 1 ] , [ 3 ] , [ 7 ] , and [ 9 ] .

Exercises
We named our operations arbitrarily and didn't specify what they did, other than requiring an identity and an inverse. Would using rules 0, 2, 4, and 5 (deleting the rest) also give us a group?

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 , and the distributive law holds," which would be a pretty unhelpful definition to put at the top of this page.

The discrete log problem

Fix g and x in some group. What integer a makes g a = x ? In the group 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 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 p q under multiplication (so p q * ).

Exercises
Let p be prime and call the additive group of integers modulo p p + . Let g and x be elements of it. Why is finding an integer a such that g a = x NOT difficult (where exponentiation is repeated addition in this case)?

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 .

Generating a group

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 , } = { g , ( g g ) , ( g g g ) , } = S We say g generates the whole group. Angle brackets denote the set of every possible combination (using ) of the items inside, where x , y , z is read as "the group generated by x , y , and z ." If a group G is cyclic, then G = g .

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: 00 = { 00 } , 01 = { 01 , 00 } , 10 = { 10 , 00 } , 11 = { 00 , 11 }

Back to our multiplicative groups over the integers, we may find ourselves wanting a generator of 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:

Exercises
In the group 10 * , what is [ 3 ] ?

{ [ 3 ] , [ 3 2 ] = [ 9 ] , [ 3 3 ] = [ 7 ] , [ 3 4 ] = [ 1 ] }. So 10 * = [ 3 ] , meaning [ 3 ] generates the group.

Does [ 9 ] also generate 10 * ?

No. [ 9 ] = { [ 9 ] , [ 1 ] } , which is not equal to 10 * = { [ 1 ] , [ 3 ] , [ 7 ] , [ 9 ] }

Say we have a group n * with generator g (so n * = g , g 2 , g 3 , ). If we list all of out g , g 2 , g 3 , ... will we loop back to g a = [ 1 ] at some point?

Yes. [ 1 ] is in the group (by rule 8), so if it's not in g , 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 g b = g g 1 = [ 1 ] .)

In an earlier exercise, we found all inverses in 7 * by guessing and checking and we found that inverses formed neat pairs. Given the additional information that [ 3 ] generates the group and { [ 3 ] , [ 3 2 ] ] , [ 3 3 ] ] , [ 3 4 ] , [ 3 5 ] , [ 3 6 ] } = { [ 3 ] , [ 2 ] , [ 6 ] , [ 4 ] , [ 5 ] , [ 1 ] } in that order, can you find all inverses again without guessing?

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 ] [ 3 5 ] = [ 1 ] , so [ 3 ] and [ 5 ] are inverses
[ 3 2 ] [ 3 4 ] = [ 1 ] , so [ 2 ] and [ 4 ] are inverses
[ 3 3 ] [ 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 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] |

Euler's theorem, Fermat's little theorem

It would be very useful if the pattern of ones in the right-hand column held true for any element of any 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 n * be cyclic with generator g , so the whole group can be written as a list (call it L 1 ) n * = L 1 = { g , g 2 , g 3 , g φ ( n ) } We know all the group's elements are in L 1 , just in an unknown order. (recall the elements are [ 1 ] , [ 2 ] , , [ n 1 ] minus any terms not coprime to n ). Let a be any element of the group. Notice that the list L 2 = { a g , a g 2 , a g 3 , a g φ ( 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: Prod ( L 2 ) = Prod ( L 1 ) i = 1 φ ( n ) a g i = i = 1 φ ( n ) g i Factoring all the a terms out, we get: a φ ( n ) i = 1 φ ( n ) g i = i = 1 φ ( n ) g i Finally, multiplying both sides by the inverse of i = 1 φ ( 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 φ ( n ) = [ 1 ] ( mod n ) which is exactly Euler's theorem.

Fermat's little theorem follows straight from Euler's by substituting prime p for n : a p 1 = [ 1 ] ( mod p ) So we know that, no matter what element we pick from the multiplicative group modulo n , raising it to the φ ( n ) (the size of the group) will give us 1.

Lagrange's theorem

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 n * and the subgroup a .

Notation notes

Conclusion

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.