a ctfer on the load

1
from Crypto.Util.number import bytes_to_long
2
from sympy import nextprime
3

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

7
def trick(k):
8
    if k > 1:
9
        mul = prod(range(1,k))
10
        if k - mul % k - 1 == 0:
11
            return euler_phi(k) + trick(k-1) + 1
12
        else:
13
            return euler_phi(k) + trick(k-1)
14
    else:
15
        return 1
16

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

1
#include <iostream>
2
#include <vector>
3
#include <cmath>
4
using namespace std;
5
typedef long long ll;
6

7
int main() {
8
    ll n = 715849728;
9
    vector<bool> isPrime(n, true);
10
    isPrime[0] = isPrime[1] = false;
11

12
    // 处理2的倍数
13
    for (ll j = 4; j < n; j += 2) {
14
        isPrime[j] = false;
15
    }
16

17
    // 只处理奇数
18
    for (ll i = 3; i * i <= n; i += 2) {
19
        if (isPrime[i]) {
20
            for (ll j = i * i; j < n; j += 2 * i) {
21
                isPrime[j] = false;
22
            }
23
        }
24
    }
25

26
    ll count = 0;
27
    for (ll i = 2; i < n; i++) {
28
        if (isPrime[i]) {
29
            count++;
30
        }
31
    }
32

33
    cout << count << endl;
34
    return 0;
35
}
36

37
//37030583
38

39
#include <cstdio>
40
#include <iostream>
41
#define ll long long
42
using namespace std;
43
const int N = 1e7 + 1;
44
ll phi[N + 10], prime[N + 10];
45
int tot;
46
bool mark[N + 10];
47
void getphi(int n)
48
{
49
    phi[1] = 1;
50
    for (int i = 2; i <= n; i++)
51
    {
52
        if (!mark[i])
53
        {
54
            prime[++tot] = i;
55
            phi[i] = i - 1; // 性质1
56
        }
57
        for (int j = 1; j <= tot && i * prime[j] <= n; j++)
58
        {
59
            mark[i * prime[j]] = 1;
60
            if (!(i % prime[j]))
61
            {
62
                phi[i * prime[j]] = phi[i] * prime[j]; // 性质2
63
                break;
64
            }
65
            else
66
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
67
        }
68
    }
69

70
    for (int i = 2; i <= n; i++)
71
        phi[i] += phi[i - 1];
72
}
73
ll work(int n)
74
{
75
    if (n <= N)
76
        return phi[n];
77
    ll ans = 0;
78
    int pos;
79
    for (int i = 2; i <= n; i = pos + 1)
80
    {
81
        pos = n / (n / i); // 向下取整，很长一段是相同的
82
        ans += (pos - i + 1) * work(n / i);
83
    }
84
    return (ll)n * (n + 1) / 2 - ans;
85
}
86
int main()
87
{
88
    int n = 715849728;
89
    getphi(N);
90
    printf("%lld", work(n));
91
    return 0;
92
}
93

94
// 155763335410704472

1
from Crypto.Util.number import *
2
from sympy import nextprime
3

4
e = 65537
5
trick_result = 155763335410704472+37030583
6

7
p = q = nextprime(trick_result<<128)
8
n=p**2
9
phi=p**2-p
10
enc=2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546
11
d=inverse(e,phi)
12
print(long_to_bytes(int(pow(enc,d,n))))

1
from Crypto.Util.number import *
2
import random
3
from Crypto.Cipher import AES
4
import hashlib
5
from Crypto.Util.Padding import pad
6
from secrets import flag
7

8
list = []
9
bag = []
10
p=random.getrandbits(64)
11
assert len(bin(p)[2:])==64
12
for i in range(4):
13
    t = p
14
    a=[getPrime(32) for _ in range(64)]
15
    b=0
16
    for i in a:
17
        temp=t%2
18
        b+=temp*i
19
        t=t>>1
20
    list.append(a)
21
    bag.append(b)
22
print(f'list={list}')
23
print(f'bag={bag}')
24

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

1
import hashlib
2
from Crypto.Util.number import *
3
from Crypto.Cipher import AES
4
list=
5
bag=
6
ciphertext=
7
L=Matrix(ZZ,65,68)
8
for i in range(64):
9
    L[i,i]=2
10
    L[i,-1]=list[0][-i-1]
11
    L[i,-2]=list[1][-i-1]
12
    L[i,-3]=list[2][-i-1]
13
    L[i,-4]=list[3][-i-1]
14
L[-1,:]=1
15
L[-1,-1]=bag[0]
16
L[-1,-2]=bag[1]
17
L[-1,-3]=bag[2]
18
L[-1,-4]=bag[3]
19
x=L.BKZ()
20
print(x[0])
21
p=''
22
for i in x[0][:64]:
23
    if i==x[0][0]:
