Writeup for Crypto problems in De1CTF 2020

2020-05-04 4751 words 10 minutes views

Contents

NLFSR

task.py

 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


from flag import a, b, c, d, flag
assert flag == "De1CTF{" + ''.join([hex(i)[2:] for i in [a, b, c, d]]) + "}"
assert [len(bin(i)[2:]) for i in [a, b, c, d]] == [19, 19, 13, 6]

ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31


def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)


def combine():
    global a, b, c, d
    a = lfsr(a, ma)
    b = lfsr(b, mb)
    c = lfsr(c, mc)
    d = lfsr(d, md)
    [ao, bo, co, do] = [i & 1 for i in [a, b, c, d]]
    return (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do


def genkey(nb):
    s = ''
    for i in range(nb*8):
        s += str(combine())
    open("data", "w+").write(s)


genkey(128*1024)

LFSR部分把r左移一位，m和r二进制值共同为1位数的奇偶决定空位补1或0。

每次combine()会把4个LFSR进行一些运算，最终只会返回1bit值，通过这1bit的信息我们可以把ao，bo，co，do的状态分成两类：

1
2
3
4
5
6
7
8
9


def test(tar):
    for ao in [0, 1]:
        for bo in [0, 1]:
            for co in [0, 1]:
                for do in [0, 1]:
                    if (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do == tar:
                        print("ao={},bo={},co={},do={}".format(ao, bo, co, do))

test(0)

combine()返回0时对应的8个状态：

ao=0,bo=0,co=0,do=0
ao=0,bo=0,co=1,do=1
ao=0,bo=1,co=0,do=0
ao=0,bo=1,co=0,do=1
ao=0,bo=1,co=1,do=0
ao=0,bo=1,co=1,do=1
ao=1,bo=0,co=0,do=0
ao=1,bo=0,co=1,do=1

combine()返回1时对应的8个状态：

ao=0,bo=0,co=0,do=1
ao=0,bo=0,co=1,do=0
ao=1,bo=0,co=0,do=1
ao=1,bo=0,co=1,do=0
ao=1,bo=1,co=0,do=0
ao=1,bo=1,co=0,do=1
ao=1,bo=1,co=1,do=0
ao=1,bo=1,co=1,do=1

CTF wiki上有一个类似的题:

https://ctf-wiki.github.io/ctf-wiki/crypto/streamcipher/fsr/nfsr/

可以看到这题也是有75%的概率combine()返回值和ao的值相等，可以从这里爆破a。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31
def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)
f=open("data","r")
S=f.read()
S=S[:100]#为了提高一点效率，可以先从小的开始尝试，找不到合适的就改一改

def bruteforce():
    for a in range(2**18,2**19):
        a_tmp=a
        cnt=0
        for i in S:
            a_tmp=lfsr(a_tmp,ma)
            if a_tmp&1==int(i):
                cnt+=1
        if cnt/len(S)>0.7:#这里也是慢慢改着算的...会有多个输出，然后把概率提高到0.74-0.76，逐个验证一下
            print(a)
            print(cnt/len(S))
bruteforce()

现在很容易得到了a的值363445，现在通过类似的方法可以枚举b，观察上面两组状态，可以看到有75%的概率 combine() 返回值和 ao, bo 的同或值（相同为真，相异为假）相等。

 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


a = 363445
ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31
def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)
f=open("data","r")
S=f.read()
S=S[:100]#为了提高一点效率，可以先从小的开始尝试，找不到合适的就改一改
​
def bruteforce():
    for b in range(2**18,2**19):
        a_tmp,b_tmp=a,b
        cnt=0
        for i in S:
            tmp=0
            a_tmp=lfsr(a_tmp,ma)
            b_tmp=lfsr(b_tmp,mb)
​
            if (a_tmp&1)==(b_tmp&1):#同或关系
                tmp=1
            else:
                tmp=0
​
            if tmp==int(i):
                cnt+=1
        if cnt/len(S)>0.7:#这里也是慢慢改着算的...会有多个输出，然后把概率提高到0.74-0.76，逐个验证一下
            print(b)
            print(cnt/len(S))
bruteforce()

改一改就可以用来枚举 b 了，从输出中逐个验证，得到 494934。

a 和 b 都知道了，c 和 d 比较小可以直接爆破了，一共刚好也是 2^19bit。

 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


