TJCTF | Crypto
This was a rather fun CTF event which I played with the team CyberHero. While I didn’t get a chance to try my hands at all the categories, the cryptography challenges were all rather enjoyable. As the challenges were beginner-friendly, I’ve made the write-up be as beginner-friendly as I could. I’ve taken the time to outline my solution and thought process for two of the challenges, those being:
crypto/e
Author: stosp
64 solves / 60 points
smol e
Note: Below you’ll find a guided solution. If interested just in the solve script, click here
When we first open up our challenge, we are greeted with two files: gen.sage
and output.txt
. It’s the former that interests us a lot more, so let’s take a look:
from Crypto.Util.number import bytes_to_long
p = random_prime(2 ^ 650)
q = random_prime(2 ^ 650)
N = p*q
e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)
c = m ^ e % N
print("N: ", N)
print("C: ", c)
print("e: ", e)
Obviously, we’re dealing with RSA here. The primes seem safely generated and the encryption’s standard - we can find our public key and the ciphertext in output.txt
. So our eyes turn to the central section:
e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)
Immediately we notice that
Next, we notice that our message (i.e. plaintext) is a combination of a known string and the (unknown) flag. More precisely, it means we have a partially known plaintext.
Enter Coppersmith
Let’s take a short detour.
In the mid-to-late 90s, a very clever man named Don Coppersmith, building on the ideas of other clever people, came up with a method for solving univariate modular equations. That is, equations with one variable modulo some
Though that begs the question: what’s small? For a polynomial of degree
Now, what does this have to do with us? Well, let’s look at our message:
b'the challenges flag is ' + flag
Obviously, we know the higher bits of the plaintext (
Which tells us that the ciphertext is:
And since we know that
And what we get, after expanding it, is a:
- univariate polynomial (it has only one unknown,
), - that is modulo
, - with a small degree
, - and a relatively small root.
So we can apply Coppersmith! Luckily for us, SageMath already has Coppersmith’s method implemented for us in the form of the small_roots
function.
Solve script (crypto/e)
To make our lives easier, we recall that the flag format for the CTF is tjctf{
so we append that to our known string. Additionally, as standard calls to small_roots()
don’t result in any outputs, we increase the epsilon value (which defaults to 1/8). We can roughly understand it as increasing the bounds of the algorithm. The lower the epsilon, the larger the bounds.
from sage.all import *
N = 8530080367614029604 ...
C = 2987003325076547237 ...
e = 5
Z = Zmod(N)
P.<x> = PolynomialRing(Z)
msg = b'the challenges flag is tjctf{'
known = Z(int(msg.hex(), 16)) # Bytes to decimal
for unknown_bytes in range(2,33): # x < N^(1/5) ~= 32 bytes
m = known * 2^(8*unknown_bytes)
f = (m + x)^e - C
roots = f.small_roots(epsilon=1/12)
if roots != []:
print(roots) #
break
When converting the number to bytes, we get coppersword2}
, resulting in the full message being the challenges flag is tjctf{coppersword2}
.
crypto/keysmith
Author: stosp
30 solves / 128 points
I lost my key… can you find it?
nc tjc.tf 31103
Note: Below you’ll find a guided solution. If interested in just the solve script, click here
Downloading the challenge, we stumble upon server.py
- let’s see what we’ve got:
#!/usr/local/bin/python3.10 -u
from Crypto.Util.number import getPrime
flag = open("flag.txt", "r").read()
po = getPrime(512)
qo = getPrime(512)
no = po * qo
eo = 65537
msg = 762408622718930247757588326597223097891551978575999925580833
s = pow(msg,eo,no)
print(msg,"\n",s)
try:
p = int(input("P:"))
q = int(input("Q:"))
e = int(input("E:"))
except:
print("Sorry! That's incorrect!")
exit(0)
n = p * q
d = pow(e, -1, (p-1)*(q-1))
enc = pow(msg, e, n)
dec = pow(s, d, n)
if enc == s and dec == msg:
print(flag)
else:
print("Not my keys :(")
Interesting. So we’re given
So our
Right, that’s a few expressions. Let’s put some words behind them.
Effectively, we’re looking to input parameters
Obviously, one way to get the flag would be to send the private parameters back. However, seeing as the target
The DLP is the ‘hard’ problem behind cryptosystems such as Diffie-Hellman. It’s proven to be rather difficult in the general case, however there are some special cases when it’s far easier. Notably, for a prime
The algorithm in question, called Pohlig–Hellman, is luckily implemented in SageMath through the discrete_logarithm
function. All that’s left now is to code-up the rest.
Generating smooth numbers
While for solving our special case of the DLP we have an efficient algorithm, how would we go about generating these ‘smooth’ numbers? The method we’ll employ is surprisingly simple: multiply a lot of small numbers, check if the incremented version of the number is prime and, if so, return that number. Here’s one way to achieve just that in SageMath:
from sage.all import *
def smooth_prime(r=80):
not_found = True
while not_found:
k = 2
for _ in range(r):
k *= random_prime(1000, 10000) * random_prime(10000, 1000000)
k += 1
if is_prime(k) and len(factor(k-1)) > 20:
not_found = False
return k
Here our function’s parameter r
corresponds to a rough estimate of how many prime multiplications we’d like. While not ideal, it gets the job done - a better method would be to go about multiplying random numbers until a certain bit-length is reached. But we don’t have to worry about a key-size here, as long as our public key $n$ is larger than
Solve script (crypto/keysmith)
To simplify things, we only bother with ensuring
from sage.all import *
def smooth_prime(r=80):
not_found = True
while not_found:
k = 2
for _ in range(r):
k *= random_prime(1000, 10000) * random_prime(10000, 1000000)
k += 1
if is_prime(k) and len(factor(k-1)) > 20:
not_found = False
return k
# === SETUP
from pwn import *
server = "tjc.tf"
port = 31103
io = remote(server, port)
# === INIT
msg = int(io.recvline())
s = int(io.recvline())
eo = 65537
# === PAYLOAD
successful = False
while not successful:
p = int(smooth_prime(55))
q = 3
n = p*q
print("Attempting...")
Z = Zmod(n)
try:
e = discrete_log(Z(s), Z(msg))
e = int(e)
e = e % ((p-1)*(q-1))
d = pow(e, -1, (p-1)*(q-1))
except ValueError:
continue
except ZeroDivisionError:
continue
successful = True
# === CHECKS
enc = pow(msg, e, n)
dec = pow(s, d, n)
assert enc == s
assert dec == msg
# === ATTACK
p_ = str(p).encode()
print(p_)
io.sendline(p_)
q_ = str(q).encode()
print(q_)
io.sendline(q_)
e_ = str(e).encode()
print(e_)
io.sendline(e_)
io.interactive() # tjctf{lock-smith_289378972359}