- Any computer with Python 3.

- 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}(modx)p

## Problem 1: Find a Collision

We'll find integers (,a), and (b,A) such that:BThis problem is easier than the DLP because of the birthday paradox.g^{a}=x^{b}g^{A}(modx^{B})pWe'll use an algorithm called the Tortoise and the Hare to solve it.

Where

(F) =u{ ifgu(h) = 0u

ifu^{2}(h) = 1u

ifxu(h) = 2u

We start with a value ** u_{0}**
and calculate a series of values:

Eventually, we'll hit a value we've seen before, and after that point, further iterations will just loop through the same series of values, as shown below.=u_{1}(F)u_{0}

=u_{2}(F)u_{1}

=u_{3}(F) etc.u_{2}

This diagram looks like the greek letter rho, which is why this method is called the Rho method.

The tortoise-and-hare algorithm is a way to find the loop without needing to maintain a table of old values in memory.

We generate two sets of values,
the ** u** series (the tortoise)
and
the

The idea is that they both race down the track shown in the figure above, with one moving faster than the other. When they hit the loop, the tortoise will catch up to the hare and the two values will be equal.=u_{1}(F)u_{0}=v_{1}(F(F))v_{0}

=u_{2}(F)u_{1}=v_{2}(F(F))v_{1}

=u_{3}(F)u_{2}=v_{3}(F(F)) etc.v_{2}

When that happens, they will each contain a different
number of factors of ** g** and

## Algorithm for Tortoise and Hare

1. We'll use this hash function:2. Define the function

import hashlib def h(u): i = (u + 64) % 1256991 b = i.to_bytes(3, byteorder="big") m = hashlib.md5(b).hexdigest() result = int(m, 16) % 3 return result(F) that keeps track ofu(the number ofafactors) andg(the number ofbfactors), as shown below. The reasonxandaare calculated (modb- 1) is explained in the Problem 2 section below.p3. Start out with

(F,u,a) =b{ ifgu(h) = 0; add 1 tou(moda- 1)p

ifu^{2}(h) = 1; doubleuanda(modb- 1)p

ifxu(h) = 2; add 1 tou(modb- 1)panduboth equal to 1.v4. Update values:

Settou(F)u

Settov(F(F))v5. If

=u, we're done. The result is (v,a) for the Tortoise and (b,A) for the Hare.B

Otherwise go to step 4, unless there have been too many attempts and we give up.

## C 507.1: Race (15 pts)

For these values:Run the race. The flag is the final value of

= 47p= 7g= 5x.a

## Problem 2: Find

After running the Tortoise and Hare race, we havefrom the CollisionyIn the equation above, replacingg^{a}=x^{b}g^{A}(modx^{B})pwithxgives:g^{y}=g^{a + yb}(modg^{A + yB})pFermat's little theoremtells us, for any integer:cTherefore we can remove factors of (c^{(p - 1)}= 1 (mod)p- 1) from the exponents:pg^{(a + bv) (mod (p - 1))}=g^{(A + Bv) (mod (p - 1))}(mod)pRearranging terms:=a + bv(modA + yB- 1)pLet(=b - B)y((modA - a)- 1)pbe the greatest common denominator ofG(,b - B)(, and (A - a)- 1).pThen each of those terms can be written as

times another integer, indicated by prime marks, like this:GSince every term is an integral multiple of(=b' - B')Gy(modG(A' - a'))G p', we can just rescale this statement (see gray box below), measuring every term in units ofGand make the ring smaller by a factor ofG, like this:GSo:(=a' - A')y((modB' - b'))p'This formula gives us=y((modA' - a') (b' - B')^{-1})p'(mody), which we'll callp', so any of these values might be the realy_{0}:yWe don't know=y+y_{0}kp'so we'll have to try many values to find a solution.k

## Scaling

Consider this equation:900 = 100 (mod 800)If all the quantities in this equation are divisible by 100, we can renumber the ring in units of 100 without losing any information, since the numbers 1-99, 101-199, etc. are never used:9 = 1 (mod 8)This is a situation common in physics, like switching the units of measurement from meters to inches.

## Algorithm for Problem 2: Find

from the Collisiony1. GCD: Find, the greatest common denominator of these three numbers:G2. Calculate

((modb - B)- 1)p((modA - a)- 1)p- 1p(,b' - B')(, andA' - a')by dividing those three numbers byp'.G3. Calculate the modular inverse (

-b')B'^{-1}(mod)p'

Calculate=y_{0}((modA' - a') (b' - B')^{-1})p'4. Loop through values of

= 0, 1, 2, 3, ...k

Calculate=y+y_{0}k. Ifp'=g^{y}, we're done.x

## C 507.2: GCD (10 pts)

Find the GCD of these numbers:The flag is the GCD value.

- 39199007823998693533
- 32254013411746110071
- 56652933174483971459

Hint: usePyCryptodome

## C 507.3: Inverse (5 pts)

Find(moda^{-1}) for these values:p'The flag is the value of

= 5a= 4093082899p'.a^{-1}

## C 507.4: DLP (15 pts)

Given:Find=g^{y}(modx)pfrom these values:yThe flag is the value of

= 777777p= 1971g= 22173x.y

## C 507.5: DLP (10 pts)

Given:Find=g^{y}(modx)pfrom these values:yThe flag is the value of

= 22333555577777p= 197119721973g= 17728870310451x.y

A Quick Tutorial on Pollard's Rho Algorithm

Pollard rho Factorization Method

The Pollard-Rho attack on Diffie Hellman

NCC Group Whitepaper: How to Backdoor Diffie-Hellman

Pollard's rho algorithm for logarithms

Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method

Posted 9-10-20 by Sam Bowne