# ecssp (crypto)

This is the challenge code:

```python
#!sage
from sage.all import EllipticCurve, GF
from Crypto.Util.number import bytes_to_long

flag = b'SSMCTF{REDACTED}'

#secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7

E = EllipticCurve(GF(p),(a,b))

A = [E.random_point() for _ in range(42)]
enc = []

m = bin(bytes_to_long(flag))[2:]
m = m.zfill(len(m)//42*42+42) # makes the number of bits a multiple of 42

for i in range(0,len(m),42):
    buffer = None
    for j, bit in enumerate(m[i:i+42]):
        # the buffer is the summation of points wherein j has a 1 bit
        if bit == '1':
            if not buffer:
                buffer = A[j]
            else:
                buffer += A[j]
    enc.append(buffer)

A = [i.xy() for i in A]
enc = [i.xy() for i in enc]
print(f'{A = }')
print(f'{enc = }')
```

Output:

```python
A = [(114022552566672434287471812777717333762408551721791348889344472111227927502889, 91848347484952671316308675369245644465513610696925627817363786882910842914630), (5134235591147639910038981348618172041966754946151413595658689762008632417144, 3511794964597550219657005150446044437507191250164867133904557082591168200810), (7032886284728108699844541145867001038913067269804679108520652174728735284910, 23374784913016520963837121466288011654300981565362994781090990047581133995522), (64787929624393757911733465336546182797274948931237749247448226674433887764438, 100817994108392828748624813186243365302623148897918291171263241159232476705779), (61415319441662283644671806891506262708697273153238310958561291976566757851073, 47494855000112343060989722245396024127687216333344414084480138013856386400789), (31185225928020456074752113695930814394830270813864650049700325446839880436127, 98491843633049747320558494747016228169500900638949819454524008871199970848281), (61269037926178524499534355938680601447869226876831633887037654303319306902653, 7355959218752508692581981354345577329362806703629635457558186391126933065749), (46719743249477073536538523513876054148471856984109116152739306755928621137426, 79618227045878281991826536940081720008541694129455394111913396631045566145019), (71315609148455933583113137278156208113945683697681378464038731331649140453423, 41583976526604472993060418781265873641544347584287693599816935475869235033534), (34066985707582221727977428114751711145513492613331952008062524932064871300560, 9357963789875591485663090690843223368692879191592063080397524581806899989236), (112020015499791865542782141811688326015931444990628396652697052762093557415090, 97128953852476344478082470122398620436012998399897014560451651165696740697799), (42634390421337524463301787804160248224871449877456106839396316088983266777563, 36921893488724507975591286756011274949418646781286950314836583088947321399436), (109004872868473933843880334915627471365175851567444755103105745779429972062867, 10573682450940016830774151372886548289936213323569507701136657060721130866102), (24771770795854826019973902904410515550685645037907625865334744293267191703844, 238372343166032899435738271938582337808395959304176115681472003829671766069), (89898689270246478820497970612987341984775455104130834253057564247800138515216, 51361988465970660503417536945674893360422898646549654448056592592182179319322), (29353616892236794960022032235244696999870640837822460779312808945733127358965, 17189936243022410767965833508172954000235716444164810378420545005517265790590), (40907116228495544023560546056350488549701829492088999807726782859492817068142, 30600558861609828228122226133163256268226672743476940517404142980188899308141), (65595884403128634532554508209524238590976304321760189307800388865013736066122, 43739639766381874302525066091683537092274252516033766178153325330777753436173), (25248021323749208361083970171444517434971442331821340582052299954992625989433, 16433968721701929908034597638247694006984447527539174579327824152287410930927), (66637292000429090447834237361626051524039437607541033364971712194112098231001, 62897600570026652121263578113146768874909942153620854376802483617302774115980), (115212652540512582012577970245526787954210815528182926099395974524525631662162, 99777843108973546310076149803711850216390102688256655995359800874570043056555), (83878517831334008537079994787751658186104835789618280423583097526657039236116, 103511299944003266439173166120956421458183958407018392943008279310148901530099), (52594410772860121402953141618705939118615173192654401872197358793802093515001, 83405724211182079540236196795249163629897595215932404038528725584752940112891), (33065844213457587899962903396905924355762651943441569081451445513507319530855, 84459733639665926869498081695782057380035530851686381235158073488183035616786), (92852131344469309458360217477923144206844568659427057865288421289109253101850, 107983952221059675122423299705365141729775323231590366324267237436140008945947), (96029923597418235178467955471356574309551942895748993166823415663148665366818, 44009545809587730664603276939770224891921201461689182875991144734130730148132), (14491509301756702536461113822340540580917882458515619656898399058847358427165, 49697262878580453821093137648994944864996947361941635057840345229346592103325), (7142334457994882719662437060979343972591452514665838139143484105280906359843, 115551291934769872032845156599846422261691630966595375293712684039045331609773), (76199441895199959275724182330257364704683013310299613213681996128885039748856, 61818592218490595235086300654053309843951970828080818853139158729491555260528), (109929676816214299202831373205057089272383846164015783800295478396646698467323, 85603015167410332963621281121877119398125218999394242687621353796693626604814), (42085095747394420012437156518121954367239135800432273121845002452192659516043, 99152489145483114144014322676393985173394178769761002353396529032837553322954), (46785837870376203194490078015227240349998784412414091973301490669202030071274, 50158820599587084300110311636192802928718158911039536915016098936406858562516), (2542408287329394787358496421330518153382875002992489916936545569680393263826, 90960446941858157396519547124374187601195250590035308278734642699690186774134), (71104981300440345730027322716187483726593985627650490829854057008302951470953, 33514784920149980284990693642981138878817995455645608482499592830700653956566), (2219892059755913648923157677311647289191116275916201596356192006714889434836, 88618328428853723603356473619982882118747874012454061529636978281392148038263), (97178746971516087889535720327071518678118751045576788550771262246668598290172, 109805470081585872699137219689787905302272845563258748145297268263743508487479), (115534988340017196814212470995899778229858109387047371649837573529558387904853, 73561296050053000878918947216300173621080314170028964145490299232785134490670), (71020415564613394809479505654058314877327019326561551804364004670235803702823, 63721115749327971913307535980809347713258942827871762375911063350230411291154), (103525157991421687186695127818409910674944424344157107349452655919519635026348, 32688475822302762091357434289719114377166781834307639574849691681988225039970), (5087645535251679155915786583389386699946293717913736425888766550834106777832, 39404753198204781082643593694294372610894075291929137737571839372499106216263), (46869233779509670367924828352772167995400504169134812168319240561141370079721, 10556762214950234444787499536590640061428436758010737349806108326319636463365), (97699454395659998727515199878750545107706971087247916527908427481361566291361, 102405817218001246838012518871118424034120058607873164728157421470161986209902)]
enc = [(64790039097843726619666409283242777555003893618465502278317178757450138780247, 102844883231790621570884937608458381278419605840318534308920025637869951920685), (65467005106282061101664483249093359627045329274101984251422509764159888516782, 29577274831610547096769142678647481089072852714288000323692708023231117856259), (71126810596268579329235558066839193156863450492831082744027778860379767646458, 10061110158348361585582673111744600909320452001919882022692480289045281568038), (68130211277586543741700239238753266861237930181769784115771631347659811533995, 62916875538459760084037730097955290681027631961337350448937045279643828518377), (40739841185675326976137753552659542076873069897376020788702703621548466410384, 95505667868305009079261482128316557710057532847302718993997202290022214506067), (18113528668110280401511533074417338843730161007004980298553405689312187829593, 54549787510067678331569900262990828737439364417965444112678791347445057986509), (65785972692053719083883036722006292317181610120596386229948182706617388553330, 26925186146344157810917265671643490784806237827525588744976777335589847243551), (52049982563010361166332130366254990594595414206544311311954755536493054807189, 49859379427158965363993305038648217602616149186457294969786353267658272232018)]
```

