Look at the clock face. Try to do some arithmetic calculations.
For example9 + 7 = ? 5 - 7 = ? 9 * 3 = ?
Check your calculations using next form.
Calculations on the twelve-hour dial are equivalent to arithmetic calculations modulo 12.
The basis of asymmetric cryptography is Modular Arithmetic with large natural numbers.
Large natural numbers are often called BigInt. This is not entirely correct, but in practice it does not lead to errors. Treat it like IT-jargon.
To calculate the modulus, perform the calculations as usual, and then divide the result with the remainder by the modulus. The remainder is the desired result.
If you are studying asymmetric cryptographic schemes, you can check the calculations using the following forms.
A + B = C (mod M)
A - B = C (mod M)
If the minuend is less than the subtrahend, see the explanation for negative numbers.
If the absolute value of a number is less than the modulus, add the modulus. Otherwise, calculate the remainder of the division by the modulus of the absolute value and add the modulus.
If the minuend and subtrahend are less than the modulus, then division is not required.
Try replacing subtraction with addition
a-b = a+(-b) = a+(-b+m) = a+(m-b)
a-b = 0 ⇔ a = b
The opposite of numbers in modular arithmetic corresponds to the usual addition of numbers that are opposite in sign and equal in modulus. In other words, the addition of opposite numbers gives zero in any arithmetic system.
Choose any modulus (M). Choose any number (N). Find the opposite number (-N) by modulus (M). Sum the chosen number and the opposite number.
Repeat the previous task several times. The following formula should become completely obvious to you.
Mod M
N+(-N) = M = 0
Mod 12 (like a clock face)
9+(-9) = 9+(3) = 12 = 0
A × B = C (mod M)
In general, division by modulo does not exist.
10 × 3 = 30 = 6 (mod 12) 6 ÷ 3 = 2 -- Wrong! 6 ÷ 10 = ! -- Does not exist for natural numbers
Solving a division problem comes down to replacing the divisor with the reciprocal of the multiplication.
A ÷ B = A × ( 1 ÷ B ) = A × B-1 B × B-1 = B × ( 1 ÷ B ) = B ÷ B = 1 B-1 = 1 ÷ B
In modular arithmetic there is an analogue of mutually reciprocal numbers.
In general, the modular inverse of a number can be found using the Extended Euclidean Algorithm.
A × X + B × Y = gcd(A,B) A × X + B × Y = 1 -- if A and B are coprime A × X = 1 (mod B) -- A and X are mutually inverse modulo B B × Y = 1 (mod A) -- B and Y are mutually inverse modulo A
The practical calculation of the reciprocal number in cryptography is carried out using Euler's theorem.
B-1 = BM-2 (mod M) -- this works when M is a prime number
AB = C (mod M)
The RSA scheme uses exponentiation for encryption and decryption
AB = C (mod M) -- Encryption.
B√C (mod M) -- A potential deciphering formula. However, calculating the root of a number in modular arithmetic is impossible.
C1/B = A (mod M) -- Working formula for deciphering.
Quadratic residue -- calculating the square root by the prime number modulo.
x2=q (mod M) -- x is the square root of q modulo M. M -- is Prime