A python script and a output file are given. The script uses a password (which is given) that is used by a redacted function. The challenge is to understand what the funcion did and to reverse it.
From the name of the function one can understand that the password is in Polish notation and from the order of the digits (mostly in front) and letters (mostly at the end) that it's a reverse polish notation.
The password therefore is equivalent to c( b(e(a(0,8)),e(7)), b(3,d(c(1,2,a(2,7)))), e(f(a(5,a(5,3)))) ), let's analyze c and his 3 arguments.
The first one returns 0 and sets the random seed to e(7);
The second one is just a number and all the variables to calculate it are given, the problem is that the function d is very slow so we have to substitute it with another called fastd;
d is the A028365 sequence on OEIS wich has a different definition
The third uses the f function wich uses the flag so can't be calculated completely, we can easely compute until that point (a(5,a(5,3))), then compute the output of f from the given output and recover the flag,
to do so we know that when the first argument of c is 0 the other two are xored, so we xor the second argument with the output;
now to reach f we need to reverse e wich is RSA.
To decrypt RSA we need to factor n, how to do so is easy if you see the number in a divverent base:
the number in base 16
0x1702f4d2a98712defc05cb40b72a821479ccb9000a9bd698520082544b652bacfa721041f115da3a3cb8f4211a847706ae4dc9f048c7262a964e337bc47065de1059eccc87c19f662c21f9066805e5f75b3c62305395138d5eb71e9f9966297750ee17ccfcace1386abaf53434b264696744ae990bdebb17a4a56c4edc0cccfcf8da138fcf0c911f434d2d3e0b493b8fa9917f83f41273b4aaf7d631dabb66939f67fcb270e0a7156c7e66338027387e873c225991180fec96ea4fc0f9f88815010e5994d5f35ae21568d5641b00d44876762c392e9853045a5a92eb2354486f80946368f83469a7b37e621906f81f8005b126417fd716bcd79c84610dc093dd7575ebcf3af3d71a869830455d3ad6d68ad2254843320233e01f1cafdc73310f7ffb1deccb4df2fee6150a1a588867c5285c7049bf39e1a631badc81d61dda69e5d2e017235306ad46b0703e88a5c65807737a6a459231f5eb6bd6afd44fb46566c1
in base 17 is
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggegggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggf0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
As for a mersenne prime is easy to brute force the right prime number, in this case p = 17 ** 232 -2.
At the end we can recover the input and the output of f and so the flag.
from Crypto.Util.number import *
# from secret import FLAG
import random
from hashlib import md5
def a(x, y) -> int:
return x ** y
def b(f: int, x: int) -> int: # caller
func = [random.seed, getPrime, isPrime, md5]
if f == 3:
return bytes_to_long(func[f](long_to_bytes(x)).digest())
r = func[f](x)
return int(r) if r else 0
def c(z: int, x: int, y: int) -> int:
if z:
return random.randint(x ** 11, x ** 11 + y)
x = long_to_bytes(x)
y = long_to_bytes(y)
while len(x) < len(y):
x += x
x = x[:len(y)]
return bytes_to_long(xor(x, y))
def d(n):
n = n - 1
temp = 1
for i in range(1, n + 1):
temp *= (2 ** i) - 1
esp = 2 ** ((n ** 2 + n) // 2)
return temp * esp
def e(msg: int) -> int: # rsa
n = 0x1702f4d2a98712defc05cb40b72a821479ccb9000a9bd698520082544b652bacfa721041f115da3a3cb8f4211a847706ae4dc9f048c7262a964e337bc47065de1059eccc87c19f662c21f9066805e5f75b3c62305395138d5eb71e9f9966297750ee17ccfcace1386abaf53434b264696744ae990bdebb17a4a56c4edc0cccfcf8da138fcf0c911f434d2d3e0b493b8fa9917f83f41273b4aaf7d631dabb66939f67fcb270e0a7156c7e66338027387e873c225991180fec96ea4fc0f9f88815010e5994d5f35ae21568d5641b00d44876762c392e9853045a5a92eb2354486f80946368f83469a7b37e621906f81f8005b126417fd716bcd79c84610dc093dd7575ebcf3af3d71a869830455d3ad6d68ad2254843320233e01f1cafdc73310f7ffb1deccb4df2fee6150a1a588867c5285c7049bf39e1a631badc81d61dda69e5d2e017235306ad46b0703e88a5c65807737a6a459231f5eb6bd6afd44fb46566c1
e = 0x10001
return pow(msg, e, n)
def revE(msg: int) -> int: # rsa
n = 0x1702f4d2a98712defc05cb40b72a821479ccb9000a9bd698520082544b652bacfa721041f115da3a3cb8f4211a847706ae4dc9f048c7262a964e337bc47065de1059eccc87c19f662c21f9066805e5f75b3c62305395138d5eb71e9f9966297750ee17ccfcace1386abaf53434b264696744ae990bdebb17a4a56c4edc0cccfcf8da138fcf0c911f434d2d3e0b493b8fa9917f83f41273b4aaf7d631dabb66939f67fcb270e0a7156c7e66338027387e873c225991180fec96ea4fc0f9f88815010e5994d5f35ae21568d5641b00d44876762c392e9853045a5a92eb2354486f80946368f83469a7b37e621906f81f8005b126417fd716bcd79c84610dc093dd7575ebcf3af3d71a869830455d3ad6d68ad2254843320233e01f1cafdc73310f7ffb1deccb4df2fee6150a1a588867c5285c7049bf39e1a631badc81d61dda69e5d2e017235306ad46b0703e88a5c65807737a6a459231f5eb6bd6afd44fb46566c1
p = 2911721007088133262675953106197241703556747554305425259320716892314498939605330257723180761563459946872506915178651543859508747846871417959638013334210124890497567604326390324762618539999256667220682352421111253679877478493941553844107359114872928940037671284003186268154810467080223359
q = n // p
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))
return pow(msg, d, n)
def xor(x, y):
return bytes(a ^ b for a, b in zip(x, y))
def polacco(password: str) -> int:
stack = []
func = {'a': (a, 2), 'b': (b, 2), 'c': (c, 3), 'd': (d, 1), 'e': (e, 1), 'f': (f, 1)}
for t in password:
if t.isdigit():
stack.append(int(t))
else:
args = []
for _ in range(func[t][1]):
args.append(stack.pop())
args.reverse()
tmp = func[t][0](*args)
stack.append(tmp)
return stack.pop()
def solve():
random.seed(e(7))
out = int(
'69699507fd48efde364bab82106f89d23d22e463631a77941cfe29863229a40be8ba9ea548323b183bc37e4d7b151e8b60fac7d657185dfd1b75eebc2701c21bd3901f800145e76b1d48789428c7c3e8f7bc0aa11232ee076262d4f3c9b84b2a43e3da768e2f7622d645fa3bb94e65e64744b977f260ba1fd0956330c3cfc2fbddf350db366c2da5d72f91eb23905bc1b714b66460d726af257ff37d60897b33778d74c9a1e5dbf8c15390a5d65114c738f6812b39ec42afc00a873d866166411f2d4c9a69fce5aca631af87f4a6449282664e2a8ab79f5376486cf0f9fcb226e76b735dda222a024fda883352b8e24fee309f2057c7472a58a8aac886b9a1889e9b1f8d2306b493c4e16f3401a01263828a08e2070b4cdc6dd398bcac17d707847325064d4bf6dcfa9e683cee3c126eb4ad753997ae66792b71f83f835524ad6da5e25b3dabc21e541cd049bc038b7ced304c1012fe67919619c28f593940c5cb9c',
16)
l = long_to_bytes(out)
temp = long_to_bytes(b(3, d(c(1, 2, a(2, 7)))))
# temp = long_to_bytes(160041365501716368448053427917678638214)
while len(temp) < len(l):
temp += temp
temp = temp[:len(l)]
temp = bytes_to_long(xor(temp, l))
temp = revE(temp)
temp2 = a(5, a(5, 3))
print(xor(long_to_bytes(temp), long_to_bytes(temp2)))
solve()