Instantly share code, notes, and snippets.

# defund/jeopardy-carmichael.py

Last active April 5, 2022 22:23
Show Gist options
• Save defund/a670ce45ae4050667de2de92a5891c58 to your computer and use it in GitHub Desktop.
redpwnCTF 2020
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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])))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)]))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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'))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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()