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
signature.asc
Description: Digital signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves