13 Modular Arithmetics, Set of Residues, Diffie-Hellman, Multiplicative Inverse, Chinese Remainder Theorem

Lecture from: 30.10.2024 | Video: Videos ETHZ

Modular Arithmetics

Addition and Multiplication of Modular Congruences

Let m be a positive integer, and let a, b, c, and d be integers. If $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$, then:

1. Addition: $a+c\equiv b+d(\mathrm{mod}m)$.
2. Multiplication: $a\cdot c\equiv b\cdot d(\mathrm{mod}m)$.

Addition

• Assumptions: $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$. This means there exist integers k and l such that $a=b+km$ and $c=d+lm$.
• Adding the Equations: Adding these equations, we get: $a+c=(b+km)+(d+lm)=(b+d)+(k+l)m$
• Conclusion: Since $(k+l)$ is an integer, we have shown that $a+c$ and $b+d$ have the same remainder when divided by m: $a+c\equiv b+d(\mathrm{mod}m)$

Multiplication

• Assumptions: $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$. This means there exist integers k and l such that $a=b+km$ and $c=d+lm$.
• Multiplying the Equations: Multiplying these equations, we get: $a\cdot c=(b+km)(d+lm)=bd+b(lm)+d(km)+k(lm)m=bd+(bl+dk+klm)m$
• Conclusion: Since $(bl+dk+klm)$ is an integer, we have shown that $a\cdot c$ and $b\cdot d$ have the same remainder when divided by m: $a\cdot c\equiv b\cdot d(\mathrm{mod}m)$

Congruences and Polynomial Expressions in Modular Arithmetic

Let m be a positive integer, and let $f(x_1,...,x_k)$ be a multivariate polynomial in k variables with integer coefficients. If $a_i{\equiv }_m{b}_i$ for $1\le i\le k$, then:

$f(a_1,...,a_k){\equiv }_{m}f(b_1,...,b_k)$

Example:

Proof: Evaluating a polynomial involves a sequence of additions and multiplications. We have already established that congruences are preserved under addition and multiplication modulo m:

Lemma: If $a{\equiv }_{m}b$ and $c{\equiv }_{m}d$, then:

• $a+c{\equiv }_{m}b+d$
• $a\cdot c{\equiv }_{m}b\cdot d$

Therefore, in each step of evaluating the polynomial f, the congruence modulo m will be maintained. Since we are performing a sequence of operations that preserve congruences, the final result of evaluating $f(a_1,...,a_k)$ will be congruent modulo m to the final result of evaluating $f(b_1,...,b_k)$.

The Set of Residues: ${\mathbb{Z}}_m$

The set of residues, denoted by ${\mathbb{Z}}_m$, is a fundamental concept in modular arithmetic.

Definition: The set of residues ${\mathbb{Z}}_m$ is the set of possible remainders when integers are divided by m. It consists of the integers from 0 to m-1: ${\mathbb{Z}}_m=\{0,1,2,\dots ,m-1\}$

Example:

• ${\mathbb{Z}}_5=\{0,1,2,3,4\}$

Lemma: $a{\equiv }_m{R}_m(a)\in {\mathbb{Z}}_m$

This lemma states that any integer a is congruent modulo m to its remainder R_m(a) when divided by m.

Proof

By the Division Algorithm, we can write a as $a=qm+R_m(a)$, where q is the quotient and $R_m(a)$ is the remainder. Since qm is a multiple of m, it is congruent to 0 modulo m. Therefore, we have: $a=qm+R_m(a){\equiv }_{m}0+R_m(a){\equiv }_m{R}_m(a)$

Lemma: $a{\equiv }_{m}b⟺R_m(a)=R_m(b)$

This lemma establishes a key relationship between modular congruences and remainders: Two integers are congruent modulo m if and only if they have the same remainder when divided by m.

Proof

Forward Direction: If $a{\equiv }_{m}b$, then by definition there exists an integer k such that $a=b+km$. Since km is a multiple of m, it is congruent to 0 modulo m. Therefore, we have: $a=b+km{\equiv }_{m}b+0{\equiv }_{m}b$This implies that a and b have the same remainder when divided by m: $R_m(a)=R_m(b)$

