# What's the catch with this Diffie-Hellman based cryptosystem?

This is most likely a dumb question. I'm doing a mathematical research project that overflowed a bit into cryptography. It got me thinking about something. Can the following cryptosystem work?

Let Alice and Bob share a private key $$d$$ using the Diffie Hellman key exchange, where $$d\in \mathbb{F}_p$$ for some prime $$p$$. If Alice wants to send Bob a message $$x$$, then Alice sends Bob the encrypted message $$x+d$$. Bob decrypts this message by subtracting $$d$$ (all while in $$\mathbb{F}_p$$, of course).

If a hacker was to crack this cryptosystem, it would essentially be the same difficulty as cracking Diffie-Hellman, right? The encryption/decryption is incredibly fast, it's just an addition/subtraction modulo $$p$$, and the cracking is hard. It seems that the rate of information transfer is a lot faster with this cryptosystem as opposed to RSA.

My main question is: What's the catch, if there is any? Is this a known cryptosystem?

• "Is this a known cryptosystem?" --> it is one-time pad Jul 19, 2023 at 6:57
• Well, the final modulo addition would be akin to a one time pad. The DH doesn't quite randomize the end result fully, which is why usually the DH is followed by a KDF. Also, modulo addition / subtraction is probably not as fast as XOR and might leak more information. Personally, I'd have a look if IES would not do what's required, to avoid common practical / implementation issues. Jul 19, 2023 at 7:39
• Well, if you do a separate DH exchange for every message, it can be viewed as a variant of El Gamal (which does multiplication rather than addition to stir in the message). In any case, there are some subtle security issues here; one nice thing about IES is that something thought through the issues and came up with ways to address them... Jul 19, 2023 at 12:47

If a hacker was to crack this cryptosystem, it would essentially be the same difficulty as cracking Diffie-Hellman, right?

Well, the answer to that comes down to the meaning of "crack"; cryptographers give a different meaning to that then lay people do.

What a cryptographer means by "crack" an encryption system includes "find any information about the plaintext"; one such piece of information is "does this ciphertext encrypt the specific plaintext $$x'$$"?

Well, it turns out that, with your system, if $$x \ne x'$$ (that is, his guess wasn't the actual encrypted plaintext), an adversary as about a 50% chance of being able to prove it, and to a cryptography, that would constitute a "break".

