# kleinvieh_2

## Decription
In this challenge you have to break not just one but 5 encryptions.

## Source

- `chall.py`
```
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
import math

# Utility functions
def chunks(l : list, n : int):
"""Yield successive n-sized chunks from l."""
for i in range(0, len(l), n):
yield l[i:i + n]

# Encryption Methods

def encrypt1(message : bytes, key):
return pow(bytes_to_long(message), key.e, key.n)

def encrypt2(message : bytes, key):
r = 688234005348009046360676388021599552323079007705479727954148955984833460337936950913921276804334830417982234720038650432729780498514155995618937412575604196815690605161835755609341381092145548153312943119696398326144902639226831471200542337105282064399184931676924592908530791494346900227871404063095592748764296028255530577278656680463782655139421219302422899667665339277824718421901831817043159552132252016945226370677278067424506514993298100924479619565269428391036310378044733517453768164252655931111202089432697078947184486267865943138659836155939343134738408972426979329158506027280653209318479413895259774319848662706808171929571545923310500352950348748809789292920278241362015278963315481777028997344480172010960294002098578989469089294022590134823913936869548907125294447477430739096767474026401347928008150737871869441842515706902681140123776591020038755234642184699856517326004574393922162918839396336541620212296870832659576195010466896701249003808553560895239860454162846759635434691728716499056221797005696650174933343585361153344017021747827389193405667073333443569659567562247406283282451284155149780737904760989910944550499316655128394899229284796584787198689342431338201610314893908441661953172106881929330452489260
return pow(bytes_to_long(message) * r, key.e, key.n)

def encrypt3(message : bytes, key):
bytelength = int(math.floor(math.log2(key.n))) // 8
msg = message + b'\x00' * (bytelength - len(message))
return pow(bytes_to_long(msg), key.e, key.n)

def encrypt4(message : bytes, key):
bytelength = int(math.floor(math.log2(key.n))) // 8
msg = message * (bytelength // len(message))
return pow(bytes_to_long(msg), key.e, key.n)

def encrypt5(message : bytes, key):
bytelength = int(math.floor(math.log2(key.n))) // 8
msg = b'\x42' * (bytelength - len(message)) + message
return pow(bytes_to_long(msg), key.e, key.n)

# Actual code
flag = open('flag.txt','r').read()
messages = [x for x in chunks(flag.encode(), len(flag) // 5 + 1)]

key = RSA.generate(4096, e = 3)
key_file = open('pubkey.pem','wb')
key_file.write(key.public_key().export_key())
key_file.close()

encryptors = [encrypt1,encrypt2,encrypt3,encrypt4,encrypt5]

for i in range(5):
print(encryptors[i](messages[i], key))
```

