5 ms·

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

• Retric 9y ago
  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.
  • noobermin 9y ago
    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.
  • 19eightyfour 9y ago
    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?
    • dfox 9y ago
      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.
      • 19eightyfour 9y ago
        Thanks.