a = 363445
b = 494934
ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31
def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)
f=open("data","r")
S=f.read()
S=S[:100]#为了提高一点效率，可以先从小的开始尝试，找不到合适的就改一改
​
def bruteforce():
    global a,b
    for c in range(4096, 8192):
        for d in range(32, 64):
            cnt=0
            a_tmp,b_tmp,c_tmp,d_tmp=a,b,c,d
            for i in S:
                a_tmp = lfsr(a_tmp, ma)
                b_tmp = lfsr(b_tmp, mb)
                c_tmp = lfsr(c_tmp, mc)
                d_tmp = lfsr(d_tmp, md)
                [ao, bo, co, do] = [t & 1 for t in [a_tmp, b_tmp, c_tmp, d_tmp]]
                if int(i)==(bo*ao) ^ (bo*co) ^ (bo*do) ^ co ^ do:
                    cnt+=1
            if cnt/len(S)==1:#这里可以要求的很严格了，当然要100%满足
                print(c)
                print(d)
                return
bruteforce()

得到 d=4406，c=63。

a = 363445, b = 494934, c = 4406, d = 63 转换hex拼接得到flag：De1CTF{58bb578d5611363f}

easyRSA

task.py

 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


from Crypto.Util.number import *
import gmpy2
import random
from FLAG import flag

def genE(lcm,limit):
    while True:
        r = random.randint(limit,limit*0x1000000000001)
        d = gmpy2.next_prime(r)
        e = gmpy2.invert(d,lcm)
        if isPrime(e):
            break
    return e

p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
lcm = gmpy2.lcm(p-1,q-1)
limit = gmpy2.iroot(n,3)[0]

e1,d1 = genE(lcm,limit)
e2,d2 = genE(lcm,limit)

phi = (p-1)*(q-1)
d1 = gmpy2.invert(e1,phi)
d2 = gmpy2.invert(e2,phi)

e = [e1,e2]
plain = bytes_to_long(flag)
cipher = pow(plain,e[random.getrandbits(1)],n)

print('N:' + str(n))
print('e1:' + str(e1))
print('e2:' + str(e2))
print('cipher:' + str(cipher))

D^3CTF有一道和这题类似的题目，wp也很详细……

https://gist.github.com/LurkNoi/dfe86ed4d16776242251318b380336e7

构造好的矩阵竟然可以直接拿来用，直接LLL就可以解出来d1，d2….

由于我们不知道 genE() 中 d 的具体的 bit_length，在 d 的范围数量级内进行枚举。

exp.sage:

 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


n= 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1= 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2= 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723

m1 = n^(1/2)
m1 = int(m1)

def GCD(a,b):
    if a%b == 0:
        return b
    else:
        return GCD(b,a%b)

def autoflag(t):
    m2= n^(1+t)
    m2 = int(m2)
    print(t)

    B2 = matrix([[1,-n,  0, n**2],
                [0,e1,-e1,-e1*n],
                [0, 0, e2,-e2*n],
                [0, 0,  0,e1*e2]])

    D2 = matrix([[n, 0, 0,0],
                [0,m1, 0,0],
                [0, 0,m2,0],
                [0, 0, 0,1]])

    M = B2*D2 # k1k2, k2d1, k1d2, d1d2

    for vec in M.LLL()[:1]:
        b1,b2,b3,b4 = vec
        x2 = Matrix([[b1,b2,b3,b4]])*M.inverse()
        a,b,c,d = x2[0]
        print(GCD(b,d))
        print(GCD(c,d))
    print("DONE")

t=0.3334
while t<0.3570:#0.3334-0.3569
    t+=0.0001
    autoflag(t)
#0.3550
#13055886542241324849606848300654111050213895018931668525112390666717463659828011236495055020349316934910897599568907550458905937640534150366439142917379092077356477487038001707677114834324987975339711919914028174834026692
#10524758552977623950522576266095598971604066598976786723316565384341562423375977453510267182029447059155214674557556041512997808420285719007717780425013978916702926738382048840861185251222579340831080549153967201958081132

exp.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from Crypto.Util.number import *

