What is modular arithmetic?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, History of cryptography, Modular arithmetic and historical ciphers

Modular arithmetic is a fundamental concept in number theory and is extensively utilized in the field of cybersecurity, particularly in classical cryptography. It forms the backbone of many cryptographic algorithms and protocols. To understand modular arithmetic, one must first grasp the notion of congruence relation, which is the cornerstone of this mathematical system.

Modular arithmetic involves the arithmetic of remainders. When an integer a is divided by another integer n (known as the modulus), it yields a quotient q and a remainder r. This relationship can be expressed using the equation:

    \[ a = nq + r \]

where 0 \leq r < n. The remainder r is the result of the modular operation, and this is written as:

    \[ r = a \mod n \]

For instance, if we consider a = 17 and n = 5, dividing 17 by 5 gives a quotient of 3 and a remainder of 2. Therefore, in modular arithmetic terms:

    \[ 17 \mod 5 = 2 \]

The concept of congruence is central to modular arithmetic. Two integers a and b are said to be congruent modulo n if they have the same remainder when divided by n. This is written as:

    \[ a \equiv b \mod n \]

For example, 17 and 2 are congruent modulo 5 because both leave a remainder of 2 when divided by 5:

    \[ 17 \equiv 2 \mod 5 \]

Modular arithmetic has several properties that make it particularly useful in cryptographic applications. These properties include:

1. Addition:
If a \equiv b \mod n and c \equiv d \mod n, then:

    \[ (a + c) \equiv (b + d) \mod n \]

2. Subtraction:
If a \equiv b \mod n and c \equiv d \mod n, then:

    \[ (a - c) \equiv (b - d) \mod n \]

3. Multiplication:
If a \equiv b \mod n and c \equiv d \mod n, then:

    \[ (a \cdot c) \equiv (b \cdot d) \mod n \]

4. Exponentiation:
If a \equiv b \mod n, then for any integer k:

    \[ a^k \equiv b^k \mod n \]

These properties allow complex arithmetic operations to be performed in a simplified manner, which is particularly advantageous in cryptographic computations.

Historical Ciphers and Modular Arithmetic

Modular arithmetic has been used in various historical ciphers, most notably in the Caesar cipher and the Vigenère cipher.

Caesar Cipher

The Caesar cipher is one of the simplest and most well-known encryption techniques, attributed to Julius Caesar, who used it to communicate securely with his generals. The Caesar cipher is a substitution cipher where each letter in the plaintext is shifted a certain number of places down or up the alphabet. The shift is determined by a fixed integer k.

For example, with a shift of 3 (i.e., k = 3), the letter 'A' would be encrypted as 'D', 'B' as 'E', and so on. Mathematically, this can be expressed using modular arithmetic. Let P be the plaintext letter and C be the corresponding ciphertext letter. The encryption process can be defined as:

    \[ C = (P + k) \mod 26 \]

where 26 is the number of letters in the English alphabet. Decryption reverses the process:

    \[ P = (C - k) \mod 26 \]

For instance, if the plaintext letter is 'B' (which is the 1st letter in the alphabet, considering 0-based indexing), and the shift k is 3, the ciphertext letter would be:

    \[ C = (1 + 3) \mod 26 = 4 \]

Thus, 'B' is encrypted to 'E'.

Vigenère Cipher

The Vigenère cipher is a more complex polyalphabetic substitution cipher that uses a keyword to determine the shift for each letter in the plaintext. Each letter of the keyword determines the shift for the corresponding letter in the plaintext. If the keyword is shorter than the plaintext, it is repeated to match the length of the plaintext.

Let P be the plaintext letter, K be the keyword letter, and C be the ciphertext letter. The encryption process is:

    \[ C = (P + K) \mod 26 \]

Decryption is performed by:

    \[ P = (C - K) \mod 26 \]

For example, if the plaintext is "HELLO" and the keyword is "KEY", the keyword is repeated to "KEYKE". The encryption process for each letter is as follows:

– 'H' (7) + 'K' (10) = 17 (R)
– 'E' (4) + 'E' (4) = 8 (I)
– 'L' (11) + 'Y' (24) = 35 mod 26 = 9 (J)
– 'L' (11) + 'K' (10) = 21 (V)
– 'O' (14) + 'E' (4) = 18 (S)

Thus, "HELLO" is encrypted to "RIJVS".

Applications in Modern Cryptography

Modular arithmetic is not just a relic of historical ciphers but is also a cornerstone of modern cryptographic algorithms. Some of the most widely used cryptographic protocols, such as RSA (Rivest-Shamir-Adleman) and Diffie-Hellman key exchange, rely heavily on modular arithmetic.

