Knapsack primes

solved by tomato

I was wondering why knapsacks used only addition but not multiplication of primes so I created one for you :o have fun!

We are given knapsack_primes_chall.py:

knapsack_primes_chall.py

from Crypto.Util.number import getPrime
from math import gcd

flag = b'YBN24{????????????????????????????}'

def gen_private():
    a = []
    for i in range(8):
        a.append(getPrime(128))
    return sorted(a)

def gen_public(a):
    while True:
        b = []
        n = getPrime(256)
        m = getPrime(256)

        for i in range(8):
            b.append((a[i] * n) % m)
        
        if all(gcd(i,j) == 1 or i == j for i in b for j in b):
            break
    return (n, m, b)

def encrypt(flag, b):
    enc = []
    in_bins = []

    for char in flag:
        in_bin = f'{char:08b}' 
        in_bins.append(in_bin)

        c = 1
        for i in range(len(in_bin)):
            if in_bin[i] == '1':
                c *= b[i]
        enc.append(c)
        
    return enc, in_bins

a = gen_private()
n,m,b = gen_public(a)
enc, in_bins = encrypt(flag, b)
print('n =',n)
print('m =',m)
print('enc =',enc)

and knapsack_primes_output.txt:

knapsack_primes_output.txt

n = 69445536039141548709981721571866113401602879002160450287075363762901927607533
m = 101441574708806390006875152196799734893549039523990755785821399979419806943511
enc = [7190014366077632299029977702076324295997188075603137450819370327874755152687047838239786627501157729363616956118566819285098429491573611114073030591829561445210638862244012057372125782865463003610413177891466422100934098271624683522978711334832396442062707669213093866143515397190548542180863385656763546817, 641963578196982921615671179191265672018394031399430908711768563973382030779294576305708409488258114130314799237643016183961265888719935490644545603167310, 438138967816855189399376492183537053308500152235099915155256598166952380307719367967364102490451027636673157445700932670923901547542903773586387261561613748590383873500522922677940837092428201064096111714455359018566584575645535589112297801130309000440181477587376521769943350836635663772022324587376754470, 66533972125588203934965488439503055214619702148529456145871458052929995571824126881907940137785473255655654364597062900097287801548975079130525586592611414738537486577813737631271830271829424602906045873654818436823085563997664630, 52575798778890162749169735842645954634769716496542684712210550480144238781509130247821096253553095062028869608836303603869389997676896847081394598163381090244536307360777764494625056127269273407660294724327551720897994694419260583, 9372678326894865356488289664455522341586053151244623100257508117077408498768321294358450224703034107926347196116354870872216328722359438299288001857805313839139665806198558663050348784925533019038398347171948611286518741206489057607408620811639652607467310733886211215816401415707413258436600332426445040319586501862902154770068628686066966717544413898849264825093985497523045355945380925891614542187819225548402517177561944275641202158718590376329666295375490, 183634473560328819212665065481413955837907161204315555898365448222573912474403825751094647626486244789971260719172274242097447486466378871599314065889534433616982423833522934651340117492064986766607493152325726237551088771267259736646936578496368036167081027959172519739825216513919113432212957018334761189935499934833351107106801003201545813600511978609537967597902862391613330110310, 38467007029426618167719241484120645018949356795192398816066031219793199822319616166337319532100110060163273175249063095731075096197780408132955847055146094090727110882898813540979777382131659531085575230763802467526046518730610717732188960151164041171320492669108163928499585327570609342567064346503941186711895994284606990353576141746358586227998691705284221665894658973367343914170, 52575798778890162749169735842645954634769716496542684712210550480144238781509130247821096253553095062028869608836303603869389997676896847081394598163381090244536307360777764494625056127269273407660294724327551720897994694419260583, 193748774860669485717579974515231254855741671527081444616364777850577361086905056855978824126390422722099782886361259791891601916303189857560223436373891594415783098559743170380014778881550887434479304703393480238092788183597745757, 2944771238707506948774447734034564293291594096762784952387309536381705739943331675801245452960314540595796606910356494510912501020009267340858593499272337592171232295305321127669146938920098573170672136007833355385902153938282449043942108658129027427675570262286452576182762360943741325065317790911045862083, 43236740981823340421614846369992164566446121448164155900287241526690252726153, 3156840126595753463680034615678100118426753332722026161347355467436343864421540317382966064850102313135338629280022470893968812512542549648349422851135570272530869885139477349718704192932125322883545139855456102813644462456039002664355501339444294935665526295230496262841588914246416496237888636155047640410, 183634473560328819212665065481413955837907161204315555898365448222573912474403825751094647626486244789971260719172274242097447486466378871599314065889534433616982423833522934651340117492064986766607493152325726237551088771267259736646936578496368036167081027959172519739825216513919113432212957018334761189935499934833351107106801003201545813600511978609537967597902862391613330110310, 1252526900014711095595280972313242758198269141084265122091894776411109380811082989935202734876629025222240752081083789909165730806948034837590032475014967264414925013346351477105098395053315599448161636820387022149022288139269716847319777427927608243762434013624460797541602328538575268616536957785947685181609509212083627330413815002074430224780410369869136666534635964611798809060850130164749999258743587865870574987691607735912406190572683378173545570525130, 2206797325518343741010542994949867415233679078209235375839806865306097684186656700856551828364121089307318746871067427076988721866407672945005872371050387, 2876712119285911284466700020775969597331472097282503963560528902833062518391548747621734329634206367092263868406829257933055472217059139686699242196067490612844080126567199765877632430800330400448337578370112687661754593332137334400507214342075107073028389106241203040350941192388457659871992939782924068390, 250987271335915664343380903992505859266134242634462199818412738137831480911199195881015204572619356409315469911732340279753224765171546950854558095174854198199673897175851157823341478527085032461314588635475232655993673947149624969, 145109766068846737667439409254815694029351910547493283682346268609019568862216897106934361916011664066927764859328002078332443778586093314917520800149240859661837852403245088041430346996094501342339145848728004863644091434720604109354610235073401638844979200914603144645568487407674576039408288376055873188275140410697951033052048770305905503366675586956608937260172778763191506649471, 3726568726732619299995175990210717592618824030957571808940425042220819691094160428449158575857096594666099117864638426994048782857195038214530519838501294106283016440934232857533029678607093001152694054167723764604469034578218003726393689343442758841354149538225719129293435409831811579564232940666709079630, 161124686788701465784217694821299615315500855930722934294431110618870284127813837387712988812235279792614878746107811015112349436168706157875954524591903212980155535915510022755788447783640951926498230556649935780906142838480306269845704366107803867844719983051110245638626088436569008664078155157446397688856865039297544605895265615638877230545804580158252141498496554965565060563390, 1252526900014711095595280972313242758198269141084265122091894776411109380811082989935202734876629025222240752081083789909165730806948034837590032475014967264414925013346351477105098395053315599448161636820387022149022288139269716847319777427927608243762434013624460797541602328538575268616536957785947685181609509212083627330413815002074430224780410369869136666534635964611798809060850130164749999258743587865870574987691607735912406190572683378173545570525130, 421867372345529136360123216455463909191296680484490788149304386330054839033672560488240234290184243480199992543257693855618509103768336240925211745584591315011987527280220425672580419963336458108225363639888878704450169815139457253194224343801853796684915289826346166466500358895661913626313175561382183170, 35956389161533127704243126671515587394551991976692924490937823635746550985576750516451204150001611011355481555331788234722282828242272040472452768055321358275721352479603950311280595283407157338047795214780762723803735457033522310, 507285929764598533161191123257807124797989840126409763399581627133843800859451865891544578078108450635154071509357006646697141720122318345525688005023171, 1252526900014711095595280972313242758198269141084265122091894776411109380811082989935202734876629025222240752081083789909165730806948034837590032475014967264414925013346351477105098395053315599448161636820387022149022288139269716847319777427927608243762434013624460797541602328538575268616536957785947685181609509212083627330413815002074430224780410369869136666534635964611798809060850130164749999258743587865870574987691607735912406190572683378173545570525130, 2421690478430563383645815677087435931243268147315390081482438531135063618877761739965981023478185655743550218491218316480091270716114123085562225547012653, 2273206193715337837768135492971973936957319748409622157733375379059107070259316762311142122976343719418101001577771304759043678488852113655309838646858210677388027351081886477821367580398399138513596106878576554495681578526107713006446540195904926801096123465658920982592105153779729212706394450566246127199, 4247185828310428627819231347608770546795540503400780921901713651548969064278202934926120928438194836394592009537600915337102125095290821511321083308728338197072840711332082673658758540719351946527107456416891301384316880011109503642368507283536265731177097081145461018293896948104448980757355994283027033270, 52575798778890162749169735842645954634769716496542684712210550480144238781509130247821096253553095062028869608836303603869389997676896847081394598163381090244536307360777764494625056127269273407660294724327551720897994694419260583, 3156840126595753463680034615678100118426753332722026161347355467436343864421540317382966064850102313135338629280022470893968812512542549648349422851135570272530869885139477349718704192932125322883545139855456102813644462456039002664355501339444294935665526295230496262841588914246416496237888636155047640410, 2091595497402890525045225266142409205262150684122032906456918097888638899396240062651260967941891749469212451531014358624650651124574411485840550174553306306970225557878756244234493379665477143666339470621605863558597033742124053209102526113189697315049624099267673706411269044002478119267654268233648833210, 4917475436008450288314944865721220439629335311591982171258058218720343826904996907279765230924232949602784720004549399700456198274872349232118603678880011, 4917475436008450288314944865721220439629335311591982171258058218720343826904996907279765230924232949602784720004549399700456198274872349232118603678880011, 7406382544002259090952208107298770068452903123788298992754063412899829285721138670026187021121483148475903393073711395303690154629266278381500727606382284068724911150556261786018846431964531047596089451417427473388950041305989872395602986065972829874100219558698763780111205954403045953424142592128223987747220896504531726224177114523715706041939816450394348068673988937525424102975514077061604692198707073170832943835231575011773277444951275378408978288938309]

