JNU-Xp0int 新生赛 Crypto WP

RSAstudy1

题目一共有4个问题。

已知n,d,c，求m.
$m = c^{d} \mod n$
懂？
已知n,e,c，求m.

这种就是正常的使用RSA，如果没有什么问题是没办法求m的。但这里用的n太小了，可以直接分解出p,q。用分解出的p,q求d，然后就跟1.一样了。

已知n,e,c，求m.

这里能求m是因为选的e太小了。
$m^e = c \mod n$
e太小导致 $m^{e} < n$ ，所以直接对c开5次方就行了。
已知p,q,c，求m.

很明显这里缺了一个e，看代码就知道e的位数是20位。24位以内的数爆破都不会很久的，除非每一轮的操作非常复杂。

直接爆破e，然后求d就行了。求出了d就跟1.一样了

RSAstudy2

RSAstudy3

2和3其实都是wiener's attack。2给的是普通的只给一个 $e$ 的wiener's attack。只给一个 $e$ 的可以用连分数的做法去做，但事实上大家肯定都能搜到一堆奇怪的库和脚本直接秒掉。如果对原理感兴趣的可以看看下面这个论文

Extending Wiener's Attack in the Presence of Many Decrypting Exponent

3的话就是Extending wiener's attack了，上面的那个论文主要说的也就是这个东西。具体的推导过程也不说了，有兴趣的自己去看吧，上面那个论文说的挺详细的。

具体怎么做呢。

两道题题目都差不多，开头的一堆奇怪的计算只是为了生成能够用wiener‘s attack的题目数据，因为wiener's attack只有当 $d < N^{\alpha}$ 时才能使用，这里的 $\alpha$ 跟给的 $e$ 的个数有关，也就是这两题的区别，一题给了一个，一题给了两个。

第一题就不说了，到处都是脚本和库，说一说第二题。

第二题具体还是得用格这个玩意，根据论文里提到的，我们可以把等式

d_1ge_1 - k_1N =g +k_1s, \\ k_1d_2e_2 - k_2d_1e_1 = k_1 - k_2,\\ d_1d_2g^{2}e_1e_2 - d_1gk_2e_1N - d_2gk_1e_2N + k_1k_2N^2 = (g + k_1s)(g+ k_2s)

写成矩阵的形式，然后就有

(k_1k_2,d_1gk_2,d_2gk_1,d_1d_2g^2) \begin{pmatrix} 1&-N&0&N^2\\ 0&e_1&-e_1&-e_1N\\ 0&0&e_2&-e_2N\\ 0&0&0&e_1e_2 \end{pmatrix} \\= (k_1k_2,k_2(g+k_1s),k_1-k_2,(g+k_1s)(g+k_2s))

怎么写成下面这个有矩阵的等式的，只能说做多了格的题才能快速的看出等式左右两边是啥吧，可以试试手动算一下，左边相乘以后根据上面的三行式子，是不是刚好就是等式右边的那个向量。

到这里以后，其实要构造的格就是那个矩阵，格基规约以后就能得到等式右边的向量

(k_{1} k_{2}, k_{2} (g + k_{1} s), k_{1} - k_{2}, (g + k_{1} s) (g + k_{2} s))

然后求公因数得到 $k 1, k 2, g, s$ ，再代入上面的三行等式就能求 $d_{1}, d_{2}$ 了。

DoUknowLattice

背包问题，直接进入正题。

把 $f l a g$ 看成 $s_{0} ， s_{1}, s_{2}, . . ., s_{i}$ ，也就是每个字符都转成ascii码。

那题目给出的等式其实就是

A_0s_0 + A_1s_1 +A_2s_2 +\cdots+A_is_i - SUM = 0

跟上面RSAstudy3中的把等式写成带矩阵的等式一样，我们可以根据上面那行等式写出下面的式子

(s_0,s_1,s_2,\cdots,s_i,-1) \begin{pmatrix} 1&0&0&\cdots&A_0 \\ 0&1&0&\cdots&A_1 \\ 0&0&1&\cdots&A_2 \\ \vdots&\vdots&\vdots &\ddots&\vdots \\ 0&0&0&\cdots&A_i \\ 0&0&0&\cdots&SUM \end{pmatrix} = (s_0,s_1,s_2,\cdots,s_i,0)

对矩阵格基规约就能得到右边的向量了。

在用sagemath的LLL算法格基规约的时候，会遇到第一行不是目标向量的情况，因为题目选的格并不是特别大，所以会有很多短向量，右边的向量只是短向量中的一个。

如何判断哪个才是自己想要的向量呢？看末尾的0就行了，哪一行末尾是0哪一行就是了。

treasure

这道题需要解开五个盒子中的四个盒子，拿到四个点坐标并还原曲线得到 $S$ 。

box1

ROT13 + 栅栏密码

box2

摩斯电码，大小写对应.-

box3

简单的单表替换，词频攻击就行了

https://quipqiup.com/ 扔进这里面就好了

box4

base64 32 16套娃，根据base的表，16能解码的，32和64一般都能解码。32能解码的64一般能解码，而64能解码的就只有64能解码。

所以拿到编码以后的字符串之后，先用16解码，不行就用32解码，还不行就用64解码，直到解不出可打印字符串。

from base64 import b64decode,b32decode,b16decode

with open('key.base','r') as f:
    text = f.read()

while True:
    try:
        text = b16decode(text).decode()
    except:
        try:
            text = b32decode(text).decode()
        except:
            try:
                text = b64decode(text).decode()
            except:
                print(text)
                break

box5

键盘密码

final

最后，当你解完上面的五道题以后，要么你就用计算器慢慢按，在纸上解出 $S$ ，要么就用sagemath这个工具去解，要么就用python的z3-solve库去解。

proof_of_work

这个是大部分交互题都有的一部分，proof_of_work，几乎所有的交互题都会有这一部分来防止选手进行爆破答案等操作。

题目需要我们给出四字节的字符串，该字符串在拼接以后进行sha256，并且得到的结果要和服务端给的结果一致。

其实四字节的字符串直接爆破就行了，这里主要是想让大家试试怎么写交互题的脚本，虽然这里手打也没事，但以后的题可能就不是输入一次，而是几十次几百次的时候，手打就是纯傻杯好吧。

from hashlib import sha256
import pwn
import re

String = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz'
con = pwn.remote('35.229.138.83',10001)
resp = con.recv(1024).decode()
END = re.findall('\+(.*)\)',resp)[0]
HASH = re.findall('\=\= (.*)',resp)[0]
print(END,HASH)

for i in String:
    for j in String:
        for k in String:
            for l in String:
                s = i+j+k+l+END
                if sha256(s.encode()).hexdigest() == HASH:
                    print(sha256(s.encode()).hexdigest())
                    con.sendline(i+j+k+l)
                    resp = con.recv(1024).decode()
                    print(resp)