# e000p

Author. EggRoll (Discord ID. 蛋捲鯛魚燒#5393)

## Overview

We are asked to solve dlog on Edwards Curve41417 with equation of the form $$x^2+y^2 = 1+dx^2y^2\pmod{p}$$ The curve is secure as the order is a prime number. Fortunately, we are also given most bit values of the exponent.

## Motivation

First of all, notice that there are **only** `45` unknown bits according to the hint.

bm = (1 << 412) - 1
bm ^= ((1 << 22) -1) << 313    # 22-bit mask
bm ^= ((1 << 22) -1) << 13     # 22-bit mask
bm ^= 1 << 196                 #  1-bit mask
hint = bm & pow(msg, -1, order)

Though it's impoosible to test all $2^{45}$ possibilties, we aware of that $2^{\lfloor\frac{45}{2}\rfloor}$ is brute-forcable. This motivates us to apply meet-in-the-middle (MITM).

## Exploit

To clearly explain the attack, let's identitfy the problem more mathematically. So basically, there are two points $P, Q$ on the curve satisfying $$mP = Q$$ where $m$ is the secret exponent (`m = pow(msg, -1, order)` in our case). We also know that $$m \oplus bm = hint$$ Here $bm$ has only $45$ bits being $0$. In other words, there are only $45$ bits of $m$ that we don't know. We may assume $$m = hint +i_{1}\cdot 2^{e_{1}}+\cdots+i_{45}\cdot 2^{e_{45}} = hint+\sum\limits_{k=1}^{45}{i_{k}2^{e_{k}}}$$ for some $i_{1}, \dots, i_{45} \in\{0, 1\}$ and different integers $e_{1}, \dots, e_{45}$ (they are $13\sim 34$, $313\sim 334$ and $196$). The attack consists of two main steps

1. Bulid a lookup table or dictionary $T$ such that $$T\left[\left(hint+\sum\limits_{k=1}^{23}{j_{k}2^{e_{k}}}\right)P\right] = \sum\limits_{k=1}^{23}{j_{k}2^{k}}$$ In fact, the right-hand-side (RHS) can be other number, it's only required that $j_{1},\dots,j_{23}$ can be recovered.
2. Try the other $22$ bits and check whether the following point: $$\left(m-\sum\limits_{k=24}^{45}{j_{k}2^{e_{k}}}\right)P$$is a key of $T$. Once the key is found, the exponent is revealed.

## Remark

### Too Slow?!

As the curve operations could be slow, there are some ways to speed-up our computations:

1. Pre-computing the points $\{2^{e_{j}}P,\quad j = 1,\dots,45\}$
2. Transform the curve into Weierstrass form [Sage code](https://neuromancer.sk/std/other/Curve41417) and there are libraries optimizing such things

### Highlight

When the number of unknowns is small enough (less than $50$), then it's possible to apply MITM. For instance, the following problems could be solved using this technique.

* *Fault* from TetCTF 2022
* *Corrupted-Curve+* from corCTF 2022 [Official Repo](https://github.com/Crusaders-of-Rust/corCTF-2022-public-challenge-archive/tree/master/crypto/corruptedcurvesplus)

## Quick Implementation

# MITM 1st Step
lookup = {}

# Pre-processing for speed-up
tmp = mul(hint, base)
points = [mul(1 << (313 + i), base) for i in range(22)]

for i in range(1 << 22):
	
	res = tmp
	for j in range(22):
		if i & (1 << j):
			res = add(points[j], res)
	lookup[res] = i

# MTIM 2nd Step

# Pre-processing for speed-up
points = [inverse(mul(1 << (13 + i), base)) for i in range(22)]
points += [inverse(mul(1 << 196, base))]

for i in range(1 << 22):
	
	res = enc
	for j in range(22):
		if i & (1 << j):
			res = add(points[j], res)
            
	if res in lookup:
		print(i)
		print(lookup[res])

	if add(points[-1], res) in lookup:
		print("+")
		print(i)
		print(lookup[res])

You should be able to find the flag from here :P

:::success
maple{th3_3dw4rd_cu12ve_and_kn0wn_bits_dlp}
:::

Sorry for my ugly code, you may also refer [maple3142 and vishiswoz's scripts](https://gist.github.com/maple3142/39cface48563d01dc90607344c6bcad9)