Contents

dicectf2021

Contents

[toc]

garbled

这个有意思了


文件里面给了一堆文件,并有一个示例文件和flag获取文件来调用整个加密电路

from generate_garbled_circuit import g_tables, keys

分析一遍数据生成流程

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

具体流程如下,以第1组table生成的情况示例:

 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))
            

分析调用电路生成input的代码发现input的4个元素为 $key_{11},key_{21},key_{31},key_{41}$

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

以第一组 g_tables 即 key1,key2,key5为例

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

通过key1_1~4_1可以恢复出所有keyi_1

你问我为什么不恢复出所有key?

这就涉及到GarbledCircuit设计初衷了 咕咕咕

对解密的场景可以扩展出这样的式子

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))

我们可以想办法找出所有的key1,key2开缩小范围,但2**48的复杂度是我们不愿意看到的,这里用中间相遇攻击的思想将复杂度降到$O(2\times2^{24})$,这是一个我们可以接受的范围

现在,我们得到了所有满足下式成立的key,需要我们想办法准确的定位地定位到 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)) $$

综上,可以得到 key1_1, key2_1 的准确值

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