NKCTF 2024 Crypto Writeups

字数统计: 5.6k字   |   阅读时长≈ 30分

最终排名第一，NKCTF 2024 所有 crypto 赛题的题解。

电脑打比赛最累的一集（确信）。这次 crypto 有两题随便写的 exp 要跑近 100 h，最后好歹优化到单核 2h 内能跑完。

 

eZ_Math

 

题解

有如下关系：

1
2
3
4
5
6
7
8
9
10
11
n = p * q * r * s
x = pow(q + r, p, n)
y = pow(p * q + r, p, n)
z = pow(s + 1, m1, s ** 3)
-->
(1). (x-y) | q
(2). y = k1 * p + r 
(3). x = k2 * p + q + r
(4). x - y = (k2-k1) * p + q
-->
(5). (x-y-q)|p , (x-y-q)|q
  1. Step 1 可以得到 q 。
  2. Step 2 得到 q 之后，由 (5) 我们 可以得到 ，从而得到 和 。
  3. 从 (2) （概率性），从而分解 。

 

解密：

  1. flag 第一部分的加密一个简单的 上的离散对数，由于指数不大于 , 直接二项展开求 log，或者用 sage 内置的 p-adic rings 求 log 即可。
  2. flag 第二部分在模 的有限域上求解，因为指数 与 不互素，需要开 次根，这里也直接 sage 求解就行。

 

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 Crypto.Util.number import *

n = 16063619267258988011034805988633616492558472337115259037200126862563048933118401979462064790962157697989038876156970157178132518189429914950166878537819575544418107719419007799951815657212334175336430766777427972314839713871744747439745897638084891777417411340564312381163685003204182743581513722530953822420925665928135283753941119399766754107671729392716849464530701015719632309411962242638805053491529098780122555818774774959577492378249768503656934696409965037843388835948033129997732058133842695370074265039977902884020467413323500218577769082193651281154702147769044514475692164145099161948955990463002411473013
x = 3021730035236300354492366560252387204933590210661279960796549263827016146230329262559940840168033978439210301546282150367717272453598367244078695402717500358042032604007007155898199149948267938948641512214616076878271433754986480186150178487625316601499002827958344941689933374158456614113935145081427421623647242719093642478556263121508238995676370877385638074444859047640771188280945186355013165130171802867101829647797879344213688981448535289683363612035513789240264618036062440178755665951650666056478493289870170026121826588708849844053588998886259091357236645819074078054595561158630194224419831088510266212458
y = 8995787142441643101775260550632842535051686960331455373408888374295557050896156890779515089927839904014859222004906681231525326673182671984194300730575609496770604394218160422560576866112460837985407931067753009696969997384839637927957848613356269534870170452152926447601781637641134982178028922559652443398183848786034348994249923007092159192374765197460466878587635412657807328348343062302127490267456095927890461140420639805398464266081441243108883599713672104446500850203779995739675784794478089863001309614674686652597236324659979849324914804032046113978246674538411441434320732570934185579553749616238819583998
z = 1283646988194723153191718393109711130382429329041718186548715246082834666179475883560020086589684603980734305610989683434078096863563033623169666389076830792095374856743015929373461198718962686411467443788047511292138922700655772772117855226419561159782734009961921473456332468653898105909729309377890721920937410781006337057478451806364879679045839945032594716202888196404203782734864187890231653321470085251
c = 4988583141177813116287729619098477713529507701428689219486720439476625736884177254107631282807612305211904876847916760967188201601494592359879509876201418493870112712105543214178376471651715703062382025712952561985261461883133695993952914519494709871429166239968478488380137336776740647671348901626710334330855078254188539448122493675463406596681080368929986034772169421577420193671300532508625180845417164660544286332963072804192276425664877337357353975758574262657585309762422727680851018467657523970318042829660721433987195369353660020476598195375492128671951807024027929490113371463210453342974983253996717176870

q = gcd(y-x, n)
n1 = gcd(x - y - q, n)
p = n1 // q
n2 = n // n1
r = gcd(y%p, n)
s = n2 // r
assert p * q * r * s == n

R = Zp(s, prec=3)
m1 = int((R(z).log() / R(s+1).log()).lift())
f1 = long_to_bytes(m1)

