search

briansmith / ring

Safe, fast, small crypto using Rust
Other
3.71k stars 699 forks source link

Replace Curve25519 `fe_invert()` C function with a Rust equivalent #500

Open briansmith opened 7 years ago

briansmith commented 7 years ago

See p256_elem_inv() and p384_elem_inv() for the model to copy. Basically, leave the field multiplication and squaring operations in C, but do higher-level part of the Fermat's Littler Theorem implementation in Rust.

ranweiler commented 7 years ago

Picking this up!

briansmith commented 7 years ago

Note to self for the review:

  b1 = z
  b10 = sqr(b1)
  b1001 = sqr_mul(b10, 1 + 1, b1)
  b1011 = mul(b1001, b10)
  acc = sqr_mul(b1011, 1, b1001)
  t1 = sqr_mul(acc, 5, acc)
  t2 = sqr_mul(t1, 10, t1)
  t2 = sqr_mul(t2, 20, t2)
  t1 = sqr_mul(t2, 10, t1)
  t2 = sqr_mul(t1, 50, t1)
  t2 = sqr_mul(t2, 100, t2)
  t1 = sqr_mul(t2, 50, t1)
  out = sqr_mul(t1, 5, b1011)