Rating:

# SEC-T CTF 2019 : Trivial RSA

**category** : crypto

**points** : 359

**solves** : 32

## write-up

We are given `n1, n2, (p1 - p2) % (q1 - q2), (q1 - q2) % (p1 - p2), c`, Where

```

n1 = p1 * q1

n2 = p2 * q2

e = 65537

c = pow(m, e, n1)

```

Assume `y1 = (p1 - p2) % (q1 - q2), y2 = (q1 - q2) % (p1 - p2)`

We already know the values of `y1, y2`

There are only two possibilities (don't mind the equal situation):

1. `p1 - p2 < q1 - q2`, then `p1 - p2 = y1, q1 - q2 = y2 + k * y1` for some `k`

2. `p1 - p2 > q1 - q2`, then `p1 - p2 = y1 + k * y2, q1 - q2 = y2` for some `k`

Brute force the value of `k`, then we know the exact value of `p1 - p2` and `q1 - q2`

Assume the exact values are `p1 - p2 = x1, q1 - q2 = x2`

Then we will have 4 equations

```

p1 - p2 = x1

q1 - q2 = x2

p1 * q1 = n1

p2 * q2 = n2

```

After some math calculations, we will get a quadratic equation

```

x2 * p1 * p1 + (n1 - n2 + x1 * x2) * p1 + x1 * n1 = 0

```

solve for `p1` and factor `n1`

flag: `SECT{ju99lin_w1d_d3m_alg3br0s}`

# other write-ups and resources

Original writeup (https://github.com/OAlienO/CTF/tree/master/2019/SEC-T-CTF/Trivial-RSA).