# strength

## PLAID CTF Crypto Challenge: 110 pts

## Challenge Description:

"We've captured the flag encrypted several times... do you think you can recover it?"

The challenge presented the user with a set of `{N : e : c}`

. Each set represented a different RSA public key encryption of the same message, the flag.

## Material:

```
- captured public key and cipher text file
```

# Solution:

The solution to this challenege was pretty simple, a.k.a. python brute force works well. :]

(*Python scripts for solution linked at the bottom.*)

```
1) Vulnerability in poorly chosen RSA *exponent e*
2) Find the exponents which are off by *1* so they cancel out
3) You can compute the message from the two cooresponding ciphertexts
```

`C1 = M1^(e) mod(N)`

`C2 = M1^(e+1) mod(N)`

`compute the modular inverse of the two vuln e's => {a,b}`

`C1^(-a)*C2^(b) = M1^(-e)*M1^(e+1) mod(N)`

`modular_inv(C1, N)*C2 = M1^(1) mod(N)`

##### Steps to flag:

- take the gcd of all pairs of exponents provided, if the gcd is '1' they are vulnerable
```
for e1 in e:
for e2 in e:
if 1 == gcd(e1,e2):
print "THE VULN E"
print e1, e2
```

compute `{a,b}`

such that e1*a + e2*b = 1

```
print "a and b such that e1*a + e2*b = 1"
print hex(inverse_mod(e_2,e_1))
print hex(inverse_mod(e_1,e_2))
`
```

calculate the flag

```
p1 = pow(inverse_mod(c_1, N), -a, N)
p2 = pow(c_2, b, N)
```

```
flag = (p1 * p2) % N
print hex(flag)
```

# Flag:

# Scripts:

SOLVER