# Diffie-Hellman: Does the size of the prime modulus depend on the potential size of the secret?

I'm writing my own cryptosystem that uses One Time Pad and Diffie-Hellman to generate keys for the OTP. I am using Rails on the server side and Javascript for the client side.

Please don't tell me this is insecure and I shouldn't do it. I'm doing this purely for educational purposes and in no way will this be deployed in a non-experimental sense.

Since this is OTP, I need a keystream that is at least as long as the message being encrypted. From what I have read, it seems like DH needs a ridiculously large safe prime modulus. Or does it?

Every character needs a different random key, so for a string that is 10 characters long the DH key exchange needs to happen 10 times to create an array of common secret keys for that string.

However, I seem to be getting what may be integers that are way larger than necessary.

Let's say that the user makes an array of private keys:

var userPrivateKeys = [9,12,0,23,7,8,4,7,15,24]


And a 2048-bit safe prime modulus with 2 as the generator:

var prime = 32317006071311007300338913926423828248817941241140239112842009751400741706634354222619689417363569347117901737909704191754605873209195028853758986185622153212175412514901774520270235796078236248884246189477587641105928646099411723245426622522193230540919037680524235519125679715870117001058055877651038861847280257976054903569732561526167081339361799541336476559160368317896729073178384589680639671900977202194168647225871031411336429319536193471636533209717077448227988588565369208645296636077250268955505928362751121174096972998068410554359584866583291642136218231078990999448652468262416972035911852507045361090559

var generator = 2


The array of shared keys for the user ends up looking like this:

var userPublicKeys = [512,4096,1,8388608,128,256,16,128,32768,16777216]


After the user and the server exchange their public keys, we get this as the common key:

var commonKeys = [134217728,2.2300745198530623e+43,1,1.725436586697641e+69,72057594037927940,16777216,17592186044416,1.78405961588245e+44,6.216540455122333e+85,1]


Holy....

Those integers are way way larger than the modulus of the alphabet, or even the modulus of ASCII.

I [think I] understand that the prime modulus must be huge in the context of creating keys to be used in ciphers like AES, but what about in the context of having different random keys for each character in OTP?

For example, let's say that my messages only feature letters a through z, and I have a smaller modulus:

p = 27
g = 3

userPrivateKeys = [9,12,0,23,7,8,4,7,15,24]


Our algorithm would be:

2^a mod 27


or in Javascript...

Math.pow(2, a) % 27


And we'll have generated a list of public keys:

userPublicKeys = [26,19,1,5,20,13,16,20,17,10]


That's way more manageable.

So in this context, is there a problem with the prime modulus being so small?

As far as I can tell, the only way to break this is through exhaustive search; since OTP cryptext contains no information about the original message, exhaustive search would be infeasible. I have read of other possible ways of breaking this and DH in general, but usually I don't understand them or they either depend on one of the secrets being known.

So is there something I'm missing?

-
Yes, since one can solve the discrete logarithm problem to go from userPublicKeys to userPrivateKeys. $\hspace{.31 in}$ The ciphertext is irrelevant to that attack, since that attack only uses the key exchange data. $\:$ You're also missing that mod(g^a,p) needs to be computed exactly, rather than via Math.pow(g, a) % p. $\hspace{.57 in}$ –  Ricky Demer Dec 10 '13 at 4:57
Okay, I read a little more on the discrete logarithm problem. (I swear I couldn't find much specific on it last night. Haha) So would I be correct in saying that the discrete logarithm problem can be solved easily when the prime modulus is small but it becomes increasingly difficult to solve the larger the prime gets? –  user10800 Dec 10 '13 at 5:15
Yes. ${}{}{}\;$ –  Ricky Demer Dec 10 '13 at 5:17

Instead, you are performing a series of Diffie-Hellman operations to generate shared secrets, and then using those shared secrets to perform a stream encryption.

Here is why this is distinction is important; you state:

the only way to break this is through exhaustive search; since OTP cryptext contains no information about the original message

This would indeed be true, if you were using an OTP; the attacker would literally have no information beyond the ciphertext, and the ciphertext would indeed reveal no information about the plaintext. However, the ciphertext is not the only thing the sender and receiver are exchanging, you mention previously that:

the user and the server exchange their public keys

That is, there is information available to the attacker in addition to the ciphertext that he can use. That is, instead of being informationally secure (which OTP is), you also hope that the attacker cannot use the public keys to recover the shared secret (pads), that is, you hope that the problem of recovering the shared secret is just too difficult for the attacker. In other words, you hope that you are computationally secure.

Here, in that light, when you ask:

is there a problem with the prime modulus being so small?

The question you are asking is "is Diffie-Hellman computationally secure, even if the modulus is tiny". The answer to that is "no, it is not". For MODP groups (which are the groups you are using), it appears that DH can be broken unless the modulus is at least 800 bits (actually, attacks against modulii that size haven't actually been demonstrated, but there have been attacks against related primitives, and we believe those attacks can be converted into attacks against Diffie-Hellman).

There are other groups that can be made smaller and still are believed to be secure (for example, an elliptic curve group is probably pretty secure even if the curve is only 200 bits or so); however you won't get anywhere close to "an ASCII value".

When we use Diffie-Hellman like this, what we generally do is perform a single Diffie-Hellman operation to generate a single (large) shared secret, and then give that shared secret to a Key Derivation Function; the output of that KDF may be then presented to a Stream Cipher, whose output is then used to actually encrypt the data

-
"unless to modulus" $\: \mapsto \:$ "unless the modulus" $\;\;\;\;$ –  Ricky Demer Dec 10 '13 at 5:18
@RickyDemer: thanks; if you go through my answers, you'll find that I often think one word, but type something else... –  poncho Dec 10 '13 at 5:21
Since OTP requires perfect informational secrecy by definition, what would you suggest I refer to this scheme as? Just a "stream cipher"? I referred to it as a One Time Pad because, aside from the fact that information about they keys is leaked, it seems to be the same idea otherwise. Couldn't using a key derivation function open up my system to exhaustive search? Wouldn't there still be an advantage to each message character having its own random shift? In case I didn't mention(and in case it's important), only truly random numbers are being used. –  user10800 Dec 10 '13 at 5:22
@user10800: well, I'm not sure what you should call it (stream cipher really doesn't apply either, come to think of it; it uses inputs from both sides; it appears to be closest to El Gammal, but it's not that either). The term OTP doesn't apply, because the one point that you're missing is a very important point about OTPs. As for exhaustive search, well, you're secure computationally, and so the correct protection against exhaustive search is to make it computationally to difficult to consider. As for each character getting its own random shift, we have better ways to protect plaintext. –  poncho Dec 10 '13 at 23:44