RSA / Smooth

!README.md

LetoCTF 2019 | Smooth (crypto)

Задание с AntiCTF, который проводился в Летней школе CTF летом 2019 года.

Dockerfile

FROM ubuntu:latest

RUN apt update && apt install -y socat python3-minimal

RUN useradd -m -s /bin/false -u 1001 task && \
    mkdir /home/task/smooth/

COPY task.py secret.py message.txt /home/task/smooth/

WORKDIR /home/task/smooth/

ENTRYPOINT socat TCP-LISTEN:37316,reuseaddr,fork SYSTEM:"timeout 30 python3 -u task.py",su=1001

genprime.py

#!/usr/bin/python3

from gmpy2 import is_prime, next_prime
from random import getrandbits


def gen_prime(bits, size):
    while True:
        number = 2
        while number.bit_length() < size:
            prime = next_prime(getrandbits(bits))
            number *= prime
        number += 1
        if number.bit_length() == size and is_prime(number):
            return number


def main():
    bits, size = 16, 1024
    prime = gen_prime(bits, size)
    print(prime)


if __name__ == '__main__':
    main()

message.txt

BERNARDO
Who's there?
FRANCISCO
Nay, answer me: stand, and unfold yourself.
BERNARDO
Long live the king!
FRANCISCO
Bernardo?
BERNARDO
Here is your flag: CTF{Omae_Wa_Mou_Shindeiru}

secret.py

#!/usr/bin/python3

p = 165547060714386928557896871080117090254719588829761105413669889306149725930126567912360117810707358631940615838362069714233314793654095415648854110814649446301814875947540461675198156170524888267463804066901844941736860781876191722638365614725117150788144336530640618490815080853792034181004687506800385803739
q = 133308926564612428507296370756973243718481100854492445913338586578912767955697542989834887722387399880278021743169441038487052645571289176253147982459434775445634574256478396889467906540364272628907472589685304970109023537058449869609189491972523392367411603675784227946605414515532209895159986856853605707247

solver.sage

import re
import socket


def pollard(n):
    a = 2
    b = 2
    while True:
        a = pow(a, b, n)
        d = gcd(a - 1, n)
        if d > 1: 
            return int(d)
        b += 1


def recvline(sock):
    data = ''
    while '\n' not in data:
        data += sock.recv(1)
    return data


def encrypt(sock, val):
    sock.send('E\n')
    sock.send(str(val) + '\n')
    res = re.search(r'\d+', recvline(sock)).group(0)
    return int(res)


def main():
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.settimeout(3)
    sock.connect(('0.0.0.0', 37316))
    N = encrypt(sock, -1) + 1    
    print('N = %d' % N)
    g = 2
    c = encrypt(sock, g)
    print('c = %d' % c)
    sock.close()
    p = pollard(N)
    q = N // p
    print('p = %d' % p)
    print('q = %d' % q)
    e_p = GF(p)(c).log(g)
    e_q = GF(q)(c).log(g)
    e = crt([e_p, e_q], [p-1, q-1])
    print(e.hex()[2:].decode('hex'))


if __name__ == '__main__':
    main()

task.py

#!/usr/bin/python3

from secret import p, q


def egcd(b, n):
    (x0, x1, y0, y1) = (1, 0, 0, 1)
    while n != 0:
        (q, b, n) = (b // n, n, b % n)
        (x0, x1) = (x1, x0 - q * x1)
        (y0, y1) = (y1, y0 - q * y1)
    return (b, x0, y0)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise ValueError
    return x % m


class RSA(object):
    def __init__(self, p, q, e):
        self.n = p * q
        self.e = e
        self.d = modinv(e, (p - 1) * (q - 1))

    def encrypt(self, pt):
        return pow(pt, self.e, self.n)

    def decrypt(self, ct):
        return pow(ct, self.d, self.n)


def ui(rsa):
    while True:
        choice = input('[E]ncrypt / [D]ecrypt?: ').lower()[0]
        if choice == 'e':
            pt = int(input('Input plaintext: '))
            ct = rsa.encrypt(pt)
            print('Ciphertext: %d' % ct)
        elif choice == 'd':
            ct = int(input('Input ciphertext: '))
            pt = rsa.decrypt(ct)
            print('Plaintext: %d' % pt)
        else:
            print('Try again!')


def main():
    with open('message.txt', 'rb') as file:
        message = file.read()
    e = int.from_bytes(message, 'big')
    rsa = RSA(p, q, e)
    try:
        ui(rsa)
    except Exception as e:
        print('Error: %s' % e)


if __name__ == '__main__':
    main()