大家好,这里k1rit0,今天带大家了解红帽杯Crypto wp。到底是怎么一回事呢?让我们一起来看看吧。

说起红帽杯,相信大家一定很熟悉,但Crypto是什么呢?就让小编带大家一起了解吧

其实,Crypto就是search,大家可能会惊讶,Crypto竟然就是search!

这就是Crypto wp了,不知道大家有什么想法呢?欢迎在屏幕下方留言哦
https://pwnthem0le.polito.it/2020/12/20/hxpCTF-2020-Hyper-writeup/
https://www.secmem.org/blog/2020/09/20/poka-science-war-hacking/

XD

XD

XD

XD

笑死根本笑不死, 全是有原题, 做的快还不如别人搜的快, 不过第二题超椭圆曲线还在看paper, 现在还是不会(24页, 看都看不懂)

游戏体验极差, 做完题就只能看着队友输出, 逆向爷爷开心到起飞了

就把自己做第一题的思路写一下吧

primegame

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python3

from decimal import *
import math
import random
import struct
from flag import flag

assert (len(flag) == 48)
msg1 = flag[:24]
msg2 = flag[24:]
primes = [2]
for i in range(3, 90):
f = True
for j in primes:
if i * i < j:
break
if i % j == 0:
f = False
break
if f:
primes.append(i)

getcontext().prec = 100 #设置有效数字
keys = []
for i in range(len(msg1)):
keys.append(Decimal(primes[i]).ln())

sum_ = Decimal(0.0)
for i, c in enumerate(msg1):
sum_ += c * Decimal(keys[i])

ct = math.floor(sum_ * 2 ** 256)
print(ct)

sum_ = Decimal(0.0)
for i, c in enumerate(msg2):
sum_ += c * Decimal(keys[i])

ct = math.floor(sum_ * 2 ** 256)
print(ct)

analyses

一看到还以为是小数的背包问题, 怎么可能嘛, 看一下式子就能懂了
$$
ct = 2^{256}(k_0m_0 + k_1m_1 + k_2m_2 + \cdots k_{23}m_{23}) - e
$$
这里多了个$-e$ 就是把取整直接看成减去一个小数$e$了

$k_n$是已知的, 而且是小数, 不能直接造格子, 但我们把$2^{256}$分配给每一项就不一样了, 对于其中一项
$$
2^{256}km = 2^{256}\ln p \cdot m = (\lfloor 2^{256} \ln p \rceil - e’)\cdot m
$$
记$\lfloor 2^{256} \ln p_i \rceil = A_i$每一项都这么干, 那么整个$ct$就会变成
$$
\begin{align}
ct &= A_0m_0 + A_1m_1 + \cdots + A_{23}m_{23} -(m_0e_0’+m_1e_1’+\cdots+m_{23}e_{23}’ + e’’) \\
& = A_0m_0 + A_1m_1 + \cdots + A_{23}m_{23} -E
\end{align}
$$
其中系数$A$都是特别大的数, 而$m,E$都非常小, 这时我们就可以用背包问题的解法求出$m$

构造格子
$$
\begin{pmatrix}
1 & 0 & 0 & \cdots & 0 & A_0 \\
0 & 1 & 0 & \cdots & 0 & A_1 \\
0 & 0 & 1 & \cdots & 0 & A_2 \\
\vdots &\vdots &\vdots &\ddots&\vdots&\vdots \\
0 & 0 & 0 & \cdots & 1 & A_{23} \\
0 & 0 & 0 & \cdots & 0 & -ct
\end{pmatrix}
$$
规约就能得到$(m_0,m_1,\cdots,m_{23},E)$了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from decimal import *
import math
primes = [2]
for i in range(3, 90):
f = True
for j in primes:
if i * i < j:
break
if i % j == 0:
f = False
break
if f:
primes.append(i)
getcontext().prec = 100
keys = []
for i in range(24):
keys.append(math.floor(Decimal(primes[i]).ln()*2**256))
c1 = 597952043660446249020184773232983974017780255881942379044454676980646417087515453
c2 = 425985475047781336789963300910446852783032712598571885345660550546372063410589918

L = matrix([[0 for _ in range(25)] for _ in range (25)])
for i in range(24):
L[i,-1] = keys[i]
L[i,i] = 1
L[-1,-1] = -c1

for i in L.LLL()[0][:-1]:
print(chr(i),end='')
L[-1,-1] = -c2
for i in L.LLL()[0][:-1]:
print(chr(i),end='')