24
        p+='1'
25
    else:
26
        p+='0'
27
p=int(p,2)
28
key = hashlib.sha256(str(p).encode()).digest()
29
cipher = AES.new(key, AES.MODE_ECB)
30
flag = cipher.decrypt(ciphertext)
31
print(flag)
32

33

34
'''
35
            |           |
36
|p0 p1 ...|*|a0 a1 a2 a3| = |b0 b1 ...|
37
            |           |
38
'''
39

40
A= matrix(ZZ,list).T
41
B= matrix(ZZ,bag)
42
M= block_matrix(ZZ,[[1,A],[0,B]])
43

44
v = M.BKZ()
45
a = -1*v[-1]
46
p =  int(''.join(map(str,a[:-4][::-1])),2)
47
#17739748707559623655
48
key = hashlib.sha256(str(p).encode()).digest()
49
cipher = AES.new(key, AES.MODE_ECB)
50
cipher.decrypt(ciphertext)

1
from Crypto.Util.number import *
2
import random
3
from sympy import prime
4

5
FLAG=b'hgame{xxxxxxxxxxxxxxxxxx}'
6
e=0x10001
7

8
def primorial(num):
9
    result = 1
10
    for i in range(1, num + 1):
11
        result *= prime(i)
12
    return result
13
M=primorial(random.choice([39,71,126]))
14

15
def gen_key():
16
    while True:
17
        k = getPrime(random.randint(20,40))
18
        a = getPrime(random.randint(20,60))
19
        p = k * M + pow(e, a, M)
20
        if isPrime(p):
21
            return p
22

23
p,q=gen_key(),gen_key()
24
n=p*q
25
m=bytes_to_long(FLAG)
26
enc=pow(m,e,n)
27

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

1
#roca脚本
2
from Crypto.Util.number import *
3
## Coppersmith-howgrave
4
def coppersmith_howgrave(f, N, beta, m, t, R):
5
    #Check if parameters are within bounds
6
    assert 0 < beta <= 1, 'beta not in (0, 1]'
7
    assert f.is_monic(), 'f is not monic'
8

9
    #get delta and the matrix dimension
10
    delta = f.degree()
11
    n = delta * m + t
12

13
    #Building the polynomials
14
    fZ = f.change_ring(ZZ) #change the ring from Zmod(N) to ZZ
15
    x = fZ.parent().gen()  #make x a variable in ZZ
16
    f_list = []
17
    for ii in range(m):
18
        for j in range(delta):
19
            #We want them ordered that's we have N^(m-ii1) and fZ^ii
20
            f_list.append(((x*R)^j) * N^(m-ii) * fZ(x*R)^(ii)) #the g_{i,j}
21
    for ii in range(t):
22
        f_list.append((x*R)^ii * fZ(x*R)^m) #the h_i
23

24
    #Build the lattice
25
    B = matrix(ZZ, n) # n = delta * m + t
26
    for ii in range(n):
27
        for j in range(ii+1):
28
            B[ii, j] = f_list[ii][j]
29

30
    #LLL it
31
    B_lll = B.LLL(early_red = True, use_siegel = True)
32

33
    #take the shortest vector to construct our new poly g
34
    g = 0
35
    for ii in range(n):
36
        g += x^ii * B_lll[0, ii] / R^ii
37

38
    #factor the polynomial
39
    potential_roots = g.roots()
40
    #print('potential roots:', potential_roots)
41

42
    #we don't need to do this Since our we test in our roca function
43
#     #test roots
44
#     roots = []
45
#     for r in potential_roots:
46
#         if r[0].is_integer():
47
#             res = fZ(ZZ(r[0]))
48
#             if gcd(N, res) >= N^beta:
49
#                 roots.append(ZZ(r[0]))
50
    #print('roots:', roots)
51
    return potential_roots
52
    #return roots
53
def roca(N, M_prime, g, m, t, beta):
54
    g = int(g)
55
    c_prime = discrete_log(Zmod(M_prime)(N), Zmod(M_prime)(g))
56
    ord_M_prime = Zmod(M_prime)(g).multiplicative_order()
57

58
    #search boundaries
59
    bottom = c_prime // 2
60
    top =(c_prime + ord_M_prime) // 2
61
    print('numbers to check',   top - bottom, ' between ', (bottom, top))
62

63

64
    #constants for coppersmith
65
    P.<x> = PolynomialRing(Zmod(N))
66
    epsilon = beta / 7
67
    X = floor(2 * N^beta / M_prime)
68

69
    #the search
70
    for i, a in enumerate(range(bottom, top)):
71
        if i % 1000 == 0: #count iterations
72
            print(i)
73

74
        #construct polynomial
75
        f = x + int((inverse_mod(M_prime, N)) * int(pow(g, a, M_prime)))
76