- `output`
```
220063927409019701680780388734859413263649938528559880958114989945319210396443096153070875125175228115415476201776095239222264863
521405777679638898956934268538900625825553438750301296652588113926908675649695287473044872094704614120486323959657990026640254596060659622526156708812669359650586620385290808935734592790788255073585330621151468871219769656595135843333814407503403584485725875093573131958504623569333490646639116961719078216840229603919536018487825851994866357917761987217050792416697381377048912395473353778387941958191907824408107449076068401916848269614839157102521989010679392116485801486351905021880108912590420172605418475794616003449288680484874497236175444664128438401914724753429360434711903099273327857734995750524336685921743399501618966233467673179877216701974657036419446491274854437281396070824372634560507303755215464570159167837973755757084277460889038540426254099700613477619367190997235567982845416706558020882785247647017658533190054489579620395565959077232929730085201031313238724372408560517067025821200011117585158799293570307490792480672057216647059928346781983773928742745961020992758462787355967282442061725370293489410415806016306004266400903317110818168429756442671778827765363252714782616931406456862197207387559816797319132734318242504254436838880072071853192476696183220292931118231156006566093505435792459195491243680582
270666484654665630744901461996006692323963839982688652821336211084979467239347411813160298980515940583603861222174521984995420008548684262439808167328926021870579303960012771121601180529687766238396064375729105115543248938593316359682370849163035376370382430086321848989469101241917690539277074390985259902303859203469942292526312785642432913613936993258827179590899881832319079212987637373648192635781867448864854757206430089991579140087742146982306295873762255307312524837239897502872553828380739799963200435212855355849421115331904398013024635259514540481471626803307520164323612306097337438109957993918779265436327033558060626053354750562352860044802675727693412211125966360236444057953485024215560142475510160722114624532935356913983972915673608523025209720167213909179022327299978019112977846926119199262414918029479523990318896183663433071251579236571042002734675157891234966022932698905198698241706452025453847010887618278823570050783989170662300961633292513523806788091889082274722372602239592372048577727269817482906420208931626412130427401917267155522492175168008656904232528370893411707370782832090829602128710489070166301148107529844470225377087526762510454613609000260941022095648201987928579356978933393880920171979201
653824340069025689137734254884130538700629136163559226740194794484993327658776187767570065320577134162743283784425272380809589160993088925874733196055173409287931015748252064633449072261545303183579447460502965342804624603405929157397131141984984644568357653302213965819415468460642952197339991556281367534783709497954301841184449070203282829556818406681886900718807834059676277878423047814575995317125009067646248518224341963179051812872833920966444865854397107596362642091691676816880789051432546280982801936460897107739053704289586862815777802365195344200436339914632247470287475059508482642321374344266084746769130713777040613388188063244264539412036380560226898399218628361640805872727932488302521211097971713325651815102241321497845489911517697687601337373561866169629605144418239966598946278151568343055898100847891792937851579379932984962575775149818916217268297467279875725571404166944999117855879952146915514369003878816227211205583465391314024099614444033724650197415698616726563650695337089763944873372957911180655004798934831152909017151923470147174567931032793367193038245769647005250292165097213630935925441110568790329108402080201984414111112552177466252777781418725448757243067372449888316330317213717511659267093522
358008688390962979576377899144327321078101097951911268175317488500603502519487932330612462905624620597194558963905078036617959827652774950608159539755872698070336695988156123259549872787213397592148258199055613243895883287122890753360508292871837174063088420693224462093920149982044282287843545879889673811146267351528090047294284591799007589644031290908451176760853222636619363811207185693725681140126798792027873548626157363148637874670590965485611082128311321694683523699469128409485949494113757646949983087406842230923148769118322570130431421259760535420603207584288801345366412235455743468488327636151425392848303200702882860489019370153190810988494600882544600108525238483037309140333051358221984674540701977879624246387893765464282113949391789532777484259814371861241414118348867987309273292578129887971446610687731851915056696448523460974558006120340055071716623978233935275849865817975522109696101884471525506261697387468489779620579480299246665603825623773259263912587161909414417437045900004826755951647391749631385635652448151832357232824962202646901774457696625192040117636828038808343932086478692164048901540300465526784540912169577834838256728624868904132298644241575543460006379361856217382572895303794378838795856964
```

- `pubkey.pem`
```
-----BEGIN PUBLIC KEY-----
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAq0qupn0dQPB2KBxkqKbH
qVdlQVInAL+PVtOIqiPfAKuomeiAPFqSxYnVszx8OX7esMulhF/JXERl17Glc7nr
1f4g5TqCRBdLjn7L5UFQfnTDgs0H0eEEXkDo6ujFrP7SCCjwm4u0YQUE14nIFDk2
eLNj7UHXNXvsTLhdJ6cahmMQ0UpcNLvJ2Utq+mPnxHQ4t8WfAe9LeMGSwyHvN6aW
33crJlWIA7q+USLxqQjfOVX2/nGMh/hUZiWkIWrUu5DrbN187s1UuFp/XMsgfTFM
gAFwe8yzwOS5NBc97H4hBechDSCIpUwYd07pkmPEon7V9sUuQasM84UqgzvSQBTF
vP8uKlzZpnoMIVFQJ1iPOUOsf6RYEhw2rgywIKgWILDUutcrBhMm/sZyYR1IqiYc
QBUaJ9jeCQ8pJk5GtTb2B/MDDlazW37iQmPopUGuaRAkWRVpSENC04/3pa57g0R3
jKffVevsNNOPcdVveZ9CNUJ36ckCHMkVjhtwTj3ChhCJkq0EJsmFZcSMe5dWtUEs
6tZm/OXkyCCIkJW2+9bv6fDxAuGtY6VKHKDYeFS1nfufA8fI7L022O++D9nkLnBX
bbi8dinhS9SfTS9GqR5mbEm5NvGT0bG74YbYO4Oy1GPThJOtMXVuNh1qevzDgKKF
PQlPTql78u4Zhw+T2ukQPGsCAQM=
-----END PUBLIC KEY-----
```