Reverse Direction: If $R_m(a)=R_m(b)$, then by the Division Algorithm, we can write a as $a=q_{1}m+R_m(a)$ and b as $b=q_{2}m+R_m(b)$. Since $R_m(a)=R_m(b)$, we have: $a=q_{1}m+R_m(a)=q_{1}m+R_m(b)$ $b=q_{2}m+R_m(b)$ Subtracting the second equation from the first, we get: $a-b=(q_1-q_2)m$

Therefore, $a-b$ is a multiple of m, which implies that $a{\equiv }_{m}b$.

Modular Arithmetic with Polynomials (Corollary 4.17)

This corollary provides a powerful tool for simplifying computations involving polynomials in modular arithmetic. It states that for a multivariate polynomial $f(x_1,...,x_k)$ with integer coefficients, and $m\ge 1$, the remainder of $f(a_1,...,a_k)$ when divided by $m$ is the same as the remainder of $f(R_m(a_1),...,R_m(a_k))$ when divided by $m$.

In other words, we can replace each variable $a_i$ in the polynomial $f$ with its remainder $R_m(a_i)$ modulo $m$ before evaluating the polynomial, and the result will have the same remainder when divided by $m$.

Formal Statement:

Let $f(x_1,...,x_k)$ be a multi-variate polynomial in $k$ variables with integer coefficients, and let $m\ge 1$. Then: $R_m(f(a_1,...,a_k))=R_m(f(R_m(a_1),...,R_m(a_k))).$

Proof:

The proof of this corollary follows directly from the properties of modular congruences and the fact that polynomial evaluation involves a sequence of additions and multiplications.

1. Congruence Preservation: We know that if $a_i{\equiv }_m{b}_i$, then $a_i+b_i{\equiv }_m{b}_i+b_i$ and $a_i\cdot b_i{\equiv }_m{b}_i\cdot b_i$. This means congruences are preserved under both addition and multiplication modulo $m$.
2. Remainders and Congruences: We have previously established that $a_i{\equiv }_m{R}_m(a_i)$ for all $i$.
3. Applying Congruence Preservation: Since each term in the polynomial $f$ is a sum and/or product of the variables, we can repeatedly apply the property of congruence preservation to replace each $a_i$ with its corresponding remainder $R_m(a_i)$. This will lead to a new expression congruent modulo $m$ to the original expression.
4. Resulting Remainder: Since the final expression is congruent modulo $m$ to the original, they have the same remainder when divided by $m$. This means the remainder of $f(a_1,...,a_k)$ is equal to the remainder of $f(R_m(a_1),...,R_m(a_k))$ when divided by $m$.

Example:

Let’s consider the polynomial $f(x_1,x_2)=x_1^2+2x_1{x}_2+x_2^3$, and we want to find the remainder when $f(17,23)$ is divided by 5.

1. Replace with Remainders: $R_5(17)=2$ and $R_5(23)=3$.
2. Evaluate with Remainders: $f(2,3)=2^2+2\cdot 2\cdot 3+3^3=4+12+27=43$.
3. Final Remainder: $R_5(43)=3$.

Therefore, the remainder when $f(17,23)$ is divided by 5 is 3.

Another Example:

This corollary is a crucial tool for simplifying calculations involving polynomials in modular arithmetic. It allows us to work with smaller numbers (remainders) instead of large numbers, significantly reducing the complexity of computations. This is particularly helpful when dealing with large numbers or repeated calculations.

Diffie-Hellman Key Exchange

The Diffie-Hellman (DH) key exchange, a groundbreaking achievement in cryptography, revolutionized secure communication by solving a fundamental problem: how to establish a shared secret key over an insecure channel. Before its invention, secure communication relied on pre-shared secrets, requiring a secure channel for key distribution—a major logistical hurdle, especially in wartime scenarios like WWII and even into the 1970s. This challenge persists today: how can we securely connect to a server over the insecure internet?

