# Discrete log problem - does luck exist?

Assume the discrete log problem:

$$g^x mod (p) = h$$

For sure, $$p$$ is a prime number and $$g$$ is its primitive root or generator and assume that Alice sent $$h$$ to Bob and middle man caught it. So attacker knows $$g, p, h$$ and wants to find $$x$$.

One solution is for the attacker to try all possible values. The modular exponentiation and prime/primititve root allows that $$g^x mod (p)$$ for $$x$$ values would result in all the sequence between $$0$$ and $$p-1$$.

Question: Since the sequence order is random, why can't attacker just got lucky, let's say at the 100th try ? Take a look at the image where $$g=5$$ and $$p=277$$ and assume Alice got $$h=193$$. When attacker goes through brute force, he will reach 193 pretty fast because it's close in the sequence.

• That's why key / field size are important security parameters? For a 2048 bit key you'd have about 615 decimal digits or so (for an adversary that doesn't take any advantage of mathematical properties of the key, DH 2048 doesn't have a 2048 key strenght). That makes guessing right a very unwieldy proposition. Such small numbers allow easy computation / insight, but they don't offer any security. Mar 4 at 14:21
• @MaartenBodewes the operation iteration number, is it always 2^{number of bits of p} or it's just "p" operations" ? for example if $p = 17$, we would get a sequence {1, ..., 17}, so 17 operations. why is it said that it takes 2^{number of bits of p} ? Mar 4 at 14:24
• Because the actual value of $p$ is close to two to the power of that number of bits. See e.g. here here and note that hexadecimal is more dense than decimals. Put that number in WolframAlpha or similar to get the decimal values. Oh, and note that 2048 is the about smallest size you should use, for 128 bit strength or better you'd start at 3072 bits. Mar 4 at 14:31
• Thanks for the answer. in $p=17$ example, it's represented by 5 bits. so if you say number of operation is 2^5 = 32, you will be wrong. as number of operations will clearly be max 16 Mar 4 at 14:33
• Luck on the order of $1/2^{256}$ or $1/2^{1024}$ or $1/2^{2048}$ isn't luck, it's divine intervention. Mar 5 at 7:05

Examples that use very small parameter and key sizes are mainly provided to let students understand the system. Of course they do provide the same security as expected for the algorithm. The thing is that this security scales with the size of the parameters / key size. Note here that the key size is determined by specific parameters required by the algorithm.

How the key size determines the (key) strength is directly. You can get a good idea how they relate by looking at keylength.com, for instance the second table provided by NIST. Obviously the security strength is in the second column and the Discrete Logarithm shows the key sizes (basically the field size).

For these really small parameter / key sizes the difference between 4 and 5 bit matters a lot. The value 17 is close to $$2^4$$ but you'd still require 5 bits to encode it as a positive integer. However, it is perfectly fine for a 3072 bit field size to be slightly smaller than that. The actual private key may even be smaller than that (!) if it is a random value between 1 and the maximum size.

For 128 bits, the usual minimum key strength you'd require a key / field size of 3072 bits. Each 10 bits is roughly equivalent to 3 decimal digits (as $$2^{10} = 1024$$) so you'd expect a number with at least $$(3072 / 10 * 3) = 921$$ decimal digits. In case of the named finite field parameters ffdhe3072 with a key size of 3072 this would mean guessing between $$2$$ and the value $$q - 2$$ (inclusive). I'll show the decimal value below the answer to give some indication of the size of the number involved, it messes up the text if I show it here.

Winning the lottery isn't just more likely, it's almost a given compared to guessing correctly. Luck exists, but not at this scale.

There are, of course, better ways to solve the Discrete Logarithm problem, which is why such a large key size is still required.

Here's $$q - 2$$, all 925 decimals:

2,904,802,997,684,979,031,379,293,327,137,290,023,895,861,052,485,328,253,719,434,870,043,896,647,469,511,089,876,550,450,075,158,301,207,418,480,298,946,765,627,157,878,032,850,085,253,971,512,897,361,935,809,534,141,411,289,574,103,829,992,165,862,143,028,566,900,103,507,410,178,478,966,667,182,267,588,100,696,547,203,482,140,184,073,180,161,208,698,600,960,778,328,155,348,149,208,707,159,217,464,696,403,464,434,157,415,892,166,118,519,284,130,494,356,118,598,332,871,450,176,756,394,201,938,888,284,472,745,591,643,764,548,444,442,174,443,588,450,997,878,794,274,670,109,903,803,074,977,528,435,890,523,058,597,726,713,535,127,266,929,482,364,550,877,140,560,893,665,162,753,287,464,251,750,667,468,789,595,674,589,450,900,933,225,631,415,780,285,189,890,141,302,034,131,397,512,192,159,299,855,474,428,723,092,567,326,414,970,763,868,236,430,086,177,258,366,933,938,890,414,525,673,083,576,797,164,796,169,626,147,935,988,444,534,942,982,064,019,296,501,168,423,076,761,074,513,114,992,197,390,819,250,562,656,338,225,918,572,472,725,665,916,261,473,342,310,477,092,180,147,435,899,062,660,217,343,068,115,027,606,624,293,967,811,562,169,326,312,393,110,935,564,951,285,059,982,067,141,009,320,628,556,626,023,135,863,373,821