Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
redpwnCTF 2020 solutions
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)
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])))
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)
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)]))
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()
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'))
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment