Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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
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.