G = GF(p)
phi = (p-1)*(q-1)*(r-1)
g = gcd(s-1, p-1)
d = ZZ(inverse_mod(0x10001 *(s-1)//g, p-1))
cd = G(pow(c, d, p))

PR.<x> = PolynomialRing(G)
f = x^4 - cd

for r in f.roots():
    print(f1 + long_to_bytes(int(r[0])))

 

GGH

 

EXP

整个加密过程很简单：

问题出在 error 向量 的生成方式，熵太小了，穷举即可解出秘密向量 ，审计源码可知，Delta 的值只能是 1，3，7，对应 error 只有三种可能。于是直接爆破 error ，解 Z 上的线性方程组即可。

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
import re
def filter_numbers(text):
    # include negative numbers
    return [int(x) for x in re.findall(r'-?\d+', text)]
    
def read_mat(file):
    with open(file) as f:
        lines = f.readlines()
        mat = [filter_numbers(line) for line in lines]
        return mat
def get_error(n,delta):
    k = 4*delta -2
    tmp = []
    tmp += [delta - 2]*(n//k)
    tmp += [delta - 1]*( ((k-2)*n) // (2*k))
    tmp += [delta]*(n//k)
    tmp += [delta + 1]*( ((k-2)*n) // (2*k))
    return tmp

n = 260    
pk = read_mat('pubkey.txt')
ct = eval(open("./ciphertext.txt", "r").read().strip())
W = matrix(ZZ, pk)
c = vector(ZZ, ct)

for delta in [1,3,7]:
    e = vector(ZZ, get_error(n, delta))
    sol = (W).solve_left(c - e)
    if sol[0].is_integer():
        print(sol)
        print(bytes(sol[:50]))

 

EZ-random

 

题解

这题思路其实很容易，但是实现上需要考虑挺多优化上的细节（当然不排除我的做法是非预期 orz）。

题目给出的数组 T 和 R 实际上对应了 上的线性方程，即未知的 key 是 64 byte，即 512 比特。T , R 给出了二元域 上 个关于 key 的线性方程。 表示取第 个比特，则第 个方程如下，

那么我们还需要 64 个方程才能完全恢复出 64 字节的 Key。考虑到 key 的生成方式，如果不加入随机性的话， 它是线性的，相邻两个字节可以提供 8 个线性方程。可惜加入随机的 offset 之后，我们无法建立确定性的线性方程。

好好好，那么就考虑爆破吧！猜测某个 state 的状态（256 个），爆破后面 7 轮的 state，我们能够得到额外 64 格比特信息，配合前面的方程信息，刚好能够解出所有比特，此时检查 key 的合理性即可。理想的复杂度是 ： ，拿 python plus 版本的 pypy 跑应该没问题。

 

实际上 exp 写出来的复杂度 ，因为题目给出数据在前面 个方程上进行部分高斯消元的形式不完美，为了高效计算，舍弃了 8 个消元后的方程，虽然这些方程也能用起来，但是比较麻烦，于是增加一点点暴力穷举的工作量。比赛时候的 exp 在 i7-13700 上用 pypy 3.10 单核预估时间 , 也就 6 个小时，开 8 核并行一下，运气不错很快出来了。写 wp 时优化了一下，每个子进程只需要 20 s，单核缩短到 1 h。

1
2
3
4
5
6
7
8
9
$ pypy.exe exp.py 96 128
[+] try state0 96 in range 96 to 128
16777216it [00:19, 868396.44it/s]
[+] try state0 97 in range 96 to 128
16777216it [00:22, 745091.61it/s]
[+] try state0 98 in range 96 to 128
16777216it [00:20, 834502.70it/s]
[+] try state0 99 in range 96 to 128
5712792it [00:06, 868110.74it/s]b'NKCTF{1ab1e94f-a699-431b-8f17-8aabdea55ec6}\x05\x05\x05\x05\x05'

 

EXP

高斯消元 448 个方程，512 个变量，得到前 440 个比特的表达式（以后 64 + 9 = 72 个比特为未知元），比较完美的高斯消元形式应该可以把前 448 个比特用后面 64 个未知元表示。

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
# sage
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long
from Crypto.Cipher import AES
from hashlib import sha256
from itertools import product
from tqdm import tqdm

def next_state(state, offset):
    state = (state >> offset | state << (8 - offset)) & 0b11111111
    state = state ^^ 0b11000001
    return state

def is_valid_consistent_key(s1, s2):
    for shift in range(8):
        if next_state(s1, shift) == s2:
            return True
    return False

EncryptedFlagHex = "a9ebc27bdc700ff2fb68489dc63196fa35ec4ceecb9e7981e8bf8420d3fb3117bbc8fe290f163ccc31f9365bf795b728"
EncryptedFlag = bytes.fromhex(EncryptedFlagHex)
T = "..."
R = "..."

BoolPoly = BooleanPolynomialRing(64 * 8, [f"x{i}" for i in range(64*8)])
xs = list(BoolPoly.gens())
rs = ZZ(R).digits(base=2, padto=64 * 7)[::-1]
eqs = []
poly_eqs = []
for t,r in zip(T,rs):
    coeffs = ZZ(t).digits(base=2, padto=64 * 8)[::-1]
    poly = sum([coeff * x for x, coeff in zip(xs, coeffs)]) - r
    poly_eqs.append(poly)
    eqs.append(coeffs + [r])

J = matrix(GF(2), eqs).echelon_form()

unknown_bits = 64 + 8
known_bits = 512 - unknown_bits
nice_rows = []
nice_nums = []
for i,row in enumerate(J):
    if i >= known_bits:
        break
    coeff = list(row[-(unknown_bits + 1):])
    if row[i] != 1: print(f"check mat {GB[i] = } {i = }")
    nice_rows.append(coeff)
    nice_nums.append(ZZ(coeff[::-1], 2))

print(f"{nice_nums = }")

 

最终 exp （8 核命令行手动并行）

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
# -*- coding: utf-8 -*-
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long
from Crypto.Cipher import AES
from hashlib import sha256
from itertools import product
from tqdm import tqdm

def next_state(state, offset):
    state = (state >> offset | state << (8 - offset)) & 0b11111111
    state = state ^ 0b11000001
    return state

def is_valid_consistent_key(s1, s2):
    for shift in range(8):
        if next_state(s1, shift) == s2:
            return True
    return False

EncryptedFlagHex = "a9ebc27bdc700ff2fb68489dc63196fa35ec4ceecb9e7981e8bf8420d3fb3117bbc8fe290f163ccc31f9365bf795b728"
EncryptedFlag = bytes.fromhex(EncryptedFlagHex)
T = "..."
R = "..."
nice_nums = ["..."]

# guess offset
# bf = (product(list(range(8)), repeat=8))
unknown_bits = 64 + 8
assert len(nice_nums) == 512 - unknown_bits

import argparse
if __name__ == "__main__":
    # parse paras from command line ./exp.py p1 p2
    # run example: python3 exp.py 0 256
    parser = argparse.ArgumentParser()
    p1 = parser.add_argument("p1", type=int)
    p2 = parser.add_argument("p2", type=int)
    args = parser.parse_args()
    p1 = args.p1
    p2 = args.p2

    for state0 in (range(p1, p2)):
        print(f"[+] try state0 {state0} in range {p1} to {p2}")
        bf = (product(list(range(8)), repeat=8))
        for shifts in tqdm(bf):
            states = bytes([state0])
            state = states[-1]
            for shift in shifts:
                state = next_state(state, shift)
                states += bytes([state])
            states_num = (bytes_to_long(states)<<1) | 1
            pre_sol = ""
            for num in nice_nums[-16:]:
                pre_sol += str((states_num & num).bit_count() % 2)
            num1 = int(pre_sol[:8],2)
            num2 = int(pre_sol[8:16],2)
            
            if is_valid_consistent_key(num1, num2) and is_valid_consistent_key(num2, states[0]):
                pre_sol = ""
                for num in nice_nums:
                    pre_sol += str((states_num & num).bit_count() % 2)
                key = long_to_bytes(int(pre_sol,2)) + states
                cipher = AES.new(sha256(key).digest()[:16], AES.MODE_ECB)
                if b"NKCTF{" in cipher.decrypt(EncryptedFlag).upper():
                    print(cipher.decrypt(EncryptedFlag))
                    exit()
                    
# $ pypy.exe run_ezradnom.py 96 128

drsn

 

题解

由于 ascii 字节高位固定为 0，在经过只有 轮密钥异或、shuffle （没有 Sbox）的加密算法时，这个比特位会加密成一个固定的值（对于相同 key），因此如果没有最后一轮与 key 的 rng 无关的纯随机的 shuffle，密文某个固定比特位会不变。

1
2
3
4
5
6
7
def encrypt_block(self, block: bytes) -> bytes:
    for _ in range(self.ROUNDS - 1):
        block = self.split(block); self.rng.shuffle(block); block = self.unite(block)
        block = self.xor(block, self.key)
    #
    block = self.split(block); random.shuffle(block); block = self.unite(block)        
    return block

 

题目对密文加入了一个随机 shuffle 后 （random.shuffle(block);），ascii 字节高位 0 的密文比特位置不固定了，但是这个值固定是不变。这意味着给定一个 task(bit, n) ，存在某个不固定的位置的值恒为 0 （或者 1） ，其他位置为 0，1 均匀分布。

最后这个 shuffle 把固定位置不变的比特特征抹去了，但是并不能改变 0,1 比特数目不平衡（非随机分布）的特性，实际上密文的分布和明文的分布是一致的。即加密的密文（或者说明文分布）中的 0，1 分布比随机分布更不均匀，可以通过 0， 1 数量的差（or 方差）区分出这两个分布，从而通过题目中的 Oracle 挑战。

 

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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from pwn import remote, context, log, process
# import mbruteforce from pwnlib
from pwnlib.util.iters import mbruteforce
from Crypto.Util.number import long_to_bytes, bytes_to_long
import string
import hashlib

# node.nkctf.yuzhian.com.cn:37755 
io = remote('node.nkctf.yuzhian.com.cn', 32291)
# node.nkctf.yuzhian.com.cn:32291
# io = process(["python3", "main.py"])
# context.log_level = 'DEBUG'

def solve_pow(io:remote):
    io.recvuntil(b"sha256(XXXX + ")
    suffix = io.recvuntil(b") == ", drop=True)
    target = io.recvuntil(b"\n", drop=True).decode()
    log.info(f"suffix: {suffix}, target: {target}")
    sol = mbruteforce(lambda x: hashlib.sha256(x.encode() + suffix).hexdigest() == target,
                      string.ascii_letters + string.digits, 
                      4)
    io.sendlineafter(b"XXXX>", sol.encode())
    log.info(f"solved pow: {sol}")
    return True 

def challenge_func(option):
    io.recvuntil(b"[Q]uit\n")
    io.sendlineafter(b">", option.encode())
    if option == "s":
        return None
    io.recvline()
    io.recvline()
    return io.recvuntil(b"\n", drop=True)

def to_bits(s):
    return ''.join(format(x, '08b') for x in s)

def compute_diff(res):
    diff = 0
    table01 = {}
    table01["1"] = 0
    table01["0"] = 0
    for block in range(0, len(res), 16):
        rblock = res[block:block+16]
        bres = to_bits(rblock)
        cnt1 = bytes_to_long(rblock).bit_count()
        cnt0 = 128 - cnt1
        table01["1"] += cnt1
        table01["0"] += cnt0
    diff += abs(table01["1"] - table01["0"])
    return diff

def check_fix_bit(res:bytes):
    table = {}
    bit = 0
    n = 1
    for block in range(0, len(res), 16):
        rblock = res[block:block+16]
        bres = to_bits(rblock)
        for i, c in enumerate(bres):
            if i not in table:
                table[i] = [0,0]
            else:
                table[i][int(c)] += 1

    for k, v in table.items():
        if 0 in v:
            print(k, v)
            print(f"fixed bit: {k = }")
            return True
        print(k, v)
    return False        

def rounds_func(n, times=1, bound=10000):
    io.recvuntil(b"ROUND #")
    round_num = int(io.recvuntil(b"\n", drop=True))
    log.info(f"round_num: {round_num}")
    io.recvuntil(b"CHAOS: ")
    chaos = int(io.recvuntil(b"\n", drop=True), 16)
    log.info(f"chaos: {chaos}")
    io.recvuntil(b"  SPIRIT: ")
    spirit = int(io.recvuntil(b"\n", drop=True))
    log.info(f"spirit: {spirit}")
    
    diff = 0
    io.sendlineafter(b"n>", str(n).encode())
    for i in range(times):
        tmp = challenge_func("h")
        bytes_res = eval(tmp.decode())
        diff += compute_diff(bytes_res)
    if diff > bound:
        guess_bit = 0
    else:
        guess_bit = 1
    log.info(f"bytes_res: {guess_bit = } with {diff = }")
    challenge_func("s")
    io.sendlineafter(b"b>", str(guess_bit).encode())
    response = io.recvuntil(b"\n", drop=True).decode("utf-8")
    if "Accept" in response:
        log.info(f"round {round_num} accepted")
        return True
    elif "Reject" in response:
        log.info(f"round {round_num} rejected")
    else:
        log.info(f"round {round_num} error")
    return False
solve_pow(io)

n = 256
t = 50
lb = 10000
ROUND = 30
spirit = 3

for i in range(ROUND):
    rounds_func(n, t, lb)
    
print(io.recvline())
io.interactive()

 

fly to the hyper

 

题解

定义一个 HyperellipticCurve ：

记 ，给定一 80 个点集 ，和一个子集和 满足 :

我们需要恢复出秘密向量 $\vec b = (b1, \cdots, b_{80})$ ，其中 10 比特已知（password 生成过程中的字节高位为 1），实际上只需要恢复 70 比特。

这是一个基于 HyperellipticCurve 上 jocabian 群（divisor）的子集和（subset-sum-problem abbr ssp）问题，现学 HyperellipticCurve ，尝试寻找 jocabian 上一些特殊性质求解子集和，然后发现 ssp 的求解和群关系不大。

 

于是尝试转换到 上的 Modular SSP 问题，要完成这个转换，我们首先要完成下面几个步骤：

  1. 求 jocabian 群的阶。
  2. 寻找 jocabian 群的一个生成元（或者高阶元）
  3. 确认该 jocabian 群上的离散对数问题可解（或者部分可解）。

完成上述转换之后，求解 80 个点（因为 password 的每个字节的高位为 1 ，实际只需要 70 个）对 的离散对数，得到一个数集 , 离散对数对应子群的阶记为 , 同时求出点 对 的离散对数 ，从而得到 Modular SSP ：

解这个 Modular SSP 即可恢复出 password 的所有比特。

 

一些细节

计算阶

计算阶：参考论文 An elementary introduction to hyperelliptic curves , 0CTF 2020 Simple Curve 中有具体实现。

得到的阶为：

1
2^5 * 3^12 * 13^2 * 19^2 * 101 * 157 * 271 * 461 * 523 * 701 * 829 * 1531 * 1747 * 20341 * 57901 * 71161 * 623881 * 93383701 * 1563346261 * 118050254940601 * 1559805923143337117401

这个阶相当光滑，于是可以应用 pohlig hellman 算法求解离散对数。

 

生成元

由于这个 jocabian 群上的 sage 内置点加并不快，随机生成寻找生成元还是很困难的，但是我们只要找到某个光滑子群的生成元即可，一类很好找的生成元，它的阶包含上述每个素因子都至少一次。

寻找到这个生成元：

1
base = (x + z^179 + z^178 + z^175 + z^174 + z^172 + z^166 + z^164 + z^163 + z^162 + z^161 + z^159 + z^157 + z^155 + z^154 + z^153 + z^152 + z^149 + z^147 + z^145 + z^143 + z^142 + z^140 + z^139 + z^136 + z^134 + z^133 + z^131 + z^128 + z^127 + z^120 + z^116 + z^115 + z^109 + z^107 + z^103 + z^100 + z^96 + z^93 + z^92 + z^91 + z^90 + z^89 + z^87 + z^83 + z^78 + z^74 + z^73 + z^71 + z^70 + z^68 + z^66 + z^58 + z^57 + z^53 + z^52 + z^50 + z^49 + z^48 + z^44 + z^43 + z^42 + z^41 + z^36 + z^34 + z^32 + z^30 + z^29 + z^28 + z^25 + z^24 + z^23 + z^20 + z^19 + z^18 + z^16 + z^15 + z^14 + z^13 + z^12 + z^11 + z^10 + z^8 + z^7 + z^6 + z^4 + z^3 + z^2 + z + 1, z^177 + z^176 + z^175 + z^174 + z^173 + z^171 + z^169 + z^166 + z^165 + z^163 + z^162 + z^161 + z^159 + z^158 + z^155 + z^152 + z^151 + z^145 + z^141 + z^140 + z^139 + z^137 + z^135 + z^133 + z^131 + z^130 + z^128 + z^127 + z^126 + z^125 + z^119 + z^118 + z^115 + z^114 + z^113 + z^110 + z^108 + z^106 + z^104 + z^103 + z^102 + z^100 + z^97 + z^96 + z^95 + z^94 + z^81 + z^78 + z^77 + z^76 + z^75 + z^74 + z^73 + z^71 + z^69 + z^61 + z^60 + z^53 + z^51 + z^49 + z^46 + z^42 + z^41 + z^40 + z^38 + z^36 + z^35 + z^34 + z^32 + z^29 + z^28 + z^26 + z^24 + z^23 + z^22 + z^21 + z^14 + z^7 + z^6 + z^5 + z^4 + z^2)

这个子群的阶为：

1
base_order = 2^4 * 3^3 * 13 * 19 * 101 * 157 * 271 * 461 * 523 * 701 * 829 * 1531 * 1747 * 20341 * 57901 * 71161 * 623881 * 93383701 * 1563346261 * 118050254940601 * 1559805923143337117401

忽略掉大的素因子，最终选取的子群阶为：

1
m_order =  2^4 * 3^3 * 13 * 19 * 101 * 157 * 271 * 461 * 523 * 701 * 829 * 1531 * 1747 * 20341 * 57901 * 71161 * 623881

 

离散对数

Sage 内置 discrete_log 有些 bug （9.2），需要 hook 改动的地方也比较多，不如自己写一个 pohlig hellman + bsgs 算法。还可以进行 batch log 优化。

 

Modular SSP 问题

属于是经常能碰到的问题了， 这里我们模数有 163 比特，集合大小 n = 70 ，背包密度小于 0.6 ，用一般的格即可规约出短向量，从而恢复出目标向量 。

 

EXP

SSP 转换 （i7-13700 上跑 1h40min，还可以进行优化，相同 base 的 bsgs 过程可以复用大部分计算）

1
100%|█████████████████████████████████████████████████████████████████████████████████| 70/70 [1:40:53<00:00, 86.48s/it]

Sage:

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
from Crypto.Util.number import *
from random import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from tqdm import tqdm, trange

load("./output.sage")
"""
# output.sage
extend = 180
F = GF(2^extend, 'z', modulus = x^180+x^3+1)
z = F.gens()[0]
PRx = PolynomialRing(F,"x")
x = PRx.gens()[0]
h = x^2 + 1
f = x^5 + x^2 + 1
H = HyperellipticCurve(f, h)
J = H.jacobian()

s = ...
points = ...
c = ...
"""

def count_points(F, curve):
    return [(x, y) for x in F for y in F if curve(x, y) == 0]

def jacobian_order(q, n, curve, debug=False):
    # step 1
    # +1 represents the point at infinity.
    ps1 = count_points(GF(2), curve)
    m1 = len(ps1) + 1
    if debug:
        print('points in GF(2) =', ps1)
        print('M1 =', m1)

    ps2 = count_points(GF(4), curve)
    m2 = len(ps2) + 1
    if debug:
        print('points in GF(4) =', ps2)
        print('M2 =', m2)

    # step 2
    a1 = m1 - 1 - q
    a2 = (m2 - 1 - q ^ 2 + a1 ^ 2) / 2
    if debug:
        print('a1 =', a1)
        print('a2 =', a2)

    # step 3
    # X^2 + a1X + (a2 − 2q) = 0 => x^2 - x - 5 = 0 => zeros = (1 +- sqrt(21)) / 2
    var('X')
    gammas = list(map(lambda x: x.rhs(), solve(
        [X ^ 2 + a1*X + (a2 - 2 * 2) == 0], X)))

    # step 4
    # X^2 − gamma1X + q = 0
    alpha1 = list(map(lambda x: x.rhs(), solve(
        [X ^ 2 - gammas[0]*X + q == 0], X)))[0]
    alpha2 = list(map(lambda x: x.rhs(), solve(
        [X ^ 2 - gammas[1]*X + q == 0], X)))[0]
    if debug:
        print('points in GF(2) =', ps1)
        print('M1 =', m1)
        print('points in GF(4) =', ps2)
        print('M2 =', m2)
        print('a1 =', a1)
        print('a2 =', a2)
        print('gammas =', gammas)
        print('alpha1 =', alpha1)
        print('alpha2 =', alpha2)

    # step 5
    nj = int(abs(1-alpha1 ^ n) ^ 2 * abs(1-alpha2 ^ n) ^ 2)
    return nj

def hash_str(g):
    return md5(str(g).encode()).hexdigest()


def bsgs_add_group(y, base, ub, identity=None, verbose=True):
    from itertools import product
    from tqdm import tqdm, trange
    complexiy = int(sqrt(ub)).bit_length()
    if identity == None:
        identity = 0
    if verbose: print(f"[+] estimate time {complexiy = } bits")
    # y =  base ^ x \mod p
    # i * m + j =  x \mod p-1, i,j \in bf
    # y =  base (i * m + j)
    # y - base (i * m) =  j * base
    # y + (-m * base) * i =  j * base
    # giant step gap        
    T = int(sqrt(ub) + 1)
    if ub < 200:
        # try bruteforce
        g0 = identity
        for i in range(ub):
            if y == g0:
                return i
            g0 += base
        return None
    
    table = dict()   
    if verbose: print(f"[*] start baby step...")
    st = identity
    if verbose: bf = trange(T) 
    else: bf = range(T)
    for j in bf:
        table[hash_str(st)] =  j
        st += base
        
    if verbose: print(f"[*] start giant step")
    giant = -T * base
    # y + (-m * base) * i 
    c = y
    if verbose: bf = trange(T) 
    else: bf = range(T)
    for i in bf:
        if hash_str(c) in table:
            if verbose: print("[+] find collision")
            j = table.get(hash_str(c))
            return ZZ(i * T + j)
        c += giant
    print("[+] bsgs fails")
    return None



def is_prim_element(element, identity, group_order, fs=None):
    if fs == None:
        fs = factor(group_order)
    for p, e in fs:
        mul = ZZ(group_order/p)
        if mul * element == identity:
            return False
    return True

def is_fake_prim_element(element, identity, group_order, fs=None):
    if fs == None:
        fs = factor(group_order)
    for p, e in fs:
        mul = ZZ(group_order/(p**e))
        if mul * element == identity:
            return False
    return True

def element_order(element, identity, group_order):
    fs = factor(group_order)
    res = 1
    for p, e in fs:
        mul = ZZ(group_order/(p^e))
        y = mul * element
        while y != identity:
            res *= p
            y = p * y
    return res

def element_order_pure(element, identity, group_order):
    fs = factor(group_order)
    res = 1
    for p, e in fs:
        mul = ZZ(group_order/(p^e))
        y = mul * element
        if y != identity:
            res *= p
    return res

def pollig_hellman_add_group(y, g, group_order, identity, verbose=True):
    # we do not handle the case p^e with large e (e>=2)
    fs = factor(group_order)
    mods = []
    dlogs = []
    for p, e in fs:
        if verbose:
            print(f"[+] Sub dlog in  group with order {p}^{e}")
        sub_order = ZZ(p**e)
        sub_mulc = group_order//sub_order
        new_y = sub_mulc * y
        new_g = sub_mulc * g
        # sub_log = bsgs_add_group(new_y, new_g, sub_order, identity, False)
        sub_log = bsgs_add_group(new_y, new_g, sub_order, identity, False)
        
        if verbose:
            print(f"   Sub dlog  x = {sub_log} % {sub_order}")
        mods.append(sub_order)
        dlogs.append(sub_log)
    return crt(dlogs, mods)

def gen_point():
    while(1):
        try:
            a = F.fetch_int(randint(1,2^extend-1))
            PRy.<y> = PolynomialRing(F,"y")
            y = PRy.gens()[0]
            curve = y^2 + h(a)*y - f(a)
            y , k = curve.roots()[0]
            if(k == 1):
                return J(H(a , y))
        except:
            pass


E_f = lambda x, y: y^2 + (x^2 + 1)*y + x^5 + x^2 + 1
q = 2
n = 180
J_order = ZZ(jacobian_order(q, n, E_f, debug=False))


target_sum = J(s)
points_set = []
useless_points = []
base_point = None

# rm_order = 118050254940601 * 1559805923143337117401 * 1563346261 * 93383701
# m_order = J_order // rm_order
base = (x + z^179 + z^178 + z^175 + z^174 + z^172 + z^166 + z^164 + z^163 + z^162 + z^161 + z^159 + z^157 + z^155 + z^154 + z^153 + z^152 + z^149 + z^147 + z^145 + z^143 + z^142 + z^140 + z^139 + z^136 + z^134 + z^133 + z^131 + z^128 + z^127 + z^120 + z^116 + z^115 + z^109 + z^107 + z^103 + z^100 + z^96 + z^93 + z^92 + z^91 + z^90 + z^89 + z^87 + z^83 + z^78 + z^74 + z^73 + z^71 + z^70 + z^68 + z^66 + z^58 + z^57 + z^53 + z^52 + z^50 + z^49 + z^48 + z^44 + z^43 + z^42 + z^41 + z^36 + z^34 + z^32 + z^30 + z^29 + z^28 + z^25 + z^24 + z^23 + z^20 + z^19 + z^18 + z^16 + z^15 + z^14 + z^13 + z^12 + z^11 + z^10 + z^8 + z^7 + z^6 + z^4 + z^3 + z^2 + z + 1, z^177 + z^176 + z^175 + z^174 + z^173 + z^171 + z^169 + z^166 + z^165 + z^163 + z^162 + z^161 + z^159 + z^158 + z^155 + z^152 + z^151 + z^145 + z^141 + z^140 + z^139 + z^137 + z^135 + z^133 + z^131 + z^130 + z^128 + z^127 + z^126 + z^125 + z^119 + z^118 + z^115 + z^114 + z^113 + z^110 + z^108 + z^106 + z^104 + z^103 + z^102 + z^100 + z^97 + z^96 + z^95 + z^94 + z^81 + z^78 + z^77 + z^76 + z^75 + z^74 + z^73 + z^71 + z^69 + z^61 + z^60 + z^53 + z^51 + z^49 + z^46 + z^42 + z^41 + z^40 + z^38 + z^36 + z^35 + z^34 + z^32 + z^29 + z^28 + z^26 + z^24 + z^23 + z^22 + z^21 + z^14 + z^7 + z^6 + z^5 + z^4 + z^2)
base = J([PRx(i) for i in base])
base_order = 2^4 * 3^3 * 13 * 19 * 101 * 157 * 271 * 461 * 523 * 701 * 829 * 1531 * 1747 * 20341 * 57901 * 71161 * 623881 * 93383701 * 1563346261 * 118050254940601 * 1559805923143337117401
m_order =  2^4 * 3^3 * 13 * 19 * 101 * 157 * 271 * 461 * 523 * 701 * 829 * 1531 * 1747 * 20341 * 57901 * 71161 * 623881
rm_order = J_order // m_order
base_point = (base_order//m_order) * base

# remove pos 0, 8, 16,.., since the bit is 1
for i in trange(len(points)):
    pi = J(points[i])
    if i % 8 == 0 :
        target_sum = target_sum - pi
        useless_points.append(pi)
        if base_point is None and is_prim_element(pi, J(0), J_order):
            print(f"[+] use points[{i}]")
            base_point = rm_order * pi
    else:
        points_set.append(rm_order * pi)
    

print(f"[+] sub group : {m_order.nbits()} bits")
tsum = pollig_hellman_add_group(rm_order * target_sum, base_point, m_order, identity=J(0))

numset = []
qmod =  m_order
# len(points_set)
for pi in tqdm(points_set):
    numset.append(ZZ(pollig_hellman_add_group(pi, base_point, m_order, identity=J(0))))
    
print(f"{numset = }")
print(f"{tsum = }")
print(f"{qmod = }")

SSP Solver

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
from random import shuffle
from secrets import randbits 
from collections.abc import Iterable
"""
Implemented by tl2cents
General Modular Subset Sum Solver
"""

def check_valid_solution(M, col_from=0):
    sols = []
    for row in M:
        if all(num in [-1,1] for num in row[col_from:]):
            sols.append(row)
    return sols

def build_modular_ssp_lattice(numset, t_sum, mod, w = None):
    dim = len(numset)
    k = ZZ(max(numset)).nbits()
    density = RR(dim/k)
    if w is None:
        w = 2**k
    M = matrix(ZZ, dim + 2, dim + 2)
    for i in range(dim):
        M[i,0] = w * numset[i]
        M[i,i+1] = 2
    M[dim] = [-w * t_sum] + [-1] * (dim + 1)
    M[dim + 1, 0] = w * mod
    
    print(f"[+] build ssp lattice with {density = }, dimension = {dim}")
    return M

def solve_modular_ssp(numset, t_sum, mod, w=None, bkz=None, verbose=True):
    M = build_modular_ssp_lattice(numset, t_sum, mod, w)
    if verbose: print(f"[*] LLL reduction with dimensions {M.dimensions()}.")
    lattice = M.LLL()
    if verbose: print(f"[*] LLL done.")

    # remove useless vectors
    optimized_lattice = lattice[:-1,1:]
    sols = check_valid_solution(lattice)
    if len(sols) != 0 or bkz is None:
        return sols 
    if isinstance(bkz, int) or isinstance(bkz, Integer):
        bkz = [bkz]
    else:
        assert isinstance(bkz, Iterable), "not valid type"
    
    basis = optimized_lattice[:]
    for bs in bkz:
        if verbose: print(f"[*] BKZ reduction with dimensions {basis.dimensions()} and block_size = {bs}.")
        basis = basis.BKZ(block_size=bs)
        if verbose: print(f"[+] BKZ done.")
        sols =  check_valid_solution(basis)
        if len(sols) != 0:
            if verbose: print(f"[+] find {len(sols)} solutions")
            return sols

def sol2num(sol):
    return int("".join("1" if xi==1 else "0" for xi in sol),2)

numset = [1134377146236307273211352296932497796726645013538, 4322674742504873739323622793554751612763909345541, 1589174007064767939189305163860435609207851475628, 3768361685436615008056985969285203407431184616764, 7544944319636193522098476790275940897438834903661, 915658681467510466941441639883192325063917330374, 2533989085113724204960984726119407829475626228987, 5155028284874247647034416493107673129053320478970, 5059193707527698079493764865529508507277744368237, 1788052426331222176463329238304118711992914588016, 6527989097855860620683119930785984889747631321892, 6234672389447372514356681059048364620296590226876, 6473954063620441793065364171778184796020848662781, 7303594300575577993254546033573713921012204959428, 6336453151459945651309646818952183190305348871720, 4977030520023879402108012961155249738170331294708, 7383309519617413260213452109214128220829015649252, 4372825732666039269126231968367204588779581872288, 1744744357279509172730566715506464255253559958153, 2884641242220857553535460186796926355993313780815, 7207776942952578183853872953286665755384060625055, 8293013249444730288214883880667596395229829444992, 1934050603758453703244404407480464257983283313763, 8932965923313128267935036317230296004014957451865, 4844414973588482117016093696824378708425897330122, 5037654213456056878310395468065306125495541884079, 1743782486428824155237444805905424302642338834236, 3697866167111119117396386323795330383447453078782, 1062100159168209563836665908203110537581918424576, 6158996015311332482983640250131189675582606497329, 8598490277212273876979263609688483883496476119991, 6943023134579524267045156441773688513936601589693, 1669765636132717649563875744557568338197784710599, 7668130709388509182807415685170201471559338995029, 304334157538777549513116260073189760578488476422, 2990448211955276858529443199201329112253885795614, 1913596305861219747491935735403144860059849609966, 1163925650825585315124481033166239457401710476442, 7933354153901445831737589873733846868221084584399, 8429070299916706079128377285156162272305547191119, 604802377251546856699955111546885990717005410750, 8040530683500302848722465780235251255871719885168, 2747653176994282902662199323535012100100182360629, 1919486646572654089332487360990954480446641871630, 2166968874631715734227805212293946741962376757608, 8152985550764408252426267380211786893650102961467, 3012490031303816723198407101190721098069383149085, 1088305977217199970160126081014733150093068609582, 5535450543340635784123762905368072004590856516207, 4446134603495007425770160753330155034279120261181, 1795193306747884463940320728788755217115110290583, 3296826827481388636146509754635030145370908026202, 2615416198294138563406804830433130617794136596156, 4804033693911030556029553076232365763785467439469, 3288741894467167744855565379342860722672599261999, 4615256356838741080274578173849827361120785526960, 1959868119573781060459346285406729649072895298060, 623248134618001455584425263785831476997298276924, 6174058329904945319919632464818788279833924246758, 6992591479250433421630616813550998110806075338829, 8328992522867340613709893270270171498186659662949, 8593049397147723528227779805015378606200274862024, 3018516323006104435936564962627472546012393788369, 3414782091428646447034537985603441812454371812375, 6226705246804351442353255252674456914107252182201, 1049062751139217092731922605874024245357086534197, 7222430747981529606700395136325713352498232099615, 4716366999226313542858945325596699161984249178722, 1683295795994715357879129782210664263880934069854, 6967723154705627111439553482234354584519224879215]
tsum = 7883312907716494529662648068345674577802305481986
qmod = 8984966079379553115577623365251076670488873519952

sols = solve_modular_ssp(numset, tsum, qmod, bkz=range(16,30,1))
print(f"[+] {sols = }")

sol = list(- sols[0][:-1] * sols[0][-1])


ss = sum([j for i,j in zip(sol, numset) if i==1]) % qmod
print("[+] check solution : " , ss == tsum)

pwd_bits = []
for i in range(0, len(sol), 7):
    pwd_bits += [1] + sol[i:i+7] 

c = b'\xb1h\x85\xf1+\x15\x14(\x93\xc3J\xff`\xf6\xd3\xf3\x97ZEJ\xbd\x9dX\t\x81\x04Td\xfeIek\xc0\x96X\x92\xd5\xdeP\xd6K\x04\xe7\x13cL\xff\xb0'
password = long_to_bytes(sol2num(pwd_bits))
key = md5(password).digest()
cipher= AES.new(key,mode = AES.MODE_ECB)
msg = cipher.decrypt(c)
print(msg)

 

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


Hi, this is tl2cents
Currently Ph.D at IIE of UCAS
Graduated from USTC (2018-2022)

CTFer
Focus on blockchain, crypto and reversing
Team member of NeSE and Nebula

Research
Blockchain | ETH | FHE
PQC | Cryptography | Android

Contact Me
echo Y2F4dWxhc2FlbGFAb3V0bG9vay5jb20K | base64 -d

Thanks for JoeyBling and Litten