Intro to Crypto 1 - localo

Category: Crypto
Difficulty: Hard
Author: black-simon


What did you say?

nc 9400


The author provided a script 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.
mcd (mod N)m \equiv c^d\ (\textrm{mod}\ N) Since we control dd and NN a simple solution is:
mck (mod ckm)m \equiv c^k\ (\textrm{mod}\ c^k - m) And since for every divisor tt of NN
mcd (mod t)m \equiv c^d\ (\textrm{mod}\ t) is a solution, we "just" need to factor ckmc^k - m and if we find two prime-factors with their product is greater than mm we should get the flag. I factored it up to k=6k = 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
  sol = gp("znlog(%d, Mod(%d, %d))" % (M,C,N))
  if len(sol) == 0:
  D = Integer(sol)
    E = inverse_mod(D,(P-1) * (Q-1))

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(("", 9400))