HGAME 2026 Crypto方向Write UP
|
116
|
0
|
Write UP

3987 字
|
51 分钟

前言

寒假无聊打了一会，把Crypto给AK了，似乎今年的没去年的难，是错觉吗_(:з)∠)_

Week 1

Classic

给了个flag.txt，内容如下：

Ane Hmnknèdi joptiy cae rvz izzlttqh ie Vukltèrq; ma cae jpxsf tyupawlj iz 1553 ff zhq Maglueu Miazht Bmxaosfe Iklxezu, yqx pz wmw ugmqh hltqv Cogqrèyk dgi au huw 1586 pspdsckmqray, lqecons Flrlmwv crarnry ovljifik lod xoxeq glttgvpks.
Ux byep e rky fs jecxi anraynn 26 Cmizgr mpwnaniay luol g dqgr uf oeyjs, qeytizk pz tti aotxi vl "tti btbdihqanpl iibllx."
Iz xok 19tt glttgvf, Hanfhme qbwusqh pzs biyoopmj cemoukse, hlrihiyons e mgtmp iroi xogt qrkkd uxz zwa-glttgvf-rozk tett.
euewmc,P nobi fuu isbrd xmrk cxezyioes irktaugdewny。Flpy ie cvar rphm:VUHHX{Tti Julxmzooz sm zhq Rlc azh ane Apk}

直觉告诉我这大概率是维吉尼亚，直接用Vigenere Solver | guballa.de求解就行：

但是题目还给出了另外一个文件task.py：

from Crypto.Util.number import *  
from secret import flag  
p = getPrime(512)  
q = getPrime(512)  
n = p * q  
e = 65537  
leak = p >> 230  
m = bytes_to_long(flag)  
c = pow(m,e,n)  
print("n=",n)  
print("leak=",leak)  
print("c=",c)  
'''  
n= ...  
leak= ...  
c= ...  
'''

直接打Coppersmith就可以分解\(n\)：

from Crypto.Util.number import *

n = ...
leak = ...
c = ...
e = 65537

ph = leak << 230

R.<x> = Zmod(n)[]
f = ph + x
sol = f.small_roots(X=2^230, beta=0.4, epsilon=0.02)

p = ZZ(sol[0]) + ph
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

解密出来是Vigenere,key=hgame，应该是拿flag的提示，实际上这一步可以忽略。

ezCurve

from Crypto.Util.number import *  
import socketserver  
import logging  
import io  
import os  
from sage.all import *  

with open('flag.txt', 'rb') as f:  
    flag = f.read()  

HOST = '0.0.0.0'  
PORT = 10000  

menu = """1. get x  
2. check x  
> """  

class Curve(socketserver.StreamRequestHandler):  
    def handle(self):  
        global istream, ostream  

        logging.info(f"connection from {self.client_address}")  
        istream = io.TextIOWrapper(self.rfile, encoding="UTF-8")  
        ostream = io.TextIOWrapper(self.wfile, encoding="UTF-8", write_through=True)  

        p = getPrime(1024)  
        a = getPrime(200)  
        b = getPrime(200)  
        E = EllipticCurve(GF(p), [a, b])  
        R = E.random_element()  
        P = E.random_element()  

        print(p, file = ostream)  
        print(a, file = ostream)  
        print(b, file = ostream)  
        print(R, file = ostream)  

        for i in range(30):  
            print(menu, file = ostream)  
            choice = int(istream.readline().strip())  
            if choice == 1:  
                print("t> t = ", end = "", file = ostream)  
                t = int(istream.readline().strip())  
                O = P + t * R  
                print(int(O[0] - getPrime(163)), file = ostream)  
            elif choice == 2:  
                ans = int(istream.readline().strip())  
                if ans == P[0]:  
                    print(flag, file = ostream)  
                else:  
                    print("error", file = ostream)  


if __name__ == "__main__":  
    logging.basicConfig(level=logging.INFO)  
    with socketserver.TCPServer((HOST, PORT), Curve) as server:  
        logging.info(f"listening on {HOST}:{PORT}")  
        server.serve_forever()

标准的ECHNP，参考椭圆曲线隐藏数问题（Elliptic Curve Hidden Number Problem） – 三极管域 | Triode Field

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from sage.all import *

io = remote("cloud-middle.hgame.vidar.club", 31638)

p = int(io.recvline().decode())
a = int(io.recvline().decode())
b = int(io.recvline().decode())
x, y = map(int, io.recvline()[1:].decode().split(":")[:2])

E = EllipticCurve(GF(p), [a, b])
R = E(x, y)

