糖醋小鸡块的blog
0%

2024-DASCTF-GFCTF-wp-crypto

发表于 更新于 分类于 Valine：

真难。标$的是赛后也还没做出来的。

The Mystery of Math

题目描述：

1
离散数学的知识你还记得多少？

题目：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from Crypto.Util.number import bytes_to_long, getPrime
from sympy import nextprime, gcd
from random import randint
from CustomNiBoLan import get_pDNF, get_pCNF
from secret import flag, random_proposition
import sys


class Godel:
    def __init__(self):
        self.table = ['﹁', '∨', '∧', '→', '↔', 's', '(', ')', 'p', 'q', 'r', 't']
        self.dict = self.generate_dict()

    def generate_dict(self, max_value=30):
        res = {}
        used = set()

        for k in self.table:
            while True:
                r = randint(1, max_value)
                if r not in used:
                    res[k] = r
                    used.add(r)
                    break

        return res

    def generate_primes(self, count, start=2):
        primes = []
        tmp = start

        while len(primes) < count:
            primes.append(tmp)
            tmp = nextprime(tmp)
        
        return primes

    def translate(self, seq):
        p = self.generate_primes(len(seq))
        gn = 1
        for c, prime in zip(seq, p):
            gn *= prime ** self.dict[c]
        return gn


def encrypt(para):
    p = nextprime(para)
    q = getPrime(512)
    e = 65537
    n = p * q
    m = bytes_to_long(flag)
    c = pow(m, e, n)
    return c, n


if __name__ == '__main__':
    g = Godel()

    plaint = input("请输入命题，例p∧q（最多四个变量）：")

    conj = get_pCNF(plaint)
    disj = get_pDNF(plaint)
    reslist = [g.translate(conj), g.translate(disj)]

    p = g.translate(random_proposition)
    c, n = encrypt(p)
    print(random_proposition)
    print(f'c: {c}')
    print(f'n: {n}')
    print(f'tip: {gcd(*reslist)}')

题目的内容基于离散数学数理逻辑一章，连接上靶机后，靶机会先将以下数理符号：

1
['﹁', '∨', '∧', '→', '↔', 's', '(', ')', 'p', 'q', 'r', 't']

分别对应到1-30的一个数字(数字不可重复)。然后题目允许我们输入一个命题，靶机会计算这个命题的主合取范式与主析取范式。

而对于任意一个命题，靶机有个translate函数，可以将该命题转化成一个素数。这里举个简单的例子，比如对于一个简单命题：

假设在初始化Godel类的时候有如下对应：

1
2
3
( : 15
p : 19
) : 3

那么返回的素数就是：

其中，2、3、5就是从而开始依次生成的小素数。而对于靶机用来RSA加密的模数n，其中一个素数p就是这样translate而来的，只是用于translate的命题是给定的random_proposition这个随机命题。

而我的做法相当简单，注意到当nextprime如果恰好偏移量为1的话，那么p-1就是个光滑数，并且由于知道p-1所有可能的素因子，所以很轻易就能构造出包含所有因子的k(p-1)，然后就可以分解掉n从而解密。

至于nextprime偏移量不一定为1这个问题，只需要反复重连直到刷出这种情况就好。

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
32
33
34
from Crypto.Util.number import *
from sympy import nextprime
from pwn import *

#context.log_level = 'debug'

t = 1
a = 2
for i in range(20):
    t *= a**150
    a = nextprime(a)

while(1):
    sh = remote("node5.buuoj.cn",28758)
    sh.sendline("p".encode('utf-8'))

    sh.recvuntil(b"random_pro: ")
    random_pro = sh.recvline().decode('utf-8')
    sh.recvuntil(b"c: ")
    c = int(sh.recvline().strip().decode())
    sh.recvuntil(b"n: ")
    n = int(sh.recvline().strip().decode())
    sh.recvuntil(b"tip: ")
    tip = int(sh.recvline().strip().decode())

    if(GCD(pow(2,t,n)-1,n) != 1 and GCD(pow(2,t,n)-1,n) != n):
        p = GCD(pow(2,t,n)-1,n)
        q = n // p
        phi = (p-1)*(q-1)
        d = inverse(65537,phi)
        print(long_to_bytes(pow(c,d,n)))
        exit()
    
    sh.close()



Sign-in by quantum computer

题目描述：

1
You can get the flag by running it on a quantum computer.

题目：

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
# The code is compressed by an algorithm
import hashlib

'''
I have a quantum computer and I use it to solve some of the problems in my work. The following is part of my work.
In order to protect the privacy of my work, all variable names have been replaced with simple letters. 
I believe you have also a quantum computer. Now please prove to me that you have a quantum computer.
'''

n = lambda q, r: q % r
x = lambda y, z: y**z
i = lambda j, k: j if not k else i(k, n(j, k))
l = lambda m: 1 if not m else m * l(m-1)
o = lambda p: x(2, p)
op = lambda p: o(p)+1
os = lambda p: o(p)-1
oh = lambda p: p*o(-1)
xp = lambda y, z: x(y, z)+1
xs = lambda y, z: x(y, z)-1
xt = lambda y: x(y, 2)


a1 = o(17*o(9))
a2 = os(a1)
b1 = o(17)
b2 = os(b1)
b3 = b1-1+o(10)-o(5)+17
b4 = os(b3-1)
c1 = o(o(13))
c2 = os(c1)
d = i(a2, c2)
e = i(b2, c2)
f1 = i(d+2, e+2)
f2 = xt(l(os(b3-2)))
f3 = xt(n(f2, b4))
f4 = 2*n(f3, b4)
f = f4*op(a2+f1+f4)
g = i(xp(f, a1), xs(f, c1))
h = x(x(xt(f1)*g, oh(f)*f4), b2)
flag = hashlib.md5(str(h)[1-b1:].encode()).hexdigest()
print(flag)

题目描述需要用量子计算机来高速跑出这个程序结果，因为直接用自己电脑的话，很容易就发现这个数量级要跑是完全不行的。实际上，这是一个很纯粹的数论问题，任务是利用各种数论定理来简化计算步骤，从而达到求解本题的目的。

题目的各个lambda函数意义都比较简单，所以不在这里一一列出来说，直接先以直观形式写出一些基本量：

然后接下来就是要简化的部分了。

d、e

由题意可以看出，函数i是求两数gcd的意思。那么也就有：

可以看出，d、e其实都是在对如下形式的两个数字求gcd：

而对于这种数字显然可以利用平方差进行分解：

同时，对于分解得到的式子，可以发现第二项可以继续利用平方差公式分解。因此，只要有m>n成立，那么一定有：

也就是：

所以其实d、e的求解其实是指数上的一个比大小问题，由于有：

所以有：

f1

f1依然是求gcd：

由上面的计算结果也就有：

这本质上是两个费马数，而任何两个不相同的费马数都是互素的，因此f1=1。

费马数是指如下形式的数：

取任意两个费马数a、b，如果他们两个不相等则一定互素，证明如下：

设：

并记a、b的最大公约数为d。不妨令m大于n，此时由之前求d、e的部分，可以知道下式成立：

又因为：

所以：

d是a、b的公约数，所以肯定也有：

由整除的性质就有：

但显然a、b都是奇数所以d一定不是2，所以d为1，所以a、b互素。

f2、f3、f4

在f2、f3、f4的计算中，函数l为计算阶乘，n为取模，xt为求平方，所以f2、f3、f4可以写为：

看到阶乘，并且看到后面的取模操作，自然想到的就是威尔逊定理。

威尔逊定理内容为：

  • 当p是素数：
  • 当p不为素数$(p \neq 4)$：
  • 当p=4：

