crypto的挨打之路（退役版） | T5uppari = 蒟蒻的入土史

2023.1.30，退役篇，最后随缘更新 20 题了

# 0x0B from rec matrix_e 9.13

附件

#!/usr/bin/env sage
# Problem by rec, with nothing.
import os
import secret
import hashlib
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad

LEN = 32

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

def challenge(m: bytes, pbits: int, level: int=0):
    p = getPrime(pbits)
    M = random_matrix(GF(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M

    return {"p": p, "M": M.list(), "c": c.list()}

args = {
    "chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00
    },
    "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01
    },
    "chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10
    }
}

out = dict()
enc = pad(secret.flag, LEN)
for i in range(3):
    out[f"chall{i+1}"] = challenge(**args[f"chall{i+1}"])
    enc = xor(enc, hashlib.sha512(args[f"chall{i+1}"]["m"]).digest())
out["enc"] = enc.hex()
with open('output.txt', 'w') as f:
    f.write(f"{out = }")

总能从 rec 大佬的题里学到很多！

题目分为三部分，都是涉及到矩阵乘法，一部分一部分分别看吧

第一部分，32 长度的向量 m 乘上 32*32 的矩阵 M 得到 32 长度的向量 c

没啥说法，直接矩阵求逆即可

#chall1
data = {"p": p, "M": M.list(), "c": c.list()}
p = data['p']
M = data['M']
c = data['c']
c = vector(GF(p),c)
M = [M[i:i + 32] for i in range(0,len(M),32)]
M = matrix(GF(p),M)

m = c * M.inverse()
print(m)
print(bytes(m))
#(217, 220, 57, 174, 24, 89, 132, 130, 40, 56, 42, 134, 44, 31, 52, 244, 80, 57, 169, 240, 71, 19, 73, 92, 142, 118, 147, 184, 215, 105, 6, 40)
#d9dc39ae1859848228382a862c1f34f45039a9f04713495c8e7693b8d7690628

第二部分，32 长度的向量 m 乘上 32*31 的矩阵 M 得到 31 长度的向量 c

只差了一位，可以直接爆破向量 m 的最后一位，在 (0,256) 的范围，之后将这一位所作的运算减到向量 c 里面，再对 31*31 的矩阵求逆，用得到的向量 m 是否都为 (0,256) 来进行判断即可

#chall2
from tqdm import tqdm
data = {"p": p, "M": M.list(), "c": c.list()}
p = data['p']
M = data['M']
c = data['c']
M = [M[i:i + 31] for i in range(0,len(M),31)]
mat = matrix(GF(p),M[:-1])
for key in tqdm(range(256)):
    M = data['M']
    cc = data['c']
    M = [M[i:i + 31] for i in range(0,len(M),31)]
    cc = vector(GF(p),cc)
    cc = cc - key * vector(GF(p),M[-1])
    M = matrix(GF(p),M[:-1])
    m = cc * M.inverse()
    numlist = list(m) + [key]
    if all(num <= 256 for num in numlist):
        #print(numlist,cc,M)
        print(bytes(numlist).hex())
        #966865a39e934abd1bf22cf32aa279702add8ac172bdfc252dfc6b17b418ee47

第三部分，32 长度的向量 m 乘上 32*16 的矩阵 M 得到 16 长度的向量 c

有点像背包算法，将等式写出可以发现 $m_1a_1+m_2a_2+kp-c=0$ ，m 的范围在 (0,256)，p 和 c 已知，m 很小，构造 49*49 的格子得到

$\begin{bmatrix} {m}&k&1 \end{bmatrix} \begin{bmatrix} 1&M& \\ &p& \\ &c&1 \end{bmatrix} \begin{bmatrix} m&0&1 \end{bmatrix}$

M 为题目给出的 32*16 的矩阵，p 放置斜对角，c 放最后一行，这样右边可以得到 0，格基规约后就可以得到我们想要的向量 $(m,0,1)$

data = {"p": p, "M": M.list(), "c": c.list()}
p = data['p']
M = data['M']
c = data['c']
print(len(c))
m = list(bytes.fromhex('9cc4498a21d9bebfd9798205f21d620dc86278e475b31cd01c8fae85c39028a9'))
M = [M[i:i + 16] for i in range(0,len(M),16)]
mat = [[0 for _ in range(49)] for _ in range(49)]
for i in range(32):
    mat[i][i] = 1
    for j in range(32,48):
        mat[i][j] = M[i][j - 32]
for i in range(32,48):
    mat[i][i] = p
    mat[-1][i] = c[i - 32]
mat[-1][-1] = 1
mat = matrix(ZZ,mat)
ans = mat.LLL()[0].list()
print(mat.LLL())
m = [int(abs(i)) for i in ans[:32]]
print(bytes(m).hex())
#1190f7db6972605611dc8c28672e66c201369a8f467391d3149d638397274a6d

格基规约第一行就是向量 $(m,0,1)$

最后按照题目逻辑 sha512 完了异或即可

import hashlib
from functools import reduce
def hashkey(m):
    return hashlib.sha512(bytes.fromhex(m)).digest()
def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])
key1 = 'd9dc39ae1859848228382a862c1f34f45039a9f04713495c8e7693b8d7690628'
key2 = '966865a39e934abd1bf22cf32aa279702add8ac172bdfc252dfc6b17b418ee47'
key3 = '1190f7db6972605611dc8c28672e66c201369a8f467391d3149d638397274a6d'
key1,key2,key3 = hashkey(key1),hashkey(key2),hashkey(key3)
enc = '72c0e8ef53c726969a91368ca600a081f38f5cfaa1d0669d9049f278fb2f0fb4f36dced86bf9b7e9ef59af082cc5a5b2458cae490ab23c0c8c5b9361499ae2e2'
enc = bytes.fromhex(enc)
flag = reduce(xor,[key1,key2,key3,enc])
print(flag)

# 0x0A 2023bluehat DHRSA 8.27

附件

# sage
from sage.all import *
from Crypto.Util.number import getPrime,getStrongPrime, isPrime, bytes_to_long
from secret import r,g
from secret import flag

assert r.bit_length() == 512 and isPrime(r)
FLAG = bytes_to_long(flag)

def gen_DH_key(g,r):
    x = randint(2,r-1)
    return x, pow(g,x,r)

def gen_RSA_parameters(g,r):
    main_key = gen_DH_key(g,r)
    sub_key = gen_DH_key(g,r)
    x, X = main_key
    w, W = sub_key
    print(f"[+] Public DH Keys { X = }")
    print(f"[+] Public DH Keys { W = }")
    while True:
        c, C = gen_DH_key(g,r)
        t1 = randint(0,1)
        t2 = randint(0,1)
        p = ZZ(C * W^t1 * pow(X, c, r) % r)
        if not is_prime(p):
            continue
        q = ZZ(pow(W, -t2, r) * pow(X, -c, r) % r)
        if not is_prime(q):
            print(f"[+] Try {c ,C}")
            continue
        return p,q
    
p, q = gen_RSA_parameters(g,r)
n = p*q
e = 65537
c = pow(FLAG,e,n)
print(f"{ c = }")
print(f"{ n = }")

观察题目，变量都是通过以下函数生成

1
2
3

def gen_DH_key(g,r):
    x = randint(2,r-1)
    return x, pow(g,x,r)

通过后面的 try 给出的 c，有式子 $C \equiv g^c \bmod n$ 可以进行尝试构造格子，只需找到一组合适的系数 $k$ 使得 $\sum_{i=1}^nk_ic_i=0$ ，其中系数 k 有正有负。这样就有 $g^{\sum_{i=1}^nk_ic_i}=1 \bmod n$ ，同过格基规约可以找到我们想要的系数，格子如下

$\begin{bmatrix} {k_1}&{k_2}&{k_3} \end{bmatrix} \begin{bmatrix} 1&0&0&Nc_1\\ 0&1&0&Nc_2\\ 0&0&1&Nc_3\\ \end{bmatrix} \begin{bmatrix} {k_1}&{k_2}&{k_3}&0 \end{bmatrix}$

from sage.all import *
from functools import reduce
data = open('out.txt','r').read().splitlines()[2:-2]
ee = []
cc = []
for i in data:
    line = i.replace('[+] Try (','').replace(')','').split(', ')
    e,c = list(map(int,line))
    ee.append(e)
    cc.append(c)
l = len(ee)
pad = 2 ** 12

mat = [[0 for _ in range(l + 1)] for _ in range(l)]
for i in range(l):
    mat[i][i] = 1
    mat[i][-1] = pad * ee[i]
mat = matrix(ZZ,mat)
# print(mat)
print(mat.LLL())
kk = list(mat.LLL()[0])[:-1]
mul = lambda x,y:x * y
ans = sum([k * e for k,e in zip(kk,ee)])
assert ans == 0

得到系数之后，下一步将其放在指数位上，由于没有取模，直接运算的指数中有正有负，得到的就不是一个整数，会得到结果 $\frac{g^{k_ic_i}}{g^{k_jc_j}}=1 \bmod n$ ，也就是说，分子分母做差就是 k 倍的 n，得到两组进行 GCD 即可得到我们的模数，也就是我们的 r。

l = len(ee)
pad = 2 ** 10

mat = [[0 for _ in range(l + 1)] for _ in range(l)]
for i in range(l):
    mat[i][i] = 1
    mat[i][-1] = pad * ee[i]
mat = matrix(ZZ,mat)

result = mat.LLL()
kk1 = list(result[0])[:-1]
kk2 = list(result[1])[:-1]
mul = lambda x,y:x * y
ans1 = sum([k * e for k,e in zip(kk1,ee)])
assert ans1 == 0
ans2 = sum([k * e for k,e in zip(kk2,ee)])
assert ans2 == 0
tmp1 = reduce(mul,[ZZ(C) ** k for C,k in zip(cc,kk1)])
kr1 = tmp1.numer() - tmp1.denom()
tmp2 = reduce(mul,[ZZ(C) ** k for C,k in zip(cc,kk2)])
kr2 = tmp2.numer() - tmp2.denom()
r = GCD(kr1,kr2)
print(r,isPrime(r))
#10667924450645948100608927157603781268991945924055943816082403476371801785989561454936076097627912279097114498936308342036099904242687703932444772733243819 1

得到 r 之后可以共模攻击得到 g，取两组没有公约数的 e 即可，这样可以得到 g。得到的 r 发现 r-1 光滑，也就是说指数位可解

之后分析 p 和 q 的生成，可以看出

$p=(CW^{t_1}X^c) \bmod r \\ q=(W^{-t_2}X^{-c}) \bmod r \\ n=p\times q= CW^{t_1-t_2} \bmod r$

其中 t1-t2 的范围只有三个值 -1,0,1 ，这样可以得到三个 C 的可能值，逐个尝试即可，之后按照原逻辑生成即可。完整 exp 为

