- Any computer with Python 3.

I am following this Wikipedia page and this tutorial.

- On a ring with a prime
modulus
*p* - And a base integer
*g* - We know an integer
*x* - We want to find an integer
such that:*y*

=g^{y}x

= 23*p*= 5*g*= 20*x*

Run this program. As shown below, the answer is 5.

p = 23 g = 5 for i in range(p): print(i, pow(g, i, p))

## C 506.1: Brute Force (5 pts)

Findfrom these values:yThere are two solutions. The lower one is the flag.

= 13337p= 13g= 1337x

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.

We are looking for=g^{y}x

We break ** x** into two pieces
using

Where=y+imj

Therefore, we have:

=g^{im + j}x

We make a table of all possible=g^{j}(x)g^{-m}^{i}

This is a time-memory trade-off algorithm.

1. Calculate= Ceiling(sqrt(m))p2. Calculate all the baby steps

forg^{j}from 0 tojand save them in a tablem3. Compute

g^{-m}4. Loop through

from 0 toim5. Look in the table for

(x)g^{-m}^{i}. If it's found,isy+imj6. If it's not found, increment

and go to step 5.i

or=a^{p}(moda)p

So, setting= 1 (moda^{(p - 1)})p

(Multiplying both sides by)g^{m}=^{(p - 1)}= 1 (modg^{m * (p - 1)})p

=g^{m * (p - 2)}(modg^{-m})p

## C 506.2: Find

Find(5 pts)mfor this value:mThe value of

= 5915587277pis the flag.m

Hint: use the Decimal library.

## C 506.3: Find

For these values:(5 pts)g^{-m}Calculate

= 5915587277p= 497g. That's the flag. The value ofg^{-m}is the flag.j

## C 506.4: Baby Steps (10 pts)

For these values:Create the Baby Steps table. Find the

= 5915587277p= 497gsuch that:jThe value of= 3457701878 (modg^{j})pis the flag.j

## C 506.5: Crack DLP (15 pts)

Put all the pieces together and findfor these values:yThe value of

= 5915587277p= 497g= 5751318998xis the flag.y

Hint: use a dictionary

## C 506.6: Crack DLP (10 pts)

Put all the pieces together and findfor these values:yThe value of

= 777737777777777p= 7777g= 719517368978140xis the flag.y

This took about 3 minutes on my system.

Posted 9-6-20 by Sam Bowne

Point total corrected 11-11-21