wow this is really interesting. In Java, I can do 2206 variable base scalar mults per second, but 90k conversions between ed25519 ad curve25519 points per second

so it's faster to convert an ed25519 point to a curve25519 point, scalarmult it, and then convert it back to an ed25519 point (vs just doing a varbase scalar mult on the ed25519 point directly)

knaccc: are you deserializing first and converting both coordinates?

UkoeHB the ed25519<->curve25519 conversion doesn't require serializing/deserializing, because they're just 32 byte little endian unsigned ints. after the conversion, then yes the curve25519 scalarmult lib must be decoding and later encoding the point

i can't do a direct comparison between ed25519 and curve25519 in my dev environment, because they're totally different libraries with all sorts of inefficiencies due to the java object overheads etc

are you sure? are the ed25519 and curve25519 encoding schemes the same?

UkoeHB it seems to all be working. Ed25519 compressed points are just a "y" coordinate, and Curve25519 points are just a "u" coordinate

is the sign of the other coordinate preserved when converting?

there doesn't seem to be any need for messing with the sign

the encoding scheme pastes the sign of the other coordinate in the MSB

yeah i've seen curve25519 code do that

but the libsodium conversion code doesn't do anything like that when doing ed25519->curve25519 conversion

and i'm not doing it either

and i've been testing ECDH exchanges and things seem to work

oh libsodium has its own conversion code?

it does in the ed25519->curve25519 direction. github.com/jedisct1/libsodium/blob/…to_sign/ed25519/ref10/keypair.c#L46

they are testing `ge25519_is_on_main_subgroup()`, although for our use-case it might not be needed

honestly I am quite confused about the sign question

UkoeHB i did this test: pick scalars a and b, and in ed25519 derive A=aG, B=bG and S=aB. Then I convert A from ed25519 to curve25519, and in curve25519 calculate b * A_curve25519. I then convert the result back to an ed25519 point S', and I can verify that S==S'

so everything seems to be working perfectly

hmm

My report seems to have been approved. A hell lot of links there:

oh wait, actually that's not what my test does. actually i keep b * A_curve25519 as a curve point, and convert the ed25519 aB result to curve25519 and check they're the same

i'll test converting them to ed25519 instead

s/i keep b * A_curve25519 as a curve point/i keep b * A_curve25519 as a curve25519 point

ah ok it fails when i convert back the curve25519 result to ed25519, so maybe this is only easy in the ed25519->curve25519 direction

you're right, it only passes my test sometimes

e.g. a failure here:

b125f55e9a791496e077868b15364629a501c8436c39b52e511574439d8d525e

b125f55e9a791496e077868b15364629a501c8436c39b52e511574439d8d52de

so i need to encode the sign

but only in the curve25519->ed25519 direction

so i need to recover the x coordinate from the y coordinate when doing curve25519->ed25519

but that's great for our use case, because we only need to go in that direction if the view tag matches

so it doesn't matter if that's more expensive

why do you need to go back to ed25519?

the resulting key is always hashed

UkoeHB depends on whether we want to use Hs(curve25519 shared secret)G + D or stick to Hs(ed25519 shared secret)G + D

i think i'd be happy just using the curve25519 ECDH derivation everywhere

knaccc: you can try `a * B ?= a * (-B)`

maybe `curve25519(ed25519(B)) == curve25519(ed25519(-B))`

knaccc: crypto.stackexchange.com/questions/…9-over-ed25519-for-key-exchange-why

"Under the birational equivalence of Curve25519 and edwards25519, each X25519 public key corresponds to two possible Ed25519 public keys."

UkoeHB yes you're right, I did the test and they're the same (because I've not fixed the code yet)

UkoeHB are you saying you think it is not actually possible to convert back from curve25519 to ed25519 then, because of the ambiguity?

ah actually

i think the secret is to not just convert the curve25519 u coord back to the ed25519 y coord

i need to also determine the x coord

and then there won't be an ambiguity

the ed25519 x coord is just curve25519 u/v

but that does mean i need to recover v first

so there will be a performance hit

doh, i don't have a proper curve25519 library to do that for me

I don't think the reverse conversion is possible without losing the sign. You just have to 'pick one'

UkoeHB but if i know both x and y coordinates, instead of just the y coordinate, there is no sign ambiguity

so i just need to convert both x and y from u, instead of only getting y

after doing a variable scalar mult, the sign will change

it's not really a 'sign' in the first place, it is just whether the x coordinate is odd/even

UkoeHB here is the java code that normalizes the X and Y and then simply uses the sign of x to encode the sign into the 32 byte compressed representation:

final Ed25519FieldElement inverse = this.Z.invert();

final Ed25519FieldElement x = this.X.multiply(inverse);

final Ed25519FieldElement y = this.Y.multiply(inverse);

final byte[] s = y.encode().getRaw();

s[s.length - 1] |= (x.isNegative() ? (byte)0x80 : 0);

so i'm thinking that if i know X and Y properly, i can |= the 0x80 myself if necessary, depending on the value of X

(normalization required because this is one from P3 coordinate space)

You can try it, but I don’t think the ‘sign’ can be preserved. Odd/even of x will change at random during a multiplication.

UkoeHB you may well be right, i'll need to think it through. i'll let you know how the experiments go

still, this is moot if we just use the curve25519 derivation everywhere

so not a problem

UkoeHB lol you're totally right, my brain wasn't processing properly what you asked me to test earlier. if curve25519(ed25519(B)) == curve25519(ed25519(-B)), then there is no way the sign can be recovered

there is an interesting technique that people use when they want to publish a Curve25519 public key, but sign using Ed25519. They use their private key to derive the Ed25519 properly, and then store the sign of the proper Ed25519 public key into the unused bits of the scalar in the schnorr signature

so then the person validating the signature can convert the curve25519 public key to the ed25519 point with the correct sign

as documented here: moderncrypto.org/mail-archive/curves/2014/000293.html

hmm interesting

> The Ed25519 public key's sign bit is conveyed in the signature. This allows an attacker to try to forge a signature for Alice based on either her actual Ed25519 public key or its negative. Since both are legitimate public keys, an attacker who can't break Ed25519 can't forge signatures for either.

Would this reduce bit security from 2^128 to 2^127? Aka not a practical impact? How do you think about that

jberman[m] it's just an interesting technique. i'm not suggesting at all that we should use it

we don't need it

but yes i think it just takes 1 bit off the security of the signature

Got it, just trynna learn :)

What is the best way to debug the functions at src/crypto/crypto.cpp? I'm struggling to execute the check_ring_signature. I have compiled the code and tried to execute the cncrypto but I always get 'invalid argument' so probably Im not executing it correctly. (Im using the terminal and gdb)

My c++ skills are pretty rusty too

Are there any bindings or some test file that I could easily call these functions?

git grep check_ring_signature tests

Piggy back on one of the files you find. performance_tests is minimal.

<moneromooo> "git grep check_ring_signature..." <- Thanks moneromooo but I know where the files are but I don't know how to set breakpoints on them as I dont know how to execute them separated. Do you mean executing the ctests like recommended in tests/README ?

Sure. If you can't set breakpoints, you can add printf or log calls, that's what I usually do.