Mathematical Cryptography II
Theory of Groups Overview
A group is a set G combined with a binary operation * that satisfies the following four properties:
- Identity Law
There is an e ∈ G such that e * a = a * e = a for every a ∈ G.
- Inverse Law
For every a ∈ G there is a (unique) a^−1 ∈ G satisfying;
a * a^−1 = a^−1 * a = e.
- Associative Law
a * (b * c) = (a * b) * c for all a, b, c ∈ G.
- Commutative Law
a * b = b * a for all a, b ∈ G
Addition
Set: All integers {... -2, -1, 0, 1, 2, ...}
Operation: +
Identity Element: 0
Inverse Element: for every a ∈ G, its inverse is -a
Modular Arithmetic Addition
Set: Integers modulo n: {0, 1, 2, 3..., n-1}
Operation: + (mod n)
Identity Element: 0
Inverse Element: For each a, an integer b such that; a + b = 0 (mod n)
Matrix Group Multiplication
Set: All invertible 2 X 2 matrices over R or C
Operation: Matrix multiplication
Identity Element: Identity matrix = I
Inverse Element: For a matrix A, its matrix inverse such that; A x A^-1 = I
Group Types
If the operation is commutative, the group is called an Abelian or Commutative group.
Groups can be finite or infinite. The order of a group is the number of its elements.
How hard is the DLP ?
The discrete logarithm problem is a bit like solving a puzzle, where you need to figure out a special number, called an exponent. Imagine you have a specific operation you can do with numbers, and you want to find out how many times you need to repeat this operation on a base number g to get another number h. This is tough because you have to guess and check a lot of possibilities, especially when the numbers involved are massive.
Guess and Check - Not Practical
If you tried to solve this by simply trying every single possibility one by one, you might end up trying an enormous number of times, especially if the range of possible numbers is huge.
Fast Exponentiation - Still Not Practical
This method starts to feel slow when the numbers get really large, because you still have to do a lot of guesses.
Shanks's BabyStep-GiantStep Algorithm
This method is designed to solve the DLP more efficiently than simply trying brute force.
How it works ?
- Divide and Conquer
Create a 2 smaller list of possibilities.
Find the exponent x solves the DLP equation.
- Setting Up Lists
Baby Steps: Store the powers of g in a list. (g, g^2, g^3, ...)
Giant Steps: Calculate powers of h multiplied by inverse powers of g raised to large increments and store them in another list. (h.g^-n, h.g'-2n, ...)
- Finding a match
Looks for a common element between two lists.
- "Finding a common element" means two calculation methods agree, revealing the solution x. (collision)
- Efficiency
This method significantly reduces the number of operations compared to brute force.
In a group of size 10,000, Shanks's Algorithm needs only around 200 steps to find the answer (200^2 = 10.000) but a brute force would require all 10,000 options.
The Chinese Remainder Theorem (CRT)
Imagine you're trying to figure out a number that, when divided by 3, leaves a remainder of 2, and when divided by 5, leaves a remainder of 1. Doing this by checking each number one by one is so boring and requires a lot of time. The CRT exists to solve this kind of problem quickly and efficiently by finding a number that works for all conditions(aka puzzles) without having to test every single possibility.
Simple Example:
Puzzle 1: Event that occurs every 7 days (weekly on a Monday), and today is Monday. Today could be represented as:
x = 0 (mod 7)
Puzzle 2: A second event that happens every 5 days, and today it's happening too. Today could be represented as:
x = 0 (mod 5)
What are the days that both events will happen again on the same day?
CRT comes to play
The CRT tells that both events will align every 7×5=35 days. So, the next time both events happen on the same day will be 35 days from today.
Mathematical Representation
Looking for an integer x that simultaneously solves both of the puzzles
below:
x = 1 (mod 5)
x = 9 (mod 11)
For the first puzzle, we can say:
x = 1 + 5y (y ∈ Z)
For the second one;
x = 1 + 5y = 9 (mod 11) then, 5y = 8 (mod 11)
Finding modulo inverse:
(a x b = 1 (mod m))
To solve 5y = 8 (mod 11), we need the inverse of 5 modulo 11. This inverse exists because gcd(5, 11) = 1.
5 x b = 1 (mod 11).
Because the modulus is so small that we can find it by trial and error.
5x9 = 45 = 1 (mod 11)
9 is the modular inverse of 5 modulo 11.
Using the Inverse to Solve for y:
Given the equation above:
5y = 8 (mod 11)
Multiply Both Sides by the Inverse of 5 Modulo 11:
Multiply both sides of the equation by 9:
9×5y = 9×8 (mod 11)
Simplify the Equation & Solving y:
Because 9 x 5 = 1 (mod 11), the equation simplifies
y = 72 (mod 11) ⇾ y
Finding x with y:
Since;
x = 1 + 5y
1 + 5x6 = 31
Solving puzzles with composite moduli
Let's find x such that: x^2 = 197 (mod 437)
(437 is a composite number because 437 = 19 × 23. Both 19 and 23 are prime numbers.)
Step 1.
Factor the modulus
437 = 19 × 23
Step 2.
Apply CRT
Since 437 can be factored into two relatively prime numbers, we can split the original congruence into two separate congruences based on these prime factors:
x^2 = 197 = 7 (mod19)
x^2 = 197 = 13 (mod 23)
Step 3.
Simplify the Congruences
- x^2 = 7 (mod 19) and x^2 = 197 = 13 (mod 23)
Because 19 (mod4) = 3, 23 (mod 4)=3;
x^2 = 64 ⇾ x = 8 | -8
x^2 = 36 ⇾ x = 6 | -6
Step 4 with choosing positive solutions 8 and 6.
Apply the CRT Again
x = 8 (mod 19) and x = 6 (mod 23);
Inverse modulo of 6 and 23:
x = 23k + 6 = 8 (mod 19)
23k = 2 (mod 19)
k = 5
Multiply both sides of equation with 5:
5 x 23k = 2 x 5 (mod 19) ⇾ k = 10
Finally:
x = 23 x 10 + 6 = 236 | - 236 for x^2 = 197 (mod 437) equation.
If the modulus were prime, there would be only these "two" square roots. However, since 437 = 19 · 23 is composite, there are two others. In order to find them, we replace one of 8 and 6 with its negative. This leads to the values x = 144 and x = 293.
This means that 197 has 4 square roots modulo 437.