1
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

enter image description here

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 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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Note that this is not a secure sample code because a smart compiler will notice that power_temp is never used and that its defining RHS doesn't have side-effects as per the language specification and will optimize it away. A better solution would be to remove the if and add a constant time conditional copy in the next line. $\endgroup$ – SEJPM Oct 31 '19 at 18:49
  • $\begingroup$ @SEJPM I'll look into that. $\endgroup$ – kelalaka Oct 31 '19 at 18:56
  • 1
    $\begingroup$ I think the basic python interpreter doesn't do dead-store / dead-code elimination. But I suppose it's not a great idea to make such an implicit assumption about the interpreter / compiler and "just providing a secure example" might be a better plan. Also to counter power-analysis attacks multiplicative blinding may be necessary. $\endgroup$ – SEJPM Oct 31 '19 at 19:19
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.