A Guide to RSA for Beginners
Hi guys! Today I’ll try to explain RSA in relatively simple terms. RSA is a key cryptography concept that feature in most CTFs. It might seem a little intimidating to beginners, especially with the rather complicated math involved. But rest assured, I hope that this guide will help to simplify things. Now let’s dive right into it.
A small introduction into RSA
RSA is a public-key cryptosystem that is widely used for secure data transmission. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977.
In a public-key cryptosystem, the encryption key is public and different from the decryption key, which is kept secret (private).
It makes use of the prime-number trapdoor function, where it is easy to compute the product of two prime numbers, but much harder to factorise it to give prime numbers, especially for very big numbers.
How the Math Works
You can check out this Wikipedia article here, which actually explains the math behind RSA in detail. Do note that a bit of modular math and congruence relation knowledge may be required to fully understand this.
Attacks to crack RSA
Cube Root Attack (Small public exponent)
This attack is often used when the e value is small (say single digit). Let’s see how this attack can be used to crack RSA implementations which use small public exponents.
Here’s a sample problem to illustrate this example:
n = 81832507579458804740250584856923933092398801685885683858740598563784998986420046289169539484692213329249102876941392571693602184898624601614151420131581689452549417902911480947066578195782197823307860997361580966665089526326483752568366293605132381827954870366511712131028081177062838287529180851266732989497
c = 186035579992453204660167654731539505540120087566437631356217089894239617370847231609614206764208623183075851675884383009415698552997259734642161918768122812546137099960045259689649922538369565123709665455527752800635284847292158024526879370134702068906005612874893
e = 5
Rightaway, you can tell that this RSA implementation is bad as it uses a small exponent. Hence, we can use the Cube Root Attack to crack this.
The Math
\[\begin{equation} c \equiv m^{e} \pmod N \end{equation}\] \[\begin{equation} c = m^e + kn (k \in ℤ) \end{equation}\]Using the properties of modulo math, we derive the 2nd equation from the 1st. Since the value of e is really small (5 in this case), \( m^e \) works out to be really small. It seems that c and n are of similar size, so the value of k wouldn’t be too big hence it is possible to bruteforce for k.
Hence, we can easily rearrange the equation to get:
\[\begin{equation} m = \sqrt[e]{c + k \cdot N} \end{equation}\]The Script
Now, we convert all these math concepts into our script, and we make use of our computer’s power to help us bruteforce for the value of k.
from Crypto.Util.number import long_to_bytes
import gmpy2
import math
N = 81832507579458804740250584856923933092398801685885683858740598563784998986420046289169539484692213329249102876941392571693602184898624601614151420131581689452549417902911480947066578195782197823307860997361580966665089526326483752568366293605132381827954870366511712131028081177062838287529180851266732989497
e = 5
c = 186035579992453204660167654731539505540120087566437631356217089894239617370847231609614206764208623183075851675884383009415698552997259734642161918768122812546137099960045259689649922538369565123709665455527752800635284847292158024526879370134702068906005612874893
for k in range(0, 100000):
m, t = gmpy2.iroot(c + k * N, e)
if t:
print(long_to_bytes(m))
And thus, we get the flag xxdydx{5m411_3xp0n3n7}.
I hope with this, you have gotten an understanding into how Cube Root Attacks work, which is one of the simplest attacks used in RSA.
Wiener Attack (Very large public exponent)
This attack is often used when a small private key (d) is used, often leading to a very large public exponent (e), sometimes as big as the modulus.
Here’s a sample problem:
n = 13704044832982292138395293766088413802848766696644681657989345648894307723945223260343949171705289793010442774065636046758834301006600656747553732002162894939273006424207989120611833238240923807366554841711183420216945437415961153960094592268784605121352361193425452780806466204619466742707267232257961818470285175851985227359835748601358045311793424386509746386595159562306722822079463647698598960652225445875077492633632010490587862704242764441744589267868404206164783432637852761334239604216347630356677596978234675737589246551120390571732510435614967325503986534325883291103328316168149236405105688473830080862177
e = 31853764682752559836706569837484301725651302628464025674092531295008821814438422598774435580749172569773400017970206952362997692325938113382519281111787457501999999650954078859365719161348435739410815940045733895389467468054781312667556867621739454410956782913329509718709566185280706198292535867176662879975912523514453252654467471805631717503384918290800891334447091017561484745847402618777537364154368951548571516909469743821463157123635350458830956380255948566466144030833961497468043286051595984714140223822548157499428068136519635273994712698521102688868435319667263809339762500035697002016549186916519108917603
c = 2241287056775250403738434452363598789742608867060801677763572233298639695715701463119531113593421834897758950202113838694318091826284915910476782176437347425950342835162606572468361230425686288332083329771527234968864894020407952101523691943142819592413793652638168070036096090317398273982949929122350496956713888535142025139409667462450632575085617031477368269697075161832317831994081328431405837378666098354106686822673930146846995737053014621066225289588727920479747553392920755793772708167510933765022166554749118833879456138543087426339817576703393935447141570412147728554829735844184716481598193302148221928749
As you can see, the public exponent value is really big, almost as big or bigger than the modulus.
Hence, we can exploit the Wiener attack. The math behind it is pretty complicated (tbh we don’t really need to understand it for the purpose of CTF i think), but fortunately there’s a Wiener attack function available on Python, so if we use that, we can easily find the d value, hence enabling us to decrypt the ciphertext. Let’s get to work!
Here’s my script.
from Crypto.Util.number import long_to_bytes
import gmpy2
import math
import owiener
n = 13704044832982292138395293766088413802848766696644681657989345648894307723945223260343949171705289793010442774065636046758834301006600656747553732002162894939273006424207989120611833238240923807366554841711183420216945437415961153960094592268784605121352361193425452780806466204619466742707267232257961818470285175851985227359835748601358045311793424386509746386595159562306722822079463647698598960652225445875077492633632010490587862704242764441744589267868404206164783432637852761334239604216347630356677596978234675737589246551120390571732510435614967325503986534325883291103328316168149236405105688473830080862177
e = 31853764682752559836706569837484301725651302628464025674092531295008821814438422598774435580749172569773400017970206952362997692325938113382519281111787457501999999650954078859365719161348435739410815940045733895389467468054781312667556867621739454410956782913329509718709566185280706198292535867176662879975912523514453252654467471805631717503384918290800891334447091017561484745847402618777537364154368951548571516909469743821463157123635350458830956380255948566466144030833961497468043286051595984714140223822548157499428068136519635273994712698521102688868435319667263809339762500035697002016549186916519108917603
c = 2241287056775250403738434452363598789742608867060801677763572233298639695715701463119531113593421834897758950202113838694318091826284915910476782176437347425950342835162606572468361230425686288332083329771527234968864894020407952101523691943142819592413793652638168070036096090317398273982949929122350496956713888535142025139409667462450632575085617031477368269697075161832317831994081328431405837378666098354106686822673930146846995737053014621066225289588727920479747553392920755793772708167510933765022166554749118833879456138543087426339817576703393935447141570412147728554829735844184716481598193302148221928749
d = owiener.attack(e, n)
m = gmpy2.powmod (c, d, n)
print("d =" , d)
print('message:', long_to_bytes(m))
Here’s the flag: xxdydx{lAr93_3XpoN3n7_15_8ad_lOL}
Small Modulus Attack
The whole secure premise of RSA is hinged on the fact that it is hard to factorise the modulus. Hence, if the modulus is small enough to be factorised easily, or if the two primes are known, it’ll be very easy to find the original message.
Here’s a sample problem.
n = 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
e = 65537
c = 525712785518469874437278825147177601576667010796196954724530146238629326041160681
Using a popular factorising tool, FactorDB, we can actually factorise n, to give p and q. According to FactorDB, the values of p and q are:
p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033
Hence, we can get to work now, as now all we need is to find the totient function, and with that we can find out the private key, d.
The Script
from Crypto.Util.number import long_to_bytes, bytes_to_long
import gmpy2
import math
n = 1280678415822214057864524798453297819181910621573945477544758171055968245116423923
p = 1899107986527483535344517113948531328331
q = 674357869540600933870145899564746495319033
e = 65537
c = 525712785518469874437278825147177601576667010796196954724530146238629326041160681
totient = (p-1)*(q-1)
d = gmpy2.invert (e, totient) # d = e^(-1) mod totient
m = gmpy2.powmod (c, d, n)
print(long_to_bytes(m))
Here’s the flag: xxdydx{factorise_the_modulus}.
Monoprime Modulus Attack
The modulus used in a secure RSA implementation should be a product of two primes. What if a prime number modulus is used? Will it still be secure? Let’s see in this sample problem shown below.
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
c = 70714384643118444370704561367337462736501868678891899446079778482983138453009820058229381851044255506983008836721646205239556140398487897703881844518256564914225164619536255336792526924379355949730690493361729237445684355599472452115656074315432477235148635419354509824295429620435724113577096532131823665386
\(n\) is given to be prime, and you can prove that it is prime, perhaps using GMPY2’s isPrime function. Anyways, if a prime number modulus is used, it is very easy to crack the private key, \( d \), since the totient function of the modulus, \( n \), is simply just \( n -1 \). Hence, it is very easy to just use GMPY2’s invert function to figure out \( d \), given \( e \) and \( n \).
Here’s my code:
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
c = 70714384643118444370704561367337462736501868678891899446079778482983138453009820058229381851044255506983008836721646205239556140398487897703881844518256564914225164619536255336792526924379355949730690493361729237445684355599472452115656074315432477235148635419354509824295429620435724113577096532131823665386
from Crypto.Util.number import *
import gmpy2
import math
totient = n-1
d = gmpy2.invert (e, totient)
m = gmpy2.powmod (c, d, n)
print(long_to_bytes(m))
And here’s the flag: xxdydx{dont_use_monoprime_modulus}
Prime-squared Modulus Attack
Similar to the attack before, I’ll be explaining how to attack RSA implementations where the modulus uses a square of one prime, as shown below.
\[\begin{equation} n = p^2 \end{equation}\]Here’s a sample problem.
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
c = 39870589384887810131905870499537909084916348679745515732822429242821249327447648499429729189108525499673497777454890315418590953160562899911182151664221448755430051852380249668687749236382248217767749293413441809715937269324539551406861736989421885760142641670464157419188086390414525932677513909266258066014980670984599953824857719132085723416777239649457191358023828717110884306308556465984884513433892423452635376245371513822599720628350803250747002401589988660161437485992319144544139418355775372605319283891336953801864650896505303916540900558679948893838794415194795321224440080683273518681921537617822917324566003395834696950187328557055657036281601937721767162830251189369009629392526213061122415280818338865916562053386763207016527035365445612266022987172471028276074825295682110910095254551950317830484773521736558967092476739803258114509830336539072011954933905125401074027267005271990086734438852130113976196448758836265496605718893905198811144782465059378918384797396212300728227871523411829997875053243389067780143797209149971767392298348728758066581643965006682219191163382861091676937393052949924089760448725249682750384476211283681152692946298545466670776049703067296556273791496491272955078833741994938359572065149
It is given that \( n = p^2 \). In such a case, the totient function is just equal to \( p(p-1) \). Hence, we can just adapt the code given in the earlier problem.
Here’s my code:
from Crypto.Util.number import long_to_bytes
import gmpy2
import math
n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
c = 39870589384887810131905870499537909084916348679745515732822429242821249327447648499429729189108525499673497777454890315418590953160562899911182151664221448755430051852380249668687749236382248217767749293413441809715937269324539551406861736989421885760142641670464157419188086390414525932677513909266258066014980670984599953824857719132085723416777239649457191358023828717110884306308556465984884513433892423452635376245371513822599720628350803250747002401589988660161437485992319144544139418355775372605319283891336953801864650896505303916540900558679948893838794415194795321224440080683273518681921537617822917324566003395834696950187328557055657036281601937721767162830251189369009629392526213061122415280818338865916562053386763207016527035365445612266022987172471028276074825295682110910095254551950317830484773521736558967092476739803258114509830336539072011954933905125401074027267005271990086734438852130113976196448758836265496605718893905198811144782465059378918384797396212300728227871523411829997875053243389067780143797209149971767392298348728758066581643965006682219191163382861091676937393052949924089760448725249682750384476211283681152692946298545466670776049703067296556273791496491272955078833741994938359572065149
p = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
invmodulus = p * (p-1)
d = gmpy2.invert (e, invmodulus)
m = gmpy2.powmod (c, d, n)
print(long_to_bytes(m))
And we get the flag, xxdydx{s4m3_pr1m3_n0_g00d}.
To be continued…
