# Noise Writeup

D^3CTF 2019 Crypto - Noise

Writeup: https://hackmd.io/@JHSN/r1r5vuO2B

File: https://gist.github.com/Chrstm/f225a5e67f12d20caba117224d1b4241

## Problem

$n$ is an unknown constant integer (1024 bits). You can interactive with an oracle for less than 50 times: given a non-negative integer $x$, return $f(x) = (x + r) \bmod n$ where $r$ is an inconstantly random integer (1000 bits). Retrieve the $n$.

## Solution

One natural way is the binary search. In this way, we can get only one bit each round and it doesn't work when the length of the range of the $n$ is close to the noise. However, maybe it's a good idea for breaking through the problem to start from a rough range and make it smaller.

Assumes that we have already known a rough integer interval $[L, R]$ satisfying $n \in [L, R]$. If we can find a pair of integer $(I, t)$ where the following equation holds for all possible $n$ and $r$:

$$f(I) = (I + r) \bmod n = I + r - tn$$

in other words,

$$tn = I - f(I) + r$$

Obviously $I - f(I) + r$ is a multiple of $t$ and its range is only related to the $r$. Thus a different range of $n$ comes out:

$$n = \frac{I - f(I) + r}{t} \in \left [ \frac{I - f(I) + r_{\min}}{t} , \frac{I - f(I) + r_{\max}}{t} \right ]$$

The $r$ ranges in $\left [0, 2^{1000} \right ]$. Let $s = r_{\max} = 2^{1000}$ and the length of the above range of $n$ is around $\frac{s}{t}$.

Now the problem is how to choose a proper pair $(I, t)$ and make the $t$ as large as possible to get a small range of $n$. Look back to the assumption,

$$\forall r \in [0, s], n \in [L, R], \quad tn \leq I + r < (t+1)n$$

in other words,

$$(tn - r)_{\max} \leq I < ((t + 1)n - r)_{\min}$$

thus,

$$(tn - r)_{\max} = tR \quad < \quad ((t + 1)n - r)_{\min} = (t + 1)L - s$$

$$\Leftrightarrow \quad tR \leq (t + 1)L - s - 1$$

$$\Leftrightarrow \quad t \leq \frac{L - s - 1}{R-L}$$

The $I$ always exists as long as the $t$ satisfies this inequation. Besides, the $t$ has a lower bound $t\geq 1$ such that the division makes sense. So we have requirements for the $L, R$:

$$1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1$$

There are two ways to pick out valid $[L, R]$ at the beginning:
1. Assumes that the $n$ ranges in $\left [2^{1023}, 2^{1024} \right ]$. (the possibility is about 50%, so take more tries if unlucky)
2. Binary search. (it's trivial and see more detail in the [exp](https://gist.github.com/Chrstm/f225a5e67f12d20caba117224d1b4241#file-noise_exp-py) script)

Let's take a summary. Try to pick a valid pair $L, R$ as the initial interval of $n$. Then Let the $t$ be the maximum $\frac{L - s - 1}{R-L}$ and select a $I$ from the range $[tR, (t + 1)L - s - 1]$, so

$$n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]$$

Let the $[L, R]$ be the new interval and repeat for a couple of times. The range of $n$ shrinks from $\Delta \sim R-L$ to $\Delta' \sim \frac{s}{t}$ where

$$\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}$$

The number of iterations is about $\log_s n$, typically around 45 times. (similarly, take more tries if not lucky enough)

FYI: This is a general solution. You will find some much easier ways to retrieve it if you just make some assumptions (such as assume that the $n$ is in a certain range, let $I = tR$, etc.), simplify the above steps and try a couple of times.

## 问题

$n$ 是一个未知整数 (1024 bits)。你可以访问一个黑盒函数不超过 50 次：给定一个非负整数 $x$，返回 $f(x) = (x + r) \bmod n$，$r$ 是一个每次都重新生成的随机数 (1000 bits)。 求 $n$。

## 解答

一种比较自然的想法是二分查找，但这样每次只能获取到 1 bit 信息且当区间大小接近噪声大小时就无法再缩小范围了。不过我们可以以这种方式切入，假设已知某个范围并想办法缩小它。

假设我们已有 $[L, R]$ 满足 $n \in [L, R]$。如果我们可以找到一对 $(I, t)$ 对于所有可能的 $n$ 和 $r$ 都满足：

$$f(I) = (I + r) \bmod n = I + r - tn$$

即

$$tn = I - f(I) + r$$

那么显然 $I - f(I) + r$ 是 $t$ 的倍数，它的范围只和 $r$ 有关。所以可得 $n$ 的新区间：

$$n = \frac{I - f(I) + r}{t} \in \left [ \frac{I - f(I) + r_{\min}}{t} , \frac{I - f(I) + r_{\max}}{t} \right ]$$

$r$ 的范围是 $\left [0, 2^{1000} \right ]$。令 $s = r_{\max} - r_{\min} = 2^{1000}$，则上述区间长度大约是 $\frac{s}{t}$。

现在的问题就转化为如何选取一对合适的 $(I, t)$ 并且 $t$ 尽可能大，这样得到的新区间就尽可能小。回到一开始的假设上，

$$\forall r \in [0, s], n \in [L, R], \quad tn \leq I + r < (t+1)n$$

即

$$(tn - r)_{\max} \leq I < ((t + 1)n - r)_{\min}$$

则有

$$(tn - r)_{\max} = tR \quad < \quad ((t + 1)n - r)_{\min} = (t + 1)L - s$$

$$\Leftrightarrow \quad tR \leq (t + 1)L - s - 1$$

$$\Leftrightarrow \quad t \leq \frac{L - s - 1}{R-L}$$

只要 $t$ 满足这个条件，我们就可以找到对应的 $I$。除此之外，因为 $t$ 参与除法，所以还有一个下界 $t\geq 1$，由此我们可以得到对 $L, R$ 的限制条件:

$$1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1$$

有两种方法来设置合法的初始 $[L, R]$：
1. 直接假设 $n$ 落在 $\left [2^{1023}, 2^{1024} \right ]$（这样的概率大约是 50%，所以如果假设不成立就多试几次）
2. 二分查找（这是一种很显然的方法，详见 [exp](https://gist.github.com/Chrstm/f225a5e67f12d20caba117224d1b4241#file-noise_exp-py)）

综上所述，首先选取一对 $L, R$ 作为 $n$ 的初始范围.然后令 $t$ 为最大值 $\frac{L - s - 1}{R-L}$ 并在区间 $[tR, (t + 1)L - s - 1]$ 中选择一个 $I$，由此可得新区间

$$n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]$$

更新 $[L, R]$ 的值重复上述过程。$n$ 的范围跨度从 $\Delta \sim R-L$ 缩小到 $\Delta' \sim \frac{s}{t}$，有

$$\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}$$

所以迭代次数大约是 $\log_s n$，一般在 45 次左右（同样如果一次不行，就多试几次）

FYI：这是一般性的做法。如果直接做一些假设（譬如假设 $n$ 落在某个范围，令 $I = tR$ 等等），可以省略掉一些繁琐的步骤得到一些更简单但需要多试几次的做法。