redpwnCTF 2020

jeopardy-carmichael.py

from functools import reduce
from math import prod
from tqdm import tqdm
import random
import gmpy2

def rabin(n):
	if n == 2: return True
	if n%2 == 0: return False
	r,d = 0,n-1
	while d%2 == 0: r += 1; d //= 2
	for k in range(1):
		a = random.randint(2,n-2)
		x = pow(a,d,n)
		if x == 1 or x == n-1: continue
		for i in range(r-1):
			x = pow(x,2,n)
			if x == n-1: continue
		else: return False
	return True

k = 941869
P = [5, 13, 19, 23, 37, 397]

L = reduce(gmpy2.lcm, map(lambda p: p-1, P))
while True:
	k += 1
	M = k*L + 1
	Q = [M*(p-1) + 1 for p in P]
	if all(map(gmpy2.is_prime, Q)):
		break

Q = list(map(int, Q))
n = prod(Q)

print('k', k)
print('Q', Q, list(map(int.bit_length, Q)))
print('n', n, n.bit_length())
print(f'./ecgen --fp -n {n}')

for i in range(1000):
	if rabin(n):
		print(i)

jeopardy.sage

def dlog(a, base, order, f):
	l=[0]*len(f)
	for i,(pi,ri) in enumerate(f):
		for j in range(ri):
			c=bsgs(base*(order//pi),(a-base*l[i])*(order//pi**(j+1)),(0,pi),operation='+')
			l[i] += c*(pi**j)
	from sage.arith.all import CRT_list
	return CRT_list(l,[pi**ri for pi,ri in f])

Q = [1837470101, 5512410301, 8268615451, 10106085551, 16537230901, 181909539901]
n = 2546219544036917612349940381838413660553096101698112741559701
p = 0x0195a2dc6d72ec12adb2a30974903006d8e28d4debe9fe127483
a = 0x0195a2dc6d72ec12adb2a30974903006d8e26cb7298e1f127483
b = 0x0195a2dc6d72ec12adb2a30974902b8d242ef90b767e7e127483

E = EllipticCurve(GF(p), [a,b])
assert E.order() == n

def read(s):
	params = eval(s.replace(':', ','))[:2]
	return E(params)

# G = read(input('G: '))
# H = read(input('H: '))

G = '(900930215601169444799562853488996822803750434935519762580486 : 1437862562854832336539753568489027856889819688286102097925406 : 1)'
H = '(500463740668168523549332991632103121852346083045111145104802 : 1268713509142947882103270251122311761466400555565647889961807 : 1)'

# secret = randint(1,E.order()-1)
# G = E.gens()[0]
# H = secret*G
# print(secret)

print(dlog(H, G, n, Factorization([(q, 1) for q in Q])))

newcrypt-relation.sage

R.<d1,k1,d2,k2,d3,k3,d4,k4,g,e1,e2,e3,e4,n> = PolynomialRing(ZZ)

d = [0, d1, d2, d3, d4]
e = [0, e1, e2, e3, e4]
k = [0, k1, k2, k3, k4]

def W(i):
	return d[i]*g*e[i] - k[i]*n

def G(i,j):
	return k[i]*d[j]*e[j] - k[j]*d[i]*e[i]

exp = W(1)*W(2)*W(3)*W(4)
print(exp)

newcrypt.sage

n = 23606413766185125262715665064098566623392366241549799634536224249606821166508227661740963059390510723969542207420674403866302781734490190584327801883726734032078963903132346089383414812961131951474870457122782912866128207079825120011396670079612200883368880755263795594045770557800307577612649185609143459990250705270899075372732462351203338356687954929562907624387508223669835198161500541223853908304758164434125791065298963775559151746919521768558386507634585806044506359628534349719576557511850094141412958204131051925016158924842149605538033982403051452611258604768375962306349429212807320398845497859144547996527
e1 = 4525378769631249566244977471897300614866560736266259975908397510012737494956566617381502438794014727854889718181911378152998641026929902118170421346949931286522194349443052417574441576358833971754953241812309251772026259915877917090213817244523040289167891599867320580181862721332605390261883096160062124032826906947020479111505769862994328817442655622791326614092270594159299823940068956115680704908939376540075590153580411903703101062677967582828934914868515341773539758028428871167827435637597669409923861761295261613203526142470432108663654597077567466133772066684681016873916660847339562150611606875182092076747
e2 = 10172735311139530699605801066001604371200661094358260342392004380609091599491445007621569572730528007213603532285433070714283212002659767339317913009735445913936839236136136317225848872060024826651469980094298505689620956131817386821110797264073358204216337754890530637685833810019492317120012785929280086664917654155804421781103769012386285484397833314578860517006477753670275972937399848570953454457594300181990814514260868465771475694027441647750408361573878741462372842574791467349786885013303504507258134982535903368406483033869397798769650628468865161839214573530007810862766821126984737250324234847589513058569
e3 = 2227060622231017112810183337871567667710669960386807798108316064846234792846864759847654302635488115451385882008160666716857009943700159083293350411903039563964249756463539812328540527896366502459538825055036253734211485128491340972560832697514492848834194085703098012472707942482910460449741522913386044654154046491053065661530251267448363456369149215363633902843311408750667917053390508638660435885059453366105512987332779316890388243159349290320804371506523364055394589040348799728812357961002300391287402897804354719101619793128058550667388155552628739463459259252191247115431112364476319460584549335194551842079
e4 = 9181198739883924674262577976574080839604033433089422736970738072462688908040351153438466304266985952969750956794586135273753050004215013974417810470681608130130489047507539176804082510852245411368681478259682031096252377598320002363387961411850851931035802345092191610135511904800337822534477599351098742654324305322262337437503115193360343414083931764469122224172424390209847262499640368362531535916015916278036286434131652956971303170132714895420317010320064070889097959403124401509672648853727890286757665544936418429561485912274366845641146542105108156247157759856869485926363831994924875752485708876235530600469

a = 896/2048

M = matrix([
	[1, -n,   0,   n^2,   0,      0,      0,     -n^3,   0,      0,      0,      0,         0,         0,         0,         n^4],
	[0, e1, -e1, -e1*n, -e1,      0,   e1*n,   e1*n^2, -e1,      0,      0,      0,         0,         0,   -e1*n^2,     -e1*n^3],
	[0,  0,  e2, -e2*n,   0,   e2*n,      0,   e2*n^2,   0,   e2*n,      0,      0,         0,   -e2*n^2,         0,     -e2*n^3],
	[0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*n,   0, -e1*e2,      0,  e1*e2,         0,   e1*e2*n,   e1*e2*n,   e1*e2*n^2],
	[0,  0,   0,     0,  e3,  -e3*n,  -e3*n,   e3*n^2,   0,      0,      0,      0,   -e3*n^2,         0,         0,     -e3*n^3],
	[0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*n,   0,      0,  e1*e3,      0,   e1*e3*n,         0,   e1*e3*n,   e1*e3*n^2],
	[0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*n,   0,      0, -e2*e3, -e2*e3,   e2*e3*n,   e2*e3*n,         0,   e2*e3*n^2],
	[0,  0,   0,     0,   0,      0,      0, e1*e2*e3,   0,      0,      0,      0, -e1*e2*e3, -e1*e2*e3, -e1*e2*e3, -e1*e2*e3*n],
	[0,  0,   0,     0,   0,      0,      0,        0,  e4,  -e4*n,      0,      0,    e4*n^2,    e4*n^2,    e4*n^2,     -e4*n^3],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,  e1*e4, -e1*e4, -e1*e4,  -e1*e4*n,  -e1*e4*n,         0,   e1*e4*n^2],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,  e2*e4,      0,  -e2*e4*n,         0,  -e2*e4*n,   e2*e4*n^2],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,      0,  e3*e4,         0,  -e3*e4*n,  -e3*e4*n,   e3*e4*n^2],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,      0,      0,  e1*e2*e4,         0,         0, -e1*e2*e4*n],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,      0,      0,         0,  e1*e3*e4,         0, -e1*e3*e4*n],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,      0,      0,         0,         0,  e2*e3*e4, -e2*e3*e4*n],
	[0,  0,   0,     0,   0,      0,      0,        0,   0,      0,      0,      0,         0,         0,         0, e1*e2*e3*e4],
])

