NLFSR
task.py
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的状态分成两类：
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。
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 的同或值（相同为真，相异为假）相等。
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^19bits。
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
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:
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
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可选的空间。
本地计算参数列表的脚本：
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分钟就可以算完。输出的三个参数列表存在一个文件里：
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)]
有了参数列表就可以干服务器上的程序了：
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)