from sage.all import *
from functools import reduce
from Crypto.Util.number import *
X = 197551296081022143608034360606381334253374533627365455002683616928330857539205836504075700389569213696043700490195977045586318090211726350917451410932216
W = 10625560347436147537644301075885059900758953251551866239435327407977591190018531918316486861730777808988185029637608372445416280896280058313924537678128258
n = 66022752859576751705544115674843820574619778139841743306742674741819040147745776264697779394213058328572691946505564202779552568613562176486470653760142864852745249430164256770469301179840812051842363261404790355057115296671805975126795017665392798621718740402876024901551851638786170466127104615340863081593
enc = 61040814411609979711931510878805548760848686739454567580358315369154260598969544907138563610735920809370306294050956464828615417082277087799410050319871691154003766481799397897519555113273982347768485719165972634089532894585256662433949694618032747408071953491187718726218120284389638124624152241321006634774
data = open('out.txt','r').read().splitlines()[2:-2]
ee = []
cc = []
for i in data:
    line = i.replace('[+] Try (','').replace(')','').split(', ')
    e,c = list(map(int,line))
    ee.append(e)
    cc.append(c)
l = len(ee)
pad = 2 ** 10

mat = [[0 for _ in range(l + 1)] for _ in range(l)]
for i in range(l):
    mat[i][i] = 1
    mat[i][-1] = pad * ee[i]
mat = matrix(ZZ,mat)

result = mat.LLL()
kk1 = list(result[0])[:-1]
kk2 = list(result[1])[:-1]
mul = lambda x,y:x * y
ans1 = sum([k * e for k,e in zip(kk1,ee)])
assert ans1 == 0
ans2 = sum([k * e for k,e in zip(kk2,ee)])
assert ans2 == 0
tmp1 = reduce(mul,[ZZ(C) ** k for C,k in zip(cc,kk1)])
kr1 = tmp1.numer() - tmp1.denom()
tmp2 = reduce(mul,[ZZ(C) ** k for C,k in zip(cc,kk2)])
kr2 = tmp2.numer() - tmp2.denom()
r = GCD(kr1,kr2)
# print(r,isPrime(r))
s,s1,s2 = xgcd(ee[1],ee[2])
assert s == 1
g = pow(cc[1],s1,r) * pow(cc[2],s2,r) % r
C1 = int(n * pow(W,1,r) % r)
C2 = int(n * pow(W,0,r) % r)
C3 = int(n * pow(W,-1,r) % r)
for C in [C1,C2,C3]:
    c = discrete_log(Zmod(r)(C),Zmod(r)(g))
    print(f'Try c:{c}')
    p1 = int((C * W ** 0 * pow(X, c, r) % r))
    p2 = int((C * W ** 1 * pow(X, c, r) % r))
    for p in [p1,p2]:
        if int(n) % int(p) != 0:
            continue
        q = int(n // p)
        assert p * q == n
        phi = int((p - 1) * (q - 1))
        d = inverse_mod(65537,phi)
        m = pow(enc,d,n)
        assert pow(m,0x10001,n) == enc
        print(long_to_bytes(int(m)))
        break

# 0x09 2023HWS Random 7.15

附件

from os import urandom
from gmpy2 import next_prime
from random import randint
from functools import reduce
from Crypto.Util.number import bytes_to_long
from secret import flag

assert flag[:4] == b'flag'

def padding(m, length):
    return m + urandom((length >> 3) - len(m))

def generate_p(base):
    return next_prime(base + randint(1, 500000))

def generate_e():
    return reduce(lambda x, y: x * y, [randint(1, 100) for _ in range(randint(2, 5))])

def generate_pubkey():
    base = 1 << randint(128, 256)
    
    n = reduce(lambda x, y: x * y, [generate_p(base) ** randint(1, 5) for _ in range(randint(2, 10))])
    e = generate_e()
    
    return (n, e)

n, e = generate_pubkey()

m = bytes_to_long(padding(flag, n.bit_length()))
assert m < n
c = pow(m, e, n)

with open ("./data.txt","w") as f:
    f.write("n = {}\ne = {}\nc = {}".format(n, e, c))
    f.close()

算是我见过最恶心的 AMM 了。

首先要先分解 n，观察 n 的生成函数，可以看到是一个公共的 base，通过这个 base 来生成素数 p，偏差只有 randint(1,500000) ，素数 p 还有一个 randint(1,5) 的次方，综上 n 的分解应该为

$n=\prod_{i=1}^{n}(p+k_i)^{e_i}$

尝试直接对 n 开 es 次方，es 为 $e_i$ 的乘积，如果 es 是正确的，那得到开方结果的高位应该是 $2^i$ 形式。所以直接用一个 table 变量打表出范围内 $2^i$ 的所有值，之后进行爆破就可以得到可能满足条件的所有 base

import gmpy2
from Crypto.Util.number import *
from tqdm import tqdm
from os import urandom

n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
e = 57564
c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702
table = {}
bases = []
ee = []
for i in range(128,257):
    base = 2 ** i
    idx,data = i,str(base)[:30]
    table[data] = idx
# print(table)
for es in range(2,100):
    tmp = gmpy2.iroot(n,es)
    cnt = str(tmp[0])[:30]
    try:
        print(table[cnt],es)
        bases.append(table[cnt])
        ee.append(es)
        # print(es)
    except:
        pass
#bases = [250, 210, 175, 150]
#es = [21, 25, 30, 35]

这样就得到了所有可能的 base，之后再对这些 base 进行爆破，得到了正确的 base，也就成功地将 n 进行了分解

base = 47890485652059026823698344598447161988085597568237568
primes = []
for i in tqdm(range(500000)):
    p = base + i
    if n % p == 0:
        primes.append(p)
print(primes)
fac = []
for p in primes:
    for i in range(6,0,-1):
        if n % (p ** i) == 0:
            fac.append((p,i))
            break
print(fac)
#[(47890485652059026823698344598447161988085597568251161, 5), (47890485652059026823698344598447161988085597568297951, 4), (47890485652059026823698344598447161988085597568338059, 3), (47890485652059026823698344598447161988085597568363667, 4), (47890485652059026823698344598447161988085597568398337, 3), (47890485652059026823698344598447161988085597568433917, 5), (47890485652059026823698344598447161988085597568484111, 1), (47890485652059026823698344598447161988085597568667099, 2), (47890485652059026823698344598447161988085597568729849, 3)]

得到了 n 的分解之后，观察 e 的生成，都是一些小因数的乘积，肯定会有模不互素。意思是要批量 amm，而且素数都有次方，还得 hensel lift。在 sage 里面发现一个很厉害的有限域开方函数 Zmod(p ** i)(c).nth_root(e,all=True) ，也自带了 hensel lift，这个函数跑出来的结果就是 c 在 $p^i$ 的有限域下开 e 次方的列表集合，功能非常强大。用这个函数打这个题也很快了，但是跑一次 flag 得花半个钟头

from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
import itertools


n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
e = 57564
c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702

ps = [(47890485652059026823698344598447161988085597568251161, 5), (47890485652059026823698344598447161988085597568297951, 4), (47890485652059026823698344598447161988085597568338059, 3), (47890485652059026823698344598447161988085597568363667, 4), (47890485652059026823698344598447161988085597568398337, 3), (47890485652059026823698344598447161988085597568433917, 5), (47890485652059026823698344598447161988085597568484111, 1), (47890485652059026823698344598447161988085597568667099, 2), (47890485652059026823698344598447161988085597568729849, 3)]
mods = [int(p ** k) for p,k in ps]
phi = 1
for p,ee in ps:
    if ee != 1:
        phi *= p ** (ee - 1) * (p - 1)
    else:
        phi *= (p - 1)
eps = [GCD(e,p - 1) for p,_ in ps]


ee = e // 108
d = inverse_mod(ee,phi)
c = int(pow(c,d,n))
e = 108
root = Zmod(int(ps[0][0]) ** ps[0][1])(c).nth_root(108,all=True)
print(root)
roots = []
for i in tqdm(range(9)):
    root = Zmod(ps[i][0] ** ps[i][1])(c).nth_root(108,all=True)
    roots.append(root)
# print(roots)
for i in tqdm(itertools.product(*roots,repeat=1)):
    ai = list(map(int,i))
    m = CRT_list(ai,mods)
    flag = long_to_bytes(int(m))
    if b'flag' in flag:
        print(flag)
        break

# 0x08 2023ichunqiu cisticola 5.22

附件

#!/usr/bin/env sage
# Problem by rec, with nothing.
import Q
import secret
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key = os.urandom(16)
cipher = AES.new(key=key, iv=bytes(range(16)), mode=AES.MODE_CBC)
enc = cipher.encrypt(pad(secret.flag, 16)).hex()
print(f"{enc = }")

p = 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942484012852921804371007968007851081933599
R.<x> = PolynomialRing(GF(p))
Q = R(Q.Q)

t = 17
pos = random.sample(range(600), t) + [600]
poly = [int(os.urandom(16).hex(), 16) for _ in range(t)] + [int(key.hex(), 16)]
hint = 0
for i in range(t+1):
    hint = (hint + poly[i]*x^pos[i]) % Q
print(f"{pos = }\n{hint = }")

抽代的内容了，研究的不多，比较粗俗的理解就是不涉及进位的进制，例如 $x^2-1 \bmod (p=17) = x^2 + 16 \bmod (p = 17)$

这题最后是用非预期做出来的，非预期的方法也是值得学习的。

首先仔细观察 hint 的生成，poly 的量为待求量， $hint = \sum(poly_i \times x^{pos_i}) \bmod Q$ ，其中 Q，pos 是已知量，poly 是待求量但是相对模数 $p$ 来说较小。预期解应该是找关系打格子，可惜才疏学浅。

仔细分析可得，Q 的最高位是系数为 1 的 $x^{430}$ ，即后续的 pos 若小于 430，则模除 $Q$ 之后还是原始值，若大于则会发生复杂的取模运算。分析 hint 的组成，在每一项中 $hint_{i}=poly_{i} \times x^{pos_i} \bmod Q$ ，运算的优先级可以这样考虑 $hint_{i}=poly_{i} \times (x^{pos_i} \bmod Q)$ ，则括号内的内容就是可以运算的量，hint 的长度为 430，pos 的长度为 18，也就是说有 18 个变量，430 个同余式，解方程就好了。

from Crypto.Cipher import AES
from Crypto.Util.number import *
Q = 
p = 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942484012852921804371007968007851081933599
R.<x> = PolynomialRing(GF(p))
Q = R(Q)
enc = 'e086deeb9f060c014867c5adbd1ee1b449193b6e6177f58a36948282e1728f3b529b2def3c39f69c7a9001b4cac4d1d5'
pos = [477, 491, 210, 515, 150, 142, 561, 5, 475, 329, 598, 274, 241, 310, 108, 483, 181, 600]
hint = 
mat = [[0 for _ in range(430)] for _ in range(18)]
# print(Q)
PR.<a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17> = PolynomialRing(GF(p))
a = [a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17]

for i,pp in enumerate(pos):
    tmp = list(x ** pp % Q)
    for j,t in enumerate(tmp):
        mat[i][j] = a[i] * t
# print(mat) 
mat.append(list(hint))
ff = []
for i in range(430):
    tmp = 0
    for j in range(18):
        tmp += mat[j][i]
    tmp -= mat[-1][i]
    ff.append(tmp)
print(ff)
I = Ideal(ff)
print(I.groebner_basis())
# [a0 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942251245947429682847423244896114784571840, a1 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942155951579510371133104055248512821058402, a2 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942333546689677540574648441829120164200263, a3 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942419856042732508027928937880966528965678, a4 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942477242440201679929560431846449850728314, a5 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942402850007349508639046549625566370735523, a6 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942338856934358003057852501739714995242544, a7 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942188922148901513137769699923520143568903, a8 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942202100080454223166267793321382393527839, a9 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942444212108989123403851398643912126051811, a10 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942356103439790326992493002039390602461809, a11 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942160739218709559983956317741927065496004, a12 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942411486325717861983300194796811016589910, a13 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942343857452774108124499344398633347051679, a14 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942198611477667309363260275106661907181321, a15 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942307880784830630882477073480841448524000, a16 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942193549940805400643378549025789266511646, a17 + 1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942208402895698278177510126987163765863091]
key = (-1439830214451992034013504859825496348425599138552815552028441481225682951310010651304957987750558339128649248859043607574873717185051113737355019502086518775325158336557488060325293103679742942208402895698278177510126987163765863091) % p
key = long_to_bytes(int(key))
enc = bytes.fromhex(enc)
cipher = AES.new(key=key, iv=bytes(range(16)), mode=AES.MODE_CBC)
flag = cipher.decrypt(enc)
print(flag)

# 0x07 2023ichunqiu ecdsa 5.22

附件

import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor
import secret

p = getPrime(256)
gen = lambda: p + getPrime(16)
pad = lambda m: m + os.urandom(32 - len(m) % 32)

key = os.urandom(30)
sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)
sig1 = sk.sign(data=b'This is the first message.', k=gen()).hex()
sig2 = sk.sign(data=b'Here is another message.', k=gen()).hex()
enc = xor(hashlib.sha512(key).digest(), pad(secret.flag)).hex()

