**Category:** Crypto

**Difficulty:** Hard

**Author:** black-simon

What did you say?

nc hax1.allesctf.net 9400

The author provided a script `server.py`

we send a private key to decrypt a fixed message: `Quack! Quack!`

if this message decrypts to a sentence chosen by the author we get the flag.

My first approach was to come up with a general solution.

$m \equiv c^d\ (\textrm{mod}\ N)$ Since we control $d$ and $N$ a simple solution is:

$m \equiv c^k\ (\textrm{mod}\ c^k - m)$ And since for every divisor $t$ of $N$

$m \equiv c^d\ (\textrm{mod}\ t)$ is a solution, we "just" need to factor $c^k - m$ and if we find two prime-factors with their product is greater than $m$ we should get the flag. I factored it up to $k = 6$, but had no luck and the process was quite time consuming, therefore I knew it was not the ideal solution. I did some google searches and found this writeup from this years `BSidesSF CTF`

it is basically the same problem, I tried to understand what is going on, and I guess I kind of got it, but to be honest I had already thought about discrete logarithms, but I thought, that it would be even harder to solve it that way, I still don't get why there are those special cases and how they work and `I just copy-pasted the code`

and did some automation.

import numpy from pyasn1.codec.der import encoder from pyasn1.type.univ import SequenceOf from pyasn1.type.univ import Integer as CompInt import base64 import socket def gen_cand(b,l): p = 2 while log(p)/log(2) < b: np = next_prime(numpy.random.randint(2,l)) p = p*np return p+1 def kk(b,l): while True: p = gen_cand(b,l) if is_prime(p): return p M = 1067267517149537754067764973523953846272152062302519819783794287703407438588906504446261381994947724460868747474504670998110717117637385810239484973100105019299532993569 C = 6453808645099481754496697330465 Q = 2 bits = 559 E = 0 while E <3: P = kk(bits,10**6) N = P*Q gp("addprimes(%d)"%(P)) sol = gp("znlog(%d, Mod(%d, %d))" % (M,C,N)) if len(sol) == 0: continue D = Integer(sol) try: E = inverse_mod(D,(P-1) * (Q-1)) except: continue P = P.__int__() Q = Q.__int__() D = D.__int__() N = N.__int__() E = E.__int__() print("P: %d"%P) print("Q: %d"%Q) print("E: %d"%E) print("D: %d"%D) seq = SequenceOf(componentType=CompInt()) enc = encoder.encode([0,N,E,D,P,Q,D % (P-1), D % (Q-1), inverse_mod(Q,P).__int__()],asn1Spec=SequenceOf(componentType=CompInt())) pem = '-----BEGIN RSA PRIVATE KEY-----\n%s\n-----END RSA PRIVATE KEY-----\n' % base64.b64encode(enc) s = socket.socket( socket.AF_INET, socket.SOCK_STREAM) s.connect(("hax1.allesctf.net", 9400)) s.recv(1024) s.send(pem+"\n") s.recv(1024) s.send("\n") print(s.recv(1024)) print(s.recv(1024))

- upgrade your google skills 😉
- don't trust user input

CSCG{下一家烤鴨店在哪裡？}