Skip to main content
5 of 7
edited title

Diffie-Hellman private key recover with non-prime modulus

Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:

p = 0xb5e131610f325255d0a13d28f1acd70cf9c4a05b5ac36db80788ef8449835bd51bf2710e8d6d46e818db44d9d7caf635744db4286e9ef4ca1bd3130b022abdb783b10c3a1b7567d38e2c06faf3ac4f6bb4e430d4d5c29f0fb48290d98642f34dc25c52e599949956fdc6b01602bde81a4ce1b52d009b26002efa6fa2054bb257f3c060784cbe3a21e611a333fe875ab0e29122b0740b1f04acc065877eeb5de66245ebe0a8f1aa783a9b467bc9d184dc860915ebbd18aad5d14a666fe2e24bd7bcd166171dc83909cb2e4ea04c0de6df016e76c09004e648ba790a3708002d017efcd4e1b014ab072c5273305c31c64958a1df2f5dda87e1aa51ff568a51051b`

g = 2

y = 0x669cab3ea6f4999ad5174b86d53e85f7626d39d9734f5c730e772ac950acdddc5301b6845171de4502bc6d1a8bacdb2dbdf8add39295ff2f49dbf08645c7d8556b4774bb299433706a37b7c0ce06f477406f51940e3a3467236cb05bd80642a94e10dda19b70cfca8b5635d73993e6b1a6e571e0c8a9404dfb048540481b38a1d90c1b3fbbb366514501f87427d456c08930d52f37acd8f2ed8e8abde27955b30ec392501006e1ff35ca376a3fc33847f2696a782bd2ec4d347a65c3e61c89c72e3156837667d1a9ffe370f71e5ddcbd51bf3cadca98fb2521cecc563f2ab1b54f6e3f618f4b832893583829aa8d4d2b7a98acdd946c8f65de59319d2127585a

Where $p$ is the modulus, $g$ is the base, $y$ is the public key, and $x$ is the private key in the following equation:

$y = g^x \bmod p$

It happens that the modulus is a composite number, which factorized has the following primes:

18072481203497442511, 18106104909531467117, 18107526042434713051, 18128579828291071093, 18130111242668268281, 18132842465546955301, 18150332662278074701, 18155116105591513309, 18159483435771255379, 18172863048465716483, 18179298730338477761, 18189958641177466721, 18196325044181063441, 18197943051562651469, 18235401697977180833, 18246008227771792913, 18262075579397590001, 18279768681612792817, 18287793748043038657, 18287954881521181249, 18288399030408160057, 18292245591562292983, 18303771618911578381, 18327479207877724861, 18353120081261497783, 18362997414545766673, 18377749324618289369, 18390656168692157183, 18391509959665624283, 18411801130598231773, 18420548427123207229, 18434958041914966891

How can someone find $x$, thus solving in the discrete logarith problem (DLP), by factorizing the modulus into primes, and solving the smaller DLP's with the primes, then combining them with chinese remainder theorem?


I have solved $g^{x_i} \bmod p_i = y \bmod p_i$, where $x_i$ is the $x$-th solution the to smaller discrete logarithm problem with $p_i$ as the $i$-th prime dividing the modulus. E.g. taking $x_1$ and $p_1$, we get the following equation:

$$\begin{align} 2^{1070852037316948481} \bmod 18072481203497442511 &= y \bmod 18072481203497442511\\ &=8431942269025158389\end{align}$$

According to the chinese remainder theorem, I should be able to combine the solutions of the smaller DLP to the solution of the orignal DLP. However, I find that several different algorithms output a different result, which does not happen to be the solution of $y = g^x \bmod p$.

I have read a lot about the Pohlig-Hellman algorithm for attacking the suborder group, but the Pohlig-Hellman is not applicable nor necessary due to the composite modulus.

I started studying public cryptography not long ago, so I apologise beforehand if my data or question is not comprehensive. I hope some of you might be able to come up with a solution to this; it has kept we awake a couple of nights now. Also, I don't know if it is worth mentioning, but the Diffie-Hellman key exchange is the base of an Elgamal encryption, where I have the ciphertext ($c_1, c_2$), and the aforementioned parameters.

Best regards,

Alice and Bob