格密码进阶

发表于 2023-08-25 更新于 2024-02-20 分类于格密码阅读次数： Waline：本文字数： 6.1k 阅读时长 ≈ 22 分钟

刷题过程中，接触到有关格更进一步的问题

隐藏数问题（HNP / Hidden Number Problem）

打WMCTF的时候偶然接触这个感念，便在la佬的博客学习了一下

大概就是下面这样的形式

由$k_i \equiv A_ix + B_i \mod p$

如果有多组$k_i,A_i,B_i$

可以通过构造格，来求得这个x

$K$是$k_i$的上界

我的在疑惑是否可以自己调参，而不是套用别人构造的格呢？

根据具体情况调参

两种情况在实际测试过程中并没有成功。能恢复出bit位一样，但是值不对

会不会是因为数据之间得满足某些关系，才能用格恢复

希望懂的师傅们指点指点

下面分享一些有关HNP的题目

第一个当然是WM

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

def pr(msg):
    print(msg)


def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P

pq_bit = 512
offset = 16

P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)

inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

又是p ^ q这类的题目，类似于DAS7月赛

先遍历$2^{15}——2^{16}$恢复出gift，再爆出p,q

from tqdm import *

h = 
N = 

for j in trange(2**15,2**16):
    gift = int(bin(j)[2:] +bin(h)[2:].rjust(496,'0'),2)
    pbar = gift >>(512-16)
    while True:
        try:
            qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
            qbar = qbar>>6
            gifts = gift^(qbar<<(512-16-qbar.bit_length()))
            pbar = gifts >> (512-16-qbar.bit_length())

        except:
            break

    for i in range(64):
        p = (pbar<<6)+i
        if N % p == 0:
            q = N//p
            print("[+] p =",p)
            print("[+] q =",q)
            break

$\because R_i \equiv B_i × secret \mod p $，题目只给出了$R_i$的低16位

$\therefore r_i \equiv R_i \mod 2^{16}$

$\therefore r_i \equiv (B_i×secret \mod 2^{16}) \mod p \longrightarrow r_i \equiv B_i×secret + k_i×2^{16} \mod p$

$\therefore k_i×2^{16} \equiv B_i×secret -r_i \mod p \longrightarrow k_i \equiv B_i×secret×inv - r_i×inv \mod p $这里$inv$是$2^{16}$模$p$的逆元

最后可以得到$k_i = B_i×secret×inv - r_i×inv + l_ip$

于是有

这里的$k_i \approx 496bit$，所以取$K=2^{496}$，为了让右边向量的值都差不多大，调出$\frac{K×secret}{p}$

因为这题不是很清楚secret的大小，我就直接套脚本了。

现学的，理解不是很透彻

exp:

from tqdm import *
from gmpy2 import *

h = 
N = 

for j in trange(2**15,2**16):
    gift = int(bin(j)[2:] +bin(h)[2:].rjust(496,'0'),2)
    pbar = gift >>(512-16)
    while True:
        try:
            qbar = (N>>(1024 - pbar.bit_length()*2))//pbar
            qbar = qbar>>6
            gifts = gift^(qbar<<(512-16-qbar.bit_length()))
            pbar = gifts >> (512-16-qbar.bit_length())

        except:
            break

    for i in range(64):
        p = (pbar<<6)+i
        if N % p == 0:
            q = N//p
            print("[+] p =",p)
            print("[+] q =",q)
            break



p = 
B = 
R = 

n = len(R)

M = Matrix(QQ,n+2,n+2)
inv = invert(2 ** 16,p)

for i in range(n):
    M[i,i] = p
    M[-2,i] = B[i] * inv
    M[-1,i] = -R[i] * inv

t = QQ(2^496 / p)
K = 2^496

M[-2,-2] = t
M[-1,-1] = K

L = M.LLL()

x = L[1][-2] // t
print(x % p)

2023闽盾杯DDSA

题目

from random import randbytes
from hashlib import sha256
from secret import FLAG

prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351
prime_p = 2 * prime_q + 1
generator = 2

def generate_keys(prime_p:int, prime_q: int, generator: int):
    private_key = int(randbytes(48).hex(), 16)
    public_key = pow(generator, private_key, prime_p)
    return private_key, public_key

def signature(m: str, private_key: int):
    ephemeral_key = pow(int.from_bytes(m.encode(), "big"), -1, prime_q)
    value_r = pow(generator, ephemeral_key, prime_p) % prime_q
    hash_value = sha256(m.encode()).hexdigest()
    value_s = pow(ephemeral_key, -1, prime_q) * (int(hash_value, 16) + private_key * value_r) % prime_q
    return hash_value, value_r, value_s

def verification(message_hash: str, value_r: int, value_s: int, public_key: int):
    message_hash = int(message_hash, 16)
    inverse_s = pow(value_s, -1, prime_q)
    u1 = message_hash * inverse_s % prime_q
    u2 = value_r * inverse_s % prime_q
    value_v = (pow(generator, u1, prime_p) * pow(public_key, u2, prime_p) % prime_p) % prime_q
    return value_v == value_r

private_key, public_key = generate_keys(prime_p, prime_q, generator)
print(f"prime_p = {prime_p}")
print(f"prime_q = {prime_q}")
print(f"generator = {generator}")
print(f"public_key = {public_key}")
hash_value, value_r, value_s = signature(FLAG, private_key)
assert verification(hash_value, value_r, value_s, public_key)
print("FLAG= *******************************")
print(f"Here is your gift = {hash_value}")
print(f"value_r = {value_r}")
print(f"value_s = {value_s}")

#
prime_p = 254843759712120770192107797102254314236912507988317949449773952808056853528137124034192193635099026436082859359975257478069529928753465466553898924428657727410192480025664330547720267491593689914315716652925690802124634579341155119238992435231736067051804606192447508930100501670982605518547228404550199336703
prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351
generator = 2
public_key = 67243435243013084147486854556817234112402511481243660325565023251853355494433326575673419694681555652669449040366620819266474334253578972440047168279142184141910485872726393507923996391796227576994885784959692699388957187699662551912804856807879764447982440118185734843107861320087767180763032071844141444498
hash_value = '1cd920cc96d95280c96dd519df9ef49fed44c0ccfc80202372d1d196ea52ccb1'
value_r = 55738970979693187681378167695787130117222895714960965190485398883361826593727577547551100491285488657995662094510198245807164881975668033129508588482949937072551764160574163358989597712065236233432502150653495180122562651440328815420270936429340024510654195118602283837975822678425908768515924976212206091388
value_s = 16167384383010337939063062611160328697878797853686180912699394152331808942993583340068941838844464059078517385061012722104618040645796346201205622044690989665622791251498050801728558982153896995503905626972211668853043513769350513237538819164197920332285202321957958655237257294973629465658550364418471213584

题目把$m$当作$k^{-1}$，把m的哈希值记作$H$，$x$是私钥

已知$s \equiv k^{-1}×(H + xr) \mod q$即$s \equiv m(H+xr) \mod q$

其中，$H,r,q,s$已知

做个推导$\because s \equiv mH+mxr \mod q \longrightarrow sH^{-1} \equiv m + mxrH^{-1} \mod q$

$\therefore m = sH^{-1}-mxrH^{-1} +kq$，$sH^{-1}$看作常数$B$，$-rH^{-1}$看作$A$，令$mx=t$

于是有$m = At + B + kq$

构造格

猜测$m \approx 320bit$，因为$x \approx 384bit$，所以$t \approx 2^{384+320}$

所以构造出$1/2^{384}$，使得目标向量每个值差不多大

exp:

#sage
import gmpy2
from Crypto.Util.number import *

p = 
q = 
g = 2
pb = 
h = '1cd920cc96d95280c96dd519df9ef49fed44c0ccfc80202372d1d196ea52ccb1'
r = 
s = 

H = int(h,16)
inv = gmpy2.invert(H,q)
A = -r*inv
B = s*inv

M = [[q,0,0],
      [A,1/2^384,0],
      [B,0,2^320]]

Ge = Matrix(M)

for i in Ge.LLL():
    if i[-1] == 2^320:
        m = i[0]
        print(long_to_bytes(int(m)))

BabyHNP

from secret import flag
from random import randint
import libnum
import os
assert len(flag) == 44

def padding(f):
    return f + os.urandom(64 - 1 - len(f))

n = 5
m = libnum.s2n(padding(flag))
q = libnum.generate_prime(512)
A = [randint(1, q) for i in range(n)]
B = [A[i] * m % q for i in range(n)]
b = [B[i] % 2**128 for i in range(n)]

print('q = %s' % q)
print('A = %s' % A)
print('b = %s' % b)

感谢Harry师傅提供的题目

$\because B_i \equiv A_im \mod q$，$b_i \equiv B_i \mod 2^{128}$

$\therefore B_i = b_i + k_i×2^{128}$

$\therefore b_i+k_i×2^{128} \equiv A_im \mod q \longrightarrow k_i×2^{128} \equiv A_im-b_i \mod q$

$\therefore k_i \equiv A_im×inv - b_i×inv \mod q$，inv是$2^{128}$模$q$的逆元

$\therefore k_i = A_im×inv - b_i×inv +l_iq$

这里$k_i \approx 2^{384}$，所以$K= 2^{384}$

因为$m \approx 2^{512}$，为了让最后目标向量差不多大，$K/q$这个位置可以换成$\frac{1}{2^{128}}$差不多大的值

exp:

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

p = 
B = [, , , , ]
R = [, , , , ]


n = len(R)

M = Matrix(QQ,n+2,n+2)
inv = invert(2 ** 128,p)

for i in range(n):
    M[i,i] = p
    M[-2,i] = B[i] * inv
    M[-1,i] = -R[i] * inv

t = 1 / 2^128
K = 2^384

M[-2,-2] = t
M[-1,-1] = K

L = M.LLL()

x = L[1][-2] // t
m = x % p
print(int(m).bit_length())
print(long_to_bytes(int(m)))

[HGAME 2023 week4]LLLCG Revenge

from Crypto.Util.number import *
from random import randint
from sage.all import next_prime
from flag import flag

class LCG():
    def __init__(self) -> None:
        self.n = next_prime(2**360)
        self.a = bytes_to_long(flag)
        self.seed = randint(1, self.n-1)

    def next(self):
        self.seed = (self.seed * self.a + randint(-2**340, 2**340)) % self.n
        return self.seed

lcg = LCG()

outputs = []
for i in range(40):
    outputs.append(lcg.next())

with open('output.txt', 'w') as f:
    f.write(str(outputs))

$X_{i+1} \equiv aX_i + b_i \mod n$

$\therefore X_{i+1} = aX_i + b_i + k_in \longrightarrow b_i = X_{i+1} - aX_i + k_in$

HNP问题

构造格

exp:

from Crypto.Util.number import *