由于f2并没有取模，数量级相当大。所以能够想到的是直接去计算有取模的f3、f4。经过检验可以知道，其模数：

并不是一个素数。不过为了清楚起见，这里我还是把b4写成p，那么f4就是：

其实也就是：

可以看到式子内部并不是p-1，他除以了一个2，所以其缺失了后面一半的数，这就需要对威尔逊定理做一点变形。具体来说，由于p不是素数，所以有：

把这个式子以$\frac{p-1}{2}$为界，分为前后两半得到：

可以发现，两部分均恰好有$\frac{p-1}{2}$个数字，而对于第二部分的每个数字，在模p下都可以用第一部分的数字进行如下表示：

把所有负号提出来就能得到：

所以当p不是素数时，在模p下应该有：

所以可以推出：

这两个0是整个题目最奇怪的地方。

f、g

由于有：

1
2
f = f4*op(a2+f1+f4)
g = i(xp(f, a1), xs(f, c1))

因为f4=0，所以f=0。因此有：

之所以这里不把i写成gcd，是因为有负数的引入，辗转相除时可能会碰到问题。所以这里直接调题目的函数i可以得到他的计算值是-1。

h、flag

这一部分的代码为：

1
2
3
h = x(x(xt(f1)*g, oh(f)*f4), b2)
flag = hashlib.md5(str(h)[1-b1:].encode()).hexdigest()
print(flag)

代入之前的值进去计算，可以得到h=1这个事实。然而如果h=1的话，最后计算flag的这一部分就显得很奇怪：

1
str(h)[1-b1:]

这个式子可以看作是在取h这个数值的末(b1-1)个十进制位，换句话说，在计算h的过程中进行的b2次方的操作，其实可以写成类似如下的形式：

所以感觉按预期来说，这里应该是想考一个模幂运算，从而使得大到b2这样数量级的幂运算能够计算。因此k应该不会是1这种简单的数字才对。

然而的确没看出哪一步出了问题，如果推理没有错误的话，那么感觉最大的可能性是威尔逊定理那一步当成了素数去计算从而得到了f4=2，从而继续下一步计算。


那么接下来，我们不妨假设f4=2，从而进行下一步计算。由于f2、f3不会参与后续计算了，因此也不需要关心它们的值。

f、g

当f4=2时有：

即：

这里不把a2展开，是因为展开的话实在太繁琐了，所以先把a2留在指数上进行下一步运算，此时有：

这里乍一看可能会觉得和前面求d、e的步骤有点类似，因为可以对第二个求平方差从而不断分解他。但问题在于第二个数应该是大于第一个数的，所以平方差分解后得到的项并不会包含第一个数，因此两者gcd不是第一个数。

那么就要想其他办法，这里需要注意到一个事实：

由于有这个关系，那么我们不妨先不把f展开写，也就是：

化简一下：

由于指数运算的顺序，先运算的应该是最右上角的部分，所以这样拆下来是没有问题的。

可以用一些小的，能运算的值来check：

1
print(2^(2^(2^3+2^2)) == 2^(2^(2^3)*2^(2^2)))

这个时候令：

就有：

由辗转相除本身得到：

而又因为：

此时可以两两配对得到：

所以：

就得到：

又因为f是偶数，所以t是偶数，因此t-1是奇数。

这代表着，在令f4=2以后，我们仍然得到了g=1！那么h显然又是1，又没法做了！

h、flag

这样吧，我们不妨再令g=2然后继续下一步，那么有：

然而，这里的f显然和我们求的不太一样，因为只有f是奇数的时候才有可能得到g=2这个事实，然而我们的f是偶数，并且还是个很大的偶数，实在不知道怎么继续下去了。

这个时候，我们不妨令f=3，那么就有：

然后就可以得到flag了XD：

1
DASCTF{ba4078b01d4432f7a3a73145dd31485c}

image-20240424095858807

碎碎念

