HITCON CTF 2015 Quals rsabin write-up

rsabin (Crypto 314)

author: 193s (fuzzi3)

Python script rsabin.py and an encrypted flag was given.
The modulo, N was 314-bit, so first of all I started factoring N using yafu.
It took over 70 minutes…
p = 164184701914508585475304431352949988726937945291
q = 123722643358410276082662590855480232574295213977

Looks good, there we go!

rsabin = rsa + rabin

It seems like you just need to calculate m = c^d (mod N) where private key, d = mod_inv(e, φ(N)), but it won’t work: In this case, mod_inv(e, φ(N)) can’t be calculated! Yes, e, RSA’s public exponent must be chosen as co-prime to φ(N).

e = 31415926535897932384 = 2^5 * 563 * 15647 * 93967 * 1186001

φ(N) = (p-1)(q-1) = 2^4 * 3^2 * 5 * 13 * 3769 * 27077 * 17846641 * 83901947 * 159936353 * 310427287 * 95195293927205442569 * 3004887825587533352438332710071

The challenge title rsabin reminded me of rsa and rabin!
The encryption algorithm for rabin cipher (in case k=0) is as follows:
c = m^2 mod N
I was certain that I can calculate m^(e/2) mod N from m^e mod N when e is an even number.

So, what I need to do is:

  • apply this method 5 times, then I get c' = m^e' mod N where e’ = e/32 (satisfies gcd(e', φ(N)) = 1)
  • decrypt m with normal RSA:
    d' = mod_inv(e', φ(N)), m = c'^d' mod N.

Note that decryption algorithm for rabin cipher returns 4 numbers (m1, m2, m3, m4), and the right plaintext is one of them (there is no way to tell which is the correct one). Because of this, there are 4**5=1024 possible ways of c'.

bruteforcing missing info

I calculated m by using above method for 1024 possible combinations (actually only 16 unique values satisfied m'^e = c), but none of them looked like a flag.

rsabin.py:

1
2
flag = open('flag').read().strip()
assert len(flag) == 50

What?! FLAG is 400-bits length but N is 314-bits?
ok, that means that some upper bits of the flag are missing. (now I have m = FLAG mod N, so just need to know i satisfies FLAG = iN+m)
( I contacted the admin and made sure that the flag is not in the following format: \x00\x00\x00...\x00hitcon{....} )

We know that the flag starts with hitcon{, followed by ascii-printable characters, and ends with }, so I tried to bruteforce i (satisfies FLAG = iN+m) to find the flag matches ^hitcon{[:print:]+}$ for each m.

I wrote a little script, and after 20 minutes, my script showed me the flag!

flag: hitcon{Congratz~~! Let's eat an apple pi <3.14159}

solver: https://gist.github.com/193s/c1391481a1977dcb1570