There's a new password store mechanism, called Sphinx http://webee.technion.ac.il/~hugo/sphinx.pdf which is very nice and protects from device or user compromise. I haven't found any implementations and tried to do my own using curve25519 primitive and libsodium.

Sphinx proto

There's login phase when user and device do communication and that's where I got stuck, though it looks pretty simple.

I convert hash to a valid curve point x using elligator2. Then scalar multiply it by some random ρ. Then "device" multiplies it by its k.

So, I have β = x * ρ * k.

I'm stuck at the point where I need to do β1/ρ

in Ref10 implementation of curve25519 there's "feInvert" function which I tried to apply to ρ and then scalar-multiply again, but that did not work.


While point coordinates lie in the finite field over which the curve is defined, in this case $GF(p)$ with $p=2^{255}-19$, the scalars that you use lie in a field defined by the order of the generator, which is different from $p$.

Therefore when you invert using feInvert you invert with respect to the wrong prime.

You need to invert in $GF(n)$ with $n=2^{252} + 27742317777372353535851937790883648493$.

Unfortunately for you, X25519 never use arithmetic in $GF(n)$ and the only operation required by ed25519 in $GF(n)$ is the modulo reduction, not the inversion. Therefore there is no readily available code for that in the reference implementations, and you have to either look for some code that implemented it or build your own.

| improve this answer | |
  • $\begingroup$ Thanks! What about for example p-256 curve? Is it easily achievable? $\endgroup$ – John dow May 17 '17 at 13:22
  • $\begingroup$ It depends on the implementation. Any ECDSA signature generation/verification should have an inversion function. The problem with curve25519 is that it is used with EDDSA which doesn't need the inverse. $\endgroup$ – Ruggero May 17 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.