On Wed, Dec 12, 2012 at 11:14:08AM -0500, vmonmoonshine@gmail.com wrote:

...

The only issue with your trick, is that I'm not looking forward implementing a custom DH key exchange in Python (especially the DH parameter generation and public key validation parts).

From the conversation of Zack with Steven at the breakfast table at Hotel Cellai, I'm pretty sure that Stegotorus is using DH based on elliptic curve and its twist protocol. So you can find an implementation of it there. Though I haven't looked at the crypto part of the code myself.

Also could you please refer me to the reference that proves that X or p-X is uniformly random. It seems to me that you are taking a quadratic residue to an even power, so you always get a bi-quadratic residue for X. Then if I'm the distinguisher who knows the public group, and I see that the bi-quadratic residues appears 1/2 times instead of 1/4 of the times then I can smell that something going on.

Z_p^* has order 2q, where q=(p-1)/2 is prime. Since 2 is a quadratic residue, both 2 and 4 generate all of the order-q subgroup of quadratic residues (call the group Q), so X will be a uniform (up to negligibility) element of Q. Since -1 is a quadratic non-residue, X is a quadratic residue if and only if p-X is not. (For all 0 < X < p.) So the output (randomly X or p-X) will be a uniform element of Z_p^*, which is negligibly different from a uniform 1536-bit string.

[There's no such thing as a "bi-quadratic residue" in this setting; all quadratic residues in this group have one square root which is itself a quadratic residue and one which is not.]

- Ian