77
        #roots = f.small_roots(X, beta, epsilon) #coppersmith
78
        roots = coppersmith_howgrave(f, N, beta, m, t, X)
79
        #check solutions
80
        for k_prime, _ in roots:
81
            p = int(k_prime * M_prime) + int(pow(g, a, M_prime))
82
            if N % p == 0:
83
                return p, N//p
84
    return -1, -1
85
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
86
e=65537
87

88
def get_M1_m_t_values(key_size):
89
    if 512 <= key_size < 1024:
90
        m = 5
91
        M1=0x1b3e6c9433a7735fa5fc479ffe4027e13bea
92
    elif 1024 <= key_size < 2048:
93
        m = 4
94
        M1=0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
95
    elif 2048 <= key_size < 3072:
96
        m = 6
97
        M1=0x016928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
98
    elif 3072 <= key_size < 4096:
99
        m = 25
100
    else:
101
        m = 7
102
    return M1,m, m+1
103
M_prime,m, t = get_M1_m_t_values(512)
104
p, q = roca(n, M_prime, e, m, t, .5)
105
assert(p*q==n)
106
print(p)
107
print(q)
108
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
109
print(long_to_bytes(int(pow(enc,inverse_mod(e,(p-1)*(q-1)),n))))

1
import random
2

3
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"]
4
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"]
5
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"]
6
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"]
7
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"]
8
Minor_Arcana = wands + cups + swords + pentacles
9
tarot = Major_Arcana + Minor_Arcana
10
reversals = [0,-1]
11

12
Value = []
13
cards = []
14
YOUR_initial_FATE = []
15
while len(YOUR_initial_FATE)<5:
16
    card = random.choice(tarot)
17
    if card not in cards:
18
        cards.append(card)
19
        if card in Major_Arcana:
20
            k = random.choice(reversals)
21
            Value.append(tarot.index(card)^k)
22
            if k == -1:
23
                YOUR_initial_FATE.append("re-"+card)
24
            else:
25
                YOUR_initial_FATE.append(card)
26
        else:
27
            Value.append(tarot.index(card))
28
            YOUR_initial_FATE.append(card)
29
    else:
30
        continue
31
print("Oops!lets reverse 1T!")
32

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

35
YOUR_final_Value = Value
36

37
def Fortune_wheel(FATE):
38
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
39
    return FATEd
40

41
for i in range(250):
42
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
43
print(YOUR_final_Value)
44
YOUR_final_FATE = []
45
for i in YOUR_final_Value:
46
    YOUR_final_FATE.append(tarot[i%78])
47
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
48
print("oh,now you GET th3 GOOd lU>k,^^")
49

50
"""
51
Oops!lets reverse 1T!
52
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
53
Your destiny changed!
54
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
55
oh,now you GET th3 GOOd lU>k,^^
56
"""

1
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"]
2
Minor_Arcana = ["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",
3
                "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",
4
                "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",
5
                "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"]
6
tarot = Major_Arcana + Minor_Arcana
7

8
YOUR_final_Value = [2532951952066291774890498369114195917240794704918210520571067085311474675019,
9
                    2532951952066291774890327666074100357898023013105443178881294700381509795270,
10
                    2532951952066291774890554459287276604903130315859258544173068376967072335730,
11
                    2532951952066291774890865328241532885391510162611534514014409174284299139015,
12
                    2532951952066291774890830662608134156017946376309989934175833913921142609334]
13

14
def reverse_Fortune_wheel(FATEd):
15
    f0 = (FATEd[4] - FATEd[3] + FATEd[2] - FATEd[1] + FATEd[0]) // 2
16
    return [f0, FATEd[0] - f0, FATEd[1] - FATEd[0] + f0, FATEd[2] - FATEd[1] + FATEd[0] - f0, FATEd[3] - FATEd[2] + FATEd[1] - FATEd[0] + f0]
17

18
for _ in range(250):
19
    YOUR_final_Value = reverse_Fortune_wheel(YOUR_final_Value)
20

21
YOUR_initial_FATE = ['re-' + tarot[i ^ -1] if i < 0 else tarot[i] for i in YOUR_final_Value]
22
FLAG = f"hgame{{{'&'.join(YOUR_initial_FATE).replace(' ', '_')}}}"
23

24
print(FLAG)

1
from Crypto.Util.number import *
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import pad
4
from random import randint
5
import hashlib
6
from secrets import flag
7

8
def add_THCurve(P, Q):
9
    if P == (0, 0):
10
        return Q
11
    if Q == (0, 0):
12
        return P
13
    x1, y1 = P
14
    x2, y2 = Q
15
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
16
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
17
    return x3, y3
18

19

20
def mul_THCurve(n, P):
21
    R = (0, 0)
22
    while n > 0:
23
        if n % 2 == 1:
24
            R = add_THCurve(R, P)
