Write Up - IrisCTF 2023: babynotrsa | Why you should beware tweaking RSA
Informations
Sincere acknowledgements to aaSSfxxx who helped me a bit with mathematical demonstrations and kindly read my write up before I posted it.
This challenge is one of the ones I flagged during the IrisCTF 2023. Thanks to the organizers, I didn’t tried lots challenges but that one was particulary fun as a beginner.
Challenge
Name: babynotrsa
Author: sera
Description:
Everyone knows RSA, but everyone also knows that RSA is slow. Why not just use a faster operation than exponentiation?
Files:
chal.py
from Crypto.Util.number import getStrongPrime
# We get 2 1024-bit primes
p = getStrongPrime(1024)
q = getStrongPrime(1024)
# We calculate the modulus
n = p*q
# We generate our encryption key
import secrets
e = secrets.randbelow(n)
# We take our input
flag = b"irisctf{REDACTED_REDACTED_REDACTED}"
assert len(flag) == 35
# and convert it to a number
flag = int.from_bytes(flag, byteorder='big')
# We encrypt our input
encrypted = (flag * e) % n
print(f"n: {n}")
print(f"e: {e}")
print(f"flag: {encrypted}")
output.txt :
n: 21429933885346644587620272790089165813353259223649897308397918491861562279767580488441831451651834802520437234248670652477414296159324726172158330221397420877323921934377321483041598028053870169281419856238830264612049920637819183013812186448416408328958360799645342598727238977986741643705720539702955864527935398839069236768630867447760912744208154645904678859979378604386855741350220991958191408182147658532111413386776058224418484895056146180001830405844881486308594953615999140110712045286000170660686758188247928230655746746482354748673482506070246808187808961599576834080344066055446605664648340486804023919467
e: 10788856448030235429585145974385410619185237539198378911887172763282204686697141640582780419040340318300048024100764883750608733331571719088729202796193207904701854848679412033514037149161609202467086017862616635522167577463675349103892366486246290794304652162107619408011548841664240624935414339021041162505899467159623692906986841033101688573177710503499081107294555688550493634416552587963816327790111808356639558596438537569271043190414208204773219496030644456745185896540608008662177117212000718802474957268532153146989410300300554162811564064457762004188326986236869603714437275058878379647196886872404148116134
flag: 3954523654845598592730156937269688140867480061118457307435945875579028695730063528424973907208923014508950419982702682082417623843946231057553311028711409093751376287876799688357176816093484535703797332422565021382453879908968161161537921292725907853309522100738603080298951279637316809695591295752657105226749125868510570125512146397480808774515489938198191435285342823923715673372695893409325086032930406554421670815433958591841773705563688270739343539481283865883427560667086249616210745997056621098406247201301461721906304555526293017773805845093545204570993288514598261070097976786800172141678030841959348372097
First approach
Let be $m$ the plaintext flag and $c$ the encrypted flag (from output.txt).
Reminder: RSA cryptosystem is based on modular exponentation, and compute messages this way: $$c = m ^ e \pmod n$$
The algorithm looks almost like a classic RSA encryption. However, unlike RSA, this algorithm uses multiplication instead of exponentation as a way to compute $c$$: $$c = m \times e \pmod n$$
This implies that the decryption is made like this: $$m = c \times d \pmod n$$
Where \(x^2 + y^2 = z^2\) is the modular multiplicative inverse of $e \pmod n$. This number, also called “secret exponent”, is usually part of the RSA private key $(d,n)$, used for decrypting messages.
Throughout all this write up, we’ll admit that $e$ and $n$ are coprimes, because we can tell from the piece of chal.py below that the chance for them to not being coprime (if the randbelow(n) fonction returns $p$ or $q$) is equal to: $\frac{1}{2^{(2 \times 1024)}} \iff \frac{1}{2^{1024}}$, which is honestly quite low.
# We get 2 1024-bit primes
p = getStrongPrime(1024)
q = getStrongPrime(1024)
# We calculate the modulus
n = p*q
# We generate our encryption key
import secrets
e = secrets.randbelow(n)
So, what’s the matter ?
To decrypt $c$, we have to retrieve $d$. But as we’ll see, due to the fact that the algorithm uses multiplication instead of exponentation, $d$ is actually easy to compute.
First method
Let’s define two functions: $$encrypt(m) \rightarrow m \times e \pmod n$$ $$decrypt(c) \rightarrow c \times d \pmod n$$
Therefore: $$m \pmod n = decrypt(encrypt(m))$$ $$\iff m \pmod n = (m \times e \pmod n) \times d \pmod n$$ $$\iff m \pmod n = m \times e \times d \pmod n$$
To satisfy this equation, we must have $e \times d \equiv 1 \pmod n$.
Which is the same as: $$d \equiv e^-1 \pmod n$$
We got $d$.
Second method (Bézout’s identity and extended Euclidean algorithm)
Admiting $e$ and $n$ are coprimes, we have: $gcd(e,n) = 1$. Yet, we know from the BĂ©zout’s identity that the following diophantine equation admits a solution couple $(u,v) \in \mathbb Z$$: $$e \times u + n \times v = gcd(e,n) \iff e \times u + n \times v = 1$$
From there, and because $gcd(e,n) = 1$, the extended Euclidean algorithm tells us that in this equation, $u$ is the inverse of $e \pmod n$; and we know for a fact that the inverse is defined by this expression: $$u \equiv e^-1 \pmod n$$
This is exactly what we were searching for. Replacing $u$ by $d$, we get our solution: $$d \equiv e^-1 \pmod n$$
Solution
We compute $d$ this way: $$d \equiv e^-1 \pmod n$$
Once we’ve got $d$, we decrypt our ciphertext (and thus, retrieve $m$): $$m \equiv c \times d \pmod n$$
from Crypto.Util.number import *
n = 21429933885346644587620272790089165813353259223649897308397918491861562279767580488441831451651834802520437234248670652477414296159324726172158330221397420877323921934377321483041598028053870169281419856238830264612049920637819183013812186448416408328958360799645342598727238977986741643705720539702955864527935398839069236768630867447760912744208154645904678859979378604386855741350220991958191408182147658532111413386776058224418484895056146180001830405844881486308594953615999140110712045286000170660686758188247928230655746746482354748673482506070246808187808961599576834080344066055446605664648340486804023919467
e = 10788856448030235429585145974385410619185237539198378911887172763282204686697141640582780419040340318300048024100764883750608733331571719088729202796193207904701854848679412033514037149161609202467086017862616635522167577463675349103892366486246290794304652162107619408011548841664240624935414339021041162505899467159623692906986841033101688573177710503499081107294555688550493634416552587963816327790111808356639558596438537569271043190414208204773219496030644456745185896540608008662177117212000718802474957268532153146989410300300554162811564064457762004188326986236869603714437275058878379647196886872404148116134
flag = 3954523654845598592730156937269688140867480061118457307435945875579028695730063528424973907208923014508950419982702682082417623843946231057553311028711409093751376287876799688357176816093484535703797332422565021382453879908968161161537921292725907853309522100738603080298951279637316809695591295752657105226749125868510570125512146397480808774515489938198191435285342823923715673372695893409325086032930406554421670815433958591841773705563688270739343539481283865883427560667086249616210745997056621098406247201301461721906304555526293017773805845093545204570993288514598261070097976786800172141678030841959348372097
d = pow(e, -1, n)
decrypted_flag = flag * d % n
print(long_to_bytes(decrypted_flag).decode())
irisctf{discrete_divide_isn't_hard}
Bonus : small example on the extended Euclidean algorithm
The extended Euclidean algorithm allows us to not only to find the gcd of two number, but also to find BĂ©zout coefficients $(u,v) \in \mathbb Z$ for diophantines equations such as this one : $$e \times u + n \times v = gcd(e,n)$$
The book Introduction to Algorithms (written in part by one of the inventors of RSA; for the fun fact) gives a pseudocode recursive version of the algorithm. Here is a Python code snippet I wrote from it to fit our example :
def egcd(e, n):
if n == 0:
return e, 1, 0
gcd, u, v = egcd(n, e % n)
return gcd, v, u - (e//n)*v
e, n = 7, 33
result = egcd(e, n)
print(f"gcd({e},{n}) = {result[0]}; u = {result[2]}; v = {result[1]}")
With $e = 7$ and $n = 33$, we get this output: $gcd(7,33) = 1; u = -14; v = 3$. And we notice that: $e \times u + n \times v = gcd(e,n)$ works : $$7 \times -14 + 33 \times 3 = 1$$
But also, we notice that the definition of $u$ being the inverse of $e \pmod n$ (only if $gcd(e,n)=1$) works: $$e \times u \equiv 1 \pmod n$$ $$7 \times -14 \equiv 1 \pmod {33}$$
I won’t explain much about this algorithm because it would weigh down the article (and I couldn’t see myself explaining it in details in this write up to be honest).
I hope you learnt something (that modifiying just a tiny part of a cryptosystem can be crucial, for example) reading this wu/article. Give me feedback on Discord (REDACTED) or my other social medias if you liked it; I would really appreciate it.