Write-up 10 challenges of RSA on Cryptohack

Register

At the first look on the register form, there will be a small challenge requires us to solve Roman emperor's cipher

To solve this challenge just simply bruteforce the key of Caesar Cipher to find the plaintext

s  = 'QBABEZBZRAGOYBBQPNZREN'
for rot in range(26):
    result = ""
    for x in s:
        if x == ' ':
            result = result + ' '
            continue
        y = ord(x) + rot
        if y > 90:
                y = y - 26
        result = result + chr(y)
    print("[+]",rot ,result)

And the key is 13, our flag is DONOR MOMENT BLOOD CAMERA

One register, we move on to RSA section challenge.

RSA

Starter

Description

All operations in RSA involve modular exponentiation.

Modular exponentiation is an operation that is used extensively in cryptography and is normally written like: 210 mod 17

You can think of this as raising some number to a certain power (210 = 1024), and then taking the remainder of the division by some other number (1024 mod 17 = 4). In Python there's a built-in operator for performing this operation: pow(base, exponent, modulus)

In RSA, modular exponentiation, together with the problem of prime factorisation, helps us to build a "trapdoor function". This is a function that is easy to compute in one direction, but hard to do in reverse unless you have the right information. It allows us to encrypt a message, and only the person with the key can perform the inverse operation to decrypt it.

This challenge this simply ask us to find the solution to 101^17 mod 22663

Solution

Just simply run pow(101,17,22663) in python

Starter 2

Description

RSA encryption is modular exponentiation of a message with an exponent e and a modulus N which is normally a product of two primes: N = p * q.

Together the exponent and modulus form an RSA "public key" (N, e). The most common value for e is 0x10001 or 65537.

"Encrypt" the number 12 using the exponent e = 65537 and the primes p = 17 and q = 23. What number do you get as the ciphertext?

This challenge require us to using RSA to encrypt the number 12 with e = 65537, p = 17 and q = 23

Solution

We just simply using the RSA encryption algorithm

C = m^e mod n

e = 65537 
p = 17 
q = 23
n = p*q 
m = 12 #message

print(pow(m,e,n))

And the answer is 301

Starter 3

Description

RSA relies on the difficulty of the factorisation of the modulus N. If the primes can be found then we can calculate the Euler totient of N and thus decrypt the ciphertext.

Given N = p*q and two primes:

p = 857504083339712752489993810777

q = 1029224947942998075080348647219

What is the totient of N?

This challenge ask us the totient of N base on
p = 857504083339712752489993810777 and
q = 1029224947942998075080348647219

Solution

To find the totient of N, we just use a simple formula (p-1)*(q-1)

p = 857504083339712752489993810777 
q = 1029224947942998075080348647219 
print((p-1)*(q-1))

And our answer for challenge starter 3 is 882564595536224140639625987657529300394956519977044270821168

Starter 4

Description

The private key d is used to decrypt ciphertexts created with the corresponding public key (it's also used to "sign" a message but we'll get to that later).

The private key is the secret piece of information or "trapdoor" which allows us to quickly invert the encryption function. If RSA is implemented well, if you do not have the private key the fastest way to decrypt the ciphertext is to first factorise the modulus.

In RSA the private key is the modular multiplicative inverse of the exponent e modulo the totient of N.

Given the two primes:

p = 857504083339712752489993810777

q = 1029224947942998075080348647219

and the exponent:

e = 65537

What is the private key d?

In this challenge we have to find the private key of d base on

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537

Solution

So d = e^-1 mod φ (n)

p = 857504083339712752489993810777 
q = 1029224947942998075080348647219 
phi = (p-1)*(q-1)
e = 65537 
d = pow(e,-1,phi)
print(d)

So our private key is: 121832886702415731577073962957377780195510499965398469843281

Starter 5

Description

I've encrypted a secret number for your eyes only using your public key parameters:

N = 882564595536224140639625987659416029426239230804614613279163

e = 65537

Use the private key that you found for these parameters in the previous challenge to decrypt this ciphertext:

c = 77578995801157823671636298847186723593814843845525223303932

