背包密码 | W'Blog

醉漾轻舟，信流引到花深处。

整体流程

参数

私钥为一个超递增序列 $\left { an \right } $，满足 $a_i>\sum{k=1}^{i-1}a_k $

模数 m，满足 $m>\sum_{i=1}^{n}a_i$

乘数w，满足gcd(w,m)=1，

公钥为 $ \left { b_i \right } $ ，满足 $b_i=wa_i \pmod m$

加密

设明文为 $ \left { v_i \right } ，v_i\in\left { 0,1 \right } $，

$c\equiv\sum_{i=1}^{n}b_iv_i \pmod m$

解密

$v=w^{-1}c=\sum_{i=1}^{n}v_ia_i \pmod m$

v = c * inverse(w,m) % m
# a = [pow(3, i) for i in range(64)]

m = ''
for i in reverse(a):
	if v >= i:
        m = '1' + m
        v -= i
    else:
        m = '0' + m

造格

1 2	import math math.log2(b)

常规格：

$L=\begin{bmatrix} 1 & & & & b_1\\ & 1 & & & b_2\\ & & \ddots & &\vdots \\ & & & 1&b_n \\ & & & &-c \end{bmatrix}$

因为$(v_1,v_2,\dots,v_n,1)L=(v_1,v_2,\dots,v_n,0)$，所以$v=(v_1,v_2,\dots,v_n,0)$是一个格点

优化格：

$L=\begin{bmatrix} 2 & 0 & ... & 0 & b_1\\ 0 & 2 & ... & 0 & b_2\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & ... & 2 & b_n\\ 1 & 1 & ... & 1 & c \end{bmatrix}$

$(v_1,v_2,\dots,v_n,-1)L=(2v_1-1,2v_2-1,\dots,2v_n-1,0)$

先浅浅记录，后续更新

例题

[2023羊城杯]MCeorpkpleer

题目描述：这数据都不全要怎么计算呢？

题目

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


def pubkey(list, m, w):
    pubkey_list = []
    for i in range(len(e_bin)):
        pubkey_list.append(w * list[i] % m)
    return pubkey_list


def e_cry(e, pubkey):
    pubkey_list = pubkey
    encode = 0
    for i in range(len(e)):
        encode += pubkey_list[i] * int(e[i]) % m
    return encode


p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = getPrime(64)
m = bytes_to_long(flag)
c = pow(m, e, n)

e_bin = (bin(e))[2:]
list = [pow(3, i) for i in range(len(e_bin))]
m = getPrime(len(bin(sum(list))) - 1)
w = getPrime(64)
pubkey = pubkey(list, m, w)
en_e = e_cry(e_bin, pubkey)

print('p = {}\n'
      'n = {}\n'
      'c = {}\n'
      'pubkey = {}\n'
      'en_e = {}'.format((p >> 435) << 435, n, c, pubkey, en_e))

'''
p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
en_e = 31087054322877663244023458448558
'''

题解：

方法一

超递增序列

1	list = [pow(3, i) for i in range(len(e_bin))] # len(e_bin) = 64

背包密码，上面常规格构造

$(e_1,e_2,\dots,e_n,1)\begin{bmatrix} 1 & & & & b_1\\ & 1 & & & b_2\\ & & \ddots & &\vdots \\ & & & 1&b_n \\ & & & &-c \end{bmatrix}=(e_1,e_2,\dots,e_n,0)$

其中 $b_i，c$ 都是已知的，那直接就求得明文，也就是此处的e了

还有一步是常规的已知p高位攻击

exp：

b = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
c = 31087054322877663244023458448558

n = len(b)
L = Matrix(ZZ, n+1, n+1)

for i in range(n):
    L[i,i] = 1
    L[i,-1] = b[i]
L[-1,-1] = -c

res = L.LLL()

for i in range(n + 1):
    M = res.row(i).list()       # 取矩阵的每一行，转换成列表
    flag = True
    for m in M:
        if m != 0 and m != 1:   # 背包密码的明文 v 不是 0 就是 1
            flag = False
            break
    if flag:
        e = M
       
for i in range(len(e)):
    e[i] = str(e[i])
e = "".join(e)[:-1] 	# 注意看上面构造格求出的结果，最后面多了一个0

from Crypto.Util.number import *
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
p0 = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464

kbit = 435
PR.<x> = PolynomialRing(Zmod(n))
f = p0+x
x = f.small_roots(X=2^kbit, beta=0.4)
p = p0+int(x[0])
q = n//p
e = int(e,2)
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))

