Recently stumbled upon a discussion in the forum
What is Shamir’s Trick used for?
Are there any such examples?
$\begingroup$
$\endgroup$
2
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
1
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.
answered Feb 27 '19 at 17:36
-
$\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
$\begingroup$
$\endgroup$
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$.
