Beginner's Crypto writeup

BeginnersCrypto.md

Beginner's Crypto

Given val such that flag * 2^{10000} mod 10^{175} == val.

From definition of modulus, we get flag * 2^{10000} - k * 10^{175} == val.

Divide by 2^{175}, flag * 2^{10000-175} - k * 5^{175} == val / 2^{175}

Then we get modulo 5^{175}, flag * 2^{10000-175} == val / 2^{175} (mod 5^{175})

and multiply the inverse. flag == (val / 2^{175}) * inv(2^{10000-175}) (mod 5^{175})

solve.py

val = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576

val >>= 175

n = pow(5,175)
phi = n-n//5
ed = 1<<(10000-175)
inv = pow(ed,phi-1,n)
ans = val * inv % pow(5,175)

hx = hex(ans)[2:]
if len(hx) % 2 == 1:
    hx = '0' + hx
print(hx)
print(bytes.fromhex(hx))