2023 NCTF Crypto Writeups

字数统计: 11.9k字   |   阅读时长≈ 64分

今年最后一场认真看题的 CTF 了，周末同时段还有安洵杯，第一天打安洵，第二天来玩 NCTF，拿了两个第一，赢！ 两场的 crypto 都 AK 了，安洵的题都是国内赛比较常规的考点，NCTF 的密码题倒还挺好玩的，很有国际赛的感觉，质量很高。

 

Code Infinite

题目源码附件下载 ： Code_Infinite.zip

 

恢复 Curve 参数

实现了一个基于 Elliptic Curve 的 DH 秘密共享。每次接收我们输入的一个点 作为我们的公钥，然后 server 端将共享密钥值 返回。如果我们能够求解在目标 Elliptic Curve 上的离散对数问题，即可解出服务端的私钥拿到 flag。但是 Elliptic Curve 的参数 都没有给出，于是第一步考虑通过 oracle 拿到 Elliptic Curve 上多组点，将 恢复。

考虑到 Elliptic Curve 的方程 ：

拿到 个点 ，其实就等价于拿到了 个线性方程：

消元 得到：

从上述等式我们就能得到模数 的整数倍，对于任意 ， ，不断收集这样的 的整数倍，然后 得到最大公因子， 足够大时，大概率就能直接恢复 。得到 之后，直接解模线性方程组即可恢复 。最终得到 ：

1
2
3
p = 6277101735386680763835789423207666416083908700390324961279
a = 6277101735386680763835789423207666416083908700390324961276
b = 2455155546008943817740293915197451784769108058161191238065

 

Invalid Curve Attack

恢复曲线后，发现 Elliptic Curve 的阶恰好是一个不等于自身的大素数，在原曲线上求解离散对数是不可行的。发现服务端并没有检查输入的点是否在原曲线 上，存在 Invalid Curve Attack 。

由于 Elliptic Curve 的点加运算、标量乘法都与 的参数 无关，只与 有关，所以可以通过平移曲线 到 上，这样不会改变群的运算，但是 的阶会发生改变，只要 的阶足够光滑，或者有小的素因子，就可以求解（子群上）离散对数，最后再用 CRT 恢复出服务端私钥 。

关于如何寻找光滑的曲线，这题的 比较小，可以直接尝试爆破 的值，然后看阶是否光滑。一般来说阶的最大素因子小于 ，就能很快（几分钟）跑出 DLP 了。当然，实在找不到，就找四个曲线，在各自子群上求 DLP ，只要最终四条曲线上光滑子群阶的 大于 ，也能完全恢复私钥。

其他思路（未验证） ：

  • 赛后看这题，好像可以尝试选取 进行 singular curve attack，即同态到 上求解，虽然 也不太光滑，但是有限域的 DLP 还是比 ECC 快多了。
  • 直接构造特定阶的 Elliptic Curve ，最近看 grhkm 的博客了解到 CM Method 就是构造有限域上特定阶或者迹的曲线的方法，有空可以补上这块，感兴趣的读者可以参考 HackTM Final 上的这题 DDLP (Upsolve)。

 

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
from pwn import remote
from itertools import product
import string
import hashlib
from tqdm import tqdm
from ast import literal_eval

table = string.ascii_letters+string.digits

# 8.222.191.182 11112
# 115.159.221.202
def solve_pow():
    io.recvuntil(b"[+] sha256(XXXX+")
    proof, target = io.recvline().decode().strip().split(") == ")
    print(f"[+] {proof = }")
    print(f"[+] {target = }")  
    bf = product(table, repeat=4)
    for i in tqdm(bf):
        prefix = "".join(i)
        if hashlib.sha256((prefix + proof).encode()).hexdigest() == target:
            print("[+] pow solved")
            io.sendlineafter(b'[+] Plz tell me XXXX: ', prefix.encode())
            return
        
pks = []
encs = []

for i in range(10):
    io = remote("115.159.221.202", "11112")
    solve_pow()    
    io.recvuntil(b"The secret is ")
    enc = bytes.fromhex(io.recvline().decode().strip())
    io.recvuntil(b"Alice's public key is ")
    pk = literal_eval(io.recvline().decode().strip())
    pks.append(pk)
    io.close()
    
# y^2 = x^3 + a^x + b
rs = []
# xi, a * xi + b
for (x,y) in pks:
    rs.append((x,y^2 -x^3))
    
ks = []
# k, k * b
for xi, ri in rs:
    for xj, rj in rs:
        if xi == xj:
            continue
        ks.append((xj -xi, xj*ri - xi * rj))

kps = []
for ki, kbi  in ks:
    for kj, kbj in ks:
        if ki == kj:
            continue
        kp = ki * kbj - kbi * kj
        kps.append(kp)
        
p = gcd(kps)
print("[+] check" , is_prime(p))
b = ZZ(inverse_mod(ks[0][0], p)) * ks[0][1] % p
a = ZZ(inverse_mod(rs[0][0], p)) * (rs[0][1] - b) % p 

print(f"[+]  {p = }")
print(f"[+]  {a = }")
print(f"[+]  {b = }")

恢复私钥

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
from pwn import remote
from itertools import product
import string
import hashlib
from tqdm import tqdm
from ast import literal_eval
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES

table = string.ascii_letters+string.digits

# 8.222.191.182 11112
# 115.159.221.202
def solve_pow():
    io.recvuntil(b"[+] sha256(XXXX+")
    proof, target = io.recvline().decode().strip().split(") == ")
    print(f"[+] {proof = }")
    print(f"[+] {target = }")  
    bf = product(table, repeat=4)
    for i in tqdm(bf):
        prefix = "".join(i)
        if hashlib.sha256((prefix + proof).encode()).hexdigest() == target:
            print("[+] pow solved")
            io.sendlineafter(b'[+] Plz tell me XXXX: ', prefix.encode())
            return

io = remote("115.159.221.202", "11112")
solve_pow()    
io.recvuntil(b"The secret is ")
enc = bytes.fromhex(io.recvline().decode().strip())
io.recvuntil(b"Alice's public key is ")
pk = literal_eval(io.recvline().decode().strip())
p = 6277101735386680763835789423207666416083908700390324961279
a = 6277101735386680763835789423207666416083908700390324961276
b = 2455155546008943817740293915197451784769108058161191238065
# smooth curve order
_b = 5219181578875570541716764769996943115709496807312581959816 
E = EllipticCurve(GF(p),[a,b])
_E = EllipticCurve(GF(p),[a,_b])

assert E.is_on_curve(pk[0], pk[1])

g = _E.gens()[0]
g_order = g.order()

io.sendlineafter(b"Give me your pub key's x : \n", str(g[0]).encode())
io.sendlineafter(b"Give me your pub key's y : \n", str(g[1]).encode())
io.recvuntil(b"The shared key is\n ")
Q = _E(literal_eval(io.recvline().decode().strip()))

sk = discrete_log(Q, g, ord=g_order, operation="+")
print(f"[+] {sk = }")

key = long_to_bytes(int(sk))[:16]
Cipher = AES.new(key,AES.MODE_ECB)
flag = Cipher.decrypt(enc)
print(flag)

 

SteinsGate

题目源码附件下载 ： SteinsGate.zip

 

Padding 算法分析

这题和 hitcon 的 careless padding 出自于同一个篇论文，场景很相似。当初打 hitcon 的 careless padding 时候，exp 太难写了，这题比 hitcon 好写一点。这次刚好补一下之前 hitcon 咕掉的题解。

对 Padding 算法感兴趣的读者可以参考下面两个链接：

 

首先简单分析一下本题中 Padding 的算法，下图是两个分组情况下的填充格式示意图：

padding

Padding 的字节有 ，其中 分别是倒数第二个分组的第一和第二个字节。 直接加在消息最后，只占一个字节，然后填充 字节直至满足分组长度的整数倍。特别地，当明文消息中 时，上图中 Padding 部分使用的填充字节实际上是 ，以保证 unpad 时不会多截断一个字节。

 

于是一个简单的 unpad 的流程如下：

unpadding

  1. 取最后一个字节为 ，从填充后消息的末尾开始，依次去掉连续重复的 ，直到碰到第一个不同的字节，记为 ，则 之前的消息均是原始的消息内容，确定消息长度为 。

  2. 根据消息长度 ，定位倒数第二个分组，取它的第一第二个字节为 和 ，则正确的填充格式一定满足：

设计这种填充方式，是为了防止诸如 CBC 场景下的 padding oracle 攻击，因为经典场景下的填充格式检查通常只在单个 block 内进行，也就是说在 CBC 分组加密下，我们改变前一个分组的某个字节值，就能恰好对应改变后一个分组的对应字节值，再通过是否满足 padding 格式的信息，我们就能确定最后一个分组的某个字节此时解密为某个特定的值，从而逐字节恢复出最后一个分组的明文，于是在 CBC padding oracle 模式下攻击者就拥有了解密任意分组密文的能力。 而上述填充方式的检查涉及到最后一个分组和倒数第二个分组，因此我们修改倒数第二个分组的密文值，由于雪崩效应，会导致倒数第二个分组的密文解密后的明文发生不可预估的巨大改变，也就说，此时如果我们想通过修改倒数第二个分组的密文，来修改最后一个分组解密得到的 ，则 的变化是完全不可控的，也因此无法从 padding oracle 获取有用信息。

 

已知明文的 2-block 攻击

考虑下面的密文场景，其中 Block1 密文解密对应的明文是已知的（实际上只要求前两个字节 已知）， IV 可以由我们任意修改控制。

2-block

显然，这个场景下，我们可以通过 Padding Oracle 泄露出 Block2 的最后两个字节，原理如下：我们不修改 Block1 和 Block2 密文，通过修改 IV 的前面两个字节 去修改 Block1 解密后的 的值，记修改后的值为 ，只有当 的值恰好修改成 或者 ，才会 unpad 成功，该过程最多需要 次交互，在已知明文字符集的情况下，Oracle 的交互次数还能进一步减少。因此通过已知（部分）明文的密文分组，我们可以确定任意一个未知密文分组的最后两个字节的值。

 

Single Block Attack

我们考虑一下本题中存在的单个密文分组的 Padding Oracle 攻击。

1
2
3
4
5
6
7
8
def unpad(msg):
    msg_length, X, Y = find_repeat_tail(msg)
    block_count = count_blocks(msg_length)
    _X = msg[(block_count-2)*N]
    _Y = msg[(block_count-2)*N+1]
    if (Y != _Y and Y != _Y^1) or (X != _X):
        raise ValueError("Incorrect Padding")
    return msg[:msg_length]

由于 Python 的语言特性，上面 unpad 过程中的 _X ， _Y 在只有单个分组的情况下（block_count = 1），变成了本分组的第一、第二个字节。也就说，此时 unpad 是否成功需要检查的信息又回到了单个分组内部，如下图所示（IV 略）

one-block

单个 block 的情况下，就是经典的 Padding Oracle 攻击的模式了。此时假设我们通过上节的已知明文攻击，恢复了单个 Block 中最后两个字节 ，此时通过下面的攻击，我们可以解密整个 Block ：

  1. 解密前两个字节 ： 修改 ，修改 的值为 ，直到 unpad 成功。此时有 ：

    即可成功恢复出 的值。

  2. 解密中间字节：固定前两个字节为 ，通过修改 IV 将最后两个字节修改为 ，此时我们通过修改 IV 的倒数第三个字节去修改解密出来的明文的倒数第三个字节，直到 unpad 成功，根据 unpad 的等式即可推导出明文倒数第三个字节的值，以此类推，能够完整解密整个分组。

至此，我们就已经有了在 Padding Oracle 上解密任意密文的能力。

 

Remarks

实际上，所有与 相关的等式都可能存在两个解，即 的最低比特位是未知，也就是上述攻击中的第二个字节和倒数第一个字节都有 2 种可能。可以通过 padding oracle 确定最后的比特位，也可以通过手动穷举忽略掉这个。

 

Padding Oracle Attack

回到本题，注意到本题 flag 的未知 byte 都是 hex ，这意味着单个字节只有 16 种可能的取值。给出如下形式的密文：

1
2
3
4
5
6
def chal():
    key = urandom(16)
    iv = urandom(16)
    flag = ('NCTF{'+sha1(secret).hexdigest()+'}').encode()
    tmp = AES.new(key,AES.MODE_CBC,iv)
    enc = tmp.encrypt(padding(iv+flag))

通过 CBC 的特性我们知道，给出的 enc 第一个分组解密（ECB）得到的明文是已知的 ，同时第一个密文分组等价于 flag 密文的 IV 值。有了已知明文分组，就能很轻松地进行我们上面阐述地两种攻击，解密任意加密分组了。记我们得到的四个分组如下 ，其中 对应的明文是全 0 字节，基本流程如下：

  1. 利用诸如 形式的密文，进行已知明文的 2-block 攻击，得到 解密后的最后两个字节。（flag 未知的字节是hex，此步最多需要交互 次）
  2. 利用诸如 形式的密文，进行单分组攻击，得到 的完整解密结果 。（flag 未知的字节是hex，此步最多需要交互 次）
  3. 以此类推，解密 。

 

EXP

flag 是固定的，下面的 exp 没有处理 的低未知比特信息。解密单个 block 的 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
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
from pwn import *
from Crypto.Util.number import long_to_bytes
import time
import re
from itertools import product
import string
from hashlib import sha1,sha256
from tqdm import tqdm
from Crypto.Cipher import AES


table = string.ascii_letters+string.digits
flag_kernel_table = b"0123456789abcdef}{"

def xor(a,b):
    return bytes([x^y for x,y in zip(a,b)])

def solve_pow():
    io.recvuntil(b"[+] sha256(XXXX+")
    proof, target = io.recvline().decode().strip().split(") == ")
    print(f"[+] {proof = }")
    print(f"[+] {target = }")  
    bf = product(table, repeat=4)
    for i in tqdm(bf):
        prefix = "".join(i)
        if sha256((prefix + proof).encode()).hexdigest() == target:
            print("[+] pow solved")
            io.sendlineafter(b'[+] Plz tell me XXXX: ', prefix.encode())
            return

def oracle(ct):
    io.sendlineafter(b"Try unlock:", ct.hex().encode())
    res = io.recvline().decode().strip()
    if "Hey you unlock me" in res:
        return 2
    elif "Bad key... do you even try?" in res:
        return 1
    elif "weirdo" in res:
        return 0
    else:
        print(f"[+] check {res = }")
        return -1

    
def guess_last_two_bytes(block_iv, block_ct, known_pt):
    # known_pt is the plaintext of block_iv
    # Note cases not considered: 
    # case 1 : last two equal
    known_pt_arr = bytearray(known_pt)
    block_iv_arr = bytearray(block_iv)
    # guess X, Y
    for X in flag_kernel_table:
        for Y in flag_kernel_table:
            new_iv = known_pt_arr[:]
            new_iv[0] = new_iv[0] ^ X
            new_iv[1] = new_iv[1] ^ Y
            check = oracle(new_iv + block_iv + block_ct)
            if check == 1:
                print(f"[+] yes, find X = {bytes([X])}, Y = {bytes([Y])}")
                return X, Y
                
def guess_first_two_bytes(block_iv, block_ct, known_last_two):
    X0, Y0 = known_last_two
    for X in flag_kernel_table:
        for Y in flag_kernel_table:
            new_iv = bytearray(block_iv)
            new_iv[0] = new_iv[0] ^ X ^ X0
            new_iv[1] = new_iv[1] ^ Y ^ Y0
            check = oracle(new_iv + block_ct)
            if check == 1:
                print(f"[+] yes, find X = {bytes([X])}, Y = {bytes([Y])}")
                return X, Y

def guess_middle_bytes(block_iv, block_ct, known_first_two, known_last_two):
    X0, Y0  = known_first_two
    X, Y = known_last_two
    init_iv = bytearray(block_iv)
    # fix the first two bytes to X = 0xff, Y = 0x00
    init_iv[0] = init_iv[0] ^ X0 ^ 0xff
    init_iv[1] = init_iv[1] ^ Y0 ^ 0x00
    # also the last two bytes
    init_iv[-2] = init_iv[-2] ^ X ^ 0xff
    init_iv[-1] = init_iv[-1] ^ Y ^ 0x00
    pt = bytes(last_two)
    for i in range(16 - 4):
        # set the last i + 2 bytes be 0x00
        pos = 15 - 2 - i
        print(f"[+] try {pos = }")
        init_iv[pos + 1] = init_iv[pos + 1] ^ 0xff ^ 0x00
        # guess:
        for b in flag_kernel_table:
            new_iv = init_iv[:]
            new_iv[pos] = new_iv[pos] ^ b ^ 0xff
            check = oracle(new_iv + block_ct)
            if check == 1:
                print(f"[+] {pos}-th byte : {chr(b)}")
                init_iv = new_iv[:]
                pt = bytes([b]) + pt
                break
    print(f"[+] {pt = }")

# io = process(["python3" , "./chall.py"])
# io = remote("127.0.0.1", 11111)
# 8.222.191.182
io = remote("115.159.221.202", 11111)
# io = remote_pow_solver("115.159.221.202",11111)
solve_pow()

io.recvuntil(b"key:")
ct = io.recvline()
ct = bytes.fromhex(ct.decode())

Z = b"\x00"*16
Zero_enc = ct[:16]
real_iv = ct[:16]
real_ct = ct[16:]

# [+] yes, find X = b'd', Y = b'0'
X,  Y = guess_last_two_bytes(real_iv, real_ct[:16], Z)
last_two = [X, Y]
X0, Y0 = guess_first_two_bytes(real_iv, real_ct[:16], last_two)
# last_two = b"d1"
prefix = b"NCTF{"
guess_middle_bytes(real_iv, real_ct[:16], prefix[:2], last_two)
# NCTF{aa7a62268d1

# block 2
known_pt = b"NCTF{aa7a62268d1"
known_pure_pt = xor(known_pt, real_iv)
# X,  Y = guess_last_two_bytes(real_ct[:16], real_ct[16:32], known_pure_pt)
# [+] yes, find X = b'2', Y = b'4'
# last_two = [X, Y]
# X0, Y0 = guess_first_two_bytes(real_ct[:16], real_ct[16:32], last_two)
# [+] yes, find X = b'6', Y = b'8'
# first_two = [X0, Y0]
last_two = b"24"
first_two = b"68"
guess_middle_bytes(real_ct[:16], real_ct[16:32], first_two, last_two)
# b'68ee2c717abf0f24'

# block 3
known_pt = b"68ee2c717abf0f24"
known_pure_pt = xor(known_pt, real_ct[:16])
# X,  Y = guess_last_two_bytes(real_ct[16:32], real_ct[32:48], known_pure_pt)
# [+] yes, find X = b'6', Y = b'8'
# last_two = [X, Y]
# X0, Y0 = guess_first_two_bytes(real_ct[16:32], real_ct[32:48], last_two)
# [+] yes, find X = b'a', Y = b'b'
# first_two = [X0, Y0]

last_two = b"69"
first_two = b"ab"
guess_middle_bytes(real_ct[16:32], real_ct[32:48], first_two, last_two)

# b'ab9fcd572b021}69'
# b"NCTF{aa7a62268d1"+ b'69ee2c717abf0f24' + b"ab9fcd572b021}69"
# NCTF{aa7a62268d169ee2c717abf0f24ab9fcd572b021}

 

FaultMilestone

题目源码附件下载 : FaultMilestone.zip

 

Differenti Fault Analysis

这题是很经典的差分故障分析（Differenti Fault Analysis），用的是 DES。之前在 n1ctf 上打过一道基于国密 SM4 的 DFA 题，非预期打的，因为当时分组长度只有 32 比特，可以直接拿 c 写爆破脚本，恢复出轮密钥。这里 DES 的分组长度是 48 比特（密钥长 56 比特），只能用 DFA 打。这题的场景其实就是 ： Differential Fault Analysis on DES Middle Rounds 。

分析 encrypt 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
def encrypt(plain: List[int], sub_keys: List[List[int]],dance=0) -> List[int]:
    plain = IP(plain)
    L, R = plain[:32], plain[32:]
    for i in range(16):
        if i == 13 and dance:R[2] = R[2]^1
        prev_L = L
        L = R
        expanded_R = EP(R)
        xor_result = [a ^ b for a, b in zip(expanded_R, sub_keys[i])]
        substituted = S_box(xor_result)
        permuted = P(substituted)
        R = [a ^ b for a, b in zip(permuted, prev_L)]
    # omit

在 DES 的第 14 轮加密的时候，引入了一个差分故障，该差分只有单个比特，因此只会影响一个 Sbox，也就是说只会影响 4 个 bit。记 DES 的轮函数为 ，单轮作用如下：

feistel

本题中故障差分产生在第 14 轮的右边，也就等价于发生在第十三轮的左边，下图中 (a) 即本题的差分场景：

error_trans

记差分为 ，未发生故障时密文为 ，其对应的第十六轮输出为 ，发生差分故障后密文为 ，其对应的第十六轮输出为 。由上图中差分的传播路径可知，最终传播到 15 轮末（16 轮起始）左边时，差分的可能取值为

而在第 16 轮，如下差分等式恒成立：

其中 均可从密文 推出，而如果我们已知 ，就能够尝试穷举，从上面的等式中将 可能的值得到。注意到轮函数 中差分的作用是每 6 个比特独立的：

因此，穷举过程只需要 的复杂度。回到本题， 并不是一个确定的取值，而是一个差分集合，但是，该差分只经过了一轮 函数扩散混淆，最多只会影响到扩展的 6 个 bit，在轮密文 输出里最多只会影响到 4 个 bit。因此 至多有 4 个比特不确定，其他均为 0。实际 的差分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 659,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 374,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 366,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 394,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 635,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 555,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 130,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 232,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 259,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 122,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 370
}

将 函数中 permutation 的扩散作用取消 （作用一次 ），可能的差分结果为

1
2
3
4
5
6
7
8
9
10
11
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

只有前 4 个比特是不确定的，后 28 比特完全确定，与我们预期完全相符。因此利用多个故障差分密文对，我们可以恢复出第16 轮轮密钥的绝大多数比特，不使用差分路径的概率去筛选，本题到最后也只有 13 可能的 的取值。

至此，差分故障分析的核心思路就到这里结束了。后面就剩下怎么从 DES 的单次轮密钥恢复出原始密钥比特了。

 

DES 主密钥恢复

轮密钥生成函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_sub_key(key: List[int]) -> List[List[int]]:
    key = PC_1(key)
    L, R = key[:28], key[28:]
    sub_keys = []

    for i in range(16):
        for j in range(ROTATIONS[i]):
            L.append(L.pop(0))
            R.append(R.pop(0))

        combined = L + R
        sub_key = PC_2(combined)
        sub_keys.append(sub_key)
    return sub_keys

DES 的主密钥是 64 位，有效密钥是 56 位，轮密钥是 48 位，而需要解密 DES ，只需要 56 位的有效密钥即可。由上述轮密钥生成过程可以看出，轮密钥由有效密钥进行若干循环移位，最后通过置换（会丢弃 8 个比特）得到，完全是可逆的，因此通过恢复出的 ，我们可以恢复出有效密钥的 48 位，剩下 8 个比特穷举，然后去拿密文解密验证验证即可。

 

EXP

EXP 以及 Sovler 。

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
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
from operator import add
from typing import List
from functools import reduce
from Crypto.Util.number import long_to_bytes,bytes_to_long
import random
import string
from os import urandom
from hashlib import sha256
from operator import add

def bitxor(plain1: List[int], plain2: List[List[int]]) -> List[int]:
    return [int(i) for i in bin(int(''.join(str(i) for i in plain1),2)^int(''.join(str(i) for i in plain2),2))[2:].zfill(64)]

def bytes2bits(bytes):
	result = reduce(add, [list(map(int, bin(byte)[2:].zfill(8))) for byte in bytes])
	return result

def bits2bytes(bits):
	result = ''
	for i in bits:result += str(i) 
	return long_to_bytes(int(result,2))

_IP = [57, 49, 41, 33, 25, 17, 9,  1,
	59, 51, 43, 35, 27, 19, 11, 3,
	61, 53, 45, 37, 29, 21, 13, 5,
	63, 55, 47, 39, 31, 23, 15, 7,
	56, 48, 40, 32, 24, 16, 8,  0,
	58, 50, 42, 34, 26, 18, 10, 2,
	60, 52, 44, 36, 28, 20, 12, 4,
	62, 54, 46, 38, 30, 22, 14, 6
]

def IP(plain: List[int]) -> List[int]:
    return [plain[x] for x in _IP]

__pc1 = [56, 48, 40, 32, 24, 16,  8,
	  0, 57, 49, 41, 33, 25, 17,
	  9,  1, 58, 50, 42, 34, 26,
	 18, 10,  2, 59, 51, 43, 35,
	 62, 54, 46, 38, 30, 22, 14,
	  6, 61, 53, 45, 37, 29, 21,
	 13,  5, 60, 52, 44, 36, 28,
	 20, 12,  4, 27, 19, 11,  3
]

__pc2 = [
	13, 16, 10, 23,  0,  4,
	 2, 27, 14,  5, 20,  9,
	22, 18, 11,  3, 25,  7,
	15,  6, 26, 19, 12,  1,
	40, 51, 30, 36, 46, 54,
	29, 39, 50, 44, 32, 47,
	43, 48, 38, 55, 33, 52,
	45, 41, 49, 35, 28, 31
]
ROTATIONS = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

def PC_1(key: List[int]) -> List[int]:
    return [key[x] for x in __pc1]


def PC_2(key: List[int]) -> List[int]:
    return [key[x] for x in __pc2]

def invPC_1(key: List[int]) -> List[int]:
    return [key[__pc1.index(x)] for x in range(56)]

def invPC_2(key: List[int]) -> List[int]:
    return [key[__pc2.index(x)] for x in range(56) if x in __pc2]

def get_sub_key(key: List[int]) -> List[List[int]]:
    key = PC_1(key)
    L, R = key[:28], key[28:]
    sub_keys = []

    for i in range(16):
        for j in range(ROTATIONS[i]):
            L.append(L.pop(0))
            R.append(R.pop(0))

        combined = L + R
        sub_key = PC_2(combined)
        sub_keys.append(sub_key)
    return sub_keys

def get_sub_key_from_active_key(active_key: List[int]) -> List[List[int]]:
    L, R = active_key[:28], active_key[28:]
    sub_keys = []

    for i in range(16):
        for j in range(ROTATIONS[i]):
            L.append(L.pop(0))
            R.append(R.pop(0))

        combined = L + R
        sub_key = PC_2(combined)
        sub_keys.append(sub_key)
    return sub_keys

def fill_missing_8bits(round_key: List[int]):
    possible_keys = []
    missing_pos = [8, 17, 21, 24, 34, 37, 42, 53]
    len_split = [j - i - 1 for i,j in zip([-1] + missing_pos, missing_pos + [56])]
    assert sum(len_split) == 48, f"{len_split}"
    rk_split = []
    for i in len_split:
        rk_split.append(round_key[:i])
        round_key = round_key[i:]
    assert len(rk_split) == 9
    
    for i in range(2**8):
        bits = [int(x) for x in format(i, '08b')]
        possible_key = rk_split[0][:]
        for i in range(8):
            possible_key += [bits[i]]
            possible_key += rk_split[i+1][:]
        possible_keys.append(possible_key)
    return possible_keys

def recover_keybits(round_key, round = 16):
    shift = 56 - sum(ROTATIONS[:round])
    round_key = invPC_2(round_key)
    possible_keys = fill_missing_8bits(round_key)
    final_candidates = []
    for full_key in possible_keys:
        L, R = full_key[:28], full_key[28:]
        for i in range(shift):
            L.append(L.pop(0))
            R.append(R.pop(0))
        final = L + R
        final_candidates.append(final)
    return final_candidates

__ep = [31,  0,  1,  2,  3,  4,
		 3,  4,  5,  6,  7,  8,
		 7,  8,  9, 10, 11, 12,
		11, 12, 13, 14, 15, 16,
		15, 16, 17, 18, 19, 20,
		19, 20, 21, 22, 23, 24,
		23, 24, 25, 26, 27, 28,
		27, 28, 29, 30, 31,  0
]

__p = [15,  6, 19, 20, 28, 11, 27, 16,
		0, 14, 22, 25,  4, 17, 30,  9,
		1,  7, 23, 13, 31, 26,  2,  8,
		18, 12, 29,  5, 21, 10,  3, 24
]

def EP(data: List[int]) -> List[int]:
    return [data[x] for x in __ep]

def P(data: List[int]) -> List[int]:
    return [data[x] for x in __p]

__s_box = [

	[
		[14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7],
		[ 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8],
		[ 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0],
		[15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13]
	],


	[
		[15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10],
		[ 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5],
		[ 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15],
		[13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9]
	],


	[
		[10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8],
		[13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1],
		[13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7],
		[ 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12]
	],


	[
		[ 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15],
		[13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9],
		[10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4],
		[ 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14]
	],


	[
		[ 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9],
		[14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6],
		[ 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14],
		[11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3]
	],


	[
		[12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11],
		[10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8],
		[ 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6],
		[ 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13]
	],


	[
		[ 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1],
		[13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6],
		[ 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2],
		[ 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12]
	],


	[
		[13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7],
		[ 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2],
		[ 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8],
		[ 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11]
	]
]

def S_box(data: List[int]) -> List[int]:
    output = []
    for i in range(0, 48, 6):
        row = data[i] * 2 + data[i + 5]
        col = reduce(add, [data[i + j] * (2 ** (4 - j)) for j in range(1, 5)])
        output += [int(x) for x in format(__s_box[i // 6][row][col], '04b')]
    return output

def encrypt(plain: List[int], sub_keys: List[List[int]],dance=0) -> List[int]:
    plain = IP(plain)
    L, R = plain[:32], plain[32:]
    for i in range(16):
        if i == 13 and dance:R[2] = R[2]^1
        prev_L = L
        L = R
        expanded_R = EP(R)
        xor_result = [a ^ b for a, b in zip(expanded_R, sub_keys[i])]
        substituted = S_box(xor_result)
        permuted = P(substituted)
        R = [a ^ b for a, b in zip(permuted, prev_L)]

    cipher = R + L
    cipher = [cipher[x] for x in [39,  7, 47, 15, 55, 23, 63, 31,
                                38,  6, 46, 14, 54, 22, 62, 30,
                                37,  5, 45, 13, 53, 21, 61, 29,
                                36,  4, 44, 12, 52, 20, 60, 28,
                                35,  3, 43, 11, 51, 19, 59, 27,
                                34,  2, 42, 10, 50, 18, 58, 26,
                                33,  1, 41,  9, 49, 17, 57, 25,
                                32,  0, 40,  8, 48, 16, 56, 24]]
    
    return cipher

def decrypt(cipher: List[int], sub_keys: List[List[int]]) -> List[int]:
    return encrypt(cipher, sub_keys[::-1])


delta_r15 = {
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 659,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 374,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 366,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 394,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 635,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 555,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)": 130,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 232,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 259,
    "(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 122,
    "(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)": 370
}


# inv permutation in f function
def inv_FP(data: List[int]) -> List[int]:
    return [data[__p.index(x)] for x in range(32)]

def f_func_full(R: List[int], sub_key : List[int]):
    expanded_R = EP(R)
    xor_result = [a ^ b for a, b in zip(expanded_R, sub_key)]
    substituted = S_box(xor_result)
    permuted = P(substituted)
    return permuted

def f_func_without_perm(R: List[int], sub_key : List[int]):
    expanded_R = EP(R)
    xor_result = [a ^ b for a, b in zip(expanded_R, sub_key)]
    substituted = S_box(xor_result)
    return substituted[:32]

def xor(a,b):
    assert len(a) == len(b), f"{len(a) = }, {len(b) = }"
    return [x^y for x, y in zip(a,b)]



# remove the permutation for Delta_R15
inv_P_Delta_R15_list = []
for delta in delta_r15 :
    rd15 = list(eval(delta))
    freq = delta_r15[delta]
    inv_P_Delta_R15 = inv_FP(rd15)
    inv_P_Delta_R15_list.append(inv_P_Delta_R15)
    print(f"{inv_P_Delta_R15 = } {freq = }")
    
inv_P_Delta_R15_list_f4 = [i[:4] for i in inv_P_Delta_R15_list]

enc1 = ['a3363b2d3c43e6a2', '559a2f1cef0ed06c', '45249287bc5cd2eb', '35c30fa315d58d4f', '52a97412ef644af4']
enc2 = ['3b03dca831c12f61', 'a08bbf7bafffef3f', '04140443adde0eaa', '75e26aab90efaa0c', '07b855d1a2830b32']

lhs = []
Ls = []
for ct, _ct in zip(enc1, enc2):
    # inverse last_Perm
    ct = IP(bytes2bits(bytes.fromhex(ct)))
    _ct = IP(bytes2bits(bytes.fromhex(_ct)))
    # roll back L, R
    R16, L16 = ct[:32], ct[32:]
    _R16, _L16 = _ct[:32], _ct[32:]
    # R16 ^ _R16 = f_k16(L16) ^ f_k16(_L16) ^ delta
    # invFP(R16 ^ _R16) = invFP(f_k16(L16)) ^ invFP(f_k16(_L16)) ^ invFP(delta)
    # invFP(R16 ^ _R16) = f_k16_np(L16)) ^ f_k16_np(_L16) ^ invFP(delta)
    lhs.append(inv_FP(xor(R16, _R16)))
    Ls.append((L16, _L16))
    
sk0s = []
# check sk0
for i in range(1):
    for ski in range(2**6):
        sk_list = [0] * 48
        sk_list[i*6 : i*6 + 6] = list(map(int, bin(ski)[2:].zfill(6)))
        good = 1
        for lh, (L16, _L16) in zip(lhs, Ls):
            t = xor(f_func_without_perm(L16, sk_list), f_func_without_perm(_L16, sk_list))
            result = xor(t, lh)
            if result[:4] not in inv_P_Delta_R15_list_f4:
                good = 0
                break
        if good:
            print(f"[+] possilbe {i}-th ski {ski = }")     
            sk0s.append(ski)
            
sks = []
# check ski
for i in range(1, 8):
    for ski in range(2**6):
        sk_list = [0] * 48
        sk_list[i*6 : i*6 + 6] = list(map(int, bin(ski)[2:].zfill(6)))
        good = 1
        for lh, (L16, _L16) in zip(lhs, Ls):
            t = xor(f_func_without_perm(L16, sk_list), f_func_without_perm(_L16, sk_list))
            result = xor(t, lh)
            if result[4*i: 4*i + 4] != [0, 0, 0, 0]:
                good = 0
                break
        if good:
            print(f"[+] possilbe {i}-th ski {ski = }")
            sks.append(ski)

# generate all possible round key
round_key_cadidate = []
round_key_fixed = []
for ski in sks:
    round_key_fixed += list(map(int, bin(ski)[2:].zfill(6)))
for sk0 in sk0s:
    round_key_cadidate.append(list(map(int, bin(sk0)[2:].zfill(6))) + round_key_fixed[:])
print(f"[+] {len(round_key_cadidate) = }")

cts = [bytes2bits(bytes.fromhex(enc)) for enc in enc1]

# check round key and generate all possible active keys
for round_key in round_key_cadidate:
    active_key_list = recover_keybits(round_key, 16)
    for active_key in active_key_list:
        rks = get_sub_key_from_active_key(active_key)
        pt = bits2bytes(decrypt(cts[0], rks))
        if all( 32 <= num<= 128 for num in pt):
            secret = b"".join([bits2bytes(decrypt(ct, rks)) for ct in cts])
            # recheck            
            if all( 32 <= num<= 128 for num in secret):
                print(f"[+] cracked {round_key = }")
                print(f"[+] cracked {active_key = }")
                print(f"[+] cracked {secret = }")

 

CalabiYau

题目源码附件下载 ：CalabiYau.zip

 

题解

作者给的代码有 typo ，而且也不能直接跑。整个代码看起来像是 Ring-LWE 的框架。定义有限域 上的多项式商环 ，其中 ， 是一个随机生成 2042 比特的大素数。

在 上随机采样二元系数，得到多项式 ，和在 上随机 ，最后公钥如下：

实际上这题和 Ring-LWE 关系不大，这里就直接跳过。来到题目交互部分。第一部分我们能指定一个 seed 来生成 多项式，然后输入一个公钥 ，服务端会返回 ，其中 如下：

其中取整符号对所有系数进行，我们只需要让 ，则 ，即泄露了 alice 的私钥，就能顺利进入三月七的 Party 了（为什么三月七的 Party 都是 Alice 和 Bob 呢，这可太不二次元了，雾）。

之后的场景是一个 Oracle，Bob 私钥公钥信息我们均不知道，但是 Bob 会不断更他的私钥 ，并且把 返回给我们。看到这里，如果对多项式乘法和格比较熟悉，就能发现这其实是一个 Hidden Subset Sum Problem （HSSP）。因为在 上的多项式乘法可以展开成矩阵乘法，即多项式的向量表示为 ，以及，多项式乘法矩阵为

记 ，则 ，本题中 向量固定，每次生成的 都是二元的，即 上的元素都在 上，每个 都对应了集合 的一个子集和问题，但是这里 均未给出，所以是 HSSP 问题。

HSSP 问题的求解方法可以使用正交格攻击，Nguyen-Stern 算法求解，或者 OL+Multivariate 的算法，感兴趣的读者可以参考我另一篇博客：正交格攻击-HSSP 。这里就不再赘述。

 

EXP

HSSP 的 Solver 直接用的论文 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem 的代码，使用 flatter 用于加速 LLL reduction，论文代码的 recovery binary 函数没有用标准的 NS 算法来写，所以可能恢复不出足够的目标向量，多跑几次就好了。

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
from pwn import remote, context
from itertools import product
import string
import hashlib
from tqdm import tqdm
from ast import literal_eval
from time import time

# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b,x0):
    m=b.length()
    M=Matrix(ZZ,m,m)

    for i in range(1,m):
        M[i,i]=1
    M[1:m,0]=-b[1:m]*inverse_mod(b[0],x0)
    M[0,0]=x0

    for i in range(1,m):
        M[i,0]=mod(M[i,0],x0)

    return M

def allones(v):
    if len([vj for vj in v if vj in [0,1]])==len(v):
        return v
    if len([vj for vj in v if vj in [0,-1]])==len(v):
        return -v
    return None

def recoverBinary(M5):
    lv=[allones(vi) for vi in M5 if allones(vi)]
    n=M5.nrows()
    for v in lv:
        for i in range(n):
            nv=allones(M5[i]-v)
            if nv and nv not in lv:
                lv.append(nv)
            nv=allones(M5[i]+v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)

def allpmones(v):
    return len([vj for vj in v if vj in [-1,0,1]])==len(v)

# Computes the right kernel of M using LLL.
# We assume that m>=2*n. This is only to take K proportional to M.height()
# We follow the approach from https://hal.archives-ouvertes.fr/hal-01921335/document
def kernelLLL(M):
    n=M.nrows()
    m=M.ncols()
    if m<2*n: return M.right_kernel().matrix()
    K=2**(m//2)*M.height()
  
    MB=Matrix(ZZ,m+n,m)
    MB[:n]=K*M
    MB[n:]=identity_matrix(m)
  
    # MB2 = MB.T.LLL().T
    MB2 = flatter(MB.T).T
    
    assert MB2[:n,:m-n]==0
    Ke=MB2[n:,:m-n].T

    return Ke

def solve_hssp(h, m, n, q):
    x0 = q 
    b = h 
    M = orthoLattice(b,x0)

    t = cputime()
    # M2 = M.LLL()
    M2 = flatter(M)
    print("LLL step1: %.1f" % cputime(t))

    MOrtho = M2[:m-n]

    print("  log(Height,2)=",int(log(MOrtho.height(),2)))

    t2 = cputime()
    ke = kernelLLL(MOrtho)

    print("  Kernel: %.1f" % cputime(t2))
    print("  Total step1: %.1f" % cputime(t))

    if n > 170: return

    beta = 2
    tbk = cputime()
    while beta<n:
        if beta==2:
            # M5=ke.LLL()
            M5 = flatter(ke)
        else:
            M5=M5.BKZ(block_size=beta)

        # we break when we only get vectors with {-1,0,1} components
        if len([True for v in M5 if allpmones(v)]) == n: break

        if beta==2:
            beta = 10
        else:
            beta += 4

    print("BKZ beta=%d: %.1f" % (beta,cputime(tbk)))
    t2 = cputime()
    MB = recoverBinary(M5)
    print("  Recovery: %.1f" % cputime(t2))
    print("  Number of recovered vector = ", MB.nrows())

    NS = MB.T
    invNSn = matrix(Integers(x0),NS[:n]).inverse()
    ra = invNSn * b[:n]
    print("  Total step2: %.1f" % cputime(tbk))
    print("  Total time: %.1f" % cputime(t))
    return ra

    
# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
def flatter(M):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in $$PATH
    z = '[[' + ']\n['.join(' '.join(map(str,row)) for row in M) + ']]'
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int,findall(b'-?\\d+', ret)))

# context.log_level = "debug"
table = string.ascii_letters+string.digits
# nc 115.159.221.202 11110 (
def solve_pow():
    io.recvuntil(b"[+] sha256(XXXX+")
    proof, target = io.recvline().decode().strip().split(") == ")
    print(f"[+] {proof = }")
    print(f"[+] {target = }")  
    bf = product(table, repeat=4)
    for i in tqdm(bf):
        prefix = "".join(i)
        if hashlib.sha256((prefix + proof).encode()).hexdigest() == target:
            print("[+] pow solved")
            io.sendlineafter(b'[+] Plz tell me XXXX: ', prefix.encode())
            return
        
def input2list(data):
    data = data.replace('[','')
    data = data.replace(']','')
    data = data.split(',')
    data = list(map(int,data))
    return data

def Bob_Send():
    io.sendlineafter(b'>', str(1).encode())
    return input2list(io.recvline().decode().strip())
    
    

io = remote("115.159.221.202", int(11110))
solve_pow()
io.recvline()
N = int(io.recvline().decode().strip().split(" = ")[1])
q = int(io.recvline().decode().strip().split(" = ")[1])
PRq.<a> = PolynomialRing(Zmod(q))
Rq = PRq.quotient(a**N - 1, 'x') 
seed = 0

io.sendlineafter(b'>', str(seed).encode())
io.sendlineafter(b'>', str(list([q//4 + 10])).encode())
io.recvuntil(b"Here are alice's answer:\n")

alice_pk_list = input2list(io.recvline().decode().strip())
alice_w_list = input2list(io.recvline().decode().strip())
print(f"[+] Alice pk, w received")
print(io.recvline().decode().strip())
io.sendlineafter(b'>', str(alice_w_list).encode())
print(io.recvline().decode().strip())

print("start to get Bob sending")
# p, h, s = gen_HSSP(n,m,pbits)
H1 = Bob_Send()
H2 = Bob_Send()
h = vector([ZZ(num) for num in H1 + H2])
p = q
F = GF(p)
n = 128
m = 128 * 2
print(f"start to solve HSSP with {m = } {n = }")
ra = solve_hssp(h, m, n, q)

ra = sorted([ZZ(num) for num in ra])

h2x = Rq(H2)
rax = Rq(ra)

rs = h2x * rax^-1
print(f"[+] check {rs = }")

io.sendlineafter(b'>', str(2).encode())
io.sendlineafter(b'>', str(list(rs)).encode())
print(io.recvline())

 

Sign

题目源码附件下载 ：sign.zip

 

题解

真签到题，NTRU 加密，给了公钥，甚至私钥，因此写一个解密函数即可。

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

n=509
p=3
q=512
d=3
Zx.<x> = ZZ[]
# R.<x> = ZZ[]
def balancedmod(f,q):
    g = list( ((f[i] + q//2) % q) - q//2 for i in range(n) )
    return Zx(g)

def cyclicconvolution(f, g):
    return (f*g) % (x^n-1)

def invertmodprime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
    assert q.is_power_of(2)
    g = invertmodprime(f,2)
    while True:
        r = balancedmod(cyclicconvolution(g,f),q)
        if r == 1: return g
        g = balancedmod(cyclicconvolution(g,2 - r),q)

def encrypt(message, publickey):
    r = rpoly()
    return balancedmod(cyclicconvolution(publickey, r) + message, q)

def decrypt(cipher,f,fp):
    # cipher=Zx(cipher)
    a=balancedmod(cyclicconvolution(f, cipher), q)
    m=balancedmod(cyclicconvolution(fp, a),p)
    return m

def attack(publickey):
    recip3 = lift(1/Integers(q)(3))
    publickeyover3 = balancedmod(recip3 * publickey,q)
    M = matrix(2 * n)
    for i in range(n):
        M[i,i] = q
    for i in range(n):
        M[i+n,i+n] = 1
        c = cyclicconvolution(x^i,publickeyover3)
        for j in range(n):
            M[i+n,j] = c[j]
    M = M.LLL()
    for j in range(2 * n):
        try:
            f = Zx(list(M[j][n:]))
            f3 = invertmodprime(f,3)
            return (f,f3)
        except:pass
    return (f,f)

fx =  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
gx =  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
hx =  [292, 374, 91, 384, 263, 330, 77, 497, 294, 141, 485, 464, 46, 478, 315, 100, 287, 1, 337, 477, 451, 387, 340, 370, 384, 19, 158, 440, 377, 177, 235, 340, 166, 359, 488, 332, 252, 443, 256, 453, 33, 282, 175, 18, 218, 208, 414, 147, 12, 468, 155, 34, 109, 390, 312, 472, 345, 176, 9, 184, 100, 414, 293, 366, 132, 128, 223, 242, 137, 223, 268, 259, 446, 57, 463, 344, 459, 115, 509, 510, 82, 42, 408, 139, 341, 351, 511, 339, 317, 139, 317, 297, 288, 58, 33, 120, 244, 194, 44, 128, 278, 130, 449, 282, 274, 376, 209, 240, 148, 426, 244, 319, 251, 438, 317, 166, 161, 37, 361, 468, 172, 116, 211, 64, 446, 162, 301, 447, 92, 325, 285, 4, 8, 160, 382, 365, 413, 150, 141, 323, 107, 225, 466, 93, 86, 219, 174, 198, 155, 88, 194, 259, 140, 36, 82, 462, 182, 496, 250, 337, 39, 435, 448, 365, 262, 146, 89, 283, 195, 395, 216, 159, 312, 53, 70, 485, 368, 130, 491, 474, 325, 4, 205, 1, 292, 330, 186, 66, 137, 291, 452, 236, 25, 114, 407, 125, 343, 2, 304, 267, 459, 432, 129, 21, 197, 51, 26, 342, 457, 163, 51, 52, 82, 229, 332, 72, 408, 242, 218, 286, 368, 503, 498, 434, 135, 311, 321, 205, 269, 318, 19, 119, 422, 425, 463, 368, 317, 99, 178, 390, 8, 127, 156, 27, 332, 437, 87, 187, 92, 115, 380, 54, 236, 287, 259, 386, 391, 94, 312, 454, 459, 340, 382, 424, 25, 318, 47, 249, 115, 20, 89, 82, 377, 328, 231, 298, 402, 336, 452, 264, 265, 83, 254, 156, 449, 34, 99, 412, 101, 183, 38, 142, 231, 181, 495, 6, 327, 278, 92, 452, 372, 12, 91, 102, 277, 98, 418, 22, 32, 493, 50, 374, 230, 479, 496, 6, 382, 300, 496, 157, 1, 221, 418, 381, 275, 391, 199, 472, 5, 222, 448, 377, 102, 468, 94, 35, 6, 6, 464, 452, 453, 354, 277, 425, 120, 501, 172, 222, 314, 362, 6, 105, 387, 77, 14, 112, 289, 358, 495, 350, 411, 378, 30, 89, 115, 171, 42, 32, 427, 125, 420, 486, 435, 151, 234, 416, 428, 425, 250, 142, 301, 245, 154, 338, 223, 292, 27, 194, 220, 34, 283, 255, 53, 5, 420, 134, 351, 216, 92, 242, 39, 454, 96, 239, 390, 182, 368, 463, 176, 187, 25, 122, 441, 54, 171, 426, 435, 318, 345, 166, 224, 258, 246, 349, 50, 400, 381, 236, 315, 439, 249, 201, 262, 95, 210, 327, 199, 205, 402, 175, 280, 337, 388, 205, 336, 52, 68, 364, 293, 462, 388, 354, 169, 163, 72, 374, 220, 355, 275, 36, 208, 198, 363, 369, 344, 61, 13, 230, 196, 190, 463, 351, 37, 276, 336, 110, 352, 56, 117, 376, 500, 373, 438, 309, 496, 400, 76, 169, 447, 434, 255, 456, 511, 414, 83, 369, 174, 291, 213, 227, 254, 186, 145, 402, 265, 13, 20, 212, 442]
e=[219, 149, 491, 115, 68, 464, 91, 223, 480, 506, 103, 373, 19, 52, 368, 467, 304, 380, 495, 372, 506, 318, 320, 263, 120, 126, 165, 271, 435, 378, 443, 261, 336, 381, 57, 360, 36, 155, 424, 458, 84, 80, 187, 261, 501, 279, 167, 13, 241, 85, 214, 133, 483, 374, 430, 401, 265, 127, 497, 405, 60, 34, 81, 422, 423, 200, 276, 424, 245, 437, 31, 193, 282, 154, 93, 13, 499, 190, 1, 304, 415, 189, 82, 472, 13, 488, 366, 364, 319, 121, 322, 120, 468, 134, 305, 228, 288, 284, 33, 430, 125, 366, 212, 207, 227, 201, 286, 377, 376, 57, 336, 379, 101, 461, 375, 101, 475, 126, 306, 73, 88, 1, 149, 378, 381, 129, 402, 341, 390, 57, 305, 139, 436, 101, 386, 460, 43, 468, 9, 449, 255, 184, 374, 466, 429, 167, 101, 247, 183, 159, 346, 45, 79, 192, 259, 32, 140, 151, 16, 214, 42, 450, 111, 7, 303, 286, 435, 491, 339, 248, 114, 185, 103, 81, 414, 100, 485, 428, 137, 13, 243, 202, 62, 208, 136, 376, 88, 158, 377, 404, 355, 194, 452, 373, 107, 290, 89, 489, 259, 462, 169, 235, 86, 214, 333, 472, 343, 487, 19, 371, 203, 234, 315, 339, 430, 133, 96, 161, 278, 13, 20, 87, 303, 466, 353, 139, 395, 131, 298, 85, 144, 244, 150, 488, 254, 284, 89, 300, 297, 288, 245, 439, 307, 222, 110, 343, 318, 202, 429, 81, 203, 468, 144, 140, 480, 370, 501, 14, 490, 278, 493, 390, 214, 108, 174, 150, 287, 197, 497, 374, 420, 298, 222, 188, 146, 298, 466, 459, 456, 16, 131, 253, 153, 481, 342, 498, 173, 12, 452, 197, 233, 18, 439, 332, 185, 48, 330, 4, 99, 105, 75, 306, 174, 492, 131, 39, 126, 491, 79, 145, 186, 493, 23, 230, 195, 118, 310, 173, 244, 80, 25, 502, 373, 457, 275, 282, 26, 206, 14, 181, 61, 391, 454, 417, 370, 70, 413, 389, 434, 400, 88, 417, 364, 458, 496, 425, 12, 280, 102, 265, 471, 43, 257, 327, 10, 334, 239, 344, 77, 298, 140, 287, 260, 194, 431, 65, 304, 302, 210, 393, 473, 463, 312, 255, 368, 476, 462, 390, 412, 266, 138, 410, 246, 101, 460, 307, 123, 4, 240, 502, 115, 147, 370, 241, 222, 495, 109, 51, 138, 354, 447, 282, 434, 280, 275, 404, 214, 68, 77, 167, 302, 95, 462, 16, 184, 213, 227, 130, 50, 405, 30, 353, 24, 143, 100, 163, 212, 388, 283, 252, 187, 247, 190, 163, 252, 169, 267, 363, 72, 399, 195, 215, 103, 60, 466, 318, 71, 193, 449, 65, 358, 443, 260, 253, 46, 5, 416, 115, 390, 15, 120, 384, 50, 122, 87, 428, 282, 464, 83, 80, 401, 8, 175, 457, 301, 63, 205, 402, 468, 368, 510, 488, 345, 103, 306, 387, 34, 119, 459, 43, 319, 264, 184, 406, 407, 358, 242, 42, 241, 34, 118, 477, 117, 325, 511, 499, 365, 192, 507]

Rp = PolynomialRing(Zmod(p),'xp')
Rp = Rp.quotient(x^n - 1)
fp = list(Rp(fx) ^ (-1))
m = decrypt(Zx(e),Zx(fx),Zx(fp))
print(int(ZZ(m.coefficients(sparse=False)[:42*8][::-1], 2)).to_bytes(42, "big"))

 

扫一扫，分享到微信

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