Algebraic structures
Relevant readings: (Menezes, Oorschot, and Vanstone 1996) 2.5–2.6, (Hoffstein, Pipher, and Silverman 2014) 2.10
Note: We’ll take the proofs of the results here for granted in this course, but you can check the reference above for the full proofs if you’re interested.
First of all, why?
To put it simply, an algebraic structure is a set with additional features. For example, if you have a set of nonnegative integers less than \(n\) and slap it with addition and multiplication operations along with a bunch of properties, then you’ve got \(\ZZ_n\), the ring of integers modulo \(n\).
Algebraic structures are prominent in modern cryptography, where public-key cryptosystems like RSA work with rings of integers modulo a large semiprime, Diffie–Hellman key exchange works with finite cyclic groups, and symmetric-key primitives like AES and RC4 uses finite fields. Modern cryptography also relies on (yet proven) assumptions about these algebraic structures, particularly about the inefficiency of factoring integers and taking discrete logarithms.
Groups
A group \((G, \cdot)\) is a set \(G\) together with a binary operation \(\cdot\), such that these properties hold:
-
Closure: If \(x, y \in G\), then \(x \cdot y \in G\).
-
Associativity: For all \(x, y, z \in G\), \((x \cdot y) \cdot z = x \cdot (y \cdot z)\).
-
Identity: There exists an element \(e \in G\) (called the identity element), such that \(x \cdot e = e \cdot x = x\) for all \(x \in G\).
-
Inverses: For each \(x \in G\), there exists a unique element \(y \in G\) (called the inverse of \(x\)), such that \(x \cdot y = y \cdot x = e\).
If \((G, \cdot)\) additionally satisifies the commutative property, i.e., for all \(x, y \in G\) we have \(x \cdot y = y \cdot x\), then it is an abelian group.
Some might call it an abuse of notation, but we usually refer to the group \((G, \cdot)\) by its underlying set \(G\) instead, and we’ll do so for convenience.
A group \(G\) is finite if \(\Len{G}\) is finite. The number of elements in a finite group is called its order.
-
The set of integers under addition forms a group.
-
The set \(\ZZ_n\) under multiplication does not form a group. On the other hand, \(\ZZ_n\) under addition does form a group.
Subgroups and cyclic groups
If \(H\) is a non-empty subset of \(G\) and \((H, \cdot)\) is also a group, then \(H\) is a subgroup of \(G\), usually denoted by \(H \le G\). Furthermore, if \(H \le G\) and \(H \ne G\), then \(H\) is a proper subgroup of \(G\).
A group \(G\) is cyclic if there is an element \(g \in G\) such that for all \(x \in G\) there is an integer \(k\) with \(x = g^k\). Such an element \(g\) is called a generator of \(G\).
If \(G\) is a group and \(a \in G\), then the set of all powers of \(a\) forms a cyclic subgroup of \(G\), called the subgroup generated by \(a\), denoted by \(\gen{a}\).
Let \(G\) be a group and \(a \in G\). The order of \(a\) is the smallest positive integer \(k\) such that \(a^k = e\), provided that such an integer exists. If not, then the order of \(a\) is defined to be \(\infty\).
If \(G\) is a finite group and \(H\) is a subgroup of \(G\), then \(\Len{H}\) divides \(\Len{G}\). Hence, if \(a \in G\), the order of \(a\) divides \(\Len{G}\).
Powers, primitive roots, and discrete logarithms
Let \(G\) be any group. Then for any \(x \in G\) and positive integer \(k\), the expression \(x^k\) is the product of \(x\) with itself \(k\) times: $$x^k = \underbrace{x \cdot x \cdots x}_{\text{$k$ times}}.$$ If \(k = 0\), then \(x^0 = e\).
Let’s consider \(\ZZ_n^\ast\), the set of all positive integers less than \(n\) that are relatively prime to \(n\), defined as follows: $$\ZZ_n^* = \Set{a \in \ZZ_n \mid \gcd(a, n) = 1}.$$ The definition also implies $$\Len{\ZZ_n^*} = \phi(n),$$ which is the order of \(\ZZ_n^\ast\).
\(\ZZ_n^\ast\) forms a group under multiplication, so we also call \(\ZZ_n^\ast\) the multiplicative group of integers modulo \(n\).
Let \(g \in \ZZ_n^\ast\). If the order of \(g\) is \(\phi(n)\), then \(g\) is a generator or a primitive element of \(\ZZ_n^\ast\). Thus \(\ZZ_n^\ast\) is cyclic if it has a generator.
Suppose \(G\) is a finite cyclic group of order \(n\). Let \(g\) be a generator of \(G\), and let \(h \in G\). The discrete logarithm of \(h\) to the base \(g\), denoted \(\log_g h\), is the unique integer \(x\) (where \(0 \le x \le n-1\)) such that \(g^x = h\).
Consider the group \(\ZZ_{17}^\ast\). The discrete logarithm of \(13\) with respect to base \(3\) is \(4\), because $$3^4 = 81 = 13 \quad\text{in $\ZZ_{17}^*$}.$$ As such we denote this as \(\log_3 13 = 4\).
Notice that taking the discrete logarithm is the inverse operation of modular exponentiation, in the same way logarithms and exponentiation are inverses in the \(\RR\) world, but you should also note that the discrete logarithm bears little resemblance to the continuous logarithm defined on the real or complex numbers.
Rings
A ring \((R, +, \cdot)\) is a set \(R\) together with two binary operations \(+\) and \(\cdot\) (we’ll call them addition and multiplication, respectively), such that these properties hold:
-
\(R\) forms an abelian group under \(+\), with \(0\) as the additive identity.
-
Associativity under \(\cdot\): For all \(x, y, z \in R\), \((x \cdot y) \cdot z = x \cdot (y \cdot z)\).
-
Identity for \(\cdot\): There exists an element \(1 \in R\) (called the multiplicative identity) for which \(1 \ne 0\), such that \(x \cdot 1 = 1 \cdot x = x\) for all \(x \in R\).
-
Distributivity: For all \(x, y, z \in R\), \(x \cdot (y + z) = x \cdot y + x \cdot z\) and \((x + y) \cdot z = x \cdot z + y \cdot z\).
If \(R\) additionally satisifies the commutative property for \(\cdot\), i.e., for all \(x, y \in R\) we have \(x \cdot y = y \cdot x\), then it is a commutative ring.
We have already seen \(\ZZ\) and \(\ZZ_n\), both of which also happen to be commutative rings.
Fields
Intuitively, a field supports the notion of addition, subtraction, multiplication, and division.
A field is a commutative ring in which all nonzero elements have multiplicative inverses.
-
The set of rationals \(\QQ\) under addition and multiplication forms a field, since for every \(p/q \in \QQ\), the additive inverse is \(-p/q\) and the multiplicative inverse is \(q/p\).
-
The sets \(\RR\) under addition and multiplication form a field, since for every \(x \in \RR\), the additive inverse is \(-x\) and the multiplicative inverse is \(1/x\).
-
\(\ZZ_n\) under addition and multiplication forms a field when \(n\) is prime, since for every \(x \in \ZZ_n\), the additive inverse is \(n-x\) and the multiplicative inverse is \(x^{-1}\) (which we can compute using the extended Euclidean algorithm).
Divisibility and quotient rings
The concept of divisibility, originally introduced for the integers \(\ZZ\) can be generalized to any ring.
Let \(a\) and \(b\) be elements of a ring \(R\) with \(b \ne 0\). We say that \(b\) divides \(a\), or that \(a\) is divisible by \(b\), if there is an element \(c \in R\) such that $$a = b \cdot c.$$
Recall that an integer is called a prime if it has no nontrivial factors. What is a trivial factor? We can “factor” any integer by writing it as \(a = 1 \cdot a\) and as \(a = (-1)(-a)\), so these are trivial factorizations. What makes them trivial is the fact that \(1\) and \(-1\) have multiplicative inverses.
In general, if \(R\) is a ring and if \(u \in R\) is an element that has a multiplicative inverse \(u^{-1} \in R\), then we can factor any element \(a \in R\) by writing it as \(a = u^{-1} \cdot (u a)\). Elements that have multiplicative inverses and elements that have only trivial factorizations are special elements of a ring, so we give them special names.
Let \(R\) be a ring. An element \(u \in R\) is called a unit if it has a multiplicative inverse, i.e., if there is an element \(v \in R\) such that \(u \cdot v = 1\).
An element \(a\) of a ring \(R\) is said to be irreducible if \(a\) is not itself a unit and if in every factorization of a as \(a = b \cdot c\), either \(b\) is a unit or \(c\) is a unit.
We have noted in the previous lecture notes that the integers \(\ZZ\) are uniquely factorizable (due to the fundamental theorem of arithmetic). Not every ring has this important unique factorization property though, but those that do are called unique factorization domains (UFDs).
Polynomial rings
Let \(K\) be a field (or more generally, a commutative ring). We define a polynomial in \(x\) over \(K\) as an expression of the form $$f(x) = a_n x^n + \cdots + a_2 x^2 + a_1 x + a_0$$ where each coefficient \(a_i \in K\) and \(n \ge 0\). The degree of \(f(x)\), denoted by \(\deg f(x)\) is the largest integer \(m\) such that \(a_m \ne 0\). If the leading coefficient \(a_m\) is equal to \(1\), then \(f(x)\) is monic.
For this section, we let \(K\) be any arbitrary field. The polynomial ring \(K[x]\) is the ring formed by the set of all polynomials in \(x\) where the coefficients come from \(K\). The associated operations are the usual polynomial addition and multiplication, but coefficients are computed in \(K\).
Let \(f(x) \in K[x]\) be a polynomial of degree at least \(1\). Then \(f(x)\) is said to be irreducible over \(K\) if it cannot be written as the product of two polynomials in \(K[x]\), each of positive degree.
Like the ring of integers, the division theorem also applies to polynomials (if you remember how to divide one polynomial by another back in high school, this is exactly what we do here):
If \(g(x), h(x) \in K[x]\), with \(h(x) \ne 0\), then ordinary polynomial long division of \(g(x)\) by \(h(x)\) yields unique polynomials \(q(x), r(x) \in K[x]\) such that $$g(x) = q(x) h(x) + r(x),$$ where \(\deg r(x) < \deg h(x)\). Here, \(q(x)\) is the quotient and \(r(x)\) is the remainder.
Rings of this sort that have a “division with remainder” algorithm are called Euclidean domains.
The polynomial ring \(K[x]/\gen{m(x)}\) consists of polynomials in \(K[x]\) of degree less than \(n = \deg f(x)\), where addition and multiplication are done modulo \(m(x)\).
We can now define common divisors and greatest common divisors in \(K[x]\).
A common divisor of two elements \(a, b \in K[x]\) is an element \(d \in K[x]\) that divides both \(a\) and \(b\). We say that \(d\) is a greatest common divisor of \(a\) and \(b\) if every common divisor of \(a\) and \(b\) also divides \(d\).
The greatest common divisor of \(x^2 - 1\) and \(x^3 + 1\) is \(x + 1\). Notice that $$x^2-1 = (x+1) (x-1) \quad\text{and}\quad x^3+1 = (x+1)(x^2-x+1)$$ so \(x+1\) is a common divisor. I will leave it to you to check that it is the greatest common divisor.
Finite fields
Finite fields (also called Galois fields) are fields with a finite number of elements. Any finite field has order \(p^n\) (thus contains \(p^n\) elements) for some prime \(p\) and integer \(n \ge 1\). For every prime power order \(p^n\), there is a unique finite field of order \(p^n\). We denote this field by \(\FF_{p^n}\) or sometimes \(\mathrm{GF}(p^n)\). When \(n = 1\), we get \(\ZZ_p\), the ring of integers modulo a prime.
For example, AES uses the finite field \(\FF_{256}\), defined by the polynomial ring \(\ZZ_2[x]/\gen{m(x)}\) where \(m(x) = x^8 + x^4 + x^3 + x + 1\).
Finite field arithmetic
Let \(m(x)\) be a monic irreducible polynomial over \(\FF_2\). Then the finite field with \(2^n\) elements \(\FF_{2^n}\) is defined as the polynomial ring \(\FF_2[x]/\gen{m(x)}\), where \(m(x)\) is the modulus such that \(n = \deg m(x)\).
Addition in \(\FF_{2^n}\) is the usual polynomial addition where the coefficients are added over \(\FF_2\). Since \(-1 = 1 ;\text{(in $\FF_2$)}\), subtraction is exactly the same as addition. As the order of the finite field is power of \(2\), we can represent an element of \(\FF_{2^n}\) as bits (where the \(i\)th least significant bit is set if there is an “\(x^i\)” term). Then addition/subtraction is identical to the XOR operation.
In “normal arithmetic” we would have a term like \(2x^6\), but this
becomes \(0x^6\) when we reduce the coefficients modulo \(2\).
$$\begin{align}
&(x^6 + x^4 + x + 1) + (x^7 + x^6 + x^3 + x) \\
&= x^7 + x^6 + x^6 + x^4 + x^3 + x + x + 1 \\
&= x^7 + x^4 + x^3 + 1
\end{align}$$ We can represent \(x^6 + x^4 + x + 1\) and
\(x^7 + x^6 + x^3 + x\) in binary as 01010011 and 11001010
respectively. Then we have:
$$\texttt{01010011} \oplus \texttt{11001010} = \texttt{10011001}$$
which corresponds to \(x^7 + x^4 + x^3 + 1\).
Multiplication in \(\FF_{2^n}\) is done using polynomial multiplication and then dividing the product by the modulus, thus the remainder is the actual product.
Suppose we’re working over \(\FF_2[x]/\gen{x^8+x^4+x^3+x+1}\). To multiply \(x^6 + x^4 + x + 1\) and \(x^7 + x^6 + x^3 + x\): $$\begin{align} &(x^6 + x^4 + x + 1) (x^7 + x^6 + x^3 + x) \\ &= (x^{13} + x^{12} + x^9 + x^7) + (x^{11} + x^{10} + x^7 + x^5) + (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x) \\ &= x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x \end{align}$$ and then $$\begin{align} &(x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x) \bmod (x^8+x^4+x^3+x+1) \\ &= 1. \end{align}$$
Getting the multiplicative inverse of an element in \(\FF_{2^n}\) can be done using the extended Euclidean algorithm, and division in \(\FF_{2^n}\) is defined by \(a / b = a b^{-1}\) for any \(a, b \in \FF_{2^n}\).
References
-
Hoffstein, Jeffrey, Jill Pipher, and Joseph H. Silverman. 2014. An Introduction to Mathematical Cryptography. 2nd ed. Springer-Verlag New York. http://link.springer.com/10.1007/978-0-387-77993-5.
-
Menezes, Alfred J., Paul C. van Oorschot, and Scott A. Vanstone. 1996. Handbook of Applied Cryptography. CRC Press.