Diffie and Hellman’s ingenious solution, introduced in their landmark 1976 paper, leverages modular arithmetic and the concept of one-way functions, allowing two parties to generate a shared secret key without ever exchanging it directly. This seemingly paradoxical achievement remains impactful even today, particularly in a world where the National Security Agency (NSA) and other powerful entities constantly seek to intercept and decipher communications.

One-Way Functions

Central to DH is the concept of a one-way function. A one-way function, $f:A\to B$, is computationally efficient to compute in the forward direction (finding $f(x)$ for any $x\in A$), but computationally infeasible to invert (finding $x$ given $f(x)\in B$). A one-way function need not be injective ; multiple elements in $A$ can map to the same element in $B$. The crucial property is the difficulty of inverting the function.

Formally, a function is considered one-way if there is no known algorithm with polynomial runtime complexity that can compute its inverse. This means the computational effort required to invert the function grows exponentially with the input size, making it practically impossible for large inputs. Even for hypothetical adversaries like the NSA with their advanced computing power, inverting a well-designed one-way function remains a formidable challenge.

Modular Arithmetic and the Discrete Logarithm Problem

Diffie and Hellman’s groundbreaking work leveraged modular arithmetic, specifically exponentiation modulo a large prime number $p$, as a candidate one-way function. Let’s illustrate with a simplified example using $p=19$.

For certain values (called generators or primitive roots, like $g=2$ in our example), the function $y=g^x(\mathrm{mod}p)$ generates all elements from $1$ to $p-1$ as $x$ varies. This forms a cyclic group. Calculating $y$ given $x$, $g$, and $p$ is computationally efficient using algorithms like “square-and-multiply.” However, finding $x$ given $y$, $g$, and $p$ (the Discrete Logarithm Problem or DLP) is computationally hard for large primes, forming the basis of DH’s security. This difficulty of inverting the modular exponentiation function makes it very challenging for even the most sophisticated adversaries, including those with the resources of the NSA, to break the DH protocol.

The Diffie-Hellman Protocol: Secure Key Establishment

The DH protocol allows Alice and Bob to establish a shared secret key $k$ as follows:

1. Public Parameter Agreement: Alice and Bob publicly agree on a large prime $p$ and a generator $g$.

2. Private Key Generation: Alice chooses a secret random integer $x_A$ and Bob chooses a secret random integer $x_B$.

3. Public Key Computation: Alice computes $y_A=g^{x_A}(\mathrm{mod}p)$ and Bob computes $y_B=g^{x_B}(\mathrm{mod}p)$.

4. Public Key Exchange: Alice sends $y_A$ to Bob, and Bob sends $y_B$ to Alice. This exchange happens over the insecure channel. While the NSA or other eavesdroppers can intercept this information, it’s insufficient to compromise the security of the protocol.

5. Shared Secret Calculation:

• Alice computes $k=y_B^{x_A}(\mathrm{mod}p)=(g^{x_B}{)}^{x_A}(\mathrm{mod}p)=g^{x_A{x}_B}(\mathrm{mod}p)$.
• Bob computes $k=y_A^{x_B}(\mathrm{mod}p)=(g^{x_A}{)}^{x_B}(\mathrm{mod}p)=g^{x_A{x}_B}(\mathrm{mod}p)$.

Both Alice and Bob now share the secret key $k$ without ever directly transmitting it. An eavesdropper, knowing $p$, $g$, $y_A$, and $y_B$, faces the computationally hard DLP to determine $x_A$ or $x_B$, and thus, $k$. Even with the resources of the NSA, this task is practically impossible for appropriately chosen large primes $p$.

Beyond Primes and the Quantum Threat

The DH principle extends beyond modular arithmetic with primes ; any group with suitable properties can be used. Elliptic Curve Diffie-Hellman (ECDH) offers similar security with smaller key sizes, making it more practical for certain applications. However, both DH and ECDH are vulnerable to quantum computers running Shor’s algorithm, motivating research into post-quantum cryptography.

Prime Generation and Computational Hardness

