2
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

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.

$\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.