n= 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1= 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2= 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723
c= 5089249888618459947548074759524589606478578815336059949176718157024022678024841758856813241335191315643869492784030633661717346809979076682611760035885176766380484743187692409876479000444892361744552075578050587677106211969169204446554196613453202059517114911102484740265052582801216204900709316109336061861758409342194372241877343837978525533125320239702501424169171652846761028157198499078668564324989313965631396082388643288419557330802071756151476264735731881236024649655623821974147680672733406877428067299706347289297950375309050765330625591315867546015398294367460744885903257153104507066970239487158506328863

d1=13055886542241324849606848300654111050213895018931668525112390666717463659828011236495055020349316934910897599568907550458905937640534150366439142917379092077356477487038001707677114834324987975339711919914028174834026692
d2=10524758552977623950522576266095598971604066598976786723316565384341562423375977453510267182029447059155214674557556041512997808420285719007717780425013978916702926738382048840861185251222579340831080549153967201958081132
d1=d1//4
d2=d2//4

m=pow(c,d1,n)
print(long_to_bytes(m))

flag：De1CTF{4ef5e5b2-c169-47e2-b90e-9421c56f2f5e}

感觉自己菜爆了…自闭比赛，做的时间最长的一题ECDH最终还是没弄出来，一直感觉是Invalid Curve Attack，因为服务器端没有检测发送的点是否在开始的那条椭圆曲线上。赛后发现，在选取 bi 的时候，n%p==0 没有加上 ==0 ……

ECDH

拿来代码可以看到我们可以向服务器发送一个点 Gi (Exchange)，然后可以为我们加密一段 msg (Encrypt)，返回给我们 secret*Gi 合并 x y 后与 msg 异或的结果，我们收到这个结果再与 msg 异或一下然后分离 x y 就可以得到点 secret*Gi 了。我们的目的是得到并向服务器发送 secret 的值，就能得到 flag 啦。

简化一下：发送点 Gi，得到点 secret*Gi，计算 secret 并发送，得到 flag。 $$ E:y^2=x^3+Ax+B $$

注意到计算 secret*Gi 的 mul() 和 add() 函数并没有用到椭圆曲线 $E$ 的参数 B，也没有检查 Gi 是否为 E(A,B,q) 上的点。所以我们可以构造 E'(A,Bi,q)，然后发送曲线 $E'$ 上的点 Gi，所以程序在计算 secret*Gi 的时候，它以为是在E上计算，其实被骗了，是在 $E'$ 上计算。发送多组Gi最终可以得到足够的数据通过剩余定理合并，得到secret，这种攻击就是 Invalid Curve Attack。

Invalid Curve Attack

Local Preparation

随机选取 Bi，并计算此时的 $E'$ 的阶 $n$，判断$n$是否能被一个小素数 qi 整除，如果可以就保留 Bi，qi。
在 $E'$ 上找一个随机点 $H$ ,并计算 $Gi=(n'/q)H$ ，检查 Gi 是否为无穷远点就可以了，是的话重新选这个随机点 $H$ ，不是就把这个 Gi 保存。
这样就得到了一组 (bi, qi, Gi)，不断重复一二两步，直到所有的 qi 之积大于 $q^2$ 就退出循环。

Online Attack：

发送点 Gi ，得到程序返回的 secret*Gi
在 $(0,qi)$ 范围内枚举 ti ，使其满足 ti*Gi == secret*Gi ，计算 $t_i^2\ mod\ q_i$，这时有 $secret^2 = t_i^2\ mod\ q_i$。
重复上面两步，发送完所有的 Gi，保存到了所有的 $t_i^2\ mod\ q_i$。然后用剩余定理合并所有的 $t_i^2$，得到 $t^2$ 也就是 $secret^2$，开平方根就得到了 secret。

Writeup

在计算参数列表 Bi，qi，Gi 的时候，要注意到程序最多只能和我们交互 90 次，交互两次才能完成发送Gi和加密msg，所以 qi 的个数需要小于 45 ，最好给 qi 定一个不太小的下限（我的是5000），以保证 qi 个数较少。我先生成一个 5000 之后1000 个素数的列表作为 qi 可选的空间。

本地计算参数列表的脚本：

 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
82
83
84
85
86


from random import randint
from gmpy2 import sqrt,invert,mpz

sieve_base=[5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 
5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 
6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 
7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 
8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 
9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249]

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
zero = (0,0)
F=FiniteField(q)
def f(b,x):
    return (pow(x,3,q) + a*x + b) % q

