Outline
Modular Arithmetic
Modular Multiplication
Modular Multiplicative Inverse (Its Modular Division)
Greatest Common Divisor Algorithm
Extended Euclidean Algorithm
Optimized Binary Extended Euclidean Algorithm
Constant Time Binary Extended Euclidean Algorithm
Modular Exponentiation
Optimized Binary Modular Exponentiation
Square-and-Multiply Algorithm
Primality Test Using Miller-Rabin and Trial Division
Modular Inversion for Prime Moduli
Last blog post I explained how modular addition and subtraction can be done without risk of Integer Overflow/Underflow. In this blog post I will continue that discussion with Modular Multiplication and Modular Inversion, which is the modular version of division.
Modular Multiplication
Of course we have to watch out for Integer Overflows/Underflows. From the last blog post we learned we should choose the form of a number in modular arithmetic that has the lowest absolute value, whether that is the positive or negative version of the number. So for example 30 mod 31 = -1 mod 31. Thus we should choose to represent 30 mod 31 as -1 mod 31 as we do any modular arithmetic with that number. To convert between the positive and negative versions of a modulo number recall the formula from the last blog post:
This approach does not help us when the absolute value of a in a mod n is equal or close to n / 2. In that case the positive and negative versions of a modulo number are roughly the same.
For example 15 mod 31 = -16 mod 31. Technically the lowest absolute value form of the modulo number is 15 mod 31. Still, this does not help when you have to calculate 15 * 15 mod 31. Try coming up with a new technique as you do the following exercises.
Do the below exercises on paper without doing any arithmetic that yields results that have a larger absolute value than the modulus base number n. This will prepare you for the next coding exercise.
Once you have done the above exercises complete the next coding exercise:
Once you have your solution compare it to mine:
Let us take a deeper look at two important blocks of code:
The above function __builtin_mul_overflow() is a built-in API call available for use when you compile C++ code using the g++ compiler. I strongly recommend using it or the other built-in overflow API functions g++ offers:
Next let's take a look at the block of code that gurantees the correct answer without risk of Integer Overflow/Underflow:
There is a logic to the above formula. When g++ detects multiplication overflow in signed arithmetic for 64-bit integers the program applies the following math formula to derive the correct answer without risk of Overflow/Underflow:
MAX_INT is the largest possible value that can be stored in the bit vector used to store modulo numbers. Since we are using signed 64-bit integer arithmetic MAX_INT is 2^63 -1.
Notice a_1 is the value for a at line 3 in mul_without_overflow_risk.cpp. This ensures the recursion works properly for the operator*.
The above program has been tested with the 38 Modular Multiplication exercises and gives the correct answer without risk of Integer Overflow/Underflow.
Modular Inversion
The logical equivalent of division for modular arithmetic is known as modular inversion. It is crucial in public-key cryptography. The main benefit of public-key cryptography is that the sender of a document can encrypt data with a public key that only the owner of the private key can decrypt. To conduct modular inversion we must first review the Euclidean Algorithm.
Euclid's Algorithm
Thousands of years ago a Greek mathematician named Euclid documented a technique to find the largest common multiple between two numbers in his magnum opus: Euclid's Elements. This technique is called finding the Greatest Common Divisor. The following is the algorithm for Euclid's Algorithm:
There are several faster variants of Euclid's Algorithm. Luckily for you you don't even have to worry about programming your own since C++ already has a built-in API function for it. You can use this standard API call as long as you use primitive integer data types. The C++ standard API will calculate the greatest common divisor between |a| and |m| for you.
Although a program to find the greatest common divisor between two positive integers is nice in the real world a version other algorithms can be used to find the modular inverse.
Below is a snippet demonstrating how to use the C++ standard API call for gcd:
Definition of Modular Inverse
The logical equivalent of division in modular arithmetic can be done with the modular multiplicative inverse:
If we want to find the modular inverse of a number a relative to a modulus number n we must first check if the greatest common divisor between a and n is 1. This means a and n are relatively prime or coprime. If it is not then finding the modular inverse of the number a relative to the number n is impossible.
We can use Euclid's Division Algorithm to calculate the modular inverse. It only works when 0 < a < m and m is a prime number. However, most cryptosystems feature a prime number for m--including RSA, Diffie-Hellman, Elliptic Curve Cryptography, and even NIST-approved post-quantum cryptography. Usually this prime number must be massive to ensure it is difficult for the attacker to guess the secret key. For now we will do arithmetic using signed 64-bit arithmetic. Below is sample code that gets this done assuming both a and m are expressed as signed 64-bit numbers.
The below algorithm calculates the modular inverse for number a relative to prime number modulus base number m. 0 < a < m.
One piece of code missing is a function call that tests for primality. I decided not to discuss since prime number generation and primality tests are out of scope for this article.
I rejected other methods of calculating the modular inverse on purpose since they were more complicated to program and/or less efficient including Extended Euclid's Algorithm and Binary Exponentiation. The solution you see above is easy to understand and is fast.
Modular Exponentiation
In grade school you learned exponents are a short hand way of multiplying a number to itself the number of times of some number called an exponent. In cryptography we multiply massive numbers to itself hundreds of times. But for now we will explore modular exponentiation using signed 64-bit arithmetic since we are beginning to learn about it for the first time.
We can express modular exponentiation as the following:
Having to multiply a to itself n times in a row would be an obvious way to solve for modular exponentiation. Yet that would be very inefficient. We would first have to figure out a way to store the current-most product we found. It would be annoying to have to program big integer arithmetic when we know for a fact the largest possible result would be m - 1, which fits in a signed 64-bit integer. A way to calculate modular exponentiation would be to apply the Square-and-Multiply Method. This is also known as Binary Exponentiation. The following is a snapshot from Math StackExchange that does a great job of explaining how it works:
And here are some test cases to help you debug your program:
Here is my solution:
Let's take a magnified look at the actual function that implements the solution:
The exp() function is an implementation of Bruce Schneier's implementation of the square-and-multiply algorithm. You can find the pseudocode on Wikipedia:
The technique Schneier used is known as Right-to-Left Binary Exponentiation.
Primality Testing
Earlier I showed a code snippet that computes the modular inverse assuming the modulus base number is a prime number. I only checked if the number was greater than two back in the earlier example, which is obviously not good enough. How do cryptographers test for prime numbers on a machine.
One of the most efficient methods of primality testing is to use the Miller-Rabin algorithm. This is a test for what is called probable primes. That means the algorithm's decision on whether or not the number is prime has a chance of error. To minimize the chance of error cryptographers often run Miller-Rabin several times.
An excellent paper that reviews how Miller-Rabin works is the paper A Performant, Misuse-Resistant API for Primality Testing.
The following is the Miller-Rabin algorithm:
As long as either of the two equalities passes Miller-Rabin will declare the number to be prime. Only when both equality tests fail will Miller-Rabin declare the number to composite. Miller-Rabin never declares a true prime to be composite. However, it may declare a true composite to be a prime! The chance that Miller-Rabin declares a true composite to be prime is 2^(-2t) where t is the number of times we run Miller-Rabin where each iteration uses a unique value for a. Ideally the value for a should be chosen by a Cryptographically Secure Pseudo Random Generator. If we use fixed values for a in our tests for Miller-Rabin an attacker can pass composite numbers that Miller-Rabin will pass as prime numbers.
To ensure it is too difficult for attackers to feed composites that pass as prime numbers the researchers recommend running Miller-Rabin at least 64 times for an error rate of 2^(-2*64) = 2^(-128) that Miller-Rabin declares a true composite to be a prime number. The reasoning for choosing an error-rate of 2^(-128) is simple: in public-key cryptography the chance of guessing the private key is often no less than 2^(-128). It does not help to use more rounds of Miller-Rabin such that the chance of it declaring a true composite to be prime is less than the chances of cracking the secret key since the attacker can instead try to crack the key anyway. Let's test if we understand how Miller-Rabin works:
Below is the code template for the aforementioned exercise:
Have you tested your solution and see if it works? Good! Now compare it to mine!
My solution first tests if the moduli number is 2 which is a prime number. It then checks if the number is even (besides 2) which is guaranteed composite since an even number greater than 2 is always divisible by 2. It then checks if the modulus number is divisible by the first 128 odd primes. If this test fails it then applies the Miller-Rabin test with 64 distinct, random values for a:
With the primality test in place we can now refactor the mod inverse function so that it does a proper test for primality:
Below is the full code featuring the above snippet for inverse_moduli_prime(void):
Conclusion
The above concludes our review of the skills in programming modular arithmetic that we need to understand how programs of cryptosystems work. In this article we have reviewed methods to calculate fast modular multiplication, exponentiation, an efficient test for primality and using that for modular inversion (the logical equivalent of division). You will find these concepts used as you study cryptographic programs--whether you are source code auditing, using a cryptographic API, or even writing your own cryptographic code (you better make sure someone qualified reviews that!).
You might have been reading this article with some background in cryptography and have been thinking: "Gee its nice to know these basic algorithms but in the real world we use numbers much larger than what can be stored in signed 64-bit arithmetic". Of course you are right about that! But before I get to that it is important to review how these modular arithemtic algorithms work in the first place. There are several math tricks we had to do just to ensure Integer Overflow/Underflow is not an issue and that the algorithms were fast enough! And these tricks are counter-intuitive! You were taught that signed arithmetic is unsafe. Ironically, it actually helped us avoid Integer Overflow problems. In a future article we will review how to program Big Integer Arithmetic and translate the algorithms mentioned in this section so they can use the massive integers modern cryptography demands.