Chỉ là code một số ví dụ trong [paper](https://eprint.iacr.org/2023/032.pdf) của Joseph vì mình quá lười tạo `Matrix` . Nếu bạn muốn đọc về lý thuyết thì có ở [đây](https://hackmd.io/@nomorecaffeine/r1xstVfxC)
# Knapsnack Problem
## Low-density Subset Sum Problems
> Đề bài : Biết $a_1,a_2,..,a_n$ và $s$ tìm lại $x$
$\sum_{i=1}^n {x_i*a_i} = s$

**Matrix** :
\begin{equation}
\begin{pmatrix}
1 & 0 & \cdots & 0 & a_1 \\
0 &1 & \cdots & 0 & a_2 \\
\vdots & \vdots & \ddots &0 & \vdots \\
0 & 0 & \cdots & 1 & a_n \\
0 &\cdots & \cdots &\cdots & s
\end{pmatrix}
\end{equation}

### Ví dụ
**1-10 (1337 live up CTF)**

from random import randint
from re import search
from flag import FLAG

cs = [randint(0, 2**1000) for _ in range(10)]
xs = [randint(0, 2**64) for _ in range(10)]
xs = [ord(f) + i - (i%1000)  for i, f in zip(xs, search("{(.*)}", FLAG).group(1))]

print(f"{cs = }")
print(f"s = {sum(c*x for c, x in zip(cs, xs))}")

cs = [8508903290440008966939565321248693758153261635170177499193552423579929500027826696702216711413627480472568726828904707392607240309148374882044455682656477650413559779578913981575195542381602155806438946382809049847521263107908111429547314575039079118614485792613461747911710760754291582134293099750060, 10234293217173095983648586990138462404689872504690765936890158736280331352728086141006820545673419953576281340699793983414878095413526583845311613647542879798224462254801103246845064675391113534349390649562211376117941776588135441368773636568930887968431002105334751994385414474789708434897717472259757, 6001064586644974650131784742218587067958465984737568290249286706923485137083921908971767187010824715217158349948368322929900720010489749231105336650564421771867089333709608235963711368415685056362117910529113580811922176651335662802405504434103542105450330213217418470901029864459362153866361049469621, 5859510800336462649673113647904370677448984650623412649303149431740483580968255760095323745895405406649271411277663981671465673293279417168147656423009231087547991428322779036740050269460373254323377738756038706795196225547099530503996157675637620918729310987613041873955654973230573780794437230183289, 8212120161226957435594246142362544687871307206030517377713172267061914524817671684448986080347503212333314134144272096534190656954277299391948626024244379808998220515649968150824587976113971840005858079163744362874678111323034234960076591622752217194796532407435861854992608669653483268713825154541681, 4292538496747452556903766205458518557016170261915268175117554973221631407580344459540989898488936014316805799620957521118332103032738032797936315597220903773140347787977387271254963436603728977128756213671653297994336981775219965231686927050793105808729293803455246360077380768093287937551667515822737, 8583458084429417950887051233123781099671792568724013361916924355046040863544385972858215904752358387759143712618915109914726815547284050405347634520790328222420443989299783668017365846692013464579110450651166600940834254189911732107856656458621485902792541383514622551498513045029193930072821693821256, 927938350277846540058170699346614173130036388369329189433895716040551556863284640834396837739290832786836335265440745786025530973467859153202044442045287145528583412999497854136387626360287750242048999254798532603013016406637079389023297629455299864761196574249382738851682248453939600976884575974199, 4606866838328488359534883828872534448488908284003992208192170511899852596906485417934690617926601159129473558885893097400239110669875450476234618534668886892219546199419412794765402627731086862572263105282498567494065303352715044800789544479262215220148659740517187562922289802434925672447697743660640, 5696622808956926263797513675882969816326582766528835713485415099018508834817057303528828064039948371652175876967703746446602159940653502950606513683435185458750394450192106019388424601807240033502531431423705043713657847236861816929000927218441444067742560786753091009546483807078198791541719979069795]
s = 605466527953516222016485516214431809590993588699320208021845670703468281059947406248463347211427615855012720451029976981068579151311047123161756448068506197424807516350675172131826275005312472029312861168498961728971558322943730466676859739724928104907194812943584226111451426124864722285484117269190235012612078303171378

Mình không đặt output vào code do nó chiếm nhiều chỗ quá , các bạn thông cảm hen :crying_cat_face:
**Script** :

from sage.all import *
def Low_density_Subset_Sum_Problems(multi,result) :
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ , n + 1 , n + 1)
    
    
    for i in range(n) :
        M[i,i] = 1
        M[i,-1] = N*multi[i]
        M[-1,i] = 1/2
    M[-1,-1] = -N*result 
    
    
    M = M.LLL()[0]
    M = [i-1/2 for i in M]
    return M[:-1]
cs = ..
s = ..
M = Matrix(ZZ, len(cs)+1, len(cs)+1)
xs = Low_density_Subset_Sum_Problems(cs,s)
flag = ''
for i in xs :
 flag += chr(i%1000 )
print(flag)

## Multiple Subset Sum Problem
> Đề bài : Biết $a_{1.1},a_{1.2} ,..,a_{n.n}$ và $s$ tìm lại $x_{1,..,n}$
> $\sum_{i=1}^n {x_i*a_{i,j}} = s$
>
**Matrix** :

\begin{equation}
\begin{pmatrix}
1 & 0 & 0 & 0 & a_{1.1} &a_{2.1} & \cdots & a_{n.1} \\
1 &0 & 0 & 0 & a_{1.2} &a_{2.2} & \cdots & a_{n.2}\\
\vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
0 & \cdots & 1 & 0 & a_{1.n} & a_{2.n} & \cdots & a_{n.n}\\
1 &\cdots & 1 &1 & s_1 & s_2 & \cdots & s_n
\end{pmatrix}
\end{equation}
### Ví dụ
Vì mình lười tìm chall nên tự tạo 1 trường hợp như sách giáo khoa để test nhé :smiley_cat:
**Source**

