T4QI
T4QI

Group Theory and Modular Arithmetic – Foundations for Basic Cryptography

• 8 min read

Cryptography relies heavily on specific mathematical structures and number theory. This post breaks down the fundamental definitions of Groups, Modular Arithmetic, and key theorems like the GCD and the Chinese Remainder Theorem based on my study notes.

1. Group Theory

To understand modern encryption (like RSA or Elliptic Curve Cryptography), we must first define the algebraic structures they operate on.

Semigroups

A set $S$ combined with a binary operation $\circ$ is a Semigroup if it satisfies:

  1. Closure: For all $a, b \in S$, the result $a \circ b = c$ is also in $S$ ($c \in S$).

  2. Associativity: For all $a, b, c \in S$:

    $$(a \circ b) \circ c = a \circ (b \circ c)$$

Monoids

A Monoid is a Semigroup that includes an Identity Element (denoted as $e$).

  • There exists an element $e$ such that for any $a \in S$:

    $$a \circ e = e \circ a = a$$

Groups

A Group is a Monoid that also possesses an Inverse Element.

  • For every element $a$, there exists an element $b$ such that:

    $$a \circ b = e$$

    (Here, $b$ is considered the inverse of $a$).

Abelian Groups

An Abelian Group is a group that satisfies the Commutative Property.

  • For all $a, b \in S$:

    $$a \circ b = b \circ a$$

Cyclic Groups

A Cyclic Group is a group that can be generated by a single element (a “generator”). By repeatedly applying the group operation to this generator, you can produce every other element in the group.

2. Modular Arithmetic

Modular arithmetic is the system of integer arithmetic where numbers “wrap around” upon reaching a certain value—the modulus.

Definition:

If $a % b = r$, then arithmetic can be expressed as:

$$a = b \cdot q + r$$

Congruence:

We say $a$ is congruent to $b$ modulo $n$ ($a \equiv b \pmod n$) if $n$ divides $(a-b)$.

Core Properties

  1. Reflexivity: $a \equiv a \pmod n$

  2. Symmetry: If $a \equiv b \pmod n$, then $b \equiv a \pmod n$

  3. Transitivity: If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a \equiv c \pmod n$

3. Arithmetic Operations & Proofs

Below are proofs demonstrating how standard arithmetic operations function within a modulus.

Addition Property

Theorem: If $a \equiv b \pmod n$, then $a + k \equiv b + k \pmod n$.

Proof:

  1. $a \equiv b \pmod n$ implies $a = nq + b$.

  2. Add $k$ to both sides:

    $$a + k = nq + b + k$$

  3. Rearranging the right side:

    $$a + k = nq + (b + k)$$

  4. Therefore, $(a + k) \equiv (b + k) \pmod n$.

Multiplication by a Constant

Theorem: If $a \equiv b \pmod n$, then $ak \equiv bk \pmod n$.

Proof:

  1. $a = nq + b$.

  2. Multiply both sides by $k$:

    $$ak = (nq + b)k$$

    $$ak = n(qk) + bk$$

  3. Since $n(qk)$ is a multiple of $n$, the remainder is determined by $bk$.

  4. Therefore, $ak \equiv bk \pmod n$.

Addition of Two Congruences

Theorem: If $a_1 \equiv b_1 \pmod n$ and $a_2 \equiv b_2 \pmod n$, then $(a_1 + a_2) \equiv (b_1 + b_2) \pmod n$.

Proof:

  1. Define $a_1 = nq + b_1$ and $a_2 = np + b_2$.

  2. Add the equations:

    $$a_1 + a_2 = (nq + b_1) + (np + b_2)$$

  3. Group the terms with $n$:

    $$a_1 + a_2 = n(q + p) + (b_1 + b_2)$$

  4. Therefore, $(a_1 + a_2) \equiv (b_1 + b_2) \pmod n$.

Subtraction

Theorem: $a_1 - a_2 \equiv b_1 - b_2 \pmod n$.

Proof:

  1. $a_1 - a_2 = (nq + b_1) - (np + b_2)$

  2. $a_1 - a_2 = n(q - p) + (b_1 - b_2)$

  3. Therefore, $(a_1 - a_2) \equiv (b_1 - b_2) \pmod n$.

Multiplication of Two Congruences

Theorem: $a_1 a_2 \equiv b_1 b_2 \pmod n$.

Proof:

  1. $a_1 = nq + b_1$ and $a_2 = np + b_2$.

  2. Multiply the equations:

    $$a_1 a_2 = (nq + b_1)(np + b_2)$$

  3. Expand the terms:

    $$a_1 a_2 = n^2 qp + nq b_2 + np b_1 + b_1 b_2$$

  4. Factor out $n$ from the first three terms:

    $$a_1 a_2 = n(nqp + q b_2 + p b_1) + b_1 b_2$$

  5. Since the first part is divisible by $n$, the remainder is $b_1 b_2$.

    $$a_1 a_2 \equiv b_1 b_2 \pmod n$$

Exponentiation

Theorem: $a^k \equiv b^k \pmod n$.

Logic:

