I am following this Wikipedia page and this tutorial.
gy = x
p = 23
g = 5
for i in range(p):
print(i, pow(g, i, p))
Run this program.
As shown below, the answer is 5.
C 506.1: Brute Force (5 pts)
Find y from these values:There are two solutions. The lower one is the flag.
- p = 13337
- g = 13
- x = 1337
Try running the program and you will see that it can quickly calculate 1 million values, but it will take a long time to try that many.
g y = xWe are looking for y, which could be from 1 to p - 1.
We break x into two pieces using m, which is the square root of p, rounded up to the nearest integer:
y = im + jWhere i and j are both between 0 and m. That is, we take i giant steps and j baby steps.
Therefore, we have:
g im + j = x
g j = x (g -m) iWe make a table of all possible g j values. Then we pick a value for m. Then we try values for j until a match is found in the table of g j values.
This is a time-memory trade-off algorithm.
1. Calculate m = Ceiling(sqrt(p))2. Calculate all the baby steps g j for j from 0 to m and save them in a table
3. Compute g -m
4. Loop through i from 0 to m
5. Look in the table for x (g -m) i. If it's found, y is im + j
6. If it's not found, increment i and go to step 5.
a p = a (mod p)or
a (p - 1) = 1 (mod p)So, setting a to g m:
(g m) (p - 1) = g m * (p - 1) = 1 (mod p)Multiplying both sides by g -m:
g m * (p - 2) = g -m (mod p)
C 506.2: Find m (5 pts)
Find m for this value:The value of m is the flag.
- p = 5915587277
Hint: use the Decimal library.
C 506.3: Find g -m (5 pts)
For these values:Calculate g -m. That's the flag. The value of j is the flag.
- p = 5915587277
- g = 497
C 506.4: Baby Steps (10 pts)
For these values:Create the Baby Steps table. Find the j such that:
- p = 5915587277
- g = 497
g j = 3457701878 (mod p)The value of j is the flag.
C 506.5: Crack DLP (15 pts)
Put all the pieces together and find y for these values:The value of y is the flag.
- p = 5915587277
- g = 497
- x = 5751318998
Hint: use a dictionary
C 506.6: Crack DLP (10 pts)
Put all the pieces together and find y for these values:The value of y is the flag.
- p = 777737777777777
- g = 7777
- x = 719517368978140
This took about 3 minutes on my system.
Posted 9-6-20 by Sam Bowne
Point total corrected 11-11-21
Color updated 6-19-24