Brian Smith

2016-03-23 12:16:03 UTC

Hi,

[I am not sure if boring topics like ECDSA are appropriate for this list. I

hope this is interesting enough.]

ECDSA signature verification is quite expensive. A big part of why it is

expensive is the two inversions--one mod q, one mod n--that are typically

used.

A while back I stumbled across an interesting optimization [1] in

libsecp256k1. The optimization completely avoids the second inversion

during verification.

The comments in the code explain how, but here's a rough summary: Normally

we convert the Jacobian coordinates (X, Y, Z) of the point multiplication

result to affine (X, Y) so that the affine X coordinate can be compared to

the signature's R component. The conversion to affine coordinates requires

the inversion of Z. But, instead of doing that, we can simply multiply the

signature's R component by Z**2 and then compare it with the *Jacobian* X

coordinate, avoiding any inversion.

I asked Greg Maxwell, the author of that code, about it and he didn't know

of anybody else using this optimization.

The optimization has two important properties:

1. It make verification notably (but not hugely) faster.

2. It reduces the amount of code required by an enjoyable amount, if one is

writing prime- specific specialized inversion routines.

Two questions:

1. Does anybody know of prior published software or papers documenting this?

2. Does anybody know why it would be a bad idea to use this technique? I.e.

am I overlooking some reason why it doesn't actually work?

[1]

https://github.com/bitcoin/secp256k1/blob/269d4227038b188128353235a272a8f030c307b1/src/ecdsa_impl.h#L225-L253

(shortened: https://git.io/vad3K)

Thanks,

Brian

[I am not sure if boring topics like ECDSA are appropriate for this list. I

hope this is interesting enough.]

ECDSA signature verification is quite expensive. A big part of why it is

expensive is the two inversions--one mod q, one mod n--that are typically

used.

A while back I stumbled across an interesting optimization [1] in

libsecp256k1. The optimization completely avoids the second inversion

during verification.

The comments in the code explain how, but here's a rough summary: Normally

we convert the Jacobian coordinates (X, Y, Z) of the point multiplication

result to affine (X, Y) so that the affine X coordinate can be compared to

the signature's R component. The conversion to affine coordinates requires

the inversion of Z. But, instead of doing that, we can simply multiply the

signature's R component by Z**2 and then compare it with the *Jacobian* X

coordinate, avoiding any inversion.

I asked Greg Maxwell, the author of that code, about it and he didn't know

of anybody else using this optimization.

The optimization has two important properties:

1. It make verification notably (but not hugely) faster.

2. It reduces the amount of code required by an enjoyable amount, if one is

writing prime- specific specialized inversion routines.

Two questions:

1. Does anybody know of prior published software or papers documenting this?

2. Does anybody know why it would be a bad idea to use this technique? I.e.

am I overlooking some reason why it doesn't actually work?

[1]

https://github.com/bitcoin/secp256k1/blob/269d4227038b188128353235a272a8f030c307b1/src/ecdsa_impl.h#L225-L253

(shortened: https://git.io/vad3K)

Thanks,

Brian

--

https://briansmith.org/

https://briansmith.org/