print(f"{sig1 = }\n{sig2 = }\n{enc = }")
'''
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
'''

用的第三方包 ecdsa 来做的，首先要清楚签名的流程。

观察变量定义的代码

sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)

说明其中私钥用的是 key , 曲线用的是固定的曲线 ecdsa.SECP256k1 。其中用 ecdsa 签名的曲线都是相对固定的，对应的参数也都可以找到。以下是一个签名的流程

#sage
import hashlib
from Crypto.Util.number import *
from tqdm import tqdm
from Crypto.Util.strxor import strxor as xor
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a,b = 0,7
E = EllipticCurve(Zmod(p),[a,b])
_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
_Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = E(_Gx,_Gy)
n = int(G.order())
key = b'\r\x10\x12\xc9\xdc=_\x17\xf9~^\x94\x88\xc9)2Q)\xf1\xf6\xb7n\x85\xe6\xf8j\xa8\xdb\xb4\xe7'
d = bytes_to_long(key)
k = 87388283475313773609267381590151961688122112605990157606506013532563806668001
msg1 = b'This is the first message.'
msg2 = b'Here is another message.'
z = int(hashlib.sha1(msg1).hexdigest(),16)
K = k * G
kx,ky,_ = K
r = int(kx)
s = inverse_mod(k,n) * (z + r * d) % n
print(hex(r)[2:] + hex(s)[2:])
#21f3a9a4c280a50b7dc2aac6d21562744445853396833d740260ba704d256bfc69cac9a4714ce22f319adc0d4ba78bc9807289b77193149fb935786af9448844

#python
import os
import ecdsa
import hashlib
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor as xor
from pwn import *
# import secret
flag = b'flag{1234567890123123456423423321454}'
# p = getPrime(256)
# gen = lambda: p + getPrime(16)
# pad = lambda m: m + os.urandom(32 - len(m) % 32)
p = 87388283475313773609267381590151961688122112605990157606506013532563806668001

key = b'\r\x10\x12\xc9\xdc=_\x17\xf9~^\x94\x88\xc9)2Q)\xf1\xf6\xb7n\x85\xe6\xf8j\xa8\xdb\xb4\xe7'
# print(hashlib.sha512(key).digest())
# print(pad(flag))
sk = ecdsa.SigningKey.from_secret_exponent(
    secexp=bytes_to_long(key),
    curve=ecdsa.SECP256k1
)
sig1 = sk.sign(data=b'This is the first message.', k=p).hex()
sig2 = sk.sign(data=b'Here is another message.', k=p).hex()


print(f"{sig1 = }\n{sig2 = }")
#sig1 = '21f3a9a4c280a50b7dc2aac6d21562744445853396833d740260ba704d256bfc69cac9a4714ce22f319adc0d4ba78bc9807289b77193149fb935786af9448844'

可以看出，自己签名和第三方包签名是一致的，分别解释一下就是

参数	含义
k	随机整数 $k \in [1,n]$ ，用于计算 $P = kG = (x,y)$
G	对应曲线中的基点
n	基点 G 的阶
d	私钥
z	$Hash(msg)$ ，其中 hash 签名算法根据具体的曲线算法而定
r,s	签名的结果

签名的流程如下

1. 选择一个随机整数 k，计算出 $K = kG$ ，签名 $r$ 即为点 $K$ 的横坐标

2. 计算出 $z=Hash(m)$ ，在本题中用的曲线为 SECP256k1 ，跳转到源码中查看发现 hash 算法是 sha1 ，则得到 z = int(hashlib.sha1(msg1).hexdigest(),16)

3. 计算出 $s=k^{-1}(z+r \times d) \bmod n$

4. 签名值即为 $(r,s)$

在本题中，两个签名所用的私钥 $d$ 是一样的，不同的是随机整数 $k$ ，但是差值不会很大，范围是可以爆破的，理清楚同余式的逻辑之后就很好写 exp

import hashlib
from Crypto.Util.number import *
from tqdm import tqdm
from Crypto.Util.strxor import strxor as xor
# from pwn import xor
import gmpy2
sig1 = '3f4a6f288e35a4397201d246a98c1f9cfa463e67717fbbdcbd26d7fac75f875855455c2bfb355f7f593ffbe4c4bd1fc729cc129976b56905639100c8ac716b37'
sig2 = '9f563b21f0ee31b2f7a1a8c6edc8ff23b63e0a9d5dd4a699ecc3164871b4982df51bb2feb4bc06c578afd21d3e6227231dd5fe1d8440f3dcd025fd3ea68f5516'
enc = 'cc66d251bfa54954890c81dc1c607bae716573949f327db18aa1f4c0f420b8d29dc7e7ff9edb17b90306bd2aa753fc3fd4dafb9cc4b771cbdd79000ef05a40c0'
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
r1,s1 = int(sig1[:64],16),int(sig1[64:],16)
r2,s2 = int(sig2[:64],16),int(sig2[64:],16)
hm1 = int(hashlib.sha1(b'This is the first message.').hexdigest(),16)
hm2 = int(hashlib.sha1(b'Here is another message.').hexdigest(),16)

for t in tqdm(range(-65537,65537)):
    k1 = (hm1 * r2 - hm2 * r1 + s2 * t * r1) * gmpy2.invert(s1 * r2 - s2 * r1,n) % n
    d = (s1 * k1 - hm1) * gmpy2.invert(r1,n) % n
    key = long_to_bytes(d)
    key = hashlib.sha512(key).digest()
    flag = xor(key,bytes.fromhex(enc))
    if b'flag' in flag:
        print(flag)
        break

# 0x06 2023miniL curvesignin 5.11

附件

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