## Solution

- After extracting `n` and `e` from the pubkey and the 5 ciphertexts from the output file, the 5 decryption methods were

1. `pt1` is just the cuberoot of `ct1` since `n` is much larger that `pt1 ** 3`
2. First we remove the effect of `r` by dividng the `r**3` from `ct2` under `mod n` then we find cuberoot to get `pt2`
3. Here `r` is `r = 256 ** bytelength-lm mod n` where `lm` is block length of all 5 parts of the flag and `bytelength` is the number of bytes in n, floored down. The process is same as the 2nd part.
4. Here `r` is the sum of `256 ** (lm * k) mod n` for `k` in range `0` to `bytelength / lm - 1`, the process remains same as part 2
5. This part uses coppersmith attack where a large prefix is known and a small suffix is unknown.

- `solve.py`
```
n = 698809279803729100079401078372877880427534404702960341414657347899868695112937851068715263778044026960633490809424029064042059332067584211653792196700294350014573184050423710869400198311885677686776017504286227076537554159472858525076085634316345875740693290133882175978733925820699211845215919301594415766540019628304963946324745390725546428536097179973714842991708107348137633653650305109545081201035764079475728847207709375197074999828255856201471365404842335215247826759981584891713402716199125948297913830799181837372349720366417853754796224373298275046483568482746775859489692619384473186252774861885551132459800952522899651670157743254166927522541977826908655008388262139384030791486359107484039097526310532872263205859627319202436841723699816330454014234233782897304181837031056847338989710295447928978914887694045437118913508152754428093165631142831515262870346794228649249227188823826429873812279500464419259184458884477035660529116246947819203737674026095282077223581457285927181664053908670826417300651727432619278835787730219365136633094261034800600159172455889800794002324761994100506313076450253206268905858518116325377063495847739400746814680699716314543913219769366318366988661130926848067294360557400700653304560747

e = 3

ct = [220063927409019701680780388734859413263649938528559880958114989945319210396443096153070875125175228115415476201776095239222264863,
521405777679638898956934268538900625825553438750301296652588113926908675649695287473044872094704614120486323959657990026640254596060659622526156708812669359650586620385290808935734592790788255073585330621151468871219769656595135843333814407503403584485725875093573131958504623569333490646639116961719078216840229603919536018487825851994866357917761987217050792416697381377048912395473353778387941958191907824408107449076068401916848269614839157102521989010679392116485801486351905021880108912590420172605418475794616003449288680484874497236175444664128438401914724753429360434711903099273327857734995750524336685921743399501618966233467673179877216701974657036419446491274854437281396070824372634560507303755215464570159167837973755757084277460889038540426254099700613477619367190997235567982845416706558020882785247647017658533190054489579620395565959077232929730085201031313238724372408560517067025821200011117585158799293570307490792480672057216647059928346781983773928742745961020992758462787355967282442061725370293489410415806016306004266400903317110818168429756442671778827765363252714782616931406456862197207387559816797319132734318242504254436838880072071853192476696183220292931118231156006566093505435792459195491243680582,
270666484654665630744901461996006692323963839982688652821336211084979467239347411813160298980515940583603861222174521984995420008548684262439808167328926021870579303960012771121601180529687766238396064375729105115543248938593316359682370849163035376370382430086321848989469101241917690539277074390985259902303859203469942292526312785642432913613936993258827179590899881832319079212987637373648192635781867448864854757206430089991579140087742146982306295873762255307312524837239897502872553828380739799963200435212855355849421115331904398013024635259514540481471626803307520164323612306097337438109957993918779265436327033558060626053354750562352860044802675727693412211125966360236444057953485024215560142475510160722114624532935356913983972915673608523025209720167213909179022327299978019112977846926119199262414918029479523990318896183663433071251579236571042002734675157891234966022932698905198698241706452025453847010887618278823570050783989170662300961633292513523806788091889082274722372602239592372048577727269817482906420208931626412130427401917267155522492175168008656904232528370893411707370782832090829602128710489070166301148107529844470225377087526762510454613609000260941022095648201987928579356978933393880920171979201,
653824340069025689137734254884130538700629136163559226740194794484993327658776187767570065320577134162743283784425272380809589160993088925874733196055173409287931015748252064633449072261545303183579447460502965342804624603405929157397131141984984644568357653302213965819415468460642952197339991556281367534783709497954301841184449070203282829556818406681886900718807834059676277878423047814575995317125009067646248518224341963179051812872833920966444865854397107596362642091691676816880789051432546280982801936460897107739053704289586862815777802365195344200436339914632247470287475059508482642321374344266084746769130713777040613388188063244264539412036380560226898399218628361640805872727932488302521211097971713325651815102241321497845489911517697687601337373561866169629605144418239966598946278151568343055898100847891792937851579379932984962575775149818916217268297467279875725571404166944999117855879952146915514369003878816227211205583465391314024099614444033724650197415698616726563650695337089763944873372957911180655004798934831152909017151923470147174567931032793367193038245769647005250292165097213630935925441110568790329108402080201984414111112552177466252777781418725448757243067372449888316330317213717511659267093522,
358008688390962979576377899144327321078101097951911268175317488500603502519487932330612462905624620597194558963905078036617959827652774950608159539755872698070336695988156123259549872787213397592148258199055613243895883287122890753360508292871837174063088420693224462093920149982044282287843545879889673811146267351528090047294284591799007589644031290908451176760853222636619363811207185693725681140126798792027873548626157363148637874670590965485611082128311321694683523699469128409485949494113757646949983087406842230923148769118322570130431421259760535420603207584288801345366412235455743468488327636151425392848303200702882860489019370153190810988494600882544600108525238483037309140333051358221984674540701977879624246387893765464282113949391789532777484259814371861241414118348867987309273292578129887971446610687731851915056696448523460974558006120340055071716623978233935275849865817975522109696101884471525506261697387468489779620579480299246665603825623773259263912587161909414417437045900004826755951647391749631385635652448151832357232824962202646901774457696625192040117636828038808343932086478692164048901540300465526784540912169577834838256728624868904132298644241575543460006379361856217382572895303794378838795856964]

pt = b''

import gmpy2
from Crypto.Util.number import *

pt+=long_to_bytes(int(gmpy2.iroot(ct[0],3)[0])) # 1

r = 688234005348009046360676388021599552323079007705479727954148955984833460337936950913921276804334830417982234720038650432729780498514155995618937412575604196815690605161835755609341381092145548153312943119696398326144902639226831471200542337105282064399184931676924592908530791494346900227871404063095592748764296028255530577278656680463782655139421219302422899667665339277824718421901831817043159552132252016945226370677278067424506514993298100924479619565269428391036310378044733517453768164252655931111202089432697078947184486267865943138659836155939343134738408972426979329158506027280653209318479413895259774319848662706808171929571545923310500352950348748809789292920278241362015278963315481777028997344480172010960294002098578989469089294022590134823913936869548907125294447477430739096767474026401347928008150737871869441842515706902681140123776591020038755234642184699856517326004574393922162918839396336541620212296870832659576195010466896701249003808553560895239860454162846759635434691728716499056221797005696650174933343585361153344017021747827389193405667073333443569659567562247406283282451284155149780737904760989910944550499316655128394899229284796584787198689342431338201610314893908441661953172106881929330452489260
pt+=long_to_bytes(int(gmpy2.iroot((ct[1]*pow(pow(r,-1,n),3,n))%n,3)[0])) # 2

bytelength = int(math.floor(math.log2(n))) // 8
lm = len(pt)//2
r = pow(256,bytelength-lm,n)
pt+=long_to_bytes(int(gmpy2.iroot((ct[2]*pow(pow(r,-1,n),3,n))%n,3)[0])) # 3

r2 = bytelength//lm
r = 1
for i in range(r2-1):
r = (r*pow(256,lm,n)+1)%n
pt+=long_to_bytes(int(gmpy2.iroot((ct[3]*pow(pow(r,-1,n),3,n))%n,3)[0])) # 4

pt+=long_to_bytes(5789294961746878883045450977581610159144202) # 5

print(pt)
```

