Before your start on attacking RSA, it's important to first understand basic RSA operations like encryption and decryption. For this challenge, we have generated a publickey. Your job isto encrypt the provided message with that publickeytoget the ciphertext.
RSA encryption uses the encrypting exponent, e. Decryption is the same mathematical operation except that it uses the decrypting exponent, d. If you can encrypt with the provided e then you could decrypt (if you had d) just as easily.
One ofthe most intimidating things about RSA when you firstread aboutitisthe notion of a "modular inverse". In our everyday lives we're pretty familiar withthe idea that (1/3) * 3 = 1orthat (5/7) * (7/5) = 1. That is, 1/3isthe inverse of3and5/7isthe inverse of 7/5. What happens though when the numbers "wrap around" because of a modulus? As one example, you can verify easily thatthe inverse of2 mod5is3mod5 because 2 * 3 = 6and6mod5 = 1. The idea that2 and3 are inverses mod5isnotat all obvious. Or, even ifmod5is obvious, inthe general case wherethe modulus is large inverses are not obvious.
In this challenge you are given e and n (as well asthe factors of n, p and q)and you need to find the modular inverse of e mod phi(n). Recall that when n has two factors phi(n) is (p - 1) * (q - 1).
== Generated Public Key == Public Modulus (n): 98160686216077010306650598451384523493996357373041397278666044179163041918013 Encrypting Exponent (e): 65537 == Secret Primes == Prime p: 296478161395804220864289487232795949083 Prime q: 331089095243782724782290601373623640711
What is secret decrypting exponent (d) thatisthe couterpart of e?
RSA is an"asymmetric" encryption algorithm because the key used to decrypt (d) is notthe same key that is used toencrypt (e). This challenge will let you experience that first-hand. You provide your public key (n) and (e) and this challenge will encrypta secret message (m) and provide you the ciphertext (c). Then using your decrypting exponent (d) you can decryptthe ciphertext back tothe secret message.
You are highly encouraged to generate your own key here instead of finding RSA keys somewhere.
To pass this challenge the n value you provide must be at least 512 bits, not be prime andthe e value you choose must be at least 100.65537 is a good choice for e.
What is n for your publickey? 106293394713836728584770048927645487102102551426684751134581194296372962576295840454537397021655815550308189352325607048529938553341796769007606529397626198231177636817810729599073564849299319322213650544188212299806442994412502877875106694978621139604395094335492409498378148226052685740633787250985960933413
What is e for your publickey? 65537 The ciphertext you must decrypt is10747018944552439199720581255039720388084637469960708491916798595496468141161787523686458134928624981502687900182498988328445362551185644407711340320568644670092570168829217359152240930612218395791282480938275664550764054659163828364062000797849017204210153179497288454002327624996357110961011485773669626403
What was m (decrypt with the d you've made for your key!)?
RSA is only secure when factoring n is hard. If you can factor n into p and q then you can compute Euler's phi(n) (the totient function) which, when n only has two prime factors, is just (p - 1) * (q - 1). With phi(n) you can use e to find d which gives you the private key!
In this challenge, a secret message has been encrypted with a very weak RSA key. The RSA key's n is approximately 128 bits meaning (assuming they are the same size) p and q are about 64 bit each. It's your job to decrypt the secret message by breaking the RSA key (factor n!) andthen determining d using n's prime factors. 128-bit RSA keys are just big enough you can't use trivial methods like trial division but are easily small enough that almost anything more sophisticated will factor them in seconds.
RSA's security relies on factorization being a hard problem. Unfortunately there are many different factorization algorithms that are quite fast in certain special cases. This makes generating secure RSA keys quite challenging because tons of gotchas and pitfalls must be avoided. One pitfall iswhen p and q are too close together because an algorithm known as"Fermat's Factorization" can be used.
In this challenge, a 2048 bit RSA key has been generated using two 1024 bit primes, p and q. The flaw is that p and q share approximately their first 500 bits. That may not sound that bad since they still are different in their lower ~524 bits but you'll see that isn't nearly enough.
Message to decrypt (c): 10426074392847872381473627569957969180320053109752606227916079994083532053799703036065905282122615431437721866313171294013350515428252537309345482269880415619442294601156752585446010009194624361395148280761278099888525138605830066285813688990522801677857932428538220521983981413448850469004996008927906933730792935466887940039979883069300623808947669972015213977651647997784626563669640738954071792582917241174307901215091315797664765124678924852716239603589657100939596203624339673928916386333510127266261894581633834712017193560070996878504040955960547901590264230976711955989542053963668368387177301946035693856117
What is the plaintext (m) for the encrypted message (c) for the publickey?
fac: factoring 25240054906527308715123083513191206839625173490523222251828485342363714336785380565865997526799064756242760495920245470292094107572885037758544627319924131106469206061990262762473830559723089863710658174860933300953411483624472662692904888669381554917178242116550796585404855973132973772929016519378021061815488878618803864877487986518434955737510882129986289035083960210216734245350444938463326983372446311710518586992606167860499851814468283028623132695394370326534082149664539102785030529344576581865843167524739917242789374803048921371234481347145388496209423571350226798734660569948183356006127158058090767513593 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations Total factoring time = 7.6796 seconds
It is critically important that the primes used in an RSA key have never been used inany other RSA key. If two keys happen toshare a prime then a quick comparison using the GCD algorithm between the two n values will find a common prime. This is a common flaw for keys generatedon devices with poor (orno) entropy on first boot.
This challenge generates two keys that share a prime. Use the GCD between the two n to find the common prime.
The modular arithmetic aspect of RSA is one of the main security features that prevent trivial decryption of messages. It's important that the modulus n reduces the resulting value's size. For example, if the encrypting exponent were 3 and the ciphertext were 125 then a simple cube root would reveal that the encrypted message was 5. Because of this, RSA is generally considered insecure when used "raw" like in this challenge. Messages are supposed to be padded in size so that 5 becomes something like 100000000...000005. Exact padding schemes vary and are supposed to have some randomness to them. Also, the encrypting exponent needs to be big enough that encryption operations produce results many times the size of n so that the modulus by n reduces them greatly. Finally, it's important that the same message is not encrypted with multiple keys. Using "Chinese Remainder Theorem" (CRT) a message encrypted with multiple keys can be reconstructed if the sum of the modulus size for all the key exceeds the size of the encrypted result (pre-modulus).
In this challenge, the message getting encrypted is 64 bits and the encrypting exponent is 101. This produces a result that is approximately 101 * 64 = 6500 bits. The message is then encrypted with four different 2048 bit RSA keys. The four keys combined are about 8200 bits which is bigger than the 6500 bit intermediate result of the encryption operation. Using CRT the 6500 bit encrypted message can be recovered and then the 101st integer root can be taken to recover the original 64 bit message.
== Generated Public Key 1 == Public Modulus (n): 23149105273119856627850090136919929723261823943624757765177549219866234384407443983691092738521031053203614477766656986767286266446444753737595544946472216224508161386171999255740873450148968555277596893973797691032923207849752189313156941377324765127716924091042774578614137857563130021083931714855059086528319464004755957875715598938914828284652002920579316752760142748768497603128211200838068910581466727558789046853980447659618327548379965828203663511630084649428450353266659376896302538711661311614077550561369584239426264779153594798510395598348794151054501986173283660486525134797651978877284141209813142620353 Encrypting Exponent (e): 101 Encrypted message (c): 4133098674895364475122584859727936636319542148084723385127010324327313789334393930206458052870325462125129516244259655103297937948615632716958036799846515784943596344659171054099447520291118273021064059336853671027556967972413169273404209750919489026617828517460910331013223288149485999850602777587671440578608610811039866904431406022561453341605551948558124880741033754123533721467625272714253906039692619129939195122566028002230169531368415886389935020627567435607209913240567022647994916867444034515723636583599469039313449903333413389457244138789788808665623522246598817641042647619000635273611183224626880248944
== Generated Public Key 2 == Public Modulus (n): 27505003639755307755377499909116790316666559241048462052708838019026245876061305032506336142607123275928140916064623611321267478241118533648691082780205975675848930891049661612587641417134731442097549122052889052873494510311763619581247175094225425295301201416148508869270650795946882209628169916402212595347072398536774964258765618683344988682136591522691855765474591800551003356738950115475986218748865738256040385018144667288963471023985981776397834650529125410415157989610913249638002630420759275424711122746274087218674581203767628461879942706575343687840846649398728521575759042643850479174348322700725152859179 Encrypting Exponent (e): 101 Encrypted message (c): 1739787364426947826729125390015498042633640345967134916542238682709304408943088145667424845845517943847244192660150225311643364678630739496448816122882054922412037008580775971375290713350552018895747047751648267738492662247630323384176319114392074862370478124092683816850069295355099746484470004393034493698412438690692636346398477331324809186840095746501169042776273857686097678768604865263346852531284195968241769030057050871599017420069734395480513006992209345486383715490267735794610384399680997873975671890958828764776368371097805716088332777475179458219585218216497145123375660441094713278890674938571932381488
== Generated Public Key 3 == Public Modulus (n): 23943992665005716914265748181378044020163225463944348787139747620070493441066981349214063664476165988435985828513188893343155039302311995874372727359429651639443442258295642274472710398428893112110181883065676797050367135114334409107720580674354846328795686014101403670618429882603919281846439213906309422478551046883785057516103930044593323333307553091446120290651424839856749893243675869030846434162150766596575521905731655641301802636196920315967062547856059292665187665794385263754141467629309390311239484966966962304043655439642471022652647482083941901373189746935767061122773274542240116211061429832031627444639 Encrypting Exponent (e): 101 Encrypted message (c): 19767759825914120713480654388913002907682584898016181997793326000329269531331547744785734164928410151086832198173774683214897941427775071585114906921627736047610200414157221293720422178460316657569689615289690667699532754041172774690035641861841049734906636233903208024641071920381980528962741503024268715672111438448667026120256281719821441794618486573597045681470587530870988650916524194457151054045651116850560891414366638095586467350677980494433751521957595486130004535388092882581591841627178062736831925448026071811776224612588994657584656478966565710308371560272935517045167518919934363672571637207453820737908
== Generated Public Key 4 == Public Modulus (n): 23764882147307056027005386922771967158083000845038109106003774249423632198485870921435962915038604258992363942683714487677164840502159532488262243238422271988447264107769115146700709762088120987424670297526032023889996339452998923199685412788748818176001822310309065993936711895735716914143587537590216206044501353689058205837089559899900836823313025042963189643956178442108568422925457393179572553420165084207399626407406447085305010961166687962292136079785531624901866292850569253781233922810459554095009877264479825892076775128519566724087703837984362767805722834293423659825643823352593873758485964298109062499299 Encrypting Exponent (e): 101 Encrypted message (c): 4200591912955199563979501872447323146617285786017413457040833853096647252495282176757667370964891089582307763252793332014110634684577275241510438935460795623158895099508356538022570772990943795127101179891821312550040505597385238071003932128751650976515586342666263903701969711589529513715648354184394669982822015645429160867813979611140609363112226286104769818496188762050564612227378368967743343698409735242567687523483613871073583201483076450563741645337691456798723334003820025909864260550025607987279304993898490653449697341369989367293215886097687051801809614329388180441198807195809708893458983328341875490575
The same message (m) was encrypted with all keys, what was the message?
One of the slowest aspects of RSA encryption and decryption operations is the need toperform modular arithmetic mod n. The other operations that are slow are the ones that use the decrypting exponent, d, since d tends to be quite largelike n.
One common optimization isto implement RSA operations mod p and mod q andthen use the Chinese Remainder Theorem to assemble the smaller results into the final result mod n. This iscalled RSA-CRT.
Although RSA-CRT can be substantially faster than traditional RSA, it requires saving p and q as part of the private key andthen the intermediate steps toperform an RSA operation use p and q. If a hardware fault (like a bit flip) occurs during an operation with p or q there is risk that p or q could get exposed in the final calculation result.
In this challenge, two signatures are provided. One signature isvalid and the other signature was produced using RSA-CRT with a fault, resulting in an invalid signature.
Using the faulty signature you need to recover the private key.
See https://eprint.iacr.org/2002/073.pdf for a discussion of this issue and section 2.2for specifics.
Signed Message (m): 76589046204045860242452095050720941865379417190758198073582782077942829633646
Good Message Signature (s): 17325267447814446311355159968784166643403597062830555186292278909407730058965908425047388536352948396884805415515011080230756248824282492130908750756123192695675198318659278263688404328209023590879438869601583177837203307625831869828767421917697572620208858182749108816360161491597773218856070998037376245034974546384410507173259914610628592075718146841935598464732970089109029209226228627059215763957981996096436107902541481923438970091699518171836243620582740860277567287363646182037455413444739511958943032953778117438478454480617990915477445067705592198996202631720932689361239443694873608130401548530381941318233
Bad Message Signature (s): 15560881472440963776812355687263772526799224459493465055411530467812341984615805222376647328602748875265740363403184343010139401584450440120706769134393997687683465315417839518347583296628663097911219566569959436210328102687469397856364290519652485072922276969140055247679930269523169632492462567935396255717642826528934615993335270136129635684773184252764824838098967401117436037823782028218281686360820286858701887330347540973559854295889323011981842854554834266081896736088393072010095414016636556324175277435257379852551709036180461462719357770502022163873660878350507927593844159774420414635489802142702898337920
What is the private decrypting exponent (d) for the public key?
n = 23154885630854261581442853508324093951285850590669895605587380575521607235130640544163038357995530183077307108610005939771651006915357243729445798049117319493254714109948731131702737721279228901692687894303893338872375856964797219358972744318545166050544352909134282184933180708435651918762591420996061517085207453652776549270709284644419226914688644151059035005050410930727981245377188391115441239955392677194034468965281888607451952614751181223872620212423712394604641694913836491081539520184795848120063846286690175706164225270915188223556103208363481609433822007116992669527079368460205470274996573363959160287149 e = 65537 m = 76589046204045860242452095050720941865379417190758198073582782077942829633646 S_ = 15560881472440963776812355687263772526799224459493465055411530467812341984615805222376647328602748875265740363403184343010139401584450440120706769134393997687683465315417839518347583296628663097911219566569959436210328102687469397856364290519652485072922276969140055247679930269523169632492462567935396255717642826528934615993335270136129635684773184252764824838098967401117436037823782028218281686360820286858701887330347540973559854295889323011981842854554834266081896736088393072010095414016636556324175277435257379852551709036180461462719357770502022163873660878350507927593844159774420414635489802142702898337920
q = gmpy2.gcd(m % n - gmpy2.powmod(S_,e,n), n) assert sympy.isprime(q) assert n % q == 0 p = n//q d = gmpy2.invert(e, (p-1)*(q-1)) print(d)