How he would do that would rely on quadratic residues [1]; by observing the DH exchange (and testing whether the exchanged values are quadratic residues), the adversary can determine whether $$x$$ is a quadratic residue (even though he doesn't know that value). Then, when he sees the ciphertext $$x+d$$, he can subtract $$x'$$ from it (giving $$d+(x-x')$$), and test whether that is a quadratic residue. If $$x \ne x'$$, then whether that value is a quadratic residue has a 50% change of not agreeing with $$x$$ being a quadratic residue, and if those two things disagree, he then knows $$x \ne x'$$

And, for a cryptographer, that is enough to say the system is "cracked".

And, even if you use the definition of "cracked" as full message recovery:

The encryption/decryption is incredibly fast, it's just an addition/subtraction modulo $$p$$, and the cracking is hard.

That sounds like you are proposing to use the shared secret from a single DH exchange to encrypt multiple messages. That can be easily 'cracked' (that is, fully decrypted) depending on the contents of the message; for example, it would be straight-forward to recover both messages if they were ASCII-encoded english (with the attacker knowing nothing about the messages beyond that. He would do this by looking for the relationships between the two ciphertexts - the attack would be similar to breaking a "two-times pad".

[1]: Background: a value $$x$$ is a quadratic residue modulo $$p$$ if there exists an integer $$y$$ such that $$x = y^2 \pmod p$$. It is easy to tell, given $$x$$, whether it is a quadratic residue (for prime $$p$$).

• Sorry, I should have been more clear. In my context, "crack" means to discover the original message. Jul 19, 2023 at 19:13
• @TheBestMagician: see my additions about encrypting two different messages with the same DH shared secret Jul 19, 2023 at 19:24

It's studied Diffie-Hellman in the multiplicative subgroup of the finite field $$\mathbb F_p$$, followed by encryption in $$\mathbb F_p$$. That is, appropriate prime $$p$$ and some $$g\in\mathbb F_p$$ are publicly agreed upon, e.g. the 3072-bit MODP Group of RFC 3526. Then sending a confidential message $$x\in[0,p)$$ from $$A$$ to $$B$$ goes:

• A chooses random $$s_A\in[1,p)$$, computes and sends $$t_A=g^{s_A}\bmod p$$
• B chooses random $$s_B\in[1,p)$$, computes and sends $$t_B=g^{s_B}\bmod p$$
• A computes $$d={t_B}^{s_A}\bmod p$$, computes and sends $$c=d+x\bmod p$$
• B computes $$d={t_A}^{s_B}\bmod p$$, computes $$x=c-d\bmod p$$

Absent alterations, $$d$$ and $$x$$ are the same on both sides. But there are serious security issues:

1. The system is totally vulnerable to a Man in the Middle attack, where an active adversary $$E$$ impersonates $$B$$ w.r.t. $$A$$, and $$A$$ w.r.t. $$B$$, which allows to intercept $$x$$ unknown to $$A$$ and $$B$$, or/and alter $$x$$ in transit as desired.
2. An integer $$x$$ can carry a limited amount of information (383 bytes for the parameters considered). For larger messages the protocol needs to be redone. If instead we reused $$d$$ for multiple distinct $$x$$, the protocol would be very insecure: if e.g. we cut a 384-byte message into a 383-byte segment and a 1-byte segment, the later can take only a few (at most 256) values, leading to 256 possible values for $$d$$ given the second $$c$$, which allows to decipher most of the first segment of the message; and for messages with some redundancy, probably the whole message.
3. In circumstances where the adversary knows that $$x$$ is one of two distinct known values $$x_0$$ or $$x_1$$ (e.g. because $$x$$ is the name of one of two candidates in an election), an adversary merely capturing a copy of the communications can find $$x$$ and be sure of that for about at half of the uses of the protocol (so gets at least 75% probability of correct guess of $$x$$), based on quadratic residuosity. The attack goes as follows.
• Acquire $$t_A$$, $$t_B$$ and $$c$$ as they are transmitted.

• Compute $$d_0=c-x_0\bmod p$$ and $$d_1=c-x_1\bmod p$$, which are the two possible values of $$d$$. In the rare event that one of these $$d_i$$ is $$0$$, that can't be the correct $$d$$, thus we get $$x=x_{1-i}$$.

• Otherwise compute the Legendre symbol for $$d_0$$, that is $$\left(\frac{d_0}p\right)=({d_0}^{(p-1)/2}+1\bmod p)-1$$, and similarly $$\left(\frac{d_1}p\right)$$. If they are equal (that is both $$+1$$ or both $$-1$$), we can't learn $$x$$, stop.

• Otherwise, compute the Legendre symbol $$\left(\frac d p\right)$$ for the real $$d$$, using that

• if $$\left(\frac{t_A}p\right)=+1$$ or $$\left(\frac{t_B}p\right)=+1$$ then $$\left(\frac d p\right)=+1$$
• otherwise $$\left(\frac d p\right)=-1$$.

[Note: if $$\left(\frac g p\right)=+1$$, then $$\left(\frac d p\right)=+1$$ and it's not necessary to intercept $$t_A$$ or $$t_B$$]

• This $$\left(\frac d p\right)$$ will match one of the two $$\left(\frac{d_i}p\right)$$, and we get $$x=x_i$$.

As in any cryptosystem there are possible implementation issues, on top of the above theoretical ones.

Note: contrary to the question's claim, the system is slower than RSA at equal size of the public modulus, ignoring establishment of the public/private key pair (which in RSA is reused): it's hundreds times slower for encryption (because it uses thousands of modular multiplications rather than 17 typically in RSA), and over 3 times slower for decryption (because the Chinese Remainder Theorem can't be used with of a prime public modulus, as typically in RSA).