文章目录
  1. noise
    1. 题目信息
    2. 分析
    3. 利用$n_{i}$控制$k_{i}$
    4. 值得注意的地方
    5. 解题
  2. threshold
    1. 题目信息
    2. 分析
    3. 解题

noise

题目信息

附件是一个Python脚本，Gitee备份在此

分析

穷举通过proof_of_work之后，我们来看代码逻辑：

  • secret=getrandbits(1024)，注意他自己实现的getrandbits(1024)实际上是生成长1017~1024位的随机数；
  • 对上述生成的secret，服务器最多只会与你交互64次；
  • 若op为’god’，服务器会返回num * getrandbits(992) % secret，这里num也由我指定；
  • 若op为’bless’，服务器会判断num与secret是否相等，若相等服务器返回FLAG。

由于我至少要留一次交互机会发送我计算出的secret，因此我必须在63次交互内计算出secret！为下面叙述方便，声明如下记号：

  • 第 i 次发送的num记为$n_{i}$；
  • 第 i 次getrandbits(992)记为$g_{i}$；
  • 第 i 次接收的num * getrandbits(992) % secret记为$c_{i}$。

记secret为$m$，则：

$c_{i} \equiv n_{i}\cdot g_{i}\ \textrm{mod}\ m,i=1,\cdots ,63$

即存在$k_{i}\in Z$，$n_{i}\cdot g_{i}=c_{i}+k_{i}\cdot m$

对等式两边模$n_{i}$则有：

$c_{i}+k_{i}\cdot m \equiv 0\ \textrm{mod}\ n_{i}$

若我能够控制$k_{i}=1$，那么：

$m \equiv (n_{i}-c_{i})\ \textrm{mod}\ n_{i}$

同时得到多个如上形式的等式可考虑使用中国剩余定理解出$m$！

利用$n_{i}$控制$k_{i}$

$m$有$1/2$的概率长1024比特，$g_{i}$有$1/2$的概率长992比特；此时，要控制$k_{i}=1$，即：

对上式两边取对数：

记$log(g_{i})=991+\alpha,log(n_{i})=32+\beta,log(m)=1023+\gamma;\alpha,\beta,\gamma \in (0,1)$(其中$X=2^{\alpha},Y=2^{\gamma}$服从$[1,2]$上的均匀分布)。上式改写为：

综上，$P(k_{i}=1)=P(\alpha+\beta>\gamma,\alpha+\beta<1+\gamma)=p(2^{\beta}\cdot x>Y,2^{\beta-1}\cdot X<Y)$

直观地看，$\beta$越大越有利于约束条件$\alpha+\beta>\gamma$而不利于约束条件$\alpha+\beta<1+\gamma$，反之，$\beta$越小越有利于约束条件$\alpha+\beta<1+\gamma$而不利于约束条件$\alpha+\beta>\gamma$。

注意到我可以判断是否满足约束条件$\alpha+\beta>\gamma$—若$n_{i}\cdot g_{i}<m$则$c_{i}=n_{i}\cdot g_{i}$从而$c_{i}\equiv 0\ \textrm{mod}\ n_{i}$。

由此，我选择$n_{i}$时应该尽量满足约束条件$\alpha+\beta<1+\gamma$，即$\beta$应尽量小，为何不设置$\beta$为0，理由如下：

当$\beta=0$时，$P(k_{i}=1)=P(\alpha>\gamma,\alpha<1+\gamma)=p(\alpha>\gamma)=1/2$；

由上述：$n_{i}$长$33$比特，而$m$长$1024$比特；由中国剩余定理可知：我们需要32个如下形式的同余式才能解出$m$！

$m \equiv (n_{i}-c_{i})\ \textrm{mod}\ n_{i}$

要得到如上形式的同余式，即需要$k_{i}=1$，而$P(k_{i}=1)=1/2$，那么我得到$32$个如上形式的同余式“平均”需要$64$次交互，从而我没有发送secret的交互机会。

综上，$\beta$应在大于0的前提下尽量小！

值得注意的地方

通过2.1，我知道了$n_{i}$值多大时可以解出$m$，结合中国剩余定理，同余式的模数之间是互素的，即我选择的$n_{i}$需两两互素，因此$n_{i}$不是取确定的值而是在一定的取值范围内取素数！

解题

上述链接中的solve.py为解题的Python脚本，程序运行(成功时)结果如下：

1
2
3
4
5
6
7
$ python3 solve.py
[+] Opening connection to 182.92.153.117 on port 30101: Done
[+] MBruteforcing: Found key: "l9a"
success!
95613903744255213782277288259288084531700829576284706991256294359734535087821985034716432798049279163174069238632678362676474782669781482301447573436852554131343117198284150657465643396718720128642929008328391123641254705186541184339088382138616985634723733544083949806487213357784626124965521562172300016682
b'CONGRATULATIONS ByteCTF{Noise_i5_rea11y_ANN0YING}\n'
[*] Closed connection to 182.92.153.117 port 30101

注：此程序并非次次运行都能解出secret

threshold

题目信息

附件是一个Python脚本，Gitee备份在此

分析

程序又臭又长，但其实考点特别简单，稍微使用一下欧拉定理即可！我来分析一下程序的逻辑：

在类TSM2初始化时：

$pks \equiv [(sk+1)\cdot sks]^{n-2}\ \textrm{mod}\ n$

接着在output_p1函数中：

$s \equiv (d_{1}\cdot k_{1}\cdot s_{2}+d_{1}\cdot s_{3}-r)\ \textrm{mod}\ n$

其中$d_{1}=sks$，而$r,s_{2},s_{3}$均由我指定，那么我令$r=s_{2}=0,s_{3}=1$，则得到的$s$即为$d_{1}$在模$n$下的值，即：

$s \equiv sks\ \textrm{mod}\ n$

注意到$n$是素数，欧拉函数$\phi(n)=n-1$，显然$(n-2,n-1)=1$，即存在$x\in Z,x\cdot (n-2)\equiv 1\ \textrm{mod}\ \phi(n)$

由欧拉定理：$pks^{x}\equiv [(sk+1)\cdot sks]^{(n-2)x}\equiv (sk+1)\cdot sks\ \textrm{mod}\ n$

因此$(sk+1)\equiv pks^{x}\cdot sks^{-1}\equiv pks^{x}\cdot s^{-1}\ \textrm{mod}\ n$，而密钥$sk$是小于阶$n$的，因此解出密钥$sk$，有了密钥干什么不行呢，按照程序的要求，对消息b’Hello, Welcome to ByteCTF2020!’签名即可！

解题

略