# PlaidCTF - strength - Crypto 110 Point Challenge

## April 24, 2015

It’s my lucky day, two RSA challenges back to back and this one is worth some nice points.

Strength Crypto (110 pts) Strength in Difference We’ve captured the flag encrypted several times… do you think you can recover it

Along with this clue we had a file containing again a list of long numbers with a header listing them as “N : e : c” format. So again yeah, RSA public keys along with corresponding ciphertext. The clue essentially tells us that all of the ciphertexts should be the same.

`````` {N : e : c}
``````

This time we note a couple of things. Firstly the exponents are a much more reasonable size so we won’t use Wiener’s attack. Secondly all of the modulii are the same. Third, the exponents are all different.

So here, we want to use a common modulus attack. This attack works when the same message is sent multiple times with the same modulus (n) and different public exponents (e). If we can find two exponents which have no common factors (i.e. with a gcd == 1) then we can use simple math to recover the plaintext. The attack works like this.

1. Firstly, iterate through our list of exponents and examine each exponent pair (call them e, and f) for common factors
2. If no common factors are found, if gcd(e, f) == 1, then calculate r and s in the equation:
• er + fs = 1
3. Calculate the plain text using the equation
• (Me mod n)rx (Mf mod n)s = Mer+fs mod n = M mod n

To implement this we found someone else had already done this previously for VolgaCTF 2013. You can read their writeup here.

`````` #!/usr/bin/python
import sys
sys.setrecursionlimit(5000)
# math code from http://h34dump.com/2013/05/volgactf-quals-2013-crypto-200/
def gcd(a, b):
if a == 0:
x, y = 0, 1;
return (b, x, y);
tup = gcd(b % a, a)
d = tup
x1 = tup
y1 = tup
x = y1 - (b / a) * x1
y = x1
return (d, x, y)
#solve the Diophantine equation a*x0 + b*y0 = c
def find_any_solution(a, b, c):
tup = gcd(abs(a), abs(b))
g = tup
x0 = tup
y0 = tup
if c % g != 0:
return (False, x0, y0)
x0 *= c / g
y0 *= c / g
if a < 0:
x0 *= -1
if b < 0:
y0 *= -1
return (True, x0, y0)
# read all the rsa stuff into a buffer
f = open('captured_827a1815859149337d928a8a2c88f89f','rb')
f.close()
rsatrunk = rsastuff.splitlines()
modulii = []
exponents = []
ciphers = []
for junk in rsatrunk:
gear = junk.split(":")
gear = gear.replace("{","")
gear = gear.lstrip()
gear = gear.replace("}","")
if "N" in gear:   # handle the header
continue
modulii.append(long(gear,16))
exponents.append(long(gear,16))
ciphers.append(long(gear,16))
print "[+] Performing common modulus attack..."
for a in exponents:
for b in exponents:
if a <> b:
c1 = ciphers[exponents.index(a)]
c2 = ciphers[exponents.index(b)]
n = modulii[exponents.index(a)]
(x, a1, a2) = find_any_solution(a, b, 1)
if a1 < 0:
(x, c1, y) = find_any_solution(c1, n, 1)#get inverse element
a1 = -a1
if a2 < 0:
(x, c2, y) = find_any_solution(c2, n, 1)
a2 = -a2
m = (pow(c1, a1, n) * pow(c2, a2, n)) % n
flag = ("%0512x" %m).decode("hex")
if "flag" in flag:
print "[+] Flag: " + flag
quit()
``````

When we run the code we get the flag

`````` root@mankrik:~/plaid/strength# ./strpwn.py
[+] Performing common modulus attack...
[+] Flag: flag_Strength_Lies_In_Differences
``````

### RITSEC CTF 2018: Cictrohash

I didn't plan to play this CTF but when I saw this challenge I was a bit hooked. So I ended up competing in it.> See the attached PDF for...… Continue reading

#### Square CTF 2018: Dot-n-dash

Published on November 15, 2018

#### Riscure RHme2: FridgeJIT - Reverse Engineering Challenge

Published on February 28, 2017