Rating:
# Real EC
## Task
We use the elliptic curve P256 (NIST-standard).
The programme generates some random 1000-Byte secret (from urandom).
This is split into 250 32-bit Integers *e_i*.
Then for all 250 parts, we also generate some random *n = x0...0x0...0x* (8 bit unknown).
Finally, we get *g^(e_i * n)*.
Find the hash of the secret, you have 100 seconds.
## Solution
* We cannot break ECDSA.
* Each point has 40 Bit -> somehow brute-force
Before we get the 250 values, we have arbitrary time.
Create a lookup table, then just search for all of these points in table.
Table gets too large (some TB RAM), instead meet-in-the-middle.
* Create k bit table.
* Try 40-k bit in-time
In the end the following worked
* Use server, with 80 cores to lookup points in parallel
* Use 22 Bit table
* Compute inverses of possible n before
* try to use addition of points (instead of multiplication) for speedup
Finished Lookup table: 162.18 seconds
Finished with all points: 41.88 seconds