RSA Algorithm

The RSA algorithm is an asymmetric cryptographic technique that uses two keys: a public key for encryption and a private key for decryption. The security of RSA is based on the difficulty of factoring large composite numbers. The algorithm involves the following steps:

1. Key Generation:
– Select two large prime numbers, p and q.
– Compute n = p \cdot q.
– Compute the totient \phi(n) = (p-1) \cdot (q-1).
– Choose an integer e such that 1 < e < \phi(n) and \gcd(e, \phi(n)) = 1 (i.e., e is coprime with \phi(n)).
– Compute d such that d \equiv e^{-1} \mod \phi(n) (i.e., d is the modular multiplicative inverse of e).

The public key is (e, n), and the private key is (d, n).

2. Encryption:
– Convert the plaintext message M into an integer m such that 0 \leq m < n.
– Compute the ciphertext c using the public key:

    \[ c \equiv m^e \mod n \]

3. Decryption:
– Compute the plaintext message m using the private key:

    \[ m \equiv c^d \mod n \]

For example, let p = 61 and q = 53. Then n = 61 \cdot 53 = 3233 and \phi(n) = (61-1) \cdot (53-1) = 3120. Let e = 17, which is coprime with 3120. The modular multiplicative inverse d of 17 modulo 3120 is 2753. Thus, the public key is (17, 3233) and the private key is (2753, 3233).

To encrypt a message m = 65:

    \[ c \equiv 65^{17} \mod 3233 = 2790 \]

To decrypt the ciphertext c = 2790:

    \[ m \equiv 2790^{2753} \mod 3233 = 65 \]

Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange protocol allows two parties to securely share a common secret key over an insecure channel. The protocol relies on the difficulty of the discrete logarithm problem in modular arithmetic. The steps are as follows:

1. Public Parameters:
– Choose a large prime number p and a primitive root g modulo p.

2. Key Exchange:
– Alice chooses a private key a and computes her public key A \equiv g^a \mod p.
– Bob chooses a private key b and computes his public key B \equiv g^b \mod p.
– Alice and Bob exchange their public keys A and B.

3. Shared Secret:
– Alice computes the shared secret s \equiv B^a \mod p.
– Bob computes the shared secret s \equiv A^b \mod p.

Since B \equiv g^b \mod p and A \equiv g^a \mod p:

    \[ s \equiv (g^b)^a \mod p = g^{ba} \mod p \]

    \[ s \equiv (g^a)^b \mod p = g^{ab} \mod p \]

Thus, both Alice and Bob arrive at the same shared secret s.

For example, let p = 23 and g = 5. Alice chooses a = 6 and computes A \equiv 5^6 \mod 23 = 8. Bob chooses b = 15 and computes B \equiv 5^{15} \mod 23 = 19. They exchange public keys A = 8 and B = 19. Alice computes the shared secret s \equiv 19^6 \mod 23 = 2, and Bob computes the shared secret s \equiv 8^{15} \mod 23 = 2.

Importance in Cryptographic Security

Modular arithmetic's significance in cryptographic security cannot be overstated. Its properties enable the construction of robust cryptographic algorithms that are resistant to various types of attacks. The difficulty of solving problems like integer factorization and discrete logarithms underpins the security of many cryptographic protocols. As computational power increases, the complexity of these problems ensures that cryptographic systems remain secure.

In modern cryptography, modular arithmetic is also used in elliptic curve cryptography (ECC), which provides similar security levels to RSA and Diffie-Hellman but with smaller key sizes, leading to faster computations and reduced storage requirements. ECC relies on the algebraic structure of elliptic curves over finite fields, which involves modular arithmetic.

The ongoing advancements in quantum computing pose a potential threat to classical cryptographic algorithms. Quantum algorithms, such as Shor's algorithm, can efficiently solve the integer factorization and discrete logarithm problems, rendering many current cryptographic systems vulnerable. As a result, the field of post-quantum cryptography is exploring new cryptographic primitives that remain secure against quantum attacks, many of which still rely on modular arithmetic in some form.

Modular arithmetic is a vital and enduring component of cryptographic theory and practice. Its mathematical properties and applications in historical and modern ciphers underscore its importance in securing communication and data. As the field of cryptography continues to evolve, modular arithmetic will remain a foundational element, adapting to new challenges and innovations.

Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:

View more questions and answers in EITC/IS/CCF Classical Cryptography Fundamentals

More questions and answers:

Tagged under: , , , , , , ,