On Wed, Dec 12, 2012 at 04:52:11AM +0200, George Kadianakis wrote:
Let p = 3 mod 4 be prime, with q=(p-1)/2 also prime, and p is at least 1536 bits. (2048 if there's room.) [Use group 5 or group 14 from RFC 3526.] Let g be a generator of the order-q subgroup of Z_p^* (g=2 for the two above groups from the RFC.)
To pick a private key, pick a random 1536-bit (or 2048-bit) number, and force the low bit to 0. So there are 1535 (2047) bits of randomness, which is the size of q. Let x be that private key. Let X = g^x mod p.
Here's the trick: When you send the public key, randomly decide to send either X or p-X. That will make the public key part a uniform 1536-bit (2048-bit) string (well, negligibly different from uniform).
The other side constructs y and Y=g^y mod p in the same way, and sends either Y or p-Y.
Note that both (p-Y)^x = Y^x mod p since x is even, and similarly (p-X)^y = X^y mod p, so key derivation goes through unchanged.
The downside of the larger public keys is that it puts a lower bound on the size of the data sent by the initiator before the responder answers.
Ha. The Z_p stunt you describe is nifty! I will seriously consider it, if the telex-curve protocol doesn't work out without a pre-shared public key.
Note that the above protocol assumes that p is very close to a power of 256, but that's true of the RFC 3526 groups 5 and 14 I pointed to.
Right.
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).
You're in luck! You don't get to implement any of those parts! ;-)
Write a class UniformDH that has hard-coded constants p (the 1536-bit prime in group 5 of RFC 3526) and g = 2. Compute len = the number of bytes of p = 192. Its init method will pick a uniformly random len-byte string, and convert it to a long called priv. Let flip = (priv % 2) and priv -= flip (so flip is the old low bit of priv, and priv is now even for sure). Compute pub = pow(g,priv,p) and if flip == 1: pub = p - pub. Convert pub to a len-byte string and store it as pubstr.
Add a method getpub() which returns pubstr.
Add a method getsecret(theirpub) which converts theirpub (a len-byte string) into a long called theirpublong. Compute secret = pow(theirpublog,priv,p) and convert secret into a len-byte string and return that string.
That should be it.
[You can use Crypto.Util.Number.{long_to_bytes,bytes_to_long} to accomplish the conversions above, if you're allowed to use PyCrypto. For the randomness, os.urandom() is fine.]
- Ian