HGAME2025-Crypto

Crypto

sieve

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

FLAG = b'hgame{xxxxxxxxxxxxxxxxxxxxxx}'
m = bytes_to_long(FLAG)

def trick(k):
    if k > 1:
        mul = prod(range(1,k)) 
        if k - mul % k - 1 == 0:
            return euler_phi(k) + trick(k-1) + 1
        else:
            return euler_phi(k) + trick(k-1)
    else:
        return 1

e = 65537
p = q = nextprime(trick(e^2//6)<<128)
n = p * q
enc = pow(m,e,n)
print(f'{enc=}')

trick计算的是小于k的所有数的欧拉函数之和加上素数的个数

这个k - mul % k - 1 == 0成立代表此时为素数(因为wilson定理)

然后使用c/c++写脚本比较好，python容易爆了

计算素数的个数

埃氏筛

#include <bits/stdc++.h>
using namespace std;

int main()
{	
	int n=715849728;
    vector<int> isPrime(n);
    int count=0;
    for(int i=2;i<n;i++){
        if(!isPrime[i]){
            count++;
            long long int j=(long long)i*i;
            while(j<n){
                isPrime[j]=1;
                j+=i;
            }
        }
    }
    cout<<count<<endl;
    //37030583
    return 0;
}

计算欧拉函数之和

这个找了个脚本

快速求欧拉函数之和-CSDN博客

#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int N=1e7+1;
ll phi[N+10],prime[N+10];
int tot;
bool mark[N+10];
void getphi(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
     {
        if(!mark[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;//性质1
        }
        for(int j=1;j<=tot&&i*prime[j]<=n;j++)
        {
            mark[i*prime[j]]=1;
            if(!(i%prime[j]))
             {
                phi[i*prime[j]]=phi[i]*prime[j];//性质2
                break;
             }
            else
             phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
     }

     for(int i=2;i<=n;i++)
      phi[i]+=phi[i-1];
}
ll work(int n)
{
    if(n<=N) return phi[n];
    ll ans=0;int pos;
    for(int i=2;i<=n;i=pos+1)
    {
        pos=n/(n/i);//向下取整，很长一段是相同的
        ans+=(pos-i+1)*work(n/i);
    }
    return (ll)n*(n+1)/2-ans;
}
int main()
{
    int n;
    getphi(N);
    scanf("%d",&n);
    printf("%lld",work(n));
    return 0;
}

flag

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

e = 65537
trick_result = 155763335410704472+37030583

p = q = nextprime(trick_result<<128)
print(p.bit_length())
phi=p**2-p
enc=2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546
print(long_to_bytes(int(pow(enc,inverse(e,phi),p*p))))
#b'hgame{sieve_is_n0t_that_HArd}'

ezBag

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secrets import flag

list = []
bag = []
p=random.getrandbits(64)
assert len(bin(p)[2:])==64
for i in range(4):
    t = p
    a=[getPrime(32) for _ in range(64)]
    b=0
    for i in a:
        temp=t%2
        b+=temp*i
        t=t>>1
    list.append(a)
    bag.append(b)
print(f'list={list}')
print(f'bag={bag}')

key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

01背包问题，但无法使用常规脚本求解

只使用一组数据的话会发现密度已经到了2.0了，很明显不满足

所以可以多用几组数据构造格（为什么这样能出我也不知道）

$$\left( \begin{matrix} 1&0&…&0&a[0][63]&a[1][63]&a[2][63]&a[3][63]\\ 0&1&…&0&a[0][62]&a[1][62]&a[2][62]&a[3][62]\\ ⋮&⋮&⋱&⋮&⋮&⋮&⋮&⋮\\ 0&0&…&1&a[0][0]&a[1][0]&a[2][0]&a[3][0]\\ 0&0&…&0&b[0]&b[1]&b[2]&b[3]\\ \end{matrix} \right)$$

但是构造完发现格不出来，尝试常见的优化

$$\left( \begin{matrix} 2&0&…&0&a[0][63]&a[1][63]&a[2][63]&a[3][63]\\ 0&2&…&0&a[0][62]&a[1][62]&a[2][62]&a[3][62]\\ ⋮&⋮&⋱&⋮&⋮&⋮&⋮&⋮\\ 0&0&…&2&a[0][0]&a[1][0]&a[2][0]&a[3][0]\\ 1&1&…&1&b[0]&b[1]&b[2]&b[3]\\ \end{matrix} \right)$$

这样使用LLL格不出来，BKZ就可以(我也不懂)

然后格出来的第一个向量就我们需要的，我们知道最高位一定为1，所以跟第一位一样的就是1就行了

import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
list=
bag=
ciphertext=
L=Matrix(ZZ,65,68)
for i in range(64):
    L[i,i]=2
    L[i,-1]=list[0][-i-1]
    L[i,-2]=list[1][-i-1]
    L[i,-3]=list[2][-i-1]
    L[i,-4]=list[3][-i-1]
L[-1,:]=1
L[-1,-1]=bag[0]
L[-1,-2]=bag[1]
L[-1,-3]=bag[2]
L[-1,-4]=bag[3]
x=L.BKZ()
print(x[0])
p=''
for i in x[0][:64]:
    if i==x[0][0]:
        p+='1'
    else:
        p+='0'
p=int(p,2)
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(flag)
#b'hgame{A_S1mple_Modul@r_Subset_Sum_Problem}\x06\x06\x06\x06\x06\x06'

suprimeRSA

from Crypto.Util.number import *
import random
from sympy import prime

FLAG=b'hgame{xxxxxxxxxxxxxxxxxx}'
e=0x10001

def primorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= prime(i)
    return result
M=primorial(random.choice([39,71,126]))

def gen_key():
    while True:
        k = getPrime(random.randint(20,40))
        a = getPrime(random.randint(20,60))
        p = k * M + pow(e, a, M)
        if isPrime(p):
            return p

p,q=gen_key(),gen_key()
n=p*q
m=bytes_to_long(FLAG)
enc=pow(m,e,n)

print(f'{n=}')
print(f'{enc=}')

改之后就是roca，套脚本就好了

通过enc的值可以判断密钥空间大小

from Crypto.Util.number import *
## Coppersmith-howgrave
def coppersmith_howgrave(f, N, beta, m, t, R):
    #Check if parameters are within bounds
    assert 0 < beta <= 1, 'beta not in (0, 1]'
    assert f.is_monic(), 'f is not monic'
    
    #get delta and the matrix dimension
    delta = f.degree()
    n = delta * m + t
    
    #Building the polynomials
    fZ = f.change_ring(ZZ) #change the ring from Zmod(N) to ZZ
    x = fZ.parent().gen()  #make x a variable in ZZ
    f_list = [] 
    for ii in range(m):
        for j in range(delta):
            #We want them ordered that's we have N^(m-ii1) and fZ^ii
            f_list.append(((x*R)^j) * N^(m-ii) * fZ(x*R)^(ii)) #the g_{i,j}
    for ii in range(t):
        f_list.append((x*R)^ii * fZ(x*R)^m) #the h_i
        
    #Build the lattice
    B = matrix(ZZ, n) # n = delta * m + t
    for ii in range(n):
        for j in range(ii+1):
            B[ii, j] = f_list[ii][j]
            
    #LLL it
    B_lll = B.LLL(early_red = True, use_siegel = True)

    #take the shortest vector to construct our new poly g
    g = 0
    for ii in range(n):
        g += x^ii * B_lll[0, ii] / R^ii
    
    #factor the polynomial
    potential_roots = g.roots()
    #print('potential roots:', potential_roots)
    
    #we don't need to do this Since our we test in our roca function
#     #test roots
#     roots = []
#     for r in potential_roots:
#         if r[0].is_integer():
#             res = fZ(ZZ(r[0]))
#             if gcd(N, res) >= N^beta:
#                 roots.append(ZZ(r[0]))
    #print('roots:', roots)
    return potential_roots
    #return roots
def roca(N, M_prime, g, m, t, beta):
    g = int(g)
    c_prime = discrete_log(Zmod(M_prime)(N), Zmod(M_prime)(g))
    ord_M_prime = Zmod(M_prime)(g).multiplicative_order()
    
    #search boundaries
    bottom = c_prime // 2 
    top =(c_prime + ord_M_prime) // 2 
    print('numbers to check',   top - bottom, ' between ', (bottom, top))

    
    #constants for coppersmith
    P.<x> = PolynomialRing(Zmod(N))
    epsilon = beta / 7
    X = floor(2 * N^beta / M_prime)
    
    #the search
    for i, a in enumerate(range(bottom, top)):
        if i % 1000 == 0: #count iterations
            print(i)
            
        #construct polynomial
        f = x + int((inverse_mod(M_prime, N)) * int(pow(g, a, M_prime)))

        #roots = f.small_roots(X, beta, epsilon) #coppersmith
        roots = coppersmith_howgrave(f, N, beta, m, t, X)
        #check solutions
        for k_prime, _ in roots:
            p = int(k_prime * M_prime) + int(pow(g, a, M_prime))
            if N % p == 0:
                return p, N//p
    return -1, -1
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
e=65537

def get_M1_m_t_values(key_size):
    if 512 <= key_size < 1024:
        m = 5
        M1=0x1b3e6c9433a7735fa5fc479ffe4027e13bea
    elif 1024 <= key_size < 2048:
        m = 4
        M1=0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
    elif 2048 <= key_size < 3072:
        m = 6
        M1=0x016928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
    elif 3072 <= key_size < 4096:
        m = 25
    else:
        m = 7
    return M1,m, m+1
M_prime,m, t = get_M1_m_t_values(512)
p, q = roca(n, M_prime, e, m, t, .5) 
assert(p*q==n)
print(p)
print(q)
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
print(long_to_bytes(int(pow(enc,inverse_mod(e,(p-1)*(q-1)),n))))

"""
24000
954455861490902893457047257515590051179337979243488068132318878264162627
824752716083066619280674937934149242011126804999047155998788143116757683
b'hgame{ROCA_ROCK_and_ROll!}'
"""

Ancient Recall

import random

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card)^k)
            if k == -1:
                YOUR_initial_FATE.append("re-"+card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue
print("Oops!lets reverse 1T!")

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")

YOUR_final_Value = Value
def Fortune_wheel(FATE):
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
    return FATEd

for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
    YOUR_final_FATE.append(tarot[i%78])
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

逆着分析一下就好了

就讲一下逆YOUR_final_Value这个

记上一个状态为a,b,c,d,e，则下一个状态为a+b,b+c,c+d,d+e,e+a

之后看代码里就能理解了e+a-a-b+b+c-c-d+d+e=2e，然后一个个求出来就可以还原了

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

YOUR_final_Value=[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
def reverse_Fortune_wheel(FATEd):
    f0 = (FATEd[4] - FATEd[3] + FATEd[2] - FATEd[1] + FATEd[0]) // 2
    f1 = FATEd[0] - f0
    f2 = FATEd[1] - f1
    f3 = FATEd[2] - f2
    f4 = FATEd[3] - f3
    return [f0, f1, f2, f3, f4]
for i in range(250):
    YOUR_final_Value = reverse_Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_initial_FATE=[]
for i in YOUR_final_Value:
    if i<0:
        YOUR_initial_FATE.append('re-'+tarot[i^-1])
    else:
       YOUR_initial_FATE.append(tarot[i])
FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")
print(FLAG)
#hgame{re-The_Moon&re-The_Sun&Judgement&re-Temperance&Six_of_Cups}

Intergalactic Bound

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


p = getPrime(96)
a = randint(1, p)
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
x = randint(1, p)
Q = mul_THCurve(x, G)
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

Twisted Hessian曲线：$a*x^3*+y^3+1=d*x*y$

但不知道参数a和d

但是通过两个点，可以联立两个方程进行求解

之后将该曲线映射到ECC上求解

通过2024羊城杯，可以知道利用sage中的EllipticCurve_from_cubic，可以直接做映射

参考2024羊城杯：tangcuxiaojikuai.xyz/post/689431.html

p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"

# 定义有限域
F = GF(p)

# 定义多项式环，a 和 d 作为未知量
R.<a, d> = PolynomialRing(F)

# 转换到有限域
G0, G1 = F(G[0]), F(G[1])
Q0, Q1 = F(Q[0]), F(Q[1])

# 定义方程
eq1 = d * G0 * G1 - (a * G0^3 + G1^3 + 1)
eq2 = d * Q0 * Q1 - (a * Q0^3 + Q1^3 + 1)

# 求解
solutions = R.ideal(eq1, eq2).variety()

a=int(solutions[0]["a"])
d=int(solutions[0]["d"])
d = (a*G[0]^3+G[1]^3+1)%p*inverse_mod(G[0]*G[1],p)%p

R.<x,y,z> = Zmod(p)[]
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
G = E(G)
Q = E(Q)
x = (Q).log(G)
x = int(x)
import hashlib
from Crypto.Cipher import AES
key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(flag)
#b'hgame{N0th1ng_bu7_up_Up_UP!}\x04\x04\x04\x04

SPiCa

from Crypto.Util.number import getPrime, long_to_bytes,bytes_to_long
from secrets import flag
from sage.all import *

def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A

with open("data.txt", "w") as file:
    file.write(str(m) + "\n")
    file.write(str(p) + "\n")
    for item in h:
        file.write(str(item) + "\n")

直接抄就行了https://0xffff.one/d/2077

可以先到后面攻击部分开始看，会直观一点

from Crypto.Util.number import *

import logging
logging.basicConfig(
    level=logging.DEBUG,
    format="[%(levelname)s] %(message)s"
)

# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
def flatter(M, **kwds):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in [imath:0]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)))
def checkMatrix(M, wl=[-1, 1]):
  M = [list(_) for _ in list(M)]
  ml = list(set(flatten(M)))
  logging.debug(ml)
  return sorted(ml) == sorted(wl)

def Nguyen_Stern(h, m, n, M):
  B = matrix(ZZ, m)
  B[0, 0] = M
  h0i = Integer(h[0]).inverse_mod(M)
  for i in range(1, m):
    B[i, 0] = - h[i] * h0i
    B[i, i] = 1
  #L = B.BKZ()	# slooooooow
  L = flatter(B)
  logging.info('flatter done.')

  '''
  vh = vector(Zmod(M), h)
  logging.debug([vector(Zmod(M), list(l)) * vh  for l in L])
  '''

  Lxo = matrix(ZZ, L[:m-n])
  Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster
  logging.info('right_kernel done.')

  '''
  try:
    Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
    rsc = Lxc.row_space()
    logging.debug([xi in rsc for xi in Lx_real])
  except:
    pass
  '''

  e = matrix(ZZ, [1] * m)
  B = block_matrix([[-e], [2*Lxc]])
  Lx = B.BKZ()
  logging.info('BKZ done.')
  assert checkMatrix(Lx)
  assert len(set(Lx[0])) == 1

  Lx = Lx[1:]
  E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())])
  Lx = (Lx + E) / 2

  Lx2 = []
  e = vector(ZZ, [1] * m)
  rsc = Lxc.row_space()
  for lx in Lx:
    if lx in rsc:
      Lx2 += [lx]
      continue
    lx = e - lx
    if lx in rsc:
      Lx2 += [lx]
      continue
    logging.warning('Something wrong?')
  Lx = matrix(Zmod(M), Lx2)

  vh = vector(Zmod(M), h)
  va = Lx.solve_left(vh)
  return Lx, va


m=247
n=70
M= 
h=
Lx, va = Nguyen_Stern(h, m, n, M)


for i in Lx:
  flag=''
  for j in i:
    flag+=str(j)
  flag=long_to_bytes(int(flag,2))
  if b'hgame' in flag:
    print(flag)
#hgame{U_f0und_3he_5pec14l_0n3!}