How Modular Arithmetic is the Building Block of Cryptography

Modular Arithmetic and Why It is the Building Block of Cryptography

Photo by Ocean Ng on Unsplash

Modular arithmetic is a branch of mathematics that deals with integers and their remainders when divided by a fixed integer. It involves operations such as addition, subtraction, multiplication, and division, but instead of working with the actual numbers, we work with their remainders modulo a fixed number, called the modulus.

For example, if we consider 7 modulo 3, we can write it as $7\equiv1\pmod{3}$ because 7 leaves a remainder of 1 when divided by 3. Similarly, $-5 \equiv 1\pmod{3}$ because -5 leaves the same remainder of 1 when divided by 3.

Modular arithmetic has many interesting properties that make it useful in various applications, including cryptography. In this article, we will explore some of these properties and their significance in cryptography.

Addition and Subtraction

In modular arithmetic, addition and subtraction work similarly to regular arithmetic but with one key difference. If the result of the operation exceeds the modulus, we take the remainder modulo the modulus as the final result.

For example, let's consider $6 + 4\pmod{7}$ . The sum is 10, which is greater than 7, so we need to take the remainder modulo 7, which is 3. Therefore, $6 + 4\equiv 3\pmod{7}$ .

Similarly, if we consider $2 - 5\pmod{7}$ , we get $2 - 5 = -3$ , which is less than 0. To obtain a positive remainder, we add the modulus to -3 until we get a positive number. In this case, we add 7 to -3, giving us 4. Therefore, $2 - 5\equiv 4\pmod{7}$ .

Multiplication

Multiplication in modular arithmetic is also similar to regular multiplication, but with the remainder of the product modulo the modulus as the final result. For example, let's consider $3\times5\pmod{7}$ . The product is 15, and the remainder of 15 when divided by 7 is 1. Therefore, $3\times5\equiv 1\pmod{7}$ .

One interesting property of modular multiplication is that it is distributive over addition. That is, $(a+b)\times c\equiv a\times c+b\times c\pmod{m}$ for any integers $a$ , $b$ , and $c$ and modulus $m$ . This property is important in cryptography, as we will see later.

Division

Division in modular arithmetic is more involved than the other operations, and it is not always possible. In general, we can only divide if the divisor is relatively prime to the modulus. That is, if $gcd(c,m) = 1$ , where $gcd$ denotes the greatest common divisor.

Suppose we want to solve the equation $axequiv bpmod{m}$ for $x$ , where $a$ , $b$ , and $m$ are integers. If $gcd(a,m) = 1$ , then there exists an integer solution $x$ . We can find this solution using the extended Euclidean algorithm, which is beyond the scope of this article.

Modular Exponentiation and Diffie Hellman

Modular exponentiation is an important mathematical operation used in various cryptographic protocols. It involves computing the remainder when a base number is raised to a power and divided by a modulus. This operation is particularly useful for encryption algorithms because it allows for fast computation of large powers modulo a prime number. One of the most common algorithms for modular exponentiation is the square and multiply algorithm, which utilizes the binary representation of the exponent to perform efficient exponentiation. This operation is widely used in public key cryptography, such as RSA, Diffie-Hellman key exchange, and ElGamal encryption.

The Diffie-Hellman key exchange protocol is a method for two parties to agree on a shared secret over an insecure communication channel. The protocol relies on the properties of modular exponentiation. Let's say Alice and Bob want to agree on a shared secret key $K$ . They first agree on a prime number $p$ and a generator $g$ modulo $p$ , which means that $g$ is relatively prime to $p$ and can generate all possible values modulo $p$ .

Then, each party chooses a secret number - Alice chooses $a$ and Bob chooses $b$ . They each compute their public value as follows:

$A = g^a \bmod p$

$B = g^b \bmod p$

Alice and Bob then exchange their public values with each other over the insecure communication channel. They can now compute the shared secret key $K$ using the other party's public value and their own secret value:

$K = B^a \bmod p = g^{ab} \bmod p$

$K = A^b \bmod p = g^{ab} \bmod p$

Since both parties have computed the same value of $K$ , they now share a secret key which can be used for encryption and decryption. This protocol is secure because an eavesdropper cannot compute $a$ or $b$ from $A$ or $B$ alone without knowing the other party's secret value.

Conclusion

Modular arithmetic is a fundamental concept in cryptography and plays a crucial role in many cryptographic algorithms. It enables the secure computation of large numbers by reducing them to a smaller set of residue classes modulo a prime number, making it harder for attackers to decrypt sensitive information. Modular exponentiation, in particular, is widely used in public key cryptography algorithms such as Diffie-Hellman key exchange, RSA, and ElGamal encryption. These algorithms provide secure communication over unsecured networks by utilizing the properties of modular arithmetic to protect sensitive data from unauthorized access. Therefore, understanding and implementing modular arithmetic is critical to building strong cryptographic systems that can provide secure communication and data protection.