flag = flag.strip(b'miniLctf{').strip(b'}')
flag1 = bytes_to_long(flag[:len(flag)//2])
flag2 = bytes_to_long(flag[len(flag)//2:])

q = getPrime(80)
a,b,c = [random.randrange(1,q-1) for _ in "_what_is_this_equation_?_"][:3]

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q

	x3 = b*inverse(c,q)*t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)

def mul(t, A, B=0):
	if not t: return B
	return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

G = (543964449142803087188784, 288605946000947449279542)
assert G[0] == flag1

Ps = []
ms = [random.randrange(1,q-1) for _ in "welcome_to_xxxctf2023"[:4]] + [flag2]
for m in ms:
	P = mul(m,G)
	Ps.append(P)
print(f'G = {G}\nPs = {Ps}')

'''
G = (543964449142803087188784, 288605946000947449279542)
Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]
'''

首先得通过加法函数推出原曲线，加法函数如下

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q

	x3 = b*inverse(c,q)*t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)

可以看出斜率就是 t，当两个相同的点相加时，切线的斜率为 t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q ，也就是 $\frac{(3cx^2+a)}{(2by)}$ ，由此可推出原曲线的格式为 $by^2=cx^3+ax+d$ ，简化计算可令 $c$ 为 1，其他系数跟着变化即可。

PR.<a,b,d> = PolynomialRing(ZZ)
ff = []
for P in Ps + [G]:
    x,y = P
    f = x ** 3 + a * x + d - b * y ** 2
    ff.append(f)
I = Ideal(ff)
print(I.groebner_basis())
#[a + 1383761324420174433943441, b + 4911310444444537745356422, d + 101839133990109714860886, 5271017285827233379503222]

这样就求出了各个系数，由于 flag2 是作为加密系数，加密方式为 $P=mG$ ，求 m，可以进行一个映射。

我们得到的曲线为 $by^2=x^3+ax+d$ ，稍作变换可写成形如 $y^2=x^3+ax+b$ 的格式，即

$(b^2y)^2=(bx)^3+(ab^2)(bx)+b^3d$

已知的点 P 和点 G 映射到新的曲线上即可，就可以用 sage 中的函数求解系数，完整 exp 如下

from Crypto.Util.number import *
G = (543964449142803087188784, 288605946000947449279542)
Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]
P = Ps[-1]
# PR.<a,b,d> = PolynomialRing(ZZ)
# ff = []
# for P in Ps + [G]:
#     x,y = P
#     f = x ** 3 + a * x + d - b * y ** 2
#     ff.append(f)
# I = Ideal(ff)
# print(I.groebner_basis())
# [a + 1383761324420174433943441, b + 4911310444444537745356422, d + 101839133990109714860886, 5271017285827233379503222]
p = 878502880971205563250537
a = (-1383761324420174433943441) % p
b = (-4911310444444537745356422) % p
d = (-101839133990109714860886) % p
aa = (a * b ** 2) % p
bb = (b ** 3 * d) % p
E = EllipticCurve(Zmod(p),[aa,bb])
flag1 = long_to_bytes(G[0])
xg,yg = G
xp,yp = P
GG = ((xg * b) % p,(yg * b ** 2) % p)
PP = ((xp * b) % p,(yp * b ** 2) % p)
GG = E(GG)
PP = E(PP)
oo = GG.order()
flag2 = GG.discrete_log(PP)
#此处求得的flag2满足mG=P，但是不是我们要求的flag2，需要再算上阶
flag2 += oo
flag2 = long_to_bytes(flag2)
print(flag1 + flag2)

# 0x05 2023nkctf raven 3.28

附件

#!/usr/bin/env sage
# Problem by rec, with a bad raven.
import os, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES

def Raven(n: int, secret: bytes):
    H = lambda x: hashlib.md5(os.urandom(8) + x).digest()

    p = getPrime(728)
    R.<z> = PolynomialRing(GF(p))

    seed = H(secret)
    f = R(
        [bytes_to_long(secret)] + [bytes_to_long(H(seed)) for _ in range(n - 1)]
    )
    x = [getRandomRange(2, p - 1) for _ in range(n)]
    y = [ZZ(f(xi)^2 + getPrime(256)) for xi in x]

    pairs = list(zip(x, y))
    return p, pairs

flag = b'#####'
key = os.urandom(16)
cipher = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
ct = cipher.encrypt(flag + os.urandom(16 - len(flag) % 16))
p, pairs = Raven(4, key)

print(f"{p = }\n{pairs = }\n{ct = }")
'''
p = 1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153
pairs = [(615358616404864757405587650175842125441380884418119777842292095751090237848084440177153221092040264723889917863863854377665802549748720692225139890884830475485512763149974948701807492663962748292710803434009673589337265, 84982753624462868217739962129526665082932464631118597651920986288766037499319751354013335054886685186857222944776560264528363811382359242656883760986496856164448940929282013856762706210675691655747370624405968909408102), (528363810186974800127873139379943131424126521611531830591311656948009967709310974894584084912262479395720199930206495204352231804549705720854271566421006481173043064265399467682307971910488405265826107365679757755866812, 496810092723839642457928776423789418365006215801711874210443222720529161066621876103037104247173440072986344011599384793861949574577559989016501090247331146721371126871470611440468688947950954988175225633457347666551944), (68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873, 995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800), (61574167546312883246262193556029081771904529137922128124933785599227801608271357738142074310192454183183340219301304405636497744152219785042075198056952749425345561162612590170550454476602892138914473795478531165181812, 618169326093802548516842299173393893046765466917311052414967158839652012130855552015876657514610755108820971877570295328618373296493668146691687291894702228119875561585283226588768969944781923428807766632578060221034862)]
ct = b"|2\xf0v7\x05Y\x89\r]\xe93s\rr)#3\xe9\x90%Z\x9a\xd9\x9ck\xba\xec]q\xb8\xf2'\xc8e~fL\xcf\x93\x00\xd6^s-\xc9\xd6M"
'''

这个格子算是我目前调过最复杂的格子了，但是原理不太难，理清楚关系即可。

理解 raven 中的函数，观察到函数 f 的函数的系数都是经过 sha256 的，不太可能通过逆向或者是正向爆破得解。可以确定的是 sha256 之后的数都不太大。本地调试的时候可以直接 print(f) 可以看到 f 大概是等于 $f=ax^3+bx^2+cx^2+d$ ，而其中系数 $d$ 就是我们要求的量。我们有以下关于 x 和 y 的关系

$a_0x_i^6+a_1x_i^5+a_2x_i^4+a_3x_i^3+a_4x_i^2+a_5x_i+a_6+t_i=y+k_ip$

i 的范围从 0-3 共 4 组，t 为 256 位的素数，由此我们可以构造格 (中间加一列常数 $2^{256}$ 是为了让格子成为一个方阵)

$\begin{bmatrix} {a_0}&{a_1}&\dots&{a_5}&-1&{k_0}&{k_1}&{k_2}&{k_3} \end{bmatrix} \begin{bmatrix} 1&0&\dots&0&0&{x_0}^6&{x_1}^6&{x_2}^6&{x_3}^6\\ 0&1&\dots&0&0&{x_0}^5&{x_1}^5&{x_2}^5&{x_3}^5\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&\dots&1&0&{x_0}&{x_1}&{x_2}&{x_3}\\ 0&0&\dots&0&2^{256}&{y_0}&{y_1}&{y_2}&{y_3}\\ 0&0&\dots&0&0&p&0&0&0 \\ 0&0&\dots&0&0&0&p&0&0 \\ 0&0&\dots&0&0&0&0&p&0 \\ 0&0&\dots&0&0&0&0&0&p \\ \end{bmatrix} \begin{bmatrix} {a_0}&{a_1}&\dots&{a_5}&2^{256}&{a_6} + {t_0}&{a_6} + {t_1}&{a_6} + {t_2}&{a_6} + {t_3} \end{bmatrix}$

造好中间这个格子之后，LLL 出来第一行就是我们要的变量，通过 5 个系数可以求出最后的 secret，之后便可求得 flag

最后的 exp 为

from Crypto.Util.number import *
from Crypto.Cipher import AES
p = 1018551160851728231474335384388576586031917743463656622083024684199383855595168341728561337234276243780407755294430553694832049089534855113774546001494743212076463713621965520780122783825100696968959866614846174188401153
pairs = [(615358616404864757405587650175842125441380884418119777842292095751090237848084440177153221092040264723889917863863854377665802549748720692225139890884830475485512763149974948701807492663962748292710803434009673589337265, 84982753624462868217739962129526665082932464631118597651920986288766037499319751354013335054886685186857222944776560264528363811382359242656883760986496856164448940929282013856762706210675691655747370624405968909408102), (528363810186974800127873139379943131424126521611531830591311656948009967709310974894584084912262479395720199930206495204352231804549705720854271566421006481173043064265399467682307971910488405265826107365679757755866812, 496810092723839642457928776423789418365006215801711874210443222720529161066621876103037104247173440072986344011599384793861949574577559989016501090247331146721371126871470611440468688947950954988175225633457347666551944), (68711183101845981499596464753252121346970486988311398916877579778110690480447199642602267233989256728822535174215153145632158860662954277116345331672194812126361911061449082917955000137698138358926301360506687271134873, 995428771589393162202488762223106955302099250561593105620410424291405842350539887383005328242236156038373244928147473800972534658018117705291472213770335998508454938607290279268848513727721410314612261163489156360908800), (61574167546312883246262193556029081771904529137922128124933785599227801608271357738142074310192454183183340219301304405636497744152219785042075198056952749425345561162612590170550454476602892138914473795478531165181812, 618169326093802548516842299173393893046765466917311052414967158839652012130855552015876657514610755108820971877570295328618373296493668146691687291894702228119875561585283226588768969944781923428807766632578060221034862)]
ct = b"|2\xf0v7\x05Y\x89\r]\xe93s\rr)#3\xe9\x90%Z\x9a\xd9\x9ck\xba\xec]q\xb8\xf2'\xc8e~fL\xcf\x93\x00\xd6^s-\xc9\xd6M"
xs = [x for x,y in pairs]
ys = [y for x,y in pairs]
mat = [[0 for _ in range(11)] for _ in range(11)]
for i in range(6):
    mat[i][i] = 1
    for j in range(4):
        mat[i][7 + j] = int(xs[j] ** (6 - i))
mat[6][6] = 1
for i in range(7,11):
    mat[6][i] = ys[i - 7]
    mat[i][i] = p
mat = matrix(ZZ,mat)
# print(mat.LLL())
ans = list(map(abs,list(mat.LLL()[0])))
print(ans)
t1,t2,t3,_,_,t6 = ans[:6]
a = isqrt(t1)
b = t2 // (2 * a)
c = (t3 - b ** 2) // (2 * a)
secret = t6 // (2 * c)
print(a,b,c,secret)
key = long_to_bytes(secret)
aes = AES.new(key=key, IV=bytes(range(16)), mode=AES.MODE_CBC)
flag = aes.decrypt(ct)
print(flag)

# 0x04 2023nkctf fake_MT 3.28

附件

import random
# import signal

def guess_number_1():
    randoms = []
    for _ in range(208):
        randoms.append(random.getrandbits(96))

    print("randoms = "+str(randoms))
    number = str(random.getrandbits(96))
    guess = str(input("Guess after number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_2():
    number = str(random.getrandbits(96))
    randoms = []
    for _ in range(627):
        randoms.append(random.getrandbits(32))

    print("randoms = "+str(randoms))
    guess = str(input("Guess pre number:"))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_3():

    def _int32(x):
        return int(0xFFFFFFFF & x)  
    def init(seed):
        mt = [0] * 624
        mt[0] = seed
        for i in range(1, 624):
            mt[i] = _int32(1812433253 * (mt[i - 1] ^ mt[i - 1] >> 30) + i)
        return mt[-1]
    number = random.getrandbits(32)
    print("last number = "+ str(init(number)))
    guess = int(str(input("Guess seed number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)

def guess_number_4():
    def extract_number(y):
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        return y&0xffffffff

    number = random.getrandbits(32)
    print("extract number = "+ str(extract_number(number)))
    guess = int(str(input("Guess be extracted number:")))
    if guess != number:
        print("Wrong Number! Guess again.")
        exit(0)
    

print("Welcome to the Mersenne Twister basic challenge. Please try to solve 20 challenges in 60 seconds.")
# signal.alarm(60)

for i in range(20):
    print("Round: "+str(i+1))
    random.choice([guess_number_1,guess_number_2,guess_number_3,guess_number_4])()
    print("Good job!")

flag = open('/flag').read()
print("Congratulations on passing the challenge. This is your flag: " + str(flag))

题目不难，一直没有在 blog 里记过 mt19937 的题目。

题目一共 4 个不同的挑战，通过 20 次即可拿到 flag。

guess_number_1 是预测后一位随机数， guess_number_2 是预测之前的随机数， guess_number_3 是根据 mt19937 的原理逆向函数预测之前的数， guess_number_4 也是逆向函数。

mt19937 一直有一个很好用的包，https://github.com/kmyk/mersenne-twister-predictor，不建议初学者使用，过于方便不适合在了解原理的阶段使用。难度不大，就直接放 exp 了

from pwn import *
import gmpy2
from tqdm import tqdm
from extend_mt19937_predictor import ExtendMT19937Predictor
def inverse_right(res, shift):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp

# right shift with mask inverse
def inverse_right_mask(res, shift, mask):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

# left shift inverse
def inverse_left(res, shift):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp

# left shift with mask inverse
def inverse_left_mask(res, shift, mask):
    tmp = res
    bits = len(bin(res)[2:])
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y

def recover(y):
    y = inverse_right(y, 18)
    y = inverse_left_mask(y, 15, 4022730752)
    y = inverse_left_mask(y, 7, 2636928640)
    y = inverse_right(y, 11)
    return y

def hacker1(randoms):
    hacker = ExtendMT19937Predictor()
    [hacker.setrandbits(i,96) for i in randoms]
    ans = hacker.predict_getrandbits(96)
    return str(ans).encode()

def hacker2(randoms):
    hacker = ExtendMT19937Predictor()
    [hacker.setrandbits(i,32) for i in randoms]
    [hacker.backtrack_getrandbits(32) for _ in range(627)]
    ans = hacker.backtrack_getrandbits(96)
    return str(ans).encode()

def hacker3(num):
    for i in range(623,0,-1):
        num = (num - i) * gmpy2.invert(1812433253,2 ** 32) % (2 ** 32)
        num = inverse_right(num,30)
    return str(num).encode()

def hacker4(num):
    return str(recover(num)).encode()

def recvrandoms():
    r.recv(1)
    num = int(r.recvuntil(b'L, ')[:-3].decode())
    randoms = [num]
    if num.bit_length() > 40:
        for _ in range(206):
            num = int(r.recvuntil(b', ')[:-3].decode())
            randoms.append(num)
        num = int(r.recvuntil(b']\n')[:-3].decode())
        randoms.append(num)
        return randoms
    else:
        for _ in range(625):
            num = int(r.recvuntil(b', ')[:-3].decode())
            randoms.append(num)
        num = int(r.recvuntil(b']\n')[:-3].decode())
        randoms.append(num)
        return randoms

r = remote('node2.yuzhian.com.cn',39122)
# r.recvuntil(b'Press Enter to start...')
# r.sendline()
context(log_level = 'debug')
for i in tqdm(range(1,21)):
    r.recvuntil(('Round: ' + str(i) + '\n').encode())
    rec1 = r.recvuntil(b' = ')
    print(rec1)
    if b'randoms = ' in rec1:
        randoms = recvrandoms()
        cnt = r.recvuntil(b'number:')
        if b'after' in cnt:
            ans = hacker1(randoms)
            r.sendline(ans)
        else:
            ans = hacker2(randoms)
            r.sendline(ans)
    if b'extract' in rec1:
        num = int(r.recvline()[:-1].decode())
        ans = hacker4(num)
        r.recvuntil(b'Guess be extracted number:')
        r.sendline(ans)
    if b'last' in rec1:
        num = int(r.recvline()[:-1].decode())
        ans = hacker3(num)
        r.recvuntil(b'Guess seed number:')
        r.sendline(ans)

r.interactive()

# 0x03 2022 羊城杯 NovelSystem2 3.23

附件

from Crypto.Util.number import *
from gmpy2 import *
from uuid import uuid4
from flag import flag

class NovelSystem:
    def __init__(self, delta):
        self.p = getPrime(delta >> 1)
        self.q = getPrime(delta >> 1)
        self.N = self.p * self.q
        
        self.beta = 0.397
        self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1)
        self.e, self.d = self.generate_key(delta)
        self.r = getPrime(delta % delta.bit_length())
        

    def generate_key(self, delta):
        delta = int(delta * self.beta)
        d = getPrime(delta)
        e = invert(d, self.psi)
        return (e, d)

    def print_pk(self):
        print("pk:", (self.N, int(self.e), self.r))
    
    def print_sk(self):
        print("sk:", (self.N, self.p, self.q, self.e, self.d))
    
    def add_(self, a, b):
        m, n = a
        k, l = b
        if a[1] == 0:
            a, b = b, a
            m, n, k, l = k, l, m, n
        if l == 0:
            if n == 0:
                return (m * k, m + k)
            if (n + k) % self.N == 0:
                if (m - n ** 2) % self.N == 0:
                    return (0, 0)
                return ((m * k + self.r) * invert(m - n * n) % self.N, 0)
            return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k,self.N) % self.N)
        if (m + k + n * l) % self.N != 0:
            return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N)%self.N,(n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N)

        if (n * k + m * l + self.r) % self.N == 0:
            return (0, 0)
        return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0)

    def mul_(self, a, n):
        ans = (0, 0)
        while n > 0:
            if n & 1 == 1:
                ans = self.add_(ans, a)
            a = self.add_(a, a)
            n //= 2
        return ans

    def encrypt(self, m):
        return self.mul_(m, self.e)
        
    def decrypt(self, c):
        return self.mul_(c, self.d)

delta = 1024
enc = NovelSystem(delta)

m = bytes_to_long(flag[:len(flag) // 2]), bytes_to_long(flag[len(flag) // 2:])
c = enc.encrypt(m)
enc.print_pk()
print(c)
assert enc.decrypt(c) == m

'''
pk: (69608791192421919283757675475568920773353852553984294535246714322217147926140334786382671447161809319059757926660104907264892471513691210713164936055575369238706600340586833164515933300246888063235136692968128246137215938114060492757345025435557818940819819146315427528432401269318798897677955790143951114837, 3569709831456961963983317856906282564247794656174883346551318455409781951821532194464316039706968856000098892463123452801581913760419867217744612993876726508565953876218527986879338419527071132882516845467078252901861510834762733680624403662683842157212966883670782784707420186939792539380416673702618954148609178781352393489552193742869735649479707631323667621294737562886946346783459713562739324444015141587968954791790724386091523034752910330271202144122827876441229219899077622471534860855412052877175120218922873300885113936346989198403927493848984768217738562507350427274074810257890679068944519650350540061773, 3)
(mpz(25277872308079622747549210576460613586229133947234593535200353386990766871354231190884983744062724190757790170095336476433339679661865115249940491581950905446714526508336734968117122923367321009658430492676221613955154012709104353264746945809594342072744903918483080444098810305069478604650812993367066108686), mpz(23837611977059204694294310415628596206205358541193793076161113947121055317488611201828968875769165810136018932772918536959013421962176622562932517080185242296377551991015543007194938521921909070483342042300905806379510158998331097627686209024554054114596970966269941945120227200103961459438854583220408434182))
'''

赛后才知道考点是二元 cop，只能说当时被题目唬住了，看到类似于曲线里面的 mul 和 add 函数之后就直接放弃了。

其实这题主要在 psi 里面， $\text{psi}=(p^2+p+1)(q^2+q+1)$ ，化简得到

$\text{psi}=n^2+n(p+q)-n+(p+q)^2+p+q+1$ ，再根据公私钥生成的式子得到

$ed \equiv 1 \bmod \text{psi}$ ，令 $s=p+q$ 写成等式就是 $ed=1+k(n^2+ns-n+s^2+s+1)$

观察一下数据量的大小，在模 e 的情况下可以用二元 cop 求出其中较小的 k 和 s。其中一直不太了解二元 cop 的原理，一直把它当作普通的 cop 来做，就是比普通一元的 cop 的界更紧。以下是二元 cop 的过程

import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
n,e,r = (69608791192421919283757675475568920773353852553984294535246714322217147926140334786382671447161809319059757926660104907264892471513691210713164936055575369238706600340586833164515933300246888063235136692968128246137215938114060492757345025435557818940819819146315427528432401269318798897677955790143951114837, 3569709831456961963983317856906282564247794656174883346551318455409781951821532194464316039706968856000098892463123452801581913760419867217744612993876726508565953876218527986879338419527071132882516845467078252901861510834762733680624403662683842157212966883670782784707420186939792539380416673702618954148609178781352393489552193742869735649479707631323667621294737562886946346783459713562739324444015141587968954791790724386091523034752910330271202144122827876441229219899077622471534860855412052877175120218922873300885113936346989198403927493848984768217738562507350427274074810257890679068944519650350540061773, 3)
PR.<s,k> = PolynomialRing(Zmod(e))
psi = n ** 2 + n * s - n + s ** 2 + s + 1
f = k * psi + 1

bounds = (2 ** 513,2 ** 406)
root = small_roots(f,bounds,m=6,d=4)
print(root)
#[(16735107022622476383866840093901965222228713238108348681003452372987945455610490028938094968941275455301623881501712248119610615329278201446033374682492202, 109544961591167891450312756961715400985114370115235587811168068856002720019953678125934219464349698130680024301825175448812)]

得到 s 之后后面的内容都很简单了，顺着原来类里面的函数逆回去就好了

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

class NovelSystem:
    def __init__(self, delta,p,q,n,e,d):
        self.p = p
        self.q = q
        self.N = n
        self.e = e
        self.d = d
        self.beta = 0.397
        self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1)
        # self.e, self.d = self.generate_key(delta)
        self.r = getPrime(delta % delta.bit_length())

    # def generate_key(self, delta):
    #     delta = int(delta * self.beta)
    #     d = getPrime(delta)
    #     e = invert(d, self.psi)
    #     return (e, d)

    def print_pk(self):
        print("pk:", (self.N, int(self.e), self.r))

    def print_sk(self):
        print("sk:", (self.N, self.p, self.q, self.e, self.d))

    def add_(self, a, b):
        m, n = a
        k, l = b
        if a[1] == 0:
            a, b = b, a
            m, n, k, l = k, l, m, n
        if l == 0:
            if n == 0:
                return (m * k, m + k)
            if (n + k) % self.N == 0:
                if (m - n ** 2) % self.N == 0:
                    return (0, 0)
                return ((m * k + self.r) * invert(m - n * n, self.N) % self.N, 0)
            return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k, self.N) % self.N)
        if (m + k + n * l) % self.N != 0:
            return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N) % self.N,
                    (n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N)

        if (n * k + m * l + self.r) % self.N == 0:
            return (0, 0)
        return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0)

    def mul_(self, a, n):
        ans = (0, 0)
        while n > 0:
            if n & 1 == 1:
                ans = self.add_(ans, a)
            a = self.add_(a, a)
            n //= 2
        return ans

    def encrypt(self, m):
        return self.mul_(m, self.e)

    def decrypt(self, c):
        return self.mul_(c, self.d)
s = 16735107022622476383866840093901965222228713238108348681003452372987945455610490028938094968941275455301623881501712248119610615329278201446033374682492202
n,e,r = (69608791192421919283757675475568920773353852553984294535246714322217147926140334786382671447161809319059757926660104907264892471513691210713164936055575369238706600340586833164515933300246888063235136692968128246137215938114060492757345025435557818940819819146315427528432401269318798897677955790143951114837, 3569709831456961963983317856906282564247794656174883346551318455409781951821532194464316039706968856000098892463123452801581913760419867217744612993876726508565953876218527986879338419527071132882516845467078252901861510834762733680624403662683842157212966883670782784707420186939792539380416673702618954148609178781352393489552193742869735649479707631323667621294737562886946346783459713562739324444015141587968954791790724386091523034752910330271202144122827876441229219899077622471534860855412052877175120218922873300885113936346989198403927493848984768217738562507350427274074810257890679068944519650350540061773, 3)
# p,q = sympy.Symbol('p'),sympy.Symbol('q')
# f1 = p * q - n
# f2 = p + q - s
# result = sympy.solve([f1,f2],[p,q])
# print(result)
p,q = 7729462160300184063354083506942486302239289283623335189017826590761497646527271658325039881984377424646284428281668979724518269305474372716053376048320159, 9005644862322292320512756586959478919989423954485013491985625782226447809083218370613055086956898030655339453220043268395092346023803828729979998634172043
psi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = gmpy2.invert(e,psi)
delta = 1024
dec = NovelSystem(delta,p,q,n,e,d)
c = (25277872308079622747549210576460613586229133947234593535200353386990766871354231190884983744062724190757790170095336476433339679661865115249940491581950905446714526508336734968117122923367321009658430492676221613955154012709104353264746945809594342072744903918483080444098810305069478604650812993367066108686, 23837611977059204694294310415628596206205358541193793076161113947121055317488611201828968875769165810136018932772918536959013421962176622562932517080185242296377551991015543007194938521921909070483342042300905806379510158998331097627686209024554054114596970966269941945120227200103961459438854583220408434182)
m = dec.decrypt(c)
print(m)
flag = long_to_bytes(m[0]) + long_to_bytes(m[1])
print(flag)
#b'DASCTF{a1a4a518320a469088c64aa4fbc22438}'

# 0x02 2022 羊城杯 linearAlgebra 3.23

附件

from secret import flag
import libnum
import random
import os

assert flag[:7] == b'DASCTF{' and flag[-1] == ord('}')

n = 32
asize = 512

def pad(m, n):
  assert len(m) < n*n
  return m + b'\x00' + os.urandom(n*n - len(m) - 1)

def bytes2Matrix(m, n):
  assert len(m) == n*n
  return matrix(ZZ, [[m[r*n+c] for c in range(n)] for r in range(n)])

def randMatrix(s, n):
  while True:
    Mt = matrix(ZZ, [[random.randint(0, 2^s) for c in range(n)] for r in range(n)])
    if Mt.det() != 0:
      return Mt

def corrupt(Mt, s, n):
  Mt_ = matrix(ZZ, Mt)
  for i in range(n):
    r_ = random.randint(0, n-1)
    c_ = random.randint(0, n-1)
    Mt_[r_, c_] = random.randint(0, 2^s)
  return Mt_

m = pad(flag[7:-1], n)
M = bytes2Matrix(m, n)
A = randMatrix(asize, n)
C = A*M
Ac = corrupt(A, asize, n)

print('C:')
print(C)
print('Ac:')
print(Ac)

数据量太大就不放了，复现的话自己生成一个 flag 即可。参考 zima👴的 blog，再膜一下膜一下

这题拿来练手 LLL 挺好的，当时比赛的时候不会格子呜呜呜，回来复现的时候发现挺好做的。

M 是要求的矩阵，pad 函数就是把 flag 数据 pad 成一个矩阵。给了 C 和 Ac，Ac 就是矩阵 A 混淆过后的矩阵。

混淆是用 corrupt 函数，其实就是在 32*32 的矩阵中随机选 32 个数据替换成一个大小差不多的数据。这个随机就很讲究，随机是纯随机，也就是说并不是这个矩阵中每一行都有数据被替换。写个循环找到某一行没有被替换的数据构造矩阵。

$\begin{bmatrix} {m_1}&{m_2}&{m_3}&-1 \end{bmatrix} \begin{bmatrix} 1&0&0&Ac_0\\ 0&1&0&Ac_1\\ 0&0&1&Ac_2\\ 0&0&0&C \end{bmatrix} \begin{bmatrix} {m_1}&{m_2}&{m_3}&0 \end{bmatrix}$

其中 m 的数据是特别小的，矩阵中的数据 Ac 是特别大的，可以规约出 m 来。

首先读取矩阵，然后测试 Ac 中哪些行的数据是没有被改过的

import re
from tqdm import tqdm
def readmatrix(data):
    out = [eval('[' + re.sub(' +',',',i[1:-1].strip()) + ']') for i in data]
    return out

data = open('out','r').read().splitlines()

dataC = data[1:33]
dataAc = data[34:]
C = readmatrix(dataC)
Ac = readmatrix(dataAc)
#print(C)
n = len(C)
ans = []
for i in tqdm(range(0,n)):
    aim = C[i][0]
    mat = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for j in range(0,n):
        mat[j][j] = 1
        mat[j][-1] = Ac[i][j]
    mat[-1][-1] = -aim
    mat = matrix(ZZ,mat).LLL()
    if mat[0][-1] == 0:
        ans.append(i)
print(ans)
#ans = [1, 3, 5, 9, 10, 20, 24, 25, 26, 27, 29, 31]

之后再随便以某一行为基准再 LLL 出其他的数据即可

完整 wp 如下

import re
from tqdm import tqdm
def readmatrix(data):
    out = [eval('[' + re.sub(' +',',',i[1:-1].strip()) + ']') for i in data]
    return out

data = open('out','r').read().splitlines()

dataC = data[1:33]
dataAc = data[34:]
C = readmatrix(dataC)
Ac = readmatrix(dataAc)
#print(C)
n = len(C)
# ans = []
# for i in tqdm(range(0,n)):
#     aim = C[i][0]
#     mat = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
#     for j in range(0,n):
#         mat[j][j] = 1
#         mat[j][-1] = Ac[i][j]
#     mat[-1][-1] = -aim
#     mat = matrix(ZZ,mat).LLL()
#     if mat[0][-1] == 0:
#         ans.append(i)
# print(ans)
ans = [1, 3, 5, 9, 10, 20, 24, 25, 26, 27, 29, 31]
M = [[0 for _ in range(n)] for _ in range(n)]
mat = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for j in range(n):
    mat[j][j] = 1
    mat[j][-1] = Ac[1][j]
for i in tqdm(range(0,n)):
    mat[-1][-1] = -C[1][i]
    fleg = matrix(ZZ,mat).LLL()[0]
    for j,s in enumerate(fleg[:-1]):
        M[j][i] = int(s)
flag = bytes(M[0] + M[1])
print(flag)

# 0x01 2022ichunqiu 勇者山峰 bob_enc 3.3

附件

from secret import * 
import random

prime =  2141
print len(flag)
flag = map(ord,flag)
flag1 = flag[:21]
flag2 = flag[21:]
row = 64

def add(msg1,msg2):
    return [(x+y)%prime for x,y in zip(msg1,msg2)]

def multi(msg1,msg2):
    out = []
    for l in msg1:
        s = 0
        for x,y in zip(l,msg2):
            s += (x*y)%prime
            s %= prime
        out.append(s)
    return out
def genkey(leng):
    l = [[] for i in range(row)]
    for x in range(row):
        for i in range(leng):
            l[x].append(random.randint(0,511))
    return l

key = genkey(len(flag1))
print key

cipher1 = multi(key,flag1)

print cipher1

cipher2 = multi(key,flag2)

noise = [random.randint(0,6) for i in range(row)]
print add(noise,cipher2)

题目分为两部分，意思很好懂。

第一部分就是正常的矩阵求逆，取 flag 长度就可以

prime =  2141
key = [[185, 96, 351, 118, 421, 449, 350, 349, 388, 95, 341, 327, 29, 156, 399, 283, 292, 461, 445, 120, 126], [495, 358, 192, 300, 279, 277, 478, 335, 231, 241, 178, 314, 453, 251, 133, 391, 213, 132, 254, 388, 46], [428, 44, 100, 483, 12, 311, 57, 443, 289, 90, 478, 495, 399, 89, 324, 275, 322, 99, 343, 489, 133], [420, 358, 472, 260, 267, 136, 303, 491, 390, 248, 430, 117, 154, 244, 62, 217, 204, 334, 277, 231, 325], [11, 96, 61, 67, 456, 361, 292, 278, 424, 237, 345, 109, 475, 473, 29, 250, 195, 430, 114, 13, 199], [17, 91, 330, 73, 384, 134, 437, 161, 166, 185, 499, 491, 342, 129, 348, 162, 478, 216, 189, 311, 502], [396, 437, 98, 421, 120, 443, 113, 432, 9, 476, 243, 122, 416, 508, 287, 45, 84, 322, 504, 287, 251], [187, 489, 407, 204, 127, 10, 302, 101, 389, 113, 469, 184, 249, 131, 113, 18, 350, 106, 486, 406, 295], [265, 425, 30, 478, 471, 211, 162, 323, 163, 205, 187, 422, 452, 226, 230, 367, 478, 229, 365, 395, 294], [360, 193, 180, 253, 337, 453, 16, 352, 243, 107, 171, 46, 25, 234, 46, 479, 267, 267, 171, 188, 127], [379, 360, 109, 360, 403, 343, 75, 306, 138, 40, 41, 253, 428, 401, 464, 495, 21, 296, 319, 410, 440], [28, 209, 1, 233, 458, 266, 301, 359, 469, 304, 264, 368, 339, 25, 490, 343, 404, 488, 275, 262, 274], [180, 372, 133, 341, 29, 352, 326, 89, 323, 479, 68, 76, 247, 225, 159, 163, 180, 160, 171, 7, 322], [322, 295, 28, 467, 361, 169, 190, 71, 456, 140, 456, 202, 295, 424, 428, 18, 286, 233, 470, 303, 429], [234, 37, 128, 175, 282, 509, 54, 186, 177, 23, 348, 487, 473, 377, 81, 225, 154, 511, 364, 120, 280], [262, 82, 383, 490, 128, 448, 289, 420, 239, 374, 392, 149, 217, 398, 441, 480, 453, 503, 318, 285, 418], [0, 347, 223, 381, 469, 208, 424, 435, 404, 64, 107, 73, 490, 116, 445, 392, 194, 287, 66, 325, 261], [99, 26, 489, 114, 3, 351, 494, 174, 369, 354, 379, 187, 90, 202, 286, 37, 48, 397, 298, 65, 499], [455, 114, 349, 401, 5, 139, 314, 227, 134, 258, 270, 135, 287, 332, 298, 272, 167, 43, 271, 484, 177], [448, 78, 479, 324, 170, 7, 230, 173, 214, 65, 91, 497, 68, 391, 44, 205, 364, 471, 460, 312, 122], [452, 360, 448, 169, 240, 496, 302, 3, 354, 266, 46, 22, 151, 498, 461, 314, 169, 88, 30, 487, 258], [282, 222, 260, 503, 106, 420, 315, 307, 202, 238, 224, 329, 351, 190, 137, 294, 171, 309, 19, 186, 391], [69, 501, 283, 96, 159, 459, 437, 192, 293, 479, 79, 49, 299, 205, 177, 360, 36, 414, 118, 194, 270], [6, 419, 459, 254, 97, 455, 445, 239, 277, 278, 226, 23, 146, 151, 273, 378, 141, 281, 480, 388, 213], [181, 508, 347, 447, 467, 351, 503, 262, 375, 74, 49, 48, 364, 492, 400, 305, 25, 207, 278, 163, 11], [320, 94, 400, 15, 201, 53, 130, 137, 219, 57, 20, 239, 467, 352, 373, 395, 58, 4, 446, 332, 41], [205, 385, 446, 185, 470, 268, 308, 461, 265, 75, 75, 104, 108, 14, 334, 499, 207, 363, 94, 505, 363], [299, 292, 112, 203, 7, 240, 499, 343, 396, 482, 383, 61, 476, 101, 187, 265, 428, 53, 24, 342, 201], [421, 286, 305, 79, 324, 216, 163, 193, 362, 57, 472, 449, 169, 33, 280, 202, 237, 376, 382, 2, 1], [379, 33, 151, 51, 353, 295, 145, 220, 147, 251, 90, 344, 96, 31, 185, 250, 270, 420, 365, 373, 356], [228, 299, 87, 113, 458, 52, 26, 228, 294, 97, 384, 493, 380, 209, 257, 20, 375, 2, 316, 129, 492], [479, 346, 57, 488, 183, 185, 18, 422, 209, 318, 461, 159, 469, 145, 44, 58, 441, 490, 510, 194, 192], [254, 398, 510, 159, 371, 280, 331, 23, 99, 150, 175, 151, 42, 473, 164, 35, 97, 174, 115, 24, 270], [280, 76, 254, 293, 491, 76, 128, 301, 240, 357, 192, 372, 343, 34, 386, 468, 313, 41, 285, 507, 282], [271, 91, 507, 16, 128, 8, 326, 102, 355, 371, 313, 292, 433, 2, 459, 14, 258, 498, 146, 446, 309], [386, 88, 502, 4, 399, 272, 49, 69, 51, 465, 291, 289, 417, 271, 374, 337, 46, 393, 19, 429, 91], [407, 35, 337, 51, 41, 460, 222, 448, 499, 381, 59, 468, 440, 216, 86, 236, 91, 18, 123, 68, 145], [384, 30, 454, 419, 275, 164, 72, 195, 489, 458, 419, 148, 269, 150, 358, 188, 109, 27, 42, 34, 123], [500, 184, 195, 193, 68, 19, 329, 511, 280, 69, 113, 124, 102, 274, 43, 374, 408, 64, 314, 309, 473], [72, 145, 242, 2, 367, 371, 143, 166, 325, 74, 414, 94, 269, 196, 124, 94, 14, 351, 111, 465, 503], [70, 47, 439, 170, 306, 82, 233, 36, 346, 234, 157, 468, 83, 85, 424, 157, 258, 120, 270, 136, 286], [442, 173, 254, 271, 420, 507, 297, 473, 296, 511, 98, 133, 37, 498, 468, 17, 260, 318, 168, 490, 124], [50, 35, 252, 472, 406, 400, 439, 89, 309, 393, 332, 324, 260, 215, 8, 322, 357, 252, 124, 358, 457], [93, 102, 478, 224, 428, 10, 238, 368, 113, 502, 148, 7, 395, 97, 73, 306, 40, 395, 9, 254, 319], [282, 277, 295, 425, 59, 21, 136, 230, 207, 1, 29, 170, 14, 337, 371, 437, 359, 10, 100, 374, 24], [3, 270, 289, 179, 434, 489, 470, 343, 478, 156, 177, 72, 13, 266, 475, 23, 148, 102, 210, 270, 323], [464, 466, 277, 191, 426, 20, 266, 33, 41, 249, 452, 475, 265, 421, 282, 250, 233, 287, 495, 170, 300], [379, 35, 137, 106, 155, 81, 154, 382, 30, 237, 294, 478, 321, 384, 48, 111, 150, 4, 454, 446, 28], [57, 355, 94, 253, 297, 424, 415, 480, 68, 356, 415, 73, 41, 171, 491, 130, 92, 180, 506, 326, 463], [279, 43, 202, 35, 397, 257, 120, 11, 231, 369, 221, 332, 47, 236, 58, 278, 75, 117, 33, 130, 358], [142, 335, 339, 112, 38, 82, 426, 211, 174, 389, 137, 96, 431, 113, 112, 500, 145, 44, 313, 96, 187], [246, 211, 400, 415, 294, 234, 367, 46, 371, 479, 412, 197, 204, 498, 18, 140, 67, 237, 510, 457, 298], [258, 3, 136, 284, 149, 161, 456, 122, 114, 383, 251, 240, 453, 227, 330, 33, 241, 160, 306, 254, 409], [391, 115, 92, 102, 359, 182, 489, 313, 204, 275, 206, 447, 436, 286, 229, 377, 374, 162, 22, 384, 40], [427, 491, 362, 240, 358, 296, 154, 178, 278, 284, 324, 422, 52, 295, 490, 56, 39, 378, 174, 202, 496], [29, 454, 436, 6, 287, 82, 154, 474, 92, 272, 400, 238, 352, 140, 386, 504, 19, 32, 334, 30, 450], [469, 123, 353, 422, 175, 260, 294, 18, 268, 479, 60, 114, 456, 55, 403, 446, 166, 259, 294, 215, 48], [404, 187, 426, 362, 296, 239, 226, 416, 306, 336, 1, 448, 47, 403, 367, 357, 501, 425, 310, 41, 303], [339, 115, 478, 416, 10, 90, 188, 229, 217, 441, 288, 152, 394, 219, 422, 376, 325, 375, 6, 454, 238], [226, 226, 149, 107, 418, 419, 209, 108, 87, 127, 202, 320, 179, 234, 87, 335, 195, 5, 273, 142, 115], [464, 177, 77, 101, 76, 19, 73, 397, 296, 34, 360, 107, 491, 460, 510, 342, 198, 118, 105, 337, 239], [464, 25, 191, 113, 455, 129, 247, 488, 303, 27, 242, 423, 336, 125, 283, 332, 244, 372, 175, 276, 49], [211, 367, 406, 314, 177, 496, 320, 385, 193, 51, 423, 80, 258, 44, 154, 362, 215, 296, 260, 424, 160], [384, 161, 92, 402, 414, 443, 129, 279, 272, 224, 294, 319, 75, 169, 242, 85, 315, 402, 4, 268, 88]]
cipher1 = [1702, 795, 740, 373, 535, 1308, 1050, 502, 40, 672, 1354, 1843, 515, 231, 774, 65, 978, 1340, 455, 2137, 733, 307, 1604, 723, 1023, 1253, 275, 1817, 404, 2035, 267, 1475, 14, 2127, 15, 487, 317, 757, 290, 541, 100, 951, 2049, 1042, 1404, 1676, 655, 1460, 1532, 273, 916, 1454, 1690, 1628, 1751, 1656, 139, 156, 2102, 264, 243, 455, 1564, 2072]
key = matrix(Zmod(prime),key[:21])
cipher1 = vector(Zmod(prime),cipher1[:21])
flag1 = (key ** -1) * cipher1
print(bytes(flag1))