import random 
vector = [random.randint(0, 1) for i in range(20)]
coffie = [[random.randint(2**100, 2**200) for _ in range(20)] for _ in range(10)]
sum_arr = []
for i in coffie:
    sum_arr.append(sum(x * y for x, y in zip(i, vector)))
print(f'{coffie = }')
print(f'{sum_arr = }')
print(f'{vector = }')

coffie = [[912062115919987384541444810508482210431927090979752545690698, 821573233141947908846346806597970855669735877866074482271510, 1021495993793538114348116360093785401813295131506227322032167, 1358732513690502306789918878264783905632141420645301005472549, 1113329540973743318616199862476168897264741394888972545552143, 954454883580610776347318556741083424259444253338627745486894, 453005693455743986311213272624007671325236606557321355048674, 261647908078577814457637728856441752956686910228804347489147, 885902204275133433867745386254044536499233590309437907536034, 651158997510545232315869304246370157225078480557739942917298, 654231095028032060766787486364970338878972425226424337014925, 1472963273849957372354850800545553133931200634763533662235631, 1106303278717548576321886156245841535079341918920047664150976, 1357365200053449259073142952185621847817069841396733615006525, 1090025389581625940209268316975981031953555186423852039017513, 1221000017327042063552857046268693234498618984065360783130414, 1189293180941096431404776639234011929195052775585155271095744, 1192524455484832318975508736406318310678987732682682615661433, 66517656405411575302252991814609773697375392718005906874641, 145888378954923434620403120637081578923705738241469332622118], [850154700720847436499834118333985479271230826681298299668976, 1385405170949937111326328647595377514410855783610561336897021, 140069553287842870567376760377705600963597498467531825127258, 928520425215850798221046840414544513076281655384200134996229, 545010218304867809951384701134647248402228009714318064506655, 1550052441612841113365766047198577427897523293910993413421067, 425966061194567011200390336068672843966563613667347130148237, 365538097699291704957022218059147873435959801980545785584469, 1169672664109239263576475796939683884723336601554711123394372, 332252452721843115958603809113587634021104950959487762793337, 875610282681597069252503204683360268675046295225934581811470, 807317646528843815063003659069734335975650741944305338884078, 2995097603320766435757144556751348894661146124518819293803, 1228345163340913888350583763424984805066609071416951702056675, 1361208305256606974149862230936227971807979906837291995993335, 1068535902214046659721964233037303348754025899867853442327292, 629709875862985210599045649392001671702190489801006873264079, 1362919796336617731497481909224410429676603036521425324629419, 1419518037491811056412752486655127534885927916202125463582765, 440628211189875130031090708317663605890280228989314244301641], [473221729632751948807866261174508000891207317504435018101475, 895331930844320625070457825914803760080572012613690797796218, 272656509279069565952076256254236556131823382733332005100345, 277380628342859254332902114928108410945524192718478960446261, 846636958963360812438343324130120354623503341927104190529254, 157253893035937701343485013283460257774108763899435258130082, 543407273456697428750960006932084260963247735604388602600892, 1548435115599271609681017901536010914530910736339430567184904, 1014012363772650632061164616218038594482324864373745181609243, 753432217424384551000310960306236664070405755388673662435168, 809580035604229527451496429153827739954025855007130518537882, 781928290936405529328595145283263785082354199399543016333403, 665863087338528883828110190585746276646664489709986248064169, 32015342811251849820803870755782912960393209047103029723636, 652752960221625795780658016893867037450441157458803847510658, 1276710156718989240056500161129775163818826982394147729091884, 844373700480670291536785506695223930499667835935575548075924, 1458620578867793313416940211437097671119652214223950132525333, 50127703930296474876605934176244724767797406687310906252621, 1144398143160786250235730907136141145360078869617210049865273], [674944521592805638496967104571131891700815881615612914065213, 272653275413965996966096675168086256761676044009784769968839, 1364131915393045883169485860106475425773029323356142097286159, 320922328051100686581540803752504014235070328311152783350573, 670338902066587941978178888256275544453963532761594164227364, 1584327257320657920333755524649082980273618894259426002735554, 1057181840127956724033134826290025789033802366445299033347304, 1267610402987144387186469929398777628829236558697047377042147, 1203768808105984635438125125619100779308489891822617758185342, 837245428723184393674790194747984165874543144079348966808931, 519888017402629107257886051437676223345701971307641098624400, 1526126332583071750524885044060428442681672967987328474836510, 1599421150571361809708047731604971401919955193127035014464280, 246467183094049337386463294740210551794154634142178442399150, 1457036227900248912534281219079197728745810431206213581085929, 392246388162162089475318651013057884217393898892973391010040, 1423696128059743918185992192898234408019190828176539983768463, 1298229307385306480864178332126732921787940209351300779074094, 277796522569143060574491723913351748186849136744342114722454, 7662759415579580317455972214393171877787817540585725889704], [289339349456214660223148046727482944099298631451566379631845, 533289232911093707031831426245824040297994356398603833235453, 93762600290372131947557895050072765637559849899804738463666, 1256264413653329557874466494756549106675036548932892627417750, 983412553951197080239826095435716983891331119532270206774699, 697382624350902269334311864757298106661790465972749583317993, 952306767379943899757610783448524861210667808660715339569477, 1065038909902695152377636492432500054532723995355692253833238, 399709595031070092316425241630298036809401476397645589227727, 1120264247330659986367424178275555258581205128291774141989775, 1327716572606205255378201749367531444736792549559031868074864, 363493053345407488824560720353951729164527648119832604500675, 519513403413649622792843141160546952493320658355924502392880, 972155733725360036212881140411622111899598043866554722137036, 764044680507696012754705327771099617249768122499449757826775, 1477053425537069520773341758366296615612760593442785588328747, 1226532158422666876953462514468506413885453950356387724734092, 858426669927368290910907810306520376162759756351343919400004, 1520946648256223026028818843727435438681409190494936142483449, 1407038030909149167417953509285942691628986338859275161062091], [918479019387246473336576969699413953339199357608585246719176, 1472440784687160922189082102476523787030744125756516251101364, 1268288769899528307076045315746823220079292730429763081196443, 354381965693460926101763412157796824989926590201707523632037, 1122326826633067298187817509791583872742815600556137951335513, 1222727781608280847332924324600843601208213675836842723238955, 1430814749179517229234203739176132019574297793277822330655940, 842137916476191884185742938438442776589168915479098328107793, 987358417657283609952373773119805609377312788508096387613653, 216414148706592744544023254577486822954291916252645730062393, 149913646952440522795669540231801803901973915287417728219430, 944067899377598282362756940127995979062039343179206350305669, 51265463902515205981005516578595609212869152659065965759132, 394955310089556660467923764866849971751433210261195705477175, 249788557498936099287427453069711012370370726377952153739015, 397647775327523960396960221721889242361025174450228032241254, 110417140143534345523881645643271595477952455892701940119939, 1081717145764022904960996791877529272271358625361860011149992, 619656438334172502098911562874765633703846512013015912945538, 1036961681920897147227741724817003658901298926057331465895202], [1009477072229189137505549178159857646140101558956645511577141, 1193851542817642602524553682044576973235473695357919375849458, 1466354888630870707475794846896722890766245778597239230034690, 468869119939881557665429858394307641960635869078516569220933, 1313771753409871670942247775180087881582125655385451239875111, 1251509833388678669977611776734755010592827216900151184996826, 116210906418572089165969561248924433274992967390477350548529, 799772807800222381593080341248979915664750789020733985670734, 100088714556955715803877355122208018310424760835985135907077, 882955782699581727511269897985855396489183382581117051170038, 362263368708365189918995167328040017372295344149695695077280, 935018352508497468332881823271549865403016785367695560766058, 1099925678497306504509036812370026082314395723631328811647221, 265240367958124577047702301165748645547716486228682547053084, 1605905710988753982086970018386164686211609827093398747169911, 1093341571303035817924691896126391527672451202146161487072726, 449650039894659068498854452237336599503897999646318996555476, 566328283953907630777853703379161087973155823474645531244786, 1525797421486765156940091887907420659883831762948455166305154, 1162580643036630390208392590710890496167587580594844377736271], [43999632580735654392639151306346828632797872384069202512114, 897465159117969265181825117365956080346874701987475928438141, 497501867380408926396473787941835111017876702620397470221067, 1088793297565063806031162951855161422962589367290219675516383, 72234889088838423975504778825126140477538584235220299610279, 203885266870807389425458650806971436875770022412287257511743, 1352133487992103253872506704855300317800681596585020576898312, 419657623707470326283494946643413726818919180715871475708667, 149630394335485440802763080510719147807495718143289775491686, 493171927587559366480306625142628777494429600221600604180512, 1008052523029985489779614989161051710163136412170117732020148, 671129151594635086797499369313410900037259625981745129368416, 1499961904977292329310835861161497267945021662144863097352477, 1303330082609446999335606572341351755499510169455054543912812, 802529595543363193191811861635303485309602508429142844689317, 754010573609874390288553751515245666631062807531485701723439, 1140004597985831439212424799905293294983376531819145202744219, 543073667798309619552303626076274651634676307474021532708831, 1306091770638848955690820846631772407109228453749244498059485, 860103190652065967912821464484094105052562598152762896149234], [1483452049797143554733662466615358230978573289255432673087734, 154966233565412418445805994691213146552820275964196331905941, 1102269140473348615367074869989659102098582183976969564818105, 212858097979744844814137826476123329237758796550670786081870, 289210744717001510787632830799665368404147775513407360194574, 1171128859013772615795878976911801385920655903801347159920216, 1131109857425975145427204511006917263479313156640348354981665, 330001848432325291322819041003870594722770050088103014240230, 1101150611204055380988816320198744572371620357102285710358588, 445364631729417688690949715049524705042076041718891369658749, 1505698005465778601425498398332570095150172356285270931881594, 1386952941665070141294011440136484826267790286714705426674932, 1386188691051032999173540649575736127899964162470823779642840, 935516090926695170703432506184625053435505711333418616847338, 1063403055405969999155765958627569392490184382459878340161570, 961675845196680924737451416044250440313193167447751691723355, 895424250853782010852320322914298827387495293252534009356458, 1565915517734761879262065662029012799038495524353285450622956, 306621580987391370864283823176531422599906118823306014960789, 1354593154629260678143040578059991867671071141682400204195552], [1441725925176555761068257411651865329561282487516689416771704, 878116549066894818554611986033368311940928966483354211059399, 172754496901694683114165281337124367794666310570638950415942, 1487288206637483442494142685621828338976542984143639843555336, 1185064488063689715556227444010685629526432123450586310046608, 1152293405351603994682049024298233899022174956766617403747884, 918913416227070010784433403690797902932838421950078155859871, 1030675450082818968474041170651616471636379262631489632824500, 1549573462809488634886260451058906543590079583297306413615990, 569669884445093214110027087402403217693335914009261913209968, 342743163014916034351585582622289949960633736459349428081190, 1563094414553728579609729602462220564551744969707368463719298, 1097834818288147795231192075853177159016072467974168270230961, 716212988602781108443171504954941541776775777812592798125875, 705002688900608733067504524072356588726991158405886477998309, 949520702502112467744669862867629489846883441590340379987590, 887635585839182876902021471707700065553586828965183890345416, 319635036564857810749567772521873354539976942943706141750325, 1211247229811010581730838619441564116131943444273895265630924, 656464328216062221606322531591629710791054515201549050536525]]
sum_arr = [8705414783051364589913504775757336628209237606465756826174870, 9647337001213530956933559771654503317421945736503706117659901, 7055276041248584587543343744375712851505843071543362629151898, 8491117760583580031450253441775961192791953600239842710257112, 8033130492234399939813066093058322066113209911179220610326651, 8271649153935749180167282683554494967501988904197583049486444, 9704121708637729958709388106870298719988245883079982723236527, 7524026807258092821342232351443346421309516386214735223219501, 9416752958321383342915246868143356887568052024129337030204520, 8341771079872220385872199360876388317537497582705559686062555]
vector = [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]

