Whitehat RSA Signing

2013 화이트햇 콘테스트 예선문제 中 RSA Signing ...

RSA 알고리즘은 아래와 같다.

Choose p = 3 and q = 11

Compute n = p * q = 3 * 11 = 33

Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20

Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7

Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]

Public key is (e, n) => (7, 33)

Private key is (d, n) => (3, 33)

The encryption of m = 2 is c = 27 % 33 = 29

The decryption of c = 29 is m = 293 % 33 = 2

결론은 RSA 가 Homogeneous 임을 이용하여 임의의 Signing 결과를 만들어내는

뭔가 매우 배울점있는 그런거였는데 기억이 잘 안난다... 나중에 다시 풀어봐야겠다.

from Config import Config

from AesUtils import AesUtils

from RsaUtils import RsaUtils

from Crypto.PublicKey import RSA

import md5

IDX_LEN = 4

DATA_LEN = 128

def s2i(s):

  res = 0

  for i in range(len(s)):

    res = (res << 8) | ord(s[i])

  

  return res

def i2s(s):

  res = ""

  while s > 0:

    res = chr(s & 0xFF) + res

    s >>= 8

  return res

class ClientHandler(object):

  def __init__(self, config_path):

    self.forbidden_strings = ['FLAG']

    self.config = Config(config_path)

    pass

  def sign(self, rsa_key, data):

    n = getattr(rsa_key,'n')

    

    data = i2s(s2i(data) % n)

    is_contain_forbidden_str = False

    for forbidden_string in self.forbidden_strings:

      if data.find(forbidden_string) != -1:

        is_contain_forbidden_str = True

    if is_contain_forbidden_str:

      return None

    

    return rsa_key.decrypt(data)

  def handle(self, socket, address):

    socket.send("""Welcome to the A.I. Automatic RSA Signing System\n""")

    rsa_key = RSA.generate(1024)

    n = getattr(rsa_key,'n')

    socket.send('modulo = ' + hex(n)[:-1])

    while True:

      cmd = socket.recv(DATA_LEN)

    

      if len(cmd) == 0:

        break

      socket.send('[ INFO] Processing commands')

      if   cmd[:4] == "SIGN":

        data = socket.recv(DATA_LEN)

        signed_data = self.sign(rsa_key, data)

        if signed_data is None:

          socket.send('[ERROR] Sign failed\n')

          socket.close()

        else:

          socket.send('[ INFO] Sign success\n')

          socket.send(signed_data)

      elif cmd[:4] == "FLAG":

        signed_data = socket.recv(DATA_LEN)

        decoded_data = rsa_key.encrypt(signed_data, "")[0]

        

        if decoded_data == cmd:

          socket.send('[ INFO] FLAG = ' + self.config.flag + '\n')

        else:

          socket.send('[ERROR] Permission denied\n')

      elif cmd[:4] == "PRNT":

        signed_data = socket.recv(DATA_LEN)

        decoded_data = rsa_key.encrypt(signed_data, "")[0]

        

        if decoded_data == cmd:

          socket.send('[ INFO] DATA = ' + i2s(decoded_data) + '\n')

        else:

          socket.send('[ERROR] Permission denied\n')

      else:

        socket.send('[ERROR] No commands')

        socket.close()