- `sol.sage` (for the coppersmith attack)
```
from sage.all import *

N = 698809279803729100079401078372877880427534404702960341414657347899868695112937851068715263778044026960633490809424029064042059332067584211653792196700294350014573184050423710869400198311885677686776017504286227076537554159472858525076085634316345875740693290133882175978733925820699211845215919301594415766540019628304963946324745390725546428536097179973714842991708107348137633653650305109545081201035764079475728847207709375197074999828255856201471365404842335215247826759981584891713402716199125948297913830799181837372349720366417853754796224373298275046483568482746775859489692619384473186252774861885551132459800952522899651670157743254166927522541977826908655008388262139384030791486359107484039097526310532872263205859627319202436841723699816330454014234233782897304181837031056847338989710295447928978914887694045437118913508152754428093165631142831515262870346794228649249227188823826429873812279500464419259184458884477035660529116246947819203737674026095282077223581457285927181664053908670826417300651727432619278835787730219365136633094261034800600159172455889800794002324761994100506313076450253206268905858518116325377063495847739400746814680699716314543913219769366318366988661130926848067294360557400700653304560747 # RSA modulus
e = 3
P = 1055907876428738747574382336202469504446655031205994630903177234937821046662420222917012401772515913763767571126730872354583024615812842801460992368232078865570360913785000917439703813554983538737013673725222004456814292944244011048014308963951328381660375642993000068454423211042399329067936374597387713150143044921479748680644849442287947642150310109169214904626221843830298646615413271925078710566050752863854614554182042009078994859831427444764196803869676420481534245191031804260264003314463482809831347285829023902898094041116890173180980607552410318330377152693938362229088785046372775058225050773843211469417451430610818172709839171799720927834846615530530761050132799558314161160583670577126654468113339993232777956248046920042262012467591519032144943214627065716583364129326995138175332031025632324238736760999572055686086674940496080199045190113313122801612353163981438745982359021020494442572329182438610064907517626049710297327840045121286408400570354995674612468648690804871212698641500080238502109240993773138967060641103337662207817912063459587526581811237659378769735615076013497260366362097025021678541473147955220627824334019221910564791637346190086313142776229908696910370701297799276932943759117280694708994048 # Known prefix
c = 358008688390962979576377899144327321078101097951911268175317488500603502519487932330612462905624620597194558963905078036617959827652774950608159539755872698070336695988156123259549872787213397592148258199055613243895883287122890753360508292871837174063088420693224462093920149982044282287843545879889673811146267351528090047294284591799007589644031290908451176760853222636619363811207185693725681140126798792027873548626157363148637874670590965485611082128311321694683523699469128409485949494113757646949983087406842230923148769118322570130431421259760535420603207584288801345366412235455743468488327636151425392848303200702882860489019370153190810988494600882544600108525238483037309140333051358221984674540701977879624246387893765464282113949391789532777484259814371861241414118348867987309273292578129887971446610687731851915056696448523460974558006120340055071716623978233935275849865817975522109696101884471525506261697387468489779620579480299246665603825623773259263912587161909414417437045900004826755951647391749631385635652448151832357232824962202646901774457696625192040117636828038808343932086478692164048901540300465526784540912169577834838256728624868904132298644241575543460006379361856217382572895303794378838795856964 # Ciphertext

PR.<x> = PolynomialRing(Zmod(N))
f = (P + x)^e - c

# Find small root using LLL reduction
x0 = f.small_roots(X=256**18, beta=0.4) # Adjust X based on expected size of x
if x0:
print("Recovered x:", x0[0])
print("Recovered message:", P + x0[0])
else:
print("Failed to recover the message.")
```

## Flag
`ENO{s0m3_0f_th35e_me1hod5_4ctua1ly_h4d_th3_sam3_1de3_th4t_i5_why_1t_i5_ju5t_1_ch4ll3nge}`