DASCTF复盘之密码学(2023.07)

DASCTF 2023年7月 密码学题解共3题

快过年了闲下来发现一点存货，遂记录之。

同期题目 DASCTF逆向2023.07

ezRSA

RSA is not easy, huh?

这是两道RSA的缝合题。

第一关：知道P^(Q>>16)，要分解N。

第二关：知道前后缀、密文以及带前后缀的密文，求明文。

一开始注意到P的高位字节已知，想用coppersmith求，但发现未知的位数太多，遂放弃。

从第0位一直到第495位每一位的组合只有两种情况，并且可以部分检验(l是部分bit长)：

$\ast \left(mod{l}^{}\right)=P\ast Q\left(mod{l}^{}\right)=N\left(mod{l}^{}\right)$Pˉ∗Qˉ​(mod2l)=P∗Q(mod2l)=N(mod2l)

直接进行一个深度优先的搜索。

Q的低16位完全未知，只能纯粹枚举。

然后是一个明文相关的板子题，使用多项式求gcd的方式求解，明文的长度需要枚举哈。

注意这里有一点比较坑，n求解之后长度只有1020完全不够，需要加上N，卡了我很久(如果加上2*N长度就超过了)。

dasctf{C0pper_Sm1th_Mak3s_T1ng5_Bet4er}

ezDHKE

DHKE is easy, huh?

Diffie Hellman密钥交换的模数任选，令 $p=g^k-$p=gk−1，有
$g^x\equiv g^{x<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>k}\left(modp\right)$gx≡gxmodk(modp)。

所以

$=g^{x<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>k}=x$logg​Cx​=logg​gxmodk=x

$=g^{y<mrow><mi>m</mi><mi>o</mi><mi>d</mi></mrow>k}=y$logg​Cy​=logg​gymodk=y

(k取的比较大)。

DASCTF{eefa6be7-57e6-4a48-99d6-936feff93108}

ezAlgebra

Algebra is not easy!

算法如下：

取3个质数pqr，p长512bit，q长256bit，r长256bit，乘积为n，n给定。

随机摇一个32bit的t，输出密文:

$=+(p+t)+(p+t{)}^{}+(p+t{)}^{}+(p+t{)}^{}(modn)$c1​=1997+(p+t)+(p+t)2+(p+t)3+(p+t)4(modn)

$=+\left(mt\right)+(mt{)}^{}+...+(mt{)}^{}\left(modq\right)$c2​=1997+(mt)+(mt)2+...+(mt)19(modq)

$=+(m+t)+(m+t{)}^{}+...+(m+t{)}^{}\left(modq\right)$c3​=1997+(m+t)+(m+t)2+...+(m+t)19(modq)

注意到
$f\left(t\right)=+t+t^{}+t^{}+t^{}-c=\left(modp\right)$f(t)=1997+t+t2+t3+t4−c1=0(modp)

可以求小根，根据coppersmith方法有

t0​<=21​nδβ2​−ϵ,ϵ=γβ​<=71​β,p>=nβ

$\delta$δ是次数，取4。
$\beta$β就是p的估计，p512bit，取0.5。

t有32bit，n有1024bit，大约解得$\gamma >=$γ>=16.5，取17。

得到t后，带入f(t)的公式和n作gcd，得到p，将n缩为qr的乘积。

令

$\left(m\right)=+\left(mt\right)+(mt{)}^{}+...+(mt{)}^{}-c$g1​(m)=1997+(mt)+(mt)2+...+(mt)19−c2

$\left(m\right)=+(m+t)+(m+t{)}^{}+...+(m+t{)}^{}-c$g2​(m)=1997+(m+t)+(m+t)2+...+(m+t)19−c3

现在，在$Z/nZ\left[x\right]$Z/nZ[x]寻找g1和g2的线性组合，使得其次数尽可能小。

$\left(m\right)=\left(m\right)-\left(m\right)$g1​ˉ​(m)=g1​(m)−g2​(m)

$\left(m\right)=\left(m\right)-m\left(m\right)$g2​ˉ​(m)=g2​(m)−mg1​ˉ​(m)

如果g1，g2同次数且都是首一多项式，进行该过程后次数均递减。

不断地进行这个过程，最后要么出现g1为常数且是q的倍数，
要么在化归首一的时候出现无逆元的最高次系数。（因为g1，g2都是q的倍式）

无论哪种情况，将其和n作gcd得到q和r。

有了q之后，在$Z/pZ\left[x\right]$Z/pZ[x]上求g2和g3的gcd，此时一定可以找到一次式$m+$m+m0​。

然后，令$m=-+iq$m=−m0​+iq爆破明文，当i取到24bit的时候得到了flag。

dasctf{ShangPoXiaPoYaSiLeYiQianDuo}

如果你知道这个梗，甚至可以猜出flag

完结撒花

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！