RSA 2K … You Will Have a Big Electricity Bill To Crack That One!

RSA 2K … Boiling Every Ocean on the Planet … and more

Someone contacted me and asked if they should upgrade to 4K keys for their Web site. “Why?”, I asked, “We have been told that 2K keys are insecure”, “But you would need to consume the energy to boil all the oceans on the planet to crack them”, “Oh!”.

In order to understand the concept of work in cracking cryptography, Lenstra [here] defined the concept of Global Security in order to show the amount of energy required to crack cryptographic algorithms and compared this with the amount of water that energy could boil something. This could be seen as the carbon footprint of cracking. For a 35-bit key symmetric key (such as AES), you only need to pay for the boiling of a teaspoon of energy, and for a 50-bit key, you just need to have enough money to pay for a shower:

So let’s look at RSA. In order to crack it, we need to factor N, into p and q (the two prime numbers used). Once cracked we can determine PHI (p-1 x q-1), and then we can determine the decryption value (d) [here]. First we will take teaspoon security, and where we would need to consume the amount of energy that can boil a teaspoon. A sample would be (242-bit RSA modulus) [here]:

N=p*q= 5896261486983538627098661478596873684661596787145726508859641645687965941

The prime numbers have 121 bits, and, if we were to crack it, the prime numbers are:

(p): 2526944374765758521282783272842906989
(q): 2333356264531983395509730755656883369

Now we try pool security, which will have a 745-bit modulus [here]:

N=p*q= 32820593417068637302218774761235133563284012029917056683084157063791880518253729060356882948911691226183490705953686023149594165668325095998315760949745673726122108730625118573143944403355956100353972339795087626332085413773

You would then have to consume the amount of energy to boil a swimming pool of water, in order to recover p and q, and which would be:

(p): 5136574890107321107930054184342872847511932740355863615831749987190796683508207354267329960601590388187075433061
 (q): 6389587248163902409204449208538775019640799414724150251382810569000364623759594714615114512184726059299258653193

Now, for a 2K modulus, we would have to get the energy to boil all the seas in the world in order to factorize this [here]:

N=p*q= 43167595701317556262423026656965675311752941263790242843723869722559144737611460632568632166086252510023021805945735591772225470974213720757550705733352824448503063524999506226660596906575816882736759369162417329042308450768818539569647978275834799861395280256322795630706924323442073941650079693323544638961692274755658766444829616155400362106306476222028695948219411648554898625217423276610753800859051583718732195244823763757178756946886496848799638990325775625765337088319529344897632569507945680260646306289624365294219736449252864209416787913390862597496737460530614841627093463597005887159713

If you could afford the energy to boil all the seas on the planet, you would be able to recover the prime number factors of:

(p): 196609148217569855881469103057436778288884865730728431036496969106242709174542556226244974424242605165013577403243273721574500460326174617160923703395095978667090714867455310166651932606597318485468745721964757615177804666962624050069365974032392172635080905056653578728556376998092239415714121906067
(q): 219560463450804526512484156665207894511493329487508026519690092833541901773486924130405885017845670513121751269792879364231218578683707161192474640518621978728363979172391042793592947789410287416485864619629721775927035570271970144478351754084252110756000450203907965120369883036301470716442779209339

Finally we move to solar security (4K modulus) [here]:

N=p*q= 3960081571383420167814679941098524090937928309488590816012966209196161594447717629829982817426147699500858353736336886688538212500739476494518433176312774088968991333976947698248519629991492642529120005788698131019622899051239531916630515702854026672543263467130654985378038454931630236636653155999253153667000741616739898252666802505968932136484029166497432922043251656271894573751299513374223876341473788971768959659494093660332016468558662263427959769631314190762350433414241237989194424754061077772372503406770663167105510157438848063647609081050040392193568744736442564106876056012592222564834186803873526496760807948668990042316968129375782077793420316049776474546085038021971914974545368413754514832542993932007256348508892381012868762395242004260990250419466271752664052646884549601175933263521857652478403283808673329360714989274196579539004889158891187902257130712437178153193341806763422097034483621244566078923257429637598615691552350410659591140346748167709449018947885391433407732878878772283602778821869413553383175098670195132506173740601661352893351053048344129586887687118260226198269183634491741066922963

You will never find the prime numbers, but they are:

(p): 2387628035654914041578676682340635535950948791037039903330270590495501744849764207480076462162294270197243407459110192208709737698247332428053357258855955290692393471421516310661792749482905080962109692416944336517049095407867686284521225687878370847230533829287501911033500368831913293493330562838467387835530549969054109399131451846959457130413492668037089837378118350872377084885693225874836148717207853352068189405415387476462556003921350678166912349980061364631958090280213640154021116006326720158290040518790513066623093136091263566334119222952846436577451
(q): 1658583963769377603578396329705793644732710623310129654038348230711585763044092787355651332948374169988931521882298144371384733551640579147022118494636732293264604461116977329421823894181755805820089237394172033870263627093736577790369697957516336302977958796425947479274422794199973433467842572527064416348509712003954901454840352976743534063167992440103943082723957859216188269111695713462656653049479588103312185114742167076660911677070759504987871743971457634287384430572107927280368523691106585718147625665698291217102305172813935222056309427697965967221113

Conclusions

Your adversary has a budget for cracking, and if they have to spend the amount of energy to boil the water in a teaspoon, it may be worth it. To crack 2K RSA — without a quantum computer — would require the energy to boil all the oceans on the planet — for a single key crack. No one has that energy, and no one can pay the bills for that consumption.