io.sendlineafter(b'> \n', b'1')
io.sendlineafter(b't> t = ', b'0')
h0 = int(io.recvline().decode())

A = []
A0 = []
B = []
B0 = []
C = []

n = 14
K = 2**163

for i in trange(n):
    t = i + 1
    xQ = ZZ((t*R)[0])

    io.sendlineafter(b'> \n', b'1')
    io.sendlineafter(b't> t = ', str(t).encode())
    h1 = int(io.recvline().decode())

    io.sendlineafter(b'> \n', b'1')
    io.sendlineafter(b't> t = ', str(-t).encode())
    h2 = int(io.recvline().decode())

    H = (h1 + h2) % p

    Ai = (H - 2*xQ)
    A0i = 2*(h0 - xQ)
    Bi = 2*(H*(h0 - xQ) - 2*h0*xQ - a - xQ**2)
    B0i = (h0 - xQ)**2
    Ci = (H*(h0 - xQ)**2 - 2*h0**2*xQ - 2*(a + xQ**2)*h0 - 2*a*xQ - 4*b)

    A.append(Ai)
    A0.append(A0i)
    B.append(Bi)
    B0.append(B0i)
    C.append(Ci)

Delta1 = matrix(ZZ, n+2, n+2)
Delta1[0, 0] = K**3
for i in range(1, n+2):
    Delta1[i, i] = K**2

Delta2 = matrix(ZZ, n+1, n+1)
for i in range(n+1):
    Delta2[i, i] = K

M1 = matrix(ZZ, n+2, n)
for i in range(n):
    M1[0, i] = -C[i]
    M1[1, i] = -B[i]
    M1[i+2, i] = -B0[i]

M2 = matrix(ZZ, n+1, n)
for i in range(n):
    M2[0, i] = -A[i]
    M2[i+1, i] = -A0[i]

L = block_matrix([[Delta1, 0, M1], [0, Delta2, M2], [0, 0, p]])

res = L.LLL()[0]

x0 = h0 + res[1] // (K**2)

io.sendlineafter(b'> \n', b'2')
io.sendline(str(x0).encode())

io.interactive()

Flux

from Crypto.Util.number import *  
import random  
from secret import key  

class Flux:  
    def __init__(self, n, x):  
        self.n = n  
        self.a = random.randint(1, n-1)  
        self.b = random.randint(1, n-1)  
        self.c = random.randint(1, n-1)  
        self.x = x  

    def next(self):  
        self.x = (self.a * self.x ** 2 + self.b * self.x + self.c) % self.n  
        return self.x  

def shash(value: str,key: int) -> int:  
    length = len(value)  

    if length == 0:  
        return 0  
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff  
    x = (ord(value[0]) << 7) & mask  
    for c in value:  
        x = (key * x) & mask ^ ord(c)  

    x ^= length & mask  

    return x  

assert key.bit_length() < 70  
value = "Welcome to HGAME 2026!"  
h = shash(value, key)  

n = getPrime(260)  
flux = Flux(n, h)  
data = [flux.next() for _ in range(4)]  

with open('data.txt', 'w') as f:  
    f.write(f"{data}\n")  
    f.write(f"{n}\n")  

magic_word = "I get the key now!"  
flag = "VIDAR{" + hex(shash(magic_word, key))[2:] + "}"  
print(flag)

一个QCG和一个带key的哈希函数，很显然我们需要先通过倒推QCG的状态来得到"Welcome to HGAME 2026!"这句话通过shash哈希后的值，再尝试通过这个哈希值来推出key，再用这个key对"I get the key now!"这句话进行哈希得到flag

首先我们知道QCG的四个输出值\(x_1,x_2,x_3,x_4\)以及模数\(n\)，则有：

$$
\begin{cases}
x_2\equiv ax_1^2+bx_1+c\pmod{n}\\
x_3\equiv ax_2^2+bx_2+c\pmod{n}\\
x_4\equiv ax_3^2+bx_3+c\pmod{n}
\end{cases}
$$

求解上述三元一次方程组就可以恢复QCG的参数\(a,b,c\)，从而求解\(x_1\equiv ax^2+bx+c\pmod{n}\)这个方程得到"Welcome to HGAME 2026!"这句话通过shash哈希后的值，对于这个哈希，由于其不涉及很复杂的操作，涉及到key的部分也不多，那么尝试使用z3进行求解来恢复key，最后用这个key对"I get the key now!"这句话进行哈希就可以得到flag：

from Crypto.Util.number import *
from z3 import *

def shash(value: str,key: int) -> int:
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^^ ord(c)

    x ^^= length & mask

    return x

s = [...]
n = ...

A = matrix(Zmod(n), [[s[0]^2, s[0], 1], [s[1]^2, s[1], 1], [s[2]^2, s[2], 1]])
v = vector(Zmod(n), [s[1], s[2], s[3]])

a, b, c = map(int, A.solve_right(v))
R.<x> = Zmod(n)[]

f = a*x^2 + b*x + c - s[0]
rts = f.roots()

mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
m = mask + 1

value = "Welcome to HGAME 2026!"

for r, _ in rts:
    k = BitVec('k', 256)
    h = shash(value, k)

    s = Solver()
    s.add(h == int(r))
    s.add(k < 2**70)
    s.add(k > 0)

    if s.check() == sat:
        key = s.model()[k].as_long()
        magic_word = "I get the key now!"
        flag = "VIDAR{" + hex(shash(magic_word, key))[2:] + "}"
        print(flag)

babyRSA

from Crypto.Util.number import *  
from gmpy2 import *  
from random import *  
import string  
k = randint(30, 40)  
str = string.digits + string.ascii_letters + "_@"  
flag = b"VIDAR{" + "".join([choice(str) for i in range(k)]).encode() + b"}"  
p = getPrime(120)  
q = getPrime(120)  
n = p * q  
e = 65537  
m = bytes_to_long(flag)  
c = pow(m, e, n)  
print(f'c = {c}')  
print(f'p = {p}')  
print(f'q = {q}')  

'''  
c = 451420045234442273941376910979916645887835448913611695130061067762180161  
p = 722243413239346736518453990676052563  
q = 777452004761824304315754169245494387  
'''

一个\(n<m\)的RSA，直接解密只能得到模\(n\)下的flag，而我们知道flag的格式以及组成flag的字符范围（最小的ASCII码为48，最大的ASCII码为122），设flag除去VIDAR{}之外的长度为\(k\)，以及去掉头尾之后的flag为\(m_0\)，则有：

$$
m_0\equiv c_0+256c_1+256^2c_2+\cdots+256^{k-1}c_{k-1}\pmod{n}
$$

尝试通过构造如下格：

$$
B=\left(\begin{matrix}
1&&&&&&1\\
&1&&&&&256\\
&&1&&&&256^2\\
&&&\ddots&&&\vdots\\
&&&&1&&256^{k-1}\\
&&&&&1&-m_0\\
&&&&&&n
\end{matrix}\right)
$$

预期有：

$$
(c_0,c_1,c_2,\cdots,c_{k-1},1,k)B=(c_0,c_1,c_2,\cdots,c_{k-1},1,0)
$$

其中\(48\le c_i\le 122, 0\le i\le k-1\)，这样的话目标向量会偏大，我们可以考虑减小目标向量中分量的范围，取字符范围的ASCII码平均值（记为\(a\)），有：

$$
m_0’\equiv m_0-(1+256+256^2+\cdots+256^{k-1})a\equiv c_0’+256c_1’+256^2c_2’+\cdots+256^{k-1}c_{k-1}’\pmod{n}
$$

其中\(c_i’=c_i-a,0\le i\le k-1\)，此时可以构造如下新格基：

$$
B’=\left(\begin{matrix}
1&&&&&&1\\
&1&&&&&256\\
&&1&&&&256^2\\
&&&\ddots&&&\vdots\\
&&&&1&&256^{k-1}\\
&&&&&1&-m_0’\\
&&&&&&n
\end{matrix}\right)
$$

预期有：

$$
(c_0′,c_1′,c_2′,\cdots,c_{k-1}’,1,k)B’=(c_0′,c_1′,c_2′,\cdots,c_{k-1}’,1,0)
$$

其中\(48-a\le c_i’\le 122-a, 0\le i\le k-1\)，此时目标向量的分量的绝对值会有所减小，可以更容易规约出目标向量，但是在本题中，上述格规约得到的向量实际是\((c_0’+\varepsilon,c_1′,c_2′,\cdots,c_{k-1}’,1,\varepsilon)\)（其中\(\varepsilon\)是个小量，这条向量实际上比\((c_0′,c_1′,c_2′,\cdots,c_{k-1}’,1,0)\)更短），只取前\(k\)个分量计算得到的实际上是：

$$
(c_0’+\varepsilon+a)+256(c_1’+a)+256^2(c_2’+a)+\cdots+256^{k-1}(c_{k-1}’+a)\equiv m_0+\varepsilon\pmod{n}
$$

所以在计算出结果之后将\(\varepsilon\)减掉就行：

from Crypto.Util.number import *
import string

str = string.digits + string.ascii_letters + "_@"
s = [ord(c) for c in str]

c = 451420045234442273941376910979916645887835448913611695130061067762180161
p = 722243413239346736518453990676052563
q = 777452004761824304315754169245494387
e = 65537

head = b"VIDAR{"
tail = b"}"

n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m0 = pow(c, d, n)

h = bytes_to_long(head)
t = bytes_to_long(tail)
mid = sum(s) // len(s)

for k in range(30, 40):
    m = (m0 - t) * inverse(256, n) % n
    m = (m - h * pow(256, k, n)) % n
    L = matrix(ZZ, k+2, k+2)

    for i in range(k):
        m = (m - mid*pow(256, i, n)) % n
        L[i, i] = 1
        L[i, -1] = pow(256, i, n)
    L[-2, -2] = 1
    L[-2, -1] = -m
    L[-1, -1] = n

    res = L.BKZ()
    for v in res:
        if v[-2] == 1:
            if all(c+mid in s for c in v[:-2]):
                flag = ""
                for c in v[:-2][::-1]:
                    flag += chr(c+mid)
                m = bytes_to_long(flag.encode()) - v[-1]
                flag = head + long_to_bytes(m) + tail
                print(flag.decode())

Week 2

ezRSA

import socketserver
import logging
import random
import os
import io
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
import base64

flag = pad(os.environ.get("FLAG", "flag{fake_flag}").encode(), 127)

HOST = '0.0.0.0'
PORT = 10000

menu="""1. Encrypt message
2. Decrypt message
3. Get flag
Your choice > """

class ezRSA(socketserver.StreamRequestHandler):
    def handle(self):
        global istream, ostream

        logging.info(f"connection from {self.client_address}")
        istream = io.TextIOWrapper(self.rfile, encoding="UTF-8")
        ostream = io.TextIOWrapper(self.wfile, encoding="UTF-8", write_through=True)

        p = getPrime(512)
        q = getPrime(512)
        phi = (p - 1) * (q - 1)
        e = random.getrandbits(50)
        while GCD(e, phi) != 1:
            e = random.getrandbits(50)

        d = pow(e, -1, phi)

        n = p * q

        safe = True

        while True:
            print(menu, end='', file=ostream)
            try:
                choice = int(istream.readline().strip())
                if choice == 1:
                    print('plz give me your plaintext:', file=ostream)
                    plain = int(istream.readline().strip())

                    print('and the bit you want to flip:', file=ostream)
                    x = int(istream.readline().strip())

                    cipher = pow(plain, e ^ (1 << x), n)
                    cipher = long_to_bytes(cipher)

                    if not safe:
                        cipher = self.disguise(cipher)
                    print(base64.b64encode(cipher).decode(), file=ostream)
                elif choice == 2:
                    print('plz give me your ciphertext:', file=ostream)
                    cipher = int(istream.readline().strip())

                    plain = pow(cipher, d, n)
                    plain = long_to_bytes(plain)

                    if not safe:
                        plain = self.disguise(plain)
                    print(base64.b64encode(plain).decode(), file=ostream)
                elif choice == 3:
                    secret = pow(bytes_to_long(flag), e, n)

                    safe = False

                    print(base64.b64encode(long_to_bytes(secret)).decode(), file=ostream)                    

            except ValueError as e:
                print("Invalid format.", file=ostream)
                continue

    def disguise(self, msg):
        res = bytearray(msg)
        mask = os.urandom(1)
        for i in range(len(res)):
            res[i] = res[i] ^ int.from_bytes(mask)
        for i in range(len(msg) - 1, -1, -1):
            res[i] = res[i] ^ int.from_bytes(mask)
            mask = os.urandom(1)
        return bytes(res)


if __name__ == "__main__":
    logging.basicConfig(level=logging.INFO)
    with socketserver.TCPServer((HOST, PORT), ezRSA) as server:
        logging.info(f"listening on {HOST}:{PORT}")
        server.serve_forever()

程序有五个功能，分别是：

  1. 用翻转指定一位的公钥加密用户输入的明文
  2. 用私钥\(d\)解密用户输入的密文
  3. 泄露用\(e\)加密的flag
  4. 用翻转指定一位的公钥加密用户输入的明文后用disguise进行一次性加密
  5. 用私钥\(d\)解密用户输入的密文后用disguise进行一次性加密

其中功能1在触发功能3后会被功能4取代，功能2在触发功能3后会被功能5取代，并且在一开始我们是不知道\(n\)和\(e\)的，我们需要先尝试获得\(n\)和\(e\).

