ctf-writeups

Techras

I'm having trouble determining when to discard a number versus when to reuse it in Techras. Any advice would be helpful!

Attachment:

#!/usr/bin/env python3

from Crypto.Util.number import *
from string import *
from flag import flag

def pad(flag):
	r = len(flag) % 8
	if r != 0:
		flag = flag[:-1] + (8 - r) * printable[:63][getRandomRange(0, 62)].encode() + flag[-1:]
	return flag

def genkey(nbit):
	p, q = [getPrime(nbit) for _ in ':)']
	n = p * q
	return n, (p, q)

def encrypt(msg, pubkey):
	msg = pad(msg)
	e = getPrime(32)
	m = bytes_to_long(msg)
	c = pow(m, e, pubkey)
	return str(c) + str(e)

nbit = 1024
pubkey, _ = genkey(nbit)

print(f'n = {pubkey}')
for _ in range(110):
	print(f'c = {encrypt(flag, pubkey)}')

The problem is, the randomness of pad is too low: only 63 possibilities. So two pad leads to the same m, which is encrypted using two e. It is prone to the attack describe in https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem:

\[c_1 = m^{e_1} \bmod N \\ c_2 = m^{e_2} \bmod N \\ e_1a+e_2b = 1 \\ m = c_1^ac_2^b \bmod N\]

Steps:

1. Recover c and e from provided output.txt
2. Enumerate all pairs until we find the flag

from Cryptodome.Util.number import *

lines = open("output.txt", encoding="utf-8").readlines()
n = int(lines[0].split()[2])
c = [int(line.split()[2]) for line in lines[1:]]
print(n, len(c))

# find 32-bit prime suffixes
cs = []
es = []
for i in c:
    for j in range(1, 12):
        part = int(str(i)[-j:])
        if isPrime(part) and part.bit_length() == 32:
            cs.append(int(str(i)[:-j]))
            es.append(int(str(i)[-j:]))
print(cs, es)


# generated by google search
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return g, x, y


# find two c with the same padded message
for i in range(len(c)):
    for j in range(i):
        c1 = cs[i]
        e1 = es[i]
        c2 = cs[j]
        e2 = es[j]
        # if c1 = pow(m, e1, n), c2 = pow(m, e2, n)
        # find e1*a+e2*b = 1
        # m = pow(c1, a, n) * pow(c2, b, n) % n
        # https://crypto.stackexchange.com/questions/1614/rsa-cracking-the-same-message-is-sent-to-two-different-people-problem
        g, a, b = extended_gcd(e1, e2)
        if g == 1:
            m = pow(c1, a, n) * pow(c2, b, n) % n
            flag = long_to_bytes(m)
            if b"ASIS" in flag:
                print(flag)

Flag: ASIS{d0nT___rEuS3___peXp!}.