D = diagonal_matrix(ZZ, map(round, [
	n^2,
	n^(3/2),
	n^(a+2),
	n^(1),
	n^(a+2),
	n^(a+3/2),
	n^(a+3/2),
	n^(1/2),
	n^(a+2),
	n^(a+3/2),
	n^(2*a+2),
	n^(2*a+2),
	n^(a+1),
	n^(a+1),
	n^(a+1),
	1
]))

L = M*D
B = L.LLL()
small = L.solve_left(B[0])

print('d1', gcd([small[i] for i in (1,3,5,7,9,12,13,15)]))
print('d2', gcd([small[i] for i in (2,3,6,7,10,12,14,15)]))
print('d3', gcd([small[i] for i in (4,5,6,7,11,13,14,15)]))
print('d4', gcd([small[i] for i in (8,9,10,11,12,13,14,15)]))

ratification.py

from Crypto.Util.number import *
from pwn import *

message = b'redpwnCTF is a cybersecurity competition hosted by the redpwn CTF team.'

t = remote('2020.redpwnc.tf', 31752)
# t = process(['python', 'server.py'])

p = int(t.recvline())
e = 65537

def sign(x):
	m = long_to_bytes(x)
	t.recvuntil('Exit\n')
	t.sendline('1')
	t.recvuntil('Message: ')
	t.sendline(m)
	t.recvline()
	return int(t.recvline())

