I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you divide?
Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python;
def fast_power(base, power): result = 1 while power > 0: # If power is odd if power % 2 == 1: result = (result * base) % MOD # Divide the power by 2 power = power // 2 # Multiply base to itself base = (base * base) % MOD return result
if condition is an attack point for side-channel attacks. One can measure power usage and determine exponent bits. The below image or similar research images can show the idea of the attack.
If you are signing with RSA your private exponent can be revealed. Squaring can be implemented faster than multiplication, in that case, it can also be exploited. Therefore, you need constant timing to prevent this. The python library contains power modulus
pow(a,e,n) which is based on repeated squaring and it is not secure. The below version of the repeated squaring method always calculates the
(result * base) % MOD and discards it when it is not necessary. This may help mitigate the attack, however, this can be still traced if there is an instrument with enough resolution. Also, during compilation, make sure that this mitigation is not removed by compilers. Compilers, like Cray's
CC can discard unused calculations as an optimization by default.
def constant_time_power(base, power): result = 1 while power > 0: # else to prevent leak if power % 2 == 1: result = (result * base) % MOD else: result_temp = (result * base) % MOD # Divide the power by 2 power = power // 2 # Multiply base to itself base = (base * base) % MOD return result
As mentioned above code, taddedhe above can be optimized by compilers with dead code elimination technique since the code contains unused code. Some compilers have pragma directives to disable local optimization. Instead of relying on compiler directives and their bugs, changes, etc., it is possible to use a constant-time conditional copy. The below show this;
def constant_time_power_with_conditional_copy(base, power): result = 1 while power > 0: # constant-time conditional copy sBit = power%2==1 result = ((result * base) % MOD)*sBit+(1-sBit)*result # Divide the power by 2 power = power // 2 # Multiply base to itself base = (base * base) % MOD return result
The famous GMP library has a secure version
mpn_sec_powm of their standard
This function is designed to take the same time and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. This function is intended for cryptographic purposes, where resilience to side-channel attacks is desired.
There are other modular multiplications like Barret or Montgomery. They have also constant-time implementations. For example for Montgomery based
- 2009 Fast and Constant-Time Implementation of Modular Exponentiation by Gopal et al.
Yes. You don't need to wait until the end of the computation to compute the remainder, you can do that in each step of the exponentiation; this way, the largest numbers you'll need to handle are twice the size of n.
There are many algorithms to compute the exponentiation itself, the simplest is square-and-multiply.