It does the following:

* Create a `secp256k1` curve
* Create an array `A` containing 42 random points on the curve
* Converts the flag from a bytestring to a bitstring whose length is a multiple of 42
* For each chunk of 42 bits in the flag, if bit `i` is `1` then add the point `A[i]` to `buffer`. Otherwise do not add the point.
  * Once all bits in the chunk are done, append the resultant point into `enc`
* Give `A` and `enc` .

We can basically think of this as a knapsack cryptosystem, where each random point in `A` is either added or not added into `buffer` for every chunk.

We can start by trying to solve the problem for an individual chunk of 42 bits.

It would take too much time to calculate all possible `chunk` values since there are $$2^{42}$$ possible resultant points (because there are 42 random points in A, and each is either used or not used).

However, we can use a meet-in-the-middle approach:

* For the first 21 points in `A`, we calculate all $$2^{21}$$ possible results of point addition and have some dictionary `d1` storing `point : bitstring` mappings where a given point can be produced by the associated bitstring. Note that $$2^{21} = 2097152$$ operations can be completed in a reasonable amount of time.
* We do the same for the last 21 points in `A` for dictionary `d2`.
* For every chunk we need to solve for, we have the encrypted point `p`. We iterate through the $$2^{21}$$ entries in `d1` . Then for each point `D` in `d1`, we calculate `x = p - D`. If `x` is present in `d2` then we know that `p = D + x`. This would imply that the point we are using from `d1` and the point we are using from `d2` exactly add up to our point `p`, which means that the bitstring we encrypted is `d1[D]` + `d2[x]`.&#x20;