Essentially ignore $a, n, m$ but care about how from gen_public the public key is 8 pairwise coprime values that are 256 bits each. Label these values $b_0, b_1, \cdots, b_7$.

In encrypt, each character of the flag is converted into 8 bits. Each bit decides whether each $b_n$ is included in this encrypted value. For example, if the character is Y = 01011001, the included $b_n$ would be $b_1, b_3, b_4, b_7$ as the bits at those indexes are 1. Now, take the product of these values, giving $b_1b_3b_4b_7$ for Y. Repeat this for every character of the flag, giving a sequence of integers stored in enc.

Recall that gcd is an extremely efficient algorithm that calculates the greatest common divisor between two numbers. Looking at how each value in enc is some product of a combination of the same eight primes repeatedly, you can expect that by taking gcd smartly between these, you can get the values of $b_n$. For example, consider the first two characters of the flag, Y and B:

Y -> 01011001 -> $b_1b_3b_4b_7$
B -> 01000010 -> $b_1b_6$

Taking the $\gcd$ of these values gives $b_1$ as that is the only common factor between these two numbers (and also since all $b_n$ are pairwise coprime). Repeating this smartly is enough to recover all values of $b_n$ except $b_0$, since all the characters of the flag are ASCII and hence in the range $[0, 127]$, meaning the most significant bit will always be zero (and hence it is not important anyways).

