Skip to content

Instantly share code, notes, and snippets.

@briansmith

briansmith/2^((nBits `div` 2) - 100) apart

Forked from lgarron/2^((nBits `div` 2) - 100) apart
Created February 4, 2017 23:12
Show Gist options
  • Save briansmith/0336e18fb91c1875b2ef5045ec592246 to your computer and use it in GitHub Desktop.
Save briansmith/0336e18fb91c1875b2ef5045ec592246 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
2^((nBits `div` 2) - 100) apart
In[121]:= p = NextPrime[RandomInteger[{2^2047, 2^2048}]]
Out[121]= \
2472858022210415099164045402553368874951528885035736322800760410002954\
4038243222193098931418739578329762267040841916783150979034128645102130\
0253513299160810798121444406865510009715543992322555089967015541632378\
0710135209985817236443936777772937122422269799403563157416882656645382\
0161318776579572843028782784167357793642890306031876148210563553196737\
6550335038180588177627102411796625979142817323054655605301722206159897\
4290495880080776782541535829627114438988359115159634994645719944873859\
5571411651510073958737684802610027599241818362961198138578683797158596\
029738178691750002854299388286460147158857999751670620041
In[122]:= q = NextPrime[p + 2^(4096/2 - 100), -1]
Out[122]= \
2472858022210415099164045402555918237217873618597038901176306682727254\
1887353810501828198428169415045621272117428572252242170768148085375029\
0070535791252750789667446889096842608702339623566861536229102914989505\
6423368317312498538562025844955226112009575158097753413758655227234014\
3435469917931601138611166384498715769205622853850395301691166423114443\
3891159241026969028153635379770052345963342972560125676929415704757645\
5992206576723061341749414534927907767489378970792775287718542201186720\
9218444902528197475575330502029332629202622324108969523636160097928385\
726792993043184747607349348569597634579602353649923872777
In[123]:= p*q
Out[123]= \
6115026798010405815879744849315154282294292051681056341864151937990532\
8953123229116354155734972625328299240748062644098939680264981572705141\
6129603635497825193954718933468047304744811193856208032614767721282483\
7077447979287258104783969012093864668250116505859901156803627675691771\
1653139085746512256280968462930384205901196925122453729082789409513632\
9849904055407389766587100215680552944399894373770709683913812754779344\
3567244269382636703257179105474332975181719776979071484453652198197251\
3132199069434977609408005351121946086864849944623915660838296263631679\
6160680549866015805915112775786103982513182424465424649852768756447582\
9206976252235429606074311664314279306375090722652079353442442513748719\
7877868810467129258589662135239076409613734756354726611172773380584966\
9889109257823976287817930524291632003848615162896668323624239224348219\
6552522631223847354471072130712045637901804202285820559987434241410421\
3898774705789082022241548944863936786055516876021520984201469736519366\
4160639843408157272238461388033513157571444962708525505846657152177912\
7787590262604958822203508302323380186116321776131376278126446191002070\
0369619149855152545019755594867573193796039491639060460228286666940236\
8254339866153362614689946030125735590523857
In[124]:= e = 65537;
d = PowerMod[e, -1, (p - 1) (q - 1)]
Out[125]= \
2026056912766802750904264456078692343038867473491347748710471873621411\
2835316199963875583832479295457202644515364332422362577128550435169742\
9693733514521564555312766329269346768622744865700195328138258789690218\
5212928657433869760399150146155701014791385473980223289421761315744863\
4982319332711289304253855825015950724734708485773058886938732154938111\
7023373310635458769728127532283862957332488616080339198872461817862866\
5236723409148642345156573952061731025574802985143103257906626849438563\
1782848934093887480517653053912475965182772352984782712962796055182542\
5512809824370823614288733979483642246002887577472911955778096464525646\
2222982936732928027835607959447699355333740881459055139931814282067539\
3288528522396432998355112308101399418735480046932175344185462214726483\
8554410388419210041063870955521079009602311784114645882797222356250357\
5889461349575898035023538076783200949426997358522258448179070455175850\
7978916657397794917662063025883091307325376151326132483214542133313920\
2799449185433024385066005692407247917473032321091797861986705637897993\
6931453218679257230115931969973755898158943578254920862395068177354396\
4252764742641901345129605089162558252102254729533191433254663547303585\
2283491945206250261328788610556425536564353
Raw
Just under 2^100 apart
In[98]:= p = NextPrime[RandomInteger[{2^2047, 2^2048}]]
Out[98]= 2551990309704378844129048930531822024127612704989383440297053\
8572229764916291096542826317330239616319370005054354224406681913876794\
5010194515709922923312284720946271465729654486724381113153353817229555\
4959677086223023672484977708052985830253244106437161746159365307130032\
2837881165055279622054495920576450040711902375680693861193551264119797\
7071350375363813884431281508141378057686522253231551845658465015850125\
1370374787613077610573558414544647916994952461591620750466292015622187\
9337847543150156338356527338771712806115172409446379802257817009359579\
009372935681904156931289114891879949525228512549814805316223938269
In[103]:= q = NextPrime[p + 2^100, -1]
Out[103]= \
2551990309704378844129048930531822024127612704989383440297053857222976\
4916291096542826317330239616319370005054354224406681913876794501019451\
5709922923312284720946271465729654486724381113153353817229555495967708\
6223023672484977708052985830253244106437161746159365307130032283788116\
5055279622054495920576450040711902375680693861193551264119797707135037\
5363813884431281508141378057686522253231551845658465015850125137037478\
7613077610573558414544647916994952461591620750466292015622187933784754\
3150156338356527338771712806115172409446379802257817009359579009372935\
681904156931289114891879950792879112778044206812927143627
In[104]:= p*q
Out[104]= \
6512654540825051449660058388264623052404399436485267892897632801080337\
2014450673496714368011393109512350230631732741069730018410361724925995\
3100327406432404771121984555324926749996058317202530310120769608112677\
8715758961676678764064091968418999380842216954444403237078042174866082\
3222135936950487166689830951206375625540875267008240651626765129721912\
7927919518140286180887136973862739744818086534739763626095782616036627\
0944859200657969239171723114494136199579484946527512593580746750060361\
1822946248646997089462311874352251029919544803682969374077861740216369\
7303977173518861660391859848506031717635554784274563836016824913932798\
1414882894950607070348718071822600298547906660456831622950429311343261\
4434070810593178241906039911254966966877188331654272762804520111915520\
9369806704423621833122693305244714221959300418092732366745423712953589\
3262538318427710668866997153755630956468692021568057981212077703378430\
8102598336385103708471212754940117270771979262497589986283130190325566\
7764011292143892316525561493889588792452930512611276623040103941165580\
8507854717161215382184296102769667893285188220135565043336996303674594\
9955210357837006897577379587832479071357836347665550777504435801004875\
3840857967048752442330250140032498944761663
In[105]:= IntegerDigits[p*q, 2] // Length
Out[105]= 4096
In[106]:= PowerMod[65537, -1, p]
Out[106]= \
1985262095604900233612025292968916524346523010489856660156319282280223\
5450619786914916980277516614413391534059937766802353846150733387940776\
9571982245132218623495182235032042582002061771089574403219775513845944\
8661190104739332262533612716233595438889265869729205203982642414580611\
6209367547663218724060441467043272026783783437222192411898921929640746\
7341705040968613533264749340296808887140153008944649921465537480531330\
0835826110744643920971814162261831657679259055510978009864137928622734\
1691325825082485211599527503458654423467732448212617064988928645419539\
799968256600514410860013663528155473325407147404321910444
In[107]:= PowerMod[65537, -1, q]
Out[107]= \
8278577594994445004529285787128879294589780751037473784383686315296775\
8994209181454825137928329682919542595397343609088920379178273508350022\
1858333666420369130005604675437150676375229636028549087431580610078808\
2014966091983250083648393846404926942468233016974854880385810512128317\
8826501787521336538360823331177051819120733553408746185389459275476585\
4438665667181751508779116759451220395151256883699126636399844425807833\
5086139127636884796865772726141368895957681486017573012516245093956677\
4092851939127480846283262013520387784736871476570668419211231783461039\
1988162986342381528909421782896089136916886395231443419
In[108]:= e = 65537;
d = PowerMod[e, -1, (p - 1) (q - 1)]
Out[109]= \
5917704165679414892766780246595942792173611645981624166837878348174833\
7633100959865867229428848736918999286420185311056386813499809889365442\
7378801242855939455884678582626598531551112696483065748625842351085798\
3620297635959018880937740157763574974886766553811804213924918923864003\
5748938691813807631969413203905269824693823674418126108982313250147853\
9879878653359995759217373495789037517797840199334008635335823348413585\
3560070882084655510515832452936902981292374209465086515216342966051154\
4380372142559602616498781941768414007838456033375357831855847332497441\
4063076440530512716119676731900059337247620235951451492008521951963626\
8691314820964432565405172670548231139993498385931074011576403600935482\
4421464418832009408559202883202169755953771038154093128412937035001668\
3811366390821518226002403206559120427753988371324064834063175929817608\
9221069713308998797529975645967179843705123688906692956857933521618607\
0480730967419137999636333101801992283426395750355364227628699826014767\
9213038568053187374598489390399975895635034210226580504600317595590540\
1771907802466682425580317633043863306334237121790462210763786772126272\
3030166252798769077732219175000064667268530477706973421676574659212180\
5356355479129182974986314934079421108894673
In[110]:= pk = PrivateKey[
<|
"Cipher" -> "RSA",
"Padding" -> "PK CS1",
"PublicExponent" -> e,
"PrivateExponent" -> d,
"PublicModulus" -> p*q
|>
]
Out[110]= PrivateKey[
Association[
"Cipher" -> "RSA", "Padding" -> "PK CS1", "PublicExponent" -> 65537,
"PrivateExponent" -> 59177041656794148927667802465959427921736116459\
8162416683787834817483376331009598658672294288487369189992864201853110\
5638681349980988936544273788012428559394558846785826265985315511126964\
8306574862584235108579836202976359590188809377401577635749748867665538\
1180421392491892386400357489386918138076319694132039052698246938236744\
1812610898231325014785398798786533599957592173734957890375177978401993\
3400863533582334841358535600708820846555105158324529369029812923742094\
6508651521634296605115443803721425596026164987819417684140078384560333\
7535783185584733249744140630764405305127161196767319000593372476202359\
5145149200852195196362686913148209644325654051726705482311399934983859\
3107401157640360093548244214644188320094085592028832021697559537710381\
5409312841293703500166838113663908215182260024032065591204277539883713\
2406483406317592981760892210697133089987975299756459671798437051236889\
0669295685793352161860704807309674191379996363331018019922834263957503\
5536422762869982601476792130385680531873745984893903999758956350342102\
2658050460031759559054017719078024666824255803176330438633063342371217\
9046221076378677212627230301662527987690777322191750000646672685304777\
069734216765746592121805356355479129182974986314934079421108894673,
"PublicModulus" -> 6512654540825051449660058388264623052404399436485\
2678928976328010803372014450673496714368011393109512350230631732741069\
7300184103617249259953100327406432404771121984555324926749996058317202\
5303101207696081126778715758961676678764064091968418999380842216954444\
4032370780421748660823222135936950487166689830951206375625540875267008\
2406516267651297219127927919518140286180887136973862739744818086534739\
7636260957826160366270944859200657969239171723114494136199579484946527\
5125935807467500603611822946248646997089462311874352251029919544803682\
9693740778617402163697303977173518861660391859848506031717635554784274\
5638360168249139327981414882894950607070348718071822600298547906660456\
8316229504293113432614434070810593178241906039911254966966877188331654\
2727628045201119155209369806704423621833122693305244714221959300418092\
7323667454237129535893262538318427710668866997153755630956468692021568\
0579812120777033784308102598336385103708471212754940117270771979262497\
5899862831301903255667764011292143892316525561493889588792452930512611\
2766230401039411655808507854717161215382184296102769667893285188220135\
5650433369963036745949955210357837006897577379587832479071357836347665\
5507775044358010048753840857967048752442330250140032498944761663]]
Out[96]= PrivateKey[
Association[
"Cipher" -> "RSA", "Padding" -> "PK CS1", "PublicExponent" -> 65537,
"PrivateExponent" -> 65781037256793231210296451640048260743491100929\
9929117712372156706951364555894399036504338815989525109105206810889058\
7013187239436201431479888663253174368758862727380642118531238964331698\
6575725831124147178408125408616960222872784741847737767222972458476060\
2830355017192229165051620300119371146458211076984962542351295662718788\
7796299199636154889288362678240071796229110169254163735084971748768323\
2576047572375211252522732115849327394694281175626131747266344877631962\
9367505819336136450639207360700984033938715582891138808368377367989636\
5414174071796154782738821088666567376950138368064596769417808339870979\
1943288667782495593162628954611160893947485110676147539613047241327506\
5411060832376348158690870850137088025352982471509721491198747934167299\
8463766780944423568975009259644456982941051926910099715079977059336080\
9304273865401059464444352456732238715820620579032031991604227575617215\
0713844992305640522551903212098430800570779228272729520266805081633374\
3877181545286888555905570039834828129748274538512756109864198567876010\
2814093769812398665179022424280484489842374908966287959376149068641537\
0481721766234897349309100201138020329193703066967066251812786564661640\
867537033711856826945280492293934127575592945399784026157213495233,
"PublicModulus" -> 9225928434126129930297035077756041055354768621916\
0791361743995108079677236131765172178104889966413086533615688163919363\
3545737268726102582814294049870074913006305778858805260618489996161904\
8992774769695329633909679217021319393968698909594226267959138013922193\
9079303119600930469928179269224505276133751396086907503160554373397663\
6077000185230874377870708876518544147978071311440953403235305382275298\
1801981147821905188714035859479047821603974933679584661433068492907796\
1518209385876507801621581917181113320154089958775389667947157091972286\
4553856666890506754738310409049876269434211239191659128006559600505828\
3229133933244870347758355713449902217535391382040465204495145040134315\
9332526472409056530521741857404293104926434179112164746274266677143721\
7545155226760247901294330662015711657630821089459771018284632904139380\
5835218532120128905899311720328666166565542347138204384600060188636851\
9301461156368165340004173551856701161757924621519129728603966157935908\
9950583588960267487524343729741701240817346140214201501396434806396305\
2793358455657112494600996314220733453012368276789466761965205619589002\
8145111957518060080837199078360410721821718208252246002967323742513567\
9698053299372331547231015228788049176374458214178789358298921439]]
Raw
Some primes
In[65]:= p = NextPrime[RandomInteger[{2^2047, 2^2048}]]
Out[65]= 3037421346162914212671516208713978834816568088481597910454900\
3484508316197767662423585394513926769437078538861955518896022684165525\
8974219061500661714597261095942774401347907142877670313026746134284984\
5255697703720465884628692683442630226069773323702581530464278949470561\
5908726325847596231099052702940600281863754972755452666172920483128679\
1036137452555026306531277089083403644672321317774019805099753301162501\
9230247572622028379201330689711082780315056230091749786368948165664709\
9780549654615782523678555753545559561801544412178260235482066191043611\
779930192349331337110791851311240017152371071100480447984819498619
In[66]:= q = NextPrime[p]
Out[66]= 3037421346162914212671516208713978834816568088481597910454900\
3484508316197767662423585394513926769437078538861955518896022684165525\
8974219061500661714597261095942774401347907142877670313026746134284984\
5255697703720465884628692683442630226069773323702581530464278949470561\
5908726325847596231099052702940600281863754972755452666172920483128679\
1036137452555026306531277089083403644672321317774019805099753301162501\
9230247572622028379201330689711082780315056230091749786368948165664709\
9780549654615782523678555753545559561801544412178260235482066191043611\
779930192349331337110791851311240017152371071100480447984819500781
In[67]:= p*q
Out[67]= 9225928434126129930297035077756041055354768621916079136174399\
5108079677236131765172178104889966413086533615688163919363354573726872\
6102582814294049870074913006305778858805260618489996161904899277476969\
5329633909679217021319393968698909594226267959138013922193907930311960\
0930469928179269224505276133751396086907503160554373397663607700018523\
0874377870708876518544147978071311440953403235305382275298180198114782\
1905188714035859479047821603974933679584661433068492907796151820938587\
6507801621581917181113320154089958775389667947157091972286455385666689\
0506754738310409049876269434211239191659128006559600505828322913393324\
4870347758355713449902217535391382040465204495145040134315933252647240\
9056530521741857404293104926434179112164746274266677143721754515522676\
0247901294330662015711657630821089459771018284632904139380583521853212\
0128905899311720328666166565542347138204384600060188636851930146115636\
8165340004173551856701161757924621519129728603966157935908995058358896\
0267487524343729741701240817346140214201501396434806396305279335845565\
7112494600996314220733453012368276789466761965205619589002814511195751\
8060080837199078360410721821718208252246002967323742513567969805329937\
2331547231015228788049176374458214178789358298921439
In[68]:= IntegerDigits[p*q, 2] // Length
Out[68]= 4096
In[73]:= 409600/4095 // N
Out[73]= 100.024
In[74]:= PowerMod[65537, -1, p]
Out[74]= 6902408732228249899952224071345543248382310533249376334041050\
2295616575847743075892161264704809707070267280966645336667602397924405\
6319795609034492716404017501850212728576892607058172325847586886477299\
0126662175795184158532602977632649031365050904054586986466348229925854\
6733701751811686630416130110455828005217953645917108893802478715112900\
7873597369562538227744680056718972562080180872729675901757881183791315\
0036784884730742733333142799009285723672449522370024500418503292986332\
2555461190807154603528500059135147863635869955989872848472528767446253\
29790810605590606887575309238724652874715998014853522618336463264
In[75]:= PowerMod[65537, -1, q]
Out[75]= 2609827020214228027369970386634921680384451006766975295415198\
9490152857064139262382082139104227082621592834610305281360970648153637\
3164735181228371176750329883480073383192730810421357294304730176354147\
4833965445385097798637812437208568452327921717976350283991852112907774\
1389387493092512494765075556636528105833802375312148787476743295015930\
6804338558231626201185326520337756422099624421703355802752219481235968\
1674084426536445672844441040455327257004762674103125291365516275641934\
8394685927049900509496363169475319353717850487421914523402515056896971\
526613196536051343882780718360425967100525922528329867196746431916
In[82]:= e = 65537;
d = PowerMod[e, -1, (p - 1) (q - 1)]
Out[83]= 6578103725679323121029645164004826074349110092999291177123721\
5670695136455589439903650433881598952510910520681088905870131872394362\
0143147988866325317436875886272738064211853123896433169865757258311241\
4717840812540861696022287278474184773776722297245847606028303550171922\
2916505162030011937114645821107698496254235129566271878877962991996361\
5488928836267824007179622911016925416373508497174876832325760475723752\
1125252273211584932739469428117562613174726634487763196293675058193361\
3645063920736070098403393871558289113880836837736798963654141740717961\
5478273882108866656737695013836806459676941780833987097919432886677824\
9559316262895461116089394748511067614753961304724132750654110608323763\
4815869087085013708802535298247150972149119874793416729984637667809444\
2356897500925964445698294105192691009971507997705933608093042738654010\
5946444435245673223871582062057903203199160422757561721507138449923056\
4052255190321209843080057077922827272952026680508163337438771815452868\
8855590557003983482812974827453851275610986419856787601028140937698123\
9866517902242428048448984237490896628795937614906864153704817217662348\
9734930910020113802032919370306696706625181278656466164086753703371185\
6826945280492293934127575592945399784026157213495233
In[85]:= PowerMod[2, e*d, p*q]
Out[85]= 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment