commit 01987404d7c842e0c8e5b9f38607c26b25468c6c
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 25 May 2024 19:08:17 +0200
Add challenge files and solution
Diffstat:
6 files changed, 146 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+__pycache__
diff --git a/chall/description b/chall/description
@@ -0,0 +1 @@
+What did you say?
diff --git a/chall/rsa-service.tar.xz b/chall/rsa-service.tar.xz
Binary files differ.
diff --git a/solve/gen_rsa_values.py b/solve/gen_rsa_values.py
@@ -0,0 +1,45 @@
+from sage.all import *
+import random
+c = 6453808645099481754496697330465
+m = 1067267517149537754067764973523953846272152062302519819783794287703407438588906504446261381994947724460868747474504670998110717117637385810239484973100105019299532993569
+ref = sqrt(m)
+succeed = False
+while not succeed:
+ ps = [3]
+ for i in range(100):
+ ps.append(next_prime(ps[-1]))
+# print ps;exit()
+ out = []
+ for i in range(2):
+ p = 0
+ while not is_prime(p+1):
+ used = set()
+ p = 1
+ while p <= ref:
+ tp = random.choice(ps)
+ used.add(tp)
+ p *= tp ** random.randint(1, 20)
+ p *= 2
+ # print p
+ for u in used:
+ # print u
+ ps.pop(ps.index(u))
+ out.append(p)
+ print(out)
+ pp, qp = out
+ p = pp + 1
+ q = qp + 1
+ try:
+ resp = discrete_log(Mod(c, p), Mod(m, p))
+ resq = discrete_log(Mod(c, q), Mod(m, q))
+ except:
+ continue
+ print('tried')
+ if resp < (p-1)/2 and resq < (q-1)/2:
+ print('good1')
+ e = crt([resp, resq], [(p-1)/2, (q-1)/2])
+ if e < p*q:
+ print('e: ', e)
+ print('p: ',p)
+ print('q: ',q)
+ succeed = True
diff --git a/solve/server.py b/solve/server.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python3.8
+# Note: The server is running a version of pyopenssl patched with this:
+# https://github.com/pyca/pyopenssl/pull/897
+# Attacking the pyopenssl wrapper code is not the intended solution.
+import OpenSSL.crypto as crypto
+
+welcome = '''=============== WELCOME TO THE RSA TEST SERVICE ===============
+You can send me a message and a key to decrypt it!
+If your setup works correctly, you will receive a flag as a reward!
+But wait, it is quite noisy here!
+'''
+question_to_ask = b"Hello! Can you give me the flag, please? I would really appreciate it!"
+
+
+print(welcome)
+print("Please give me your private key in PEM format:")
+key = ""
+while x := input():
+ key += x + "\n"
+
+message = input("Now give me your message: ")
+message = b"Quack! Quack!"
+print("Did you say '" + message.decode() + "'? I can't really understand you, the ducks are too loud!")
+
+
+key = crypto.load_privatekey(crypto.FILETYPE_PEM, key)
+assert key.check()
+numbers = key.to_cryptography_key().private_numbers()
+
+d = numbers.d
+N = numbers.p * numbers.q
+
+if pow(int.from_bytes(message, "big"), d, N) == int.from_bytes(question_to_ask, "big"):
+ print("CSCG{DUMMY_FLAG}")
+else:
+ print("That was not kind enough!")
diff --git a/solve/solve.py b/solve/solve.py
@@ -0,0 +1,63 @@
+#!/usr/bin/env python3
+
+from pwn import process, context
+from Crypto.PublicKey import RSA
+from OpenSSL.crypto import load_privatekey, FILETYPE_PEM
+from sympy.ntheory.modular import crt
+from sympy.ntheory import discrete_log
+from sympy import nextprime, isprime, prod, sieve
+from math import isqrt, gcd
+import random
+
+# We can split the decryption into two discrete logarithm problems:
+# m1^((p-1)*j+dp) = m2 (mod p) and m1^((q-1)*k+dq) = m2 (mod q)
+# If we construct p and q in a way that the factors of phi(n) are small,
+# we can use the Pohlig-Hellman algorithm for finding dp and dq quickly.
+# To construct d from dp and dq we use the Chinese-Remainder-Theorem.
+# CRT requires the moduli to be coprime, so we use sp = p and sq = q/gcd(p-1,q-1)
+# as moduli instead. To expand the resulting solution di to the (p-1)*(q-1)
+# ring again, we need to try all solutions di + i * sp * sq * gcd(p-1,q-1)
+# for i in [0,gcd(p-1,q-1)[.
+
+# P.S: Some players solved this by trial, choosing d and factoring
+# m1**d - m2 using FactorDB, but that solution seems less intended.
+
+m1 = int.from_bytes(b"Quack! Quack!", "big")
+m2 = int.from_bytes(b"Hello! Can you give me the flag, please? I would really appreciate it!", "big")
+
+def build_prime(primes, limit):
+ while True:
+ ps = []
+ while prod(ps) < limit:
+ ps += [random.choice(primes),] * random.randint(1, 10)
+ if isprime(prod(ps) * 2 + 1):
+ return ps, prod(ps), prod(ps) * 2 + 1
+
+def build_params(primes):
+ while True:
+ pp, sp, p = build_prime(list(primes), isqrt(m2)+1)
+ _, sq, q = build_prime(list(primes - set(pp)), isqrt(m2)+1)
+ try:
+ dp = int(discrete_log(p, m2, m1))
+ dq = int(discrete_log(q, m2, m1))
+ except:
+ continue # m2 not in group m1^x mod ..
+ gcdpq = gcd(p, q) # = 2 by construction
+ di = int(crt([sp * gcdpq, sq], [dp % (sp * gcdpq), dq % sq])[0])
+ for i in range(gcdpq):
+ d = di + i * sp * sq * gcdpq
+ if pow(m1, d, p*q) != m2:
+ continue # wrong i
+ if gcd(d, (p-1)*(q-1)) != 1:
+ continue # unlucky
+ e = pow(d, -1, (p-1)*(q-1))
+ return p*q, e, d
+
+params = build_params(set(sieve[1:100]))
+key = RSA.construct(params, consistency_check=False)
+
+io = process(["python", "server.py"])
+io.sendlineafter(b"PEM format:", key.exportKey("PEM") + b"\n")
+io.sendlineafter(b"your message:", b"Quack! :D")
+io.readline().decode()
+print(io.readline().decode())