n = next_prime(2^360)
x = [...]

Ge = Matrix(QQ,41,41)

for i in range(39):
    Ge[i,i] = n
    Ge[-2,i] = x[i]
    Ge[-1,i] = x[i+1]

Ge[-1,-1] = 2^340
Ge[-2,-2] = 1

for i in Ge.LLL():
    if abs(i[-1]) == 2^340:
        a = abs(i[-2])
        print(a)
        print(long_to_bytes(int(a)))

另外一种格

其中$K = 2^{340}$

exp:

from Crypto.Util.number import *

n = next_prime(2^360)
x = [...]

Ge = Matrix(QQ,41,41)

for i in range(39):
    Ge[i,i] = n
    Ge[-2,i] = x[i]
    Ge[-1,i] = x[i+1]

t = QQ(2^340 / n)

Ge[-1,-1] = 2^340
Ge[-2,-2] = t

for i in Ge.LLL():
    if abs(i[-1]) == 2^340:
        a = ZZ(i[-2] / (t))
        print(a)
        print(long_to_bytes(abs(a)))

未知来源

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

flag = b"flag{xxxxxxx}"
assert len(flag) == 38
p = getPrime(300)
t = 30
x1,x2 = bytes_to_long(flag[:len(flag) // 2]),bytes_to_long(flag[len(flag) // 2:])
A = []
B = []
for i in range(t):
    a = random.randint(0,p)
    if i < 15:
        b = (a * x1 % p) >> (300 - 30)
    else:
        b = (a * x2 % p) & (2 ** 30 - 1)
    A.append(a)
    B.append(b)
print(f'A = {A}')
print(f'B = {B}')
print(f'p = {p}')

A = [463887498379837178289434930796937204555475877586622290749258048874370169798799337104469937, 773107696240723064348524874255963716154847723824140324851906738257594371092025839092322618, 959382311121888872352942066453176913016345159699733628226033809692442378255600652170133603, 1475439387312927400751305948540244549759336332552059673660666894619118830047069015157686938, 849526462831348819335657678027942464464758618063917043187129057068191653250289714276486390, 1334127037206856127523941580821068150671372041649866724020399671459149591275291992977444717, 270665083631525557759154548751201812246030483353898310710004039080238333516013780476382216, 1018902660322104052776222955411066044807125950939527765041383184188103427291053881056928575, 209244905602559751670010690327768486619524571513992042827189611303489897515540986981111728, 1448752767778370938295347623067314667365820805495380149782146153110745097342875410404772323, 259828604923763561672700195721292502767730876290458742290887049867931720014196470106481233, 64955927829662789888801246059321257505518334913081564868033981302809434355859085577340789, 541853690860409175470448997776819435952775864942641589293140819248380415841093286149509439, 1139888865143435145477538463183158820201430904436762627802923622604703492742131126856361559, 1275201358819804049372292362561266777547371187070453684762542985512809430125709931354890689, 369607296264184981154638102500387132578476452666540211313258531786190436544288889435124252, 806708347908045807047609135976903208402075815467445877191713196364943763493569595760618980, 1455987609449801976533130312961654430816056114205781282886620693328977276162282426493869107, 78240737983903215239118749844347047542830586146993600511897384363311151546231920353144287, 178433523161741238741165004364134882377268446191666891015503424004703296483616704501522431, 160833029194895051498255704447576591540146606885321132274228852060778655408117052809405842, 665439140689838885724776126488323057267424913454382363615180272084605737991756925728109752, 1212399960630524647715423021430580541043060607704004760594818883478379710374660040225211737, 1024104693386208450852231949868224748229315263011728008967767316172947909984939303025784616, 1172245617567690331560150298653167704336960464136186977917753583487333782434094205711336284, 783927796969236661199653579569651324291785925516516459946058680074574047025620354913449506, 662785009487244748764576805406718936165913097166011574087131710238816769129253409163197996, 176622195892476124982696054672313827341938528038522227778420609502821124526352064161794848, 1207882741313080019507286406568893562247091201154746129221516369048603742944945854959243209, 865971631872293774191772297150903858147356635890878227481230935983612340880935090288780814]
B = [213262950, 338585619, 651186563, 161224022, 614133782, 358709201, 81465247, 606102220, 333896117, 244095320, 29938894, 126014939, 555731335, 373319033, 662799251, 517458562, 33441774, 922070946, 236657217, 323031182, 143007144, 9082131, 230128400, 805207434, 699486605, 511887222, 957047430, 474639197, 74284022, 547483878]
p = 1515897080671400659075132434127277346281580386706329236487649363388239277840368389427768563

Part1

$\because B_i \equiv A_ix_1 \mod p$

$\therefore B_i = A_ix_1 + k_ip$，把$B_i$分成高低位相加

即$B_{iHigh} + B_{iLow} - A_ix_1 + k_ip$

$\therefore B_{ilow} = A_ix_1 + k_ip - B_{iHigh}$

构造格

Part2

$\because B_i \equiv A_ix_2 \mod p$，题目给出低30位

即$b_i \equiv B_i \mod 2^{30}$

$\therefore b_i \equiv (A_ix_2 \mod p) \mod 2^{30}$，因为 b = (a * x2 % p)，所以可以把模$2^{30}$放里面

即$b_i \equiv (A_ix_2 \mod 2^{30}) \mod p \longrightarrow b_i \equiv (A_ix_2 + l_i\times 2^{30}) \mod p$

$\therefore l_i \times 2^{30} \equiv A_ix_2 - b_i \mod p \longrightarrow l_i \equiv A_ix_2 \times inv - b_i \times inv \mod p$

最后得到$l_i = A_ix_2 \times inv - b_i \times inv +k_ip$，其中$inv$是$2^{30}$模$p$的逆元

$l_i \approx 2^{270}$

构造格

或者

exp:

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

A = [...]
B = [...]
p = 1515897080671400659075132434127277346281580386706329236487649363388239277840368389427768563

A1 = A[0:15]
A2 = A[15:]
B1 = B[0:15]
B2 = B[15:]

#part1
M = matrix(ZZ,17,17)

for i in range(15):
    M[i, i] = p
    M[-2, i] = A1[i]
    M[-1, i] = B1[i] << 270
M[-2, -2] = 2^(270 - 19*8)
M[-1, -1] = 2^270
# print(M.LLL())

for i in M.LLL():
    if abs(i[-1]) == 2^270:
        x1 = abs(i[-2]) // 2^(270 - 19*8)
        flag1 = long_to_bytes(int(x1))
        print(flag1)

# part2
M1 = Matrix(QQ,n+2,n+2)
inv = invert(2 ** 30,p)

for i in range(n):
    M1[i,i] = p
    M1[-2,i] = A2[i] * inv
    M1[-1,i] = B2[i] * inv

t = QQ(2^270 / p)
K = 2^270

M1[-2,-2] = t
M1[-1,-1] = K

for i in M1.LLL():
    if abs(i[-1]) == K:
        print(i)
        x2 = int(abs(i[-2]) // t)
        flag2 = long_to_bytes(x2)
        print(flag2)
        
flag = flag1 + flag2
print(flag)

参考文章

lattice的HNP问题学习_无趣的浅的博客-CSDN博客

浅尝 Lattice 之 HNP-安全客 - 安全资讯平台 (anquanke.com)

子集和问题（HSP/Hideen Sum Problem）

子集和问题的一个实例为<S，t>。其中，$S=\begin{Bmatrix}{x_1,x_2,\dots,x_n}\end{Bmatrix}$是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集$S_1$，使得子集$S_1$的和等于c。

背包密码就是个子集和问题，见另一篇博客

MoeCTF2022——MiniMiniBackPack

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

def gen_key(size):
    s = 1000
    key = []
    for _ in range(size):
        a = random.randint(s + 1, 2 * s)
        assert a > sum(key)
        key.append(a)
        s += a
    return key


m = bytes_to_long(flag)
L = len(bin(m)[2:])
key = gen_key(L)
c = 0

for i in range(L):
    c += key[i]**(m&1)
    m >>= 1

print(key)
print(c)

gen_key生成超递增序列。$c$由背包加密得来，题目把$c$和私钥都给了。

把$c$依次和序列中最大的值比较即可求解

exp:

from Crypto.Util.number import *

key = [1928, 4648, 12352, 24010, 58760, 148406, 441469, 906294, 2347544, 4145527, 13246047, 33012060, 104677731, 233784625, 398671830, 1138569375, 3847891246, 7151230548, 17442630021, 46416620988, 118857237060, 363519789685, 661956375011, 1712300152639, 4761949150147, 8964540458636, 24746310311237, 62452210349278, 150016895989040, 453927852027278, 948923770773559, 3275343477577565, 5756783232753127, 13616706687879089, 26402320025439836, 91814578040763059, 211796919962932717, 385545413311588646, 742071895214889791, 2137385737378343660, 5820500440463297078, 15401185997444609852, 49206779920875282228, 101148479344021765606, 205390946600728256099, 593695571211967641654, 1163476540184124239753, 3920275177926640702128, 11188401781366603668803, 26452211702098700985776, 56612547941955968739356, 176511950177344415872304, 350456159524844834233165, 932655004294881661656249, 3077731648705646793828507, 9127653332576335535543235, 14107124912327219069005253, 53639235705342264540097281, 139903414487199921597126219, 377113327325865137005647964, 797007439689940464465071770, 2456373221352926158802602905, 4997725491122440484756502995, 17601885978368777637676626066, 27945705300453872028061217316, 70259455336271034962808380541, 241339934663279791843376677893, 565927167417896365819102921696, 1498269591024734505946670540129, 4476165672138335294342834148717, 8246962867693878472370951037335, 29609522845816295639745215494800, 71952214344473760246502727717474, 169361817288205588754741757159731, 390045301314759178244461824288458, 1337540279161737220902909199776611, 3221480198479784802709388960779700, 9670513515504338974817616478456700, 16261746247432868145400788404115430, 53594268392537203440232335914792279, 142627442102890550431018293710429426, 249683635647920776857130562696997561, 689878480570146636843962995034183967, 1647889244922264517646376201060969417, 4362391204795633804803911898013660682, 11983025462449787764688227594361812707, 19474005190319410527122673327870913310, 40950423948271412394664153066384954054, 139255978428478610787399242087880835737, 382133188700471370531564036246745271608, 618340037056166043673108074267387394368, 1728641328632513907826054966389623526131, 4246454964077064700888723109771772689322, 7526932088676669848792644586429545161503, 14761773428394206759829134632198244970685, 42336665776969730227150513015344171877811, 73191053942159553542196382411683917861300, 211549032502894704558541919050681697675397, 554709644259380577558971870420849574372151, 1251152425154260246544953154540513290303621, 2818798972367329802956936052623797403793942, 7638358444068983298092603686815486790113890, 24695143882440275994689721479314417528417480, 45729327569890326278523663568847218262894959, 129925286147414817076637512089880305727457533, 357058960265822950281886346091988882031910760, 870811282376277097902073516532006850342152858, 2399129617319427629796691807338852665469337085, 7522497498897836117435156411281203259743818186, 17703808279261898891912155690137638994014567408, 39174398341780347981624886777838524967209728446, 71626422074785376430650030090797947505033373583, 189453667691364649027951065496599754814571374684, 437295033677960022667168340703719574179513440159, 1105022320374390979035499970036715293235993540826, 2482140894382786914874701298953446381142900730227, 7941406921570365260066022237661009338911386179194, 13688077798315662160188528865690475378175919829521, 40118424472696130315297350323559766967889857978364, 105189379969045772302352882060687514329245824860122, 199293659238948607716187263853532082285127398693261, 499536111913922039437392654679505181047127518386152, 1265716378918935998920835568757397506132677689873802, 4251975766094131691018482661130820129953060977929504, 11152957210935036994690757763894857926461579995709364, 29243034751011001056721898400833781278921232465896703, 83127804731558215656517415813913013712630964732885793, 197287313991484123623412111326147421339126168589781103, 580348074469542880297800575176456597744257638809118170, 952848219059546044449261356813174361415872857630315510, 2114745453546299027601967135831843941629758587200332803, 6732303576367127091793491258707612535996916865106486930, 17969751578033370972927234837249484835783104974373526668, 50353964851880252824761483078317672020552394668185625845, 114792749147200000567884552573247130055515068451479473326, 344881289580954366545252182642967036273037618565165401985, 1028830458186445450162354520820201527695218769577051320473, 2074905233540761021629273629118215092544205899770047449244, 6827824489946353955926387525605200460781082737913381690336, 13024891552715019198360589788142658101822141014082307429749, 25961005268769363699702206141880105110265708699262059458918, 75403822308341240881775753922079349096463802345797378834029, 237384123451169596772029918832412849807327730438354057322622, 712646240930595428776240903619042913605109976371239636231758, 1858677703618066892165605509033944664007520745899837556768895, 4139395606166311238767981220233801698454319610253778363314838, 11051661045091733320416016319660914967058929654228453865287281, 29811585925705783247773137027702029276636378622129036803066195, 90685056735716951430085719312184849024248295771954003433442472, 157500945846011120649342030924242308092488581060888955520117740, 372901626023221848769914983494185928870895559258054416488096811, 768231028240804910809905945806694160784354754863882766743917789, 2779285901235347349512412519384436770411460171816095983145397440, 6374104945628711471675855561257403169698347988699930709009388571, 15606620797895735826222569176215400049549335070727802852935792508, 36407286542538484153926148252126040596266900628856973721204544487, 124345134443495254231144676818478910782759198180390061540449975329, 247113740493284619019931820393865652802499920117478290621711932786, 546250851448819627474782890078865878619982888424175090054606739349, 1708592433038733956978819431107564666115535756847903016488985258178, 3469784692808773680977989909012383598601318450115335667599446101916, 10923256812598128494335226092601900716551326610194937277684839542369, 21012491338240214838754959441277560200420746284908398093641375760080, 60889459302270258776558311240916612146241213106331686794170240374762, 163976015330661921425351604828688078789049035481531041973974028089785, 289037863251569623683823097040957275672420698243074506420157297827331, 757077203699594125515581476518783513279367742304415416466493229482750, 2419895647396662523171144180707701121877346566438572088091207837906226, 7355085337963583789485765997525070376210546183075717620390510384848601, 15051216064674860618341980616144084279926804604562228123313569479773613, 27941489504573067317849352242679271094163397351402254909630669501407776, 101620497919142332166787423172023060084593540312322612628746436809445674, 226881723516906947900548874100926330355595061853588440070446478001634192, 436083549067326238210237926429619818583468595956103126733614121273925302, 1114300762650958326100809843235006795980444078921364112608090634574957344, 2067630703150668695099956606446000647289440828791043320265352802856027353, 6184858091099126482135322120120464262653454412363734887325664168742191917, 20198724557091875844715800016163838909724718285368458520056089111628596330, 31016012035612935043240048944310566375654982913771972602093586083253422398, 120517928868495613278649932692310155587627278645665690072538147101563551766, 189853493819940791022006359464978248211780374156959402302888328075135559122, 709261139869078187523368280811328692680117587337216655356117972203528916551, 1494450926662311226674274795483402016068321469408932952124223720040234068030, 4833201522454078687541173754025375255160393643329610440001807389162022858137, 13065426763007211443646416727098859879614516619696845038342383829309179073982, 31498041121702214861734489217437935540479379421202405303460486717862084301294, 59291071262486212405215961522173655254987660557013973769285757104149711757459, 137325620971003240316895273046089454057536316983680621619104742603734626157973, 322033994335205758184753941417891767592538862759074152575171260357782006734442, 820082783566832754339608163235147685713597507674476057203654315048011026367219, 2282651344288337092906883083740075053173109353137863831730238422975306417325757, 5445119536937019732153059574137765564679350539463171899410036275958492350218676, 15640432491440562916581632653853505713511238255286321934711250830601955403677071, 41106883032429969859399906487019322357415120653637758039703350990320596875155176, 103754830954744065029443848605781937050053754534445990149281507972325774765844876, 234666834709268927734887936099822319961738129376455664521947726208265410000264742, 796501101363737180381507228150305361162624877853273443755457607681031102231623307, 1624552917282803716066319956956102765638808948119862597393339135995911391379123522, 4643272637840339310515026952678388354699825180379372281574901801196876030063101974, 12698618143562269391895747140398377495554004174836256597996901873500325652914287227, 35723733467261031422647885542793080310475947027099953899906182407397300154268828906, 66579759042299327879621766658030061118334921216187867761491910504181344451238684350, 239558348723378720363003224968080360385965369779814655734270075126998161979921905000, 674426340811237207208953232785934391016215462902095720638324651170969997400637801355, 1698823780061918718547756106555041994312203433347013142428193591099315938666752495147, 3485698669992831956608280816819201625859973318902236645999324294867314338271763576226, 11913442231481393917536601792582866930393303587594985248503741285895455503031416467367, 23070531945625150855016941245865388154950147453856685413887739256847410892916751249842, 63062109298026246794043518591814177894498277952179449322185515920851203385563000039545, 201500456854818387020432137947274011145636992031847792130877996231861744196691929847748, 386293027342088096708767070123592359264038177654678967794307420131436089009234887958085, 962652147623483170628478119235555226505070396879489339105090935822447174750045231232478, 3035935960793431917350036879195567655285637476975406683996240225461808984868014791791433, 6208746117115824715018162711918248788514776556569667609833722045497831346028332955531410, 11762322147658744239353552479176647603950873433079903790516674882105043434830328826675415, 22679200582127225664793559521091332878355319644677462980823198911465583443269858630893253, 73929710933006149888049977928677968518055319247626886667227984506656971966999436923186972, 122524349818395517581134493004049791722607446965559017459380345881157453828660236992049404, 412926833511789222428174650284405691872834629858851326844087117202853421601692502254318141, 1029385129423499530322969843276842783066057615497035785381633948646265964471244991407283657, 2374019900827890887681448469648598056064267661046120767421848772396302513783495423644064007, 7129046282305997419886465925038724574815350866486395082327924571694995543004421437396685163, 15553684426659575255143733092646126163883808844830770798803864550707886694317293166976752540, 36868510946091898479948303208447807989049331965479662439764899809218618486185846045349542501, 92245655628350120221629636214996850938258802134676165059052497372214318974743615511153118145, 186463470334970062582820387784350511557982560369498424617823476509363037536450250866616200018, 572967521502291777355369990006837729815084981232789335148124013079835565379339449250907380488, 1481745249132912511970258586968019679134485717661841452421417313959912906838055641721186578588, 3465571259266031075485176569236690543411907657240139447438094553546637617425088900258756309108, 8435925081032968505659480326132770316717891729208893135134645312992136104713045209348571379936, 20315655322325100095226141940419414017723560946817780337100296517956534785685937181001107745352, 43069115966613244938070771746304575880400024938295357246717079316564326270692925649165248799853, 154233412749662382894550506472683312102297703424057840129476320316144010040200771168572376219849, 352877164586305833533208196782157198192758667776588081344657867110512140773408077435261431699405, 731939874265903145518316019567169287035472945759023530855697163432627661288949769619402453516834, 2189452024672949178210645600969378516255080271308334836448144354429705327344143994347331957449853, 3896543605375761834186485166037278157701213968430616464967138263870727947226180820650265115757354, 9136364061744114854751740581900554472617621867814569413142650998411332183920873701211555172374338, 31182169589957210510416755511542482029989997938097777712995732237583051643250531461221140115798313, 76737932310662322563271317876920472434982416417386459109415811734811165935978744596464401289256365, 191657687539432627521287232027340814340762593718642860136243059179657356411665753239917046107562015, 530361069831754440835688500919172905456422674539149906219439563860239029311496751350136915275150864, 1387792997020024308183922178096461451972294935906886419345639014544739179094711431002567439046777688, 2286383934503119795216122706571707851067263586234080042542833733216757155431244141022301236049602882, 5217435832596475959525740735112831333306893965389666926215938837589313774349496690036610287629333005, 13857335145208908258169891019385567845284268412333112678215001155302498425490658878264656236992134935, 40163901018471004896425196956916864061977023091787666532481831101052032374062940939516719648018676594, 82892214529323438899501402117098988403652889186148588453800977258361448264060748670322604495661134167, 178956544188555415155972101504345380390695957167910254018903325710948594375512551321503428603501757891, 563888574268395325287659273510106617675959539240732287901035847602904779682730930207201257182213858543, 1616044303623257921514683914498983737627603891472634935907943748930280908786049272784565904600012939098, 2891229181345915888829785513242002484495784340354174828728993457272687483459059048534538302181816688976, 10207730272860940549823879515425309207636840459300447491903147067853625202918689426829904372421061677895, 17526621515916394607402562632381069779604072768221581075247386337947979364802058499395942689207299830365, 55864742839796343168209200305202648507682753148596246337408494037308856790224259497580631081634646188041, 165332196033938201434627346583990806851682965862702414330472648748014088812475559273855488926778988149883, 494729626554411141427744566730794748483202977845760867859438479405205853778032755546761473203576297889449, 773241724058457908926664671814549280391747757602041708672622636112281590651589333985868232639345426359863, 2643090721830219937871980242863893762864524580138013585975903383984399727700467749841537295988160882592554, 7602742125929529736410459828760559621377824926000865839917497433361558637433229365703421216832254559844712, 20298012813427893859751095024917906619591438637592000480476880613738608994530228331797315397345124353458048, 57138113294488937158388285440237932686091901290656714986248760196665994518443306993120321953623611701468826, 156180826248086652580528603931836069088833849466705801833826561589537926864487694377480227882717998855358198, 405091254840842081029125739284610173825182926000756067214428354197290398676973286834323853061720032954965963, 778366116109730017138034746329928058267161795656720444904686750506814152375884477590166274857108289313593118, 1796005150394618766778725965351985496132876507371048438760920669904977557456986675227521156526604287512648264, 3898444018773054695814825596014017751795964177961572987153324103751602074848254485225397417397654262390321944, 10703462078231223004197739814155717950000211259146027443753796966491790618726938276000128782966812980398530204, 18372321975824831177753464245580317968933119357879255869022769977852558056854497414886761863892673585456643891, 48317491803925955550053615386786484989034506042840366819980397407568791721238179125455458641299301269848666510, 158255568588301663954187011445643163738485858122034088577201324726783893231449209827193255340005164973552974453, 456823552578369748946561710072366945172148623875999657195033140013027572670231347304984109456384691884394301596, 707160118481884894551388234729179730915972581073118662214623842056893684770640844231508665861861467073743805665, 2706927376520605764276007802932993151885010075033345167172586198244735154579188535970342536626727165782495180134, 5524495123704893916572931697399108221354633312984253879509446961783982258828184219735409076305664075360213376822, 11902801828947547843316856179728603283371324186706149334180029898787026360919748804787239985463725865632928552507, 42817758358028425898228144386760814695029076486689089958556088081002352872886441780712721026897632438300836110665, 85341298053933033277929612803230545434450389443924565926372394273668666803233325131592974981823970679666528469082, 203545487666526735282497187348232067937848828434866343193810463204944901878674073018178572958556722616056919932826, 404490991972927610287798222030298357859147323959244483279529298622268125169109324278915340735214314234862449055448, 1015889532249910731454157235904076803563143859066636167138222193683905683535906365566683356226160720652109370999321, 2376026683785110886914732723263521678018967831673326233555377196140833492114241003132626058539164015299593970425136, 6462912523501528306439979574464826777892245783057732634021629306276087967421373795532316029843905278328516884883058, 16981441701453104471733297233747957918575727289870879189918428405182537334140409929337675754279869961515500536636176, 37605582989982272328044312175947277729400907856460324692248887357599456103017970584086153023793040540391945445989257, 91747039052675678105959960961981861389020215173307703983752122608163760292472703277085998681706298344337891404847646, 197976695213061406953734629818998754281337862490966315225432914015679415715157795368611025598068494075696354180224057, 407579734020903728451591407903624856111929215373480871243621182164970838186438777218257932637652562832905518769398262, 1192695842629740666007709455549699909835266353292608841275812622248241416280954865990629770667881078271433918923422731, 2356450454926316659685731978750584215969826513728852376452662114206102092287531644004469937748823746129670826796883901, 6606194810680818911726753398369719656427756109429906495763748359459974583720214056977960616895121295259675484772228900, 21238856384108665139068993634246013308212000660518883089302921531246892139968871926076965355331061987385136533519279525, 60431698017667972588320134967121949330864812114211557015977441929363675768812209839204671181454067749535515855713156763, 174665868422753780275604141699079697885219220210916384980421958910804651659162534153721798589901082858559767609552079345, 394230935137659132182806278870718863867754651145064639278806591391259891710009233085853984826856234290081395609225890238, 938316178783979725028510016300351906317832877618969965871296642973988528249289624189564279188734089982984293864940639663, 1690300816950917856165481180579373059665398098127346945618427499442023814975741786872721941536175836912500050716899314350, 4241040212750921734662543578806315663721700243000974307468609317605794291246764526126048318503818177838783905309400289117, 9899615703109749398438558898664002269482804539466079984631091253252047080143600618559486614511675282173378128689947106499, 19072918764217687057379877185516040357999863490449836492311841376572022870447983721729056895047026984202403660270528351362, 61457030295636043956746238914591148777316757448303861396901131680368800892725607851722251866187547310356464672462006792936, 130554685050076234706409249768453974245979757597714789262984612467812333642313018653001831006709360179701213479970689476759, 317707441009141362433020809851971219097475768762476580041791647909345575364794752462683617015215387354639266789655705355159, 766407353781281024676870262720057676902122989643223864583232810528888853102644816087185770633710024110065414129660560848818, 1378158372668635043591303404733183053913783647791091758022520799715774445178343987469574552089574912051263356050601448829569, 2849814783153826557775488037652012659704609417837692209372285071574038848736100379264094051217084360358380745456795092662367, 7761768442678261726960193678894950205212069061687767898603990098871593859918952089239031086652597614705182760193814143657094, 25797856998139398890116390239859835084629679432044893266362900315705828350899796936954893678013444560821963770721738841492762, 45230528787260219469707111504991583088449246785732739036848497764369166856369435663350796527642874763730890628636593210838634, 125595007654406839330037705158661517651788635482067500225344073216015649944944879970130124750959631685921435054581613709164822, 338747508849935686599681561847193572302329804892368313208731993174039023400358858978202514407262943107662339259004212857955666, 927842701337787263386928773903441275979399427379662460065544246411463087320044839262987027337743305220579800532826965270689250, 1974283905173053393614664395812743602970084360210384412934832566684934360366297764438728189449912704403685566054487439810857627, 6547791381850377804871914819409383329722364771877581519586671693693630274474320389311984387956647850854999536112540018330183809, 15709320907036538202306551117984227990557852089499582468594623629463507925701405510011304643762744267804282547349971254508845938, 40270138688478461945314017148044972001708543125646521974155404640273555509873235113536988809551924038925428913961013964565197607, 99168179703900580858922903603323807687115252977021819828415602208147447841271397891925410158445036111494543958823713690209285369, 269868178430265744761277563499719925184037917272176039027995896214226177897366881562687640385414521231482816048831046030643750903, 831659192392583336646613887566957000280656975320208034953861277421104038936580189145699653541798336705409469145595542460062434471, 2073476643694212471632333653958562004434818366225131771845046659755589302151344899589183197864077374128293181680576229954100550419, 4554149306780266313933686119966338774145476827044906188542821462680791576860383095025724314895890630857897398967476576259995321191, 14651118307465336327922062019691151414683570292038775511915021602908118951591926995520466221396947959539039452124967851254379010308, 32590352694473324794187157416677986187287003972605121693147144070229453983956761041980924463747749024664597601177994952136065984811, 81134631049823241301269776481475653931802229294857541846620286653857647735078830230944498091871440739749676625155855958593920070814, 185677119342066492911752180414903294080590111905381979357926969960006994207482364686831869137669282514024709390338951171955152686319, 611640161419871188028819133410469586343996954403636969815202842657504592966769167857498786484339404586484056783483882604337795700345, 1665805557476802274778809527131744615949426833045219219448282924298718975882034660815478936907356513550130652021165488275923832785881]
c = 2396891354790728703114360139080949406724802115971958909288237002299944566663978116795388053104330363637753770349706301118152757502162

m = ''
for i in reversed(key):
    if c > i:
        m += '1'
        c -= i
    else:
        m += '0'
        c -= 1


flag = long_to_bytes(int(m,2))
print(flag)

笔者对这道题进行稍微修改发现，有的序列(数据比较多，可能会导致序列中的数据有一些奇妙的关系)经过LLL算法规划后得到的数据有0，1以外的数据。

MoeCTF2022——knapsack

题目

from random import randint
from Crypto.Util.number import bytes_to_long,long_to_bytes,GCD,inverse
from secret import flag
def bitlength(n):#判断消息长度
	length=len(bin(bytes_to_long(n))[2:])
	return length
def makeKey(n):#生成超递增序列，得到私钥、公钥
	length=len(n)
	privKey = [randint(1, 65536**length)]
	sum = privKey[0]
	for i in range(1, length):
		privKey.append(randint(sum*255 + 1, 65536**(length + i)))
		sum += privKey[i]
	q = 255*randint(privKey[length-1] + 1, 2*privKey[length-1])
	r = randint(1, q)
	while GCD(r, q) != 1:
		r = randint(1, q)
	pubKey = [ r*w % q for w in privKey ]#将超递增序列变为非超递增序列，作为公钥
	return privKey, q, r, pubKey

def encrypt(msg, pubKey):#用公钥加密消息
	cipher = 0
	i = 0
	for bit in msg:
		cipher += bit*pubKey[i]
		i += 1
	return cipher

def decrypt(cipher, privKey, q, r):#用私钥求得超递增序列并解密
	d = inverse(r, q)
	msg = cipher*d % q
	res = b''
	n = len(privKey)
	for i in range(n - 1, -1, -1):
		temp=0
		if msg >= privKey[i]:
			while msg >= privKey[i]:
				temp=temp+1
				msg -= privKey[i]
			res =  bytes([temp]) + res
		else:
			res =  bytes([0]) + res 
	return res
privKey, q, r, pubKey=makeKey(flag)
cipher=encrypt(flag,pubKey)
f=open("pubKey.txt",'w')
f.write(str(pubKey))
f.close()
f=open("cipher.txt",'w')
f.write(str(cipher))
f.close()
print(decrypt(encrypt(flag,pubKey),privKey,q,r))
assert decrypt(encrypt(flag,pubKey),privKey,q,r)==flag

题目已经很贴心给了注释

exp:

import libnum
M = [8639902583677674310880931793028177280541434011292290504202065853840987502967193292082744312615700434593144813157877283996511132107220470301049233647133408049028266415548603044821875100911736779016733764651538561081471760073024901013269329030282540268057926893298880605006783804814169640893918174416684396473085843437738560093104518378524427428449369031845530695254533729875357632791209728472396631069254545688073527219830, 16412795671399200780410369416718200126247920664621109172347415680005387903489020995450209711828570735415943889363228088231729204296365628434015660102046415392160980472272559259705186844881452797719608700810640858964540124307963570631307965212179112567625375169247224532541645290209536697657292517320097861498807160219866672156203488965096062697707956833540149569006121676793811420684019155246005879602727894940460106460425, 1002483078449652086908127901165742700721575695431977944228135611564705696962544084765706920800603400348407970043674673111909948831677555786509139726134228930151292393556003965787320346201469741608940033259208434513230462286500445047749412928990508135782414968218031136356601029216877376563453734566125800306022631214791796995657970239075130824719419551039046131552320134110768030600558391775291997167887552475043961982479, 2238951719129102684908508004589371017508128103247447515477314623396874326632900138922634752384371309915247686376088188378411136513128697780426310438781294619639028237392912133929126286576611773410531662546965371159839695457500259703379712133530424987700108668317058486891872074268472615506849525949557819649248663298510166491366824248526632970988729421252090737838283604158996925358054184183912031175441649168801364477497, 5634843816732445026126467098373466021485769627903521660842347695720253281030482413552009914416263510962518645905534351024856098851613741584157560289954680322367708989388356896291579138242423737071936969416183795417059233168737593374557100712180960324956368186029307481493787661489262846069411165605826200576757012590288649575515313112890878467873797655979953750167348022896037285417957167761342222784479775154484055454300, 9186610770346409723100374171388664935178707704940676612563986340255427150913228007547473624373722376412452006509593871272640178049654772086095028603022475485769195013987324300619058730137213629241547292874688026607272301254060765768412491266856867815505612614998943264567979641302858974943094758843838673682824294909500855339786155131092900834359374160001259207411314769180927212657053081774058447428598226306560920557103, 20086923313584400496691602764043099251746628122644779399842432220366854165950153096939613947370676658491693142658541069764999486380151371297168776865169982649753241182524436613459151210953276528861607793419032177588079933942873702274888793149133043040881921816738144320494857431431348403935934220691400258374550028362585563810770890511960106477474196749665991783492371663595335417853709562030925255330540927197410589197346, 16344638306391326377686133680466529244247158645077173788183670515669569922257628136592428719458630174158247262608062501473710159252996556402841773688479781261071952868217032789112171578864311013133034166125522508960509753908661140291243310989744814838516658654858087285501428760026897645388510723360904014743591560741892432193065079183777716928931428528657537811530112798506687040813493577134938597056885544404165334440417, 2612829152363810360381140114448267548309487113451765642875771138774557011657898432249330366979748000196797448616557121603054240633550483300886876115997009072175661113374511516053173148943538562172144361976376460500609759755722891157667525246977951372954709581129289399522608993482768996162810200357621658110354562179066558050350148834136898974813148680250028733112017355078329753267780915289394014243208598474729032384564, 19064240755529577125292283074595989361230925740751604828791433834485710855856801533155956923513647433086102471927289219051556692578080054437968339223710189223092053257138547582773966036253443266822181812437558595870339679800887565183836282812813501470568462858382546100456455622835475204306486289729917538078517665215080886364990781487301918217104266484901312499340347150623781762028474648151175735340611348792151618766861, 3702565937757268048976391733125277066442618380743768416638899741455818391864276934809663789147326816784849214974228391513975011092043466189181524135072744668991818700123641118048186561731463987428008289526424894229838318750539451785156527758792285754054388512341416769819020768917817009268720412709209493639300206208469077070001276757631341988430056132551557700579907926834862070107929804804811568088452140366936341777345, 11502581665457615587254363930374727534860957412318365767186339391962456747857398825121846821211261108113447361990519412493867120624842707484788658261017505214188933491782380457717248447441244784000616729072274616859314952832500266181433915883265604874701734571473682998617103861022495595430816700108408197717973513190148901952092370293707843130828467727037293783684148539875615050978469354573967054299566840777623355696582, 10073083484226771776559359501269382896512475376861352563707048944846887937508361476948371289888897049589767849211355238137412974054578287303103882003280146530845186837491695691790335230428734898979480016209102240902149523701595231852831084035640546876424433409207622149923419358639246084622889479686948602188084403074936426671633324202401473825907348902812619313043234644293320117923314933945154795101196969895143521199483, 18992409093137046378732842744306503603860785524225852139724096390190053840935906726926035874997131679911084133508187235324077341016070148447808448470772128318056137717495126904574038547394615807743718419710808943840981025768473805273816544440631835254252102209159686821504850348775772310988837820388009691813555637320221225893184839014117064201469792554472415820296766165441072313200265279873167507641917097468147741179316, 12008203894395308866804419286918131211163695386800382803649167279012655799569753801988115828424417187344919188165247175430808022391086771474851545255339167112615263516693822036949280138705995693945006477452686019283850377188419366812168825267599287239756656176060444742334708935226087327402356564944368424241454091730626764098428899236088185072241508877992009374541429500266147060644167717198271648252572069852366770066941, 4038832885441543178685778998777010366178385846540652554740976864087276470059402915973964964623701441198410064422128360212066090056314261540125817743157487504771683739028804039509503547125770628097134761153720275162291365442343531369529592717402946253265532741567152583164953954964898610320442871432658088455178094417777512351495473972183676615716829056159421852585171139955117355872271110823592402383029525931751267792629, 19670194103573995335546778884365243181264524353822662897934014963532181109426494031783122562547168306646340318701174006591358124967291240381472860805618047808677531825042365670594937665873102378022268329092094697067984029740301822623602184731823873558795434660094128877563657141012814479754588351209580370149201870079338556937517586419874603443731575388938047952534772975732556105736933783615623583780757885995121940503338, 448587250547880364312998824100142781832002491807797554233277109625321555526950425023215743109760909527612986436313497543133603769113094218925472945334223939771684911674114594383329812680099071618542069490401164113149299269806494788678936049434267166672312670105320059285800764845917405038243022972683567686862055442132133699091060023879225704166728623235301057086116134392930454897470872517830183804157659700625445889830, 10930161231241723347656392354185186093279947414736961273749133046917264525983266922573827501912949183911557744485967859327719400057117437345731516339396700486673896394578991271601789139805337761538463364911028532947314087595485794633342964066494181066852782300122468958298766435768883484054954993425768743684068334128908076033268101822190508581559994522635605495674677985961570352022867982948658497701704571958572471959037, 8912625957861947176692856854564685913647250060559881612290601882706188054788510505473405766899729572895845562443591906130010557402952386484482517393552180643811875543260186615419673392566496124447912269542460226666482647910551668827648093182498966897648613164572222270243359702963101177490336287533554365928047224202986800381789195759761436787301775857956490336462761874360038594427862527456596260884381704781454223633779, 2306551289216069191130454513919221829895901755421732012054334929893242554080663470365833623647910595823559794161380381203244457273338204281828065815403836409342993408047475650247775548054870518506855112285782988053629107469383261669351486184529190835182475578503456288807168306057143062378581633799682759776120760924076418979302287358897599267369532373529226015751378954828919709070562305354324298101375251784620884529050, 4255339440978927655211913099708439239541744749715858205450532296135993491711072531673546488130525220452788120740747243665720666392815530093014478271039742032112194171931906319993753445172382189426854066713529003995100528854075591430543823563496149091625019122021620407298536429119275536878732816760877148779834810333996516623906435500182034146675214175983106767418866525349482073016790959017939121229158782423051437153215, 9873893139520117327959006627839041532640596084122498183275311439807583416537326867898240112497398037831103133225780536794667751621338906594306093907094491162973280124466357134326208711961138712559043474881854410281347249860558412201637927695809309506382983697195652836773807770471078146063769391274295604089026631661057995193996447578694999955394342030970191038699379802329038272700169720344712485611198818958034826301237, 4765089917604817672113377465925141955529222421516223531063923657154702433478270434880545390917216534893263025759911541042026110573924335888049100333952299835341171480017258706209901577677469866704411013270064823075970967687971507570610839591584275076452847872481076324238205066797040752210320592563122318631044755701635637739646416025765614160810641418286841779812770371444583299208365194975180768006212895673072116522386, 6112224947687945480280239711320637787918908433138683424770734756570826229243307796646495301320885785370269249822669591195293264920047304899609677414526321546201923169183273630074677571673196655278790073365810828842079110549121344560176457524241399552011885247148188807289668163473493287160336470378903648449586092642655607573691920693404111756416187219108551575656506522734845257486376035264495521946081148938719828033544, 195388411930456292659004793034783822168552894119815825793239515251988057168890947473241809393054966668062312553975721264016843250888334146134794233076452609281861146295329070151936139818953601652277333969475084082043879066015009690415217938561659533862830515140741722462773302261048996453107340978194386484615281173964478851257661832707168812221430391245333553374969697275213417090199524308016415986232808953337791233555, 1244720792234771369080092658020249943250558558858543228087410218998345534662117779763183654722069027909843499722901164419943926229796467885376166352837320116084647482129514330031374427777713274658505472735592998618829380710477875259621314494025610959270630909513767438377166574595122721020642680480636508393782145457915510494406492704624711370382819548311152206515088909451187140041316879980487624305109667331613444702397, 17420521136158610155456592286731848541982479314642855401677490675166753515234198487007423812022874870146225072931804869494964153944097179858754058711975536064958198128181259089930184414024073207404745484941865020376185583612084575830698697473861393413223317543665696780708006419160734997175211056844409117770896148029948413413830070992404759100435183372428243532877202421584255843340950511372816896926816072148853459897597, 706903708472011058848699822306335654841601117402541259992980291382595513869156934281756720925440180372041334909766487263157124536984532709278378467802794655209393786719712770166975275570907988257884089016583036566222245762906544594817287350363157701978129672388011595734906479201562800232080436561292648589995413689187423799267922779667354879432847963481081819133273312642100271608294867632390722051556035070483171016618, 13588117928036525396131036929216722140727623626773457297456804642287761920269285941755714752389926502053635244735082938908723844163590227890370507021161665584070634134943166185409041414310104540858882424783436357851264149321701932666540464732095496709151056094385506784810633450577104530541976191745761226361392054647950122452702677055536328206478865891505902190711023934956429659436170984452323755148142827783946983689170, 13035612161448099569620637080527976769991099967659035134135726157510271293484224205316460392491491142810512547489719500384339641597134042306613279002050232752593558311676343579221779534892019944116141753798217189420843176613961166129335180457416469246554334190776482345258322812060613256769751208473952032112714346919765236132411088975889482598477817665407310561133545838921580753339246754910148949146829091161220277523800, 5061468190653798738267114315103277995240484866758940466674688031109170357205008555147400605884432466490013550324043153140916286904706720594942806466313925952519739861008671389738724448491617803723488014434597761423015360791986220671348427679576702646137192962379221866734759953356438405870464423279037434471697115717040170596343588013833231257338815360451128669119488799203334539631159855944659628348586189260831916846349, 310519211081224360436038529767369886079208063233638857045321280938913013264485831500988519083286823510448024911412774486006384354093058665586412478745091555621093880910291350060806527846380258780481452221805321697545098807534406639559969270790330318763674434212070131506363658570473180232691446781542261978745471405470147422634838558227017494138965139937056188221867200916092073501864711946128579149564779783995131812764, 7765454929386860718098457667571027065776365809087712130247806423210057380994819419379356255913567513855445325193098721224960552359712259673134202556374845746328084939006183410638772980553376342740123581295433206004604779839814416843588103144731533226288767681739309033321761816241055963854560413354103299523850186399263379947122808750960631330918177463573091711382789330104148605172305241880223088742424771925359262276961, 21279920209240501229319113350331584665790430778846094897524930483118106031814634260802903045495829850399437278182329574699963138929930179421992737117248479197193414157068700951767757037252093980620859984584071460503299890187279597588828028508209377280155232780973353085622102108867131114851476798667397114731024315266211677829660093151838411660005343321511262290101904600206044359113839043382769572874124915349587253828026, 9404384361847700092017917497360922914422495675694955197107944898045656929107075851201447292136561925215747086463268855004949841022671138446351748131867439799577663701934862965438385718226937668810306608404586652755516424859810792109427278538957262669803852485387086606698225561320268174451728686271748237597096162506211489602963953896833644360026423773017344347726848234574166701592970696201428964781400031197865618239089, 11473536515781570615295467590180776005414036990843757506218537332857260548916287699656257748679485492923976380438772031340714031903195664536413478729735501964060575660816573010818951724268030300190364858009842520160469005602716000106343559079229134105037981332746560515786853914884397058119553354501751785487490141582378799261378484951808914485153056302334467726453053631816737123137188339174736559611576619507335456442065, 6658209986765214576523603095408925684859819107411400320441704339845709232148546095393111386992961430272770760133826876144536472235021040569911199220002850001682157274254019940107808579210365324279421587725318046615758025182034807320964209281952211101801085038313213267840401921768361130482812244634047647201542664623820862660431801687169272410840936474148169852200351846151154823648248871251508145387214557197530965990966, 3662147743842078783350403504385983360536988791880409841594842856902008843747184249906408091065206792255852486983899949749040441757153766073770174862371596437255143770762330535544930819336506298143363720373654482508230603611719528450050592020391695607369389318359724713540160798965029351305356511671756157832414716675860595439627182073770194023818550160188620097391401855031574633727321506854349395990238905940067612856696, 7933293379259371913947753225829182973440327166821331624782742813667530306183685142511569661517697089303221887502895505020874247160719683710997562072608556098407772048528722269678632972762531765385931704290441640393166153819226767175593692496736619644331844236704817294952000150386014066539732697524646127418982668700056812006011572693231332529972933598812433064570022253850176804351568177341485541235602653505364414768080, 14070615118184600860551882213714094275919094443487489248696755809883503918195587018270172984608205938888536939875430264012942369576596527716679396096608215568698430682346516654899828724942187624877959402757540416078645260766852866647428645421972345262477895972147694258806702534022844164408377042363711608742060536759496086945857809612633396792905136739597255654549008843569173238058444402641970915726989105904551420858546, 15342946815132442226042116907050674991277073193801523392169239948932666433020608630679091801966034372511342999029292508497887755004306581018004584285609282795773152090001950867971092852778256889890353738132730167551173577706777310439847369540286505119147781133148801979251138693701919045904692041106260141920375686688488149802396671219316061485675475896415179620183729993314843987100325425615893137781286754296462178178342, 3740152297282187181815345820098735405456007044475540504111210108524926232502982744404912884880365972432141621724673777802787744807157725980349110691844313336431011685019041193074796249612246618677944456394104745372829079160559888495080142311688681340347875401650358392693131033779246448214818537452437421066622719432500713770985665015229700477055550680052280279789072242114276313112192777540668840785267601183144210396020, 10185332676507104923693600244914563536350322909616212746220121432434723035761182080872998830142207437310309114085510373952850103117757585120341980926754941337344093553857422551961676140723291586487782410700709958292644147040988012341985875728853255609738370894663167840784046951024718142033286281019071858182773531406479425092563184020268791578909132566309388794626911391615731256258486251046314500831039355225743436984975]
S = 28856686525748125802152914172483571798453880654624111179873716369801238646447969551927508246737816822527579725991046201801262381722186539084044859241033407568422008911415092147086235301286167536726137372507078079415577358704181165698320539751269992479349480281465975374187246799267369957964807679383646749609694064517591097971225234359495013928292239934008888234863117359059334395043146949808360202225171337210959511092044766

n = len(M)
Ge = Matrix.identity(n)
last_row = [0 for x in range(n)]
Ge_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = M[:]
last_col.append(S)
Ge_last_col = Matrix(ZZ, len(last_col), 1, last_col)

Ge = Ge.stack(Ge_last_row)
Ge = Ge.augment(Ge_last_col)

X = Ge.LLL()[0]
print(X)
ans = []
for i in X:
    ans.append(abs(i))
    
print(bytes(ans))

很典型的用LLL算法通杀背包密码

MoeCTF2021——BBBBBBBackpack

from Crypto.Util.number import*
import random

flag = xxxxx
m = bytes_to_long(flag)

backpack = [1]
for i in range(160):
    backpack = backpack + [random.randrange(backpack[-1]*2,backpack[-1]*4)]
print(backpack)

backpack = backpack[::-1]
l_list = []
for i in backpack:
    l_list.append(m//i)
    m = m % i 
print(l_list)
print(m)

'''

[0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]
'''

已知$L_i = \frac{m}{s_i}$，$m’ = m \mod s_i$

我们可以从中推断，当$L_i=0$时，$m$是不变的，当$L_i = 1,2,3$时，$m’ \equiv m \mod s_i \longrightarrow m’ = m - x×s_i$

而且最后$\frac{m}{1} = 0$，说明最后$m=0$

把$s_i$和$L_i$相乘求和就能得到$m$

from Crypto.Util.number import *

import gmpy2

s = [1, 3, 6, 23, 81, 199, 670, 1844, 5535, 19547, 75437, 259056, 974664, 2399609, 7304021, 18537736, 38733276, 143785607, 300890806, 778420517, 3112554961, 9955080778, 34625138877, 103531993246, 294207209833, 632363887456, 2341888528510, 8736224869982, 33727228149167, 113026240109398, 334534210335245, 754812282783351, 2871232541211362, 7147990367228081, 16813142520913249, 62232346665698392, 132813746566508109, 436969187287191174, 1371311321857557068, 3465499917202578303, 10761115866584374884, 25998484366411649657, 81986464388691181616, 324842980726420787162, 1063428202306999892763, 3318046410585817603032, 12569059003729082352479, 29822650425811094387624, 89829868596281155601134, 207467076929560545986692, 424101883375592006882573, 1410057940679583010646572, 4795250448769489602371933, 12419955465903295439689190, 32127052925660652338148413, 121768246803017981541739592, 286293639144639999224246905, 876618562849333372078886060, 3495370549956845610130431964, 13777448384830441398471073019, 45339968634224370226443992856, 159636974047457043534720001443, 403806399587759901542286515690, 1190949464093267805434271517577, 2625636206558220580206955200643, 5447410189447132699195152662348, 13798370097217657917056458399390, 42652195271813913821236091812630, 87624112365004035907264763291796, 295833079631922620770335225824586, 717255284196409248439771704866883, 2119024457898120787521595829459142, 8097762744600097674390735606807128, 22990496332708170421088808438995636, 55268619563994680834441597248247582, 157779112538179073738464223501777499, 553561084981889545670380643023607621, 2094594867042850711386606235023415160, 7427564397983932982484534762285032864, 28541899514275079822011638819911534081, 59854615377110931361953157015440306520, 137071568336121640486639449884477676903, 434368553369190183317274206512577489165, 1607515956833802196435755021284640023303, 4247439813046769661567823675143526066989, 12252982336388472725165513300377051313644, 43586970358791422986656986286232849952290, 94754002216262928157061686798919700234151, 205403633516427560050027271636224615375855, 727922215919878343821825296552148942903123, 1541646353685774868780093433673052445519807, 5703469721749658936787093922654529457118594, 20762100689139896330208273986505541316962105, 80195197197818086812949239946286778357513961, 198522126001869063688321920177617046841212852, 719060816608760633741229682178956301630549900, 2171712751463320729665634385979825928332317622, 7968526190188064156742281507099763347000210904, 20302513556821857703528100337806260797703562338, 54967103106163860243927426134510653397499429384, 189866376897538250029834405810321956080892995934, 516088075785491414669664215795496674103100750375, 1531616665488077085604100033058238685259376456655, 4795563798371064843556375420641263389159268373753, 12715206263244537077480789152826620386135239585589, 45628223673569886022145657218662773486560769778049, 127988774487590162169660910342623736153210927472871, 429761810968391607465089641939438991272623610573254, 1694286408402338132220805654166083638884822137745848, 5577419986858786911316434594350519553014729018524982, 22146179230778265190752372551893625479326089828877879, 78983119075073724439850825731329386811892547014513513, 165805826557531832743325076551678254671357810872202277, 525687524776397669648788242907896052104054917192402349, 1596680185629512867035574394423929715498386636216930988, 3808351509446054183279144714875260973968494634290203802, 10792542598439044383994436390450612942036864538927761344, 31776077718298264756461043701077481610506447838959767949, 69483787236434708634666641366101673156349500969799745632, 212620878051727200345257734337176214877612639791408110401, 565705372069455623425268706185184158331866127768259060570, 2228971348185635371906791535156337404926063871528397270892, 4859328204121938264839760465087547752629065763656619388434, 14185348803209161448182653444177464165713091554806223414499, 44242932119616103779840255273986809836494122475150635493273, 156176016196847319874949580221731690886061627436916661422852, 472567672907289753186461661432798790751774534772655287936877, 1765317440470718113352833182911767208733594355879647245836603, 5835719030771522391675663002032404790451900100534570526468736, 14528961633147270325279483890277955669830128461595478399405580, 53503137764341373520101774208921450303897226002280491351371881, 153340302591307960181257267214621247064964249027062324798966650, 467036429085212303265974827129085622046910166509299763268535756, 1760478013800716951650816419888923889893355872867499404847043361, 4791886951911545137378952129838133145784256723738609871941913863, 19126760116038883506408830737976498053029475253123685318001466609, 51635927378821965754946959553487670084314385367430813170544188707, 203944552994591250724882161307279862158139878326498083669171922709, 718868928147325949276701359623063723395455731358210896767864810436, 2005627527854915017699090052821431775394584514441537184407714355949, 6108484926321410509000933490330125849664844216966621898372849074206, 15273733259375332107091552084526951416159646708621190826219429490015, 34145117254940196604842578208457005181132408450899191627170638987883, 120825229084143066199868275091825674337472013226784591902132114229359, 387687667198606192147021527980207738864855944986764666796629571317797, 1461874344207808204456192497546273455901754164965322967295868406627707, 3258300231591322626530795072101331694347928535549768492906530809069244, 8874418273687545553519370439384854004509761935319681848589844232674343, 26555971104148502495508475192114409958713364020252024170586326291995544, 56653286369586527413345416396708661964062474995701742952261047069623359, 154383566127721041301459355493059400704799197964228029280865862358894596, 341393868848806018386217706353404785528207249510734290203621418976352706, 1171362524761660822765817023463786914069613269413196584856696440695273738, 4194882148022101614597714583113090146333385168895367467002069867303753334, 10081717223153632058965668126630772845024206141591578024505075742926631137, 39590555580101758090745061229221178837429140073072263518741551403983751377, 124978669991117804453179514660098523434116842472570073354436333226196401318, 285677744249355467333640461312079508294900634926466871637187648581093663108, 685643590088926190360498081484403342771108281930489395367499236756131358960, 2509513194338799699151211958956210034789618340347017416940796124375457114430, 7869725510782496795692771133398729561144872690341264618424961946628895219979]
l = [0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]

s = list(s[::-1])
n = len(l)
m = 0
for i in range(n):
    m += s[i]*l[i]

print(long_to_bytes(m))

2023天融信杯——easybog

import os
import random
from hashlib import md5
from Crypto.Util.number import *

rr = os.urandom(10)
flag = "flag{"+rr.hex()+"}"
flag_md5 = md5(flag.encode()).hexdigest()
print(flag)

m = bin(bytes_to_long(rr))[2:].zfill(8 * len(rr))
p = getPrime(256)
def encrypt(m):
    pubkey = [random.randint(2,p - 2) for i in range(len(m))]
    enc = 0
    for k,i in zip(pubkey,m):
        enc += k * int(i)
        enc %= p
    return pubkey,enc

pubkey,c = encrypt(m)
f = open("output.txt","w")
f.write(f"p = {p}\n")
f.write(f"pubkey = {pubkey}\n")
f.write(f"c = {c}\n")
f.write(f"flag_md5 = {flag_md5}\n")
f.close()

从encrypt(m)，我们可以知道$c \equiv key_i×m_i \mod p \longrightarrow c = key_i×m_i+kp$

$\therefore 0 = \sum_{i=1}^{80}key_im_i + kp - c$

一开始构造

规约后$(x_1,x_2,…,x_{80},k,\sum_{i=1}^{80}key_ix_i+kp-tc)$就是第一行的向量。

理想情况下，第一行向量的值应该是$(x_1,x_2,…,x_{80},k,0)$，其中$x_i \in \begin{Bmatrix}0,1\end{Bmatrix}$

发现规约后的向量不符合要求

改成

两个格的区别在于行列式不同

exp:

from Crypto.Util.number import *
import hashlib

p = 85766816683407427477074053090759168259205489535331001301483049660772943816017
pubkey = [58890813098389592716367918664418237809399998613202441049117852003453550490043, 255886907973292033549191761914277947638378726729170162403000263307778539588, 43666147543837562983744529128391108960442814393989688186615627619841168438881, 2289339843351034938706095739069649849491797527322909177303809837660115875707, 41213482604182795008139260226694469358720652561587117539105919206178583341309, 85123975988270149359269904030278272256150702593339117634318036869051474541673, 38499515653492727036642516425661144597669644770181333309684190745152037999340, 20485509602350760468364550436683434882775269798789922529010411809186809838027, 66201868699675751260618542402171897519442339400362102112029773068389836772496, 5928498980938052035989976608996334019121526162545586177960440867589564370967, 50886730626726574520144515855606763616811548330471900085065588158010347676677, 64024533350992434764550819938965710849249693930938822302806256939206336927327, 38725701074483250591450474606717766666514853596721960873869603150079957176979, 79217343443391443055559755031159399927770013676937883189341106207746097977107, 61550584018851036114215415812034871024308694207855706560554908679054705909070, 18943452821091669663831772224349497605704279324611723330470460453532875854668, 19589987578009659601683539978459498259975975776374959927024576839483511789830, 30455762424330442645213719258885752997650973641135913878741104126501286615202, 58949965807078946897782791856062155685595594220625894016492979510745067947620, 62055731853485887582338078878228949009560282473783423335829652944841334703073, 9968050471897160901950463089357618812125361692340159762344476181267684171496, 82879622776859731032127240994822860125030485017752550449574280896284319539559, 4801338348200265259854446071344823901330707085102509710655971928319789477063, 45731791006706217374257923546738746982354369452894895184784691821888225473116, 67249651561046962535594292263727781436622305014470811080407605464069397278541, 74549581000796086938735007821116567870037873934415647996983670510761843574950, 53927163931460713770577528602376533863752551014779597870421933008696943680646, 56674817179749773825254339411582187056553125580899575215919582277873475282705, 46486618405288541635832334168373891479516241585245833202819962034096805786948, 33438500041468604615663063367413201369385488295864836452725688027946579037027, 67664099966578778667405575319488959391557099474146663546553930271609270514413, 45447815671440655615043306804023843286416205143693188321756314646855229497538, 11725972638697133812198141962081533057131109523301554105107846876476492922863, 64289489702331472745122326714411510149286883423778995697545620572730495023564, 57994575257987111046854716965859364231330618527165005046088441624813910607490, 14668229647185139513680523686559656096579435616501772089580139136432744069528, 17932811002316804580991874481669739042847138206519622106023735880404179858139, 5331195663859739712428554823168168360812478289288952467823046758773036202890, 74552793814948855649083379813894922159371588934498467412076815493098565156965, 44935994020454630627073800850452460158487760266394408710221643505798360283738, 56729956460199305019441584184914729272661532037080935244087594435220086006307, 62039396792619765440106521363503635264208869754554560630026111496679072778122, 2393458745997765849524009470841489934632527663821258015836036776013536950950, 35915327454351624449823951016325751779776476237317012289496757290655725512173, 32606524479615026657452402620774183996842863618201886022072527830448469143354, 63235637104235763521471020678482591762365962539497201272446150774560661623146, 62208964066864651499810642926855154855961192109426476051220581622874074871556, 56823425142073561606336827683244447153122191299012994793162957373419782442861, 60885675233604760515790987357657130734130927344692532134660791434444881730069, 70128263220978378037998154126965802527577393332688627564386146841574995052881, 71018980922731664798406835410011497130959699315348431777949257381109611662531, 12143164079299710577697191074655687226341720767219380493916347970636555672200, 13508918371738967514239962849170666297725816564248068619597724335815422874867, 35455956156846758401498039994914987477656410741995261921339242861566953715810, 69980758495467248406706658186358315365421963514406314839633132920772753269590, 40780609781497584108689952068487274243081363044494223353377248536197342087646, 44867942499383360300066493293729414921480295687316596135570022888723461284905, 82725154870798626926322339306353417520587153667878451856611421219700157524903, 25126631681527477467395254546272084567454410334950820629891182857858739056234, 6951466886617047161399523857762365328179011042304277010521273986635895511090, 76348861623318422648322072872825713398471251831589343473949016976971223635877, 56205107190224957419682681113714452084261733562014707901087589292788540501506, 18117892543394976645523077630904329147251317704285881519049138075260678609853, 44808031105096301006447146332872279574072682041430481888991436113801413524922, 49253422883319286749223459668126849556879848229728760990408851547046135426202, 84189814930926817953967035166781168797567323089104013113646102708978330223462, 47137140069594189485896203757476808738350291684312377044596204628988007490802, 40801572088832002265546622948401731702850273201235765228409527972304470614013, 66031049946459598112632104872606456117378438456948859102185817862671625118362, 81720181560222737179789740743588444616843925127263616533094516919384531350798, 22799062566507850812703708400514738660780510100747243720001217935586864713536, 19636898235593770858368519750634152409107475396982151534080287393055054087250, 29019136605948188309201641456999919579306004440518777086603961225647602320689, 79880698495154758609432245210109366091585969807890967815410904513080769679673, 9333444307040962156247586346311311869921891214405652789959336947220586492578, 5389291816105059661723219597627983160117906098832235782666626188832333763452, 80140247201709476779769310874536378021073864035213177889595402673752593492257, 10265989744904418075184606188771633319731922237097882332727796873595806941649, 28947186543573208323555611612621027283989204690818732739083074045376664847781, 76665830939598023116888796550932971936723367285838797618563918377195976634315]
c = 1381426073179447662111620044316177635969142117258054810267264948634812447218
flag_md5 = "cae8243e01090ccd03a66e3a4c52b7ee"

n = len(pubkey)

Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
    Ge[i,i] = 1
    Ge[i,-1] = pubkey[i]

Ge[-2,-2] = 1
Ge[-2,-1] = c
Ge[-1,-1] = p


L = Ge.BKZ()
ans = ''
for i in Ge.BKZ():
    if i[-1] == 0:
        tmp = i[:-2]
        for j in tmp:
            if abs(j) == 1:
                ans += '1'
            else:
                ans += '0'
        flag = "flag{" + hex(int(ans,2))[2:] + "}"
        flag_md51 = hashlib.md5(flag.encode()).hexdigest()
        if flag_md51 == flag_md5:
            print(flag)

这里使用的是BKZ算法，暂时没有了解

sagemath中的BKZ()可以设置参数，例如BKZ(block_size = 16)，指定了BKZ算法中的块大小。默认情况下是block_size = 20

[第五空间 2021]secrets

import random, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

assert(flag[:5] == b"flag{" and flag[-1:] == b"}")

flag = flag[5:-1]

p = getPrime(512)
secrets = [getPrime(32) for i in range(3)]
a = [getPrime(511) for i in range(3)]

e = [[random.randint(0,2) for i in range(3)] for j in range(3)]

c = 0
for i in range(3):
    tmp = 1
    for j in range(3):
        tmp *= secrets[j] ** e[i][j]
    c += a[i] * tmp
    c %= p

key = hashlib.sha256(str(secrets).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_flag = cipher.encrypt(flag).hex()

print(p)
print(a)
print(e)
print(c)
print(enc_flag)

'''
7920896218820943056702891053785968782942077704655549145065876361907786355057528237061821280280635146678227702121299090049267547565989625947956850127609879
[5159988341992193282580685525745512910538614629527934692498086718630359717994948104271635300443062627349528208661883545208904466234606731357843882012950859, 6335284643679900918720817621948758994408045076082703123014899812263624185305268879304513104269749790342063146501376008458665966651095670658606928517201721, 6076126683981038494289949541335915228950649182831013867715530414744306299113418155691977393469353865827225836608438360416489035800225275307683760086087019]
[[1, 2, 2], [1, 0, 2], [2, 0, 0]]
2262305826865903827781721021939132022253239409560318732728105425007767005455109451147816015758855318893496902119172860305961200859254558917933621119030425
99ff236d4f1e020e6c83cc154e20f71eb510913056d47344b44a87f98664efd3
'''

提取题目信息，发现有点类似于背包密码

已知

构造格

目标是得到

根据$tmp$的大小，让目标向量各个元素的值差不多大，最后应该是构造出这样的格

exp:

#sage
from Crypto.Cipher import AES
from Crypto.Util.number import *
import hashlib
import gmpy2


p = 7920896218820943056702891053785968782942077704655549145065876361907786355057528237061821280280635146678227702121299090049267547565989625947956850127609879
A = [5159988341992193282580685525745512910538614629527934692498086718630359717994948104271635300443062627349528208661883545208904466234606731357843882012950859, 6335284643679900918720817621948758994408045076082703123014899812263624185305268879304513104269749790342063146501376008458665966651095670658606928517201721, 6076126683981038494289949541335915228950649182831013867715530414744306299113418155691977393469353865827225836608438360416489035800225275307683760086087019]
c = 2262305826865903827781721021939132022253239409560318732728105425007767005455109451147816015758855318893496902119172860305961200859254558917933621119030425
enc = 0x99ff236d4f1e020e6c83cc154e20f71eb510913056d47344b44a87f98664efd3
enc = long_to_bytes(enc)

Ge = Matrix(ZZ,[
    [1,0,0,0,A[0]*2^300],
    [0,2^64,0,0,A[1]*2^300],
    [0,0,2^96,0,A[2]*2^300],
    [0,0,0,1,-c*2^300],
    [0,0,0,0,p*2^300]
])

for i in Ge.LLL():
    if i[-1] == 0:
        s12 = i[2] // 2^96
        s1 = gmpy2.iroot(abs(s12),2)[0]
        #s1 = 2328484063
        s32 = i[1] // 2^64 // s1
        s3 = gmpy2.iroot(abs(s32),2)[0]
        #s3 = 2829061799
        s22 = i[0] // s1 // s3^2
        s2 = gmpy2.iroot(abs(s22),2)[0]
        #s2 = 3354920123
        
        secrets = [int(s1),int(s2),int(s3)]
        key = hashlib.sha256(str(secrets).encode()).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        flag = b"NSSCTF{" + cipher.decrypt(enc) + b'}'
        print(flag)

参考文章

密码学学习笔记之 knapsack | Van1sh的小屋 (jayxv.github.io)

A-022.pdf (ieice.org)

背包加密 - CTF Wiki (ctf-wiki.org)

隐子集和问题（HSSP / Hidden Subset Sum Problem）

这个了解不是很深，接触的也不多，

只记得巅峰极客的Rosita有点关系

参考文章：格密码 | Lazzaro (lazzzaro.github.io)

容错学习问题(LWE / Learning With Errors )

给定矩阵A以及带有误差的乘积$\vec{b} = A\vec{x} + \vec{e}$，还原未知向量$\vec{x}$

即求解$A\vec{x} + \vec{e} = \vec{b}$

通过线性方程组的例子，来理解这个问题

当我们在解线性方程组：
$$
3x_1+4x_2+x_3 = 0\
4x_1+2x_2+6x_3=1\
x_1+x_2+x_3=1
$$
可以用矩阵表达

即已知$A,\vec{b}$的情况下，求解$A \vec{x}= \vec{b}$

现在如果增加难度，把这个问题变成$\vec{b}’ = A\vec{x} + \vec{e}$

这个$\vec{e}$是固定数值范围内的一个向量

此时，我们能否通过$A$和$\vec{b}’$的值来还原最初的未知数向量？

利用格可以解决

由$\vec{b}’ = A\vec{x} + \vec{e}$，可得$\vec{e} = A\vec{x} - \vec{b}’$

则有

格基规约后可得右边矩阵，再求解这个方程即可

以例题带入该求解方法的应用

SUSCTF2022——Inverse Problem

import numpy as np
from secret import flag

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

n=len(flag)
A=gravity(n)
x=np.array(list(flag))
b=A@x
np.savetxt('b.txt',b)

根据给出的$\vec{b}$，可以知道n的大小，于是我们便有了矩阵A

因为A是个实数矩阵，而且里面的元素几乎是无限小数，Python的浮点数精度为17位，矩阵相乘后，必然存在精度丢失的情况。

就是说给出的向量$\vec{b}$ 并不满足 $\vec{b} \ne A\vec{x}$，如果直接求解矩阵方程$A\vec{x} = \vec{b}$必然是不对的。

不过可以表示为$\vec{b} = A\vec{x} + \vec{e}$，则有$\vec{e} = A\vec{x} - \vec{b}$

即构造格

不过需要注意的是，这题中，$A_{i,j}$以及$b_i$都是小数，得先乘一个大数再进行规约

最终的格（利用的等式：$t\vec{e} = tA\vec{x} - t\vec{b}$）

exp:

#sage
import numpy as np

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

b = []
for i in open('b.txt','r').readlines():
    b.append(float(i.strip()))

n = 85
A = gravity(85)

t = 10^21
for i in range(len(b)):
    b[i] = -b[i] * t
    
for i in range(n):
    for j in range(n):
        A[i,j] = A[i,j] * t

M = Matrix(ZZ,n+1,n+1)

for i in range(n):
    M[-1,i] = b[i]
    for j in range(n):
        M[i,j] = A[i,j]

M[-1,-1] = 1

e = M.LLL()[0]
flag = M.solve_left(e)

print(bytes(flag[:-1]))

结合爆破

N1CTF2023——e2W@rmup

参考wp:N1CTF-Qualifier-2023/Crypto/e2W@rmup writeup - 知乎 (zhihu.com)

N1CTF2023 Crypto-CSDN博客

2023 N1CTF Crypto Writeups | tl2cents blog

import hashlib
import ecdsa
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from secret import flag

def gen():
    curve = ecdsa.NIST256p.generator
    order = curve.order()
    d = randint(1, order-1)
    while d.bit_length() != 256:
        d = randint(1, order-1)
    pubkey = ecdsa.ecdsa.Public_key(curve, curve * d)
    privkey = ecdsa.ecdsa.Private_key(pubkey, d)
    return pubkey, privkey, d

def nonce_gen(msg, d):
    msg_bin = bin(msg)[2:].zfill(256)
    d_bin = bin(d)[2:].zfill(256)
    nonce = int(msg_bin[:128] + d_bin[:128], 2)
    return nonce

def sign(msg, privkey, d):
    msg_hash = bytes_to_long(hashlib.sha256(msg).digest())
    nonce = nonce_gen(msg_hash, d)
    sig = privkey.sign(msg_hash, nonce)
    s, r = sig.s, sig.r
    return s, r

pk, sk, d = gen()
msg = b'welcome to n1ctf2023!'
s, r = sign(msg, sk, d)
print(f's = {s}')
print(f'r = {r}')

m = pad(flag, 16)
aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
cipher = aes.encrypt(m)
print(f'cipher = {cipher}')

"""
s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
c = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
"""

关键在于是求私钥d

代码sig = privkey.sign(msg_hash, nonce)作用是$s \equiv nonce^{-1}(H + dr) \mod order$

已知$nonce = H_{high} + d_{high}$，$H_{high},d_{high}$分别表示msg_hash,d的高位

于是有$s \times nonce \equiv (H + dr) \mod order$

$\longrightarrow s\times(H_{high} + d_{high})\equiv H + r\times(d_{high}\times 2^{128}+d_{low}) \mod order$

化简一下得，$sH_{high} + sd_{high} \equiv H + rd_{high}\times 2^{128} + r\times d_{low} \mod order$

两边同乘$r^{-1}$得，$sH_{high}\times r^{-1} + sd_{high}\times r^{-1} \equiv Hr^{-1} + d_{high}\times 2^{128} + d_{low} \mod order$

化简得，$d_{high}\times (2^{128}-sr^{-1}) + (Hr^{-1}-sr^{-1}\times H_{high}) + d_{low} \equiv 0 \mod order$

记$A = 2^{128} - sr^{-1}$，$B = Hr^{-1}-sr^{-1}\times H_{high}$

此时原式等于$A\times d_{high} + B + d_{low} \equiv 0 \mod order$

$\therefore -d_{low} = A\times d_{high} + B + k\times order$

即可构造格

实际可以发现这个格的行列式约$128bit$，而目标向量大小也差不多是$128bit$，规约的成功率不高

解决方法是，爆破$d_{high},d_{low}$的高位，使得目标向量小一些

具体操作如下：

此时$d_{high}$和$d_{low}$是128bit，假设$d_{high}$和$d_{low}$的第一位是1，只要把$d_{high} =2^{127} + d_{high}$和$d_{low} = 2^{127} + d_{low}$带入上式

有$-(2^{127} + d_{low}) = A\times (2^{127} + d_{high}) + B + k\times order$

$-d_{low} = A\times 2^{127} + A\times d_{high} + B + k\times order$

此时只需要令$B = A\times 2^{127} + B$

则$-d_{low} = A\times d_{high} + B + k\times order$

上标带1的表示新的变量

爆破时，根据情况修改参数

exp:

#sage
import hashlib
import ecdsa
import gmpy2
from Crypto.Cipher import AES
from Crypto.Util.number import *

curve = ecdsa.NIST256p.generator
order = curve.order()
a=ecdsa.NIST256p.curve.a()
b=ecdsa.NIST256p.curve.b()
p=ecdsa.NIST256p.curve.p()
s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
c = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'

msg = b'welcome to n1ctf2023!'
H = bytes_to_long(hashlib.sha256(msg).digest())
inv_r = gmpy2.invert(r,order)
H_high = H >> 128 << 128

A = 2^128 - s*inv_r
B = H*inv_r - s*inv_r*H_high

for i in range(1,4):
    bin_a = bin(i)[2:].zfill(2)
    t = 128 - i.bit_length()
    a = int(bin_a,2) << t
    for j in range(1,4):
        bin_b = bin(j)[2:].zfill(2)
        b = int(bin_b,2) << (128 - j.bit_length())
        B = B + A*2^t + b
        M = Matrix(ZZ,[
            [order,0,0],
            [A,1,0],
            [B,0,2^t]
        ])
        d_high,d_low = L[0][1],L[0][0]
        d = ((d_high + a) << 128) + (b + d_low)
        #print(d)
        aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
        flag = aes.decrypt(c)
        if b"flag" in flag or b"n1ctf" in flag:
            print(flag)
            break
            # n1ctf{Wow!__You_bre4k_my_s1gn_chal1enge!!___}

参考文章

容错学习问题LWE - 知乎 (zhihu.com)

初探全同态加密之二：格密码学与LWE问题 - 知乎 (zhihu.com)

-------------已经到底啦！-------------

隐藏数问题（HNP / Hidden Number Problem）

WMCTF2023——signin

2023闽盾杯DDSA

BabyHNP

[HGAME 2023 week4]LLLCG Revenge

未知来源

Part1

Part2

参考文章

子集和问题（HSP/Hideen Sum Problem）

MoeCTF2022——MiniMiniBackPack

MoeCTF2022——knapsack

MoeCTF2021——BBBBBBBackpack

2023天融信杯——easybog

[第五空间 2021]secrets

参考文章

隐子集和问题（HSSP / Hidden Subset Sum Problem）

容错学习问题(LWE / Learning With Errors )

SUSCTF2022——Inverse Problem

结合爆破

N1CTF2023——e2W@rmup

参考文章