杂题闲记-3

TCTF Quals 2020

baby ring

当时打Quals的时候还没怎么开始密码学，全程划水233，看了rxz大佬的exp发现他是拿线性基做的，这就是OI大佬吗，i了i了，但由于我是条懒狗，所以并没有去学线性基，就还是用最基本的线代知识做。

分析题目，可知是需要输入64组x，然后server计算 $y_{i} \equiv x_{i}^{e} \mod n_{i}$ ，之后获取输入 $v$ ，重复64次 $c u r = R C 4 (c u r, k e y) X O R y_{i}$ ，由于RC4计算中均是异或PRNG的生成流，又考虑到异或运算的交换律，可知 $c u r = v X O R R C 4_{s u m} X O R y_{s u m}$ ，其中 $R C 4_{s u m}$ 指RC4的所有生成流异或的结果，由于RC4的key已知，这部分是确定的， $y_{s u m}$ 指所有 $y_{i}$ 的异或结果，可知需要让 $y_{s u m} = R C 4_{s u m}$

仔细思考就会发现，这其实是个模线性方程问题，即构造矩阵 $Y = [y b_{0}, y b_{1}, \dots, y b_{63}]$ ，其中列向量 $y b_{i}$ 为 $y_{i}$ 的二进制排列，再考虑向量 $r = [R C 4 b]$ ，其为 $R C 4_{s u m}$ 的二进制排列，可知原问题等价于求出在模2（异或等价于模2上的加）上的 $A x = r$ 。

这时再考虑 $y_{i}$ 的生成，为了方便起见，只需设置一个base， $y_{i} \equiv b a s e^{e} \mod n_{i}$ 即可，进行小范围遍历（我这里选取’LordRiot’为msg，遍历到3即发现解，看到有别人的exp，选用‘aaa’做msg，2即可求解了），即可找到使得 $A x = r$ 有解的base，之后根据向量 $x$ ，第 i 次交互时，若 $x_{i}$ 为1，则发送base，否则发送0即可，exp如下：

from winpwn import *
from hashlib import sha256
from struct import pack, unpack
from Crypto.Cipher import ARC4
context.log_level = "debug"

e, Ns = 

p = remote('127.0.0.1', 10001)
p.recvuntil('message:')
p.sendline('LordRiot')

# get target
key = sha256('LordRiot'.encode()).digest()[:16]
E = ARC4.new(key)
target = 0
for i in range(64):
    target ^= unpack('Q', E.encrypt(pack('Q', 0)))[0]
print(target)

# use sage get ans
'''
from sage.all import *
candidate = [pow(3, e, N) % (1 << 64) for N in Ns]

I = GF(2)
_matrix = [[] for _ in range(64)]
for i in range(64):
    _matrix[i] = [int(bit) for bit in bin(candidate[i])[2:].rjust(64, '0')]
_matrix = matrix(I, _matrix)

target_vec = [int(bit) for bit in bin(target)[2:].rjust(64, '0')]
target_vec = matrix(I, target_vec)

ans = _matrix.solve_left(target_vec)
print('ans =', list(res[0]))
'''
ans = [0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1]

# io to get flag
print(len(ans))
for i in range(64):
    p.recvuntil('x')
    if ans[i] == 1:
        p.sendline('3')
    else:
        p.sendline('0')
p.recvuntil('v:')
p.sendline('1')
p.interactive()

Simple Curve

这个题涉及到概念 hyperelliptic curve，具体的理论我在Way to Crypto中已添加，此处不做赘述，这篇wp讲的很好，推荐一看。

这里的曲线是基于 $F_{q^{n}}, q = 2, n = 256$ 的

这里使用的超椭圆曲线即为： $v^{2} + h (u) v = f (u)$ ，此处 $h (u) = u^{2} + u, f (u) = u^{5} + u^{3} + 1$

之前的paper中提供了一种计算Jacobian阶的算法（看到Balsn是用的Magma，可以直接算）

Magma代码：

P<x> := PolynomialRing(GF(2^256));
C := HyperellipticCurve(x^5 + x^3 + 1, x^2 + x);
C;
J := Jacobian(C);
O := #J;
O;

具体算法步骤可以参见Way to Crypto中的描述和exp中的代码

这里的F.fetch_int(n) 函数的意思是将整数n转为二进制序列，然后将其作为域F上多项式 $\sum_{i = 1}^{r} a_{i} x_{i}$ 的系数，即 $a_{i}$ ，实例如下：

