# Break large exponent calculation into smaller calculations?

I am implementing SRP on an embedded platform. It has crypto acceleration and I am using its built in modular exponentiation function, however it doesn't seem to be able to handle an exponent over 32 bytes long. I have an exponent i need to use which is 64 bytes long.

Is there a way to break this exponentiation into smaller exponentiations that the modular exponentiation function can handle?

• I think that SRP is still secure with 256 bit exponents, it just degrades from information theoretical hiding to computational hiding of the secret. – CodesInChaos Aug 7 '18 at 14:32

One method uses the factorisation the exponent: If $a=bc$ then $x^a \equiv x^{bc}\equiv (x^b)^c \mod m,$ i.e. first compute $y=x^b\mod m$ and then $y^c \mod m$.

This method will work, if the largest factor of the exponent has at most 32 bytes.

Otherwise you can always use the square-and-multiply exponentitation method (see https://en.wikipedia.org/wiki/Modular_exponentiation or https://en.wikipedia.org/wiki/Modular_exponentiation or https://en.wikipedia.org/wiki/Exponentiation_by_squaring) looping over the single bits of the exponent.

Is there a way to break this exponentiation into smaller exponentiations that the modular exponentiation function can handle?

Yes there is. Normally one would do this with pre-computatations to process more than one bit of the exponent per iteration, but it should nicely adapt to your case.

In particular I suggest you use algorithm 14.82 from the Handbook of Applied Cryptography (PDF). I will re-state this algorithm here adapted to your needs. Let $e$ be your exponent and let $e_0$ be the least significant 31 bytes and $e_1$ be the next more significant 31 bytes and $e_2$ be the most significant 2 bytes. Further let $g$ be your base-point / base element. Assume the group is written multiplicatively with neutral element $1$. (This assumes you can't actually efficiently compute $g^{2^{256}}$ because the exponent takes $33$ bytes to represent)

Now compute

1. $A\gets 1$
2. $A\gets A^{2^{248}}$
3. $A\gets A\cdot g^{e_2}$
4. $A\gets A^{2^{248}}$
5. $A\gets A\cdot g^{e_1}$
6. $A\gets A^{2^{248}}$
7. $A\gets A\cdot g^{e_0}$
8. return $A$

where the six exponentiations are performed using your acceleration engine.

You may also want to explore to use $255$ bit wide values and see if implementing the 2 bit exponentiation with $e_2$ that ensues might be cheaper to do yourself while accounting for the extra overhead that the bit-level encoding may hold.

Side-Channel Note: This algorithm should be constant time iff your standard element multiplication and the exponentiation are constant-time.