注意到功能2可以用私钥解密用户输入的密文，而且输入的密文并没有限制范围，我们知道，对于\(n=pq\)（其中\(p,q\)均为较大的质数），有\(\varphi(n)=(p-1)(q-1)\)为偶数，又因为\(d\equiv e^{-1}\pmod{\varphi(n)}\)，所以\(d\)必然是奇数，那么若我们输入\(-1\)作为待解密的密文，则会得到：

$$
(-1)^d\mod{n}=-1\mod{n}= n-1
$$

将输出的结果加上\(1\)我们就可以得到模数\(n\)了.

又注意到功能1中用于加密的公钥是e ^ (1 << x)，也就是\(e\oplus 2^{x}\)，记\(e\)的最低位为第0位，则有：

$$
e\oplus2^{x}=\begin{cases}
e+2^{x}&,\text{$e$的第$x$位为0}\\
e-2^{x}&,\text{$e$的第$x$位为1}
\end{cases}
$$

又因为\(e\)只有50位，那么取\(x\ge 50\)的时候必然有\(e\oplus 2^x=e+2^x\)，此时若我们输入\(a\)进行加密，得到的就是\(c_x\equiv a^{e+2^{x}}\equiv a^ea^{2^x}\pmod{n}\)，而\(a^{2^x}\mod{n}\)我们是可以知道的，又因为我们每次可以对\(e\)的一位进行翻转，那么我们可以从\(0\)到\(49\)遍历\(e\)的每一位来对\(a\)进行加密，对其中第\(i\)位，我们设加密后的密文为\(c_i\equiv 2^{e\oplus 2^{i}}\pmod{n}\)，则存在如下两种情况：

  • 若\(a^{2^{x}}c_i\equiv a^{2^{i}}c_x\pmod{n}\)，则\(e\)的第\(i\)位为\(0\)；
  • 若\(a^{2^{x}}c_i\not\equiv a^{2^{i}}c_x\pmod{n}\)，则\(e\)的第\(i\)位为\(1\)

遍历\(0\le i<50\)我们就可以恢复完整的\(e\)

在获得\(n\)和\(e\)之后，我们就需要思考怎么获得flag了，很显然，我们只能通过功能3来获得加密后的flag，但是因为每次的\(n\)都是随机的，所以直接分解\(n\)来解密几乎不可能，而在使用功能3之后，解密功能（功能2）会变成功能5，那么直接解密获得flag显然也是不可能的了，但是分析用于一次性加密的disguise的函数可以发现，输入的字符串里面最后一个字节其实是没有被加密的，那么如果我们将先前得到的加密的flag（记为\(c\)）扔进去，得到的明文的最后一字节就是flag的最后一字节，既然如此，我们可以考虑逐字节把flag泄露出来，我们记flag的最后一字节为\(m_0\)，剩余部分为\(m’_0\)，则有：

$$
c\equiv(256m_0’+m_0)^e\equiv\sum_{i=0}^{e}C_e^i 256^{i}(m_0′)^im_0\pmod{n}
$$

对上式左右两边乘上\(256^{-e}\mod{n}\)可以得到：

$$
256^{-e}c\equiv \sum_{i=0}^{e}C_e^i 256^{i-e}(m_0′)^im_0^{i-e}\equiv(256^{-1}m_0+m_{0}’)^e\pmod{n}
$$

那么我们向功能5中输入\(256^{-e}c\mod{n}\)，可以得到\(256^{-1}m_0+m_0’\mod{n}\)被一次性加密的结果，实际上，该一次性加密可以视为在明文的基础上加上\(256\delta\)（其中\(\delta\)为整数），那么我们得到的其实是：\(256^{-1}m_0+m_0’+256\delta\mod{n}\)，那么只需要在得到的结果的基础上减去\(256^{-1}m_0\mod{n}\)并对\(256\)取模就可以得到明文剩余部分\(m_0’\)的最后一字节\(m_1\)，此时未知的明文记为\(m_1’\)，有：

$$
c\equiv[256^2m_1’+(m_0+256m_1)]^e\pmod{n}
$$

两边乘上\(256^{-2e}\mod{n}\)就可以得到：

$$
256^{-2e}c\equiv[256^{-2}(m_0+256m_1)+m_1′]^e\pmod{n}
$$

输入\(256^{-2e}\mod{n}\)就可以得到\(256^{-2}(m_0+256m_1)+m_1’\mod{n}\)被一次性加密的结果，在此基础上减去\(256^{-2}(m_0+256m_1)\mod{n}\)再对\(256\)取模就可以得到明文剩余部分\(m_1’\)的最后一字节\(m_2\)了，以此类推，设已知的flag部分为\(M_i\)（\(i=0,1,2,\cdots\)，其中\(M_0=0\)）可以得到逐字节泄露flag的流程：

  1. 向功能5中输入\(256^{-ie}c\mod{n}\)，得到\(256^{-i}M_i+m_i’\mod{n}\)被一次性加密的结果\(x_i\)
  2. 计算\(m_i=(x_i-256^{-i}M_i\mod{n})\mod{256}\)
  3. 计算\(M_{i+1}=M_{i}+256^{i}m_i\)
  4. 令\(i=i+1\)，重复上述步骤直到flag被完全泄露

