Hacker News Reader

How can you compute modular exponentiation in a Time Safe way, regarding some pseudocode or a link?

They give a partial answer aka right-to-left vs. left-to-right, but at the high level.

Make sure you do fixed computation regardless of data involved. This involves slowing things down and making sure the CPU/compiler does not optimize anything so things become unbalanced.

I am new about these things, but wouldn't just moving to fixed computation really fix this and a large number of forsee-able side-channel attacks? It sounds like the libgcrypt devs chose specifically not to do this because they thought it wasn't necessary.

Okay, I saw that, but thanks for saying it. What does right to left mean specifically? How would you compute it without a sliding window / or make it fixed time?

Straightforward implementation involves taking exponent bits from the MSB on and multiplicating by the base for 1 bits and then squaring the intermediate result.

Straightforward way to make this constant time is to do the multiplication always and discard the result for 0 bits.

Motivation of the sliding window algoritms is that they are faster and also believed to be "more constant time" than the straightforward square and multiply.

Thanks.

Reply on news.ycombinator.com