HackTheVote Qual 2016: The Best RSA

 November 07, 2016   TalkyBird

The Best RSA

250 points (Crypto)

At his last rally, Trump made an interesting statement:

I know RSA, I have the best RSA The more bits I have, the more secure my cyber, and my modulus is YUUUUUUUUUUUUUGE We don’t believe his cyber is as secure as he says it is. See if you can break it for us

best_rsa

author’s irc nick: krx

Overview

The given text file contains 3 number: the public exponent e (65537), the modulus n (about 500K bits) and the cipher text c (about 500K bits). The challenge is to factorize that “YUUUUUUUUUUUUUGE” modulus. Let’s look at its very last digits:

n = 6423578….8671875

It ends with the digit 5, so it is divisible by 5! We did a quick check and found out that it is also divisible by 3, 7, 11, 13 … Then we tried to factorize it into several first prime numbers and luckily, we succeeded with a very small effort :)

Finding the private exponent d

By factorizing the modulus n into primes p1, p2, p3 … we could use the Euler’s totient function and the public exponent e to calculate the private exponent d:

d = inv(e) (mod phi(N))

where phi is the Euler’s totient function.

Decrypting the cipher text

This seems to be the easiest part, but it took us several hours to perform the calculation to decrypt the given cipher text:

plain_text = ce (mod n)

Here’s our script to factorize n, decrypt c and save the plaintext to a given file. The result is actually a gif file:

flag

The flag

flag{s4ved_by_CH1N4_0nc3_aga1n}

HackTheVote Qual 2016: Trump Trump
HackTheVote Qual 2016: Trump Trump  07/11/2016  TalkyBird
EKOPARTY Qual 2016: The Fake Satoshi
EKOPARTY Qual 2016: The Fake Satoshi  01/11/2016  TalkyBird
WriteHat GrandPrix Qual: Hue
WriteHat GrandPrix Qual: Hue  02/11/2015  TalkyBird