综上可以写出如下脚本来获得flag：

from Crypto.Util.number import *  
from base64 import b64decode  
from tqdm import *  
from pwn import *  

def b64_to_long(s):  
    return bytes_to_long(b64decode(s))  

p = remote("ip", port)  

p.sendlineafter(b'Your choice > ', b"2")  
p.sendlineafter(b'plz give me your ciphertext:\n', b"-1")  
n = b64_to_long(p.recvline().strip()) + 1  

p.sendlineafter(b'Your choice > ', b"1")  
p.sendlineafter(b'plz give me your plaintext:\n', b"2")  
p.sendlineafter(b'and the bit you want to flip:\n', b"50")  

tmp = b64_to_long(p.recvline().strip())  

e = 0  

for i in trange(50):  
    p.sendlineafter(b'Your choice > ', b"1")  
    p.sendlineafter(b'plz give me your plaintext:\n', b"2")  
    p.sendlineafter(b'and the bit you want to flip:\n', str(i).encode())  

    a = b64_to_long(p.recvline().strip()) * pow(2, 1 << 50, n) % n  
    if a != tmp * pow(2, 1 << i, n) % n:  
        e += 1 << i  

p.sendlineafter(b'Your choice > ', b"2")  
p.sendlineafter(b'plz give me your ciphertext:\n', str(pow(2, e, n)).encode())  

assert b64_to_long(p.recvline().strip()) == 2  

p.sendlineafter(b'Your choice > ', b"3")  
c = b64_to_long(p.recvline().strip())  

flag = b''  

for i in range(127):  
    c0 = c * pow(256, -i*e, n) % n  

    p.sendlineafter(b'Your choice > ', b"2")  
    p.sendlineafter(b'plz give me your ciphertext:\n', str(c0).encode())  

    m0 = (b64_to_long(p.recvline().strip()) - bytes_to_long(flag) * pow(256, -i, n) % n) % 256  

    flag = long_to_bytes(m0) + flag  

    log.success(flag.decode())

ezDLP

from Crypto.Util.number import long_to_bytes, getPrime  
from Crypto.Cipher import AES  
from Crypto.Util.Padding import pad, unpad  
from base64 import b64encode  
import hashlib  
from sage.all import *  
from secret import getRandomMatrix  

with open('flag.txt', 'rb') as f:  
    flag = pad(f.read(), AES.block_size)  

# Want to factor n? I've already done it! Get it yourself.  
n = 144709507748526661267852152217031923282704243254105275252262414154410511284347828603240755427862752297392095652561239549522158121842455510674435510821274029842500154931546666242034086499872050823824437303603895977092291834159890433746969317535636398062008995784281741721729948231010601796589449187553147904043991226174291329  
a = Matrix(Zmod(n), getRandomMatrix())  

k = getPrime(1000)  
b = a ** k  

data = [n, a, b]  
save(data, "data.sobj")  

key = hashlib.md5(long_to_bytes(k)).digest()  

cipher = AES.new(key, AES.MODE_ECB)  
ciphertext = cipher.encrypt(flag)  

print(b64encode(ciphertext).decode())  
# ieJNk5335o9lCy6Ar2XymrDy+HVHcQhikluNSra0kBafw1WDCyyuNPkLACeBsavy

矩阵离散对数问题，但是实际操作发现矩阵\(a\)只能被对角化，所以我们没办法用在若尔当标准型与矩阵离散对数问题 – 三极管域 | Triode Field中提到的方法来做这道题，题目中提示我们需要分解\(n\)，而且也说了他已经帮我们分解好了，所以考虑去factordb查表，可以看到：

设两质因数分别为\(p,q\)，可以考虑分别在模\(p\)和模\(q\)下求解离散对数再求CRT，因为\(a\)可以被对角化，所以必然有\(a^{\varphi(n)}=I\)，那么在模\(p,q\)下分别有\(a^{p-1}=I,a^{q-1}=I\)，而且又因为\(|a|^k=|a^k|\)，所以我们可以通过取行列式将矩阵离散对数问题转换为\(\mathbb{Z}_{n}\)下的离散对数问题，尝试分解\(p-1\)可以看到：

