Progress pill
Mathematical Foundations of Cryptography 1

The modulo operation

Modern Cryptography Fundamentals

The modulo operation

  • Modulo
  • The shift cipher

Modulo

The most basic expression with the modulo operation is of the following form: .
The variable is called the dividend and the variable the divisor. To perform a modulo operation with a positive dividend and a positive divisor, you just determine the remainder of the division.
For instance, consider the expression . The number 4 goes into the number 25 a total of 6 times. The remainder of that division is 1. Hence, equals 1. In a similar manner, we can evaluate the expressions below:
  • (as 30 goes into 29 a total of 0 times and the remainder is 29)
  • (as 2 goes into 42 a total of 21 times and the remainder is 0)
  • (as 5 goes into 12 a total of 2 times and the remainder is 2)
  • (as 8 goes into 20 a total of 2 times and the remainder is 4)
When the dividend or divisor is negative, modulo operations can be handled differently by programming languages.
You will definitely come across cases with a negative dividend in cryptography. In these cases, the typical approach is as follows:
First determine the closest value lower than or equal to the dividend into which the divisor divides with a remainder of zero. Call that value .
  • If the dividend is , then the result of the modulo operation is the value of .
For instance, suppose that the dividend is and the divisor 3. The closest value lower than or equal to into which 3 divides evenly is . The value of in this case is . This equals 1 and, hence, equals 1. In a similar manner, we can evaluate the expressions below:
Regarding notation, you will typically see the following types of expressions: . Due to the brackets, the modulo operation in this case only applies to the right-hand side of the expression. If equals 25 and equals 4, for example, then evaluates to 1.
Without brackets, the modulo operation acts on both sides of an expression. Suppose, for instance, the following expression: . If equals 25 and equals 4, then all we know is that evaluates to 1. This is consistent with any value for from the set .
The branch of mathematics that involves modulo operations on numbers and expressions is referred to modular arithmetic. You can think of this branch as arithmetic for cases in which the number line is not infinitely long. Though we typically come across modulo operations for (positive) integers within cryptography, you can also perform modulo operations using any real numbers.

The shift cipher

The modulo operation is frequently encountered within cryptography. To illustrate, let's consider one of the most famous historical encryption schemes: the shift cipher.
Let's first define it. Suppose a dictionary D that equates all the letters of the English alphabet, in order, with the set of numbers . Assume a message space M. The shift cipher is, then, an encryption scheme defined as follows:
  • Select uniformly a key out of the key space K, where K = [1]
  • Encrypt a message , as follows:
    • Separate into its individual letters
    • Convert each to a number according to D
    • For each ,
    • Convert each to a letter according to D
    • Then combine to yield the ciphertext
  • Decrypt a ciphertext as follows:
    • Convert each to a number according to D
    • For each ,
    • Convert each to a letter according to D
    • Then combine to yield the original message
The modulo operator in the shift cipher ensures that letters wrap around, so that all ciphertext letters are defined. To illustrate, consider the application of the shift cipher on the word “DOG”.
Suppose that you uniformly selected a key to have the value of . The letter “O” equates to . Without the modulo operation, the addition of this plaintext number with the key would amount to a ciphertext number of . However, that ciphertext number cannot be turned into a ciphertext letter, as the English alphabet only has letters. The modulo operation ensures that the ciphertext number is actually (the result of ), which equates to the ciphertext letter “F”.
The entire encryption of the word “DOG” with a key value of 17 is as follows:
Message = DOG = D,O,G = 3,14,6 c = UFX
Everyone can intuitively understand how the shift cipher works and probably use it themselves. For advancing your knowledge of cryptography, however, it is important to start becoming more comfortable with formalization, as the schemes will become much more difficult. Hence, why the steps for the shift cipher were formalized.
Notes:
[1] We can define this statement exactly, using the terminology from the previous section. Let a uniform variable have as its set of possible outcomes. So:
...and so on. Sample the uniform variable once to yield a particular key.
Quiz
Quiz1/5
What is the value of 42 mod 2?