search

pornin / CTTK

Constant-Time Toolkit
MIT License
294 stars 14 forks source link

Feature requests for crypto: modular numbers, exponentiation, rotation #6

Open waywardgeek opened 6 years ago

waywardgeek commented 6 years ago

We'll emulate these with slower e operations for now. Rotation is not as important as modular numbers or exponentiation, but nice to have for crypto.

waywardgeek commented 6 years ago

And, while I'm asking for crypto features, maybe modular inverse? I'm not sure how to do that in constant time.

pornin commented 6 years ago

There is a constant-time modular inversion (in fact, modular division, which is more generic) in BearSSL: https://www.bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/int/i31_moddiv.c;h=9950591197674419d97f545a224a9503eda4a955;hb=420f50c213231244c8659d2e35cecb396a250ecc

As with the rest of the modular integer code in BearSSL, it's "internal", meaning that its API is unforgiving and relies on strict assumptions on input values. Copying that into CTTK requires some thinking about a proper API.

(When the modulus is a prime p, you can get a modular inversion with a modular exponentiation by p-2; however, this does not work if p is not prime. Code linked above works with any odd modulus.)