Rating:
# Backdoor CTF 2015: Rsalot
**Category:** Crypto
**Points:** 250
**Description:**
> The flag is encrypted using a system that makes use of prime factorization of large numbers.
>
> Decrypt the flag from [this](challenge/RSALOT.tar.gz).
## Write-up
The challenge consists of a collection of 100 RSA public keys and an RSA-encrypted flag file. Given the large number of RSA public keys we immediately suspected at least a single pair would have a moduli n with a common prime factor. This poses a problem because, given two RSA public keys (n1, e1), (n2, e2) where n1 = p\*q1 and n2 = p\*q2, we can trivially factor n1 and n2 by calculating the greatest common divisor of n1 and n2: gcd(n1, n2) = p and hence obtain the corresponding private keys [[1](https://factorable.net/faq.html)], [[2](http://www.hyperelliptic.org/tanja/vortraege/facthacks-RSA.pdf)].
We cooked up a [quick & dirty script](solution/rsalot.py) which checked all public key pairs for a common prime factor and if it found one (or more) it would try to decrypt to ciphertext with it:
>```python
>#!/usr/bin/python
>#
># Backdoor CTF 2015
># RSALOT (CRYPTO/250) Exploit
>#
># @a: Smoke Leet Everyday
># @u: https://github.com/smokeleeteveryday
>#
>
>import os
>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
>
># 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, ))
>
># Get prime factors of n1 if n1 and n2 have common prime factor
>def commonPrimeFactor(n1, n2):
> p = gcd(n1, n2)
> if((p != 1) and (p != n1) and (p != n2)):
> q = n1 / p
> return (p, q)
> else:
> return None
>
># Import all keys
>def getKeys():
> keys = {}
> privKeys = []
>
> filenames = next(os.walk("."))[2]
> for filename in filenames:
> if(filename[-3:] == "pem"):
> f = open(filename, 'rb')
> externKey = f.read()
> f.close()
> keys[int(filename[:-4])] = RSA.importKey(externKey)
>
> # Check for common prime factors
> for index1 in keys:
> key1 = keys[index1]
>
> for index2 in keys:
> if(index1 == index2):
> continue
>
> key2 = keys[index2]
> r = commonPrimeFactor(key1.n, key2.n)
> if(r != None):
> print "[+]Got private key from common modulus between (%d) and (%d)" % (index1, index2)
> privKeys.append(getPrivate(key1.n, key1.e, r[0], r[1]))
>
> return privKeys
>
># 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
>
># Get all private keys
>privKeys = getKeys()
>ciphertext = open("flag.enc", 'rb').read()
>
># Try all potential private keys we obtain
>for privKey in privKeys:
> try:
> print do_decrypt(privKey, ciphertext)
> print ""
> except:
> pass
>```
Which gave the following result:
>```bash
>$ python rsalot.py
>[+]Got private key from common modulus between (64) and (87)
>[+]Got private key from common modulus between (87) and (64)
>{flag removed upon request of backdoorCTF admins ;)}
>```
