The following Pari/GP function prints howmany integer discrete logarithm problems with moduli in the vicinity of n! (n factorial):
f(n,howmany) = my(g) ; my(count=0) ; for(k=0 , +oo , my(offset) ; if(k%2 , offset=0-(k-1)/2 , offset=k/2) ; my(p=n!+offset) ; if(p>2 && ispseudoprime(p) && ispseudoprime((p-1)/2) , g=znprimroot(p) ; if(lift(g)<10 , my(target=3) ; if(p==7 , target=4) ; print("solve " , lift(g) , " ^x = ",target," mod ( " , n , " ! + " , offset , " )") ; count+=1 ; if(count>=howmany , break)))) ; g
The moduli are safe primes which have a generator (primitive root, calculated with znprimroot) that is a single digit number. Here is example output for 3 problems in the vicinity of 5! :
? f(5,3)
solve 2 ^x = 3 mod ( 5 ! + -13 )
solve 2 ^x = 3 mod ( 5 ! + -37 )
solve 5 ^x = 3 mod ( 5 ! + 47 )
Mod(5, 167)
For convenience, it returns the generator of the last problem. Note: 5! + 47 = 167. Solve the last problem by passing the target and generator to znlog:
? q=znlog(3,f(5,3))
...
94
yielding the solution 5^94 = 3 mod (5! + 47).
The goal is to create compactly expressible computational problems with unique solutions, similar to previous with RSA.
We hardcode 3 as the target, the number on the right hand side to take the logarithm of, because, other than for safe prime 7, 3 seems never to be a generator of any other safe prime, so we won't see the trivial problem 3^x=3. We special-case the modulus 7 in the code, providing the problem 3^x=4 (mod 7), which is just a little bit more difficult to solve than 3^x=3 (mod 7). Targets other than 3 could be used on the right hand side to vary the problem and to thwart precomputation. Most numbers are fine; just avoid powers of the generator in the field of integers (Z), e.g., solving 2^x=8 is too easy. Vary the modulus to avoid attacks like LOGJAM.
Unlike the previous similar approach to designing compact problems around integer factorization, problems do not need extensive testing to make sure they are hard. However, as before, the poser of the problem does have to solve it first in order for the puzzle to be used in a framework which can only check answers with string equality.
Like previously, we consider the following specific constraints: the problem must be 32 characters or less, and the solution must be 63 characters or less, puzzles for a WiFi access point.
For an answer of 63 digits or less in decimal (base 10), the maximum modulus is around 49!, a 209-bit discrete logarithm problem. (But even this is larger than I could solve, seen below.) In contrast, with factorization we could pose problems as large as 82! or 408 bits because the smallest factor (the answer) is at most half the length of a number.
Base 36 is fairly obvious, which allows going up to 68! or 321 bits.
Base 64 encoding is fairly well defined. There is a bit of ambiguity of endianness when encoding the large integer. It's also possible the solver might think we are asking for an answer in base 256, encoded as base 64. The solver can try various possibilities. Base 64 allows going up to 77! or 376 bits. We explore some possible presentations of such a problem, with the length of each presentation:
2^x=3mod77!+8747base64 (22 characters)
2^x mod(77!+8747)=3,base64 (26 characters)
We could go further by requiring only the first 63 digits of the answer to be given. However, I don't know whether finding the first 63 digits of a discrete logarithm is just as difficult as finding all the digits.
99! is 519 bits. head63c is meant to suggest using the command "head -63c" to take just the first 63 digits of the 156-digit answer.
2^x=3mod99!-435541,head63c (26 characters)
Another way, probably even harder to mathematically cheat, is "compress" the answer from decimal to hexadecimal with a hash function. Hexadecimal hashes MD5 (32 characters), SHA-1 (40 characters), and SHA-224 (56 characters) fit within the 63 character limit.
2^x=3mod99!-435541,MD5 (22 characters)
Standardization would allow puzzles to be expressed even more compactly. A puzzle like this could be specified by a standard puzzle type identifier, puzzle size, and a random number seed string which is used to generate the puzzle. (Of course, WPA2 is already a standardization of a hash pre-image puzzle; we'll explore this in a future post.)
Next, we explore how long it takes to compute discrete log. Unlike factoring which seems to be a sexier problem, there is less good software for solving discrete log. We use znlog in Pari/GP. There's some old discussion at Stack Exchange and at Mersenne Forum about other software.
solve 2 ^x = 3 mod ( 11! + 179 )
time = 2 ms.
13969860
solve 2 ^x = 3 mod ( 12! + -61 )
time = 6 ms.
152894882
solve 2 ^x = 3 mod ( 13! + 347 )
time = 6 ms.
5526616656
solve 5 ^x = 3 mod ( 14! + 1103 )
time = 14 ms.
26782423544
solve 5 ^x = 3 mod ( 15! + 503 )
time = 17 ms.
865438088348
solve 5 ^x = 3 mod ( 16! + 503 )
time = 25 ms.
14155038504644
solve 2 ^x = 3 mod ( 17! + -61 )
time = 42 ms.
32655671864480
solve 5 ^x = 3 mod ( 18! + -193 )
time = 67 ms.
4821039721853340
solve 2 ^x = 3 mod ( 19! + 467 )
time = 117 ms.
59555254842989324
solve 7 ^x = 3 mod ( 20! + -2161 )
time = 182 ms.
1829979517258017906
solve 2 ^x = 3 mod ( 21! + 59 )
time = 374 ms.
35384503047553231818
solve 2 ^x = 3 mod ( 22! + -661 )
time = 523 ms.
360440708997546089152
solve 2 ^x = 3 mod ( 23! + -997 )
time = 835 ms.
25774862600178036411920
solve 5 ^x = 3 mod ( 24! + 263 )
time = 1,244 ms.
54654812251235284851692
? allocatemem
*** Warning: new stack size = 16000000 (15.259 Mbytes).
? allocatemem
*** Warning: new stack size = 32000000 (30.518 Mbytes).
? allocatemem
*** Warning: new stack size = 64000000 (61.035 Mbytes).
? allocatemem
*** Warning: new stack size = 128000000 (122.070 Mbytes).
? allocatemem
*** Warning: new stack size = 256000000 (244.141 Mbytes).
? allocatemem
*** Warning: new stack size = 512000000 (488.281 Mbytes).
solve 2 ^x = 3 mod ( 25! + 6827 )
time = 2,119 ms.
6376609950193419237303490
solve 2 ^x = 3 mod ( 26! + 4547 )
time = 3,174 ms.
254381984217288129136077800
solve 2 ^x = 3 mod ( 27! + -3733 )
time = 4,938 ms.
3730338382958842097043817720
solve 2 ^x = 3 mod ( 28! + 467 )
time = 7,520 ms.
132445085062873247077525860730
solve 2 ^x = 3 mod ( 29! + 1907 )
time = 11,773 ms.
3316651098589157239153182010304
solve 7 ^x = 3 mod ( 30! + 2039 )
time = 18,660 ms.
11943350906050307282073479589310
solve 7 ^x = 3 mod ( 31! + 1439 )
time = 32,703 ms.
6450897861060199297582162172322044
solve 2 ^x = 3 mod ( 32! + 6299 )
time = 48,325 ms.
125540980439799348727923435117232472
solve 5 ^x = 3 mod ( 33! + 887 )
time = 1min, 13,715 ms.
3867450856284778474038918304720693702
solve 5 ^x = 3 mod ( 34! + -2257 )
time = 2min, 5,319 ms.
175290720774942292904267113460748927014
solve 2 ^x = 3 mod ( 35! + -2341 )
time = 3min, 37,686 ms.
4689200263533716028058740132428049157142
solve 2 ^x = 3 mod ( 36! + -7933 )
time = 5min, 50,771 ms.
145140671181136125708192116133536058851206
solve 5 ^x = 3 mod ( 37! + 3863 )
time = 9min, 19,401 ms.
8545113068695216324695918479277865414411292
solve 5 ^x = 3 mod ( 38! + 6047 )
time = 12min, 48,589 ms.
182173888266139400598807928416669349985794766
solve 5 ^x = 3 mod ( 39! + 6407 )
time = 22min, 57,653 ms.
17036573454363009570342268599920774643716935352
solve 2 ^x = 3 mod ( 40! + 5507 )
time = 48min, 47,534 ms.
532602059903594915777537198714051569908432708876
solve 2 ^x = 3 mod ( 41! + -13093 )
time = 55min, 53,333 ms.
33325464953776748204273172974482357193250898214416
solve 5 ^x = 3 mod ( 42! + -14257 )
time = 1h, 54min, 13,395 ms.
489905972451093695458117936954866974044520256129456
? allocatemem
*** Warning: new stack size = 1024000000 (976.563 Mbytes).
? allocatemem
*** Warning: new stack size = 2048000000 (1953.125 Mbytes).
? allocatemem
*** Warning: new stack size = 4096000000 (3906.250 Mbytes).
solve 2 ^x = 3 mod ( 43 ! + 5507 )
time = 7h, 20min, 58,212 ms.
7433559102473584290093588909528835502254627734052098
43!+5507 is 176 bits. A similar sized factorization problem Pari/GP can solve in about 2 seconds with MPQS. Discrete logarithm in Zp and factorization are currently believed to have approximately the same computational complexity for the same size problem, so znlog has some catching up to do.
? m=43!+5507;
? factorint(precprime(sqrt(m))*nextprime(sqrt(m)))
time = 2,273 ms.
[245795164849461258960674059 1]
[245795164849461258960674197 1]
Finally, just for fun, we present some problems that are impossible when one is limited to resources accessible to normal people:
170! is 1020 bits. The following safe prime took 23,051 ms (23 seconds) to find. There is some evidence (leaked Snowden documents) that large governments can solve this.
solve 5 ^x = 3 mod ( 170 ! + 453143 )
300! is 2042 bits. The following safe prime took 3min, 45,318 ms to find.
solve 2 ^x = 3 mod ( 300 ! + 866843 )
421! is 3069 bits. The following safe prime took 1h, 49min, 41,239 ms to find.
solve 2 ^x = 3 mod ( 421 ! + -8945581 )
No comments :
Post a Comment