**Script**

def Multiple_Subset_Sum_Problem(multi,result) :
    n = len(multi[0])
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ,n,n+1)
    
    
    multi = Matrix(multi).T
    tmp = Matrix([1/2]*(n+1) + [-N*i for i in result])
    M = M.augment(N*multi).stack(tmp)
    
    
    for i in range(n) :
        M[i,i] = 1
    M = M.LLL()[0][:n]
    M = [i-1/2 for i in M]
    return M
coffie = ...
sum_arr = ...
vector = ...
vec_res = Multiple_Subset_Sum_Problem(coffie,sum_arr)
assert vec_res == vector

## Modular Subset Sum Problem
> Đề bài : Biết $a_1,a_2,..,a_n$ , $p$ và $s$ tìm lại $x$
$\sum_{i=1}^n {x_i*a_i} = s (mod p)$

**Matrix** :
\begin{equation}
\begin{pmatrix}
1 & 0 & \cdots & 0 & a_1 \\
0 &1 & \cdots & 0 & a_2 \\
\vdots & \vdots & \ddots &0 & \vdots \\
0 & 0 & \cdots & 0 & a_n \\
0 & 0 & \cdots &1 &p \\
1 &1 & \cdots &1 & s
\end{pmatrix}
\end{equation}
### Ví dụ
**Read between the lines (Crew CTF 2024)**
**Source**

