# Pony7 Wiki

### Outils du site

ctf:public:seccon:find-the-prime-numbers

# Find the prime numbers - Writeup by toffan

## Solution

First of all, we need to find n. Each time we are given three numbers c, o and h such as h = c * o mod n². So, with a set set of values large enough, we can affirm that n² = gcd {c * o - h}.

```#/usr/bin/env python3
from fractions import gcd

with open('data.txt', 'r') as f:
data = [ [ int(n) for n in line.split() if n != '+' and n != '=' ] for line in f ]

nbs = [ n * n - n for n in data ]

while len(nbs) > 1:
nbs.append(gcd(nbs, nbs))
nbs = nbs[2:]

print('n = {}'.format(nbs**0.5))```

`n = 2510510339.0`

Now we have n a simple google search gives us that n = 42727 * 58757, so we can decode the messages.

```#!/usr/bin/env python3

def eea(a, b):
'''
Extended Euclid Algorithm
return gcd and Bézout coeffs in (g, u, v)
'''
u, _u = 0, 1
v, _v = 1, 0
g, _g = b, a
while g != 0:
q = _g // g
_g, g = g, _g - q*g
_u, u = u, _u - q*u
_v, v = v, _v - q*v

return (_g, _u, _v)

def gcd(a, b):
'''
Greatest Common Divisor of a and b
'''
return eea(a, b)

def lcm(a, b):
'''
Least Common Multiple of a and b
'''
return a * b // gcd(a, b)

def inv(n, m):
'''
Modular multiplicative inverse of n in Z/mZ
'''
return eea(n, m) % m

def L(u, n):
return (u-1) // n

a = 42727
b = 58757
n = a * b
l = lcm(a - 1, b - 1)
g = n + 1
mu = inv(L(pow(g, l, n*n), n) , n)

data = []
with open('data.txt', 'r') as f:
data = [ [ int(n) for n in line.split() if n != '+' and n != '=' ] for line in f ]

for c, o, h in data:
m = L(pow(c, l, n*n), n) * mu % n
print("m = {}".format(m))```

Each time our algorithm gives us `m = 1510490612` which is the solution.

ctf/public/seccon/find-the-prime-numbers.txt · Dernière modification: 2016/04/09 22:51 par lemarcb

### Outils de la page 