又尝试分解\(q-1\)可以看到：

发现\(p-1,q-1\)都是光滑的，那么可以考虑直接通过sage的discrete_log来分别求解模\(p,q\)下离散对数，再计算CRT即可得到key：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from base64 import *
import hashlib

n, a, b = load("data.sobj")

ct = "ieJNk5335o9lCy6Ar2XymrDy+HVHcQhikluNSra0kBafw1WDCyyuNPkLACeBsavy"
p = 282964522500710252996522860321128988886949295243765606602614844463493284542147924563568163094392590450939540920228998768405900675902689378522299357223754617695943
q = 511405127645157121220046316928395473344738559750412727565053675377154964183416414295066240070803421575018695355362581643466329860038567115911393279779768674224503

A = matrix(Zmod(n), a)
B = matrix(Zmod(n), b)

detA = A.det()
detB = B.det()

dl1 = discrete_log(GF(p)(detB), GF(p)(detA), p-1)
dl2 = discrete_log(GF(q)(detB), GF(q)(detA), q-1)

k = crt([ZZ(dl1), ZZ(dl2)], [(p-1)//2, q-1])

key = hashlib.md5(long_to_bytes(k)).digest()

cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(b64decode(ct))

print(flag)

eezzDLP

from Crypto.Util.number import long_to_bytes, getPrime  
from Crypto.Cipher import AES  
from Crypto.Util.Padding import pad, unpad  
from base64 import b64encode  
import hashlib  
from sage.all import *  
from secret import getRandomMatrix, get_random_prime  

with open('flag.txt', 'rb') as f:  
    flag = pad(f.read(), AES.block_size)  

p = get_random_prime()  
q = get_random_prime()  
n = p * p  

a = Matrix(Zmod(n), getRandomMatrix())  

k = getPrime(660)  
b = a ** k  

data = [n, a, b]  
save(data, "data.sobj")  

key = hashlib.md5(long_to_bytes(k)).digest()  

cipher = AES.new(key, AES.MODE_ECB)  
ciphertext = cipher.encrypt(flag)  

print(b64encode(ciphertext).decode())  
# Q3UBa1pz1fi35L94peaFbPvpQe4UyXOUif3CKS/CmZdXOiV7bA5NNNjJ1KeUiAFE

还是矩阵离散对数，矩阵\(a\)依旧是可对角化的，但是这里的\(n=p^2\)，而且\(p-1\)不再是光滑的，所以上一题那种做法就行不通了，但是注意到在\(\mathbb{Z}_{p^2}\)中，该矩阵的阶为\(\varphi(p^2)=p(p-1)\)，可以尝试先使用\(p\)-进数的方法来求\(k\mod{p}\)，再通过bsgs来求解剩余部分。

我们分别分别通过求解\(p\)-进整数域下的矩阵特征方程来得到\(a,b\)矩阵中对应的特征值\(e_a,e_b\)，则由特征值的性质我们可以知道有\(e_a^k\equiv e_b\pmod{p^2}\)，由费马小定理，对于与\(p\)互质的整数\(x\)，有：\(x^{p-1}\equiv1\pmod{p}\)，也就是\(x^{p-1}=1+tp\)（其中\(t\)为整数），也就是在模\(p^2\)下，有：\(x^{p-1}\equiv1+tp\pmod{p^2}\)（此时必然有\(0<t<p\)），那么对于\(x^{s(p-1)}\)，有：

$$
x^{s(p-1)}\equiv (x^{p-1})^s\equiv (1+tp)^{s}\equiv 1+stp+\sum_{i=2}^{s}C_s^i t^ip^i\equiv 1+stp\pmod{p^2}
$$

很显然，在模\(p^2\)下，有：

$$
\frac{(x^{s(p-1)}-1)\mod{p^2}}{p}\equiv s\cdot\frac{(x^{p-1}-1)\mod{p^2}}{p}\pmod{p}
$$

那么我们定义函数\(f(x)\equiv[(x^{p-1}-1)\mod{p^2}]/p\pmod{p}\)，则有：

$$
f(e_b)\equiv f(e_a^k)\equiv kf(e_a)\pmod{p}
$$

此时计算\(f(e_b)f(e_a)^{-1}\mod{p}\)即可得到\(k_0= k\mod{p}\)，那么\(k\)可以表示为\(k=rp+k_0\)，则有：

$$
e^{k}a\equiv e_{a}^{rp+k_0}\equiv (e_a^{p})^re_{a}^{k_0}\equiv e_b\pmod{p^2}
$$

即\((e_a^p)^r\equiv e_be_a^{-k_0}\pmod{p^2}\)，又因为\(2^{659}\le k<2^{660}\)，所以我们可以知道\(r\)的范围为\(\frac{2^{659}}{p}\le r<\frac{2^{660}}{p}\)，因为\(p\)是个612位的质数，所以我们可以以\(e_a^p\)为底数，\(e_be_a^{-k_0}\)为真数，在\((2^{659}/p,2^{660}/p)\)这个范围内进行bsgs求出\(r\)，最后计算出\(k=k_0+rp\)：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import *
from base64 import *
import hashlib

n, a, b = load("data.sobj")

ct = "Q3UBa1pz1fi35L94peaFbPvpQe4UyXOUif3CKS/CmZdXOiV7bA5NNNjJ1KeUiAFE"
p = 14262553722350428046713771076551090314160260448968748240889092522867981035381835010729957810183043946868290618279293005580111881543857313243691824746036623976338940751627470874113302539

Ap = matrix(Zp(p, 2), a)
Bp = matrix(Zp(p, 2), b)

cpA = Ap.charpoly()
cpB = Bp.charpoly()

def f(x):
    return ZZ(pow(x, p-1, n) - 1) // p

eA = cpA.roots()[0][0].lift()
eB = cpB.roots()[1][0].lift()

k0 = f(eB) * inverse(f(eA), p) % p

base = pow(eA, p, n)
y = eB * pow(eA, -k0, n) % n

l = (1 << 659) // p
r = (1 << 660) // p

mid = (r - l).isqrt() + 1

table = {}
tmp = 1
for i in trange(mid):
    table[tmp] = i
    tmp = (tmp * base) % n

step = pow(base, -mid, n)
tmp = y * pow(base, -l, n) % n
dl = -1

for i in trange(mid):
    if tmp in table:
        dl = l + i * mid + table[tmp]
        break
    tmp = (tmp * step) % n

k = k0 + dl * p
key = hashlib.md5(long_to_bytes(k)).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(b64decode(ct))
print(flag)

Decision

from Crypto.Util.number import *  
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler  
from sage.crypto.lwe import LWE  
from secret import flag  

flagbin = bin(int.from_bytes(flag.split(b'hgame{')[1][:-1], 'little'))[2:].rjust(25 * 8, "0")  

n, m = 25, 15  
q=getPrime(128)  
F = GF(q)  
V = VectorSpace(F, n)  
D = DiscreteGaussianDistributionIntegerSampler(2**16)   
lwe = LWE(n=n, q=q, D=D)  

def encrypt_bit(bit):  
    if bit == 1:  
        samples_list = [lwe() for _ in range(m)]  
        return [tuple(list(a) + [b]) for a, b in samples_list]  
    else:  
        return [tuple([F.random_element() for _ in range(n + 1)]) for _ in range(m)]  

encbit = []  
for bit in flagbin:  
    encbit.append(encrypt_bit(int(bit)))  

with open("./output", "wb") as f:  
    f.write(str(encbit).encode())  

# q = 256708627612544299823733222331047933697

DLWE（Decision Learning With Error）问题，因为\(m<n\)，没有办法通过求解LWE来判断一个样本是否LWE样本，所以随机选取三组样本组合起来打Dual Attack，判断这三组样本是否均属于LWE样本，如果是，任取其中两个LWE样本与其它未知样本组合进行Dual Attack判断未知样本是否是LWE样本即可：

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

n, m = 25, 15
q = 256708627612544299823733222331047933697

f = open("./output.txt", "r")
data = eval(f.read())
f.close()

def solve(s):
    b = []
    A = []

    for l in s:
        A.append(l[:-1])
        b.append(l[-1])

    A = matrix(GF(q), A)

    kerA = A.left_kernel().basis()
    L = block_matrix(ZZ, [[matrix(kerA)], [q]])
    res = L.BKZ()[20]

    u = vector(GF(q), res)
    ub = u * vector(GF(q), b)

    if(ub > q//2):
        ub = q - ub

    if abs(int(ub)).bit_length() < 100:
        return True
    else:
        return False

idx = [i for i, _ in enumerate(data)]

while True:
    s = []
    idxs = choices(idx, k=3)
    if len(set(idxs)) < 3:
        continue
    for i in idxs:
        s += data[i]
    if solve(s):
        print(idxs)
        break

m = ""
for i in tqdm(idx):
    if i in idxs:
        m += "1"
        continue
    else:
        tmp = data[idxs[0]] + data[idxs[1]] + data[i]
        if solve(tmp):
            m += "1"
        else:
            m += "0"

flag = int(m, 2).to_bytes(25, "little").decode()
print("hgame{" + flag + "}")

Crypto
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