Recently stumbled upon a discussion in the forum

What is Shamir’s Trick used for?

Are there any such examples?

  • $\begingroup$ You should quote what you are talking about to make your question as self-contained as possible. $\endgroup$ – Maeher Feb 27 '19 at 14:34
  • 1
    $\begingroup$ Excuse me ! I edited my post. $\endgroup$ – Derick Swodnick Feb 27 '19 at 15:04

No, Shamir's trick doesn't break ECDSA. Verifying an ECDSA signature involves evaluating a sum of scalar multiplications $[h s^{-1}]G + [r s^{-1}]P$. You can compute the scalar multiplications $[h s^{-1}]G$ and $[r s^{-1}]P$ separately and then add the results, but Shamir's trick does it more efficiently as a combined computation.

This trick for evaluating a sum of products $[\alpha]P + [\beta]Q$ is to go through the binary expansions of $\alpha = \sum_i \alpha_i 2^i$ and $\beta = \sum_i \beta_i 2^i$ from msb to lsb, and add to the sum either nothing if the bits are both zero, $P$ if only $\alpha_i = 1$, $Q$ if only $\beta_i = 1$, or $P + Q$ if both bits are 1; then double the sum and move on to the next bit.

Beware: If the selection of which point to add or the arithmetic is not done in constant time, this procedure may leak the scalars $\alpha$ and $\beta$ through timing side channels. When verifying signatures this is usually not a problem (unless for some reason the signature has to be secret), but other applications may involve a sum of two scalar multiplications whose scalars are secret.

  • $\begingroup$ +1 for the remark that information leakage by side channels matters in signature verification when the signature must be kept secret (e.g. when it signs some low-entropy secret). $\endgroup$ – fgrieu Feb 28 '19 at 4:15

Shamir's trick: Given $N, x, z, e, F$ s.t. $x^e = z^F \mod N$ and $e, F$ are relatively primes, you can efficiently find $z^{1/e}\mod N$. The trick is to compute integers $a,b$ s.t. $a.e + b.F = 1$.

RSA says the following: given $N, y, e$, it's difficult to compute $y^{1/e}\mod N$.

Using shamir's trick you can prove the following: given $N, y, F, e$ s.t. $F,e$ are relatively primes, then it's difficult to compute $y^{F/e}\mod N$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.