# Backdoor CTF 2015: Rsanne
**Category:** Crypto**Points:** 350**Description:** 
> The flag is encrypted using a system that makes use of prime factorization of large numbers.> > Decrypt the flag from [this](challenge/RSANNE.tar.gz). > > If you pwned RSALOT, you should have a fun time solving this one.
## Write-up
The challenge consists of an RSA public key and an RSA-encrypted flag file. We started by inspecting the RSA public key:
>```bash>$ python rsainspect.py id_rsa.pub> [+]n: [0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdfffffffffffffffffff80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001L] (4485 bits)> [+]e: [0x10001L] (17 bits)>```
It is immediately obvious the public modulus is highly abnormal, both in size (4485 bits) and composition (the large amount of 1 bits followed by the large amount of zeros and a single trailing 1). The binary representation of the public modulus looks as follows:
> 0b11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Seeing as the 2281 higher-order bits are all 1s followed by 2203 lower-order bits (consisting of all-zeros and a single trailing 1) this means the public modulus can be expressed as:
> (2^2281 - 1)(2^2203 - 1)
Which is effectively its factorization. Using this we can [trivially](solution/rsanne.py) obtain the private key and decrypt the ciphertext:
>```python>#!/usr/bin/python>#># Backdoor CTF 2015># RSANNE (CRYPTO/350) Exploit>#># @a: Smoke Leet Everyday># @u: https://github.com/smokeleeteveryday>#>from Crypto.PublicKey import RSA>from Crypto.Cipher import PKCS1_OAEP>from base64 import b64decode>># GCD (times sign of b if b is nonzero, times sign of a if b is zero)>def gcd(a,b):>	while b != 0:>		a,b = b, a % b>	return a>># Extended Greatest Common Divisor>def egcd(a, b):>	if (a == 0):>		return (b, 0, 1)>	else:>		g, y, x = egcd(b % a, a)>		return (g, x - (b // a) * y, y)>># Modular multiplicative inverse>def modInv(a, m):>	g, x, y = egcd(a, m)>	if (g != 1):>		raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m))>	else:>		return x % m>># Decrypt ciphertext using private key (PKCS1 OAEP format)>def do_decrypt(rsakey, ciphertext):>	rsakey = PKCS1_OAEP.new(rsakey) >	plaintext = rsakey.decrypt(b64decode(ciphertext)) >	return plaintext>># Calculate private exponent from n, e, p, q>def getPrivate(n, e, p, q):>	d = modInv(e, (p-1)*(q-1))>	return RSA.construct((n, e, d, p, q, ))>># Factors of n expressed as (2^2281 - 1)(2^2203 - 1)>p = (pow(2, 2281)-1)>q = (pow(2, 2203)-1)>>ciphertext = open("flag.enc", 'rb').read()>pubKey = RSA.importKey(open("id_rsa.pub", 'rb').read())>privKey = getPrivate(pubKey.n, pubKey.e, p, q)>print do_decrypt(privKey, ciphertext)>```
Which gives us:
>```bash>$ python rsanne.py>{flag removed upon request of backdoorCTF admins ;)}>```