mirage / mirage-crypto

Cryptographic primitives for OCaml, in OCaml (also used in MirageOS)
ISC License
77 stars 43 forks source link

[ec] Handle K_gen correctly for bitlen mod 8 <> 0 #230

Closed Firobe closed 6 months ago

Firobe commented 6 months ago

Closes #228 Closes #105

During K generation, we need to retrieve l bits from RNG (where l is 256, 384, 521).

Currently, we take ceil(l / 8) whole bytes and call it a day. This works fine when l is a multiple of 8, but for l = 521 this generates 7 bits of garbage, which make it very likely the generated vector is over 2^521. When this happens, we loop and retry until we're lucky, which is a lot of busy work for nothing (and makes the time to generate k fluctuate wildly, see #228).

This PR truncates the generated vector to keep only the l leftmost bits, as per RFC 6979, which:

Since we have to keep the leftmost bits, this means we have to shift the entire string instead of just truncating the first byte. Comments are welcome if there are better ways to do that than implement here :)

Firobe commented 6 months ago

The CI failures seem unrelated

hannesm commented 6 months ago

Thanks for your work. I had minor suggestions in https://github.com/Firobe/mirage-crypto/pull/1

hannesm commented 6 months ago

FWIW, main branch, ecdsa-sign: P521: 553.436 ops per second (5212 iters in 9.418)

This PR (including my minor changes): P521: 1543.730 ops per second (15010 iters in 9.723)

other curves (256, 384) didn't change in ops per second.

Firobe commented 6 months ago

Thanks for the review! The changes are merged.