How to trigger the fixed_window_exponentiator in mod_exp?

[computereasy]

Hello,

I am playing with the rsa decryption routine of botan (version 1.10.13), and it seems that I can only trigger the Montgomery_Exponentiator implementation of the modular exponentiation.

I find the following routines in the source code, and figure out that by I can change the n (it is derived from the key, right?) to trigger the fixed_window_exponentiator. However, after trying to re-generate the secret key for several times, I still cannot trigger the fixed window implementation.

Modular_Exponentiator*
Core_Engine::mod_exp(const BigInt& n, Power_Mod::Usage_Hints hints) const
 {
 if(n.is_odd())
    return new Montgomery_Exponentiator(n, hints);
 return new Fixed_Window_Exponentiator(n, hints);
 }

So here is my question:

1. Is it legit if I hack the code, ruling out the if condition above and force the execution flow to hit the Fixed_Window_Exponentiator implementation? This is only for some academic study, not real usage so no worries about the potential safety issue. I just want to execute the fixed_window routine.

2. If not, how should I trigger this fixed window implementation?

I would really appreciate any advice and suggestion, thank you in advance!

[randombit]

Yes the fixed window exponentiation algorithm should be correct for all moduli, Montgomery representation is just an optimization.

[computereasy]

@randombit Thank you. I got it.

[computereasy]

Hi @randombit , I comment out the branch, compile, and re-run the example code rsa_dec, however, I got the following exception:

➜  examples ./rsa_dec rsapriv.pem messagefile.enc a
Exception caught: Internal error: Assertion m == powermod_e_n(x) failed (RSA private op failed consistency check) in virtual Botan::SecureVector<unsigned char>   Botan::RSA_Private_Operation::decrypt(const byte*, size_t) @src/pubkey/rsa/rsa.cpp:113 

This is how I tweak the source code:

Modular_Exponentiator*
Core_Engine::mod_exp(const BigInt& n, Power_Mod::Usage_Hints hints) const
{
 // if(n.is_odd())
 //    return new Montgomery_Exponentiator(n, hints);
 return new Fixed_Window_Exponentiator(n, hints);
}

[randombit]

Thanks, bug for certain - I will take a look at this soon.

[computereasy]

@randombit Thank you!

[randombit]

@computereasy I believe the bug you encountered is fixed in 1.10 branch with 1a0f41b

[randombit]

Closing as fixed