# pbctf 2020

December 6, 2020I didn’t have much free time this weekend, but pbctf ended up being the perfect opportunity to field-test my coppersmith script!

## LeaK

We get thirty ECDSA signatures along with their partially leaked nonces, although I ended up only using two. The challenge’s twist is that each leak is the middle 176 bits of a 256 bit nonce, leaving 40 unknown bits on each side. As a mathematical expression, we have

```
k = 2^216 a + 2^40 b + c
```

where `a`

is an unknown, `b`

is the leak, and `c`

is another unknown. Recall that in ECDSA we have the following signature equations:

```
s = inv(k) (h + r d)
d = inv(r) (s k - h)
```

Using two signatures, we can eliminate the private key entirely:

```
inv(r1) (s1 k1 - h1) - inv(r2) (s2 k2 - h2) = 0
```

This is a multivariate equation with small roots, which means it’s time for Coppersmith’s method! Some back-of-the-envelope calculation to justify the approach: we have four unknowns for a total of 160 bits, which is well below 256-bit modulus. The roots allow us to recover the nonces, and hence the private key.

```
n = ...
R = Integers(n)
samples = eval(open('output').readline())
h1, b1, r1, s1 = map(R, samples[0])
h2, b2, r2, s2 = map(R, samples[1])
P.<a1, c1, a2, c2> = PolynomialRing(R)
bounds = (2^40, 2^40, 2^40, 2^40)
k1 = a1*2^216 + b1*2^40 + c1
k2 = a2*2^216 + b2*2^40 + c2
f = r1^-1 * (s1*k1 - h1) - r2^-1 * (s2*k2 - h2)
roots = small_roots(f, bounds, m=2, d=2)[0]
d = r1^-1 * (s1*k1(*roots) - h1)
print(d)
```

## Special Gift

This solution works for both Special Gift and Special Gift Revenge. We get an RSA public key where the private key `d`

is relatively small, around `N^0.4`

. This is too large to use the Boneh-Durfee attack, but fortunately we also get a partial leak of `d`

, namely all but the lower 120 bits. In other words, we have an approximation `d0`

such that `d - d0`

is 120 bits.

Recall that in the Boneh-Durfee attack, we lift `ed = 1`

modulo `phi`

to be `ed = 1 + k phi`

over the integers, where `k = (ed - 1) / phi`

is unknown. Reducing modulo `e`

, we get

```
1 + k phi = 0
1 + k (N + 1 + s) = 0
```

where `s = p + q`

is also unknown. Notice that `k`

is approximately the same size as `d`

. The Boneh-Durfee attack solves for `k`

and `s`

using Coppersmith’s method, but in this challenge `k`

is too big. Fortunately, we have an approximation! Let `k0 = e d0 // N`

. Then `k - k0`

is 120 bits, and we can solve for this unknown instead.

```
N, e, gift = ...
d0 = gift << 120
R = Integers(e)
P.<x, s> = PolynomialRing(ZZ)
bounds = (2^120, 2^512)
k0 = e*d0 // N
f = 1 + (k0 + x) * (N + 1 - s)
x, s = small_roots(f.change_ring(R), bounds, m=3, d=4)[0]
ed = f(x.lift(), s.lift())
d = ed // e
print(d)
```

The same idea works for Special Gift Revenge, except I called `small_roots(..., d=5)`

. Also, instead of using `I.variety`

to compute roots (took ~10 minutes on my laptop), I suggest modifying `small_roots`

to use polynomial resultants.

```
roots = []
h1, h2 = I.change_ring(f.parent()).gens()
for y, _ in h1.resultant(h2).univariate_polynomial().roots():
for x, _ in h1.subs({h1.variable(1): y}).univariate_polynomial().roots():
roots.append((R(x), R(y)))
return roots
```