# Writeup for Crypto Problems in HufuCTF 2020

## GM

makekey函数中，有

\begin{aligned} (q^2 x)^\frac{p-1}{2} &\equiv q^{p-1} x^\frac{p-1}{2} \equiv (\frac{x}{p})\pmod{p} \newline (p^2 x)^\frac{q-1}{2} &\equiv p^{q-1} x^\frac{q-1}{2} \equiv (\frac{x}{q})\pmod{q} \end{aligned}

$$(q^2 x)^\frac{p-1}{2} + (p^2 x)^\frac{q-1}{2} = n - phi - 1 = pq - (pq - p - q + 1) - 1 = (p-1) + (q-1)$$

msg的这一位bi是0的话，两个勒让德符号肯定都是1；如果这一位bi是1的话，勒让德符号肯定都是-1（p-1或q-1）。

  1 2 3 4 5 6 7 8 9 10  # sage 8.9 N = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697 phi = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820 var("p q") print solve([p*q == N, p*q - p - q + 1 == phi], p, q) # [ # [p == 94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971, q == 100216711979082556377200124903474313599976321274816484378304672662900171906266478070844182716079881540999761528986068197079878654411887736955737660906283803174161740862819849415729979371880583995409044839777513091451849412985192528374337852907661670174530234397743068706607004213367391908429077794527921775907], # [p == 100216711979082556377200124903474313599976321274816484378304672662900171906266478070844182716079881540999761528986068197079878654411887736955737660906283803174161740862819849415729979371880583995409044839777513091451849412985192528374337852907661670174530234397743068706607004213367391908429077794527921775907, q == 94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971] # ] 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  # python3 from Crypto.Util.number import long_to_bytes p = ... q = ... def legendre(a, p): return pow(a, (p-1)//2, p) ciphers = open("output", "r").readlines()[2] ciphers = [int(c) for c in ciphers[1:-3].replace("L", "").split(", ")] msg = "" for c in ciphers: lp = legendre(c, p) lq = legendre(c, q) if lp == 1 and lq == 1: msg += "0" else: msg += "1" print(long_to_bytes(int(msg, 2))) # flag{bd4f1790-f4a2-4904-b4d2-8db8b24fd864} 

## mceliece

irr_poly的系数是$GF(2^6)$上的元素，总共有64个，irr_poly是一个多项式，最高次数为6，所以一共有$64^7 = 2^{42}$种可能，虽然有irreducible这个条件，但还是很多。。而且sage的运行速度挺慢的。

http://doc.sagemath.org/html/en/reference/coding/sage/coding/information_set_decoder.html

⬆️官方实现 ⬇️我的实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  # sage 8.9 ciphers = load("cipher.sobj") pubkey = load("pubkey.sobj") n = 64 k = 28 t = 6 F2 = GF(2) def GetRowVectorWeight(n): return sum(ZZ(i) for i in n[0]) def lee_brickell(G, y): while True: # step 1 I = sample(range(n), k) y_I = matrix(F2, 1, k) # 1*k G_I = matrix(F2, k, k) # k*k for i, col in enumerate(I): y_I[:, i] = y[:, col] G_I[:, i] = G[:, col] if rank(G_I) != k: # has no inverse continue invG_I = G_I^-1 # k*k G_bar = invG_I * G # k*k * k*n = k*n # step 2 y_bar = y - y_I * G_bar # step 3 x = F2.list()[1:] # F_2 / {0} = [1] for ai in range(k): # size-1 subset in I. g = matrix(x[0] * G_bar[ai]) e = y_bar - g wt_e = GetRowVectorWeight(e) # print wt_e if wt_e == t: return e c0 = ciphers[0] e = lee_brickell(pubkey, c) 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  # sage 8.9 ciphers = load("cipher.sobj") pubkey = load("pubkey.sobj") n = 64 k = 28 t = 6 F2 = GF(2) def GetRowVectorWeight(n): return sum(ZZ(i) for i in n[0]) def lee_brickell(G, y): while True: # step 1 I = sample(range(n), k) y_I = matrix(F2, 1, k) # 1*k G_I = matrix(F2, k, k) # k*k for i, col in enumerate(I): y_I[:, i] = y[:, col] G_I[:, i] = G[:, col] if rank(G_I) != k: # has no inverse continue invG_I = G_I^-1 # k*k G_bar = invG_I * G # k*k * k*n = k*n # step 2 y_bar = y - y_I * G_bar # step 3 x = F2.list()[1:] # F_2 / {0} = [1] for ai in range(k): # size-1 subset in I. g = matrix(x[0] * G_bar[ai]) e = y_bar - g wt_e = GetRowVectorWeight(e) # print wt_e if wt_e == t: return e s = "" for c in ciphers: e = lee_brickell(pubkey, c) # c = m * pubkey + e corrected = c - e # m * pubkey = c - e m = pubkey.solve_left(corrected) for i in m[0]: s += str(i) # print s print hex(int(s, 2)).strip('0xL').decode('hex') # flag{c941a3cc-85e3-4401-a0f1-764206e71bf3} 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  # sage 8.9 ciphers = load("cipher.sobj") pubkey = load("pubkey.sobj") C = codes.LinearCode(pubkey) from sage.coding.information_set_decoder import LeeBrickellISDAlgorithm A = LeeBrickellISDAlgorithm(C, (6,6)) s = "" for cipher in ciphers: corrected = A.decode(cipher[0]) # c = m * pubkey + e ==> c' = m * pubkey m = pubkey.solve_left(corrected) s += ''.join(str(i) for i in m) print hex(int(s, 2)).strip('0xL').decode('hex') # flag{c941a3cc-85e3-4401-a0f1-764206e71bf3} 