25
        P = add_THCurve(P, P)
26
        n = n // 2
27
    return R
28

29

30
p = getPrime(96)
31
a = randint(1, p)
32
G = (randint(1,p), randint(1,p))
33

34
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
35

36
x = randint(1, p)
37
Q = mul_THCurve(x, G)
38
print(f"p = {p}")
39
print(f"G = {G}")
40
print(f"Q = {Q}")
41

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

48
"""
49
p = 55099055368053948610276786301
50
G = (19663446762962927633037926740, 35074412430915656071777015320)
51
Q = (26805137673536635825884330180, 26376833112609309475951186883)
52
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"
53
"""

1
p = 55099055368053948610276786301
2
Gx, Gy = 19663446762962927633037926740, 35074412430915656071777015320
3
Qx, Qy = 26805137673536635825884330180, 26376833112609309475951186883
4
G = (19663446762962927633037926740, 35074412430915656071777015320)
5
Q = (26805137673536635825884330180, 26376833112609309475951186883)
6
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"
7
from Crypto.Util.number import*
8
numerator = ((pow(Qy,3,p)+1)*Gx*Gy - (pow(Gy,3,p)+1)*Qx*Qy) % p
9
denominator = (pow(Gx,3,p)*Qx*Qy - pow(Qx,3,p)*Gx*Gy) % p
10
a = (numerator * pow(denominator, -1, p)) % p
11
print(a)
12

13
a=39081810733380615260725035189
14

15
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
16

17
R.<x,y,z> = Zmod(p)[]
18
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
19
E = EllipticCurve_from_cubic(cubic,morphism=True)
20
P = E(G)
21
Q = E(Q)
22
r = 60869967041981
23
m = (r*Q).log(r*P)
24
from Crypto.Cipher import AES
25
import hashlib
26

27
key = hashlib.sha256(str(m).encode()).digest()
28
cipher = AES.new(key, AES.MODE_ECB)
29
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"
30
flag = cipher.decrypt(ciphertext)
31
print("Flag:", flag)

1
from Crypto.Util.number import getPrime, long_to_bytes,bytes_to_long
2
from secrets import flag
3
from sage.all import *
4

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

11
m = bytes_to_long(flag).bit_length()
12
n = 70
13
p = derive_M(n)
14

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

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

1
from Crypto.Util.number import *
2

3
import logging
4
logging.basicConfig(
5
    level=logging.DEBUG,
6
    format="[%(levelname)s] %(message)s"
7
)
8

9
# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
10
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
11
def flatter(M, **kwds):
12
    from subprocess import check_output
13
    from re import findall
14
    M = matrix(ZZ,M)
15
    # compile https://github.com/keeganryan/flatter and put it in [imath:0]PATH
16
    z = '[[' + ']\n['.join(' '.join(map(str,row)) for row in M) + ']]'
17
    ret = check_output(["flatter"], input=z.encode())
18
    return matrix(M.nrows(), M.ncols(), map(int,findall(b'-?\\d+', ret)))
19
def checkMatrix(M, wl=[-1, 1]):
20
  M = [list(_) for _ in list(M)]
21
  ml = list(set(flatten(M)))
22
  logging.debug(ml)
23
  return sorted(ml) == sorted(wl)
24

25
def Nguyen_Stern(h, m, n, M):
26
  B = matrix(ZZ, m)
27
  B[0, 0] = M
28
  h0i = Integer(h[0]).inverse_mod(M)
29
  for i in range(1, m):
30
    B[i, 0] = - h[i] * h0i
31
    B[i, i] = 1
32
  #L = B.BKZ()  # slooooooow
33
  L = flatter(B)
34
  logging.info('flatter done.')
35

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

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

45
  '''
46
  try:
47
    Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
48
    rsc = Lxc.row_space()
49
    logging.debug([xi in rsc for xi in Lx_real])
50
  except:
51
    pass
52
  '''
53

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

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

65
  Lx2 = []
66
  e = vector(ZZ, [1] * m)
67
  rsc = Lxc.row_space()
68
  for lx in Lx:
69
    if lx in rsc:
70
      Lx2 += [lx]
71
      continue
72
    lx = e - lx
73
    if lx in rsc:
74
      Lx2 += [lx]
75
      continue
76
    logging.warning('Something wrong?')
77
  Lx = matrix(Zmod(M), Lx2)
78

79
  vh = vector(Zmod(M), h)
80
  va = Lx.solve_left(vh)
81
  return Lx, va
82

83

84
m=247
85
n=70
86
M=
87
h=
88
Lx, va = Nguyen_Stern(h, m, n, M)
89

90

91
for i in Lx:
92
  flag=''
93
  for j in i:
94
    flag+=str(j)
95
  flag=long_to_bytes(int(flag,2))
96
  if b'hgame' in flag:
97
    print(flag)