Number Theory and Abstract Algebra in Cryptography

Number theory

Co-prime numbers

We say two numbers are co-prime if they share only one common divisor, and that divisor is 1. For example, 4 and 7 are co-prime.

Euler’s phi function

It is also called the phi function, it counts the number of positive integers less than $n$ that are co-prime with $n$. The phi function is denoted using greek letter $\varphi$. Consider the below example: $\varphi (8)=4$ Numbers that are co-prime to 8 are: 1, 3, 5, 7.

When with $p$ and $q$ are prime, $p\ne q$ and $n=p\times q$, we have can obtain phi with the below equation: $\varphi (n)=(p-1)(q-1)$

Greatest Common Divisor (GCD)

The greatest common divisor of $a$ and $b$ is the largest integer that divides both $a$ and $b$. For example: $gcd(60,24)=12$

Euclidean algorithm

Euclidean algorithm is a procedure for determining the Greatest Common Divisor (GCD) of two positive integer.

Finite fields

A finite field or Galois field is a mathematical structure consisting of a finite set of numbers where you can perform addition, subtraction, multiplication, and division (except by zero), and the results remain within the field. Finite fields are commonly denoted as $GF(p)$ for prime $p$, where the set contains the integers $\{0,1,2,\dots ,p-1\}$, and all arithmetic is done modulo $p$.

Prime Fields $GF(p)$: The simplest type of finite fields has a prime number $p$ of elements. Arithmetic in this field is done modulo $p$, meaning the result of any operation is reduced by $p$.

Example: In $GP(7)$, the numbers are $\{0,1,2,3,4,5,6\}$, and $5+3$ would be 1 (since $8\mathrm{mod}7=1$)

Primitive root (generator)

A primitive root of a prime number $p$ is a integer $g$ such that every nonzero element in $GF(p)$ can be written as a power of $g$ modulo $p$. In more formal terms, $g$ is a primitive root or generator if the powers $g^1,g^2,\dots ,g^{p-1}\mathrm{mod}p$ generate all the elements of the group $GF(p)$ which consists of the integers $\{1,2,\dots ,p-1\}$

Example: In $GP(7)$, 3 is a primitive root because: $3^1\mathrm{mod}7=3$ $3^2\mathrm{mod}7=2$ $3^3\mathrm{mod}7=6$ $3^4\mathrm{mod}7=4$ $3^5\mathrm{mod}7=5$ $3^6\mathrm{mod}7=1$

This show that the power of 3 generate all the elements $\{1,2,3,4,5,6\}$, so 3 is a primitive root or generator.

Discrete Logarithm Problem (DLP)

According to the trapdoor property, it is computationally infeasible to compute the discrete logarithm equation below, where $g$, $p$ and $y$ are given, $g$ is a primitive root of $p$, and $p$ is extremely large (greater than 2048 bits to represent $p$). $y=g^x\mathrm{mod}p$

Abstract algebra

---

Back to parent page: Cyber Security and Security Engineering