## pell

 1 2  a = random.randint(10,50) b = random.randint(1,2) 

wiki上就给出了在b = 1的时候，最小解的情况，但没有给出递推公式（也可以自己推算一下）（经某位师傅提醒，wiki上实际上是有递推公式的。。）。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81  import re from hashlib import sha256 from itertools import product import time from pwn import * context.log_level = "debug" s = string.ascii_letters + string.digits while True: r = remote('39.97.210.182', 61235) rec = r.recvline().decode() suffix = re.findall(r'$$XXXX\+(.*?)$$', rec)[0] digest = re.findall(r'== (.*?)\n', rec)[0] print(f"suffix: {suffix} \ndigest: {digest}") print('Calculating hash...') for i in product(s, repeat=4): prefix = ''.join(i) guess = prefix + suffix if sha256(guess.encode()).hexdigest() == digest: print(guess) break r.sendafter(b'Give me XXXX:', prefix.encode()) rec = r.recvlines(numlines=2)[1].decode() a = int(re.findall(r'a = ([0-9].*?),', rec)[0]) b = int(re.findall(r'b = ([0-9].*?)', rec)[0]) print(a, b) if a == 35 and b == 1: x, y = 1, 0 for _ in range(150): x, y = 6*x + 35*y, x + 6*y r.sendline(str(abs(x)).encode()) time.sleep(0.3) r.sendline(str(abs(y)).encode()) time.sleep(0.3) elif a == 30 and b == 1: x, y = 1, 0 for _ in range(150): x, y = 11*x + 60*y, 2*x + 11*y r.sendline(str(abs(x)).encode()) time.sleep(0.3) r.sendline(str(abs(y)).encode()) time.sleep(0.3) elif a == 24 and b == 1: x, y = 1, 0 for _ in range(150): x, y = 5*x + 24*y, 1*x + 5*y r.sendline(str(abs(x)).encode()) time.sleep(0.3) r.sendline(str(abs(y)).encode()) time.sleep(0.3) elif a == 20 and b == 1: x, y = 1, 0 for _ in range(150): x, y = 9*x + 40*y, 2*x + 9*y r.sendline(str(abs(x)).encode()) time.sleep(0.3) r.sendline(str(abs(y)).encode()) time.sleep(0.3) elif a == 15 and b == 1: x, y = 1, 0 for _ in range(150): x, y = 4*x + 15*y, 1*x + 4*y r.sendline(str(abs(x)).encode()) time.sleep(0.3) r.sendline(str(abs(y)).encode()) time.sleep(0.3) else: r.close() continue r.interactive() 

sleep(0.3)的原因是，我先在本地测试的时候，发现如果不sleep的话，可能会有客户端发送过快，导致多条内容到了服务端后会变成一条，然后int解析不了。。

invalid literal for int() with base 10: '47525\n9701\n'