Starter

Modular Exponentation

Modular exponentation: m^e mod n

In Python: pow(m, e, n)

For the challenge, we can calculate this in Python.

pow(101, 17, 22663)

The result is 19906.

Flag: 19906

Public Keys

To solve the challenge, calculate this.

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

c = pow(m,e,n)
print(c) 		# result: 301

Flag: 301

Euler's Totient

Euler's totient function of n (denoted as φ(n)) counts the number of positive integers less than or equal to n that are coprime (relatively prime) to n. Given a prime p, φ(p) is calculated as φ(p) = p-1. For a composite N made up of factors f1, f2, ..., fi, the function is calculated as φ(N) = (f1-1)*(f2-1)*...*(fi-1).

In the case of RSA, typically, the public modulus N is a product of two large primes p and q. To obtain the decryption key, φ(N) (or sometimes denoted as phi) is needed.

To solve the challenge, we can run this code.

p = 857504083339712752489993810777
q = 1029224947942998075080348647219

phi = (p-1)*(q-1)
print (phi)

Flag: 882564595536224140639625987657529300394956519977044270821168

Private Keys

In RSA, the private key d is the modular multiplicative inverse of the exponent e modulo phi. We can calculate it in Python using d = pow(e, -1, phi).

Here's the solver code for the challenge.

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
phi = (p-1)*(q-1)

d = pow(e,-1,phi)
print(d)

Flag: 121832886702415731577073962957377780195510499965398469843281

RSA Decryption

Here's the sript to solve the challenge.

from Crypto.Util.number import *

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932

# From the previous challenge
d = 121832886702415731577073962957377780195510499965398469843281

m = pow(c,d,N)
print(m)

Flag: 13371337

RSA Signatures

Basically, to prove that it is me who send the message, I can encrypt the hash of my message with my private key (not public key). This way, the receiving party can verify the signature by decrypting it with my public key.

s = pow(h,d,n)

In real cryptosystems, it's best practice to use separate keys for encrypting and signing messages.

For the challenge, we need to sign the message crypto{Immut4ble_m3ssag1ng} using the SHA256 hash function.

Here's the solver.

from Crypto.Util.number import *
import hashlib

msg = b"crypto{Immut4ble_m3ssag1ng}"
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

msg_hash = hashlib.sha256(msg).digest()
h = bytes_to_long(msg_hash)

s = pow(h,d,N)
print(s)

Flag: 13480738404590090803339831649238454376183189744970683129909766078877706583282422686710545217275797376709672358894231550335007974983458408620258478729775647818876610072903021235573923300070103666940534047644900475773318682585772698155617451477448441198150710420818995347235921111812068656782998168064960965451719491072569057636701190429760047193261886092862024118487826452766513533860734724124228305158914225250488399673645732882077575252662461860972889771112594906884441454355959482925283992539925713424132009768721389828848907099772040836383856524605008942907083490383109757406940540866978237471686296661685839083475