Write Up - IrisCTF 2023: babynotrsa | Why you should beware tweaking RSA
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 {% mathjax %}m{% endmathjax %} the plaintext flag and {% mathjax %}c{% endmathjax %} the encrypted flag (from output.txt).
Reminder: RSA cryptosystem is based on modular exponentation, and compute messages this way: {% mathjax %}c = m ^ e \pmod n{% endmathjax %}
The algorithm looks almost like a classic RSA encryption. However, unlike RSA, this algorithm uses multiplication instead of exponentation as a way to compute {% mathjax %}c{% endmathjax %}: {% mathjax %}c = m \times e \pmod n{% endmathjax %}
This implies that the decryption is made like this: {% mathjax %}m = c \times d \pmod n{% endmathjax %}
Where {% mathjax %}d{% endmathjax %} is the modular multiplicative inverse of {% mathjax %}e \pmod n{% endmathjax %}. This number, also called “secret exponent”, is usually part of the RSA private key {% mathjax %}(d,n){% endmathjax %}, used for decrypting messages.
Throughout all this write up, we’ll admit that {% mathjax %}e{% endmathjax %} and {% mathjax %}n{% endmathjax %} 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 {% mathjax %}p{% endmathjax %} or {% mathjax %}q{% endmathjax %}) is equal to: {% mathjax %}\frac{1}{2^{(2 \times 1024)}} \iff \frac{1}{2^{1024}}{% endmathjax %}, 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 {% mathjax %}c{% endmathjax %}, we have to retrieve {% mathjax %}d{% endmathjax %}. But as we’ll see, due to the fact that the algorithm uses multiplication instead of exponentation, {% mathjax %}d{% endmathjax %} is actually easy to compute.
First method
Let’s define two functions: {% mathjax %}encrypt(m) \rightarrow m \times e \pmod n{%endmathjax %} {% mathjax %}decrypt(c) \rightarrow c \times d \pmod n{%endmathjax %}
Therefore: {% mathjax %}m \pmod n = decrypt(encrypt(m)){%endmathjax %} {% mathjax %}\iff m \pmod n = (m \times e \pmod n) \times d \pmod n{%endmathjax %} {% mathjax %}\iff m \pmod n = m \times e \times d \pmod n{%endmathjax %}
To satisfy this equation, we must have {% mathjax %}e \times d \equiv 1 \pmod n{%endmathjax %}.
Which is the same as: {% mathjax %}d \equiv e^-1 \pmod n{% endmathjax %}
We got {% mathjax %}d{%endmathjax %}.
Second method (Bézout’s identity and extended Euclidean algorithm)
Admiting {% mathjax %}e{% endmathjax %} and {% mathjax %}n{% endmathjax %} are coprimes, we have: {% mathjax %}gcd(e,n) = 1{% endmathjax %}. Yet, we know from the Bézout’s identity that the following diophantine equation admits a solution couple {% mathjax %}(u,v) \in \mathbb Z{% endmathjax %}: {% mathjax %}e \times u + n \times v = gcd(e,n) \iff e \times u + n \times v = 1{% endmathjax %}
From there, and because {% mathjax %}gcd(e,n) = 1{% endmathjax %}, the extended Euclidean algorithm tells us that in this equation, {% mathjax %}u{% endmathjax %} is the inverse of {% mathjax %}e \pmod n{% endmathjax %}; and we know for a fact* that the inverse is defined by this expression:
{% mathjax %}u \equiv e^-1 \pmod n{% endmathjax %}
This is exactly what we were searching for. Replacing {% mathjax %}u{% endmathjax %} by {% mathjax %}d{% endmathjax %}, we get our solution: {% mathjax %}d \equiv e^-1 \pmod n{% endmathjax %}
*check out the end of the write up for an example
Solution
We compute {% mathjax %}d{% endmathjax %} this way: {% mathjax %}d \equiv e^-1 \pmod n{% endmathjax %}
Once we’ve got {% mathjax %}d{% endmathjax %}, we decrypt our ciphertext (and thus, retrieve {% mathjax %}m{% endmathjax %}): {% mathjax %}m \equiv c \times d \pmod n{% endmathjax %}
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 {% mathjax %}(u,v) \in \mathbb Z{% endmathjax %} for diophantines equations such as this one : {% mathjax %}e \times u + n \times v = gcd(e,n){% endmathjax %}
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 {% mathjax %}e = 7{% endmathjax %} and {% mathjax %}n = 33{% endmathjax %}, we get this output: {% mathjax %}gcd(7,33) = 1; u = -14; v = 3{% endmathjax %}. And we notice that: {% mathjax %}e \times u + n \times v = gcd(e,n){% endmathjax %} works : {% mathjax %}7 \times -14 + 33 \times 3 = 1{% endmathjax %}
But also, we notice that the definition of {% mathjax %}u{% endmathjax %} being the inverse of {% mathjax %}e \pmod n{% endmathjax %} (only if {% mathjax %}gcd(e,n)=1{% endmathjax %}) works: {% mathjax %}e \times u \equiv 1 \pmod n{% endmathjax %} {% mathjax %}7 \times -14 \equiv 1 \pmod {33}{% endmathjax %}
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 (██████████████) or my other social medias if you liked it; I would really appreciate it.