Efficient function/algorithm/method to do modular exponentiation

Question

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?

Answer 1

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

The 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. The below algorithm has given a name as square and always multiply algorithm.

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 //will be discarded.

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

As mentioned above code, the 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 mpn_powm.

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.

Gmpy now has powmod_sec(), see the update and use at own your risk.

Answer 2

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.