而decode时的这个操作:

1	x = [i.integer_representation() for i in x]

其中于integer_representation()函数为fetch_int()的逆函数，即是将多项式转为了一个整数。

exp如下：

from Crypto_tools import *

F = GF(2**256)
P = PolynomialRing(F, 'u, v')
u, v = P.gens()
PP = PolynomialRing(F, 'w')
w = PP.gens()[0]

h = u^2 + u
f = u^5 + u^3 + 1
c = v^2 + h*v - f
f = f(u=w)
h = h(u=w)


def encode(plain):
    assert plain < 2 ** 256
    x = F.fetch_int(plain)
    y, k = c(u=x, v=w).roots()[0]
    assert k == 1
    return w - x, y


def decode(c):
    x, y = c
    tmp = x
    x = [i.integer_representation() for i in x]
    y = [i.integer_representation() for i in y]
    return x, y


def add(p1, p2):
    a1, b1 = p1
    a2, b2 = p2
    d1, e1, e2 = xgcd(a1, a2)
    d, c1, c2 = xgcd(d1, b1 + b2 + h)
    di = PP(1 / d)
    a = a1 * a2 * di * di
    b = (c1 * e1 * a1 * b2 + c1 * e2 * a2 * b1 + c2 * (b1 * b2 + f)) * di
    b %= a

    while a.degree() > 2:
        a = PP((f - b * h - b * b) / a)
        b = (-h - b) % a
    a = a.monic()
    return a, b


