[curves] Computing an inverse scalar for Curve25519

[isis agora lovecruft]

Alexey Ermishkin transcribed 1.1K bytes:
> Hello everyone.
> 
> I'm trying to implement sphinx password store protocol which needs an
> inverse element webee.technion.ac.il/~hugo/sphinx.pdf using 25519
> 
> It's all ok with p-256 curve (PoC in Golang is here:
> https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042), works
> like a charm, but nothing helps for Curve25519.
> 
> I tried to
> 1) Remove clamping before second scalarMult
> 2) Inverse Endianness, convert scalar to BigInt, use the standard
> ModInverse, convert back to bytes and reverse byte order once again but that
> did not help
> 
> I'm obviously missing something but cannot figure out what. I'd love to get
> an advice on how to achieve that using ref10 notation or similar existing
> code
> 
> Thanks in advance,
> Alex.

Hello Alex,

Someone answered precisely this same question on SE [0] about a week ago, by
pointing out that field element inversion isn't the same as scalar inversion.
Curiously, the questioner, John Dow, is also implementing the same "password
store mechanism, called Sphinx".  Maybe you two should collaborate?  :)

The questioner helpfully posted a screenshot of the protocol setup
requirements of the paper, which state that the cyclic group G must be of
prime order.  Unfortunately, the group of points on curve25519 is _not_ prime
order, but, instead, the cofactor (8, in this case) times the order of the
basepoint (2^252 - 27742317777372353535851937790883648493).  All Edwards
curves — and curve25519 is one of this type — have cofactors.  Effectively,
this means you can't implement your protocol using curve25519 (at least, not
without some modification).  To say that cofactors are annoying would be
putting it mildly!

If you'd like to learn more about the historical problems arising from
cofactors, along with a very elegant solution to elliminate the cofactors of
Ed448 and curve25519, I would highly suggest reading Mike Hamburg's "Decaf:
Elliminating cofactors through point compression" paper [1] as well as the
archives of this list (if you haven't yet).

P.S.: This line of code [2] in your example should be using a random scalar
(in ℤ/lℤ, l=2^252 - 27742317777372353535851937790883648493) instead of taking
a random field element (in ℤ/(2^255 - 19)) compressing it to bytes and
treating it as a scalar, without modular reduction.  (Lines 37 and 44 are also
doing this.)  Similarly, here [3] you're inverting a field element modulo the
order of the basepoint (`N` in your library, `l` here).  Instead, `r` and
`rInv` should both be scalars.

Side note: That Golang elliptic curve library you're using is horrible!  I
can't believe that's in the Go standard library!  (Actually, I can; it's Go.)
It's exacerbating confusion between field elements and scalars with its
horrible typing, i.e. in "crypto/elliptic/p256":

    func (p256Curve) ScalarMult(bigX, bigY *big.Int, scalar []byte) (x, y *big.Int) {

No wonder you're trying to compress field elements to bytes and pass them in
as scalars, its type system is practically telling you to do that!  (And if
that weren't bad enough, it's expressing field elements as bigints… this is
really slow, not to mention weird since most libraries split up these
potentially large numbers into "limbs".)  I would not recommend that library.

[0]: https://crypto.stackexchange.com/a/47482
[1]: https://mikehamburg.com/papers/decaf/decaf.pdf
[2]: https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042#file-sphinx-go-L33
[3]: https://gist.github.com/Scratch-net/37ae11e589ea3d17fe104a2630306042#file-sphinx-go-L35

Best regards,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170530/8280c459/attachment.sig>