def add(p1,p2):
    if p1 == zero:
        return p2
    if p2 == zero:
        return p1
    (p1x,p1y),(p2x,p2y) = p1,p2
    if p1x == p2x and (p1y != p2y or p1y == 0):
        return zero
    if p1x == p2x:#p1y == p2y and p1y != 0 and p2y != 0
        tmp = (3 * p1x * p1x + a) * invert(mpz(2 * p1y) , mpz(q)) % q
    else:
        tmp = (p2y - p1y) * invert(mpz(p2x - p1x) , mpz(q)) % q
    x = (tmp * tmp - p1x - p2x) % q
    y = (tmp * (p1x - x) - p1y) % q
    return (int(x),int(y))

def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
	    if n & 1 == 1:
	        r = add(r,tmp)
	    n, tmp = n >> 1, add(tmp,tmp)
	return r

def Offline_Precomputations():
    prime_list = [sieve_base[i] for i in range(1000)]

    Gi_list = []
    qlist = []
    bi_list=[]
    qi_product = 1
    bi=1
    while(qi_product < q*q):
        bi += 1
        E=EllipticCurve(F,[a,bi])
        n = E.order()
        print(n)

        find_a_small_factor = False
        for i in range(1000):
            if n % prime_list[i]==0 and prime_list[i] not in qlist:
                print("find a small factor")
                find_a_small_factor = True
                qi_product *= prime_list[i]
                qlist.append(prime_list[i])
                bi_list.append(bi)
                print(qlist)
                break
        if not find_a_small_factor:
            continue

        H=E.random_point()
        inf=H-H
        while True:
            G = H*int(n/qlist[-1])
            if G==inf:
                H=E.random_point()
            else:
                break
        print("find!")
        print(G)
        Gi_list.append((G[0],G[1]))
    print(bi_list)
    print(qlist)
    print(Gi_list)


Offline_Precomputations()

上面的脚本大约5分钟就可以算完。输出的三个参数列表存在一个文件里：

1
2
3