#!/usr/bin/env python3

from random import shuffle
from Crypto.Util.number import getPrime


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

assert len(FLAG) < 100

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

shuffle(encoded_flag)

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n{e = }\n{c = }\n')

Bài này thì phương trình ta có dạng :
$c = \sum_{i = 0}^{N - 1} b_i \cdot (i + \mathtt{0x1337})^e \mod{n}$
Nhưng mà ta chưa biết hệ số của nó tức $(i + \mathtt{0x1337})^ \mod{n}$ , nhưng mà i nó là vị trí của các phần tử trong flag thôi nên nó chạy từ $0->x$ , mình chọn là 100 . Giờ đây đã có hệ số thì lập `Matrix` như trên rồi giải thôi .

def Modular_Subset_Sum_Problem(multi,result,modul) :
    multi.append(modul)
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = matrix(ZZ, n + 1, n + 1)
    
    
    for i in range(n):
        M[i, i] = 1
        M[i, -1] = multi[i]
        M[n, i] = 1
    M[n, -1] =  -result
    
    M = M.LLL()[0][:-1]
    
    return M
n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623
multi = [pow((i + 0x1337), e, n) for i in range(100)]
flag = Modular_Subset_Sum_Problem(multi,c,n)
for i in flag :
    try :
        print(chr(i-1) , end = '')
    except :
        pass

Để giải bài này chuẩn thì ta nên thêm các hệ số `N` và `1/2` vào , nếu không ta sẽ gặp trường hợp như trên . Ví dụ như nếu mình đặt `M[n,-1] = result` thì nó sẽ trả ký tự đầu tiên là `98` , nếu là `-result` thì `100` . Trong khi kết quả đúng là `99` :disappointed_relieved:

def Modular_Subset_Sum_Problem(multi,result,modul) :
    multi.append(modul)
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = matrix(QQ, n + 1, n + 1)
    
    
    for i in range(n):
        M[i, i] = 1
        M[i, -1] = N*multi[i]
        M[n, i] = 1/2
    M[n, -1] =  -N*result
    
    M = M.LLL()[0][:-1]
    M = [i-1/2 for i in M[:n]]
    return M
n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623
multi = [pow((i + 0x1337), e, n) for i in range(100)]
flag = Modular_Subset_Sum_Problem(multi,c,n)
for x in flag :
    try :
        print(chr(x) , end='')
    except :
        pass

## Multiple Modular Subset Sum Problem
> Đề bài : Biết $a_{1.1},a_{2.1},..,a_{n.n}$ , $p$ và $s$ tìm lại $x$
$\sum_{i=1}^n {x_i*a_{i,j}} = s \mod p$

**Matrix**
\begin{equation}
\begin{pmatrix}
1 & 0 & 0 & 0 & a_{1,1} & a_{2,1} & \cdots & a_{n,1} \\
0 & 1 & 0 & 0 & a_{1,2} & a_{2,2} & \cdots & a_{n,2} \\
0 & 0 & \ddots & 0 & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 1 & a_{1,n} & a_{2,n} & \cdots & a_{n,n} \\
0 & 0 & 0 & 0 & p & 0 & \cdots & 0 \\
0 & 0 & 0 & 0 & 0 & p & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & p \\
1 & 1 & \cdots & 1 & s_1 & s_2 & \cdots & s_n
\end{pmatrix}
\end{equation}

### Ví dụ
**Source**

import random 
from Crypto.Util.number import *
p = getPrime(256)
vector = [random.randint(0, 1) for i in range(20)]
coffie = [[random.randint(2**100, 2**200) for _ in range(20)] for _ in range(10)]
sum_arr = []
for i in coffie:
    sum_arr.append(sum(x * y for x, y in zip(i, vector)) % p)
