{{ message }}

Instantly share code, notes, and snippets.

# defund/jeopardy-carmichael.py

Created Apr 16, 2021
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. = 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. = 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()