Here, we will learn about Modular Arithmetic, i.e., the basic mathematical foundation used to develop cryptographic primitives, such as the RSA encryption scheme and Diffie–Hellman key exchange.
Objective: In layman's terms, we are interested in learning a mathematical foundation that will help us generate a number between 0 and P and perform various operations, such as addition or multiplication, in this domain.
Subsequently, we will try to find various properties that will help us design cryptographic primitives.
For example, 1) we will see the importance of arithmetic multiplication in RSA, i.e., how the multiplicative inverse concept is used to generate the encryption and decryption keys. Similarly, we will discuss the importance of the primitive element in generating keys in Diffie–Hellman key exchange.
These basic primitives are generally used in other encryption mechanisms as well. Thus understanding the fundamental properties will help us understand other cryptographic primitives we encounter.
An Introduction to Modular Arithmetic:
As we are confining our interest in a range from 0 to P,we can use remainder calculation.
Here, when we divide two integers we will have an equation that looks like the following:
Sometimes, we are only interested in the remainder when dividing A by B.
For these cases, there is an operator called the modulo operator (abbreviated as mod).
Using the same A, B, Q, and R as above, we would have: A mod B=R.
We would say this as A modulo B is equal to R, where B is referred to as the modulus.
Below, we can generate different Remainder values by changing the two sliders, A and B.
Here, Slider A represents the dividend, and B represents the divisor.So, for example, by assigning A to 13 and B to 5, we will get the remainder 3.