hellman/1_solution.py

## 1_solution.py
#-*- coding:utf-8 -*-

# python3 adaptation...
from __future__ import print_function, division

from sage.all import *

# begin copy paste ================
import hashlib
f = open('gov_officials_PK.txt','r')
Pub_keys = []
for i in f:
    Pub_keys.append(int(i.strip(),10))
f.close()

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

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

signer_count = 243

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 gen(pk):
    sig = randint(2 ** (b-1) + 2 ** (2*k) + 1, 2 ** b - 2 ** (2 * k) - 1)
    w = RSA_permutation(sig, e, pk) % 2**256
    w = tobin(w, 256)
    w = vector(GF(2), w)
    return sig, w
# end copy paste ===================

def tobin(x, bits):
    return tuple(ZZ(x).digits(2, padto=bits)[::-1])

mat = []
sources = []

# since we must take exactly one sig per member
# we start with a pair of random sigs per member,
# "assume" that we take the first ones (record xor(all w1) = target1)
# and make a binary variable tracking
#   whether we switch from first sig to the second
# for each pair we keep the difference of respective (w) vectors
# as a result, we need to find an *arbitrary* subset of those differences
# that matches the difference (target1 xor final_target)
target2 = vector(GF(2), tobin(sha256("FAKE NEWS"), 256))
target1 = vector(GF(2), (0,)*256)
for j in range(len(Pub_keys)-1):
    sig1, w1 = gen(Pub_keys[j])
    sig2, w2 = gen(Pub_keys[j])
    target1 += w1
    sources.append((sig1, sig2))
    mat.append(vector(GF(2), w1 + w2))

# note that we have 243 vectors and 256 equations
# we have to be lucky to get the solution
# but instead of generating the whole system many times,
# we can change only the last vector
# and automatically assume that we take it in the solution
# we need on average 2^{256-242} = 16k runs
# if the matrix without the last vector has full rank 242
# (this check is not done here)

m = matrix(GF(2), mat).transpose()
print(m.nrows(), "x", m.ncols(), ":", m.rank())

# generate parity check matrix
# to check for solutions quickly
# matrix x vector is O(n^2)
# vs matrix.solve_right is O(n^2.8) or whatever
paritycheck = m.left_kernel().matrix()

itr = 0
while True:
    sig, w = gen(Pub_keys[-1])

    target = target1 + target2 + w
    if paritycheck * target == 0:
        break
    print("no sol..", itr, paritycheck * target)
    itr += 1

sol = m.solve_right(target)
print("sol", sol)

ans = [s2 if take else s1 for (s1, s2), take in zip(sources, sol)]
ans.append(sig)

w = 0
for j in range(len(Pub_keys)):
    w = w ^ RSA_permutation(ans[j], e, Pub_keys[j])

assert sha256("FAKE NEWS") == w % (2 ** 256)

f = open("sol", "w")
f.write("2\n")
f.write("FAKE NEWS\n")
for v in ans:
    f.write("%d\n" % v)
f.close()

os.system("cat sol | nc 52.142.217.130 13375")

## 2_LOTR.py
"""
Author: rtitiu

The file gov_officials_PK.txt contains a list of RSA public keys of some government employees. Any signer who knows the secret key d[j] corresponding to one of the public keys N[j] is able to anonymously sign any document on behalf of all the people from the list.

Thus, a whistleblower can anonymously leak documents whose authenticity can be publicly verified, while maintaining anonymity within that group of people.

The goal of the task is to produce a valid signature of a specific document/message on behalf of the entire group, even though you don't have access to any of the secret keys. Good luck!

nc 52.142.217.130 13375
"""

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()
	#-- coding:utf-8 --

	# python3 adaptation...
	from __future__ import print_function, division

	from sage.all import *

	# begin copy paste ================
	import hashlib
	f = open('gov_officials_PK.txt','r')
	Pub_keys = []
	for i in f:
	Pub_keys.append(int(i.strip(),10))
	f.close()

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

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

	signer_count = 243

	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 gen(pk):
	sig = randint(2 (b-1) + 2 (2k) + 1, 2 * b - 2 ** (2 * k) - 1)
	w = RSA_permutation(sig, e, pk) % 2**256
	w = tobin(w, 256)
	w = vector(GF(2), w)
	return sig, w
	# end copy paste ===================

	def tobin(x, bits):
	return tuple(ZZ(x).digits(2, padto=bits)[::-1])

	mat = []
	sources = []

	# since we must take exactly one sig per member
	# we start with a pair of random sigs per member,
	# "assume" that we take the first ones (record xor(all w1) = target1)
	# and make a binary variable tracking
	# whether we switch from first sig to the second
	# for each pair we keep the difference of respective (w) vectors
	# as a result, we need to find an arbitrary subset of those differences
	# that matches the difference (target1 xor final_target)
	target2 = vector(GF(2), tobin(sha256("FAKE NEWS"), 256))
	target1 = vector(GF(2), (0,)*256)
	for j in range(len(Pub_keys)-1):
	sig1, w1 = gen(Pub_keys[j])
	sig2, w2 = gen(Pub_keys[j])
	target1 += w1
	sources.append((sig1, sig2))
	mat.append(vector(GF(2), w1 + w2))

	# note that we have 243 vectors and 256 equations
	# we have to be lucky to get the solution
	# but instead of generating the whole system many times,
	# we can change only the last vector
	# and automatically assume that we take it in the solution
	# we need on average 2^{256-242} = 16k runs
	# if the matrix without the last vector has full rank 242
	# (this check is not done here)

	m = matrix(GF(2), mat).transpose()
	print(m.nrows(), "x", m.ncols(), ":", m.rank())

	# generate parity check matrix
	# to check for solutions quickly
	# matrix x vector is O(n^2)
	# vs matrix.solve_right is O(n^2.8) or whatever
	paritycheck = m.left_kernel().matrix()

	itr = 0
	while True:
	sig, w = gen(Pub_keys[-1])

	target = target1 + target2 + w
	if paritycheck * target == 0:
	break
	print("no sol..", itr, paritycheck * target)
	itr += 1

	sol = m.solve_right(target)
	print("sol", sol)

	ans = [s2 if take else s1 for (s1, s2), take in zip(sources, sol)]
	ans.append(sig)

	w = 0
	for j in range(len(Pub_keys)):
	w = w ^ RSA_permutation(ans[j], e, Pub_keys[j])

	assert sha256("FAKE NEWS") == w % (2 ** 256)

	f = open("sol", "w")
	f.write("2\n")
	f.write("FAKE NEWS\n")
	for v in ans:
	f.write("%d\n" % v)
	f.close()

	os.system("cat sol \| nc 52.142.217.130 13375")
	"""
	Author: rtitiu

	The file gov_officials_PK.txt contains a list of RSA public keys of some government employees. Any signer who knows the secret key d[j] corresponding to one of the public keys N[j] is able to anonymously sign any document on behalf of all the people from the list.

	Thus, a whistleblower can anonymously leak documents whose authenticity can be publicly verified, while maintaining anonymity within that group of people.

	The goal of the task is to produce a valid signature of a specific document/message on behalf of the entire group, even though you don't have access to any of the secret keys. Good luck!

	nc 52.142.217.130 13375
	"""

	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()