BaaaaaaaarkingDog
코딩, 해킹
[2019 X-MAS CTF] Santa Knows Crypto

rElGamal.py

from Crypto.Util.number import *
from PRNG import PRNG

class ElGamal(object):
    def __init__(self, length, prime = None):
        self.prng = PRNG(256)
        self.length = length
        self.g = 2
        self.q = prime
        while self.q == None:
                p = self.next_prime(2**(length) + self.prng.get_bits(length))
                if ((2 * p + 1) % 8 == 3 or (2 * p + 1) % 8 == 5) and isPrime(2 * p + 1):
                    self.q = 2 * p + 1

        self.x = self.prng.get_bits(self.length)
        self.h = pow(self.g, self.x, self.q)

    def next_prime(self, x):
        if x & 1 == 0:
            x += 1
        while not isPrime(x):
            x += 2
        return x

    def encrypt(self, message):
        y = self.prng.get_bits(self.length)
        s = pow(self.h, y, self.q)
        c1 = pow(self.g, y, self.q)
        c2 = message * s % self.q
        return y, c1, c2

 

PRNG.py

import os

class PRNG(object):
    def __init__(self, length):
        self.length = length
        self.state = self.getseed()
        self.key = self.getseed()

    def parity(self,x):
        aux = self.length
        while aux > 1:
            x ^= x >> ((aux + 1) / 2)
            aux = (aux+1) / 2

        return x & 1  

    def getseed(self):
        return int(os.urandom(self.length / 8).encode('hex'), 16)

    def next_state(self):
        self.state = (self.state >> 1) | (self.parity(self.state & self.key) << (self.length - 1))

    def get_bit(self):
        output = self.state & 1
        self.next_state()
        return output

    def get_bits(self, bits):
        output = 0
        for i in range(bits):
            output = (output << 1) + self.get_bit()
        return output

 

server.py

from Crypto.Util.number import *
import SocketServer
from ElGamal import ElGamal
from secret import flag
from text import *
import os
from hashlib import sha256
prime = 685221181007655969055643176795598500987539499099103356485206001142535588544010199273848305625469714980556215814571531400059127410834556408213573648640620782264547499664798168588595354413552517947288874272302443155003080155578117949303088899418619338227631822471359675459950492254857920916052407700056096582307
PORT = 2000

class ThreadedTCPRequestHandler(SocketServer.BaseRequestHandler):
    def PoW(self):
        s = os.urandom(10)
        h = sha256(s).hexdigest()
        self.request.sendall("Provide a hex string X such that sha256(X)[-6:] = {}\n".format(h[-6:]))
        inp = self.request.recv(2048).strip().lower()
        is_hex = 1
        for c in inp:
            if not c in '0123456789abcdef':
                is_hex = 0

        if is_hex and sha256(inp.decode('hex')).hexdigest()[-6:] == h[-6:]:
            self.request.sendall('Good, you can continue!\n')
            return True
        else:
            self.request.sendall('Oops, your string didn\'t respect the criterion.\n')
            return False

    def handle(self):
        self.request.settimeout(120)
        if not self.PoW():
            return
        self.request.sendall(intro)
        enc = ElGamal(1024, prime)
        print enc.x
        self.request.sendall(details.format(enc.q, enc.g))
        correct = 0
        while correct < 10:
            m = int(os.urandom(32).encode('hex'), 16) % enc.q
            y, c1, c2 = enc.encrypt(m)
            self.request.sendall(challenge.format(c1, c2))
            self.request.sendall(get_input)
            try:
                x = self.request.recv(1024)
                x = int(x)
                if x == m:
                    self.request.sendall(correct_answer)
                    correct += 1
                else:
                    self.request.sendall(wrong_answer.format(m, y))`
                    correct = 0                    
            except:
                self.request.sendall(bad_input)
                break
        if correct == 10:
            self.request.sendall(flag+'\n')

class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass

if __name__ == '__main__':
    server = ThreadedTCPServer(('0.0.0.0', PORT), ThreadedTCPRequestHandler)
    server.allow_reuse_address = True
    server.serve_forever()

 

text.py

intro = 'Welcome!\nIn this challenge you will have to decrypt 10 messages in a row to get the flag!\n'
details = 'Here are some things to help you in your quest!\nq : {}\ng : {}\n'
challenge = 'Decrypt this:\nc1 : {}\nc2 : {}\n'
wrong_answer = "Nope, that's not it!\nhere's what you sohould've sent:\nm : {}\nalso here is your y : {}\n"
correct_answer = 'Hey, you did it, great job!\n'
get_input = 'Send the decrypted message as an integer: '
bad_input = 'Input does not match desired criteria. Aborting!\n'

STEP 1 - Recover h in ElGamal class
After send wrong $m$ to server, server tells both $m$ and $y$.

 

Then We can recover $h^y = m \cdot m^{-1}$.

 

Once we found a pair $y1, y2$ such that $gcd(y1, y2) = 1$, find $v1, v2$ satisfies $v1y1 + v2y2 = 1$ using extended gcd and recover $h = ((h^{y1})^{v1}) \cdot ((h^{y2})^{v2}))$

 

STEP 2 - Recover state, key in PRNG class
This PRNG extracts each bit by XORing specific bit in state.(If key = (1<<128) | (1<<64) | (1<<32), parity is 128-th bit of state $\oplus$ 192-th bit of state $\oplus$ 224-th bit of state)

 

Since key is fixed, with any y, you can easily build a linear equation system which contains 256 equations and 256 variables in GF(2). After solving this, you can get a key.

 

State is more easy. Extract LSB 256-bit of last Y and key(Beware of endian. Must be reversed on LSB 256-bit of last Y). Make another PRNG class adn extract dummy 1024-bit. Then state is synchronized with in server.

 

sage code for extracting key

Y = 89983791425551027210400346476092936344826533636016877225918481462124667356462216675054392621920865356045823186208305570456929667777504930092311160509140608128950177361952489418169806815449239730008355253892404586754110522969077661227581488968435597924500263911858546622164629597080557119791160012652564123666
bb = rev_bit(Y)
sz = 256

print str(Y)[:6], "done"

mat = [[0]*sz for i in range(sz)]
for i in range(sz):
    for j in range(sz):
        mat[i][j] = int(bb[1+i+j])

A = Matrix(IntegerModRing(2),mat)
Ainv = A.inverse()
vec = [0]*sz
for i in range(sz):
    vec[i] = int(bb[i])

b = vector(IntegerModRing(2), vec)
ans = A.solve_right(b)
print(ans)

key = 0
for i in ans:
    z = Integer(i)
    key = (key<<1) | z
print "key ", key

 

solver.py

from hashlib import sha256
from Crypto.Util.number import *
import random, socket



############ my socket ###############
def interactive(socket):
  print("[+] interactive mode")
  while True:
    rr = socket.recv(2**16).decode()
    if not rr:
      print("[!] socket closed")
      return None
    print(rr)
    socket.send((input('> ')+'\n').encode())

def remote(ip, port):
  sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  print("[+] Connecting to {}:{}".format(ip,port))
  sock.connect((ip,port))
  print("[+] Done!")
  return sock

def sendline(socket, msg):
  if type(msg) == str: msg = msg.encode()
  if msg[-1] != b'\n': msg += b'\n'
  socket.send(msg)

def recv(socket):
  return socket.recv(2**16).decode()

class PRNG(object):
  def __init__(self, length, key, state):
    self.length = length
    self.state = state
    self.key = key

  def parity(self,x):
    aux = self.length
    while aux > 1:
      x ^= x >> ((aux + 1) // 2)
      aux = (aux+1) // 2

    return x & 1  

  def next_state(self):
    self.state = (self.state >> 1) | (self.parity(self.state & self.key) << (self.length - 1))

  def get_bit(self):
    output = self.state & 1
    self.next_state()
    return output

  def get_bits(self, bits):
    output = 0
    for i in range(bits):
      output = (output << 1) + self.get_bit()

    return output


def rev_bit(x, sz):
  s = bin(x)[2:].zfill(sz)
  s = s[::-1]
  return int(s, 2)

def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  g, y, x = egcd(b%a,a)
  return (g, x - (b//a) * y, y)



q = 685221181007655969055643176795598500987539499099103356485206001142535588544010199273848305625469714980556215814571531400059127410834556408213573648640620782264547499664798168588595354413552517947288874272302443155003080155578117949303088899418619338227631822471359675459950492254857920916052407700056096582307


r = remote('challs.xmas.htsp.ro', 10000)
pow_target = recv(r).strip()[-6:]
print(pow_target)
sendline(r, input())

x = recv(r) # Good, you can continue

c1arr = []
c2arr = []
marr = []
yarr = []
sarr = []
i1, i2 = -1, -1

# Step 1. to find h
for step in range(100000):
  print("Collection phase ", step)
  x = recv(r) # c1,c2
  if step == 0: print(x)
  c1 = x[x.find("c1")+5:]
  c1 = int(c1.split('\n')[0].strip())
  c2 = x[x.find("c2")+5:]
  c2 = int(c2.split('\n')[0].strip())
  c1arr.append(c1)
  c2arr.append(c2)
  sendline(r, '1')
  x = recv(r)
  m = x[x.find("m : ")+4:]
  m = int(m.split('\n')[0].strip())
  y = x[x.find("y : ")+4:]
  y = int(y.split('\n')[0].strip())
  s = c2 * inverse(m, q) % q
  sarr.append(s)
  marr.append(m)
  yarr.append(y)
  for i in range(step-1):
    if GCD(yarr[i], yarr[step]) == 1:
      i1, i2 = i, step
      break
  if i1 != -1:
    break

g, v1, v2 = egcd(yarr[i1], yarr[i2])
assert(g==1)
assert(v1*yarr[i1]+v2*yarr[i2]==1)

h = 1
if v1 > 0:
  h = h * pow(sarr[i1], v1, q) % q
else:
  h = h * pow(inverse(sarr[i1],q), -v1, q) % q

if v2 > 0:
  h = h * pow(sarr[i2], v2, q) % q
else:
  h = h * pow(inverse(sarr[i2],q), -v2, q) % q

for i in range(step):
  assert(pow(h,yarr[i],q) == sarr[i])
  assert(c2arr[i] == marr[i]*sarr[i]%q)

key = 0
Y = yarr[-1]
print("Y : ", Y)
key = int(input())
prng = None
# Step 2
for step in range(10):
  print("Challenge phase ", step)
  x = recv(r) # c1,c2
  c1 = x[x.find("c1")+5:]
  c1 = int(c1.split('\n')[0].strip())
  c2 = x[x.find("c2")+5:]
  c2 = int(c2.split('\n')[0].strip())
  if step == 0:
    prng = PRNG(256, key, rev_bit(Y&(2**256-1), 256))
    prng.get_bits(256)
  nexty = prng.get_bits(1024)
  s = pow(h, nexty, q)
  m = c2 * inverse(s, q) % q
  print("guessed m : ", m)
  sendline(r, str(m))
  x = recv(r)
  print(x)

print(recv(r))
print(recv(r))
print(recv(r))

'CTF > Crypto' 카테고리의 다른 글

[2019 X-MAS CTF] Santa Knows Crypto  (0) 2019.12.14
[2019 X-MAS CTF] Hashed Presents  (0) 2019.12.14
[2019 X-MAS CTF] DeFUNct Ransomware  (0) 2019.12.14
[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
[TWCTF 2019] M-Poly-Cipher  (0) 2019.09.02
[TWCTF 2019] Simple Logic  (0) 2019.09.02
  Comments
댓글 쓰기
[2019 X-MAS CTF] Hashed Presents

server.py

from hash import secureHash
import SocketServer
import string
import random
from text import *
import os
from hashlib import sha256

PORT = 2000
ROUNDS = 10
TIMEOUT = 120
sigma = string.ascii_letters+string.digits+'!@#$%^&*()-_=+[{]}<>.,?;:'

def isPrintable(x):
    global sigma

    alpha = set(sigma)
    beta = set(x)

    return alpha.intersection(beta) == beta    

def get_random_string(l, s):
    return ''.join([random.choice(s) for i in range(l)])

class ThreadedTCPRequestHandler(SocketServer.BaseRequestHandler):
    def PoW(self):
        s = os.urandom(10)
        h = sha256(s).hexdigest()
        self.request.sendall("Provide a hex string X such that sha256(X)[-6:] = {}\n".format(h[-6:]))
        inp = self.request.recv(2048).strip().lower()
        is_hex = 1
        for c in inp:
            if not c in '0123456789abcdef':
                is_hex = 0

        if is_hex and sha256(inp.decode('hex')).hexdigest()[-6:] == h[-6:]:
            self.request.sendall('Good, you can continue!\n')
            return True
        else:
            self.request.sendall('Oops, your string didn\'t respect the criterion.\n')
            return False

    def challenge(self, n):
        s = get_random_string(random.randint(30,35), sigma)
        H = secureHash()
        H.update(s)
        h = H.hexdigest()

        self.request.sendall(chall_intro.format(n, s, h))
        inp = self.request.recv(2048).strip()
        H_inp = secureHash()
        H_inp.update(inp)
        h_inp = H_inp.hexdigest()

        if(inp == s or not isPrintable(inp)):
            self.request.sendall(chall_wrong)
            return False    

        if(h_inp != h):
            self.request.sendall(chall_wrong)
            return False    

        self.request.sendall(chall_ok)
        return True

    def handle(self):
        self.request.settimeout(TIMEOUT)
        if not self.PoW():
            return
        self.request.sendall(intro.format(ROUNDS))

        for i in range(ROUNDS):
            if(not self.challenge(i+1)):
                self.request.sendall(losing_outro)
                return    

        self.request.sendall(winning_outro.format(FLAG))

        def finish(self):
            logger.info("%s client disconnected" % self.client_address[0])


class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass

if __name__ == '__main__':
    server = ThreadedTCPServer(('0.0.0.0', PORT), ThreadedTCPRequestHandler)
    server.allow_reuse_address = True
    server.serve_forever()

hash.py

class secureHash(object):
    def __init__(self):
        self.bits = 128
        self.mod = 2**128
        self.mask = 2**128 - 1
        self.step = 23643483844282862943960719738L
        self.hash = 9144491976215488621715609182563L

    def update(self, inp):
        for ch in inp:
            self.hash = ((self.hash + ord(ch)) * self.step) & self.mask

    def hexdigest(self):
        x = self.hash
        out = ''
        for i in range(self.bits/8):
            out=hex(x & 0xff)[2:].replace('L','').zfill(2)+out
            x >>= 8
        return out

 

Provided hash is a rabin-karp hash. To capture a flag, we must find a second preimage. Rabin-karp hash is not that secure, and I have read a post about collision in rabin-karp. (Post) However, the method provides in that post is not that fit on this situation.

 

After more googling, I find a similar problem - TWCTF 2017 Palindrome Pairs. According to Solution, LLL algorithm can be used to find a collision.

 

Although I am not that familiar with LLL algorithm, just copy & paste & modified.

 

collision-poly.sage

p = 23643483844282862943960719738
mod = pow(2,128)

N = 22 ## 22 to 34, to increase a success probability
print N

def sparse_poly():
    L_rows = []
    B = 100000

    for i in xrange(N):
        row = [1 if j==i else 0 for j in xrange(N)] + [B*Integer(pow(p,N+1-i,mod))]
        L_rows.append(row)

    L_matrix = Matrix(L_rows)
    print 'Built matrix'
    print type(L_matrix)
    L_redux = L_matrix.LLL()
    sparse = L_redux[0]
    print sparse[:-1]
    poly, vals = sparse[:N], sparse[N:]

    assert all(abs(x) <=70 for x in poly)
    assert all(x == 0 for x in vals)

    return poly

def build_strings(poly):
    a = [0 for _ in xrange(N)]
    b = [0 for _ in xrange(N)]

    # a[i] - b[(N-1)-i] = poly[i]

    for i in xrange(N):
        if poly[i] >= 0:
            a[i] = poly[i]
            b[i] = 0
        else:
            a[i] = 0
            b[i] = -poly[i]

    a_str = ''.join(chr(ord('a')+v) for v in a)
    b_str = ''.join(chr(ord('a')+v) for v in b)
    return a_str, b_str

def solve():
    poly = sparse_poly()
    #s1, s2 = build_strings(poly)
    #print s1, s2

solve()

(Modified form Here)

 

Let me explain more: polynomial is (6, -18, -3, -2, -31, -1, 4, -10, -31, 11, -33, 3, 16, 37, -29, 11, 13, -18, -1, 26, -31, 6) when N = 22.

 

It means if $a[0]-b[0] = 6$, $a[1]-b[1] = -18$, ... , $a[21]-b[21] = 6$ than $a$ and $b$ has same hash.

 

Is is little annoying that there is limit of character. So probability is not 100%. But you can capture a flag at most 5~10 min.

 

solver.py

from hashlib import sha256
from Crypto.Util.number import *
import string

import socket



############ my socket ###############
def interactive(socket):
  print("[+] interactive mode")
  while True:
    rr = socket.recv(2**16).decode()
    if not rr:
      print("[!] socket closed")
      return None
    print(rr)
    socket.send((input('> ')+'\n').encode())

def remote(ip, port):
  sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  print("[+] Connecting to {}:{}".format(ip,port))
  sock.connect((ip,port))
  print("[+] Done!")
  return sock

def sendline(socket, msg):
  if type(msg) == str: msg = msg.encode()
  if msg[-1] != b'\n': msg += b'\n'
  socket.send(msg)

def recv(socket):
  return socket.recv(2**16).decode()





mod = 2**128
p = 23643483844282862943960719738
v = 9144491976215488621715609182563

s = 'abc'
sigma = string.ascii_letters+string.digits+'!@#$%^&*()-_=+[{]}<>.,?;:'
def hash(s):
  h = v
  for ch in s:
    h = (h+ord(ch))*p % mod
  return hex(h)[2:]


s = dict()
def PoW(query):
  i = 0
  while True:
    if i % 1000000 == 0:
      if input() == "quit":
        return None
    i += 1
    h = sha256(str(i).encode()).hexdigest()

    if h[-6:] == query:
      return str(i).encode().hex()

poly22 = (6, -18, -3, -2, -31, -1, 4, -10, -31, 11, -33, 3, 16, 37, -29, 11, 13, -18, -1, 26, -31, 6)
poly23 = (21, 15, 5, -1, 2, -24, 10, -11, -11, -22, -9, -11, -10, -16, -9, -54, -11, -7, 4, 15, 5, 8, 4)
poly24 = (-4, -3, -2, -1, -14, 0, 23, -9, 7, 21, 2, -13, -6, -5, 10, 9, -11, -8, 20, -3, 1, -32, -1, 2)
poly25 = (-3, -9, -7, 16, 3, 0, -6, -17, 0, -8, -8, 24, -3, -8, 23, 3, 5, -10, -7, 15, -9, 0, -11, -1, -10)
poly26 = (-14, -7, 11, 1, 1, 8, -13, 5, -12, 16, 10, 1, 7, -7, -3, -7, 4, -6, -1, -6, -1, 2, -8, 2, -1, -14)
poly27 = (2, -3, -7, 5, 3, 12, -13, 1, -13, -8, 13, 8, -8, -9, 0, 2, 13, 1, -3, -1, -11, -3, 6, 7, -8, 8, -8)
poly28 = (-6, 5, 4, 4, 3, -5, -8, -8, -6, -5, 3, -17, 8, 8, 5, -3, -6, 5, -6, -9, 11, 14, 10, 3, 6, 1, 1, 2)
poly29 = (14, 2, -1, -2, -16, 8, 6, 3, -1, -2, -9, -3, -3, 2, -10, -2, 11, -3, -1, 1, -7, 9, 7, 5, 0, 14, -3, 6, 0)
poly30 = (-7, -8, 5, -5, 3, 4, 6, -2, 0, 3, -15, -1, 14, 5, 3, -8, -3, -1, 6, -6, 1, -8, 0, -5, -5, 12, -7, 2, 3, 2)
poly31 = (-6, -13, -5, 10, 1, -3, 2, 4, -6, 1, -6, 3, -2, -5, 9, 4, -2, -14, -2, 1, 0, -3, 0, -2, 4, -1, 3, 4, -5, -1, -2)
poly32 = (-2, -4, 10, -3, 0, 1, 2, -5, -5, 5, -4, 1, 7, 1, 10, -6, 2, 0, -5, 4, 3, 0, -5, 1, -1, 4, 8, -5, 4, 2, 4, 0)
poly33 = (4, -4, -2, 1, 4, -8, -1, 8, -5, 2, 4, 1, 4, -1, 3, -5, -5, 0, -4, 0, -14, 2, 4, 9, 0, -9, -8, 7, -3, 2, 0, 0, 0)
poly34 = (-7, 1, -3, -5, -4, -5, 3, 3, 4, 3, -1, -9, 2, 4, 2, 3, 1, 2, 1, -3, 2, 3, 2, 0, 5, 0, -1, -1, -2, -9, -1, 2, 3, 2)


def collision(s):
  h = hash(s)
  n = len(s)
  polycount = 21
  for poly in [poly22, poly23, poly24, poly25, poly26, poly27, poly28, poly29, poly30, poly31, poly32, poly33, poly34]:
    polycount+=1
    if len(poly) > n: continue
    for factor in range(1,10):
      for st in range(n-len(poly)+1):
        L = list(s)
        ret = ''
        ret += s[:st]
        pos = True
        for i in range(st,st+len(poly)):
          ii = ord(s[i])+factor*poly[i-st]
          if ii < 0 or chr(ii) not in sigma:
            pos = False
            break
          ret += chr(ii)        
        if not pos: continue        
        ret += s[st+len(poly):]
        if hash(ret) == h:
          return ret
  return "FAIL"




s = dict()
for i in range(10000000):
  if i%1000000==0: print(i)
  h = sha256(str(i).encode()).hexdigest()
  s[h[-6:]] = str(i).encode().hex()



while True:
  r = remote('challs.xmas.htsp.ro', 10003)
  pow_target = recv(r).strip()[-6:]
  print(pow_target)
  if not pow_target in s: continue
  sendline(r, s[pow_target])
  x = recv(r) # Good, you can continue
  pos = True
  for step in range(10):
    if step != 0:
      recv(r) # Nice one, keep going!
    print ("step ", step)
    x = recv(r).strip()
    print("received : ",x)
    string = x[x.find("string")+8:]
    string = string[:string.find("and")-1]
    print(string)
    ans = collision(string)
    if ans == "FAIL":
      pos = False
      break
    sendline(r, ans)
  if pos:
    print(recv(r))
    print(recv(r))
    print(recv(r))
    exit(0)

 

'CTF > Crypto' 카테고리의 다른 글

[2019 X-MAS CTF] Santa Knows Crypto  (0) 2019.12.14
[2019 X-MAS CTF] Hashed Presents  (0) 2019.12.14
[2019 X-MAS CTF] DeFUNct Ransomware  (0) 2019.12.14
[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
[TWCTF 2019] M-Poly-Cipher  (0) 2019.09.02
[TWCTF 2019] Simple Logic  (0) 2019.09.02
  Comments
댓글 쓰기
[2019 X-MAS CTF] DeFUNct Ransomware

keys.txt

n: 795569463642685540507503580717531982215679866156448758181874864294322245115046429295501396806569726084791213843313411985306755767933614251017259685360119715465741448841742926933764058184678978561438979554324014291467144646477238464467422645352253054043072408503415623126059018449111807300294890437634529289983603557882115343971407081044050231310858245171002149317227947666679143716043142141154344524386085333349328691743473103727587822968025700198172293605188589348169121979328380110985341428872278372426313622759225108517531628814853640680656657769539723198346005032762702856464738405070059566116940640592020837592563966093405895649052241416909627641069000138027201809936286028443581259045590752809132011594533609186039058798304319124598876514669458750171121861029071117458575853963148168447032328126766812085206373608016609150982512467597800331177524543178311636877811255184421602626713179220562081413985985692847372669113031244726086691179028200044542399429299315486513734144695492816493025225952668485937918985944213972980220480476191347009337324778384697829597183756976186825413917475597248616769321954150777672675555280228376126308362907381766363071890237458517881243184612898247096962136202978853341989193954815333784856612689  
e: 13337

memos.enc

8f14c50f968c43fe3d40ce2692b95fb4e94c17a5dda5eee162fde77a3d0ceb7012a8b367a134194f2d3975def1adfef62657ad456fa527614218c06debaa9348011f3456fa276080e8630f2cbc806273452f4991fd269b97ca158f0264d16f1c76083f3444c6f866b5dcadebddb0687a63a9836380f750be41d423fb07dd595201af564d592a4bf4c2abac822e7d4380a5f795c022a9b2d22d43c129a159d0c5f1b957df94321e10df7c50af3f1dea36808bfa5f164a6a9a65dddee13133fe19ece35f75a969b0f8cff773c32f97cb99e759a6c5f6560c44f0bf6170b4b56c2663ca0d352cf3bb424ee059d375c78fd1ea623c44aaf307bad822f48b8ff881e27c49219d821edadd9e5de82ce9f2ff2eddf76d006adbf16a25e957b692db7c1fe40a2b2d8836039d499893c20aff7d550680c7d3d6bbe0f79dc51676215f1271d7f04ab756ae990f80e1225637ddf5c090a8c446a3a01e3c96368e2ae6b1509e22a6a8c1cf8e120b0c221eeb8fb088460b9177dc52804149504620ecb1c966d44bb6c29eb3c4a4106c486dc9da1562092dc82786628650aea5726f0742d61a40be1a7eb998450a4936bc0d99e3655735532f61c2589c535a77e10a3ae0bea0d8a01aad62e10765190593b2e09f13a6d5bc73b36a5f822542f37115ece855d087232a6d4198b7d1dbdfedf71516199fd5694a1d24993156263f0cb3fb574e491f

N is easily factorized by online tool.(HERE)

 

$N = p^2q^2$. Then $\phi(N) = pq(p-1)(q-1)$. This is all.

 

solver.py

from Crypto.Util.number import *

p = 167945946509710528501147140850136444757936485900233494350920365296618466491038783888459340376962572176658471433672446105042569166930066764067458760954444542315723029727275896055594485064790247910216515269672809063208736956951590237500845779868099616110730494457247861971337900144361732424961936041908032639503
q = 167945946509710528501147140850136444757936485900233494350920365296618466491038783888459340376962572176658471433672446105042569166930066764067458760954444551181379291048040552484392012079612125237961930510490682072102514499883651342766510399652317335461788686135874608722851478273373669551946245262568601067289

n = 795569463642685540507503580717531982215679866156448758181874864294322245115046429295501396806569726084791213843313411985306755767933614251017259685360119715465741448841742926933764058184678978561438979554324014291467144646477238464467422645352253054043072408503415623126059018449111807300294890437634529289983603557882115343971407081044050231310858245171002149317227947666679143716043142141154344524386085333349328691743473103727587822968025700198172293605188589348169121979328380110985341428872278372426313622759225108517531628814853640680656657769539723198346005032762702856464738405070059566116940640592020837592563966093405895649052241416909627641069000138027201809936286028443581259045590752809132011594533609186039058798304319124598876514669458750171121861029071117458575853963148168447032328126766812085206373608016609150982512467597800331177524543178311636877811255184421602626713179220562081413985985692847372669113031244726086691179028200044542399429299315486513734144695492816493025225952668485937918985944213972980220480476191347009337324778384697829597183756976186825413917475597248616769321954150777672675555280228376126308362907381766363071890237458517881243184612898247096962136202978853341989193954815333784856612689

e = 13337

C = 0x8f14c50f968c43fe3d40ce2692b95fb4e94c17a5dda5eee162fde77a3d0ceb7012a8b367a134194f2d3975def1adfef62657ad456fa527614218c06debaa9348011f3456fa276080e8630f2cbc806273452f4991fd269b97ca158f0264d16f1c76083f3444c6f866b5dcadebddb0687a63a9836380f750be41d423fb07dd595201af564d592a4bf4c2abac822e7d4380a5f795c022a9b2d22d43c129a159d0c5f1b957df94321e10df7c50af3f1dea36808bfa5f164a6a9a65dddee13133fe19ece35f75a969b0f8cff773c32f97cb99e759a6c5f6560c44f0bf6170b4b56c2663ca0d352cf3bb424ee059d375c78fd1ea623c44aaf307bad822f48b8ff881e27c49219d821edadd9e5de82ce9f2ff2eddf76d006adbf16a25e957b692db7c1fe40a2b2d8836039d499893c20aff7d550680c7d3d6bbe0f79dc51676215f1271d7f04ab756ae990f80e1225637ddf5c090a8c446a3a01e3c96368e2ae6b1509e22a6a8c1cf8e120b0c221eeb8fb088460b9177dc52804149504620ecb1c966d44bb6c29eb3c4a4106c486dc9da1562092dc82786628650aea5726f0742d61a40be1a7eb998450a4936bc0d99e3655735532f61c2589c535a77e10a3ae0bea0d8a01aad62e10765190593b2e09f13a6d5bc73b36a5f822542f37115ece855d087232a6d4198b7d1dbdfedf71516199fd5694a1d24993156263f0cb3fb574e491f

d = inverse(e, p*(p-1)*q*(q-1))

print(long_to_bytes(pow(C,d,n)))

'CTF > Crypto' 카테고리의 다른 글

[2019 X-MAS CTF] Santa Knows Crypto  (0) 2019.12.14
[2019 X-MAS CTF] Hashed Presents  (0) 2019.12.14
[2019 X-MAS CTF] DeFUNct Ransomware  (0) 2019.12.14
[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
[TWCTF 2019] M-Poly-Cipher  (0) 2019.09.02
[TWCTF 2019] Simple Logic  (0) 2019.09.02
  Comments
댓글 쓰기