print(f'{p = }')
print(f'{coffie = }')
print(f'{sum_arr = }')
print(f'{vector = }')

p = 88433019574061216376365286374102989235609912086517923736515886544797096814041
coffie = [[43009675503284166577453812202882141198490979912669469678501, 967674907373806119792120185587113757663095182772592913139338, 1399531445979835827557520787604690587581888582580628808350841, 477808519043026430259911611229995677979175844827616248317949, 518642503747742275520906958451523371762082799746681973874608, 877195827742376503865928358770312489929866837697518613989079, 1182930647866704451077428268189436166679126216768964925182758, 998715945374260607398833320924468427541543761171515796026810, 1258148413484936762436280768626834471027151815272435489662543, 1093565509282218114856532933680401047639894822832806635785826, 149485235282876938952243189491763907769270494534542789649841, 1376623973160503935860040767745488278069724486212755491943694, 560271979880668959968302756629711010435862870236528271897206, 93824896440633894702640856532318896766384433733009875299398, 983386584640598734180776689549055480467090187081217045474605, 1527805979661086971991764924788802429157677432365705964834543, 628475309114658852797425598311744555760854773902818203962373, 920003759849212467671480557814117668802406596834037581042294, 515424906453841357270663351604498771145151182140070028663833, 553830404373208664660627642971260685749108686243525180697599], [777842887222823116430883293232694900124339870023804999440069, 419549962900912798758917091000511183989030320857596031762376, 1527435276272443158751407603286768228610628115557862998264005, 223440221823649675121920042399466562150152939976577490063026, 1249896048907598134376713815118458201120040936298922504067464, 1072387323542692891308936364654082947311090893152845724311089, 1217335495323300459277544296862541715731296030874978985464017, 229333768245471947300196026780620401935525581026713504025583, 187975301634766361423778789309201564389846066905138415498239, 420797951255401681066310569780691856732501801965898330223501, 736834689031446989876306113820294047723018474924326766474251, 1203354280116850669982796114771285624986438161652333080159844, 1199282682825901299737766452866162587261201632337105204300492, 987101793306168176044574294161820655344092626214006356189835, 451145294859053969662765698342874637988336517908347231850017, 333647611095897330934306797817960676631024753968115625553314, 1040525333785258440654223956045454104594474366626721568571453, 523594695555603158231002487263587028600859466094156765827449, 976962669578115470899915437854517953987725622682573063313251, 314313748985517254425124788200062420354717360979473954975697], [1192259307625962342198257669079533682039187657945832852560778, 377327698981668523819487730175730465282907560526594122974194, 201579865934078457357195579976821789881961859258538421599203, 252735223320025797990652945841209918300648919199431204146634, 120149536751113358071456146145721354501008983689908455546732, 413407572486455105443669973277438227087188906403590797741774, 217432871962839705807542575785339671586167609247966779130105, 1086588153086592206426096263196360404764221808627059284164778, 443697237631732384152949317936417477366359107473339941406636, 1450921826843475202655059662678039419267518929261346920439212, 1526222839409454675768574988695425309562744791538096545698743, 522749065659359242435208515574629366548784072968267119911342, 460006643549059434187017491858686989301361004640789988553322, 1107289809888247441532414422505668947606949547532807398811121, 274784642922313197425185065181071721837796556487025646530707, 77086116225639074029753735576371073905203007679802360096891, 602432777031363218616749683905540372802851361671254143863091, 180149932014131482383583225752788798162688252316241751182540, 1446939555234105732184286908144255472120263713986659680612823, 780596467961404845998229004036242730253769413405899623444876], [1283445886819653881464145371113435340038388560153586001636426, 855524992369724542782253979420599020466033280653266049629064, 556674721806494980842385426748015807399773370103279673890774, 928682220969189838917684430042575415794663979152704722011943, 539890514150906922219776685703400696380897318938375185486319, 1240383789686194592290714412301068206714532626936698190786434, 1337159320046135873782794997877952562428520849027139482567894, 219466803237229955484055275363679781971086766763868647660033, 590937082836461595602182586299326140149003550942037622731825, 311341157649702949050631533227055812199636107936390422849535, 144920981061754486229054363210658377176811043797521880544550, 254361130650727899036962559806217549383882490915221907479575, 1557379308739352701286768720747402173941363004546119376180588, 934661411816134765947321345015169309256380542640354217357907, 1174252983063033443791241999733355516509643843022185513727755, 1189737336217409810769345621524164843950343837492383054890878, 749580066388993446062667874298197744327405457421899391952730, 302356073328952555635869151928596386846516714797919103876347, 1521223240878402094539534840813265514679522649095340540597650, 1341773554733063471349581803815376330174024643250645601335842], [759697589956554335642144195678665792688453660369833182883234, 663460700128970332147444362535563361149119511148886889174303, 821855481430729665937980428922154278099690667369762204079259, 900377383623757327832638874940952008588184160777158429512396, 1287023375652543780646531675550640571732806978669560967143114, 843580853793774157282739624527280257807549785747804584815996, 947149269234250601418942258430209720658263175747751976747557, 420504126043942133862261835562211603780370587687920120272115, 1254978182128067016273865009220696912938286558580974421900423, 1386080173216576644832329096789323653996601439757166939302813, 846479544491165057271750444506592527805323223216274261534568, 870200333771908656556199205748861495730963024772040978644955, 322130882990951873659215334938690060388365178285909196358151, 241014827785817730185514125054556197851531646364457031935970, 166976428145769036955134321999581015201934851227904697179845, 531594571398589402718539952396856670725673184968499850885813, 321186757547127739319530558336132817944109155375017559440800, 1222583026863855642325818491773006782478541117268002053008531, 1099987793838093859844471769957512002820833290014268353620103, 215029108958681131217178032447189203652663698543035673580549], [129011382193664943832624009934722596949888488102693104581815, 603561499646403192263012125959875029611245681377206933496152, 1350226719239848809473494442954791829665981527163363957733091, 1259066407864503264971245675014012290256965500819415461275279, 353056147495974812746104810168714650607011720598003947241501, 1332770493962774859018305894461535432566368359676097341207251, 240671558863218382942981988413470061180632206260218640176844, 1002209072359706405553081635087275749898760604386050959494964, 1311945449376768723839342753613360163932098805005236845731287, 595916044906235569538833807416487410586409748150774575963169, 1532659728311292752627053450077958781299905930347858225874519, 22997967417527615012053642131315259327606612856357010331855, 251658325278396199299370474344537231690561336312385511107420, 494822843182003718621710078045173831144999432890992043794142, 207540157261264729799274158164779771714928261872829857395419, 1040141273533057509447195945263325339144933725689045667566813, 381034619101269463432558343915797970487335315639464866256020, 39802157917554136886756271288869636159018041797218543359022, 1180851059146618096096785861643096176598055029985122242595071, 279380224432755307013241964156878184385201439392053672163985], [934761435640017691633844363071635698888269422064212102603895, 245813458651918731045566429891079310617779681635069157826359, 1017196481744398790237622266000078939537388344616907890539044, 1409924140838810674825382944768200735812217841318803720517456, 420228736467640799161020074026397890598701040674400373320196, 233092587292174986674041420009954841347571465988558124989965, 386246768845439864089671633091718910753253445258112125653114, 631740401237699103545528089255978900683522967186432330526588, 626617045916800735309917654659212050674858423999256567511031, 1387560898127539533163611102425642697170117870994576192292056, 1036940395951751438855007792395341844758333655579834318949872, 661002031633793525078118820882375069978085887405849161112510, 59963402163766989275184413450586337240169346964553050133281, 884788502849519349794807141419571733532101152786027871084726, 100695751100062902588269343912582799620823086263505667009391, 185004969778665252977243089685453806081360696529293590047241, 493681030022855628993566226421592129745590766135430875123583, 1384984937160696477265041778394005669037511928832718362687343, 264269826574305062611445086684871051941467029764503240359249, 186759466090842635530492548436349273515758662757762152456065], [819732012689967479687665740396921541292463616314598404393091, 731008548552412366745862445286257817005422512721905003473338, 659401368063490465890270407825309351070937783191910142534526, 620550640873996364843180779081604826558308150881698279154350, 562401544777687177522050850632370533283113962622889526210481, 798167177427791490121647480905462180066197512858618370173121, 576959410312318399676381623530784632050073078844923456885634, 578225572899883437052653160622861124855468778680019589314412, 104432110831706368303499935595459932356987324671822616398438, 344339654818489960090040387774400188328086715136032015129988, 265606015922517009857994572797828475100287164888466902622386, 1242012003932849163978340042058384840594210682251422326255758, 133316365384135901449824674791616247615073624053634791659676, 1249593634193216742962674950631107683190231927159303013092636, 160511334347251117865477157228682703282754421886133662707572, 1217538768134321507293058778845046129949855106498029594257504, 1321772481610929495766726053941804051500035412186176987444823, 1084437326148958625378030267361983961882365171490223076058244, 582525420597159392333117245688699836494367868773400519373743, 324175988143394874043753832467703486980255675945060820592637], [874382133775164019683668380686570221742903459173932823455614, 1230372691698781297127880013151321562645387151059829281736650, 398910725438867396112652995995158447848967603833886988634918, 1250390784257246406411857500378612379877583260493695256614495, 29412062187050360675481124300509437689082936504711235734738, 564797535631961550095464264862045053314326238664492836237829, 1485735498537617879673211065226707530247331814908047958075789, 1210121506169427733311305725713136047706589550935427003945386, 175268611084902485650242461366331400752786443877490786919257, 759785638050074431658067312936498645563812124659621399537584, 1149112696967181484873926019835113259795295121613473982618974, 744997950820077158455002892435871006106283970575649240640230, 5430339184661675619742972130423665834727175137694383909300, 1005636817047119124800020489357272207473310000173046042956828, 1418781847223876339582227227385463443639952209853187967706129, 24462617764936034890615690542736623943076491635330255109398, 400170039085236952852004680543867953704008437586661800850717, 1187750030564704442495440340992298551574454751993647596460163, 780443690883710409339932140536084445739461150163937582423219, 310757531157645633983085983218428540876687795141951397531011], [273590127611142140403075276732085205373551060574162895220977, 534984153390098298313787295856758998021030022068457729056949, 143866633740902239403016559532557189450765122597577737697609, 1441472724657522997135405876805082540875240894737896478588938, 618875272256605638077693738731446363730302229430575756428043, 1280186339324926485902907701214435749918391369248149403349273, 369028644670682305964127894628184829787462491990180256549757, 659658564380502629010251905505036397581930123484813604982841, 1428507850061535840495724141381701250990918961385030136260849, 1361796650561867079073638232007677643338591537335024910139096, 130312406602428877993469623579175576170401441546927212013445, 1079891812185927028529301527650227031144855638247485394898611, 219971141937550444525751443774191906837208637702383864637624, 651024857696740151410039997435329733479386356314040848434023, 42627780993735399691991278144386972301999500986942788721613, 478350124836785803647347391440587100007755444686653861386293, 1289246663738727209464729691219973013937717503637165986438518, 2103457929565513851558622729107441343456477934084872687943, 1463456394508512267219357759488597304446582817584660348254488, 266557188487218841429546462858262734391144573688047100795011]]
sum_arr = [6858862919360658122475205732026455839836731976544145414909459, 5445005670054213253081883572447760681718289490255720366623261, 3540104967209979855869806991286189670420978902341993424154614, 5638216515248226355707928649725221295694996076329167665769234, 5131081383308663537920941625875125873154858833338829334251722, 4290967121614179380357284325985798822853698668552333307302385, 4882156164260291146213755321330545889976582059199264839430097, 3891139915972625340862995894046255974454793890122736220915208, 5808669976673584704967430914413349151516713495613564518779306, 4824610897467603486672892213770882281969691353675768903740440]
vector_ = [0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0] 