Generating large prime numbers is crucial for DH security. Algorithms like the one developed by our beloved professor Ueli Maurer offer efficient prime generation, ensuring the difficulty of the DLP and thus the robustness of the DH protocol. The fundamental assumption of DH’s security is the computational hardness of the DLP, an assumption that is constantly being tested and refined.

Reduction and the Diffie-Hellman Problem

The Diffie-Hellman Problem (DHP) asks whether, given $y_A$ and $y_B$, it’s feasible to compute $k=g^{x_A{x}_B}(\mathrm{mod}p)$. The DHP is computationally equivalent to the DLP ; an efficient solution to one implies an efficient solution to the other. This equivalence highlights the close relationship between the two problems and underscores the difficulty of both. If the NSA had a service that could efficiently compute $k$ given $y_A$ and $y_B$, it would likely imply that they had also found a way to efficiently solve the DLP.

Decisional Diffie-Hellman (DDH)

The Decisional Diffie-Hellman (DDH) problem further explores the hardness of distinguishing $k=g^{x_A{x}_B}(\mathrm{mod}p)$ from a random value. It asks: given $y_A$, $y_B$, and a candidate $K$, can we efficiently determine if $K$ is the correct shared secret $k$ or a randomly generated value? This problem is believed to be difficult, even for an organization like the NSA.

Imagine, for example, that the NSA had a service that could efficiently crack DH and provide you with $k$ given $y_A$ and $y_B$. Could you verify that this $K$ is indeed a valid key? Solving the DDH problem would allow you to do exactly that, potentially undermining the security of the DH protocol.

Practical Security Concerns and Extensions

While DH offers strong theoretical security, practical implementations must consider vulnerabilities like man-in-the-middle attacks. An attacker could intercept the exchange of public keys, pretending to be both Alice and Bob, and establish separate shared secrets with each party. This allows the attacker to decrypt and modify the communication between Alice and Bob without their knowledge.

Authentication mechanisms, such as digital signatures and certificates, are crucial for mitigating these attacks and ensuring the secure deployment of DH. These mechanisms provide a way to verify the authenticity of the parties involved in the key exchange, making it much more difficult for attackers to impersonate legitimate users.

Multiplicative Inverses

The concept of a multiplicative inverse is crucial in modular arithmetic, particularly in the context of solving modular equations. Given an integer $a$ and a modulus $m$, the multiplicative inverse of $a$ modulo $m$ is an integer $x$ that satisfies the congruence:

$a\cdot x{\equiv }_{m}1$

In simpler terms, finding the multiplicative inverse of $a$ modulo $m$ means finding a number $x$ such that when you multiply $a$ and $x$ and take the remainder upon division by $m$, you get 1.

Existence and Uniqueness:

Not every number has a multiplicative inverse modulo $m$. The existence and uniqueness of the inverse depend on the greatest common divisor (GCD) of $a$ and $m$.

Lemma 4.18 states that the congruence equation $ax{\equiv }_{m}1$ has a solution $x$ in $Z_m$ if and only if $\text{gcd}(a,m)=1$. Furthermore, the solution is unique.

Proof:

• ($\Rightarrow$) If $x$ satisfies $ax{\equiv }_{m}1$, then $ax=km+1$ for some integer $k$. Note that $\text{gcd}(a,m)$ divides both $a$ and $m$, hence also $ax-km$, which is 1. Thus $\text{gcd}(a,m)=1$.
• ($\Leftarrow$) Assume now that $\text{gcd}(a,m)=1$. According to Corollary 4.5 there exist integers $u$ and $v$ such that $ua+vm=\text{gcd}(a,m)=1$. Since $vm{\equiv }_{m}0$ we have $ua{\equiv }_{m}1$. Hence $x=u$ is a solution in $Z_m$, and thus $x=R_m(u)$ is a solution in $Z_m$.

To prove uniqueness of $x$ in $Z_m$, suppose there is another solution $x^{\prime }$ in $Z_m$. Then $ax-a{x}^{\prime }{\equiv }_{m}0$, thus $a(x-x^{\prime }){\equiv }_{m}0$ and hence $m$ divides $a(x-x^{\prime })$. Since $\text{gcd}(a,m)=1$, $m$ must divide $(x-x^{\prime })$. Therefore $R_m(x)=R_m(x^{\prime })$ and hence $x=x^{\prime }$.