Repeating this for all chunks in `enc`, we can retrieve the flag.

Below is my solve script (takes a few minutes to complete):

```python
from sage.all import EllipticCurve, GF
from Crypto.Util.number import bytes_to_long, long_to_bytes
from tqdm import tqdm

#secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7

E = EllipticCurve(GF(p),(a,b))

A = [(114022552566672434287471812777717333762408551721791348889344472111227927502889, 91848347484952671316308675369245644465513610696925627817363786882910842914630), (5134235591147639910038981348618172041966754946151413595658689762008632417144, 3511794964597550219657005150446044437507191250164867133904557082591168200810), (7032886284728108699844541145867001038913067269804679108520652174728735284910, 23374784913016520963837121466288011654300981565362994781090990047581133995522), (64787929624393757911733465336546182797274948931237749247448226674433887764438, 100817994108392828748624813186243365302623148897918291171263241159232476705779), (61415319441662283644671806891506262708697273153238310958561291976566757851073, 47494855000112343060989722245396024127687216333344414084480138013856386400789), (31185225928020456074752113695930814394830270813864650049700325446839880436127, 98491843633049747320558494747016228169500900638949819454524008871199970848281), (61269037926178524499534355938680601447869226876831633887037654303319306902653, 7355959218752508692581981354345577329362806703629635457558186391126933065749), (46719743249477073536538523513876054148471856984109116152739306755928621137426, 79618227045878281991826536940081720008541694129455394111913396631045566145019), (71315609148455933583113137278156208113945683697681378464038731331649140453423, 41583976526604472993060418781265873641544347584287693599816935475869235033534), (34066985707582221727977428114751711145513492613331952008062524932064871300560, 9357963789875591485663090690843223368692879191592063080397524581806899989236), (112020015499791865542782141811688326015931444990628396652697052762093557415090, 97128953852476344478082470122398620436012998399897014560451651165696740697799), (42634390421337524463301787804160248224871449877456106839396316088983266777563, 36921893488724507975591286756011274949418646781286950314836583088947321399436), (109004872868473933843880334915627471365175851567444755103105745779429972062867, 10573682450940016830774151372886548289936213323569507701136657060721130866102), (24771770795854826019973902904410515550685645037907625865334744293267191703844, 238372343166032899435738271938582337808395959304176115681472003829671766069), (89898689270246478820497970612987341984775455104130834253057564247800138515216, 51361988465970660503417536945674893360422898646549654448056592592182179319322), (29353616892236794960022032235244696999870640837822460779312808945733127358965, 17189936243022410767965833508172954000235716444164810378420545005517265790590), (40907116228495544023560546056350488549701829492088999807726782859492817068142, 30600558861609828228122226133163256268226672743476940517404142980188899308141), (65595884403128634532554508209524238590976304321760189307800388865013736066122, 43739639766381874302525066091683537092274252516033766178153325330777753436173), (25248021323749208361083970171444517434971442331821340582052299954992625989433, 16433968721701929908034597638247694006984447527539174579327824152287410930927), (66637292000429090447834237361626051524039437607541033364971712194112098231001, 62897600570026652121263578113146768874909942153620854376802483617302774115980), (115212652540512582012577970245526787954210815528182926099395974524525631662162, 99777843108973546310076149803711850216390102688256655995359800874570043056555), (83878517831334008537079994787751658186104835789618280423583097526657039236116, 103511299944003266439173166120956421458183958407018392943008279310148901530099), (52594410772860121402953141618705939118615173192654401872197358793802093515001, 83405724211182079540236196795249163629897595215932404038528725584752940112891), (33065844213457587899962903396905924355762651943441569081451445513507319530855, 84459733639665926869498081695782057380035530851686381235158073488183035616786), (92852131344469309458360217477923144206844568659427057865288421289109253101850, 107983952221059675122423299705365141729775323231590366324267237436140008945947), (96029923597418235178467955471356574309551942895748993166823415663148665366818, 44009545809587730664603276939770224891921201461689182875991144734130730148132), (14491509301756702536461113822340540580917882458515619656898399058847358427165, 49697262878580453821093137648994944864996947361941635057840345229346592103325), (7142334457994882719662437060979343972591452514665838139143484105280906359843, 115551291934769872032845156599846422261691630966595375293712684039045331609773), (76199441895199959275724182330257364704683013310299613213681996128885039748856, 61818592218490595235086300654053309843951970828080818853139158729491555260528), (109929676816214299202831373205057089272383846164015783800295478396646698467323, 85603015167410332963621281121877119398125218999394242687621353796693626604814), (42085095747394420012437156518121954367239135800432273121845002452192659516043, 99152489145483114144014322676393985173394178769761002353396529032837553322954), (46785837870376203194490078015227240349998784412414091973301490669202030071274, 50158820599587084300110311636192802928718158911039536915016098936406858562516), (2542408287329394787358496421330518153382875002992489916936545569680393263826, 90960446941858157396519547124374187601195250590035308278734642699690186774134), (71104981300440345730027322716187483726593985627650490829854057008302951470953, 33514784920149980284990693642981138878817995455645608482499592830700653956566), (2219892059755913648923157677311647289191116275916201596356192006714889434836, 88618328428853723603356473619982882118747874012454061529636978281392148038263), (97178746971516087889535720327071518678118751045576788550771262246668598290172, 109805470081585872699137219689787905302272845563258748145297268263743508487479), (115534988340017196814212470995899778229858109387047371649837573529558387904853, 73561296050053000878918947216300173621080314170028964145490299232785134490670), (71020415564613394809479505654058314877327019326561551804364004670235803702823, 63721115749327971913307535980809347713258942827871762375911063350230411291154), (103525157991421687186695127818409910674944424344157107349452655919519635026348, 32688475822302762091357434289719114377166781834307639574849691681988225039970), (5087645535251679155915786583389386699946293717913736425888766550834106777832, 39404753198204781082643593694294372610894075291929137737571839372499106216263), (46869233779509670367924828352772167995400504169134812168319240561141370079721, 10556762214950234444787499536590640061428436758010737349806108326319636463365), (97699454395659998727515199878750545107706971087247916527908427481361566291361, 102405817218001246838012518871118424034120058607873164728157421470161986209902)]
enc = [(64790039097843726619666409283242777555003893618465502278317178757450138780247, 102844883231790621570884937608458381278419605840318534308920025637869951920685), (65467005106282061101664483249093359627045329274101984251422509764159888516782, 29577274831610547096769142678647481089072852714288000323692708023231117856259), (71126810596268579329235558066839193156863450492831082744027778860379767646458, 10061110158348361585582673111744600909320452001919882022692480289045281568038), (68130211277586543741700239238753266861237930181769784115771631347659811533995, 62916875538459760084037730097955290681027631961337350448937045279643828518377), (40739841185675326976137753552659542076873069897376020788702703621548466410384, 95505667868305009079261482128316557710057532847302718993997202290022214506067), (18113528668110280401511533074417338843730161007004980298553405689312187829593, 54549787510067678331569900262990828737439364417965444112678791347445057986509), (65785972692053719083883036722006292317181610120596386229948182706617388553330, 26925186146344157810917265671643490784806237827525588744976777335589847243551), (52049982563010361166332130366254990594595414206544311311954755536493054807189, 49859379427158965363993305038648217602616149186457294969786353267658272232018)]

for i in range(42):
    A[i] = E(A[i])

for j in range(len(enc)):
    enc[j] = E(enc[j])

def gen_perms(i, mx):
    if i == mx-1:
        return {
            A[i]:'1',
            E(0):'0'
            }
    res = {}
    z = gen_perms(i+1,mx)
    for val,bitmask in z.items():
        res[val+A[i]] = '1'+bitmask
        res[val] = '0'+bitmask
    return res

maps1 = gen_perms(0,21)
maps2 = gen_perms(21,42)

pt = ''

for enc_pt in tqdm(enc):
    for val,bitmask in maps1.items():
        v2 = enc_pt - val 
        if v2 in maps2.keys():
            pt += bitmask 
            pt += maps2[v2]
            break

print(pt)
flag = long_to_bytes(int(pt, 2))
print(flag) # SSMCTF{jus+_MITM_pr0bab1y_eas1er_th4n_LLL}
```