**Script**

p = ...
coffie = ...
sum_arr = ...
vector_ = ... 
def Multiple_Modular_Subset_Sum_Problem(multi,result,modul) :
    n = len(multi[0])
    n1 = len(result)
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ,n,n+1)
    
    
    multi = Matrix(multi).T
    M = M.augment(N*multi)
    for _ in range(n1) :
        tmp_ =  Matrix([0]*(n+1) + [0]*_ + [N*modul] + [0]*(n1-_-1))
        M = M.stack(tmp_)
    tmp = Matrix([1/2]*(n+1) + [-N*i for i in result])
    M = M.stack(tmp)
    
    
    for i in range(n) :
        M[i,i] = 1
    M = M.LLL()[0][:n]
    M = [i-1/2 for i in M]
    return M


vector_check = Multiple_Modular_Subset_Sum_Problem(coffie,sum_arr,p)
assert vector_ == vector_check

Mà đoạn code ```n1-_-1``` nhìn dấu `-_-` cười vl =))
## Code
Kết thúc phần `Knapsnack` ở đây . Tổng hợp code :

from sage.all import *
def Low_density_Subset_Sum_Problems(multi,result) :
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ , n + 1 , n + 1)
    
    
    for i in range(n) :
        M[i,i] = 1
        M[i,-1] = N*multi[i]
        M[-1,i] = 1/2
    M[-1,-1] = -N*result 
    
    
    M = M.LLL()[0]
    M = [i-1/2 for i in M]
    return M