第二部分是一个 lwe 问题，是在第一部分的基础上，在结果上加了噪声，也就是

1 2	noise = [random.randint(0,6) for i in range(row)] print add(noise,cipher2)

lwe 的原理也不懂，记个板子就好。板子来自 lazzaro

from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul
# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

key = [[185, 96, 351, 118, 421, 449, 350, 349, 388, 95, 341, 327, 29, 156, 399, 283, 292, 461, 445, 120, 126], [495, 358, 192, 300, 279, 277, 478, 335, 231, 241, 178, 314, 453, 251, 133, 391, 213, 132, 254, 388, 46], [428, 44, 100, 483, 12, 311, 57, 443, 289, 90, 478, 495, 399, 89, 324, 275, 322, 99, 343, 489, 133], [420, 358, 472, 260, 267, 136, 303, 491, 390, 248, 430, 117, 154, 244, 62, 217, 204, 334, 277, 231, 325], [11, 96, 61, 67, 456, 361, 292, 278, 424, 237, 345, 109, 475, 473, 29, 250, 195, 430, 114, 13, 199], [17, 91, 330, 73, 384, 134, 437, 161, 166, 185, 499, 491, 342, 129, 348, 162, 478, 216, 189, 311, 502], [396, 437, 98, 421, 120, 443, 113, 432, 9, 476, 243, 122, 416, 508, 287, 45, 84, 322, 504, 287, 251], [187, 489, 407, 204, 127, 10, 302, 101, 389, 113, 469, 184, 249, 131, 113, 18, 350, 106, 486, 406, 295], [265, 425, 30, 478, 471, 211, 162, 323, 163, 205, 187, 422, 452, 226, 230, 367, 478, 229, 365, 395, 294], [360, 193, 180, 253, 337, 453, 16, 352, 243, 107, 171, 46, 25, 234, 46, 479, 267, 267, 171, 188, 127], [379, 360, 109, 360, 403, 343, 75, 306, 138, 40, 41, 253, 428, 401, 464, 495, 21, 296, 319, 410, 440], [28, 209, 1, 233, 458, 266, 301, 359, 469, 304, 264, 368, 339, 25, 490, 343, 404, 488, 275, 262, 274], [180, 372, 133, 341, 29, 352, 326, 89, 323, 479, 68, 76, 247, 225, 159, 163, 180, 160, 171, 7, 322], [322, 295, 28, 467, 361, 169, 190, 71, 456, 140, 456, 202, 295, 424, 428, 18, 286, 233, 470, 303, 429], [234, 37, 128, 175, 282, 509, 54, 186, 177, 23, 348, 487, 473, 377, 81, 225, 154, 511, 364, 120, 280], [262, 82, 383, 490, 128, 448, 289, 420, 239, 374, 392, 149, 217, 398, 441, 480, 453, 503, 318, 285, 418], [0, 347, 223, 381, 469, 208, 424, 435, 404, 64, 107, 73, 490, 116, 445, 392, 194, 287, 66, 325, 261], [99, 26, 489, 114, 3, 351, 494, 174, 369, 354, 379, 187, 90, 202, 286, 37, 48, 397, 298, 65, 499], [455, 114, 349, 401, 5, 139, 314, 227, 134, 258, 270, 135, 287, 332, 298, 272, 167, 43, 271, 484, 177], [448, 78, 479, 324, 170, 7, 230, 173, 214, 65, 91, 497, 68, 391, 44, 205, 364, 471, 460, 312, 122], [452, 360, 448, 169, 240, 496, 302, 3, 354, 266, 46, 22, 151, 498, 461, 314, 169, 88, 30, 487, 258], [282, 222, 260, 503, 106, 420, 315, 307, 202, 238, 224, 329, 351, 190, 137, 294, 171, 309, 19, 186, 391], [69, 501, 283, 96, 159, 459, 437, 192, 293, 479, 79, 49, 299, 205, 177, 360, 36, 414, 118, 194, 270], [6, 419, 459, 254, 97, 455, 445, 239, 277, 278, 226, 23, 146, 151, 273, 378, 141, 281, 480, 388, 213], [181, 508, 347, 447, 467, 351, 503, 262, 375, 74, 49, 48, 364, 492, 400, 305, 25, 207, 278, 163, 11], [320, 94, 400, 15, 201, 53, 130, 137, 219, 57, 20, 239, 467, 352, 373, 395, 58, 4, 446, 332, 41], [205, 385, 446, 185, 470, 268, 308, 461, 265, 75, 75, 104, 108, 14, 334, 499, 207, 363, 94, 505, 363], [299, 292, 112, 203, 7, 240, 499, 343, 396, 482, 383, 61, 476, 101, 187, 265, 428, 53, 24, 342, 201], [421, 286, 305, 79, 324, 216, 163, 193, 362, 57, 472, 449, 169, 33, 280, 202, 237, 376, 382, 2, 1], [379, 33, 151, 51, 353, 295, 145, 220, 147, 251, 90, 344, 96, 31, 185, 250, 270, 420, 365, 373, 356], [228, 299, 87, 113, 458, 52, 26, 228, 294, 97, 384, 493, 380, 209, 257, 20, 375, 2, 316, 129, 492], [479, 346, 57, 488, 183, 185, 18, 422, 209, 318, 461, 159, 469, 145, 44, 58, 441, 490, 510, 194, 192], [254, 398, 510, 159, 371, 280, 331, 23, 99, 150, 175, 151, 42, 473, 164, 35, 97, 174, 115, 24, 270], [280, 76, 254, 293, 491, 76, 128, 301, 240, 357, 192, 372, 343, 34, 386, 468, 313, 41, 285, 507, 282], [271, 91, 507, 16, 128, 8, 326, 102, 355, 371, 313, 292, 433, 2, 459, 14, 258, 498, 146, 446, 309], [386, 88, 502, 4, 399, 272, 49, 69, 51, 465, 291, 289, 417, 271, 374, 337, 46, 393, 19, 429, 91], [407, 35, 337, 51, 41, 460, 222, 448, 499, 381, 59, 468, 440, 216, 86, 236, 91, 18, 123, 68, 145], [384, 30, 454, 419, 275, 164, 72, 195, 489, 458, 419, 148, 269, 150, 358, 188, 109, 27, 42, 34, 123], [500, 184, 195, 193, 68, 19, 329, 511, 280, 69, 113, 124, 102, 274, 43, 374, 408, 64, 314, 309, 473], [72, 145, 242, 2, 367, 371, 143, 166, 325, 74, 414, 94, 269, 196, 124, 94, 14, 351, 111, 465, 503], [70, 47, 439, 170, 306, 82, 233, 36, 346, 234, 157, 468, 83, 85, 424, 157, 258, 120, 270, 136, 286], [442, 173, 254, 271, 420, 507, 297, 473, 296, 511, 98, 133, 37, 498, 468, 17, 260, 318, 168, 490, 124], [50, 35, 252, 472, 406, 400, 439, 89, 309, 393, 332, 324, 260, 215, 8, 322, 357, 252, 124, 358, 457], [93, 102, 478, 224, 428, 10, 238, 368, 113, 502, 148, 7, 395, 97, 73, 306, 40, 395, 9, 254, 319], [282, 277, 295, 425, 59, 21, 136, 230, 207, 1, 29, 170, 14, 337, 371, 437, 359, 10, 100, 374, 24], [3, 270, 289, 179, 434, 489, 470, 343, 478, 156, 177, 72, 13, 266, 475, 23, 148, 102, 210, 270, 323], [464, 466, 277, 191, 426, 20, 266, 33, 41, 249, 452, 475, 265, 421, 282, 250, 233, 287, 495, 170, 300], [379, 35, 137, 106, 155, 81, 154, 382, 30, 237, 294, 478, 321, 384, 48, 111, 150, 4, 454, 446, 28], [57, 355, 94, 253, 297, 424, 415, 480, 68, 356, 415, 73, 41, 171, 491, 130, 92, 180, 506, 326, 463], [279, 43, 202, 35, 397, 257, 120, 11, 231, 369, 221, 332, 47, 236, 58, 278, 75, 117, 33, 130, 358], [142, 335, 339, 112, 38, 82, 426, 211, 174, 389, 137, 96, 431, 113, 112, 500, 145, 44, 313, 96, 187], [246, 211, 400, 415, 294, 234, 367, 46, 371, 479, 412, 197, 204, 498, 18, 140, 67, 237, 510, 457, 298], [258, 3, 136, 284, 149, 161, 456, 122, 114, 383, 251, 240, 453, 227, 330, 33, 241, 160, 306, 254, 409], [391, 115, 92, 102, 359, 182, 489, 313, 204, 275, 206, 447, 436, 286, 229, 377, 374, 162, 22, 384, 40], [427, 491, 362, 240, 358, 296, 154, 178, 278, 284, 324, 422, 52, 295, 490, 56, 39, 378, 174, 202, 496], [29, 454, 436, 6, 287, 82, 154, 474, 92, 272, 400, 238, 352, 140, 386, 504, 19, 32, 334, 30, 450], [469, 123, 353, 422, 175, 260, 294, 18, 268, 479, 60, 114, 456, 55, 403, 446, 166, 259, 294, 215, 48], [404, 187, 426, 362, 296, 239, 226, 416, 306, 336, 1, 448, 47, 403, 367, 357, 501, 425, 310, 41, 303], [339, 115, 478, 416, 10, 90, 188, 229, 217, 441, 288, 152, 394, 219, 422, 376, 325, 375, 6, 454, 238], [226, 226, 149, 107, 418, 419, 209, 108, 87, 127, 202, 320, 179, 234, 87, 335, 195, 5, 273, 142, 115], [464, 177, 77, 101, 76, 19, 73, 397, 296, 34, 360, 107, 491, 460, 510, 342, 198, 118, 105, 337, 239], [464, 25, 191, 113, 455, 129, 247, 488, 303, 27, 242, 423, 336, 125, 283, 332, 244, 372, 175, 276, 49], [211, 367, 406, 314, 177, 496, 320, 385, 193, 51, 423, 80, 258, 44, 154, 362, 215, 296, 260, 424, 160], [384, 161, 92, 402, 414, 443, 129, 279, 272, 224, 294, 319, 75, 169, 242, 85, 315, 402, 4, 268, 88]]
cipher2 = [884, 1584, 681, 1713, 1916, 609, 1840, 177, 1723, 1049, 254, 864, 1671, 121, 2021, 1353, 1290, 1891, 556, 1786, 1553, 1548, 727, 1967, 1800, 422, 1559, 1290, 642, 1406, 441, 1928, 395, 279, 1125, 1273, 99, 1131, 395, 76, 733, 416, 924, 571, 506, 822, 877, 887, 860, 1755, 1385, 1861, 1754, 1851, 1046, 1724, 1866, 1427, 378, 351, 146, 1367, 756, 505]