We have already proved that $a_1 a_2 \equiv b_1 b_2$. If we simply multiply the right side by itself $k$ times ($b \cdot b \dots b$) and the left side by itself $k$ times ($a \cdot a \dots a$), the congruence holds.

4. Greatest Common Divisor (GCD)

Theorem: $gcd(a, b) = gcd(b, a % b)$.

Proof via Linear Combination:

First, we establish that if a number $d$ divides $a$ ($d|a$) and $d$ divides $b$ ($d|b$), it divides any linear combination of them.

  • $a = dq$ and $b = dp$

  • $ax + by = (dq)x + (dp)y = d(qx + py)$

  • Therefore, $d$ divides $(ax + by)$.

Proving the Euclidean Step:

Let $a = qb + r$ (where $r = a % b$).

  1. Let $d = gcd(a, b)$. Since $d|a$ and $d|b$, and $r = a - qb$, then $d$ must divide $r$.

  2. Let $d’ = gcd(b, r)$. Since $d’|b$ and $d’|r$, and $a = qb + r$, then $d’$ must divide $a$.

  3. Since $d$ divides the set ${b, r}$ and $d’$ divides the set ${a, b}$, the greatest common divisors must be equal.

    $$d’ \leq d$$

5. Chinese Remainder Theorem (CRT)

The Chinese Remainder Theorem is an ancient result (dating back to the 3rd century AD) that deals with solving systems of simultaneous congruences.

In modern cryptography, CRT is a performance powerhouse. It allows us to perform calculations modulo a very large number $N$ by breaking that number down into its prime factors ($p$ and $q$).

  • RSA Optimization: Instead of performing one massive calculation modulo $N$ (where $N$ is 2048+ bits), computers can do two smaller calculations modulo $p$ and modulo $q$, and then combine them using CRT. This often makes decryption up to 4 times faster!

The Theorem

If we have a system of congruences where the moduli $n_1, n_2, \dots, n_k$ are pairwise coprime (meaning $\gcd(n_i, n_j) = 1$ for all $i \neq j$), then there exists a unique solution for $x$ modulo $N = n_1 n_2 \dots n_k$.

The System:

$$x \equiv a_1 \pmod{n_1}$$

$$x \equiv a_2 \pmod{n_2}$$

$$\dots$$

$$x \equiv a_k \pmod{n_k}$$

Constructing the Solution

To find $x$ computationally (as we do in the script below), we use the following construction:

  1. Calculate $M$, the product of all moduli: $M = n_1 \times n_2 \times \dots \times n_k$.

  2. For each equation $i$, calculate $M_i = M / n_i$.

  3. Calculate the modular inverse $y_i$ such that $M_i \cdot y_i \equiv 1 \pmod{n_i}$.

  4. The solution is the sum:

    $$x = \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \pmod M$$

6. Python Implementations

Here are the Python scripts implementing the core concepts discussed above.

Basic GCD

A recursive implementation of the Euclidean algorithm.

Python

PYTHON 
from sys import argv


def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)


if __name__ == "__main__":
    print(gcd(int(argv[1]), int(argv[2])))

Extended Euclidean Algorithm (EEA)

This script finds coefficients $x$ and $y$ such that $ax + by = \gcd(a, b)$. This is crucial for finding modular inverses in cryptography.

Python

PYTHON 
from sys import argv


def eea(a: int, b: int) -> str:
    r0, r1 = a, b
    q = r0 // r1
    r = r0 % r1

    x_prev, x = 1, 0
    y_prev, y = 0, 1

    while r != 0:
        x_prev, x = x, x_prev - (q * x)
        y_prev, y = y, y_prev - (q * y)
        r0, r1 = r1, r0 % r1
        q = r0 // r1
        r = r0 % r1
    return (
        f"In the form of a*x + b*y = gcd(a,b) we got ({a} * {x}) + ({b} * {y}) = {r1}"
    )


if __name__ == "__main__":
    print(eea(int(argv[1]), int(argv[2])))

Chinese Remainder Theorem (CRT)

This script solves for $x$ given a system of congruences. It calculates the dynamic modulus $M$, partial moduli $M_i$, and their inverses $y_i$ to reconstruct the solution.

Python

PYTHON 
from Crypto.Util.number import inverse
from sys import argv

n = int(argv[1])
numbers = []

for i in range(n):
    a = int(input("enter remainder: "))
    m = int(input("enter the mod: "))
    numbers.append(a)
    numbers.append(m)


def crt(arr: list[int]) -> int:
    arr_a = arr[0::2]
    arr_b = arr[1::2]

    M = 1
    for m in arr_b:
        M *= m

    result = 0
    for i in range(len(arr_a)):
        Mi = M // arr_b[i]
        yi = inverse(Mi, arr_b[i])
        result += arr_a[i] * Mi * yi

    return result % M


print(crt(numbers))

References & Further Reading

For a deeper dive into the number theory concepts discussed here, check out this curated playlist:

Start searching

Enter keywords to search articles.

↑↓ Navigate
↵ Select
ESC Close
CtrlK Shortcut