KalmarCTF2026
Crypto
RBG
- 注意：此题并不是在该比赛中出现的，只是为了做出
RBG+而做这题找思路。 - 题目附件如下：
1 | from Crypto.Util.number import * |
-
此题代码加密流程如下：
- 首先生成两个
137位的素数$p、q$，并计算$N=pq$，并会输出$N$ - 接着生成公钥指数$e$。注意生成公钥指数并没有输出
- 接着定义一个
LCG生成器，该LCG公式为：$s_{i+1}=3s_{i}+1337~mod(~N)$ - 最后进行$13$次循环，循环中会输出：$c_i=m^{e_i}~mod(~N)$
- 首先生成两个
-
先写出多组加密公式，对加密进行具体的推导：
- 首先根据$c_i=m^{e_i}~mod(~N)$就会有：
$$
c_0=m^{e_1}~mod(~N)\
c_1=m^{e_2}~mod(~N)\
c_2=m^{e_3}~mod(~N)\
…
$$- 接着根据
LCG的公式带入一下：
$$
\begin{array}{l}
c_0=m^{3e_0+1337~mod(~N)}~mod(~N)\
c_1=m^{3e_1+1337~mod(~N)}~mod(~N)\
c_2=m^{3e_2+1337~mod(~N)}~mod(~N)
\end{array}
$$- 这里其实可以利用$c_0=m^{e_1}~mod(~N)$与$c_1=m^{e_2}=m^{3e_1+1337}~mod(~N)$求得$c_{00}=m^{1337}~mod(~N)$。注意：此时求得的并非是$m^{1337}$的真实值，这是因为还需要考虑到
LCG中的模$N$，因此下面的这个式子是错误的。
$$
c_0^{-3}·c_{1}=m^{-3e_1}·m^{3e_1+1337}=m^{1337}=c_{00}~mod(~N)
$$- 这时我们需要思考一下：$c_0^{-3}·c_{1}$的值代表着什么含义，可以使用什么式子表达，首先我们有，满足$e_0,e_1,…,e_{13}<N$：
$$
e_1\equiv 3e_0+1337~mod(~N)\
e_2\equiv3e_1+1337~mod(~N)\
…\
e_i\equiv3e_{i-1}+1337~mod(~N)
$$- 那么我们将同余号改为等号就会有如下等式：
$$
e_1 = 3e_0 + 1337-k_1N\
e_2 = 3e_1 +1337-k_2N\
…\
e_{12}= 3e_{12}+1337-k_{12}N
$$- 接下来我们以$c_0^{-3}·c_1$为例子，不妨设$x_1\equiv -3e_1~mod(~\phi(N))$，那么就有$x_1=-3e_1+k’_1\phi(N)$。这个步骤需要特别注意
$$
c_{0}^{-3}\equiv m^{-3e_1}~mod(~N)\Rightarrow c_0^{-3}\equiv m^{x_1}~mod(~N)
$$- 那么$c_0^{-3}·c_1$就会有如下式子，则有如下式子：
$$
c_0^{-3}·c_1=m^{-3e_1}·m^{e_2}=m^{x_1+e_2}=m^{-3e_1+k’_1\phi(N)+3e_1+1337-k_1N}=m^{1337-k_1N}~mod(~N)
$$- 所以最终我们可以得出如下式子：
$$
c_{00}=c_0^{-3}c_1=m^{1337-k_1N}~mod(~N)
$$- 如果我们遍历$c_{0},…,c_{12} $，那就可能会出现几组不同的值，我们记为$c_{00},c_{01},…,c_{0n}$，式子如下：
$$
c_{00}=c_{0}^{-3}c_1=m^{1337-k_1N}~mod(~N)\
c_{01}=c_{1}^{-3}c_2=m^{1337-k_2N}~mod(~N)\
…\
c_{0n}=c_{n}^{-3}c_{n+1}=m^{1337-k_nN}~mod(N)
$$- 由于$e_0\in [731,N)$，所以$3e_0+1337 \in [3*731+1337,3N)$，因此可以得到$k_i \in {1,2,3,4}$，大概可以得到有$3,4$种可能。
-
知道了大致的值，其实可以直接用共模攻击爆破一下模数就可以求解了。
-
完整exp如下：
1 | from Crypto.Util.number import * |
*RBG+
-
在做这题之前先来看看
RBG，也就是上面的一题，看完RBG再看看这题。想不出来QAQ复现吧。 -
题目附件如下：
1 | from Crypto.Util.number import * |
-
由该题附件可以得到，此题是
RSA结合LCG，具体加密流程如下：- 首先读取
flag，并将flag转换为大整数m、 - 接着生成两个
371位的素数$p、q$，并计算模数$N=pq$ - 之后随机生成一个加密指数$e\in [731,N)$，并输出公钥对$(e,N)$
- 定义一个$lcg$，其表达式为：$s_{i+1}=3s_{i}+1337~mod(~N)$
- 最后进行$13$次的循环计算并输出：$c_i=m^{e_i}~mod(~N)+m^{e_{i+1}}~mod(~N),i=0,…,12$
- 首先读取
-
接下来对这个已经给出的式子进行推导
- 我们先写出已知的式子：
$$
c_0=m^{e_0}~mod(~N)+m^{e_1}~mod(~N)\
c_1=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)\
c_2=m^{e_2}~mod(~N)+m^{e_3}~mod(~N)\
…\
c_{12}=m^{e_{12}}~mod(~N)+m^{e^{13}}~mod(~N)
$$- 从已知的式子中可以看出，$c_{i}$是模幂运算再相加，相加之后没有再取模了，设$m^{e_i}\equiv x_i~mod(~N)$，那么就可以写成如下式子：
$$
c_0=x_0+x_1\
c_1=x_1+x_2\
…\
c_{12}=x_{12}+x_{13}
$$- 由
LCG线性同余我们还可以得到：
$$
m^{e_{i+1}} = m^{3e_{i}+1337-k_{i}N}
$$- 因此还可以得到$x_i$与$x_{i+1}$之间的关系：
$$
x_{i+1}= x_{i}^{3}·m^{1337-k_iN}
$$ -
上面是已经想到的地方，下面是没有想到的地方：
- 通过$x_{i+1}=x^{3}{i}·m^{1337-k_iN}$，通过这个同余式，我们就可以得到一个比值关系：$\frac{x{i+1}}{x_i^{3}}= m^{1337-k_iN}$，其中可以确定$k_i\in {0,1,2}$
- 这样我们在这$13$组
LCG中其实就应该存在一组或者多组数据使得：$\frac{x_{k_{1}+1}}{x^{3}{k_1}}= \frac{x{k_2+1}}{x^{3}{k{2}}}$，这里不妨设$m^{e_0}\equiv x~mod(~N)$，那么$m^{e_i}\equiv x\pm A_{i}~mod(~N),i=1,…,12$ - 很自然的$c_0,c_1,…c_{12}$就可以写成如下式子：
$$
\begin{array}{l}
c_0=2x\pm A_1\c_1=2x\pm A_1\pm A_2\…\c_{12}=2x\pm A_{11}+A_{12}
\end{array}
$$- 那么这样其实就可以得到：$\frac{x\pm A_1}{(x\pm A_2)^{3}}=\frac{x\pm A_3}{(x \pm A_4)^{3}}$，交叉相乘就可以得到：$(x\pm A_1)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_2)^{3}$
- 我们不妨取三组$k=0$的情况，此时就会有$x_{i+1}=x_i^{3}·m^{1337}$，并且比值后就得到三组这样的值：
$$
\frac{x_{k_1+1}}{x^{3}{k_1}}=\frac{x{k_2+1}}{x^{3}{k_2}}=\frac{x{k_3+1}}{x^{3}_{k_3}}\Rightarrow \frac{x \pm A_1}{(x\pm A_2)^{3}}=\frac{x\pm A_3}{(x\pm A_4)^{3}}=\frac{x\pm A_5}{(x\pm A_6)^{3}}
$$- 这样就可以得到：
$$
(x\pm A_1)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_2)^{3}\
(x\pm A_1)(x\pm A_6)^{3}=(x\pm A_5)(x\pm A_2)^{3}\
(x\pm A_5)(x\pm A_4)^{3}=(x\pm A_3)(x\pm A_6)^{3}
$$- 此时我们就可以构造出两个多项式：
$$
\begin{array}{l}
f = (x\pm A_1)(x\pm A_4)^{3}-(x\pm A_3)(x\pm A_2)^{3}\
g = (x\pm A_1)(x\pm A_6)^{3}-(x\pm A_5)(x\pm A_2)^{3}
\end{array}
$$- 由于$c_0=2x\pm A_1$，那么我们就可以变形得到：$p_0=c_0-x = x\pm A_1$，$p_1 = c_1-(c_0-x)=c_1-p_0=x\pm A_2$，进而继续改写构造出的多项式：
$$
\begin{array}{l}
f=p_{k_1}·p_{k_2}^{3}-p_{k_1}·p^{3}_{k_3}\
g=…
\end{array}
$$- 这样就可以使用多项式$gcd$，求解出$x$，也就是消息相关攻击。这样就可以直接求得$m^{e}$，通过比值关系还可以求得$m^{1337}$的值，接着就可以利用共模攻击求解了。
-
具体exp如下：
1 | from sage.all import * |
*RBG++
- 题目附件如下：
1 | from Crypto.Util.number import * |
-
由该题附件可以得到，本题加密过程如下：
- 首先读取
flag，将flag转换为大整数；并且生成两个素数$p,q$，并计算模数$N = pq$ - 接着定义一个
LCG线性同余方程，与RBG和RBG+一样的同余方程：$e_{i+1}\equiv 3e_i + 1337~mod(~N)$ - 对于此题来说，并没有泄露$e$，而是只给出模数$N$
- 最后进行循环得到的结果与
RBG+稍微有所不同，式子如下：
$$
c_0=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)\
c_1=m^{e_3}~mod(~N)+m^{e_4}~mod(~N)\
c_2=m^{e_5}~mod(~N)+m^{e_6}~mod(~N)\
…\
c_{12}=m^{e_{25}}~mod(~N)+m^{e_{26}}~mod(~N)
$$ - 首先读取
-
对比
RBG+来说，此题不能使用RBG+的用$m^{e}\equiv x~mod(~N)$，构造出$c_0-x=x\pm A_1,c_1 - (c_0-x)=x\pm A_2,…$这么一系列的递推关系。但是对于此题来说$c_0=m^{e_1}~mod(~N)+m^{e_2}~mod(~N)$并且$e_0$还没给出来，这就很蛋糕了，还需要再次详细的进行分析。- 通过线性同余方程依然可以得到等量关系，其中$k\in {0,1,2}$：
$$
e_1 = 3e_0+1337 - k_1N\
e_2 = 3e_1+1337 - k_2N\
e_3 = 3e_2+1337 - k_3N\
…\
e_{26} = 3e_{25}+1337 - k_{25}N\
$$- 如果我们像刚刚那样假设$x=m^{e_1}$，那么$c_0-x=x+A_1$，但是$c_1-(c_0-x)=x+A_3+A_4-A_1$，这就导致这个递推式子就会出现更多的未知量，这并不是我们想要的结果，而且这样计算也构造不出来
RBG+中的那个比值的式子。
*RBG+++
- 题目附件如下：
1 | from Crypto.Util.number import * |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iyheart的博客！
wechat