bi = [4, 9, 26, 28, 30, 32, 34, 40, 41, 48, 73, 86, 111, 112, 117, 119, 129, 132, 136, 141, 161, 165, 174, 188, 197, 203, 206, 213, 214, 220, 238, 242, 275, 276, 279, 291, 299, 303, 322, 336]
qi = [5657, 10903, 8191, 12157, 6073, 9241, 10687, 12893, 6719, 13859, 8117, 10301, 13099, 5527, 8737, 10631, 5107, 5693, 6079, 10657, 5927, 6113, 7873, 6217, 11047, 12113, 5147, 9103, 11057, 5923, 7027, 5717, 10501, 13063, 9127, 10133, 5477, 5471, 13421, 13759]
Gi = [(30872500276756167396951474090124654304794923360667192467226675667448229681665, 83322930424192373524322173116603156345074046542792982303484797472143217961368), (14142904415645449119907336377416481926864703912427562730055735074219145549101, 63849575435191102844140385926897263301061935266189659881317580955016050734189), (40969882994648530081916876655161985963830665410329660538461272172469167125728, 64454878682771462004362411962366300840173052580225189911399858039534581888077), (82877418346404951750675480072867011998991569892157974398985334984663117854149, 50978626336645847463851041692845664756477024069940277266625847972958761358368), (24746817534136625356292362813181235589280973302944023820185154275643462413727, 35639977980669594960678433763010741945515185245445353404428172737631739386899), (47282371694648556570679118847655449358963795004556531118348527180031145177969, 59966019181805023632948187657492552643801632478184881090936975601106229146410), (60712030606261917519568264199639402100574447377118122922524413101203741263120, 17176385919318377183171082088625527451825035445063657268915215986521393888340), (9027327243716998211781862199426408307326022952644379162790068878797188141818, 61009803152391976811447442545097299173436840401745624638955569832237555829473), (92251054066253126334428165182631564129665870611725669183888213682798259095972, 37074010565672199367874176622919563060597398699989235438216793443482295287409), (69695373440573629766708856342663276081186838699125800152765630981947711052121, 48178899944132882283599919400524668308064902957209651369122200378268323952425), (75102389801455858956597493216399156984694788514035038175249758211883103626870, 3412785211107654591249094160052537680385541044296766274185340746624483729733), (59866676681443934667114838077713240838957123181519735125754606765849866097347, 8805439985411086835249824924575402161831279521146603579645222384004542285519), (12347621918708465606908238516379113916518065052190877557445387463476295403583, 51928978269977560591638042857241338407310718393549367181739959706805873995534), (73062544334117217418276419902996007214091231775581805844308159628155628211807, 55784571416852533002117425486589483198762732580845853891284112905769938188897), (44682682941088257636486520064393268330678693434401068570127680280728944744998, 28173971913162137009249858457142752453546282574869173219057002120131181452593), (34242130021719570117253003762778941164580411253476500654240946260487756864086, 26766153725875538986947107451673755197819092915585191972024061524601120879860), (90422336812399003145559066044427724490604468992899648595340676974027580958703, 80165372718141463422545565405008761999799501548366301938489635724657401745713), (85140176786053085584193314208172740416786705738102554549989875569197541552264, 75358833217208468040762514687496665850414066877171064073115458896807483076615), (94771825545395933071508776706118073614882175454078396622630715974723704155151, 4745535117825351976526807256991485492783614974043324040684972741775042815990), (100171525035097286097545492976792764465735962531594898393076116754456861358755, 53705979238119204251739160477914836172776252121476309657209714496275276427389), (29971095349578324382901593694826617004225871191689145192858680308549101683404, 57184898779794807742616054554045038792327449405632903218800390085959225225204), (55407687548794482628601357728242040226311193190028208583744883161144062368296, 33314617302527601701593772443278423878871997724393245022228170147527022751718), (32239990110815338831999530368651186051237902011177167660513454938097407801162, 671602395501769727771718955063041871367596087541253612345325738676335116280), (3917571690569088369262203391165226228446787670578414099634000210229258526360, 70634026931612954431222806160218359603337677957192750882837663783030579509624), (2207035926055248213529107319579032297141765794563906833591403890711440160113, 31331709971636821775115781873059884810730455527131288709744391474355953219901), (3932808658713491006509410084406394244966049429248145722157725209819345215434, 85142630046436265508647141294265284061206772024019380851950823942517231823894), (1539521617181156915158018487872776183950574207896802451837845170244377427387, 24449866531527118897857255763228849849561887485160194129175253493403448504125), (75002212857098569438403863439809398015781294312789119873167994247755527333762, 87002220226810953045826905675716400420036092226734517178134089426254171587715), (92010592279557832306039829536051295550204502236267688784472039931587463456035, 58613481301723072528738357273612194677387937582367011948647990512041392950153), (83393344736952817655018385178901587930844106489134650611100773558042073140443, 30300689939783331476278918304361371781367897595104621620522420376841330066554), (91078061094403429716572485362499716404082941862048489035495641570495237378110, 40971255337503044023637629176353045221129744187378119183810433410253577683959), (16985546008320601827759048065524362704024280157173465715933238635277424622056, 22696940558362620242678088324333793057494067258280802605002237508630082994109), (19170284381687584388622601167478242887418206491615217123996130596733428386742, 75748545718743128162585628787582641365201763301552227607403853384807587009859), (26473683045754776494164819126676658456171602164787921730420301045177016736609, 4281911904902758858355404226807051591134777088628269518372910631801533181905), (53676622464735659552656571188215866927322104668956095743777971851020661674358, 32274152263769486066368214670965452735712224610879606790658391470777079972556), (17029079575716446729702735874302371314145352046618367406530611486482710572360, 69357146029376150656652047840232370865246341002948175613826165204918209020338), (34727300648324783340958409739006112355711035230437824170066703947960201976886, 1587307801581137361413368586082506549606770098958439500002828849164565562848), (20877893922423278084054972379788392567821904480521987253174872716560062157784, 6715702336736936301726721938396211844295333186474291987353293376813588111160), (31562274556840802328980745172266502601827082447947556734372585420455740249090, 34305476342176933832701449433075719459820433000960976107182392312648682867355), (19690328408555852060974020099573760475212244087504943265526342735564565974214, 85979847994448727599368990309145050030837733437134982952836810810966647646533)]

有了参数列表就可以干服务器上的程序了：

  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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169


import string
from LIST import qi, Gi
from pwn import remote
from hashlib import sha256
from gmpy2 import invert, iroot
from functools import reduce
msg = "80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8
zero = (0, 0)

def proof_of_work(txt, Hash):
    S = string.ascii_letters+string.digits
    for a in S:
        for b in S:
            for c in S:
                for d in S:
                    if sha256((a+b+c+d+txt).encode()).hexdigest() == Hash:
                        print(a+b+c+d)
                        return a+b+c+d


def add(p1, p2):
    if p1 == zero:
        return p2
    if p2 == zero:
        return p1
    (p1x, p1y), (p2x, p2y) = p1, p2
    if p1x == p2x and (p1y != p2y or p1y == 0):
        return zero
    if p1x == p2x:  # p1y == p2y and p1y != 0 and p2y != 0
        tmp = (3 * p1x * p1x + a) * invert(2 * p1y, q) % q
    else:
        tmp = (p2y - p1y) * invert(p2x - p1x, q) % q
    x = (tmp * tmp - p1x - p2x) % q
    y = (tmp * (p1x - x) - p1y) % q
    return (int(x), int(y))


def mul(n, p):
    r = zero
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r


def CRT(m, a):
    Num = len(m)
    M = reduce(lambda x, y: x*y, m)
    Mi = [M//i for i in m]
    t = [invert(Mi[i], m[i]) for i in range(Num)]
    x = 0
    for i in range(Num):
        x += a[i]*t[i]*Mi[i]
    return x % M


def stringToPoint(p):
    i = 0
    while p[i] != ',':
        i += 1
    return (int(p[1:i]), int(p[i+1:-1]))


def exchange(xi, yi):
    tmp = r.recvline()
    print(tmp)

    tmp = r.recvline()
    print(tmp)
    r.send(str(xi)+"\n")
    print(xi)

    tmp = r.recvline()
    print(tmp)
    r.send(str(yi)+"\n")
    print(yi)

    tmp = r.recvline()
    print(tmp)
    tmp = r.recvline()
    print(tmp)


def encrypt(msg):
    tmp = r.recvline()
    print(tmp)
    r.send(str(msg)+'\n')
    tmp=r.recvline()
    print(tmp)
    res = int(r.recvline().strip().decode(),16)
    print(res)
    res ^= int(msg,16)
    print("res =", hex(res))
    tmp = r.recvline()
    print(tmp)
    return res


def keysToPoint(res):
    res = bin(res)[2:]
    y = int(res[-256:], 2)
    x = int(res, 2)>>256
    return (x, y)


def getPoint(xi, yi, msg):
    r.send("Exchange\n")
    exchange(xi, yi)
    r.send("Encrypt\n")
    res = encrypt(msg)
    return keysToPoint(res)


# proof_of_work
r = remote('134.175.225.42', 8848)
r.recvuntil("XXXX+")
nonce = r.recv(16).decode()
r.recvuntil(" == ")
target = r.recv(64).decode()
w = proof_of_work(nonce, target)
r.send(str(w))
print("----------proof of work is ok!----------")
# Start_work
r.recvuntil("q: ")
q = int(r.recvline().strip().decode())
r.recvuntil("a: ")
a = int(r.recvline().strip().decode())
r.recvuntil("b: ")
b = int(r.recvline().strip().decode())
r.recvuntil("P: ")
P = stringToPoint(r.recvline().strip().decode())
r.recvuntil("Q: ")
Q = stringToPoint(r.recvline().strip().decode())
print("q :", q, "\na :", hex(a), "\nb :", hex(b), "\nP :", P, "\nQ :", Q)

exchange(1, 1)
qlen = len(Gi)
t = []
for i in range(len(qi)):
    print("--------------------{}th".format(i))
    X=getPoint(Gi[i][0],Gi[i][1],msg)
    ti=0
    for j in range(qi[i]):
        if mul(j,(Gi[i][0],Gi[i][1]))==X:
            ti=j
            t.append((ti*ti)%qi[i])
            break
    print("ti :",ti)

print(t)
ans = CRT(qi, t)
secret = iroot(ans, 2)[0]
print(secret)
if mul(secret,P)==Q:
    print("checked")

r.send("Backdoor\n")
tmp = r.recvline()
print(tmp)
r.send(str(secret)+"\n")
temp1 = r.recvline()
print(temp1)
temp2 = r.recvline()
print(temp2)