PicoCTF 2014 Write-ups

RSA - 80 (Cryptography)

Writeup by Oksisane

Created: 2014-11-07 19:13:48

Problem

A Daedalus Corp spy sent an RSA-encrypted message. We got their key data, but we're not very good at math. Can you decrypt it? Here's the data. Note that the flag is not a number but a number decoded as ASCII text.

Hint

This is just plain old RSA decryption.

Overview

Decrypt RSA given a public/private key and ciphertext.

Details

RSA is a extremely popular cryptosystems which relies on Modular arithmetic for encryption and decryption.

How does RSA work?

One of the reasons RSA is so popular is the simplicity of the cryptosystem. Here are the basic steps of RSA Encryption and Decryption.

1. Choose two (usually large) primes, p and q
2. Compute a value N = p*q, commonly reffered to as the modulus
3. Compute phi(N) = (p-1)*(q-1)
4. Choose a "public exponent value", denoted e. Typically this is 3 or 65537.
5. Compute d, the "private exponent value" which is the multiplicitve inverse of e mod(phi(N))
6. To encrypt a message m, compute m^e mod (N)
7. To decrypt a ciphertext c, compute c^d mod (N)

Opening the key_data.txt file we can see that the d and N values have already been provided for us, along with the ciphertext in ciphertext.txt. Great! All we have to do now is compute

Here is an example of this in Python, using the pow function.

c = 0x58ae101736022f486216e290d39e839e7d02a124f725865ed1b5eea7144a4c40828bd4d14dcea967561477a516ce338f293ca86efc72a272c332c5468ef43ed5d8062152aae9484a50051d71943cf4c3249d8c4b2f6c39680cc75e58125359edd2544e89f54d2e5cbed06bb3ed61e5ca7643ebb7fa04638aa0a0f23955e5b5d9
pow(c,d,N)
6861258080156838161702842331923358676171560876407473046529829839343656597465212914039681453600936115970901835821496646686989354106193309238635902806952707316468225954530890939348472370864299291305467697683712618633711800447421650242202732L


The last step in solving this question is converting the resulting number to a readable form. For this we again turn to Python where we can convert this number using the function below (credit to this blog)

def int2Text(number, size):
text = "".join([chr((number >> j) & 0xff)
for j in reversed(range(0, size << 3, 8))])
return text.lstrip("\x00")


Which gives us Congratulations on decrypting an RSA message! Your flag is modular_arithmetics_not_so_bad_after_all.

For further information on RSA, here is a great resource.

Flag

modular_arithmetics_not_so_bad_after_all