Skip to content

Instantly share code, notes, and snippets.

@n-ari

n-ari/BeginnersCrypto.md

Last active July 12, 2020 08:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save n-ari/33155680ecf3cf0824a29f3b77a277e6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save n-ari/33155680ecf3cf0824a29f3b77a277e6 to your computer and use it in GitHub Desktop.
Download ZIP
Beginner's Crypto writeup
Raw
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})

Raw
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment