🏷️ write-up cryptography

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} (\mod 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 (\mod n)$ $

This implies that the decryption is made like this: $m = c \times d (\mod n)$

Where $x^{2} + y^{2} = z^{2}$ is the modular multiplicative inverse of $e (\mod 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)}} ⟺ \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: $e n c r y p t (m) \to m \times e (\mod n)$ $d e c r y p t (c) \to c \times d (\mod n)$

Therefore: $m (\mod n) = d e c r y p t (e n c r y p t (m))$ $⟺ m (\mod n) = (m \times e (\mod n)) \times d (\mod n)$ $⟺ m (\mod n) = m \times e \times d (\mod n)$

To satisfy this equation, we must have $e \times d \equiv 1 (\mod n)$ .

Which is the same as: $d \equiv e^{-} 1 (\mod n)$

We got $d$ .

Second method (Bézout’s identity and extended Euclidean algorithm)

Admiting $e$ and $n$ are coprimes, we have: $g c d (e, n) = 1$ . Yet, we know from the Bézout’s identity that the following diophantine equation admits a solution couple $(u, v) \in Z$ $:$ $e \times u + n \times v = g c d (e, n) ⟺ e \times u + n \times v = 1$ $

From there, and because $g c d (e, n) = 1$ , the extended Euclidean algorithm tells us that in this equation, $u$ is the inverse of $e (\mod n)$ ; and we know for a fact that the inverse is defined by this expression: $u \equiv e^{-} 1 (\mod n)$

This is exactly what we were searching for. Replacing $u$ by $d$ , we get our solution: $d \equiv e^{-} 1 (\mod n)$

Solution

We compute $d$ this way: $d \equiv e^{-} 1 (\mod n)$

Once we’ve got $d$ , we decrypt our ciphertext (and thus, retrieve $m$ ): $m \equiv c \times d (\mod 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 Z$ for diophantines equations such as this one : $e \times u + n \times v = g c d (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: $g c d (7, 33) = 1; u = - 14; v = 3$ . And we notice that: $e \times u + n \times v = g c d (e, n)$ works : $7 \times - 14 + 33 \times 3 = 1$

But also, we notice that the definition of $u$ being the inverse of $e (\mod n)$ (only if $g c d (e, n) = 1$ ) works: $e \times u \equiv 1 (\mod n)$ $7 \times - 14 \equiv 1 (\mod 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.

Thanks again to aaSSfxxx and the IrisSec team :)