Outils pour utilisateurs

Outils du site


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

Find the prime numbers - Writeup by toffan

Challenge

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[0] * n[1] - n[2] for n in data ]
 
while len(nbs) > 1:
    nbs.append(gcd(nbs[0], nbs[1]))
    nbs = nbs[2:]
 
print('n = {}'.format(nbs[0]**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)[0]
 
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)[1] % 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