Appendix: Algebra
A quick primer to essential notions useful in cryptography. While this aims to be precise, it cannot and will not be exhaustive; please check out the wealth of resources available to students of cryptography1234.
Modular arithmetic
Remainder after division of $a$ by $n$:
$$a \pmod{n}=r$$Congruence
$a$ is congruent to $b$ (modulo $n$) if and only if $n$ divides $a-b$:
$$ \begin{align*} a &\equiv b \pmod{n} \iff n \mid a-b \\ a & -b = kn \quad \text{ for some }k \end{align*} $$Congruence / residue class
The set of all integers
$$ a+kn \quad \forall k$$is the congruence / residue class of $a$ modulo $n$, i.e., all integers with the same remainder as $a$ after division by $n$.
Groups
Group
A set $\mathbb{G}$ with an operation $\circ$ such that it is:
- closed under $\circ: \quad x_1 \circ x_2 \in \mathbb{G} \quad \forall x_1, x_2 \in \mathbb{G}$
- $\exists$ an identity $i\in \mathbb{G}: \quad i \circ x = x \quad \forall x \in \mathbb{G}$
- $\exists$ an inverse $x^{-1}\in \mathbb{G}: \quad x^{-1} \circ x = i \quad \forall x \in \mathbb{G}$
- associative: $(x_1 \circ x_2) \circ x_3 = x_1 \circ (x_2 \circ x_3)$
Cyclic group
Every element of the group may be obtained by repeatedly applying the group operation $\circ$ to a generator element $g$.
- $\exists$ at least one generator $g$ such that $\mathbb{G} = \left(\langle g \rangle,\circ\right)$
Abelian group
In addition to the above, an Abelian group is
- commutative: $x_1 \circ x_2 = \circ x_2 \circ x_1 \quad \forall x_1, x_2 \in \mathbb{G}$
This is often implied unless otherwise stated as non-Abelian.
Order and subgroups
Order
The order of a group generated by $g$ is the smallest positive integer $o$ satisfying $g^o \equiv 1 \pmod{n}$. Equivalently, it is the number of distinct elements of the subgroup $\lbrace g^i\rbrace \pmod{n}$.
Subgroups may be generated by other elements.
Warning
$n-1$ is always a generator of $\lbrace n- 1,1\rbrace \pmod{n}$.
Interesting groups
- The non-negative integers modulo $n$: $(\mathbb{Z}_n, +)$ is an additive cyclic group generated by $1$
- The positive integers modulo $n: x \in \lbrace 1,\ldots n-1\rbrace$ with multiplication ($\cdot$) is a multiplicative group $\mathbb{Z}_n^*$ if $n\in \lbrace 1,2,4,p^k, 2p^k\rbrace$ for $p$ an odd prime
- The points $(x,y)$ solutions to Elliptic Curve equations $E$ over finite fields $\mathbb{F}_p$ form an additive cyclic group $$ E:\quad y^2 = x^3 + ax + b $$ with $a,b \in \mathbb{F}_p$ and $4a^3 + 27b \neq 0$
Finite field
Finite field
Loosely: a finite field $\mathbb{F}$ has finitely many elements with two operations, $+, \cdot$
- All elements form an additive abelian group, with identity $0$
- All non-zero elements form a multiplicative abelian group, with identity $1$
- Multiplication distributes over addition: $a \cdot (b + c) = a\cdot b + a \cdot c$
Example: $\mathbb{Z}_7^*$
3 and 5 are both generators of $\mathbb{Z}_7^*$. The order of elements induced by the powers of $g^i$ is hard to guess without computing all entries of a table, such as below. This also suggests that, given a random element $x \in \mathbb{G}$, it is hard to find an $i$ such that $g^i=x \pmod{n}$.
| $g^i$ | $x \in \mathbb{G}$ |
|---|---|
| $3^1$ | $3$ |
| $3^2$ | $9 \equiv 2 \pmod{7}$ |
| $3^3$ | $27 \equiv 6 \pmod{7}$ |
| $3^4$ | $81 \equiv 4 \pmod{7}$ |
| $3^5$ | $243 \equiv 5 \pmod{7}$ |
| $3^6$ | $729 \equiv 1 \pmod{7}$ |
As expected, $n-1=6$ is a generator of ${6,1} \pmod{7}$:
| $g^i$ | $x \in \mathbb{G}$ |
|---|---|
| $6^1$ | $6 \equiv -1 \pmod{7}$ |
| $6^2$ | $36 \equiv 1 \pmod{7}$ |
| $6^3$ | $216 \equiv -1 \pmod{7}$ |
References
Boneh, D., and Shoup, V. (2023). A graduate course in applied cryptography. In Draft 0.6. https://toc.cryptobook.us/. ↩︎
Heninger, N. (2023). Applied cryptography CSE 207B. https://cseweb.ucsd.edu/classes/fa23/cse207B-a/. ↩︎
Menezes, A. J. (2024). Cryptography 101. https://cryptography101.ca/. ↩︎
Menezes, A. J., Oorschot, P. C. van, and Vanstone, S. A. (1997). Handbook of applied cryptography. https://cacr.uwaterloo.ca/hac/. https://doi.org/10.1201/9780429466335 ↩︎