Skip to content

Instantly share code, notes, and snippets.

@elliptic-shiho

elliptic-shiho/solve.sage

Last active July 10, 2023 06:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save elliptic-shiho/07b3440678135f0712d467925b9e81af to your computer and use it in GitHub Desktop.
Save elliptic-shiho/07b3440678135f0712d467925b9e81af to your computer and use it in GitHub Desktop.
Download ZIP
Crypto CTF 2023: Big (last phase only)
Raw
solve.sage
from sage.all import *
import output
import binascii
p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967
def compute_t(F, c, a):
cf = F(c)
af = F(a)
return ZZ((cf + sqrt(cf ^ 2 + 4 * af)) / 2)
N = output.pkey
a, C = output.E
Fp = GF(p)
Fq = GF(q)
b = []
for c in C:
tp = compute_t(Fp, c, a)
tq = compute_t(Fq, c, a)
t = crt(tp, tq, p, q)
if kronecker(t, N) == 1:
b.append(1)
else:
b.append(0)
print(binascii.unhexlify(hex(ZZ("".join(map(str, b)), 2))[2:]))
Raw
solve_log
Sun Jul 9 16:45:58 JST 2023 ~/Downloads/Big
> time sage solve.sage
b'CCTF{_Cocks_18e_5chEm3}'
real 0m2.153s
user 0m1.999s
sys 0m0.181s
@elliptic-shiho
Copy link
Author

Writeup: https://shiho-elliptic.tumblr.com/post/722391959624433664/crypto-ctf-2023-writeup-en

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment