On Wed, May 11, 2011 at 02:55:43PM -0500, Watson Ladd wrote: > > Careful! The arguments to curve25519 are (output, exponent, base). > > (Note the order; that confused me when we were coding up Sphinx.) > > Presumably you meant for EXP(a,b) to mean a^b, though. > > > > Note that 9 does not have prime order in curve25519; it has order 8 > > times a prime. But if the client always ensures private keys are 0 mod > > 8 (as djb requires; see below), this problem is mostly elided.
I just checked again, and 9 *is* a generator of the prime-order subgroup, it turns out. That doesn't affect anything we've said before, though. > More technically we have H=the curve25519 group, which is Z/pZxZ/8Z. Actually, the curve25519 group is isomorphic to Z/pZxZ/4ZxZ/2Z, I'm pretty sure. (Oddly, djb's page claims that 325606250916557431795983626356110631294008115727848805560023387167927233504 has order 8, but when I try it, it looks to have order 4 to me.) But even more correctly, curve25519 is the union of two groups, one Z/pZxZ/4ZxZ/2Z and the other Z/qZxZ/2ZxZ/2Z, for large primes p and q. (And even more more correctly, it's the x-coordinates of the elements of the above groups, which technically doesn't form a group at all, but does allow for unambiguous exponentiation.) > Since private keys are 0 mod 8 they always annihilate the Z/8Z part. > So the curve25519 group is in fact one that is cyclic with prime order > when we generate private keys the right way. The problem is completely > elided I said "mostly" because you still have to check that you don't end up with the identity element, since you might start out in the small subgroup. > > What is "checks X" here? Since the server doesn't really care whether > > or not the crypto is good, this check can probably be elided. > In the GSO paper it is required that X be a non identity element. This > is nontrivial given the curve25519 wire format, but is either > squaring four times or checking that EXP(X,y) is not zero. when we > calculate it. The paper does indeed say that, but I'm questioning whether we actually needed that restriction. All it's checking is that the client isn't stupidly picking x=0. But the server doesn't really care, as it doesn't know who it's speaking with, anyway. The client could just as easily broadcast whatever x it chose. But yes, for symmetry, we could abort if EXP(X,y) is the identity element. (Which I just verified is indeed represented by all-0s.) > The GSO paper uses HMAC for only some of the operations that we are > doing them on and use hash functions of double the length of the HMAC. > Is this an important detail or an unimportant one? Nick implemented the "double the length" hashes by simply hashing twice with different tweaks. - Ian _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
