Foundations of Security Week4 Lecture

Lecture Outline#

1. Review of the Extended Euclidean Algorithm
2. Expressing the GCD as a linear combination
3. Modular multiplicative inverse
4. Introduction to the Chinese Remainder Theorem (CRT)
5. Introduction to the RSA cryptographic algorithm

Learning Outcomes#

By the end of this lecture, students should be able to:

1. Understand the purpose of the Extended Euclidean Algorithm
2. Express the GCD as a linear combination
3. Compute modular multiplicative inverses
4. Identify when a multiplicative inverse exists
5. Solve simultaneous congruence equations using CRT
6. Perform the basic RSA Key Generation

Extended Euclidean Algorithm (Review)#

The Extended Euclidean Algorithm is an algorithm to compute integers 𝑥 and 𝑦 such that. $a\textcolor{red}{x} + b\textcolor{red}{𝑦} = \gcd(a, b)$ By reversing the steps in the Euclidean algorithm, it is possible to find these integers 𝑥 and 𝑦.

Example:

Find $\gcd(12, 34)$ and Express it as a Linear Combination

Solution:

Hence, the coefficients are $\textcolor{red}{x=3}$ and $\textcolor{red}{𝑦=−1}$. This process allows you to find 𝑥 and 𝑦 such that $\textcolor{red}{12x + 34𝑦 = \gcd(12,34)}$

Example:

Find $\gcd(93, 219)$ and Express it as a Linear Combination

Solution:

Hence, the coefficients are $\textcolor{red}{x=33}$ and $\textcolor{red}{𝑦=−14}$.
This process allows you to find 𝑥 and 𝑦 such that $\textcolor{red}{93x + 219𝑦 = \gcd(93, 219) = 3}$

Assignment: Complete these exercises and submit during seminar class

• Find the gcd and Express them as Linear Combinations:

1. $\gcd(120, 35)$
2. $\gcd(145, 252)$
3. $\gcd(100, 240)$

Show how you computed your answers.
Only handwritten solutions.
No copy-paste will be accepted.

Modular Multiplicative Inverse#

The modular multiplicative inverse of an integer $\textcolor{blue}{a}$ modulo $\textcolor{blue}{m}$ is an integer $\textcolor{blue}{x}$ such that the product ax is congruent to 1 modulo m.

$\textcolor{red}{a}x\textcolor{red}{\equiv1 \bmod m}$

Here 𝑥 is the multiplicative inverse of $a$, and we can also write the above equation as

$\textcolor{red}{a \bmod m} = \textcolor{red}{1 \bmod m} \Rightarrow \textcolor{red}{a}x \textcolor{red}{\bmod m} = \textcolor{red}{1}$

The existence of such an $\textcolor{blue}{x}$ depends on $\textcolor{red}{a}$ and $\textcolor{red}{m}$ being coprime, i.e., $\gcd(a,m)=1$. Otherwise we can say that there is no multiplicative inverse.

Example:

Find a number 𝑥 such that: $3x \equiv 1~(\bmod 12)$

Chinese Remainder Theorem#

The Chinese Remainder Theorem (CRT) is a powerful tool in number theory and discrete mathematics that allows you to solve a system of simultaneous linear congruences with different moduli, under the condition that the moduli are pairwise coprime (i.e., the gcd of each pair of moduli is 1).

Assume we have a system of equations:

Where $\textcolor{blue}{m_1,m_2,...,m_𝑘}$ are pairwise coprime. The theorem states that there is a unique solution modulo 𝑀, where 𝑀 is the product of all the moduli ($𝑀 = m_1 \times m_2 \times ... \times m_𝑘$).

Step-by-Step Method to Find the Solution

1. Compute 𝑀: $𝑀 = m_1 \times m_2 \times ... \times m_𝑘$.
2. Compute the partial products: For each 𝑖, calculate $M_i=\frac{M}{m_i}$ ​.
3. Find the modular inverses: For each 𝑖, find an integer $𝑦_𝑖$ ​such that $𝑀_𝑖𝑦_𝑖\equiv1~(\bmod m_𝑖)$. This $𝑦_𝑖$ is the modular inverse of $𝑀_𝑖$ modulo $m_𝑖$.
4. Calculate the solution: The solution 𝑥 can be found as follows:

Example

Let’s solve the system:

Step 1: Compute 𝑀: $\textcolor{blue}{𝑀 = m_1 \times m_2 \times m_3}$. $\textcolor{blue}{𝑀 =} 3 \times 5 \times 7 \textcolor{blue}{=} 105$

Step 2: Compute the partial product $M_i=\frac{M}{m_i}$

Step 3: Find the modular inverses.

• Find $\textcolor{red}{𝑦_1}$ such that $\textcolor{blue}{35\textcolor{red}{𝑦_1}\equiv1~(\bmod3)}$
  $\textcolor{red}{y_1}=\textcolor{red}{2}$ works because
  $35 \times 2 = 70 \equiv 1~(\bmod 3)$
• Find $\textcolor{red}{𝑦_2}$ such that $\textcolor{blue}{21\textcolor{red}{𝑦_2}\equiv1~(\bmod5)}$
  $\textcolor{red}{y_2}=\textcolor{red}{1}$ works because
  $21 \times 1 = 21 \equiv 1~(\bmod 5)$
• Find $\textcolor{red}{𝑦_3}$ such that $\textcolor{blue}{15\textcolor{red}{𝑦_3}\equiv1~(\bmod7)}$
  $\textcolor{red}{y_3}=\textcolor{red}{1}$ works because
  $15 \times 1 = 15 \equiv 1~(\bmod 7)$

Step 4: Calculate the solution.

Thus, $x = \textcolor{red}{23}$ is the unique solution that satisfies all the original congruences.

Assignment: Complete this exercise and submit during seminar class

Determine the value of 𝑥 using the Chinese Remainder Theorem

Show how you computed your answers.
Only handwritten solutions.
No copy-paste will be accepted.

RSA Algorithm#

The RSA algorithm is a widely used public key cryptography system that enables secure data transmission.

Named after its inventors Rivest, Shamir, and Adleman, RSA is based on the practical difficulty of factoring the product of two large prime numbers, a problem known as integer factorization.