赛后和 @yolbby 一起推了好一会儿，发现的确如他所说，这段代码问题不少。这种题目本身相当容易错，不仅仅是对解题人，更是对出题人而言。

题目中的几个不妨，是赛后和harukii交流了一下发现题目确实有错误，并且理顺之后发现错误还是好几个，所以才能这样不妨的。



$ Freedom and Captivity

题目描述：

1
2
3
You can get flag by shuttling back and forth freedom and captivity.

hint：https://www.sciencedirect.com/science/article/pii/S0747717185710425

题目：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import os
from Crypto.Util.number import *
from Crypto.Math.Numbers import Integer
import random
import hashlib
import signal

H = lambda om: int(hashlib.sha256(om).hexdigest(), 16)
flag = os.getenv("DASFLAG", "flag for gfctf2024, the problem comes from atcry241")
signal.alarm(60)

tm = b'ATCRY241: Freedom and Captivity'
black_list = [H(tm)]

class Sign:
    @staticmethod
    def check(x, l, u):
        x = Integer(x)
        if x.size_in_bits() < l or x.size_in_bits() > u or x.is_even() or x.is_perfect_square():
            return False

        nd = lambda y: -y - 2 if y > 0 else -y + 2
        d = 5
        while True:
            if x == d or x == -d:
                d = nd(d)
                continue
            js = Integer.jacobi_symbol(d, x)
            if js == 0:
                return False
            if js == -1:
                break
            d = nd(d)

        x = int(x)
        k = x + 1
        ui, vi, ut, vt = 1, 1, 0, 0
        for i in range(k.bit_length() - 2, -1, -1):
            ut = ui * vi % x
            vt = (((vi ** 2 + (ui ** 2 * d)) * k) >> 1) % x
            if (k >> i) & 1:
                ui = (((ut + vt) * k) >> 1) % x
                vi = (((vt + ut * d) * k) >> 1) % x
            else:
                ui, vi = ut, vt
        return ui == 0

    def checkall(self):
        check = self.check
        e, d, h, p, z, s, _ = self.key
        assert check(p, 2 ** 11, 2 ** 12) and check(z, 11, 56)
        assert check(d, int(3.78**3.78), int(3.87**3.87)) and check(e, 1022, 1152)
        assert (e - 1) % d == 0 and pow(h, d, e) == 1
        assert h.bit_length() >= 1022 and h < e

    def __init__(self):
        p, e, d, h, z = [int(i, 16) for i in input("param:").split('-')]
        s = random.randint(1, d // z**2) * z**2
        f = pow(h, s, e)
        self.key = [e, d, h, p, z, s, f]
        self.checkall()
        print(f)

    def sign(self):
        e, d, h, p, z, s, _ = self.key
        ml = H(input("m:").encode())
        global black_list
        assert ml not in black_list
        black_list += [ml]
        r = random.randint(1, d - 1)
        return pow(h, r, e) % d, pow(inverse(r, d) * (ml + s * pow(h, r, e) % d) % d, z, p)

    def verify(self):
        e, h = [int(i, 16) for i in input("param:").split('-')]
        d = self.key[1] + 2
        while not self.check(d, int(3.78**3.78), int(3.87**3.87)):
            d += 2
        f = pow(h, random.randint(1, d - 1), e)
        self.key[:3] = e, d, h
        self.checkall()
        sig1, sig2 = [int(i, 16) for i in input("sig:").split('-')]
        assert sig1 * sig2 > 0
        assert (pow(h, H(tm) * inverse(sig2, d) % d, e) * pow(f, sig1 * inverse(sig2, d) % d, e) % e) % d == sig1
        print(flag)


def menu():
    print("[1] Gain freedom")
    print("[2] Free the captivity")
    cc = int(input("which: "))
    return cc


def main():
    print("Freedom is the wings of the soul, and captivity is the grave of hope.")
    s = Sign()
    while True:
        print(s.sign() if menu() == 1 else s.verify())


main()
try:
    main()
except:
    print("something bad!")

完全没看懂这个验签流程，更别提怎么利用伪素数去伪造了。



Light and Darkness

题目描述：

1
You can get flag by shuttling back and forth light and darkness.

题目：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import random
import string
import sys
from Crypto.Math.Numbers import Integer
from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
import signal

signal.alarm(120)
flag = os.getenv("DASFLAG", "flag for gfctf2024, the problem comes from atcry242")

def proof_of_work():
    t = ''.join(random.sample(string.ascii_letters + string.digits, 3))
    print(f"your username is {t}")
    try:
        s = int(input("input your work proof:"), 16)
        assert s < 2^32
        random.seed(s)
        y = ''.join([chr(x) for x in random.randbytes(3)])
        assert y == t
    except:
        print("you proof nothing...")
        sys.exit()
    print(f"Hello {t}, Let's tangle together in light and darkness.")

def check(x):
    if Integer(int(x)).is_perfect_square():
        return False
    m, a = x - 1, 0
    while m & 1 == 0:
        m >>= 1
        a += 1
    for i in range(20):
        b = 1
        while b in (1, x - 1):
            b = Integer.random_range(min_inclusive=int(2), max_inclusive=int(x-2), randfunc=random.randbytes)
        z = pow(int(b), m, x)
        if z in (1, x - 1):
            continue
        for j in range(1, a):
            z = pow(z, 2, x)
            if z == x - 1:
                break
            if z == 1:
                return False
        else:
            return False
    return True

def param(init, r, s=2, l=688, u=1688):
    p = init - 3
    while not check(p):
        p = random.randint(l, u) if r else p + s
    return p

class Sign:
    def __init__(self):
        q = param(2^22, False)
        b = param(2^14, False)
        n = param(2^10-1, True) // 2
        w = param(2^3, True, l=2^2, u=2^4)
        F.<x> = PolynomialRing(GF(q))
        F.<x> = F.quotient(x^n-1)
        rp = lambda m: sum(randint(-m, m) * x**i for i in range(n))
        ph = lambda p, m: sha256(b''.join(long_to_bytes(int(p[i]), 3) for i in range(n)) + m).digest()
        hp = lambda h: sum(((1 << i) & bytes_to_long(h) != 0) * x**i for i in range(n))
        ep = lambda p : b''.join(long_to_bytes(int(p[i]), 3) for i in range(n)).hex()
        dp = lambda p : sum(bytes_to_long(p[i: i+3]) * x ** (i // 3) for i in range(0, 3*n, 3))
        a = rp(q // 2)
        s, e = rp(1), rp(1)
        t = a * s + e
        self.pri = (s, e)
        self.pub = (a, t, n, q, b, w)
        self.fcn = (rp, ph, hp, ep, dp)
        print(ep(a)+ep(t))

    def verify(self, m, sig):
        a, t, n, q, b, w = self.pub
        _, ph, hp, _, dp = self.fcn
        z1, z2, c = [dp(bytes.fromhex(i)) for i in sig]
        for i in range(n):
            if min(z1[i], q - z1[i]) > b - w:
                return False
            if min(z2[i], q - z2[i]) > b - w:
                return False
        return hp(ph(a * z1 + z2 - t * c, m)) == c

def main():
    print("There is light even in the darkest places.")
    proof_of_work()
    try:
        light, dark = Sign(), Sign()
        ls, ds = input("light = ").split('-'), input("dark = ").split('-')
        m1 = b'ATCRY242: Light and Darkness'
        m2 = m1 + b' Darkness cannot drive out darkness, only light can do that. ' + m1[::-1]
        assert light.verify(m1, ls) and dark.verify(m2, ds)
        print(flag)
    except Exception as e:
        print("something bad!")

main()

题目是基于RLWE的签名方案，需要伪造出两个给定消息的签名从而得到flag。这个签名方案可以在wiki上找到标准实现流程：

https://en.wikipedia.org/wiki/Ring_learning_with_errors_signature

其主要过程如下：

image-20240422212351394

与代码对比着看，可以发现代码的实现和这个基本上是完全一致的(不排除有小细节没有注意到)，唯一的区别在于，用于签名的多项式环是：

而标准实现中是：

回到题目，如果我们想要伪造一个消息的签名，也就是找到合理的$z_1(x),z_2(x),c(x)$，使得下面的式子成立：

由于对于公钥a、t有：

所以一个自然的想法是，如果能通过上面这个rlwe得到私钥s，那么自然就能伪造出下面这样的合法签名：

显然z1,z2符合小系数多项式的要求，所以只要能解这个RLWE得到私钥，就可以通过题目得到flag。

而x^n-1这样的可约多项式环就提供了解RLWE的便利，和前段时间L3HCTF的RLWE概念相似，对于这样的环，在n是偶数时可以利用平方差分解成多个易于规约的子环来分开解rlwe，再最后crt起来就可以得到私钥。而题目两个消息的签名中，n会在344-844中随机选择，如果两次都随机到n较小的情况，实际crt的操作中，最大的复杂度就只需要解模多项式的度不到两百次的RLWE实例，是有机会的。

然而题目限时比较紧，120s需要伪造两个消息，虽然说两次可以多进程来做，实际上是120s内解一个RLWE(proof of work可以预先建字典解决，所以不怎么占时间)，不过这个时间还是相当紧张。

而对于这个签名，不解出私钥而进行的签名伪造攻击也是存在的，就在上方wiki的参考文献里：

https://web.archive.org/web/20170828012937/https://eprint.iacr.org/2017/766.pdf

其中section 5.3的Forgery attack就描述了这种情况。

不过无论怎么说，要这样伪造的话，格规约应该是免不了的一步，而题目里制约这种方式的就是限时120s，实在太紧张了。也许是题目代码里有其他小trick也说不定。

相比起上一个签名题目，这个签名的check虽然也是一个素性检测，但很明显他就是一个Miller_Rabin素性测试，并且也没有需要自己构造的参数，所以应该没啥能利用的地方


这题其实有一个很有意思的核心思路如下。

对于通常模多项式为$x^{2n}-1$类型的RLWE，做法是分解成子环然后crt起来，所以一般来说会想着这么分解：

题目延伸出这样一步，对于n不为2的幂次的时候，x^n+1和x^n-1其实在ZZ上都是继续可分的，比如对于x^120-1，可以看到他的分解是：

image-20240424101116220

这是很神奇的一个事情，因为按我们的预料来说，分解后还会有个x^60+1的模多项式下的crt，也就是会有一个121维的格(为什么会是这么大可以见NSS Round18我的题解)。然而，由于x^60+1继续可分，所以最后留下来的最高次项也仅有32次，所以最大的格也只会是65维的，就方便求解多了。

这样的分解就给完成题目提示了两方面：

  • 找到一个在ZZ上分解后次数都较小的n
  • 想办法让n通过check

而题目奇怪的proof意义也在于此。看上去他只是要产生一个种子使其生成特定字符串，然而要注意到，proof里面会把你输入的种子设置成随机数种子，这会使之后所有的随机数部分都不再随机。也就是说我们可以利用这一点，去构造一个随机数种子，使得其能够让一个特定的数字通过check的miller rabin素性测试(这个特定的数字就要满足：由其得到的n使分解后多项式次数都较小)

如此一来就可以完成整个题目。然而这样看下来，这个题目的体量对于短时赛来说过于大了，前面套的MT的伪随机数预测和伪素数实在是难以让人直接想到怎么利用。

不过这个RLWE的crt思路是相当值得学习的，这也从另一个角度说明为什么通常RLWE要选择x^512+1,x^1024+1这样的模多项式，才能满足安全要求。