# 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:

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}`