# DASCTF{T81I_tPPS_6r7g_xlPi_OO3M_6vyV_Rkba}

方法二

利用超递增序列的性质求出e

m = getPrime(len(bin(sum(list))) - 1)
list = [pow(3, i) for i in range(len(e_bin))]
w = getPrime(64)
pubkey_list.append(w * list[i] % m)

test：

from Crypto.Util.number import getPrime

e = getPrime(64)
e_bin = bin(e)[2:]
list = [pow(3, i) for i in range(len(e_bin))]
m = getPrime(len(bin(sum(list))) - 1)
print(len(bin(sum(list))) - 1)

模数m是比超递增序列 list 的总和还要大的，本地测试可以发现模数m是一个102bit的数，远比64bit的w大，所以可以直接求出 w为公钥的第一个数

m就直接两项gcd得出， $km=w*list_i-pubkey_i $

exp：

from Crypto.Util.number import *

c = 31087054322877663244023458448558
m = 4522492601441914729446821257037
w = 18143710780782459577

v = c * inverse(w, m) % m
a = [pow(3, i) for i in range(64)]

m = ''
for i in a[::-1]:
    if v >= i:
        m = '1' + m
        v -= i
    else:
        m = '0' + m

e = int(m, 2)
print(e)
# 15960663600754919507

后续步骤同上

补充：

2024-07-20

from Crypto.Util.number import *