def mul(p, k):
    if k == 1:
        return p
    else:
        tmp = mul(p, k // 2)
        tmp = add(tmp, tmp)
        if k & 1:
            tmp = add(tmp, p)
        return tmp

# exp

def re_decode(data):
      xs, ys = data
      pt_x = PP([F.fetch_int(i) for i in xs])
      pt_y = PP([F.fetch_int(i) for i in ys])
      return (pt_x, pt_y)


# Paramters and curve
q = 2
n = 256
genus = 2
# h(x) = x^2 + x
# f(x) = x^5 + x^3 + 1
_h = lambda x: x ^ 2 + x
_f = lambda x: x ^ 5 + x ^ 3 + 1

# Calc M_i
M = []

for i in range(genus):
    P.<x> = PolynomialRing(GF(q ^ (i + 1)))
    C = HyperellipticCurve(_f(x), _h(x))
    M.append(C.cardinality())
print("Calc M done")

# Calc a_i
a = [0]
for i in range(genus):
    a.append((M[i] - 1 - q ^ (i + 1) + a[i] ^ (i + 1)) / (i + 1))
a = [1] + a[1:]
print("Calc a done")

# Calc gamma_i
var('X')
function = -genus * q
for i in range(genus + 1):
    function += a[i] * X ^ (genus - i)
gamma = list(map(lambda x: x.rhs(), solve([function == 0], X)))
print("Calc gamma done")

# Calc alpha_i
alpha = []
for i in range(genus):
    function = X ^ 2 - gamma[i] * X + q
    alpha.append(list(map(lambda x: x.rhs(), solve([function == 0], X))))
print("Calc alpha done")

# Calc #J
order = 1
for i in range(genus):
    order *= abs(1 - alpha[i][0] ^ n) ^ 2
print('#J =', int(order))


ctext = ([113832590633816699072296178013238414056344242047498922038140127850188287361982, 107565990181246983920093578624450838959059911990845389169965709337104431186583, 1], [60811562094598445636243277376189331059312500825950206260715002194681628361141, 109257511993433204574833526052641479730322989843001720806658798963521316354418])
J_card = int(order)


d = inverse(0x10001, J_card)
flag_point = mul(re_decode(ctext), d)
flag_int = decode(flag_point)[0][0]

print(long_to_bytes(flag_int))

TCTF2020 Final

Obviously Transfer

本题的关键是将 $c = x 0 X O R x 1$ ，看作 $c \equiv m^{e} \mod n$ ，则有 $c^{d} \equiv m^{e d} \equiv m \mod n$ ，则可解密出flag。

流程为：

先获取一组数据x0，x1，然后直接将x0发给server，则返回的m0p即为m0，则通过生成m0r再与m1p异或可以得到 $f l a g X O R k_{1}$
考虑到其中 $k_{1} = (x_{0} X O R x_{1})^{d}$ ，考虑 $(x_{0} X O R x_{1}) \equiv m^{e} \mod n$ ，则有 $k_{1} = m$ ，从而转化为已知enc，求m问题
想到可以通过partial oracle来实现，至于获取具体的low bit，是通过m0p的低位和m1p的高位异或而确定的，因为m0p的低位为 $l s b X O R m 0_{l o w}$ ，而m1p的高位与m1相同概率很大（因为k1模n，其高位均匀分布，故当样本增多的时候产生影响不断降低），而m1的高位又与m0相同，故重复一定次数，根据概率即可确定lsb

exp如下：

from winpwn import *
from Crypto_tools import *


def get_num(until):
    p.recvuntil(until)
    return int(p.recvuntil('\n'))


BITS = 2048
flag_len = BITS // 8
p = remote('127.0.0.1', 10002)
n = get_num('n = ')
e = get_num('e = ')

x0 = get_num('x0 = ')
x1 = get_num('x1 = ')

p.sendline(str(x0))
m0 = get_num('m0p = ')
m1 = get_num('m1p = ')

m0r = (((m0 & 1) << (BITS - 1)) | (m0 >> 1))
k1_flag = m1 ^ m0 ^ m0r


# partial oracle attack

def oracle(enc):
    cnt = 0
    loop = 40
    for i in range(loop):
        _x0 = get_num('x0 = ')
        _x1 = get_num('x1 = ')
        p.sendline(str(_x0 ^ enc))
        low_bit = get_num('m0p = ') & 1
        high_bit = get_num('m1p = ') >> (BITS - 1)
        cnt += low_bit ^ high_bit
    return 1 if cnt / loop > 0.5 else 0


def partial_oracle_attack(c, e, n, enc):
    nbits = n.bit_length()
    decimal.getcontext().prec = nbits
    low = decimal.Decimal(0)
    high = decimal.Decimal(n)
    for i in tqdm(range(nbits)):
        c = (c * pow(2, e, n)) % n
        if oracle(c) == 0:
            high = (low + high) / 2
        else:
            low = (low + high) / 2
        if i % 8 == 0:
            flag = enc ^ int(high)
            print(long_to_bytes(flag)[:i // 8])
    return int(high)


k1 = partial_oracle_attack(x0 ^ x1, e, n, k1_flag)

由于其是有概率的，所以可能需要多试几次，成功时效果如下：

本地大概需要25秒左右可以跑出一字节flag。

CryptoCTF 2020

Decent RSA

这题学到了神奇的套路233，如果将n转化为 $G F (q)$ 上多项式后，其分量不多，则可以在多项式上做分解求得p，q

此题中，n在 $G F (11)$ 上表示为如下

x^592 + x^589 + 2*x^559 + x^547 + 2*x^501 + 2*x^498 + 2*x^492 + 2*x^475 + 2*x^472 + 4*x^468 + 2*x^456 + 4*x^444 + 4*x^442 + 2*x^430 + 2*x^420 + 4*x^401 + 4*x^375 + 8*x^353 + 4*x^329 + 8*x^327 + 2*x^311 + 4*x^303 + 6*x^296 + 2*x^293 + 4*x^263 + 2*x^251 + 4*x^220 + 8*x^205 + 4*x^196 + 4*x^194 + 8*x^179 + 8*x^148 + 4*x^124 + 4*x^15 + 8

分解得p，q：

之后分解即可。

test demo：

bits = 256
p = getPrime(bits)
q = getPrime(bits)
index = 0
while True:
    p = next_prime(p)
    q = next_prime(q)
    n = p * q
    for prime in primes:
        tmp = sys_convert(n, prime, max=primes[-1]).count('0')/len(sys_convert(n, prime, max=primes[-1]))
        if tmp > 0.8:
            print('p =', p)
            print('q =', q)
            print('n =', n)
            print('density =', tmp)
            print('n base on %d = %s' % (prime, sys_convert(n, prime, max=primes[-1])))
            exit()

    index += 1
    if index % 100 == 0:
        print('%d rounds' % (index//100))
        p = getPrime(bits)
        q = getPrime(bits)

emmmmm，然而找上万轮也没找到2333，本来还想着可以拿来出题的233

abbout

这个题提醒了我密码中也要善用数学归纳法。。。

通过输出其实可以发现每个分数的倒数的绝对值的整数部分即是对应的字符的ascii值，依次写出逆函数，则有exp如下：

import string
import random
from fractions import Fraction as frac


flag_min = 48
flag_max = 125


def re_me(fini):
    res = ''
    den, num = fini[0], fini[1]
    reducer = 0
    while num != 0:
        char = int(den / num)
        res += chr(char)
        tmp = frac(den, num) - char
        reducer += 1
        den, num = tmp.denominator * reducer, tmp.numerator

    return res


def re_you(fini):
    res = ''
    den, num = fini[0], fini[1]
    reducer = -1
    while num != 0:
        char = abs(round(den / num))
        res += chr(char)
        tmp = frac(den, num) - char
        reducer *= -1
        den, num = tmp.denominator * reducer, tmp.numerator
    return res


def re_us(fini):
    res = ''
    den, num = fini[0], fini[1]
    while num != 0:
        char = abs(round(den / num))
        res += chr(char)
        tmp = frac(den, num) - char
        den, num = tmp.denominator, tmp.numerator
    return res


enc = [
    (4874974328610108385835995981839358584964018454799387862, 72744608672130404216404640268150609115102538654479393)
    ,
    (39640220997840521464725453281273913920171987264976009809, 366968282179507143583456804992018400453304099650742276)
    ,
    (145338791483840102508854650881795321139259790204977, 1529712573230983998328149700664285268430918011078)
    ,
    (84704403065477663839636886654846156888046890191627, 717773708720775877427974283328022404459326394028)
    ,
    (287605888305597385307725138275886061497915866633976011, 8712550395581704680675139804565590824398265004367939)]


flag = []
# me
flag.append(re_me(enc[2]))
flag.append(re_me(enc[3]))

# you
flag.append(re_you(enc[1]))
flag.append(re_you(enc[4]))

# us
flag.append(re_us(enc[0]))
print(flag)

以me函数分析其数学原理，以数列 ${m_{n}}$ 表示明文序列， $l$ 表示明文序列长度，可知对于分数数列 ${a_{n}}$ ，有 $a_{0} = \frac{l - 1}{m_{0}}$ ，之后进行轮操作

$a_{1} = \frac{l - 2}{a_{0} + m_{1}}, \frac{1}{a_{1}} = \frac{l - 1}{(l - 2) m_{0}} + \frac{m_{1}}{l - 2} \Rightarrow \frac{l - 2}{a_{1}} \approx m_{1}$

通过数学归纳法，不难证明对于 $a_{i}$ 均有 $\frac{l - 1 - i}{a_{i}} \approx m_{i}$ ，从而可以迭代求解。

埋个坑，下次用数学归纳法整个数列题玩玩2333

strip

终于用了点分析里的技巧2333，其实也是很常用的技巧，观察数列 ${a_{n}}$ ，可知有 $a_{n} = \frac{6 * a_{n - 1}^{2}}{a_{n - 1}} - \frac{8 a_{n - 1} a_{n - 2}}{a_{n - 3}} \Rightarrow \frac{a_{n}}{a_{n - 1}} = \frac{6 a_{n - 1}}{a_{n - 2}} - \frac{8 a_{n - 2}}{a_{n - 3}}$ 于是设 $b_{i} = \frac{a_{i}}{a_{i - 1}}, i > 1$ ，则有 $b_{n} = 6 b_{n - 1} - 8 b_{n - 2}$ ，待定系数法（有二解，等价）得 $b_{n} - 2 b_{n - 1} = 4 b_{n - 1} - 8 b_{n - 2}$ ，再设 $c_{i} = b_{i} - 2 b_{i - 1}, i > 2$ ，则有 $c_{n} = 4 c_{n - 1}$ ，即 $c_{n} = 4^{n - 3} c_{3}$

则 $c_{n} = 4^{n - 3} * (\frac{24}{2} - \frac{2 * 2}{1}) = 4^{n - 2} * 2$

然后就可以写出a的递推式了：

def b(n):
    if n < 3:
        return a(n)//a(n-1)
    else:
        return 2*b(n-1) + c(n)


def c(n):
    return 2*4**(n-2)


def my_a(n):
    if n <= 2:
        return n
    elif n == 3:
        return 24
    else:
        return my_a(n-1) * b(n)

从而得到n：

for i in range(2, 2**10):
    n = strip(my_a(i))
    if n > enc:
        print('n =', n)
        break

emmmmm但这个n太大了，yafu分解不了，factordb输入都不行，此时想到n其实是 $b_{i}$ 的连乘乘以一个常数再除以 $2^{k}$ ，于是计算k=183315：

bits = bin(my_a(606))[::-1]
for i in range(len(bits)):
    if bits[i] == '1':
        print(i)
        break

$n = \frac{24 * \prod_{i = 4}^{606} b_{i}}{2^{k}} = \frac{3 * \prod_{i = 4}^{606} b_{i}}{2^{k - 3}}$

计算phi，考虑到n太大了。。所以考虑使用n的因子 $a (x), x < 606$ 当作模，计算phi如下（获得n的所有素因子，其中get_factor_list函数是调用的factordb获得的素因子）：

def get_phi_a(index, return_list=False):
    primes = []
    for i in tqdm(range(4, index+1)):
        tmp = strip(b(i))
        if isPrime(tmp):
            primes.append(tmp)
        else:
            factors = get_factor_list(tmp)
            for factor in factors:
                primes.append(factor)

    if return_list:
        return set(primes)

    phi = 2
    factor_dict = {}
    for key in primes:
        factor_dict[key] = factor_dict.get(key, 0) + 1
    for key in factor_dict.keys():
        if factor_dict[key] == 1:
            phi *= int(key) - 1
        else:
            phi *= int(key) - 1
            phi *= pow(key, factor_dict[key]-1)
    return phi

其中index即为 $n_{l o w} = a (x)$ 中的x

然后思路有两种，一种是直接找到足够大的index，另一种是找两个大点的素数然后CRT，遗憾的是index到200的时候仍然无法获得flag，于是改为第二种：

factors_list = list(get_phi_a(606, True))
print(len(factors_list))
e = 0x10001 + 2
for prime in itertools.combinations(factors_list, 2):
    p = prime[0]
    q = prime[1]
    n = p * q
    phi = (p-1) * (q-1)
    m = pow(enc, inverse(e, phi), n)
    flag = long_to_bytes(m)
    if b'CCTF' in flag:
        print(flag)
        break

得到所有prime大概需要7，8分钟，最终得到flag：

N1CTF 2020

easy RSA

本题有两层，一层是分解n，一层是恢复LWE，恢复LWE相对简单，与攻击GGH差不多，直接LLL后CVP即可，难点在于利用p，q生成弱点分解n。

$f (x) = a_{4} x^{4} + a_{3} x^{3} + a_{2} x^{2} + a_{1} x + a_{0}$

$g (x) = b_{4} x^{4} + b_{3} x^{3} + b_{2} x^{2} + b_{1} x + b_{0}$

$x_{0} = 3^{66}$ ， p为 $f (x_{0})$ 最大的根，q为 $g (x_{0})$ 最大的根

则有 $f (x_{0}) g (x_{0}) = k n$ ，k相对于n较小，设 $f (x) g (x) = \sum_{i = 0}^{8} t_{i} x^{i}$

即有 $\sum_{i = 0}^{8} t_{i} x_{0}^{i} - k n = 0$ ，故可构造格：

$[\begin{matrix} 1 & 0 & \dots & 0 & 0 & x^{8} \\ 0 & 1 & \dots & 0 & 0 & x^{7} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & 0 & x \\ 0 & 0 & \dots & 0 & 1 & 1 \\ 0 & 0 & \dots & 0 & 0 & N \end{matrix}]$

目标向量为 $(t_{8}, t_{7}, \dots, t_{0}, 0)$ ，由于 $t_{r} = \sum_{i + j = r} a_{i} * b_{j}$ ，故 $t_{i} < 2^{64} * (5 - | i - 4 |)$

则其范数上界为 $\sqrt{\sum_{i = 0}^{8} (2^{64} * (5 - | i - 4 |))^{2}} < 2^{68}$

则由Minkowski定理得 $2^{68} < n^{\frac{1}{2}} d e t (L)^{\frac{1}{n}} = \sqrt{10} N^{\frac{1}{10}}$

而 $\sqrt{10} N^{\frac{1}{10}} > 2^{71}$

故知Minkowski上界满足，但仍需要满足格内各基向量均大于目标向量范数，即需要在原有矩阵上乘均衡系数T，可知 $2^{68} < T$

构造代码如下：

M = matrix(ZZ, 10, 10)

x = 3 ** 66
balance = 2 ** 68
for i in range(9):
    M[i, i] = 1
    M[i, 9] = (x ** (8-i)) * balance

M[9, 9] = n * balance
L = M.LLL()
print(L[0])

得到解向量后，直接多项式分解即可得到 $a_{i}, b_{i}$ ，则可分解n，分解部分完整代码如下：

# factor n

# calc the bound
bound = 0
for i in range(9):
    bound += (2**64 * (5 - abs(i - 4)))**2

# construct the Lattice
M = matrix(ZZ, 10, 10)
x = 3 ** 66
balance = 2 ** int(iroot(int(bound), int(2))[0]).bit_length()
for i in range(9):
    M[i, i] = 1
    M[i, 9] = (x ** (8-i)) * balance

M[9, 9] = n * balance
L = M.LLL()[0]

P.<y> = PolynomialRing(ZZ)
f = 0
for i in range(9):
    f += int(L[i]) * (y**(8-i))

factors = f.factor()
a = list(factors[0][0])
b = list(factors[1][0])

def recover_random_prime(tmp):
    total = 0
    for i in range(5):
        total += x ** i * tmp[i]
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])

p = recover_random_prime(a)
q = recover_random_prime(b)
assert n == p * q
e = 127
d = inverse(e, (p-1) * (q-1))
result = []
for c in enc:
    result.append(pow(c, d, n))

接下来恢复LWE即可，考虑 $A = [A_{1}, A_{2}, \dots, A_{127}]$ ， $A_{i}$ 为A的列向量，已知有 $A_{i} m_{i} + b_{i} \equiv r_{i} \mod n$ ，其中 $m_{i}$ 为flag第i个字符对应数字， $b_{i}$ 为所加小偏移向量分量， $r_{i}$ 为通过分解n恢复的向量，n即模数152989197224467。

可知有 $A_{i} m_{i} + b_{i} = r_{i} + k n \Rightarrow A_{i} m_{i} - k n = r_{i} - b_{i}$ ，故考虑构造格使 $(r_{1}, r_{2},, r_{s})$ 向量在其上，再通过CVP寻找到 $(r_{1} - b_{1}, r_{2} - b_{2}, \dots, r_{s} - b_{s})$ ，从而恢复出flag。

故构造格：

$[\begin{matrix} n & 0 & \dots & 0 \\ 0 & n & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & n \\ A_{11} & A_{21} & \dots & A_{s 1} \\ A_{12} & A_{22} & \dots & A_{s 2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ A_{1 s} & A_{2 s} & \dots & A_{s s} \end{matrix}]$

利用此格的正交基寻找CVP，改变s，发现 $s > 50$ 时，可以找到正确的向量，从而恢复flag，完整exp如下：

from Crypto.Util.number import *
from gmpy2 import *
from sage.modules.free_module_integer import IntegerLattice
import numpy as np

enc =
n = 

# factor n

# calc the bound
bound = 0
for i in range(9):
    bound += (2**64 * (5 - abs(i - 4)))**2

# construct the Lattice
M = matrix(ZZ, 10, 10)
x = 3 ** 66
balance = 2 ** int(iroot(int(bound), int(2))[0]).bit_length()
for i in range(9):
    M[i, i] = 1
    M[i, 9] = (x ** (8-i)) * balance

M[9, 9] = n * balance
L = M.LLL()[0]

P.<y> = PolynomialRing(ZZ)
f = 0
for i in range(9):
    f += int(L[i]) * (y**(8-i))

factors = f.factor()
a = list(factors[0][0])
b = list(factors[1][0])

def recover_random_prime(tmp):
    total = 0
    for i in range(5):
        total += x ** i * tmp[i]
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])

p = recover_random_prime(a)
q = recover_random_prime(b)
assert n == p * q
print('got factors')

e = 127
d = inverse(e, (p - 1) * (q - 1))
result = []
for c in enc:
    result.append(pow(c, d, n))


# recover LWE
A = np.ndarray.tolist(np.load('A.npy'))
module = 152989197224467


def CVP(lattice, target):
    gram = lattice.gram_schmidt()[0]
    t = target
    for i in reversed(range(lattice.nrows())):
        c = ((t * gram[i]) / (gram[i] * gram[i])).round()
        t -= lattice[i] * c
    return target - t


row = 51
column = 43
M = matrix(ZZ, row + column, row)

for i in range(row):
    for j in range(column):
        M[row + j, i] = A[i][j]
    M[i, i] = module

lattice = IntegerLattice(M, lll_reduce=True)
target = vector(ZZ, result[:row])
res = CVP(lattice.reduced_basis, target)
print('got CVP')
R = IntegerModRing(module)
M = Matrix(R, A[:row])

flag = M.solve_right(res)

print("".join([chr(i) for i in flag]))