# Can Shamir’s Trick crack the cryptographic strength of ECDSA?

Recently stumbled upon a discussion in the forum

What is Shamir’s Trick used for?

Are there any such examples?

• You should quote what you are talking about to make your question as self-contained as possible. – Maeher Feb 27 at 14:34
• Excuse me ! I edited my post. – Dmitry Bazhenovsky Feb 27 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.

• +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). – fgrieu Feb 28 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$$.