writeup-for-2021-redhat CTF

Posted on Edited on In Word count in article: 2.6k Reading time ≈ 2 mins.

大家好，这里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

一看到还以为是小数的背包问题, 怎么可能嘛, 看一下式子就能懂了

这里多了个 就是把取整直接看成减去一个小数了

是已知的, 而且是小数, 不能直接造格子, 但我们把分配给每一项就不一样了, 对于其中一项

记每一项都这么干, 那么整个就会变成

其中系数都是特别大的数, 而都非常小, 这时我们就可以用背包问题的解法求出

构造格子

规约就能得到了

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='')