About this challenge, we have the private key we've just calculate in the challenge starter 4.

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
d = 121832886702415731577073962957377780195510499965398469843281
c = 77578995801157823671636298847186723593814843845525223303932

Solution

Base on everything we have, now we just put it in the algorithm m = c^d mod n

n = 882564595536224140639625987659416029426239230804614613279163
e = 65537
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
c = 77578995801157823671636298847186723593814843845525223303932
phi = (p-1)*(q-1)
d = pow(e,-1,phi)

answer = pow(c,d,n)
print(answer)

Our flag is 13371337

Starter 6

Description

How can you ensure that the person receiving your message knows that you wrote it?

You've been asked out on a date, and you want to send a message telling them that you'd love to go, however a jealous lover isn't so happy about this.

When you send your message saying yes, your jealous lover intercepts the message and corrupts it so it now says no!

We can protect against these attacks by signing the message.

Imagine you write a message M. You encrypt this message with your friend's public key: C = Me0 mod N0.

To sign this message, you calculate the hash of the message: H(M) and "encrypt" this with your private key: S = H(M)d1 mod N1.

This challenge ask us to Sign the flag crypto{Immut4ble_m3ssag1ng} using your private key and the SHA256 hash function.

And this challenge provide us n and d

N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

Solution

In PyCryptodome library have a lot of powerful function which we can use, in this challenge we use function SHA256 from Crypto.Hash library to hash our message and use it as the cipher text. Before we use our hashed-message to calculate the message we send, we have to change the hash value into the number that can be used with RSA math and once again, we use the PyCryptodome library which is bytes_to_long function.

from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long

n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

hash = SHA256.new(data=b'crypto{Immut4ble_m3ssag1ng}')
s = pow(bytes_to_long(hash.digest()), d, n)
h = "6ac9bb8f110b318a40ad8d7e57defdcce2652f5928b5f9b97c1504d7096d7af1d34e477b30f1a08014e8d525b14458b709a77a5fa67d4711bd19da1446f9fb0ffd9fdedc4101bdc9a4b26dd036f11d02f6b56f4926170c643f302d59c4fe8ea678b3ca91b4bb9b2024f2a839bec1514c0242b57e1f5e77999ee67c450982730252bc2c3c35acb4ac06a6ce8b9dbf84e29df0baa7369e0fd26f6dfcfb22a464e05c5b72baba8f78dc742e96542169710918ee2947749477869cb3567180ccbdfe6fdbe85bcaca4bf6da77c8f382bb4c8cd56dee43d1290ca856318c97f1756b789e3cac0c9738f5e9f797314d39a2ededb92583d97124ec6b313c4ea3464037d3"
print(int(h,16))

Our answer is

Prime Part 1

Factoring

Description

So far we've been using the product of small primes for the modulus, but small primes aren't much good for RSA as they can be factorised using modern methods.

What is a "small prime"? There was an RSA Factoring Challenge with cash prizes given to teams who could factorise RSA moduli. This gave insight to the public into how long various key sizes would remain safe. Computers get faster, algorithms get better, so in cryptography it's always prudent to err on the side of caution.

These days, using primes that are at least 1024 bits long is recommended—multiplying two such 1024 primes gives you a modulus that is 2048 bits large. RSA with a 2048-bit modulus is called RSA-2048.

Some say that to really remain future-proof you should use RSA-4096 or even RSA-8192. However, there is a tradeoff here; it takes longer to generate large prime numbers, plus modular exponentiations are predictably slower with a large modulus.

The first challenge in Prime Part 1 requires us to

Factorise the 150-bit number 510143758735509025530880200653196460532653147 into its two constituent primes. Give the smaller one as your answer.

Solution

There are a lot of powerful tools to factorize the prime number which I choose is http://factordb.com/

Just put the number into the site and leave it do the rest

So our answer is: 19704762736204164635843

Inferius Prime

Description

Here is my super-strong RSA implementation, because it's 1600 bits strong it should be unbreakable... at least I think so!

This challenge provide us a python file which is inferius.py and a output.txt text file which is output of python file.

n = 742449129124467073921545687640895127535705902454369756401331
e = 3
ct = 39207274348578481322317340648475596807303160111338236677373

