# dicectf2021

Contents

[toc]

## garbled

from generate_garbled_circuit import g_tables, keys

1. 生成了7组key，每组两个元素为 keyi0，keyi1 每个元素的小于2**24
2. 将7组数据按照“门”的指引得到 3 组加密后的 table 每组4行没行两个元素从左到右分别为 gl，v

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  input : key1,key2,key5 # g_tables 钟元素的顺序 g_tables = {5: [(g1, v1), (g2, v2), (g3, v3), (g4, v4)], g1 = enc(key5_0,(key1_0,key2_0)) g2 = enc(key5_0,(key1_0,key2_1)) g3 = enc(key5_0,(key1_1,key2_0)) g4 = enc(key5_1,(key1_1,key2_1)) v1 = enc(0,(key1_0,key2_0)) v2 = enc(0,(key1_0,key2_1)) v3 = enc(0,(key1_1,key2_0)) v4 = enc(0,(key1_1,key2_1)) 

evaluate_circuit 对 g_tables内容进行解密，恢复出 $key_{51},key_{61},key_{71}$

 1 2 3 4 5 6 7 8  key5_1 = dec(g1, (key1_1, key2_1)) 0 = dec(v1, (key1_1, key2_1)) def dec(data, key1, key2): decrypted = decrypt_data(data, key2) decrypted = decrypt_data(decrypted, key1) return decrypted 

 1 2 3 4  0 = dec(v1, (key1_0, key2_0)) 0 = dec(v2, (key1_0, key2_1)) 0 = dec(v3, (key1_1, key2_0)) 0 = dec(v4, (key1_1, key2_1)) 

 1 2 3 4  0 = dec(v1, (key1_0, key2_0)) 0 = dec(v2, (key1_0, key2_1)) 0 = dec(v3, (key1_1, key2_0)) 0 = dec(v4, (key1_1, key2_1)) 

 1 2 3 4 5  key5_0 = dec(g1, (key1_0, key2_0)) key5_0 = dec(g2, (key1_0, key2_1)) key5_0 = dec(g3, (key1_1, key2_0)) key5_1 = dec(g4, (key1_1, key2_1)) 

$algorithm1$

$$assume (k11,k21)is\;global\;keys\\\\ there\;must\;exist\;\\\\ (k10,k21)\\\\ (k11,k20)\\\\ (k10,k20)\\\\ dec(g1, (key1\_0, key2\_0))= dec(g2, (key1\_0, key2\_1))= dec(g3, (key1\_1, key2\_0))$$

## plagiarism

algorithm：

So we have two ciphertexts:

C1 = P1e mod(N)

C2 = P2e mod(N)

where second text is simply first with known difference:

P2 = P1+δ

so we have after substitution:

f = P1e mod(N) - C1

g = (P1+δ)e mod(N) - C2

Calculating GCD(f,g) will give us common dividor a * P1 + b so P1 = -b⁄a.

sage 多项式环算 gcd

  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   R = PolynomialRing(Zmod(n), 'X') X = R.gen() f1 = (X)**e - c1 f2 = (X + delta)**e - c2 r = gcd(f1, f2) def hgcd(a0,a1): if a1.degree() <= (a0.degree()//2): return np.array([[1,0],[0,1]]) m = a0.degree()//2 X = a0.variables()[0] b0 = a0 // X**m b1 = a1 // X**m R = hgcd(b0,b1) [d,e] = (R.dot(np.array([a0,a1]).transpose())).transpose() ff = d % e m = m // 2 g0 = e // X**m g1 = ff // X**m S = hgcd(g0,g1) q = d // e return S.dot(np.array([[0,1],[1,-q]])).dot(R) def gcd(a0,a1): while True: print(a0.degree(), end=", ", flush=True) if a0 % a1 == 0: return a1 if a0.degree() == a1.degree(): a1 = a0%a1 #print(a0.degree()) R = hgcd(a0,a1) [b0,b1] = R.dot(np.array([a0,a1]).transpose()).transpose() if b0%b1==0: return b1 c = b0 % b1 a0 = b1 a1 = c