Definition 4.9: If $\text{gcd}(a,m)=1$, the unique solution $x\in Z_m$ to the congruence equation $ax{\equiv }_{m}1$ is called the multiplicative inverse of $a$ modulo $m$. One also uses the notation $x{\equiv }_m{a}^{-1}$ or $x=1/a$.

Calculating the Multiplicative Inverse using the Extended Euclidean Algorithm

The extended Euclidean algorithm is a powerful tool for calculating multiplicative inverses. Given integers $a$ and $m$, it finds integers $x$ and $y$ such that $ax+my=\text{gcd}(a,m)$.

1. Apply the Extended Euclidean Algorithm: Apply the extended Euclidean algorithm to $a$ and $m$. If the gcd is 1, the algorithm produces integers $x$ and $y$ such that $ax+my=1$.
2. The Inverse: The integer $x$ is the multiplicative inverse of $a$ modulo $m$. If $x$ is negative, you can add $m$ to it until you get a positive representative.

Example: Find the inverse of 5 modulo 11.

1. Extended Euclidean Algorithm:
   • $11=2\cdot 5+1$ Rearranging: $1=11-2\cdot 5$
2. The Inverse: From the equation $1=11-2\cdot 5$, we see that $-2\cdot 5\equiv 1(\mathrm{mod}11)$. Thus, $-2$ is the inverse. To get a positive representative, add 11: $-2+11=9$. So, $5^{-1}\equiv 9(\mathrm{mod}11)$. Check: $5\cdot 9=45=4\cdot 11+1$, so $5\cdot 9\equiv 1(\mathrm{mod}11)$.

The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) provides a method for solving systems of congruences, where we seek a single integer that satisfies multiple congruences with different moduli.

The Essence of the CRT:

The CRT states that if we have a system of congruences:

where $m_1,m_2,...,m_r$ are pairwise relatively prime integers (their greatest common divisors are all 1), and $a_1,a_2,...,a_r$ are any integers, then this system has a unique solution $x$ satisfying $0\le x<M$, where $M={\prod }_{i=1}^r{m}_i$.

Theorem 4.19: Let $m_1,m_2,...,m_r$ be pairwise relatively prime integers and let $M={\prod }_{i=1}^r{m}_i$. For every list $a_1,a_2,...,a_r$ with $0\le a_i<m_i$ for $1\le i\le r$, the system of congruence equations

for $x$ has a unique solution $x$ satisfying $0\le x<M$.

Proof: Let $M_i=M/m_i$. Hence $\text{gcd}(M_i,m_i)=1$ because every factor $m_k$ (where $k\ne i$) of $M_i$ is relatively prime to $m_i$ and thus so is $M_i$. Thus there exists an $N_i$ satisfying

$M_i{N}_i{\equiv }_{m_i}1$

Note that for all $k\ne i$ we have $M_i{\equiv }_{m_k}0$ and thus $M_i{N}_i{\equiv }_{m_k}0$ Therefore ${\sum }_{i=1}^r{a}_i{M}_i{N}_i{\equiv }_{m_k}{a}_k$ for all $k$. Hence the integer $x$ defined by $x=R_M\left({\sum }_{i=1}^r{a}_i{M}_i{N}_i\right)$ satisfies all the congruences. In order to prove uniqueness, observe that for two solutions $x^{\prime }$ and $x^{\prime \prime }$, $x^{\prime }-x^{\prime \prime }{\equiv }_{m_i}0$ for all $i$, i.e., $x^{\prime }-x^{\prime \prime }$ is a multiple of all the $m_i$ and hence of $\text{lcm}(m_1,...,m_r)=M$. Thus $x^{\prime }{\equiv }_M{x}^{\prime \prime }$.

Continue here: 14 Algebraic Structures and Operations, Monoids, Inverses, Groups, Group Properties, Landscape of Groups