The first 6 values of flag prefix are sufficient to calculate all values of $b_n$. Since there are only 7 values to recover, I just eyeballed but there is probably a more efficient way.

Y -> 01011001
B -> 01000010
N -> 01001110
2 -> 00110010
4 -> 00110100
{ -> 01111011

b1 = gcd(enc[0], enc[1])
b3 = gcd(enc[0], enc[3])
b2 = gcd(enc[3], enc[4])//b3
b4 = gcd(enc[0], enc[2])//b1
b5 = gcd(enc[2], enc[4])
b6 = gcd(enc[1], enc[2])//b1
b7 = gcd(enc[0], enc[5])//b1//b3//b4
bs = [b1,b2,b3,b4,b5,b6,b7]

Then, with only 128 combinations of encrypted values, we just have to check which of the 128 each encrypted value corresponds to, to recover the flag. Here is the full solve script:

# sage
enc = ...
b1 = gcd(enc[0], enc[1])
b3 = gcd(enc[0], enc[3])
b2 = gcd(enc[3], enc[4])//b3
b4 = gcd(enc[0], enc[2])//b1
b5 = gcd(enc[2], enc[4])
b6 = gcd(enc[1], enc[2])//b1
b7 = gcd(enc[0], enc[5])//b1//b3//b4
bs = [b1,b2,b3,b4,b5,b6,b7]
knapmap = dict()
for char in range(128):
    in_bin = f'{char:08b}'[1:]
    c = 1
    for i in range(len(in_bin)):
        if in_bin[i] == '1':
            c *= bs[i]
    knapmap[c] = char
print(bytes(knapmap[i] for i in enc))

giving the flag YBN24{kn4p5@ck_Pr1m3s_GCD_At+4cK!!}.