def Multiple_Subset_Sum_Problem(multi,result) :
    n = len(multi[0])
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ,n,n+1)
    
    
    multi = Matrix(multi).T
    tmp = Matrix([1/2]*(n+1) + [-N*i for i in result])
    M = M.augment(N*multi).stack(tmp)
    for i in range(n) :
        M[i,i] = 1
        
        
    M = M.LLL()[0][:n]
    M = [i-1/2 for i in M]
    return M
def Modular_Subset_Sum_Problem(multi,result,modul) :
    multi.append(modul)
    n = len(multi)
    N = int(sqrt((n+1)//4)) + 1
    M = matrix(QQ, n + 1, n + 1)
    
    
    for i in range(n):
        M[i, i] = 1
        M[i, -1] = N*multi[i]
        M[n, i] = 1/2
    M[n, -1] =  -N*result
    
    M = M.LLL()[0][:-1]
    M = [i-1/2 for i in M[:n]]
    return M
def Multiple_Modular_Subset_Sum_Problem(multi,result,modul) :
    n = len(multi[0])
    n1 = len(result)
    N = int(sqrt((n+1)//4)) + 1
    M = Matrix(QQ,n,n+1)
    
    
    multi = Matrix(multi).T
    M = M.augment(N*multi)
    for _ in range(n1) :
        tmp_ =  Matrix([0]*(n+1) + [0]*_ + [N*modul] + [0]*(n1-_-1))
        M = M.stack(tmp_)
    tmp = Matrix([1/2]*(n+1) + [-N*i for i in result])
    M = M.stack(tmp)
    
    
    for i in range(n) :
        M[i,i] = 1
    M = M.LLL()[0][:n]
    M = [i-1/2 for i in M]
    return M

Viết đến đây là mình phải ngồi lại từ đầu để xóa bớt mấy cái output testcase ở trên vì nó chiếm nhiểu chữ quá :crying_cat_face: , giảm 1 phát từ 70k giống 42k luôn mà :joy_cat:
# Hidden Number Problem
> Đề bài : Biết $a_1 , a_2 ,.. a_n$ , $m_1,m_2,..,m_n$ , $p$ . Tìm lại $\alpha$
> $\beta_{i} - t_i*\alpha + a_i = 0 \mod p$ ($\beta < B < p$)
> Với $B$ là số ta tự chọn

**Matrix**
\
\begin{pmatrix}
p & & & & & \\
& p & & & & \\
& & \ddots & & & \\
& & & p & & \\
t_1 & t_2 & \cdots & t_m & \frac{B}{p} & \\
a_1 & a_2 & \cdots & a_m & & B \\
\end{pmatrix}

## Ví dụ
**Code**

def hnp(a,t,B,p) : 
    
    assert len(a) == len(t)
    x = len(a)
    
    M = Matrix(QQ,x,x)
    for i in range(x) :
        M[i,i] = p
    M = M.stack(vector(a)).stack(vector(t))
    M = M.augment(vector([0]*x + [B/p] + [0])).augment(vector([0]*(x+1) + [B]))
    
    M = M.LLL()
    return M 

Challenge : `No random no bias` - Cryptohack - ECC

from hashlib import sha1
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randint

G = generator_256
q = G.order()

FLAG = b'crypto{??????????????????}'


def hide_flag(privkey):
    x = bytes_to_long(FLAG)
    p = curve_256.p()
    b = curve_256.b()
    ysqr = (x**3 - 3*x + b) % p
    y = pow(ysqr, (p+1)//4, p)
    Q = ellipticcurve.Point(curve_256, x, y)
    T = privkey.secret_multiplier*Q
    return (int(T.x()), int(T.y()))


def genKeyPair():
    d = randint(1,q-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey


def ecdsa_sign(msg, privkey):
    hsh = sha1(msg.encode()).digest()
    nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}



pubkey, privkey = genKeyPair()
hidden_flag = hide_flag(privkey)

sig1 = ecdsa_sign('I have hidden the secret flag as a point of an elliptic curve using my private key.', privkey)
sig2 = ecdsa_sign('The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', privkey)
sig3 = ecdsa_sign('Good luck!', privkey)

print('Hidden flag:', hidden_flag)
print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
print(sig1)
print(sig2)
print(sig3)

Output

Hidden flag: (16807196250009982482930925323199249441776811719221084165690521045921016398804, 72892323560996016030675756815328265928288098939353836408589138718802282948311)

Public key: (48780765048182146279105449292746800142985733726316629478905429239240156048277, 74172919609718191102228451394074168154654001177799772446328904575002795731796)

{'msg': 'I have hidden the secret flag as a point of an elliptic curve using my private key.', 'r': '0x91f66ac7557233b41b3044ab9daf0ad891a8ffcaf99820c3cd8a44fc709ed3ae', 's': '0x1dd0a378454692eb4ad68c86732404af3e73c6bf23a8ecc5449500fcab05208d'}
{'msg': 'The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', 'r': '0xe8875e56b79956d446d24f06604b7705905edac466d5469f815547dea7a3171c', 's': '0x582ecf967e0e3acf5e3853dbe65a84ba59c3ec8a43951bcff08c64cb614023f8'}
{'msg': 'Good luck!', 'r': '0x566ce1db407edae4f32a20defc381f7efb63f712493c3106cf8e85f464351ca6', 's': '0x9e4304a36d2c83ef94e19a60fb98f659fa874bfb999712ceb58382e2ccda26ba'}

`EDCSA` thực hiện ký các `msg` với random `K` , điểm `G`, và key `d` trong 1 ECC đã biết với order là `p` .
Trong đó hoạt động ký - `sign` sẽ được thực hiện như sau :
- Hash `msg` gọi là `m`
- Tạo 1 số `k` ngẫu nhiên
- Tính điểm $R = d*G$ rồi lấy giá trị `x` tại điểm đó , gọi là $r$
- Tính $s$ với $s \equiv k^{-1}*(m + r*d) \ mod \ p$

Vậy ta có :
$s \equiv k^{-1}*(m + r*d) \ mod \ p$
$k*s \equiv m + r*d \mod \ p$
$k \equiv s^{-1}*m + s^{-1}*r*d \ mod \ p$
$k - s^{-1}*m - s^{-1}*r*d \equiv 0 \mod \ p$
$k - s^{-1}*r*d - s^{-1}*m \equiv 0 \mod \ p$ (Phương trình hiện có)
$\beta_{i} - t_i*\alpha + a_i = 0 \mod p$

Vậy mảng `[t]` của mình sẽ là các giá trị $s^{-1}_i*r_i$ và `[a]` sẽ là $s^{-1}_i*m$

**Script**

from Crypto.Util.number import *
from hashlib import sha1

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)


P = E(48780765048182146279105449292746800142985733726316629478905429239240156048277, 74172919609718191102228451394074168154654001177799772446328904575002795731796)


T = E(16807196250009982482930925323199249441776811719221084165690521045921016398804, 72892323560996016030675756815328265928288098939353836408589138718802282948311)


sig1 = {'msg': 'I have hidden the secret flag as a point of an elliptic curve using my private key.', 'r': '0x91f66ac7557233b41b3044ab9daf0ad891a8ffcaf99820c3cd8a44fc709ed3ae', 's': '0x1dd0a378454692eb4ad68c86732404af3e73c6bf23a8ecc5449500fcab05208d'}
sig2 = {'msg': 'The discrete logarithm problem is very hard to solve, so it will remain a secret forever.', 'r': '0xe8875e56b79956d446d24f06604b7705905edac466d5469f815547dea7a3171c', 's': '0x582ecf967e0e3acf5e3853dbe65a84ba59c3ec8a43951bcff08c64cb614023f8'}
sig3 = {'msg': 'Good luck!', 'r': '0x566ce1db407edae4f32a20defc381f7efb63f712493c3106cf8e85f464351ca6', 's': '0x9e4304a36d2c83ef94e19a60fb98f659fa874bfb999712ceb58382e2ccda26ba'}

r1 = int(sig1["r"], 16)
s1_inv = inverse(int(sig1["s"], 16), E.order())
r2 = int(sig2["r"], 16)
s2_inv = inverse(int(sig2["s"], 16), E.order())
r3 = int(sig3["r"], 16)
s3_inv = inverse(int(sig3["s"], 16), E.order())

msg1 = bytes_to_long(sha1(sig1["msg"].encode()).digest())
msg2 = bytes_to_long(sha1(sig2["msg"].encode()).digest())
msg3 = bytes_to_long(sha1(sig3["msg"].encode()).digest())


def hnp(a,t,B,p) : 
    
    assert len(a) == len(t)
    x = len(a)
    
    M = Matrix(QQ,x,x)
    for i in range(x) :
        M[i,i] = p
    M = M.stack(vector(a)).stack(vector(t))
    M = M.augment(vector([0]*x + [B/p] + [0])).augment(vector([0]*(x+1) + [B]))
    
    M = M.LLL()
    return M 

a = [r1*s1_inv, r2*s2_inv, r3*s3_inv]
t = [msg1*s1_inv, msg2*s2_inv, msg3*s3_inv] 
p = E.order()
B = 2^160
M = hnp(a,t,B,p)
print(M)
r1_inv = inverse(r1, E.order())
s1 = int(sig1["s"], 16)
 
for row in M:
    potential_nonce_1 = row[0]
    potential_priv_key = r1_inv * ((potential_nonce_1 * s1) - msg1) % E.order()

    if G * potential_priv_key == P:
        print('Found')
        pr = potential_priv_key
        break

Vậy là ta đã tìm được lại private-key , tự làm nốt nhé :wink: