PACTF Round 2 "Can You See The Future" Solve Script + Files

key1.pem

-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgH+NJdRBPt58////////////////////////////////////////
/////////////////////////////////13ftc78gAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABh5AgMBAAEC
gYAVd1Y9/gsMG6Jj3ZwiY92cImPdnCJj3ZwiY92cImPdnCJj3ZwiY92cImPdnCJj
3ZwiY92cImPdnCJj3ZwiY92AnFLOX3QJi/Z0CYv2dAmL9nQJi/Z0CYv2dAmL9nQJ
i/Z0CYv2dAmL9nQJi/Z0CYv2dAmL9nQJi/Z0CYv2dAmQOQJBAKNR8Tx/////////
////////////////////////////////////////////////////////////////
/////00CQQDH7vZJ////////////////////////////////////////////////
///////////////////////////////dAkAqDtcN2nSli1p0pYtadKWLWnSli1p0
pYtadKWLWnSli1p0pYtadKWLWnSli1p0pYtadKWLWnSli1p0pYtadKVdAkBlRJF1
O/jEBzv4xAc7+MQHO/jEBzv4xAc7+MQHO/jEBzv4xAc7+MQHO/jEBzv4xAc7+MQH
O/jEBzv4xAc7+MP1AkEAmYdklMNfySh3qYx0xxIIU3QdfKC0YKKATv0rz4P8Zt/H
3wGsRJMGIVRBPgp5Qv9obMw5Me4YaYRGlNP1yJzbTA==
-----END RSA PRIVATE KEY-----

key2.pem

-----BEGIN RSA PRIVATE KEY-----
MIICWgIBAAKBgHAOWZ10e145P///////////////////////////////////////
/////////////////////////////////1RUFV1wAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABw7AgMBAAEC
gYAX/xK009V5e5QXi+h0F4vodBeL6HQXi+h0F4vodBeL6HQXi+h0F4vodBeL6HQX
i+h0F4vodBeL6HQXi+h0F4vDaDd086+00EsvtNBLL7TQSy+00EsvtNBLL7TQSy+0
0EsvtNBLL7TQSy+00EsvtNBLL7TQSy+00EsvtNBLL7TWjQJBALAiRBB/////////
////////////////////////////////////////////////////////////////
/////98CQQCi3eQif///////////////////////////////////////////////
//////////////////////////////8lAkBI5lXPknrthRJ67YUSeu2FEnrthRJ6
7YUSeu2FEnrthRJ67YUSeu2FEnrthRJ67YUSeu2FEnrthRJ67YUSeu13AkABKRme
EVFurpFRbq6RUW6ukVFurpFRbq6RUW6ukVFurpFRbq6RUW6ukVFurpFRbq6RUW6u
kVFurpFRbq6RUW6tAkBp8nQOFyBMj8Kon0KlhmLma4XxoXmD+F7iOAcol9AQhDAI
yKpxJ3kDMoVvakQYyhLzJVHnv+IXUQ08zYesn2wo
-----END RSA PRIVATE KEY-----

key3.pem

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDI2CE0B2RKEb//////////////////////////////////////
//////////////////////////////////75vyzSCAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAz4QIDAQAB
AoGAB+J66eImZ5qrHnThix504YsedOGLHnThix504YsedOGLHnThix504YsedOGL
HnThix504YsedOGLHnThix501y2qp54xtc5KMbXOSjG1zkoxtc5KMbXOSjG1zkox
tc5KMbXOSjG1zkoxtc5KMbXOSjG1zkoxtc5KMbXOSjG10F8CQQDbQWfif///////
////////////////////////////////////////////////////////////////
//////8XAkEA6oDWTX//////////////////////////////////////////////
////////////////////////////////xwJAIpG8bGTcGyPk3Bsj5NwbI+TcGyPk
3Bsj5NwbI+TcGyPk3Bsj5NwbI+TcGyPk3Bsj5NwbI+TcGyPk3Bsj5Nwa/wJBALVP
XeJX+CgH1/goB9f4KAfX+CgH1/goB9f4KAfX+CgH1/goB9f4KAfX+CgH1/goB9f4
KAfX+CgH1/goB9f4J9sCQQDUWMa5R/Lrn4uxI8kYHW6IbrFz/Z+WxX4g7SJxHnnN
e+pPF6eOyrhTIFJo9Og4mOCbVLMdoQUjluPtaAxyB5YB
-----END RSA PRIVATE KEY-----

message

4774968A3F4EEA651B5E35CB2E33622ADAC7EE0623D17C668E78E91B9E066F06DEDFBDFE127010D8258DF23A001542F4372D9467D00DC59032934B7763A51F8D4AB6BB1165637287AE0860C0459F07D5EF303097DBBAABD1761D3ACCE925854648612F85825B0ED54F86F55A33B13B6E86CFD6CBC1A51DF3751E28554EC45A5E

rsa.py

from Crypto.PublicKey import RSA  # stands for Reyn-Shulk Algorithm
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import isPrime, inverse, GCD
from secret import secret_seed, flag

N_BITS = 512

# very secure: used in Java in billions of devices!
class RNG:
    """This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and
    described by Donald E. Knuth in The Art of Computer Programming, Volume 3: Seminumerical
    Algorithms, section 3.2.1."""
    def __init__(self, seed):
        """Given a seed value, initializes the RNG."""
        self.seed = (seed ^ 0x5DEECE66D) & ((1 << 48) - 1)

    def next(self, bits=32):
        """Updates the state and returns the given number of random bits as an integer. Must be less than
        48."""
        self.seed = (self.seed * 0x5DEECE66D + 0xB) & ((1 << 48) - 1)
        return self.seed >> (48 - bits)

    
def lcm(a, b):
    return a * b // GCD(a, b)

def gen_random_int(a, b, rng):
    """Gets a random integer in the interval [a, b)."""
    x = rng.next(32)
    print(x)
    return int(a + (x / (2 ** 32)) * (b - a))

def gen_random_prime(rng):
    # select an odd 1024-bit number at random using random.random()
    num = gen_random_int(2 ** (N_BITS - 1), 2 ** N_BITS, rng)
    # decrement until prime
    while not isPrime(num):
        num -= 1
        # prevent underflow
        if num == 2 ** (N_BITS - 1):
            num = 2 ** N_BITS - 1
    return num

def gen_random_key(rng):
    # generate p and q at random
    p = gen_random_prime(rng)
    q = gen_random_prime(rng)
    n = p * q
    e = 65537  # standard default
    # compute d, the inverse of e mod lcm(p - 1, q - 1)
    d = inverse(e, lcm(p - 1, q - 1))
    return RSA.construct((n, e, d, p, q))

def encrypt(data, key):
    cipher = PKCS1_OAEP.new(key)
    return cipher.encrypt(data)

def decrypt(data, key):
    cipher = PKCS1_OAEP.new(key)
    return cipher.decrypt(data)


rng = RNG(secret_seed)
with open("data/key1.pem", 'wb') as f:
    f.write(gen_random_key(rng).exportKey('PEM'))
with open("data/key2.pem", 'wb') as f:
    f.write(gen_random_key(rng).exportKey('PEM'))
with open("data/key3.pem", 'wb') as f:
    f.write(gen_random_key(rng).exportKey('PEM'))

secret_key = gen_random_key(rng)
with open('data/message', 'w') as f:
    f.write(bytes(encrypt(flag, secret_key)).hex().upper())

rsabreak.py

from Crypto.PublicKey import RSA  # stands for Reyn-Shulk Algorithm
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import isPrime, inverse, GCD

import binascii

p1 = open("data/key1.pem", 'rb').read()
p2 = open("data/key2.pem", 'rb').read()
p3 = open("data/key3.pem", 'rb').read()


k_p1 = RSA.importKey(p1)
k_p2 = RSA.importKey(p2)
k_p3 = RSA.importKey(p3)


def gen(n):
    return int(2 ** 511 + (n / (2 ** 32)) * (2 ** 511))


def ungen(n):
    return int((n - (2 ** 511))/(2**479))


class RNG:
    """This is a linear congruential pseudorandom number generator, as defined by D. H. Lehmer and
    described by Donald E. Knuth in The Art of Computer Programming, Volume 3: Seminumerical
    Algorithms, section 3.2.1."""
    def __init__(self, seed):
        """Given a seed value, initializes the RNG."""
        self.seed = (seed ^ 0x5DEECE66D) & ((1 << 48) - 1)


    def next(self, bits=32):
        """Updates the state and returns the given number of random bits as an integer. Must be less than
        48."""
        self.seed = (self.seed * 0x5DEECE66D + 0xB) & ((1 << 48) - 1)
        return self.seed >> (48 - bits)

    def seed_rng(self, x):
        self.seed = x
        

# taken from OpenSSL output
values = [0xA351F13C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4D,
          0xC7EEF649FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDD,
          0xB02244107FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDF,
          0xA2DDE4227FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF25,
          0xDB4167E27FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF17,
          0xEA80D64D7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7]


for i in range(0, (2**16)):

    x = ungen(values[0])

    x = x << 16

    x += i

    r = RNG(1)

    r.seed_rng(x)

    y = r.next(32)

    if y == ungen(values[1]):
        s = x
    
r = RNG(1)

r.seed_rng(s)

def ensurePrime(x):
    while not isPrime(x):
        x -= 1

        if x == 2 ** 511:
            x = 2 ** 512 - 1

    return x


def lcm(a, b):
    return a * b // GCD(a, b)


r.next()
r.next()
r.next()
r.next()
r.next()

p = gen(r.next())
q = gen(r.next())

p = ensurePrime(p)
q = ensurePrime(q)

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

key = RSA.construct((n, e, d, p, q))

ct = open("data/message").read()

ciphertext = binascii.unhexlify(ct)

cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(ciphertext).decode())