Skip to content

Instantly share code, notes, and snippets.

Created March 14, 2016 00:14
Show Gist options
  • Save elliptic-shiho/98bb452dc14e8c40e403 to your computer and use it in GitHub Desktop.
Save elliptic-shiho/98bb452dc14e8c40e403 to your computer and use it in GitHub Desktop.
0CTF 2016 Crypto 2pt: RSA? Writeup
from scryptos import *
p1 = 32581479300404876772405716877547
p2 = 27038194053540661979045656526063
p3 = 26440615366395242196516853423447
n = p1*p2*p3
e = 3
c = int(open("flag.enc", "rb").read().encode("hex"), 16)
# from User's Guide to PARI/GP, nth_root function
sqrtnall = 'sqrtnall(x,n)={my(V,r,z,r2);r=sqrtn(x,n,&z);if(!z,error("Impossible case in sqrtn"));if(type(x)=="t_INTMOD"||type(x)=="t_PADIC",r2 = r*z;n=1;while(r2!=r,r2*=z;n++));V=vector(n);V[1]=r;for(i=2,n,V[i]=V[i-1]*z);V}'
c1 = eval(parigp([sqrtnall, "Vec(liftall(sqrtnall(Mod(%d, %d), 3)))" % (c, p1)]))
c2 = eval(parigp([sqrtnall, "Vec(liftall(sqrtnall(Mod(%d, %d), 3)))" % (c, p2)]))
c3 = eval(parigp([sqrtnall, "Vec(liftall(sqrtnall(Mod(%d, %d), 3)))" % (c, p3)]))
c1 = [6149264605288583791069539134541, 13404203109409336045283549715377, 13028011585706956936052628027629]
c2 = [19616973567618515464515107624812]
c3 = [13374868592866626517389128266735, 7379361747422713811654086477766, 5686385026105901867473638678946]
for x in c1:
for y in c2:
for z in c3:
crt = chinese_remainder_theorem([(x, p1), (y, p2), (z, p3)])
d = hex(crt, 2)[2:].decode("hex")
if "0ctf" in d:
print d[d.find("0ctf"):].strip()
Copy link

Given public key has 314-bit RSA modulus. I tried factor, and I got 3 primes.
trying calculate e^(-1) mod phi(N) .... OMG! I can't calculate e^(-1) mod phi(N), because gcd(e, phi(N)) != 1 !

Umm... ah, e = 3, this is very short. I can calculate modular e-th root using Chinese Reminders Theorem!

Mon Mar 14 09:14:36 JST 2016 ~/ctf/0ctf-2016/crypto2 Battery 0: Full, 100%
> python 

Flag: 0ctf{HahA!Thi5_1s_n0T_rSa~}

Copy link

I had read your write-up, but I still can't understand.
Could I ask for some further explanation?
Like this line
c1 = eval(parigp([sqrtnall, "Vec(liftall(sqrtnall(Mod(%d, %d), 3)))" % (c, p1)]))
Is it something like Quadratic_residue, but 3rd order?
Really want to know the theorem behind it.
Thanks a lot.

Copy link

elliptic-shiho commented Mar 18, 2016

@bananaappletw: hello, thanks to reading.
well, this chall is "calculate cubic residue challenge". that line mean \sqrt[3]{c} \mod p1.
because e equals to 3, \sqrt[e]{m^e} \mod p1 = \sqrt[3]{c} \mod p1 .

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment