2024-corCTF&DeadsecCTF-wp-crypto

记录一下这周做到的几道赛题。

corCTF

steps

题目描述：

Alice and Bob have taken steps to communicate securely.

题目：

from Crypto.Util.number import getPrime
from random import randint
from hashlib import sha512
from secret import FLAG

p = getPrime(1024)

Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

def calculate(n: int) -> Pair:
    out = 0, 1
    base = 1, 1

    while n > 0:
        if n & 1 == 1: out = apply(out, base)
        n >>= 1
        base = apply(base, base)

    return out

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
    return bytes(i ^ j for i, j in zip(a, b))

def main() -> None:
    g = tuple(randint(0, p - 1) for _ in range(2))
    a = randint(0, p)
    b = randint(0, p)

    A = step(g, a)
    B = step(g, b)

    print(p)
    print(g)
    print(A)
    print(B)

    shared = step(A, b)
    assert shared == step(B, a)

    pad = sha512(str(shared).encode()).digest()
    print(xor(FLAG, pad))

if __name__ == "__main__":
    main()

output.txt：

140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'

题目基于一个比较奇怪的DH密钥交换，其中主要的两个函数是apply和calculate，分别作用为(运算皆在模p下)：

• apply：接受两个向量$(x_0,x_1),(y_0,y_1)$作为输入，输出为：

  $$z_0 = x_0y_1 + x_1y_0 - x_0y_0$$ $$z_1 = x_0y_0 + x_1y_1$$

• calculate：显然是一个矩阵快速幂，对于输入的数字n，得到的结果是：

  $$out = \left(\begin{matrix} 0&1\\ 1&1\\ \end{matrix}\right) ^n \left(\begin{matrix} 0\\ 1\\ \end{matrix}\right)$$

然后利用这两个函数商议了用于密钥交换的函数step，对于给定的向量g和私钥x，其得到的结果为apply(g,calculate(x))。然后A、B就利用step函数分别生成自己的密钥，并计算共享密钥：

$$A = apply(g, calculate(a))$$ $$B = apply(g, calculate(b))$$ $$shared = step(A,b) = step(B,a)$$

给出g、A、B，要求计算shared来解密flag。

由于有g、A和B，所以由apply函数用resultant或者groebner可以轻松计算出calculate(a)和calculate(b)的值，而其实计算shared也就是在A的基础上继续计算(B也同理)：

$$shared = apply(A, calculate(b))$$

所以就很容易算出shared来了，因为并不需要解出a、b是多少，只需要知道calculate(a)和calculate(b)就行。

exp：

from Crypto.Util.number import *
from hashlib import sha512

p = 140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
g = (96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
A = (70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
B = (112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
c = b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'

PR.<a0,a1> = PolynomialRing(Zmod(p))
f1 = g[0] * a1 + g[1] * a0 - g[0] * a0 - A[0]
f2 = g[0] * a0 + g[1] * a1 - A[1]
res = Ideal([f1,f2]).groebner_basis()
a0 = -res[0].coefficients()[1]
a1 = -res[1].coefficients()[1]

L = Matrix(Zmod(p),[
    [0,1],
    [1,1]
])
v0 = vector(Zmod(p),[0,1])
a = vector(Zmod(p),[a0,a1])


Pair = tuple[int, int]
def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

def calculate(n: int) -> Pair:
    out = 0, 1
    base = 1, 1

    while n > 0:
        if n & 1 == 1: out = apply(out, base)
        n >>= 1
        base = apply(base, base)

    return out

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
    return bytes(i ^^ j for i, j in zip(a, b))


AB = apply(B, [a0,a1])
pad = sha512(str(AB).encode()).digest()
print(xor(c, pad))


#corctf{w4it_i7's_4ll_f1b0n4cci?}

然而真的想求出a、b其实也并不是一定没有办法，由于刚刚说了calculate实际上是个如下形式的快速幂：

$$out = \left(\begin{matrix} 0&1\\ 1&1\\ \end{matrix}\right) ^n \left(\begin{matrix} 0\\ 1\\ \end{matrix}\right)$$

所以对于calculate(a)来说就是：

$$calculate(a) = \left(\begin{matrix} 0&1\\ 1&1\\ \end{matrix}\right) ^a \left(\begin{matrix} 0\\ 1\\ \end{matrix}\right)$$

所以实际上是求一个矩阵DLP。

monkfish

题目描述：

Hmm... smells like a fishy proof of knowledge...

(Part 1 out of 2)

题目：

#!/usr/bin/sage

import sys
print("I caught a monkfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
    com = apply(F, t)
    verif = apply_verif_info(F, t, s)
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    return (com, t - a * s, verif)

def verif_pok(v, F, pi):
    com = pi[0]
    resp = pi[1]
    verif = pi[2]
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    out1 = apply(F, resp)
    out2 = com + (a * a) * v - a * verif
    return out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
    gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)
assert verif_pok(v, F, pok)

print("m0 =", [list(FF).index(i[0]) for i in list(pok[0])])
print("m1 =", [list(FF).index(i[0]) for i in list(pok[1])])
print("m2 =", [list(FF).index(i[0]) for i in list(pok[2])])

print("Can you catch a monkfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])
m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

assert(m0 != [list(FF).index(i[0]) for i in list(pok[0])])
assert(m1 != [list(FF).index(i[0]) for i in list(pok[1])])
assert(m2 != [list(FF).index(i[0]) for i in list(pok[2])])

m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])
pi = (m0, m1, m2)

res = verif_pok(v, F, pi)
assert res == True

with open("flag.txt", "r") as f:
    print(f.read())

题目基于一个矩阵zkp(运算皆在模5下)，在连接上靶机后，靶机会按顺序完成以下几个步骤：

• 随机生成64个0-255的整数当作seed

• 利用seed生成m个nxn的矩阵，并组成列表F

• 随机生成一个长为n的向量s

• 对F中每个矩阵Fi，进行如下计算：

  $$out_i = s^TF_is$$

  并将结果拼接在一起，得到长度为m的向量v

做完上面这些后就进入createpok过程，其输入为 $(v,s,F)$，具体操作是：

• 随机生成长度为n的向量t

• 对F中每个矩阵Fi，进行如下计算：

  $$out_i = t^TF_it$$

  并将结果拼接在一起，得到长度为m的向量com(这个操作和上面得到v的操作一样，也就是apply函数)

• 对F中每个矩阵Fi，进行如下计算：

  $$out_i = t^T(F_i + F_i^T)s$$

  并将结果拼接在一起，得到长度为m的向量verif

• 将com、v、verif一起做哈希并模5得到数字a

• 返回三元组 $pok = (com, t - as, verif)$

之后是verify的过程，其输入为 $(v,F,pok)$，具体操作是：

• 先解包pok得到com，resp和verify

• 由com，v和verify计算哈希得到a

• out1是apply(F,resp)得到的值

• out2为：

  $$com + a^2v - a\cdot verif$$

• out1与out2完全相等则能够通过verify

我们的任务是，给定seed、v和一个pok，要求产生另一个pok，其中每个向量均与给出的pok不相等，并且通过verify。

这很简单，由于只需要通过一次就有flag，而a只有0-4这几个值，所以随机到a=0的时候就压根不需要在意verify是什么了。

exp：

from Pwn4Sage.pwn import *
from hashlib import sha256
from Crypto.Util.number import *
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
    com = apply(F, t)
    verif = apply_verif_info(F, t, s)
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    return (com, t - a * s, verif)

def verif_pok(v, F, pi):
    com = pi[0]
    resp = pi[1]
    verif = pi[2]
    #a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    a = 0
    out1 = apply(F, resp)
    out2 = com + (a * a) * v - a * verif
    return out1 == out2


###################################################################### part1 get data
sh = remote("be.ax", 31105)
sh.recvuntil(b"m0 =")
m0 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m1 =")
m1 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m2 =")
m2 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"seed =")
init_seed = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"v =")
v = ast.literal_eval(sh.recvline().strip().decode())
v = Matrix(FF,v).T


###################################################################### part2 gen
gen_seed = bytes(init_seed)
F = []
for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
ver = random_matrix(FF, m, 1)


###################################################################### part3 get flag
sh.recvuntil(b"m0 =")
sh.sendline(str([i for i in com]).encode())
sh.recvuntil(b"m1 =")
sh.sendline(str([i for i in t]).encode())
sh.recvuntil(b"m2 =")
sh.sendline(str([i for i in ver]).encode())
print(sh.recvline())


#corctf{dont_forget_the_soundness_error}

anglerfish

题目描述：

The devil of the sea strikes back!

(Part 2 out of 2)

题目：

#!/usr/bin/sage

import sys
print("I caught an anglerfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)

def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    proofs = []
    for i in range(64):
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        com = apply(F, t)
        verif = apply_verif_info(F, t, s)
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        proofs.append((com, t - a * s, verif))
    return proofs

def verif_pok(v, F, pis):
    coms = []
    for pi in pis:
        com = pi[0]
        assert com not in coms
        coms.append(com)
        resp = pi[1]
        verif = pi[2]
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        out1 = apply(F, resp)
        out2 = com + (a * a) * v - a * verif
        assert out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
    gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)
verif_pok(v, F, pok)

for pi in pok:
    print("m0 =", [list(FF).index(i[0]) for i in list(pi[0])])
    print("m1 =", [list(FF).index(i[0]) for i in list(pi[1])])
    print("m2 =", [list(FF).index(i[0]) for i in list(pi[2])])

print("Can you catch an anglerfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])

pis = []
for x in range(64):
    m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
    m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
    m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

    for pi in pok:
        assert(m0 != [list(FF).index(i[0]) for i in list(pi[0])])
        assert(m1 != [list(FF).index(i[0]) for i in list(pi[1])])
        assert(m2 != [list(FF).index(i[0]) for i in list(pi[2])])

    m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
    m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
    m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])

    assert m0 not in [pi[0] for pi in pok]
    assert m1 not in [pi[1] for pi in pok]
    assert m2 not in [pi[2] for pi in pok]

    pi = (m0, m1, m2)
    pis.append(pi)

verif_pok(v, F, pis)

with open("flag.txt", "r") as f:
    print(f.read())

和上一题比起来，这题需要通过64次才行，所以纯碰0显然是不行了。

但是目的仍然只有一个，并不需要特别理解这个zkp里verify的细节，我们只需要让verify中out1=out2，仅此而已。

而verify的可操作性相当大，除了给定的v和F，整个pok都是我们可以自行输入的，只要不与给定的那个pok相等就行。那么不妨按如下步骤操作：

• 随机输入一个resp，得到out1
• 随机输入一个com，之后在0-4爆破a1，并由out1=out2这个式子计算出verify
• 计算出对应的verify之后，计算哈希值a2
• 如果a1=a2，就找到了符合要求的碰撞了

如果0-4都不符合条件，就重新随机取就行。

exp：

from Pwn4Sage.pwn import *
from hashlib import sha256
from Crypto.Util.number import *
from tqdm import *
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)


###################################################################### part1 get data
sh = remote("be.ax", 31106)

poks = []
for i in trange(64):
    sh.recvuntil(b"m0 =")
    m0 = ast.literal_eval(sh.recvline().strip().decode())
    sh.recvuntil(b"m1 =")
    m1 = ast.literal_eval(sh.recvline().strip().decode())
    sh.recvuntil(b"m2 =")
    m2 = ast.literal_eval(sh.recvline().strip().decode())
    poks.append([m0,m1,m2])

sh.recvuntil(b"seed =")
init_seed = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"v =")
v = ast.literal_eval(sh.recvline().strip().decode())
v = Matrix(FF,v).T


###################################################################### part2 gen F
gen_seed = bytes(init_seed)
F = []
for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))


###################################################################### part3 get flag
for i in trange(64):
    while(1):
        FIND = 0
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        out1 = apply(F, t)
        com = out1
        for a in range(5):
            if(a == 0):
                ver = random_matrix(FF, m, 1)
            else:
                ver = (com + (a * a) * v - out1) * inverse(a,5)
            aa = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(ver)])).digest()[0] % len(list(FF))]
            if(aa == a):
                FIND = 1
                break
        if(FIND == 1):
            break
    
    sh.recvuntil(b"m0 =")
    sh.sendline(str([i for i in com]).encode())
    sh.recvuntil(b"m1 =")
    sh.sendline(str([i for i in t]).encode())
    sh.recvuntil(b"m2 =")
    sh.sendline(str([i for i in ver]).encode())

print(sh.recvline())


#corctf{extra_equations_means_extra_information_isnt_zk}

roots

题目描述：

Check out this cool cryptosystem! Can you break it without the key?

题目：

from Crypto.Util.number import getPrime, bytes_to_long
from random import getrandbits
from decimal import Decimal, getcontext
from secret import FLAG

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = 2024

def chunk(inp: bytes, n: int) -> list[bytes]:
    return [inp[i:i + n] for i in range(0, len(inp), n)]

def generate() -> list[int]:
    return sorted(getPrime(PSIZE) for _ in range(N))

def otp(data: int) -> list[int]:
    key = [getrandbits(MSIZE) for _ in range(N - 1)]

    # Apply multiple times for extra security! ;)
    for k in key:
        data ^= k

    return key + [data]

def enc(data: int, key: list[int]) -> Decimal:
    return sum(a * Decimal(p).sqrt() for a, p in zip(otp(data), key))

def encrypt(plaintext: bytes, key: list[int]) -> Decimal:
    out = []
    for pt in chunk(plaintext, MSIZE // 8):
        out.append(enc(bytes_to_long(pt), key))

    return out

def main() -> None:
    key = generate()
    ct = encrypt(FLAG, key)

    print(ct)

if __name__ == "__main__":
    main()

output.txt：

[Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]

题目先生成3个128bit的素数p1、p2、p3，并按顺序排列好当作key。然后将flag按8字节拆成一个分组，记为mi，并计算：

$$c_i = (k_{i1},k_{i2},k_{i1} \oplus k_{i2} \oplus m_i) \left(\begin{matrix} \sqrt{p_1}\\ \sqrt{p_2}\\ \sqrt{p_3}\\ \end{matrix}\right)$$

明文共有四组，也就是有四个密文值，其中ki1、ki2是每次计算随机产生的64位nonce，并且计算精度为getcontext().prec = 2024，要求还原flag

首先，如果把四组明文拼接在一起，就成了一个矩阵乘法：

$$\left(\begin{matrix} k_{11} & k_{12} & k_{11} \oplus k_{12} \oplus m_1\\ k_{21} & k_{22} & k_{21} \oplus k_{22} \oplus m_2\\ k_{31} & k_{32} & k_{31} \oplus k_{32} \oplus m_3\\ k_{41} & k_{42} & k_{41} \oplus k_{42} \oplus m_4\\ \end{matrix}\right) \left(\begin{matrix} \sqrt{p_1}\\ \sqrt{p_2}\\ \sqrt{p_3}\\ \end{matrix}\right) = \left(\begin{matrix} c_1\\ c_2\\ c_3\\ c_4\\ \end{matrix}\right)$$

而如果同乘一个大系数T，就可以把含小数的计算转到整数下，也就是：

$$\left(\begin{matrix} k_{11} & k_{12} & k_{11} \oplus k_{12} \oplus m_1\\ k_{21} & k_{22} & k_{21} \oplus k_{22} \oplus m_2\\ k_{31} & k_{32} & k_{31} \oplus k_{32} \oplus m_3\\ k_{41} & k_{42} & k_{41} \oplus k_{42} \oplus m_4\\ \end{matrix}\right) \left(\begin{matrix} T\sqrt{p_1}\\ T\sqrt{p_2}\\ T\sqrt{p_3}\\ \end{matrix}\right) = \left(\begin{matrix} Tc_1\\ Tc_2\\ Tc_3\\ Tc_4\\ \end{matrix}\right)$$

而由于精度固定，所以进行运算时也会产生一定误差，因此整个式子实际上是：

$$\left(\begin{matrix} k_{11} & k_{12} & k_{11} \oplus k_{12} \oplus m_1\\ k_{21} & k_{22} & k_{21} \oplus k_{22} \oplus m_2\\ k_{31} & k_{32} & k_{31} \oplus k_{32} \oplus m_3\\ k_{41} & k_{42} & k_{41} \oplus k_{42} \oplus m_4\\ \end{matrix}\right) \left(\begin{matrix} T\sqrt{p_1}\\ T\sqrt{p_2}\\ T\sqrt{p_3}\\ \end{matrix}\right) + \left(\begin{matrix} \delta_1\\ \delta_2\\ \delta_3\\ \delta_4\\ \end{matrix}\right) = \left(\begin{matrix} Tc_1\\ Tc_2\\ Tc_3\\ Tc_4\\ \end{matrix}\right)$$

所以其实整个式子就抽象成了：

$$Ax + e = b$$

看上去像个LWE问题，但是问题在于我们只知道c而已。然而这个式子显然有个额外信息，就是除了e以外，A也是很小的，所有值都是64bit的数量级。因此可以用正交格的思路来考虑：

• 找到短向量u，使得u与b近似正交，也就是ub的结果小

• 由于u是短向量，因此ue结果也小

• 又因为x是大向量，所以要使得下面式子继续成立的话：

  $$uAx + ue = ub$$

  有理由相信此时下面的式子成立：

  $$uAx = 0$$

• 而由于A也比较小，所以在u的右核中规约就有机会找到A了

而这样操作下了，实际上找到的并不是A，而是A中向量的线性组合，但是简单爆破一下线性组合就可以找到原始的A，之后做异或就能得到flag。

exp：

from Crypto.Util.number import *
from decimal import Decimal, getcontext
from itertools import *

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = int(2024)

c = [Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]

L = block_matrix(ZZ,[
    [1,Matrix(ZZ,[int(i*int(10^2000)) for i in c]).T]
])
L = L.LLL()
res = L[0][:len(c)]
L = Matrix(Matrix(ZZ,res).right_kernel().basis())
A = L.LLL()

import string
vecs = [A[0],A[1],A[2]]
valid_vecs = []
for i in product([i for i in range(-5,5)],repeat=3):
    i1 = 0
    for j in range(3):
        i1 += i[j] * vecs[j]
    if(all(tt > 0 and tt < 2^64 for tt in i1) and i1 not in valid_vecs):
        valid_vecs.append(i1)

for i in combinations(valid_vecs,3):
    i1,i2,i3 = list(i)

    flag = b""
    for j in range(4):
        flag += long_to_bytes(abs(int(i1[j])^^int(i2[j])^^int(i3[j])))
    if(b"corctf{" in flag):
        print(flag)


#corctf{I'm_r00t1ng_f0R_U!!!!!!!}

other

此外还有两个题目，一个是区块链一个是量子，都没接触过，之后有机会再说吧，不过感觉大概率不太会去了解太多XD。

Deadsec CTF

这比赛被Zima拉着一起看了看，其中有一个题目还比较有趣，所以还是记录下。

Flag killer

题目描述：

Is it enough obfuscation?

题目：

#!/usr/bin/python3

from binascii import hexlify

flag = hexlify(b'DEAD{test}').decode()

index = 0
output = ''

def FLAG_KILLER(value):
    index = 0
    temp = []
    output = 0
    while value > 0:
        temp.append(2 - (value % 4) if value % 2 != 0 else 0)
        value = (value - temp[index])/2
        index += 1
    temp = temp[::-1]
    for index in range(len(temp)):
        output += temp[index] * 3 ** (len(temp) - index - 1)
    return output


while index < len(flag):
    output += '%05x' % int(FLAG_KILLER(int(flag[index:index+3],16)))
    index += 3

print(output)

enc.txt：

0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883

不用细看步骤，看最下面的while就知道实际上就是把flag的每三位16进制的值用某个5位十六进制表示，所以建个表然后查就好了。

exp：

from Crypto.Util.number import *
from tqdm import *

def FLAG_KILLER(value):
    index = 0
    temp = []
    output = 0
    while value > 0:
        temp.append(2 - (value % 4) if value % 2 != 0 else 0)
        value = (value - temp[index])/2
        index += 1
    temp = temp[::-1]
    for index in range(len(temp)):
        output += temp[index] * 3 ** (len(temp) - index - 1)
    return hex(int(output))[2:].zfill(5)

c = "0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883"

if(0):
    dic = {}
    for i in trange(2**24):
        dic[FLAG_KILLER(i)] = hex(i)[2:].zfill(3)

    flag = ""
    for i in trange(len(c)//5):
        flag += dic[c[i*5:i*5+5]]
    print(flag)

print(bytes.fromhex("444541447b323633663837316538383065396463376432343031303030333034666336306539386337633538387d"))


#DEAD{263f871e880e9dc7d2401000304fc60e98c7c588}

Raul Rosas

题目描述：

"I say weird stuff all the time."

题目：

from Crypto.Util.number import * 
from sympy import nextprime

p1 = bin(getPrime(1024))[2:]
p2 = p1[:605]
p2 = p2 + ('0'*(len(p1)-len(p2)))

p1 = int(p1,2)
p2 = nextprime(int(p2,2))

q1 = getPrime(300)
q2 = getPrime(300)

n1 = p1*p1*q1 
n2 = p2*p2*q2 

e = 65537 
flag = bytes_to_long(b'REDACTED')
c1 = pow(flag,e,n1)
c2 = pow(flag,e,n2)

print(f'{n1=}')
print(f'{n2=}')
print(f'{c1=}')
print(f'{c2=}')


"""
n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
"""

难得见到这么亲切的RSA题目，熟悉的味道。

题目先生成1024bit的素数p1。然后保留p1的高605位，并把低位全部抹掉之后，取nextprime得到p2，之后计算：

$$n_1 = p_1^2q_1$$ $$n_2 = p_2^2q_2$$

其中q1、q2是300bit的小素数。给出n1、n2，并给出分别用n1、n2加密flag得到的c1、c2，要求还原明文。

由于p2低位仅有一个nextprime的小量，也就是他可以写成：

$$p_2 = 2^{419}p_h + \delta$$

所以n2就是：

$$n_2 = (2^{419}p_h + \delta)^2q_2$$

展开一下：

$$n_2 = (2^{838}p_h^2 + 2^{419+1}p_h\delta + \delta^2)q_2$$

可以看出其实n2的低位其实是：

$$\delta^2q_2$$

所以爆破一下delta就可以得到q2了，之后就很容易。

exp：

from Crypto.Util.number import *
from gmpy2 import *

t = int("11100110111010000010101011000000011010100111100000010000101011001001011100001111111101100011100100011011111110000001110110010010111111001100111100011010101000010001100100000010000111010011010001101111011101101011111011111000000111100001001100001100111011110011011010001000110111110000101010110010111000111010010111",2)

n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
q2 = GCD(t,n2)

p2 = iroot(n2 // q2,2)[0]
print(p2)
phi2 = p2*(p2-1)*(q2-1)
print(long_to_bytes(pow(c2,inverse(65537,phi2),n2)))


#DEAD{Rual_R0s4s_Chiweweiner!!}

不过其实p2、q2是300bit，以及p1、q1高位相同，这些信息明显是指向copper的，比如AGCD。

SSP

题目描述：

Sometimes it requires GPU to compute huge amount of operation... like $O(2^100)$..? Nah, you'll use better algorithm, $O(2^50)$ seems fair huh?

题目：

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method

from random import randrange

for n in range(1, MAX_N + 1):

    print(f"Stage {n}")

    arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
    counts = randrange(0, n + 1)
    
    used = set()
    
    while True:

        idx = randrange(0, n)
        used.add(idx)

        if len(used) >= counts:
            break
    
    s = 0
    for idx in used:
        s += arr[idx]
    
    for a in arr:
        print(a, end=' ')
    print(s)

    answer = list(map(int, input().split()))

    user_sum = 0
    for i in answer:
        user_sum += arr[i]
    
    if user_sum != s:
        print("You are wrong!")
        exit(0)

    print(f"Stage {n} Clear")

print("Long time waiting... Here's your flag.")

with open('./flag', 'r') as f:
    print(f.read())

题目还专门说了背包没法彻底解决，然而就用背包做完全没遇到障碍TT，并且也没看出有什么特殊点。

exp：

from Pwn4Sage.pwn import *
from tqdm import *

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method

sh = remote("35.188.216.251",32222)

for n in trange(1, MAX_N + 1):
    sh.recvline()
    arr = list(map(int,(list(sh.recvline().strip().decode().split(" ")))))
    s = arr[-1]
    arr = arr[:-1]

    L = block_matrix(ZZ,[
        [1,Matrix(ZZ,arr).T],
        [Matrix.zero(1, len(arr)),-s]
    ])
    L[:,-1:] *= RAND_MAX
    res = L.LLL()[0][:-1]
    
    ans = ""
    for i in range(len(res)):
        if(abs(res[i]) == 1):
            ans += (str(i) + " ")
    sh.sendline(ans.encode())
    sh.recvuntil(b"Clear")
    sh.recvline()

print(sh.recvline())
print(sh.recvline())


#DEAD{T00_B1g_Number_Causes_Pr0blem...}

后来想了想他说的不能用的背包解法也许是指算法里的。。。

Password Guesser

题目描述：

Can you figure out my password, I lost it

题目：

from collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math

flag = b'<REDACTED>'
P = 13**37
password = b'<REDACTED>'
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)

print(f"counts = {[cnt for _, cnt in Counter(password2).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC)
print(f"c = {cipher.encrypt(pad(flag, 16))}")
print(f"iv = {cipher.iv}")


'''
counts = [5, 4, 7, 5, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 4, 4, 4, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]
c = b'q[\n\x05\xad\x99\x94\xfb\xc1W9\xcb`\x96\xb9|CA\xb8\xb5\xe0v\x93\xff\x85\xaa\xa7\x86\xeas#c'
iv = b'+\xd5}\xd8\xa7K\x88j\xb5\xf7\x8b\x95)n53'
'''

这个题目挺有意思，他先是从printable里面选取了一些字符记作password，这个password满足：

$$\prod{p_i} = \sum{p_i} \quad(mod\;13^{37})$$

将他排序好之后得到password2，给出password2里面每个元素的count，要求还原password2来解AES得到flag。

首先就是，printable里面有100个字符，然而count中只有89个，所以如果直接爆破的话，需要爆破$C_{100}^{89}$这么多种，虽然说用c++加多进程并不是做不到，但是显然有点太粗糙了。

而且可以发现，这个思路有一个很大的弊端，就是仅仅把上面给出的这个条件：

$$\prod{p_i} = \sum{p_i} \quad(mod\;13^{37})$$

当作检验爆破正确的结果在使用，然而这个条件本身肯定是解题的关键。

对于sum来说，由于所有字符都是printable里的，值都小于128，所以结合count的实际情况来看，这个sum最大也就几万，是远远小于13^37的，而prod则很轻松就能超过13^37。

那么不妨记这个sum值为c，那么其实就有：

$$c = \prod{p_i} + 13^{37}k$$

而仔细想想这个等式会发现，13^37其实带来了很大的特殊性，由于c最多只有几万，所以一定有：

$$c = \prod{p_i} + 13^{37}k < 13^5$$

那么对于prod，如果其中因子含13的字符超过了4个，那么就一定不符合上面的式子了，这是因为若有：

$$\prod{p_i} = 13^jt,\quad j>4$$

则：

$$\prod{p_i} + 13^{37}k = 13^jt + 13^{37}k = 13^jr, \quad j>4$$

所以说，password里面其实根本就没几个因子含13的字符，不然他们的prod在模13^37下一定会大于他们的sum，所以就大大减小了爆破范围，因此较短时间内就能找到解。

exp：

from collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math
import string
from tqdm import *
from itertools import *

P = 13**37
table = sorted([ord(i) for i in string.printable])
counts = [5, 4, 7, 5, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 4, 4, 4, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]

def mul(t1,t2):
    tt = 1
    assert len(t1) == len(t2)
    for i,j in zip(t1,t2):
        tt *= i**j
        tt = tt % P
    return tt % P

def dot(t1,t2):
    tt = 0
    assert len(t1) == len(t2)
    for i,j in zip(t1,t2):
        tt += i*j
    return tt % P

if(0):
    for kkk in range(1,10):
        if(kkk == 2):
            continue
        tt = [ord(i) for i in string.printable if ord(i) % 13 != 0]
        tt = [13*kkk] + tt
        tt = sorted(tt)
        idx_kkk = tt.index(13*kkk)

        for i in tqdm(combinations(range(len(tt)), len(tt) - len(counts)),total=math.comb(len(tt),len(counts))):
            temp = [0 for i in range(len(tt))]
            idxx = 0
            for j in range(len(tt)):
                if(j not in i):
                    temp[j] = counts[idxx]
                    idxx += 1

            if(temp[idx_kkk] > 4):
                continue
            if(dot(tt,temp) == mul(tt,temp)):
                print(temp)

temp = [5, 4, 7, 5, 0, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 0, 4, 4, 0, 4, 0, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]
tt = [ord(i) for i in string.printable if ord(i) % 13 != 0]
tt = [13*1] + tt
tt = sorted(tt)

password = b""
for i in range(len(temp)):
    password += (temp[i] * chr(tt[i])).encode()
print(password)
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)


c = b'q[\n\x05\xad\x99\x94\xfb\xc1W9\xcb`\x96\xb9|CA\xb8\xb5\xe0v\x93\xff\x85\xaa\xa7\x86\xeas#c'
iv = b'+\xd5}\xd8\xa7K\x88j\xb5\xf7\x8b\x95)n53'
print(f"counts = {[cnt for _, cnt in Counter(password2).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC, iv)
flag = cipher.decrypt(c)
print(flag)


#DEAD{y0u_Gu3ssEd_mY_p4s5w0rD}

*Password Guesser Revenge

这题现在还做不来，先放在这里，各位师傅也可以看看有没啥思路，我学会了就更新

题目：

from collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math

flag = b'<redacted>'
P = 13**37
password = b'<redacted>' # password charset is string.printable
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)
#print(password2)
print(f"counts = {[cnt for _, cnt in Counter(password).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC)
print(f"c = {cipher.encrypt(pad(flag, 16))}")
print(f"iv = {cipher.iv}")


'''
counts = [2, 4, 14, 7, 3, 2, 5, 3, 1, 3, 1, 4, 3, 3, 2, 10, 2, 6, 4, 1, 3, 4, 3, 2, 4, 3, 6, 1, 1, 4, 2, 21, 8, 8, 2, 4, 1, 9, 3, 4, 8, 3, 1, 2, 2, 5, 8, 2, 7, 2, 9, 2, 2, 6, 6, 3, 3, 9, 1, 3, 6, 6, 2, 4, 5, 3, 3, 8, 5, 1, 1, 9, 2, 8, 4, 1, 4, 9, 4, 1, 3, 4, 3, 4, 6, 4]
c = b'\xfb\x9e\xda\x81\xa6\xdf.\xc9zw\xb6t\x9e\x05\xb7\xdb\x84\xe5\x01\x97\xfb\xd2\x04 i\xa5\x13d\xfd\x89c\x0b'
iv = b'\xd4\xa6\xbc\xae\t/\xd3\x85YY\xb5\xda\xcf\xcaX\xb3'
'''

可以看出这一题中，给出的不再是password2的counter，而是password的，这就导致刚才的方法完全没法用了，因为还需要爆破一个置换，复杂度奇高无比。

我大致的思路是，由于sum也还是几万那个数量级，是爆破允许的复杂度范围内的，因此先假设他已知，就记为c。那么就只用sum的话，其实整个式子可以看作一个背包，虽然并不知道counter中每个量具体是谁的，但是可以用noisecrt的类似思路来做。

这个思路弊端也很明显：

• noisecrt造的格太大了，并且c也要爆破，复杂度不允许
• printable的字符值都是连续量，规约肯定有多解的
• 根本没利用上prod

如果要利用prod，可以找到一个生成元g，然后用dlp转到指数上去做背包，此时可以避免printable的字符值都是连续量这个问题，然而也有几个缺陷：

• 仍然要利用noisecrt，c仍然要爆破
• 模13^37根本找不到生成元

所以不会了。