#Timing Attack invented by Paul Kocher exploits the variations in the #Rivest-Shamir-Adleman (RSA) operations. It explores the possible operand size based on the time taken for each exponentiation done in decryption algorithm.
Several ways of improvements could be done to the algorithm in order to avoid or decrease the efficiency from timing:
- Add constant exponentiation time so that every exponentiation take the same amount of time, however this degrades the performance.
- Add random delays.
- Use blind values in calculations (RSA Data Security) where the performance hit range between 2% to 10%.
An example of blind values calculations from RSA Data Security implementation:
- Select a random \(r\) from \(Z_n^*\) which is kept secret.
- Compute \(C' = Cr^e \mod n\).
- Compute \(M' = (C')^d \mod n\).
- Compute \(M = M' r^{-1} \mod n = (Cr^e)^d r^{-1} \mod n = C^d r^{ed} r^{-1} \mod n = C^d \mod n\).
Note: \(r^{ed} = r \mod n\) because \(r^{ed} = r^{1 + k \phi(n)}\) from the equation obtained above \(de = 1 + k \phi(n)\). It is the same reason why \(C^d = M^{e \cdot d} \mod n = M \mod n\).
From the implementation above, the attacker could only see the time taken to compute \(M' = (C')^d \mod n\) where they can’t obtain sufficient information to crack the possible length of the operands \(p\), \(q\) and maybe \(r\).