Rating:
# Shor (crypto, 93+1p, 61 solved)
## Overview
In the challenge we get 3 datasets:
```
N = 3416356674834751205654717212071257500891004481277675802480899188082530781676946620047015174887499659759994825842311234570747025346194269593432201439553474104726357466423594117729691868522956307297012280773715009336391891527625452216694507033820734082774562411516154786816821799139109814782126237257954493537197995738073491626828821669476230971917909830728881441510625888688452097090833935723507974378873159008169669871084895916325728244256040953051421900207387581176872063669038872455907987681935770956653031961149178257817864076041790032686112960572631551662957882869381443972442620140208708846269452219913845752692040947773507733718069833552772389207842695834274596725601269983676368769026979527592867536756156322713708743946168101133561610926637848052441486328236721261416666787449231413994156377194904834445823205296393743874301916674863699954694052632649609814866866736039080083583524584794922211502053023693044595773419383663012687997167507079146962402233459843639452122470388183046710067826419546875172302687074961955298456070785841370571843245308435171042459399472863709320869064664474183630027880885944811713149681771668394805036911499525569725364876617355369131347083485036868905546790785483319564946606640739539740000000000001
e = 65537
Encrypted message = 2761381113410910848061431300230480498009026842114852457129705785252041512194320382139992607990523185711265558416291496166730903035100162870595351770249633960051157494292619436506842619411602708064741507667875940943200199830629156186966769529608798700085556407391764625041336657163923382446150480716540088086014660597539878575206223118477684139141382850852953596383417648061979405616513335248108939135401317656931895525429904559698612462360168606617613714419613744092435822735639489593242225248516709920461824689537628749384086945788127710215825798099407801004302766884540735728033427144173723144540438415615972235181583759134738853378222450717263640639637197665448224710544718570975791277317803802004936569093622711877823386532910160498710047256140658328647339389246101926399729410376417737133141155904985744908184776453418311221976969592540762037641244078748922362005375622546885851174461996130712712012110007014160102248347323006075438769540656035545567873264556383372389088602088215706058030212514538785797366617737232735823224036561813895187291608926452840528509117072693473454500812176162568323908661021204552565519477362475191073574449068082075563301731771738898463551240775337975574420761416092262799207037100971408380894166511517
Base element = 1055996486206343282900378582239294340792376691775344496933466299728441053731145595712130431971194025194789509268517622355475415699064683110017844110306038495669213294512300387373611752219357804438832230491906844604655582965815296272037439743337013140766325647199056633009800091721973373266284818365172234615731317282201888653323643200935585860690203559729920660732314791721010170075598012541020242212729633805500814805618699794746356843998160925987970495456937473496798050761424036710102809671554730207807099004826662404274037937805782414813889799092703191357895006998518119807675096524648668105710889520659292064959937083980230094792797660331780117673207101104336730141359386565164773139490936534220599679944915992879676814408158495294462729255659309148721319247178480380853423886332215762669161651462318898104177785569288415822890569538608749637828249746515568505820117008373602089204739125324422734144022818114547426262144105857697865525296381197288010175218167887685455029178631077447578643219786514691704255525825989866345315707869283456054142607295582337561819546799116128115591556912433522048087071838479458051821758524175955048742012086896119371652370796825701079986027369043480123068780648561901319601133577394286114422843702432
Order of the base element mod N = 4238905730299571511585410925992706985376240434599640426773730678688148201988287191828553430803354181800011233926113337354226603520697209783788323782074002570383969322036520148451330264738762823474389251519331890832896947816064451687914322654345208162866922224699576968808732333973644883697916363675589456970485473534854730462259729068231976448513756950228426287377821431710399101131033185211011454635767134370015858843667379202869398742242467296213912220088796029353706699766346980050862526610289204788284877119355791479746742348282652679426554008068210121318762257110078200503361306295050591594278560207575724450235102000132261276258646393369631386590170896001661198420859987589818266451143197584239528981328996248775188255680196412623826715722830666634670196882972751433186125430873698792718250532170807439694934936990057791640607436435301727450448556704183815360000000000000
N = 2991827431838294862966784891173748689442033961794877893451940972359233879769847725449228773148722094529956867779219983311911235955792605578395060263578808536063092916571136475239794888147950848214752108530874669597656040523610448227520304582640063474873583656809304967459752224335947620804298564179924078757517862179181060444078070172493793150026947727360122588243906747708457615039889721849607047000641714571579283754866961814830107819957024391003568024994181049938378413334966649251188961819321448682445927391114305975879570003772269969469588663531270178974591969925207103686182551942494472789179737369451543233260843746179834780752253276798913060176677373344860806929972937611690448747280201511208307706943617522916333696589954418418512093433247071173377326670866040814437718937690090980047459933178869155400675905036321541350337851757862692429647759994174403035047868866380532338380873261053816376341913465724835415340251162893735767326552546919855284937726326731441519889186734423951395212523220146945845162409884737237923785964497202757230883029324416637456965308473300854577504808364024330378522663828056533671597367520562225643048706011802233019317215123933958808152725154411743332088899288508468593418829959011282400000000001
e = 65537
Encrypted message = 2531660758159102106999922822493820302169183249029699298380750419804912981078240111089565187748502615169619449928310076159800762484249020730886854764078009557326494365796575309754306060895741885211198610505721203507814192128839503737291197069234351836810854223030378000820938504735126183620662226211294903835627678811157291048664678572304025634924267129428510979026314050106995314523210612331981768597984203429076023591397856707455528854522104986240723455104438487966058421959390227565424319636235073477666997681029116486647463880002823388608260093894456795540694720629625527329323684878152739366013269778011757631190103115043539594628554367787519741106584004241327421302272094113265773180162899203764874825552334657449934441071352148125558886491091793139344423110165781566037078043832296825375895852298473387015088375898655324500306048183570101483693662534978822756258118410200222284524929885793009405552015370616552679622972347070759844379580088041991521148785824291751921210406073912891922688439114984052272250782118904388849553081232965036241428691829851803371361644484044221342965264168539902013379507771257120299352913163345981016945342848447336225869621056777226811065585619753827670072917635971752035946214183086097252078340377
Base element = 1829153880209649817133271412751305881103610013739763088923077280434366008959719235452957078221891237308379781288879363791539430220845383889227740411644955884968196574019943709097001094862645074306716496415534566247816774897269238114091279124124091700764840107465580642637459959015903827486467910611609784194608612149345770563267560917386252645759909538776262146737382917080133277398970758572689056844853243427439055377394656794013749225347998189709948887047577042647905170078524777397680898109253683306111499807322326245646845259128584230086206539835934418642057740414834277630066579742969677059470203779983187308326453607258426368416380384523318952851218644550009238431278993675363425049662149668470280231683337923276272387771840117173908330607743659713860257263643040431559650893577414139138217937759522352285809151061311523338500433765023972281129640106225269532535796894086126118104841162208461340696704839068163154370315977002827143257580471764590022552133582987462716243934183478321807246787571759906333816115673026182562618376889910687549643049481188484777403338304913851833231384760713336723555123914290623703216306684354716413002921801327907807492210145023967509638599883924815959016469514087510318652377090383573408143189875
Order of the base element mod N = 38560713413761379609566936395075572668071080369628115670192641624417776440980701273226992681066964803737397381408237287334201476745729770113169915736677140504101099304776220304170036785989541305856749630544154979967581254694324718665152362814949431192818076514159143920559225991949100970917003919304615824659209163754766161614749009649133180228055247044270344226425323332646355266368819265059396049425171682329538795580522984697326474922568268329719528505679116152346876832004895230968147369090419957506470480923337840332756289795096914722280492211387936874519432905484354110305469319291675552896266756806053842137289993143099968838508275750939158109007269956200282881600747847025693151059090777570290662683532429738733835486556597653924207696863659981475762012361157891219362456668118612981384660665186944304494624842569258321135919050716021742463590031294193325414875000000000000
N = 639706454183841086618060975133506435367679028105293302817889792041855677471135941103994762703392838736550531721530519902301470750304779911155948306612218591799138935866091048693721293892613230480914682428803749924762632427878750084742837813855723359392232771898376144411173068466325310996285248870190702255300295718279606810768110856840161610010502480738215025268551716825052096172524263657070455782204684928203735045097429967165474359767392495180608955232616327356163710417152398486581379295622675189862310699861836394640703199409486435353374174382718391365103593266779715410988747697764215166949296221369189067831531714495456829718257893130130416683979435112783237218934779364887142409293199844536181411788012117636490932176828156653094980496223057242278831933489822824530461645422526392004499974646624081371558910799120884541611121693589957355055417494388914462063844749724848803935934167650377339476529423342556181857024514566806542877109818592708843793048372638440744883734584671163178855889594818530649315246941990069941785981955697316724277843473035594824612773270449343568535991703905499866381894302869556783328828954361131697748870040510488262322072045737316482227372952773445112189325175417604463517935092556879962500000000001
e = 65537
Encrypted message = 314557466900381591242205623579215445569259870097282668596289597435494983504258313716837830074410569549101885948568828637582431634467367466943722507276554179061705214704312821336717217276072271410024795714853171285472330519984587064351490291946402527076873292156733615667090804533241881526392028722581482187557723462380933494893691818228096727143987965819030197035623098060074104267041580315471527363573905276688203330678967500136780376909740475740022222411007552160610953916933397422648078574769436057858371423387220212599778301238209747504040262792435824139984626671181921830676755679706257094800530170169257172295175588719735103506516267986479535271545672025427357482695339982756270595766559224783234664773225592292836903578759322554594969550738489322024841847122750086552969841091794921189991698185013467950728556383510751767964677981993613884189958377917008871409895441041469390537626990484305898147725819267800469005035373857720477647896885556328405130736251247026436983943132062518372195855113707867220345039790830160353546642486915870683279621035540163308693026969159279331149570510984194914611989693165753486432581824076235984213086481799164719307250544991262352133753835282085522276721189362210449308160808673482171271973635244
Base element = 639304614539878463528258079784485748453961997788947903221008691564113768520824054912297976536885940415782622645768931907574552208662557961036585337121563972787735955983309963130196394585676321161401997238426213858836312606239377567018014879457602469055903523965367593064504320727353617645008844597485114399103468775003826394898641131760075425500944415018954023297315378870220312096580715953041280770744209039443690535218083691700925452593344949001347653528186426823387750740646066047708041588621042651593046230315985777228755475771740021166081093461613932804274331432897373691848802487920026711269596469629200479861558951471085509476724616504184151217773738289142755911284204461983148202468210535247036226138104957496934373369643383555984827000297035903273630278899210336015318311506134648061163404223082855619761623079750994914318022721602011861174058485022590668829472045006137826398687345964608059482609412099029725762290028597233216240977074149903617204351904445855117337610478775944092457560644108917597151881101242098843506234170355231516604966143012558147526635689505625221752278863528033799535375216911655599336840088585218525839719910996381383231125137334134672943265221074537386720854796169924885902033065767799038702600353014
Order of the base element mod N = 14340465843181389754296043575153150999880553806256424482462005187943660544889251567825193761881671644627116681986880575247775472382429862008693821301217688225108915963042069716362423106872635469122008951761035973093847332884289274367583111876861239752881719413283646415859188694420897533751169969651755858306856280014457872696378749964024941714569321714532004454417234363334457733364193711334660355969032846878694439112996047986990515538880360978717487357475370816216899522824940567676602652086299685154259807064490034942183064960225615267196543096878918185306891778544872672261753262617338859347952171566380431887826270695379201691684193987862510003351182776540049015193655070499556038737924000948120384038167880639676616861182091141971972645457231169645122120054623647146495784214301275060819958507861645053527917643055478749534854842138961878541223358154296875
```
The idea is that we have 3 RSA public keys, 3 encrypted messages and we have results of quantum step of Shor's algorithm.
The goal is to implement steps of the `classical part` of Shor's algorithm.
## Solution
Once we look at the description of the algorithm on wikipedia it becomes apparent that something is not right.
The algorithm suggests that if order is odd and when `a^(r/2) mod N == -1` then there won't be solutions, which suggests 2 of our 3 datasets won't work.
### Solving simple case
We can still first try to decode the first problem, which fits the algorithm just fine.
This part is trivial, prime divisor can be recovered via `gcd(pow(a, (r / 2), N) - 1, N)` or `gcd(pow(a, (r / 2), N) + 1, N)`, so we just do:
```python
def solve_first(N, e, ct, a, r):
assert a < N
assert pow(a, r / 2, N) != N - 1
p1 = gcd(pow(a, (r / 2), N) - 1, N)
p2 = gcd(pow(a, (r / 2), N) + 1, N)
if p1 != 1:
p = p1
else:
p = p2
q = N / p
print(rsa_printable(ct, modinv(e, (p - 1) * (q - 1)), N))
```
And get back first part of the flag: `First part of the flag is "SaF{Wikipedia_still"`
### Solving odd case
Now we can google a bit for `Shor algorithm odd order` and we get https://eprint.iacr.org/2017/083.pdf (`Shor’s Algorithm and Factoring:Don’t Throw Away the Odd Orders by Anna M. Johnston`).
It turns out that in some cases it's possible to use odd orders and solutions with `a^(r/2) mod N == -1`.
In such case the prime factor of `N` can be found among `gcd(pow(a, r/k, N) + 1, N)` where `k` is one of prime factors of `r`.
So we can write:
```python
def solve_odds(N, e, ct, a, r, factors_r):
for f in factors_r:
remainder = r / f
p = gcd(pow(a, remainder, N) + 1, N)
if p != 1:
q = N / p
print(rsa_printable(ct, modinv(e, (p - 1) * (q - 1)), N))
print('found for ', f)
return
p = gcd(pow(a, remainder, N) - 1, N)
if p != 1:
q = N / p
print(rsa_printable(ct, modinv(e, (p - 1) * (q - 1)), N))
print('found for ', f)
return
```
We grab factorization of `r` from factordb (not complete, but we hope it's enough) and run datasets 2 and 3 to get:
```
Second part of the flag is "_says_you_have_to_di"
('found for ', 5329)
Third part of the flag is "scard_odd_orders...}"
('found for ', 79507)
```
So the complete flag is: `SaF{Wikipedia_still_says_you_have_to_discard_odd_orders...}`
