# PicoCTF 2023 - SRA

I just recently learnt about the SRA public key cryptosystem… or wait, was it supposed to be RSA? Hmmm, I should probably check…

400 points - cryptography

This challenge was one of the ones that I found the most satisfying to solve during PicoCTF 2023. I haven’t done many cryptography challenges before, so please excuse any inefficiencies in my solution 😅.

## What is RSA?

RSA is a relatively simple asymmetric encryption/decryption algorithm (the encryption key and decryption key are different).

The wikipedia page for RSA has a great explanation of the maths behind RSA.

Applied to the context of this challenge, here’s what we know:

``````p is a 128-bit prime (would usually be much larger)
q is a 128-bit prime (would also usually be much larger)

n = pq
e = 65537 (would usually be chosen based on some constraints)
φ(n) = (p - 1) * (q - 1)
d ≡ e^(-1) (mod φ(n))

ciphertext ≡ plaintext^e (mod n)
plaintext ≡ ciphertext^d (mod n)
``````

Figure 1: SRA overview

## The code

The challenge essentially implements the algorithm outlined above to encrypt a randomly generated sequence of 16 ascii letters and digits. It then prints out `d` (`anger`) and `ciphertext` (`envy`) and gets us to enter the plaintext. If we get the plaintext correct, we get the flag.

``````from Crypto.Util.number import getPrime, inverse, bytes_to_long
from string import ascii_letters, digits
from random import choice

pride = "".join(choice(ascii_letters + digits) for _ in range(16))
gluttony = getPrime(128) # p
greed = getPrime(128) #    q
lust = gluttony * greed #  n
sloth = 65537 #            e
envy = inverse(sloth, (gluttony - 1) * (greed - 1)) # d

anger = pow(bytes_to_long(pride.encode()), sloth, lust)

print(f"{anger = }")
print(f"{envy = }")

print("vainglory?")
vainglory = input("> ").strip()

if vainglory == pride:
print("Conquered!")
with open("/challenge/flag.txt") as f:
else:
print("Hubris!")
``````

Figure 2: chal.py

The most important question to answer is what we need to decrypt the ciphertext.

## What do we need?

Recall the last equation from Figure 1; We’ve got `ciphertext` and `d`, all we need is `n`. Can’t be too hard, right?

``````plaintext ≡ ciphertext^d (mod n)
``````

Figure 3: RSA decrypt

## Maths time!

``````# Some useful information
n = pq
e = 65537 (would usually be chosen based on some constraints)
φ(n) = (p - 1) * (q - 1)

# Rearrange some modular arithmetic
d ≡ e^(-1) (mod φ(n))
ed ≡ 1 (mod φ(n))
ed - 1 ≡ 0 (mod φ(n))

# The `mod φ(n)` essentially means get the remainder dividing by φ(n)
# Thus, if the remainder is 0, `ed - 1` is a multiple of φ(n)
ed - 1 = φ(n) * k, where k is an integer

ed - 1 = (p - 1) * (q - 1) * k
``````

Figure 4: the maths

With the final rearranged equation in mind, there’s a pretty naïve solution that we can try. It could be too slow, but it’s always best to try it first and optimise later.

## The approach

The basis of this approach is that `p - 1` and `q - 1` will be divisors of `ed - 1`. Therefore, in theory, we can just list all divisors of `ed - 1` and then find all of the divisors are 1 less than a 128-bit prime. We can then take all of those possible values of `p - 1` and `q - 1`, add one to them, and go through all combinations of possible values for `p` and `q`. For each combination we can attempt to decrypt the ciphertext, and if the output is a string of ascii letters and digits, we’ve probably found the correct value. If we get lucky, there weren’t be too many divisors.

``````from Crypto.Util.number import isPrime, long_to_bytes
from string import ascii_letters, digits
from itertools import combinations
from sympy import divisors
from math import log2

anger = int(input("anger = "))
envy = int(input("envy = "))
sloth = 65537

ds = divisors(envy * sloth - 1)
primes = [x + 1 for x in ds if isPrime(x + 1)]
correct_size_primes = [x for x in primes if log2(x) // 1 == 127]

valid_plaintexts = []
charset = ascii_letters + digits
for p, q in combinations(correct_size_primes, 2):
try:
s = long_to_bytes(pow(anger, envy, p * q)).decode("ascii")
if all([c in charset for c in s]):
valid_plaintexts.append(s)
except Exception:
continue

print(valid_plaintexts)
``````

Figure 5: exploit.py

## Does it work?

The short answer; most of the time?

``````anger = 24398438998096796505136585754485122083423993128182088895588693010516281150000
envy = 79858385363514967732413083778555381826816038680345822674623719303400035174513
["HGWW0Lhmhzatb2Ul"]
``````

Figure 6: it works! (in 1 minute and 16 seconds)

In practice, this approach is a bit hit and miss because the line `ds = divisors(envy * sloth - 1)` can take an awfully long amount of time if you get unlucky and `ed - 1` ends up having an incredibly large amount of possible divisors. It works around 30-50% of the time in my experience which is certainly good enough for a CTF challenge solution 😅.

## Possible optimisations (for fun, no profit)

During the CTF I just moved on after solving the challenge, as you do, but afterwards I read a clever ‘writeup’ (answer on StackExchange) in which the hacker instead found the prime factors of `ed - 1` (much faster than finding all possible divisors). They then took the log (base 2) of each factor and used that to figure out which factors multiply together to make 128-bit numbers (if a prime is 128-bit, subtracting 1 still gives you a 128-bit number because 2^127, the smallest 128-bit number, isn’t prime). The rest of the approach is the same, but in theory it should run much faster. I haven’t personally tried out this approach, but if you do I’d be interested to hear how much of an improvement it gives.

## Conclusion

I’ve always wanted to get into cryptography challenges more (as a binary exploitation guy). And in my opinion, this challenge was a great introduction to RSA challenges, and didn’t require a prohibitive amount of maths (although take that with a grain of salt coming from a guy doing a bachelor of maths).