Table of Contents

NOiSE 2021-1-19更新 #

$$ \begin{aligned} n_i\times r_i\equiv c_i mod ;s \\ n_i r_i= c_i +k_is \end{aligned} $$

$r_i<s$

可以选取n的值得到

$n_i r_i= c_i +s$

$-c_i= s; mod;n_i$

CRT得解 #

⑧说了，学到很多

题目附件 server

这个题核心点在这段代码上

 print(num * getrandbits(992) % secret)

num是输入，乘上一个992bits的随机数后返回模上 secret 的结果。

于是我们可以得到下式：

$n_i\cdot\ g_i\equiv c_i ;mod ;m$

$n_i\cdot\ g_i=c_i+k\cdot m$

则有

$0\equiv c_i+k\cdot m; mod ;n_i$

若$k=1$则有下式

$n_i-c_i\equiv m;mod;n_i$

若能求出多个上述式子，则有几率使用中国剩余定理求出$m$

要$k=1$则需要$m<n_i\cdot g_i<2m$,因为$g,m$有固定的bit长度，想怼参数取对数分析：

$m,g$均有二分之一的概率分别大于$2^{1024},2^{992}$,当满足改条件时，设：

$$ log(m)=2^{1024}\cdot 2^\gamma, log(n)=2^{32}\cdot 2^\beta , log(g)=2^{992}\cdot 2^\alpha $$

可得下式：

$$ \gamma<\beta\cdot\alpha<\gamma +1 $$

已知我们只能控制 $n_i$ 即 $\beta$，又因为当$\beta$过小时会有$m>n_i\cdot g_i$则会出现$c_i=n_i\cdot g_i$,验证是否过小只需要验证$c_i;mod ;n_i\neq;0$就ok了

所以综上，应该将$n_i$控制的尽量小。

因为我们求出的式子$n_i-c_i\equiv m;mod;n_i$需要满足CRT的成立条件故所以$n_i$应该均为素数。

这里用下式生成$n_i$:

point = int(sqrt(1.1)*pow(2,32))
ed = pow(2, 16)
num = next_prime(getRandomRange(point-ed, point+ed))

平均测试下来30~40次时可以打通的，在可接受范围内 =v=