Cycling attack against faulty hardware

We shall illustrate this attack in the RSA signature context. Imagine that Alice wants to send a signed message to Bob. For this purpose, she carefully chooses two large primes p and q , and publishes their product n=pq . She also chooses a public verification key v according to $\gcd(v,\phi(n))=1$. The secret signature key s is computed so that $sv \equiv 1 \pmod{\phi(n)}$. Then, to sign a message m , Alice computes $S=m^s \bmod{n}$, and sends the pair (m,S) to Bob. To verify that S effectively is the signature of Alice corresponding to m , Bob checks whether $S^v \equiv m \pmod{n}$, where v is the public verification key of Alice.

We shall see that if the hardware is damaged, then a pirate can obtain some bits of the secret key s . Note that we do not deal with Chinese remaindering based implementations, because, as shown before, in this case one faulty computation modulo p or modulo q gives the secret factors of n .