Rating:
# 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 ;)}
>```