c = 287687761937146187597379915545639385740275457170939564210821293233370716878150576
key = [1, 2, 87, 99, 190, 380, 760, 1702, 3350, 6712, 13302, 26669, 53257, 106512, 213212, 426262, 852583, 1705083, 3410164, 6820581, 13640909, 27281818, 54563749, 109127508, 218254958, 436509851, 873019897, 1746039768, 3492079367, 6984158992, 13968317822, 27936635563, 55873271257, 111746542368, 223493084736, 446986169472, 893972338944, 1787944677888, 3575889355776, 7151778711750, 14303557423366, 28607114846668, 57214229693336, 114428459386792, 228856918773559, 457713837547023, 915427675094046, 1830855350188252, 3661710700376344, 7323421400752912, 14646842801505675, 29293685603011275, 58587371206022773, 117174742412045483, 234349484824090806, 468698969648181659, 937397939296363271, 1874795878592726601, 3749591757185453143, 7499183514370906547, 14998367028741812852, 29996734057483625898, 59993468114967251756, 119986936229934503501, 239973872459869007099, 479947744919738013939, 959895489839476027878, 1919790979678952055983, 3839581959357904111739, 7679163918715808223719, 15358327837431616447319, 30716655674863232894717, 61433311349726465789458, 122866622699452931578804, 245733245398905863157495, 491466490797811726314990, 982932981595623452629980, 1965865963191246905260222, 3931731926382493810520182, 7863463852764987621040623, 15726927705529975242080987, 31453855411059950484161974, 62907710822119900968323970, 125815421644239801936647918, 251630843288479603873295836, 503261686576959207746591710, 1006523373153918415493183613, 2013046746307836830986367190, 4026093492615673661972734253, 8052186985231347323945468456, 16104373970462694647890936894, 32208747940925389295781874025, 64417495881850778591563748059, 128834991763701557183127495888, 257669983527403114366254991760, 515339967054806228732509983520, 1030679934109612457465019967093, 2061359868219224914930039934133, 4122719736438449829860079868450, 8245439472876899659720159736935, 16490878945753799319440319473651, 32981757891507598638880638947330, 65963515783015197277761277894728, 131927031566030394555522555789579, 263854063132060789111045111579109, 527708126264121578222090223158048, 1055416252528243156444180446316096, 2110832505056486312888360892632193, 4221665010112972625776721785264450, 8443330020225945251553443570528835, 16886660040451890503106887141057670, 33773320080903781006213774282115477, 67546640161807562012427548564230882, 135093280323615124024855097128461699, 270186560647230248049710194256923398, 540373121294460496099420388513846796, 1080746242588920992198840777027693592, 2161492485177841984397681554055387246, 4322984970355683968795363108110774528, 8645969940711367937590726216221549105, 17291939881422735875181452432443098117, 34583879762845471750362904864886196180, 69167759525690943500725809729772392360, 138335519051381887001451619459544784838, 276671038102763774002903238919089569616, 553342076205527548005806477838179139174, 1106684152411055096011612955676358278348, 2213368304822110192023225911352716556750, 4426736609644220384046451822705433113446, 8853473219288440768092903645410866226907, 17706946438576881536185807290821732453830, 35413892877153763072371614581643464907890, 70827785754307526144743229163286929815519, 141655571508615052289486458326573859631099, 283311143017230104578972916653147719262229, 566622286034460209157945833306295438524626, 1133244572068920418315891666612590877049074, 2266489144137840836631783333225181754098066, 4532978288275681673263566666450363508196132, 9065956576551363346527133332900727016392264, 18131913153102726693054266665801454032784553, 36263826306205453386108533331602908065569081, 72527652612410906772217066663205816131138180, 145055305224821813544434133326411632262276342, 290110610449643627088868266652823264524552684, 580221220899287254177736533305646529049105368, 1160442441798574508355473066611293058098210736, 2320884883597149016710946133222586116196421472, 4641769767194298033421892266445172232392842944, 9283539534388596066843784532890344464785686063, 18567079068777192133687569065780688929571371951, 37134158137554384267375138131561377859142743902, 74268316275108768534750276263122755718285487804, 148536632550217537069500552526245511436570975608, 297073265100435074139001105052491022873141951360, 594146530200870148278002210104982045746283902576, 1188293060401740296556004420209964091492567805360, 2376586120803480593112008840419928182985135610512, 4753172241606961186224017680839856365970271221024, 9506344483213922372448035361679712731940542442048, 19012688966427844744896070723359425463881084884096, 38025377932855689489792141446718850927762169768220, 76050755865711378979584282893437701855524339536412, 152101511731422757959168565786875403711048679072824, 304203023462845515918337131573750807422097358145648, 608406046925691031836674263147501614844194716291296, 1216812093851382063673348526295003229688389432582797, 2433624187702764127346697052590006459376778865165617, 4867248375405528254693394105180012918753557730331006, 9734496750811056509386788210360025837507115460662129, 19468993501622113018773576420720051675014230921324265, 38937987003244226037547152841440103350028461842648406, 77875974006488452075094305682880206700056923685296910, 155751948012976904150188611365760413400113847370593722, 311503896025953808300377222731520826800227694741187444, 623007792051907616600754445463041653600455389482374933, 1246015584103815233201508890926083307200910778964749821, 2492031168207630466403017781852166614401821557929499642, 4984062336415260932806035563704333228803643115858999284, 9968124672830521865612071127408666457607286231717998666, 19936249345661043731224142254817332915214572463435997301, 39872498691322087462448284509634665830429144926871994535, 79744997382644174924896569019269331660858289853743989190, 159489994765288349849793138038538663321716579707487978260, 318979989530576699699586276077077326643433159414975956596, 637959979061153399399172552154154653286866318829951913129, 1275919958122306798798345104308309306573732637659903826311, 2551839916244613597596690208616618613147465275319807652591, 5103679832489227195193380417233237226294930550639615305147, 10207359664978454390386760834466474452589861101279230610294, 20414719329956908780773521668932948905179722202558461220588, 40829438659913817561547043337865897810359444405116922441176, 81658877319827635123094086675731795620718888810233844882508, 163317754639655270246188173351463591241437777620467689764860, 326635509279310540492376346702927182482875555240935379529854, 653271018558621080984752693405854364965751110481870759059704, 1306542037117242161969505386811708729931502220963741518119363, 2613084074234484323939010773623417459863004441927483036238705, 5226168148468968647878021547246834919726008883854966072477346, 10452336296937937295756043094493669839452017767709932144954692, 20904672593875874591512086188987339678904035535419864289909384, 41809345187751749183024172377974679357808071070839728579818768, 83618690375503498366048344755949358715616142141679457159637536, 167237380751006996732096689511898717431232284283358914319275072, 334474761502013993464193379023797434862464568566717828638550144, 668949523004027986928386758047594869724929137133435657277100288, 1337899046008055973856773516095189739449858274266871314554200576, 2675798092016111947713547032190379478899716548533742629108401375, 5351596184032223895427094064380758957799433097067485258216802527, 10703192368064447790854188128761517915598866194134970516433605054, 21406384736128895581708376257523035831197732388269941032867210108, 42812769472257791163416752515046071662395464776539882065734420216, 85625538944515582326833505030092143324790929553079764131468840607, 171251077889031164653667010060184286649581859106159528262937681073, 342502155778062329307334020120368573299163718212319056525875362112, 685004311556124658614668040240737146598327436424638113051750724224, 1370008623112249317229336080481474293196654872849276226103501448448, 2740017246224498634458672160962948586393309745698552452207002896896, 5480034492448997268917344321925897172786619491397104904414005793914, 10960068984897994537834688643851794345573238982794209808828011587706, 21920137969795989075669377287703588691146477965588419617656023175412, 43840275939591978151338754575407177382292955931176839235312046350824, 87680551879183956302677509150814354764585911862353678470624092701691, 175361103758367912605355018301628709529171823724707356941248185403485, 350722207516735825210710036603257419058343647449414713882496370806824, 701444415033471650421420073206514838116687294898829427764992741613648, 1402888830066943300842840146413029676233374589797658855529985483227499, 2805777660133886601685680292826059352466749179595317711059970966454839, 5611555320267773203371360585652118704933498359190635422119941932909634, 11223110640535546406742721171304237409866996718381270844239883865819325, 22446221281071092813485442342608474819733993436762541688479767731638735, 44892442562142185626970884685216949639467986873525083376959535463277328, 89784885124284371253941769370433899278935973747050166753919070926554729, 179569770248568742507883538740867798557871947494100333507838141853109648, 359139540497137485015767077481735597115743894988200667015676283706219166, 718279080994274970031534154963471194231487789976401334031352567412438331, 1436558161988549940063068309926942388462975579952802668062705134824876530, 2873116323977099880126136619853884776925951159905605336125410269649753060, 5746232647954199760252273239707769553851902319811210672250820539299506381, 11492465295908399520504546479415539107703804639622421344501641078599012695, 22984930591816799041009092958831078215407609279244842689003282157198025444, 45969861183633598082018185917662156430815218558489685378006564314396050678, 91939722367267196164036371835324312861630437116979370756013128628792101318, 183879444734534392328072743670648625723260874233958741512026257257584202636, 367758889469068784656145487341297251446521748467917483024052514515168405272, 735517778938137569312290974682594502893043496935834966048105029030336810544, 1471035557876275138624581949365189005786086993871669932096210058060673621088, 2942071115752550277249163898730378011572173987743339864192420116121347242216, 5884142231505100554498327797460756023144347975486679728384840232242694484649, 11768284463010201108996655594921512046288695950973359456769680464485388969041, 23536568926020402217993311189843024092577391901946718913539360928970777938082, 47073137852040804435986622379686048185154783803893437827078721857941555876305, 94146275704081608871973244759372096370309567607786875654157443715883111752579, 188292551408163217743946489518744192740619135215573751308314887431766223505070, 376585102816326435487892979037488385481238270431147502616629774863532447010118, 753170205632652870975785958074976770962476540862295005233259549727064894020344, 1506340411265305741951571916149953541924953081724590010466519099454129788040580, 3012680822530611483903143832299907083849906163449180020933038198908259576081160, 6025361645061222967806287664599814167699812326898360041866076397816519152162452, 12050723290122445935612575329199628335399624653796720083732152795633038304324883, 24101446580244891871225150658399256670799249307593440167464305591266076608649853, 48202893160489783742450301316798513341598498615186880334928611182532153217299508, 96405786320979567484900602633597026683196997230373760669857222365064306434599262, 192811572641959134969801205267194053366393994460747521339714444730128612869198530, 385623145283918269939602410534388106732787988921495042679428889460257225738396863]

m = ''
for i in key[::-1]:
    if c >= i:
        m = '1' + m
        c -= i
    else:
        m = '0' + m

flag = long_to_bytes(int(m[:-1],2))
print(flag)
# DASCTF{you_kn0w_b@ckpack_Crypt0?}

m= [m[i:i + 8] for i in range(0, len(m), 8)]
decoded_string = ''.join(chr(int(''.join(map(str, byte)), 2)) for byte in m)
print(decoded_string)

flag 的长度是 264 ，key 的长度是265，多了一位。。。

用厨子有奇效，就不用注意多出来的01了，也可以手动处理，如上

（int 似乎默认是从后面开始数八位来转换）

flag = long_to_bytes(int(m+'0'*7,2))
print(flag)

# b'DASCTF{you_kn0w_b@ckpack_Crypt0?}\x00'

背包密码的密度为：

$d = \frac{n}{\log_{2}{\max(a_i)}}$

# Sanity check for application of low density attack
d = n / log(max(a), 2)
print(CDF(d))
assert CDF(d) < 0.9408

Reference：

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

背包密码 | DexterJie’Blog

其他加密算法 | Lazzaro (lazzzaro.github.io)