huangx607087 祥云杯密码题wp
0. 简介
前几天打了一下祥云杯的密码题,4道题目,在别人指指点点下,写了三道题,这几天完善一下自己的wp
1.Guess
拿到题目后,先审计一下代码:
1 | #task.py |
然后题目还给出了一个key的加密方法,并给出了hint文件用于求key。
1 | from Crypto.Util.number import getRandomNBitInteger |
key = random_matrix(ZZ, 20, 4, x = 100, y =1000)
这个代码表示在整数定义域内生成一个$20$行$4$列,定义域为整数的矩阵,其中矩阵中最小数字不小于$100$,最大数字不超过$1000$。然后又注意到hint又是一个key*vector
的矩阵,其中vector
中的所有数字都是$1024$个比特。
因此,通过这个key的加密方法我们可以看出:由于这里是右乘向量,因此这边所有的向量都是列向量。所以我们可以理解成一个$20$行$4$列的矩阵,乘上一个$4$行$12$列的矩阵,得到一个$20$行$12$列的矩阵。而最后的hint是$12$行$20$列。因此我们读入数据后,需要转置一下。
看到矩阵、又看到了非常小的数字(几百)和非常大的数字($O(2^{1024})$级别的数字),因此很显然这里需要上一下LLL——问题是怎么上这个LLL还是个问题。
我们这就来简单地说一下这个是怎么做的。
由于小数与大数的线性组合,我们可以得到
$$
\sum_{i=1}^{20} a_ix_i=S_H
$$
因此,$(a_1,a_2,a_3,a_4,…,a_{20},0)$也是一个小向量,并且在数据规模相差巨大的情况下——可以认为这个是最短向量。
所以我们可以对读入后的$M$矩阵先进行随意打乱,然后随即调整LLL时的参数就可以得到题目中给出的四组解了。
1 | from random import * |
解出所有的key之后,我们就可以根据题目assert的内容,重新调整key中所有数字的内容,这是最终调整出来的真正的key数组:
1 | key=[119, 241, 718, 647, 521, 232, 550, 918, 142, 548, 349, 613, 637, 400, 939, 936, 614, 186, 148, 461, 746, 333, 355, 281, 299, 646, 942, 977, 416, 727, 685, 888, 638, 286, 313, 128, 288, 877, 577, 653, 995, 810, 184, 309, 498, 121, 130, 780, 639, 237, 307, 526, 585, 745, 983, 216, 114, 201, 611, 944, 885, 542, 903, 123, 558, 244, 271, 430, 783, 396, 530, 860, 899, 158, 566, 113, 751, 641, 427, 129] |
解出这个key之后,我们就得到了里面所有的内容,然后看到题目中的代码是Paillier同态加密算法,这个算法有个特点就是它具有同态性。因为它的加密表达式为:
$$
c\equiv g^{m}r^{n} \pmod {n^{2}}
$$
其中$g,r$均为与$n$互质的随机数 ,是加密前已经确定好的内容了。因此我们如果已知$c_1$是$m_1$的加密结果,$c_2$是$m_2$的加密结果,那么$m_1+m_2$的加密的结果就是$c_1c_2$。
所以利用这一性质,我们只需要每次发送一个$m_{99}$,将$c$接收后发送个$c^2$过去,然后除以$2m_{99}^2$,判断一下最后解密出的值在key数组中下标的奇偶性就行了。
1 | from pwn import * |
2.myRSA
题目代码:
1 | # myRSA |
先确定一下这些数字的大小:$p,q$都是$512$位,key
数组中的所有数字都是$1040$位。$x=p^2 (p + 3q - 1 ) + q^2 (q + 3p - 1)$,数量级大概是$1500$多位,$y=2pq + p + q$,数量级大约是$1030$位。
所以$x+y=(p+q)^3-(p+q)^2+(p+q)-4pq$。而$(p+q-1)^3=(p+q)^3-3(p+q)^2+3(p+q)-1$,两者的值非常接近。
所以可以认为$\sqrt[3]{x+y}=p+q-1$。然后对flag
的值除以$(x+y)$即可。而$\dfrac{\ln z}{\ln 2}=129$,因此$z$的值可以直接忽略。
3.RandomRSA
题目就是通过设置random的seed的方法,通过不断生成随机数,每一轮计算一个特定的随机数与str(dp)
进行异或的值。
基本没什么难的内容,直接逆回去就行了,然后直接套已知dp的脚本,不过要用python2.7。
chall.py
1 | from Crypto.Util.number import * |
6.py
1 | from given import *import random |
1.py
1 | from gmpy2 import * |
4. 总结
这三道题还是有点难度的,祥云杯密码学是4道题目,还有一题不是很会做,等待着后期复现吧。。。
想不到大二就这么开始了,8月30日第一天上课,也在补我之前摸的鱼,有点累。