PwnThyBytes CTF 2019 - LOTR (Crypto, 936pts, 5 solves)

0_sol.sage

import hashlib
from random import randint

f = open('gov_officials_PK.txt')
pk = []
while True:
	try:
		pk.append(int(f.readline()))
	except:
		break


k = 1024
b = 2 * k + 128
e = 0x10001

signer_count = 243

def sha256(my_string):
	m = hashlib.sha256(my_string).digest()
	return int(m.encode('hex'),16)

def RSA_permutation(x, e, N):
	r = x % N
	q = x // N 
	if (q + 1) * N <= 2 ** b:
		return q * N + int(pow(r, e, N)) # must convert to int!!!
	else:
		return x 

def num2vec(x):
	binstr = bin(x % (2 ** 256))[2:].rjust(256, '0')
	return vector(GF(2), map(int, binstr))


# ~15 mins on my laptop
cnt = 0
find = 0
while not find:
	cnt += 1
	if cnt % 100 == 0:
		print cnt
	target = num2vec(sha256('FAKE NEWS'))
	all_sig = []
	m = []
	for i in range(signer_count):
		fir = randint(2 ** (b - 1) + 1, 2 ** b - 1)
		sec = randint(2 ** (b - 1) + 1, 2 ** b - 1)
		all_sig.append((fir, sec))
		fir_ = int(RSA_permutation(fir, e, pk[i]))
		sec_ = int(RSA_permutation(sec, e, pk[i]))
		target = target + num2vec(sec_)
		m.append(num2vec(fir_) + num2vec(sec_))
	m = matrix(GF(2), m)
	m = m.transpose()
	try:
		tmp = m.solve_right(target)
		f = open('result.txt', 'wb')
		for _ in all_sig:
			f.write(str(_) + '\n')
		f.write(str(list(tmp)) + '\n')
		f.close()
		find = 1
	except:
		continue

all_sig = []
f = open('result.txt', 'r')
for i in range(signer_count):
	all_sig.append(eval(f.readline()))
choose = eval(f.readline())

w = 0
for i in range(1):
	if choose[i] == 1:
		w ^^= int(RSA_permutation(all_sig[i][0], e, pk[i]))
	else:
		w ^^= int(RSA_permutation(all_sig[i][1], e, pk[i]))

print w % (2 ** 256) == sha256('FAKE NEWS') % (2 ** 256)

1_sol.py

from pwn import *

all_sig = []
f = open('result.txt', 'r')
for i in range(243):
	all_sig.append(eval(f.readline()))
choose = eval(f.readline())

con = remote('52.142.217.130', 13375)
con.recvuntil('Command: ')
con.sendline('2')
con.recvuntil('want to verify?\n')
con.sendline('FAKE NEWS')
con.recvuntil('What\'s the signature?\n')
for i in range(243):
	if choose[i] == 1:
		con.sendline(str(all_sig[i][0]))
	else:
		con.sendline(str(all_sig[i][1]))
con.interactive()
#PTBCTF{b3123cb707b8af89643b2441b182ca17}

2_LOTR.py

import gmpy, signal, hashlib, sys
from os import urandom

from hashlib import *
from random import randint

k = 1024
b = 2*k + 128
e = 0x10001


signer_count = 243


def sha256(my_string):
	m = hashlib.sha256(my_string).digest()
	return int(m.encode('hex'),16)

def Sign_Keygen(no_users):
	f = open('gov_officials_PK.txt','w')
	g = open('gov_officials_SK.txt','w')
	for i in range(no_users):
		p = gmpy.next_prime(int(urandom(k / 8).encode('hex'),16))
		q = gmpy.next_prime(int(urandom(k / 8).encode('hex'),16))
		N = p * q 
		d = gmpy.invert(e, (p-1)*(q-1))
		f.write(str(N) + '\n')
		g.write(str(d) + '\n')
	f.close()
	g.close()


def RSA_permutation(x,e,N):
	r = x % N
	q = x // N 
	if (q+1)*N <= 2 ** b:
		return q * N + pow(r,e,N) 
	else:
		return x 

def Sign_Oracle(signer,message):
	if message != 'FAKE NEWS':
		f = open('gov_officials_PK.txt','r')
		g = open('gov_officials_SK.txt','r')
		Pub_keys = []
		d = []
		for i in f:
			Pub_keys.append(int(i.strip(),10))
		if signer < 0 or signer >= len(Pub_keys):
			return 'NOT allowed! '
		for i in g:
			d.append(int(i.strip(),10))
		f.close()
		g.close()
		x = [0] * len(Pub_keys)
		v = sha256(message)
		for j in range(len(Pub_keys)):
			if (j != signer):
				x[j] = randint(2 ** (b-1) + 1, 2 ** b - 1)
				v = v ^ RSA_permutation(x[j],e,Pub_keys[j])
		x[signer] = RSA_permutation(v,d[signer],Pub_keys[signer])
		return x
	else:
		return 'NOT allowed! '


def Verify(x, message):
	w = 0
	f = open('gov_officials_PK.txt','r')
	Pub_keys = []
	for i in f:
		Pub_keys.append(int(i.strip(),10))
	f.close()
	if len(x) != len(Pub_keys):
		return 'incorrect component count: %d given versus %d needed' % ( len(x), len(Pub_keys) )
	for j in range(len(Pub_keys)):
		w = w ^ RSA_permutation(x[j],e,Pub_keys[j])
	if sha256(message) == w % (2 ** 256):
		if message == 'FAKE NEWS':
			flag = open("flag.txt").read()
			return 'VALID signature, you get the FLAG: %s' % flag
		else:
			return 'VALID signature'
	else:
		return 'NOT valid'



def do_initial_setup():
	Sign_Keygen(signer_count)


def do_sign():
	print "What message do you want to sign?"
	msg = raw_input().strip()

	print "Who do you want to sign it?"
	idx = raw_input().strip()
	try:
		idx = int(idx)
	except:
		return

	signature = Sign_Oracle(idx, msg)
	print len(signature)
	print "Here you go:"
	for i in  signature:
		print i

def do_verify():
	print "What message do you want to verify?"
        msg = raw_input().strip()
	print "What's the signature?"

	sig_vec = []
	for i in range(signer_count):
		sig = int(raw_input())
		if (sig < 2 ** b - 2 ** (2 * k)) and (sig > 2 ** (b-1) + 2 ** (2*k)):
			sig_vec.append( sig )
		else:
			print "Signature NOT valid!"
			exit()
	print Verify(sig_vec, msg)


def input_int(prompt):
    sys.stdout.write(prompt)
    try:
        n = int(raw_input())
        return n
    except ValueError:
        return 0
    except:
        exit()

def menu():
    while True:
        print "========== LOTR =========="
        print "1. Sign message"
        print "2. Verify message"
        print "3. Exit"
        choice = input_int("Command: ")
        {
                1: do_sign,
                2: do_verify,
                3: exit,
        }.get(choice, lambda *args:1)()

if __name__ == "__main__":
    signal.alarm(15)
    menu()