m = 64
n = 21
q = prime

A_values = key
b_values = cipher2

A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
# print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
# print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

# print("Ingredients: {}".format(ingredients))
print(bytes(ingredients))

# 0x00 2022 赣网杯 lattice 1.30

附件

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

def gen(E):
    while True:
        K=getPrime(400)
        g,a,b=gmpy2.gcdext(E,K)
        if a<0:
            continue
        t=-b+E+1
        if isPrime(t):
            return t

E=getPrime(1024)
p,q=gen(E),gen(E)
n=p*q
e=0x10001
m=bytes_to_long(FLAG)
c=pow(m,e,n)
print('E=',E)
print('n=',n)
print('c=',c)


# E= 145106294105031284362950025863529581747975861699820575710872716519879803001392108419450056017622997630126276746554771656122532972639414248565300835010881208733690317975825283717056444554763316279849402612931689513790553913814829224657863376765661796202264396345600888403461230631203348607241016471422573987581
# n= 44146216754179716722914989774179545609003622919133954513612183365882143185648106448428976865616794364028711539848793072635268083809473736628189721636749099362357309849620541871571763282347330516151877113940331967499040686592378429548637013317457534594446645795078740141793093671629367727580553491215650337659527664705853572883730490883606327292351189552684783556726745519069083076011853815506574017326892680398272431716287020908845624185560350752642219469508595239978684428357590946555321280480160960814914981382127666519241796268901712746927364456562374629908387801426574825886691891613827829901620362221716562729181
# c= 42849954097468071726084946569343866748913580243693005484016477540655859876131867406160328063659045626546696925974783645320154966183202087150055162449812095144585221589345118079815257465944358288811363045125860701872706943518864751664960009957542024032708923424342364685385744625812611804391908032187252468394391715156637995783612091781280489452909027099099798074134765334858069523070373919122908726611177406605539137633787078228935029969970499482879713485023528914042281734061900906000317898016866589414229957899882390267865157996173644571590488588106926533461407231265146431839909395332178222814838553730197295527269

给了生成公钥的函数，其中变量的比特大小需要特别注意。首先是用扩展欧几里得生成了 $a$ 和 $b$ ，等式为 $aE+bK=1$ 。给了两组，其中 E 是固定的，然后再分别得到 p 和 q，总结已知量如下

${a_1}E+{b_1}{K_1}=1$ $p=-{b_1}+E+1$

${a_2}E+{b_2}{K_2}=1$ $q=-{b_2}+E+1$

其中 E 已知，要求得到 b。注意各个量的大小分别为

a	E	b	k
400	1024	1024	400

参考 zima👴的 blog，化简相当麻烦

首先令 $d=a+k$ ，原式变为 $Ed=k(p-1)+1$

代入相乘得到 $E^2{d_1}{d_2}={k_1}(p-1)+{k_2}(q-1)+{k_1}{k_2}(p-1)(q-1)+1$

不做代入化简得到 $E^2{d_1}{d_2}-{k_1}{k_2}(n-1)={k_1}{k_2}(1-p)+{k_1}{k_2}(1-q)+{k_1}(p-1)+{k_2}(q-1)+1$

代入 $Ed=k(p-1)+1$ 得到

$E^2{d_1}{d_2}-{k_1}{k_2}(n-1)=-{k_2}(E{d_1}-1)-{k_1}(E{d_2}-1)+E{d_1}-1+E{d_2}-1+1$

最后得到式子

$E^2{d_1}{d_2}-{k_1}{k_2}(n-1)=E({d_1}(1-{k_2})+{d_2}(1-{k_1}))+{k_1}+{k_2}-1$

之后可以构造格子

$\begin{bmatrix} {d_1}(1-{k_2})+{d_2}(1-{k_1})&{k_1}{k_2}&{d_1}{d_2} \end{bmatrix} \begin{bmatrix} E&1&0\\ n-1&0&1\\ {E^2}&0&0 \end{bmatrix} \begin{bmatrix} ({k_1}+{k_2}-1)&{d_1}(1-{k_2})+{d_2}(1-{k_1})&{k_1}{k_2} \end{bmatrix}$

观察我们预期规约出的向量，大小分别为

${k_1}+{k_2}-1$	${d_1}(1-{k_2})+{d_2}(1-{k_1})$	${k_1}$
400	800	800

显然这不应该是格中最短向量，我们需要适当增大格中最短向量的界即可，格中第一列中每一个数乘上 $2^{400}$ 即可 (不唯一，只要能规约出向量即可)。之后可以利用已知的 ${k_1}+{k_2}-1$ 和 ${k_1}{k_2}$ 求得 $k$ ，后续也就分别得到了 n 的分解，完整 exp 为

#sage
from Crypto.Util.number import *
import gmpy2
import sympy
E= 145106294105031284362950025863529581747975861699820575710872716519879803001392108419450056017622997630126276746554771656122532972639414248565300835010881208733690317975825283717056444554763316279849402612931689513790553913814829224657863376765661796202264396345600888403461230631203348607241016471422573987581
n= 44146216754179716722914989774179545609003622919133954513612183365882143185648106448428976865616794364028711539848793072635268083809473736628189721636749099362357309849620541871571763282347330516151877113940331967499040686592378429548637013317457534594446645795078740141793093671629367727580553491215650337659527664705853572883730490883606327292351189552684783556726745519069083076011853815506574017326892680398272431716287020908845624185560350752642219469508595239978684428357590946555321280480160960814914981382127666519241796268901712746927364456562374629908387801426574825886691891613827829901620362221716562729181
c= 42849954097468071726084946569343866748913580243693005484016477540655859876131867406160328063659045626546696925974783645320154966183202087150055162449812095144585221589345118079815257465944358288811363045125860701872706943518864751664960009957542024032708923424342364685385744625812611804391908032187252468394391715156637995783612091781280489452909027099099798074134765334858069523070373919122908726611177406605539137633787078228935029969970499482879713485023528914042281734061900906000317898016866589414229957899882390267865157996173644571590488588106926533461407231265146431839909395332178222814838553730197295527269
e = 0x10001
pad = 2 ** 400
mat = [
    [pad * E,1,0],
    [pad * (n - 1),0,1],
    [pad * (E ** 2),0,0]
]
mat = matrix(ZZ,mat)
ans = list(mat.LLL()[0])
k1k2 = abs(ans[-1])
k1_k2 = abs((ans[0] // pad) + 1)
print(k1k2)
print(k1_k2)
#懒人专用
k1,k2 = sympy.Symbol('k1'),sympy.Symbol('k2')
f1 = k1 * k2 - k1k2
f2 = k1 + k2 - k1_k2
root = sympy.solve([f1,f2],[k1,k2])
print(root)
k1,k2 = list(map(int,root[0]))
print(k1)
print(k2)
_,a1,b1 = gmpy2.gcdext(E,k1)
_,a2,b2 = gmpy2.gcdext(E,k2)
p = -b1 + E + 1
q = -b2 + E + 1
print(n == p * q)
phi = (p - 1) * (q - 1)
d = inverse_mod(e,phi)
m = power_mod(c,d,n)
print(long_to_bytes(int(m)))

学习 crypto