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

Question

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?

Answer 1

Well, for one thing, you are not using a "One Time Pad". A "One Time Pad" means, by definition, that someone generates a pad of numbers using true randomness (and not algorithmicly), and that no potential adversary has any information on what that pad may contain. Then, that pad is given to both the sender and the receiver, and then the sender uses it to disguise the plaintext, in a way that the receiver (with the pad) can recover the plaintext, but the adversary, who doesn't have the pad, gets no information about the plaintext (because with the ciphertext and any potential plaintext, there is a possible pad that makes that possible, and the adversary has no way of deciding which potential pad is more likely.

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