Tadpole corctf 2022 writeups

we were given two files

file 1: tadpole.py

from Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow

p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)

a = randbelow(p)
b = randbelow(p)

def f(s):
    return (a * s + b) % p

print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))

file 2: output.txt

a =  7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b =  16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f(31337) =  52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
f(f(31337)) =  65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949

Understanding tadpole.py

I’ll try understanding the code line by line.

from Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow

bytes_to_long, as its name suggest convert a byte to long.example:

>>> print(bytes_to_long(b'test'))
>>> 1952805748

IsPrime determine if a number is a prime.A prime number is defined as:

• A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words:
• A number that is greater than 1 that only have two factor: 1 and itself. secrets.randbelow(n)
• Return a random int in the range [0, n).

p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)

p is a long got from the the file flag.txt which is the flag. assert isPrime(p) tell us that p is a prime, otherwise an AssertionError will be raised.

a = randbelow(p)
b = randbelow(p)

a,b is a random value below p. I’m not going to check how this function is implemented.

def f(s):
    return (a * s + b) % p

function f is going to take seed s as a parameter. its going to return a times s plus b then modulo by p

print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))

print a,b,f(31337) and f(f(313337)) f(31337) and f(f(31337)) looks interesting.

Solution

note that this is my solution, i don’t know if it is mathematically correct but i got the flag nonetheless.

since we knew the result of f(31337) and f(f(31337)), we can try expand the function f to get a better picture:

• f(31337) = (a * 31337 + b) % p and
• f(f(31337)) = (a * 5292… + b) % p we know from the code p is the flag, so we need to solve for it. simplify (a * 31337 + b), (a * 5292… + b) as k1,k2
• f(31337) = k1 % p and
• f(f(31337)) k2 % p if we subtract k1 and k2 with the result of functions f that we know we will get p multiplied by some random number
• k1 - f(31337) = x1 = r1 * p
• k2 - f(f(31337)) = x2 = r2 * p r1 and r2 are both random and unknown, but we knew that x1 and x2 share p as its factor. we can try to find the greatest common divisor of x1 and x2 to find p, and then use long_to_bytes to print out the flag here is the solution code.

from Crypto.Util.number import *
a = 7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b = 16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f1 =52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
f2 = 65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949
# k = (a * s + b)
k1 = (a * 31337 + b)
k2 = (a * f1 + b)
c1 = k1 - f1
c2 = k2 - f2

def computeGCD(x, y):
    while(y):
        x, y = y, x % y
    return abs(x)
p = computeGCD(c1,c2)
print(long_to_bytes(p))

which output

b’corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm'

thank you for reading.