# PicoCTF 2014 Write-ups

## RSA Mistakes - 200 (Cryptography)

#### Writeup by ZIceZ

Created: 2014-11-07 23:22:41

### Problem

Daedalus Corp seems to have had a very weird way of broadcasting some secret data. We managed to find the server code that broadcasted it, and one of our routers caught some of their traffic - can you find the secret data? We think someone may have requested the secret using someone else's user id by accident, but we're not sure.

### Hint

Two of these messages use the same public key, and are related in a useful way.

### Details

The data recovered from the .pcap file contains a series of public keys and messages, and a python program. The python program reviews that the original message was transformed based on the User ID before being encrypted and broadcast. The transformation is:

From the other file that contains the series of public key, user ID, and message, it turns out that an employee of Daedalus Corp requested the secret message twice but on the second time he accidentally used another person ID.

His unfortunate accident gives us two messages that are related to each other, and are encrypted by the same public key.

Msg 2 0x81579ec88d73deaf602426946939f0339fed44be1b318305e1ab8d4d77a8e1dd7c67ea9cbac059ef06dd7bb91648314924d65165ec66065f4af96f7b4ce53f8edac10775e0d82660aa98ca62125699f7809dac8cf1fc8d44a09cc44f0d04ee318fb0015e5d7dcd7a23f6a5d3b1dbbdf8aab207245edf079d71c6ef5b3fc04416L

OK, that's the set up. Now to the exploit. The Franklin-Reiter Related Message Attack uses known fixed relationship between two messages to exploit

We also have:

Then let set:

So when $x = M_2$, g(x) and h(x) equal 0. Thus, $x -M_2$ is a factor to the two equation above. Therefore the GCD of the two equations above should return the factor $x-M_2$, and then $M_2$ and $M_1$ can be found.

What we have then is two messages related to each other by some coefficient:

Solve for a and b: $a = 37/52$ $b = -555$ Since fractions are not permissible in modulus, we use the multiplicative inverse instead to represent $a$. Also, don't forget that this only solves for the transformed message. Reverse the transformation before decoding.

My code in Sage:

def n2s(n):
s = hex(n)[2:-1]
if len(s) % 2 != 0:
s = '0' + s
return s.decode('hex')
c1 = 0x81579ec88d73deaf602426946939f0339fed44be1b318305e1ab8d4d77a8e1dd7c67ea9cbac059ef06dd7bb91648314924d65165ec66065f4af96f7b4ce53f8edac10775e0d82660aa98ca62125699f7809dac8cf1fc8d44a09cc44f0d04ee318fb0015e5d7dcd7a23f6a5d3b1dbbdf8aab207245edf079d71c6ef5b3fc04416L
e = 3
a1 = 37/52
b1 = -555
actuala = inverse_mod(52, n)
x = PolynomialRing(ZZ.quo(n*ZZ), 'x').gen()
f=(x*actuala*37+b1)^e-c1
g=x^e-c2
a = f
b = g
messagemess = 0
run = True
while run:
r = a % b
if r == 0:
print 'FOUND %s' % rp
c = rp.coeffs()
messagemess = -pow(c, -1, n) * c
run = False
rp = r
a, b = b, r
i += 1
realmessage = messagemess*actuala-b1
n2s(int(realmessage))


Which reveals the message: 'Wow! Your flag is: did_you_know_you_can_sometimes_gcd_outside_a_euclidean_domaipi'

### Flag

did_you_know_you_can_sometimes_gcd_outside_a_euclidean_domaipi