Solution

So the e number of really small, but in this challenge I don't use the exploitation of small exponent. I just factorize the n number to find p and q, to do this I use factordb (site above), after that leave the rest to the calculation work to find the flag.

from Crypto.Util.number import long_to_bytes
n = 742449129124467073921545687640895127535705902454369756401331
e = 3 
ct = 39207274348578481322317340648475596807303160111338236677373
p =  752708788837165590355094155871
q =  986369682585281993933185289261
phi = (p-1)*(q-1)
d = pow(e,-1,phi) #decryption key 

decrypt = pow(ct,d,n)

print(long_to_bytes(decrypt))

And our flag is: crypto{N33d_b1g_pR1m35}

Monoprime

Description

Why is everyone so obsessed with multiplying two primes for RSA. Why not just use one?

The challenge give us only a single output.txt text file.

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

This is what we get from the challenge.

Solution

After using factordb tool to factorize the n number, I realize that n=p*1, so what we have is p=n and q=1

from Crypto.Util.number import long_to_bytes
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537 
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942

p = 1 
q = n
phi = (q-1)
d = pow(e,-1,phi)
decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))

Our flag is: crypto{0n3_pr1m3_41n7_pr1m3_l0l}

Square Eyes

Description

It was taking forever to get a 2048 bit prime, so I just generated one and used it twice.

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

This is what we get from the challenge, and the challenge give us a hint, which is:

If you're stuck, look again at the formula for Euler's totient.

After take a look at Euler's totient formula, there is an interest thing that I've found.

After taking square of n number, we will get the p and q which is p=q. So to calculate phi number, we use phi=(p-1)*q

Solution

from Crypto.Util.number import long_to_bytes, inverse

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = q = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107
# print(p)
phi = (p-1)*(q)
d = pow(e,-1,phi)

decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))

Our flag is: crypto{squar3_r00t_i5_f4st3r_th4n_f4ct0r1ng!}

Manyprime

Description

Using one prime factor was definitely a bad idea so I'll try using over 30 instead.

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

In this challenge, the real problem is there are a lot of prime factor number, like they said, it's about 30.

Put it on the factordb to get all the prime number.

factorize = [ 9282105380008121879,   9303850685953812323,   9389357739583927789,   10336650220878499841,   10638241655447339831,   11282698189561966721,   11328768673634243077,   11403460639036243901,   11473665579512371723,   11492065299277279799,   11530534813954192171,   11665347949879312361,   12132158321859677597,   12834461276877415051,   12955403765595949597,   12973972336777979701,   13099895578757581201,   13572286589428162097,   14100640260554622013,   14178869592193599187,   14278240802299816541,   14523070016044624039,   14963354250199553339,   15364597561881860737,   15669758663523555763,   15824122791679574573,   15998365463074268941,   16656402470578844539,   16898740504023346457,   17138336856793050757,   17174065872156629921,   17281246625998849649,]

This is all of the prime number we get after factorize the n number.

So the phi number is calculate base on this: phi=(p-1)*(q-1). So all we have to do is initializing phi=1 and multi all the prime_number-1

Solution

from Crypto.Util.number import long_to_bytes
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464

phi = 1
factorize = [ 9282105380008121879,   9303850685953812323,   9389357739583927789,   10336650220878499841,   10638241655447339831,   11282698189561966721,   11328768673634243077,   11403460639036243901,   11473665579512371723,   11492065299277279799,   11530534813954192171,   11665347949879312361,   12132158321859677597,   12834461276877415051,   12955403765595949597,   12973972336777979701,   13099895578757581201,   13572286589428162097,   14100640260554622013,   14178869592193599187,   14278240802299816541,   14523070016044624039,   14963354250199553339,   15364597561881860737,   15669758663523555763,   15824122791679574573,   15998365463074268941,   16656402470578844539,   16898740504023346457,   17138336856793050757,   17174065872156629921,   17281246625998849649,]
#phi = (p-1)*(q-1)
for i in factorize:
    phi*=(i-1)

d = pow(e,-1,phi)

decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))

Our flag is: crypto{700_m4ny_5m4ll_f4c70r5}