Please hack.

## Time

8 hours

Solved after the CTF ended, with @tjbecker (PPP)

# Behavior

Same as blind, but the order of GF(p) isn't smooth anymore.

# Solution

I found another solution which is more efficient.

## TL;DR

- Search a elliptic curve with smooth order
- Recover the index of y using Pohlig-hellman.
- Recover the index of y in each subgroup with naive discrete log.
- Calculate y.

After the CTF ended, there's some discussion of this challenge.

```
00:29 hellmann| for blinder my guess would be to construct an elliptic curve with small factor in the order and perform dlp there,
using oracle operations to implement the ecc group
00:29 _0xbb_| you need to discuss that with y7 later^^
00:30 hellmann| looking forward :)
00:42 tjbecker| hellmann: that was my approach, but I couldn't get it down to only 0x4000 queries
00:43 tjbecker| would love to see what optimizations I was missing, if that was the intended solution
00:43 hellmann| how close could you get?
00:44 tjbecker| I needed roughly 0x20000, which is 8x too many
00:45 hellmann| still sounds cool, how many curves did you use? what were the factors
00:47 tjbecker| a,b = (242251381217038, 29739910446124)
00:47 tjbecker| gives a curve of order 2 * 3 * 11 * 13 * 17 * 67 * 71 * 131 * 173 * 179
00:48 tjbecker| (which is also nice because it's square free)
00:48 hellmann| nice, I thought about using many curves
00:48 tjbecker| maybe that's what I was missing
00:48 hellmann| maybe with montgomery arithmetic it should be good enough?
00:48 tjbecker| more liekly, I was just bad at optimizing point addition
00:50 tjbecker| yeah I also thought about using Edwards curves, but got too tired to stay up to try it
00:50 tjbecker| I was happy enough with a solution which was much better than sqrt(p)
01:01 sasdf| tjbecker: How do you construct that curve?
01:02 tjbecker| just try random (a,b) pairs, constructing the curve over GF(p) and take the one with the smoothest order
01:02 tjbecker| took like 10 minutes to find that curve
```

The method using Elliptic curve sounds promising. After @tjbecker gave me his script, we work on optimizing the algorithm together.

Here's the summary of our algorithm:

- Let C = EllipticCurve, T = Target y, G = Generator, o = C.cardinality().
- Calculate
`P = C.lift_x(T)`

. - Similar to what we do in
`blind`

, For each factor f in o:- Calculate
`X = (o / f) G`

- Calculate
`Y = (o / f) P`

- Find
`i`

such that`i X = Y`

, which means`P.order() % f = i`

.

- Calculate
- Reconstruct
`P.order()`

using Pohlig-Hellman algorithm. - Calculate T

## Embed integer

We can't encrypt arbitary integer directly. We need to construct them using 1 and add operation.

First, we calculate a list of power of two (using double and 1), and we can sum those needed bits to construct arbitary number.

## Offline calculation of operation on G

This is our first optimization.

Operation on the elliptic curve is much more expensive than embedding an integer, so we calculated all operation about the generator (i.e. `X = (o / f) G`

and `i X`

) offline, and then embed the result using previous algorithm.

For comparsion between `i X`

and `Y`

, we only compare their y coordinate.

## NAF form

For square-and-multiply (or double-and-add), we use NAF form instead of typical binary form to minimize the operation count.

## Merge order

When calculating double-and-add, we have to sum a list of numbers. If we sum them sequentially:

```
result = reduce(add, points, zero)
```

We (almost) won't hit the cache in add operation.

Instead, we add up neighbors first:

```
a, b, c, d, e, f, g -> (a+b), (c+d), (e+f), g
```

We will have a better chance that hit the cache at first round.

For Point multiplication (i.e. `Y = (o / f) P`

), we know all the operands in advance. We use a greedy algorithm: add up most common pair first. It's not optimal, but much better then merging neighbors first.

```
A = 0, 1, 2
B = 0, 1, 3
C = 0, 1, 4, 5, 6
D = 5, 6
With following order:
Add(0, 1), Add(5, 6), Add(01, 2), Add(01, 3), Add(01, 4), Add(014, 56)
```

## Constant power

There're two operation using constant power:

`inv = exp(x, p-2)`

`sqrt = exp(x, (p+1)/4)`

`p-2`

is a very bad constant when using square-and-multiply, because of it's binary representation:`111111111111111111111111111111111110101101001111`

. We have to sum all those 1 and that is a huge amount of operations.

Fortunately, we cat factor `p-2`

to `123 * 2288414444759`

, which means we can calculate `exp(exp(x, 123), 2288414444759)`

instead.

And we can apply similar techniques to `sqrt`

too.

## Linear search v.s. Baby Step Giant Step

tjbecker implemented Baby Step Giant Step too. The algorithm has lower complexity, but it needs to run point addition `sqrt(f)`

times, which needs too much operations.

A better curve with linear search works better.

## Search the curve

After we finish our algorithm, we can estimate the cost of each part:

`Y = (o / f) P`

takes about 2000 operations of each`f`

.- Comparing
`iX`

and`Y`

takes about 24 operation of each test. - Expectation of the needed tests to find
`i`

is`f / 2`

.

We can use the cost for ranking curves when searching. Here's the script we use to search the curve.

## Flag

Now combining everything together, It's time for getting our flag :) Here's the script.

It uses about 13000 operations on localhost.

...

So where's the flag?

`TimeoutError`

It seems that I have to find a server in Germany to get the flag...