RSA Private Keys and the Presence of Weak Keys: An Evaluation

The code contains two packages.

The factorization package contains the factorization code.

The universalkey package contains two classes:

• UniversalModulusGeneration: Multiplies all primes from 1 up to 2^24, which will be used to generate the private key. This number will be saved in uniKey_24.txt.

• Main: This code will do the following:

  • Generate two primes where each factor of p-1 and q-1 is smaller than 2^24.
  • Encrypt some data using the public key that has been generated.
  • Generate the private key using the number in uniKey_24.txt.
  • Decrypt the message using the generated private key.

Factorization Attack Example

N = 18369583373607319524848230962864856788641872197252249438510296626216984019007677702311097233452292800473780549833857255316215760088065227188397682289515575253632392397154509976661652110491280121945920658057741810958542678894186440036821454425304791711282798209813170929253634748758078024559105723170657056597590907448619311520601807972190177072206898115185040151891234092197380308491753453831541747105318516636718409456228079194323214814365300355951159745383220310112790585573021538809712101420219793936813969140292008646607866839526754976413947326170794193769109782049514397188341708331264800385010840190811956595297
A = 16135453
B = 16372597
C = 8338737178219779217262339729177172656984767229074467323520238877822001331814997575307844024904832045978308876022952803468558728387340737937040841658681537275437803450097529841604640562567252528627953774738450498502616683671277595830753047553434834979705178215756672060779219765553084628769389703699134
q = 134549301818517871230513271370170998079662833340671300998696608961869644855438298071493677795182746950776841888551181881585166339633702271968439459664097986675574731992286538175309122379197462514807502618464855311415541876393767097480111753405212768377788856956965641473116243903752816032530935402721302797703
p = 136526783307909622553211731662906989512230828980442936477665492490311865539270233856492481158624778441488321968646769001210914230718389803925781073018404361151221154453656466792066613260766911048456450088421430416432446407226308551665799854114224518884216061739763041712297671195835136733735823554615330230999
d(65537, lambda(N)) = 1558485361396781156668945027471099176125488251807972018845236463641204511391962721529706849410104785770789000522620797231652757928146899147400175627020788866933388386812361144689108808008093284125564112223025777573042572410446635840503410291545143056464034498617135842656026049171055609777279681239248488057407524103

Sample Run

When the private key is not generated (i.e. the file uniKey_24d.txt does not exist):

[+] Generating primes.
[+] Primes has been generated.
e : 65537
q : 142982867531359865557575017031614245494083466143021189451072799951877219911651013578060428816921520046273368314748597490360043801786853473905747186566923044497275565964216464584984818359296386791484449196347233284082335445096824652058191155290603579051659932430591202857933169557360302353974589345923030033437
p : 146338040869731240116992713249761598051741210939621879268163527559420210571355671025286286876997364851435983025105265586593609299521889664094649464039872501978893684612779065903823804670334509976367986456480704127152911817071943566208903257650006333277896865223086520173516718484405116836636188253961440658613
N : 20923832712475507953892343523721090417158803754976663905654041001661653353023987811701551638512431125162515019396813201834269074281425027001333472036365364570476623908866103763200972533577621183972593766199643439956498301700117114906432042172089532968024488934016840900143619134624389922985313562118960599159705744916004797028188956893069026902782539755267080271883775828776808824924204564745149875258070231711976545125367971519972688849058849302724017640758198476000081714808137802048082913065826146038968649921692633817745108724121983280867483281066953077620891563766590801678655755508300233781267497313248692042881
[+] Encrypting Some Data.
[+] Data has been encrypted.
m : 111000222000333000444000555000666000777000888000999000111000
c : 17697760989605948401360578545988870209123213861584305612066207059715073295101722493635989565717219705674844506272208914056740933150261475601829459994628713032175712745426564302735986968677743274319593401203940504667847555799849105483652028982990148039879943876499561984166773952356642597956257435643943785672527083393317483524335752512887856062635565807895571688216069277565694538953566393862881016977121156710085672964643263229393923574644771651251282321096811871159416377923943322090374433615682522357004818625154928241000877136595203941524101374789709744356408415453532012361817671385343396510632864621208290784517
[+] Decryption process has been started.
[+] Key has been read successfully. Processing into memory ... Please wait!
[+] Key has been processed successfully.
[+] GCD(e, UniKey): 1
[+] Private Key Has Been Generated.
[+] d Size: 24197127
[+] Key Has Ben Written Successfully ... (uniKey_24d.txt)
m : 111000222000333000444000555000666000777000888000999000111000
[+] Finished Successfully.

When the private key is generate (i.e. the file uniKey_24d.txt existed):

[+] Generating primes.
[+] Primes has been generated.
e : 65537
q : 150757653309815231531214539473827840092354647919501177739773800797262234284573956687993700778441682150968722495680036896445797580869856215981232080975821034050215211307863322495659858275039013690996348000091740092973043074301151112561298334268097085596462963559983362097082519016995850248397814413876628692407
p : 133082075738639457189689273802207271516568149382717126485108177675206358172815495543356387750545214654338326671351270636039075681314359608088004972470413162508051828736586986623321829250114966941868322834103075209631116447955983906616077208638697988499435760722780752194779026965532832130839075699954784032403
N : 20063141435956380086732743348355783895102368874562802784796224471885369352166752644259709207996402954344251963985159045124924835378152358017912995842043216290263879037565602945162836637100119326174708987519306441025110967500326425582456400362426035078855463070160736135070158689294663064828984678898460599079939956110145868823115194787463661477313948818887414260740165468353015581868539818983317366307354877655522675321808962223993946560831454818855690914805995726586929892675606962430481989447438987786850906362453032265993314445978786371578996441506952545480625834772820663288278728827938592928023019788524608064021
[+] Encrypting Some Data.
[+] Data has been encrypted.
m : 111000222000333000444000555000666000777000888000999000111000
c : 16865078599271488591163353412161680269289480527289509534559468887717720970430409160015654103999206418336954185829810034956929826479210076154438946200005070290336548486669280271758883388902045366572825573573129196488318220311686512475890250135570008827979380503167232343106783306778639720747161081978079347165122340481046885607691874852525505281420091304810305108266989090812750603131706946896612713466997896286666561854254312038535544245599687218140404623499593079322862416219379260157192665420198457951619752647666503002546348023004907059037671238752515508697452035275007261319733312567378783165359961212081208770966
[+] Decryption process has been started.
[+] Key has been read successfully. Processing into memory ... Please wait!
[+] Key has been processed successfully.
m : 111000222000333000444000555000666000777000888000999000111000
[+] Finished Successfully.

Paper Link

Mahmoud M. Almazari, Eyad S. Taqieddin, Ahmed S. Shatnawi and Zakarea AlShara. (2022). RSA Private Keys and the Presence of Weak Keys: An Evaluation. https://doi.org/10.13140/RG.2.2.17106.22728.