20150919: EKOPARTY PRE-CTF 2015 - Crypto - RSA-2070 - writeup

tags: netsec, ctf, ekoparty, crypto, 2015, rsa-2070

The task is obvious, and pretty straightforward:

just simply recover the private key and (then use it to decrypt) the flag
there's *even* a hint given to "check padding" [ref:Optimal Asymmetric Encryption Padding (OAEP)]!

contents of provided crypto100.zip:

flag.enc (SHA256: 24fb435930448305d04ceb39a19eee7e922645b5e8f80ab5b5ec97993e9e3e57)


		CQGd9sC/h9lnLpua50/071knSsP4N8WdmRsjoNIdfclrBhMjp7NoM5xy2SlNLLC2

		yh7wbRw08nwjo6UF4tmGKKfcjPcb4l4bFa5uvyMY1nJBvmqQylDbiCnsODjhpB1B

		JfdpU1LUKtwsCxbc7fPL/zzUdWgO+of/R9WmM+QOBPagTANbJo0mpDYxvNKRjvac

		9Bw4CQTTh87moqsNRSE/Ik5tV2pkFRZfQxAZWuVePsHp0RXVitHwvKzwmN9vMqGm

		57Wb2Sto64db4gLJDh9GROQN+EQh3yLoSS8NNtBrZCDddzfKHa8wv6zN/5znvBst

		sDBkGyi88NzQxw9kOGjCWtwpRw==

public.key (SHA256: 206bd413f6e7a860b4b25b3fc0addd9472cd29df26ae4c0047f4d6fbcc49ea3b)

RSA public-key cryptosystem 101

modulus n = prime p x prime q (=0x25b...e53 here)
exponent e (=65537=0x10001 here)
s.t. 1 < e < φ(n) = (p − 1)(q − 1), e & φ(n) are coprime, where φ is Euler's totient function
e * d = 1 mod φ(n) (=(p − 1)(q − 1))
pubkey contains (n, e)
privkey contains (n, d)
encrypt: pow(plaintext as int, e, n) = ciphertext
decrypt: pow(ciphertext as int, d, n) = plaintext

retrieve modulus

cat public.key | grep -v -- ----- | tr -d '\n' | base64 -d | openssl asn1parse -inform DER -strparse 19
openssl rsa -pubin -inform PEM -in public.key -text -noout -modulus

modulus n = 0x25b18bf5f389097d17237866bb51cff8de922453749ebc403b0995c97c0e386d46c161cadff77c69860dae4791c214cf8487aaaa9f26e920a977834906038aefb5c30827dfcf3fc9e9769544f94e07cdfe0872039a3a6262116678b261fb2d6b9d32539e92a153b3675629bab3942e7d35e30f7eef5abf1c50d797d0cc88e1bdccfd1a12ea6f7ef75c3727dbdf2e780f3428ae8f7a4fb7a89f184a365032b153f8425e845750eb2b7abc02dc15ce0207507aa950863bb8480a78028dd62979944d6c633fafa103e4db28ce87f5a0c6ed4a2f2664427f565c7781ab6191456d971c7ffa395272374cec0155e5f91189db742e4c28b03a0fa11cffb03173d2a4cce6ae53

modulus n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443

query online tool @ http://factordb.com/index.php?query=${modulus}

prime p = 3133337

prime q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

python rsatool.py -p "${p}" -q "${q}" -o private.pem
private.pem

one-liner: cat flag.enc | base64 -d | openssl rsautl -inkey private.pem -decrypt -oaep

#!/usr/bin/env python
#-*- coding: utf-8 -*-

import os
import sys
import codecs

sys.stdout = codecs.getwriter("utf-8")(sys.stdout)
sys.stderr = codecs.getwriter("utf-8")(sys.stderr)

def decrypt_RSA(privkey, encoded):
	from Crypto.PublicKey import RSA
	from Crypto.Cipher import PKCS1_OAEP
	from base64 import b64decode

	assert os.path.isfile(privkey)
	assert os.path.isfile(encoded)

	with codecs.open(encoded, "r", "utf-8") as f:
		flag = f.read().strip()
		with codecs.open(privkey, "r", "utf-8") as f:
			key = f.read().strip()
			rsakey = RSA.importKey(key)
			rsakey = PKCS1_OAEP.new(rsakey)
			decrypted = rsakey.decrypt(b64decode(flag))
			return decrypted
	return None

if __name__ == "__main__":
	print decrypt_RSA("private.pem", "flag.enc")

flag: EKO{classic_rsa_challenge_is_boring_but_necessary}

--- FIN ---