n = GCD(pow(sign(2), 2) - sign(4), pow(sign(3), 2) - sign(9))
q = n // p
assert isPrime(q)

d = inverse(e, (p-1)*(q-1))
s = pow(bytes_to_long(message), d, n)

t.recvuntil('Exit\n')
t.sendline('2')
t.sendline(message)
t.sendline(str(s))

t.interactive()

seekrypt.sage

encrypted, y, n = tuple(map(eval, open('output')))

mask = ((1 << 400) - 1) << 0x1f0
garbage = y & mask
alpha_bar = y - garbage

F.<x> = PolynomialRing(Zmod(n))
pol = (2^0x1f0)*x + alpha_bar
pol = pol.monic()
root = pol.small_roots(X=2^400, beta=0.5)[0]

alpha = alpha_bar + (int(root) << 0x1f0)
assert n % alpha == 0

flag2 = int(root) ^^ (int(garbage) >> 0x1f0)
print(flag2.to_bytes(50, 'big'))

speedy-signatures.py

import ecdsa
from ecdsa.ecdsa import Public_key, Signature
from ecdsa.ellipticcurve import Point
import gmpy2
import hashlib
import itertools
import sys
from tqdm import tqdm

from pwn import *

def legendre(a, p):
	return pow(a, (p - 1) // 2, p)
 
def tonelli(n, p):
	assert legendre(n, p) == 1, "not a square (mod p)"
	q = p - 1
	s = 0
	while q % 2 == 0:
		q //= 2
		s += 1
	if s == 1:
		return pow(n, (p + 1) // 4, p)
	for z in range(2, p):
		if p - 1 == legendre(z, p):
			break
	c = pow(z, q, p)
	r = pow(n, (q + 1) // 2, p)
	t = pow(n, q, p)
	m = s
	t2 = 0
	while (t - 1) % p != 0:
		t2 = (t * t) % p
		for i in range(1, m):
			if (t2 - 1) % p == 0:
				break
			t2 = (t2 * t2) % p
		b = pow(c, 1 << (m - i - 1), p)
		r = (r * b) % p
		c = (b * b) % p
		t = (t * c) % p
		m = i
	return r

C = ecdsa.NIST256p
G = C.generator
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n = C.order

def point(x):
	y = tonelli(((pow(x, 2)+a)*x+b) % p, p)
	return Point(C.curve, x, y), Point(C.curve, x, -y)

def inv(x):
	return gmpy2.invert(x, n)

m1 = b'a'
m2 = b'b'
h1 = int(hashlib.sha256(m1).hexdigest(), 16)
h2 = int(hashlib.sha256(m2).hexdigest(), 16)

# nc = process('./server.py')
nc = remote('2020.redpwnc.tf', 31452)

def recv():
	nc.recvline()
	Q = Public_key(G, Point(C.curve, *map(int, nc.recvline().split(b' '))))
	nc.sendlineafter(': ', m1)
	nc.sendlineafter(': ', m2)
	return Q, list(map(int, nc.recvline().split(b' ')))

def send(x):
	nc.recvline()
	nc.sendline(str(x))
	assert b'Correct' in nc.recvline()
	out = nc.recvline()
	if b'flag' in out:
		print(out)

Q, vals = recv()
for r1, s1, s2 in itertools.permutations(vals):
	if Q.verifies(h1, Signature(r1, s1)):
		swap = False
		break
	elif Q.verifies(h2, Signature(r1, s1)):
		t = m1; m1 = m2; m2 = t
		t = h1; h1 = h2; h2 = t
		swap = True
		break
else:
	print('none')
	sys.exit()

possible = point(r1)
for diff in tqdm(range(-4095, 4095)):
	for H1 in possible:
		H2 = H1 + diff*G
		r2 = H2.x()
		if Q.verifies(h2, Signature(r2, s2)):
			break
	else:
		continue
	break
else:
	print('error finding other r2')
	sys.exit()

if swap:
	diff = -diff
d = (diff + inv(s1)*h1 - inv(s2)*h2) * inv(inv(s2)*r2 - inv(s1)*r1) % n
assert d*G == Q.point
send(d)
k = inv(s1)*(h1 + r1*d) % n

def guess():
	Q, vals = recv()
	for s1 in vals:
		for diff in range(-4095, 4096):
			k1 = k+diff
			H1 = k1*G
			r1 = H1.x()
			d = (s1*k1 - h1)*inv(r1) % n
			if d*G == Q.point:
				send(d)
				return
			d = (s1*k1 - h2)*inv(r1) % n
			if d*G == Q.point:
				send(d)
				return
	print('no guess found')
	sys.exit()

for i in tqdm(range(99)):
	guess()

nc.interactive()