# !/usr/bin/env python# -*- coding: utf-8 -*-# @author: yjp# @software: PyCharm# @file: exp.py# @time: 2023-01-12 20:57
p=65428327184555679690730137432886407240184329534772421373193521144693375074983
q=98570810268705084987524975482323456006480531917292601799256241458681800554123
c=0x4e072f435cbffbd3520a283b3944ac988b98fb19e723d1bd02ad7e58d9f01b26d622edea5ee538b2f603d5bf785b0427de27ad5c76c656dbd9435d3a4a7cf556import gmpy2
from Crypto.Util.number import*n = p*q
u =pow(c,(p+1)//4,p)
v =pow(c,(q+1)//4,q)# sp+tq=1
s = gmpy2.invert(p,q)# (p^-1) mod q
t = gmpy2.invert(q,p)# (q^-1) mod p
x =(t*q*u+s*p*v)%n
y =(t*q*u-s*p*v)%n
print(x)print(long_to_bytes(x%n))print( long_to_bytes((-x)%n))print(long_to_bytes(y%n))print(long_to_bytes((-y)%n))
背包密碼 首先根據(jù)m,w的范圍求出l的值為198,那么列表的元素就都確定了。 接著b = [w * i % m for i in a]=>b0 = 2w %m => b0 = 2w || b0 + m = 2*w 嘗試一下,解出w[0] exp.sage
m =1528637222531038332958694965114330415773896571891017629493424b0 =69356606533325456520968776034730214585110536932989313137926c =93602062133487361151420753057739397161734651609786598765462162w =(b0)//2# w = (b0 + m)//2a =[2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904,9223372036854775808,18446744073709551616,36893488147419103232,73786976294838206464,147573952589676412928,295147905179352825856,590295810358705651712,1180591620717411303424,2361183241434822606848,4722366482869645213696,9444732965739290427392,18889465931478580854784,37778931862957161709568,75557863725914323419136,151115727451828646838272,302231454903657293676544,604462909807314587353088,1208925819614629174706176,2417851639229258349412352,4835703278458516698824704,9671406556917033397649408,19342813113834066795298816,38685626227668133590597632,77371252455336267181195264,154742504910672534362390528,309485009821345068724781056,618970019642690137449562112,1237940039285380274899124224,2475880078570760549798248448,4951760157141521099596496896,9903520314283042199192993792,19807040628566084398385987584,39614081257132168796771975168,79228162514264337593543950336,158456325028528675187087900672,316912650057057350374175801344,633825300114114700748351602688,1267650600228229401496703205376,2535301200456458802993406410752,5070602400912917605986812821504,10141204801825835211973625643008,20282409603651670423947251286016,40564819207303340847894502572032,81129638414606681695789005144064,162259276829213363391578010288128,324518553658426726783156020576256,649037107316853453566312041152512,1298074214633706907132624082305024,2596148429267413814265248164610048,5192296858534827628530496329220096,10384593717069655257060992658440192,20769187434139310514121985316880384,41538374868278621028243970633760768,83076749736557242056487941267521536,166153499473114484112975882535043072,332306998946228968225951765070086144,664613997892457936451903530140172288,1329227995784915872903807060280344576,2658455991569831745807614120560689152,5316911983139663491615228241121378304,10633823966279326983230456482242756608,21267647932558653966460912964485513216,42535295865117307932921825928971026432,85070591730234615865843651857942052864,170141183460469231731687303715884105728,340282366920938463463374607431768211456,680564733841876926926749214863536422912,1361129467683753853853498429727072845824,2722258935367507707706996859454145691648,5444517870735015415413993718908291383296,10889035741470030830827987437816582766592,21778071482940061661655974875633165533184,43556142965880123323311949751266331066368,87112285931760246646623899502532662132736,174224571863520493293247799005065324265472,348449143727040986586495598010130648530944,696898287454081973172991196020261297061888,1393796574908163946345982392040522594123776,2787593149816327892691964784081045188247552,5575186299632655785383929568162090376495104,11150372599265311570767859136324180752990208,22300745198530623141535718272648361505980416,44601490397061246283071436545296723011960832,89202980794122492566142873090593446023921664,178405961588244985132285746181186892047843328,356811923176489970264571492362373784095686656,713623846352979940529142984724747568191373312,1427247692705959881058285969449495136382746624,2854495385411919762116571938898990272765493248,5708990770823839524233143877797980545530986496,11417981541647679048466287755595961091061972992,22835963083295358096932575511191922182123945984,45671926166590716193865151022383844364247891968,91343852333181432387730302044767688728495783936,182687704666362864775460604089535377456991567872,365375409332725729550921208179070754913983135744,730750818665451459101842416358141509827966271488,1461501637330902918203684832716283019655932542976,2923003274661805836407369665432566039311865085952,5846006549323611672814739330865132078623730171904,11692013098647223345629478661730264157247460343808,23384026197294446691258957323460528314494920687616,46768052394588893382517914646921056628989841375232,93536104789177786765035829293842113257979682750464,187072209578355573530071658587684226515959365500928,374144419156711147060143317175368453031918731001856,748288838313422294120286634350736906063837462003712,1496577676626844588240573268701473812127674924007424,2993155353253689176481146537402947624255349848014848,5986310706507378352962293074805895248510699696029696,11972621413014756705924586149611790497021399392059392,23945242826029513411849172299223580994042798784118784,47890485652059026823698344598447161988085597568237568,95780971304118053647396689196894323976171195136475136,191561942608236107294793378393788647952342390272950272,383123885216472214589586756787577295904684780545900544,766247770432944429179173513575154591809369561091801088,1532495540865888858358347027150309183618739122183602176,3064991081731777716716694054300618367237478244367204352,6129982163463555433433388108601236734474956488734408704,12259964326927110866866776217202473468949912977468817408,24519928653854221733733552434404946937899825954937634816,49039857307708443467467104868809893875799651909875269632,98079714615416886934934209737619787751599303819750539264,196159429230833773869868419475239575503198607639501078528,392318858461667547739736838950479151006397215279002157056,784637716923335095479473677900958302012794430558004314112,1569275433846670190958947355801916604025588861116008628224,3138550867693340381917894711603833208051177722232017256448,6277101735386680763835789423207666416102355444464034512896,12554203470773361527671578846415332832204710888928069025792,25108406941546723055343157692830665664409421777856138051584,50216813883093446110686315385661331328818843555712276103168,100433627766186892221372630771322662657637687111424552206336,200867255532373784442745261542645325315275374222849104412672,401734511064747568885490523085290650630550748445698208825344]b =[w * i % m for i in a]n =len(b)L = matrix.zero(n +1)for row, x inenumerate(b):L[row, row]=2L[row,-1]= xL[-1,:]=1L[-1,-1]= cres = L.LLL()print(res)