0%

2023-N1CTF-junior-wp-crypto

很硬的题目,尝试复现一下。

ezezez

题目:

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
import os
from Crypto.Util.number import *
from secret import flag

flag = flag + os.urandom(512 // 8 - len(flag) - 10)

m = bytes_to_long(flag)
magic = bytes_to_long(b'N1Junior_CheckIn')
e = 24

while True:
p = getPrime(256)
if (p-1) % e == 0:
break
q = getPrime(256)
n=p*q

gx = [Zmod(n)(m)^e, Zmod(n)(magic), Zmod(n)(m+magic)^e]

a = getPrime(128)
b = getPrime(128)
Ep = EllipticCurve(GF(p),[a,b])
Eq = EllipticCurve(GF(q),[a,b])

gy = []
for x in gx:
Gp = Ep.lift_x(x)
Gq = Eq.lift_x(x)
y = crt([int(Gp[1]),int(Gq[1])],[p,q])
gy.append(y)

print(f'a = {a}')
print(f'n = {n}')
print(f'gy = {gy}')


"""
a = 259416965926853287275013962386631097709
n = 8963244108103857378610478915798540027754205184635651624801332901515870452435977078824267979279218575027152343028911705254378598817260939339516835322386427
gy = [1896722249337161391193797083807118705857637064141055866260977430130447249097804719101078827699386498665026965515554644281163046869672493999194358926022865, 1971472878970365404484102034878792535366624572891039926216530789642810299559238977732710681752685090332485586910206690093655977703795335533365202958013518, 4074555112002157403114317690671003025383051142150876016519408756236925988856478235258960189636836867363451314784889114354880607055705753428890566240606935]
"""

题目流程如下:

  • 生成素数p、q,取其乘积为n
  • 生成素数a、b,并用a、b生成两条曲线如下:
  • 在这两个曲线上分别取三个点,并crt得到在如下曲线上的三个点的坐标:
  • 其中三个点的横坐标分别是:
  • 给出a、n以及三个点在模n曲线下的纵坐标,要求求出m

首先要明白的一点是为什么一定要在模p、q下的曲线先求出纵坐标再crt起来,这是因为n是两个大素数组成的难以分解的合数,因此在模n下的二次剩余是难以求解的,所以才必须在模p、q下分别求出后再crt。

但是对于解出m来说很容易,因为椭圆曲线本质上来说就是关于x、y的多项式,并且所有y值都给了的情况下,就只剩下关于三个横坐标的方程。而虽然本题没有给b,但是由于magic为已知量,所以求出b不是问题。

但是实际上不求b也完全可行,因为两两作差就能消去b。我们将点一、二作差,点二、三作差,就得到如下两个方程:

而这两个方程有公共根m,因此求gcd或者用groebner应该都行,我这里直接用groebner。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

a = 259416965926853287275013962386631097709
n = 8963244108103857378610478915798540027754205184635651624801332901515870452435977078824267979279218575027152343028911705254378598817260939339516835322386427
gy = [1896722249337161391193797083807118705857637064141055866260977430130447249097804719101078827699386498665026965515554644281163046869672493999194358926022865, 1971472878970365404484102034878792535366624572891039926216530789642810299559238977732710681752685090332485586910206690093655977703795335533365202958013518, 4074555112002157403114317690671003025383051142150876016519408756236925988856478235258960189636836867363451314784889114354880607055705753428890566240606935]
e = 24
t = bytes_to_long(b'N1Junior_CheckIn')

PR.<m,magic> = PolynomialRing(Zmod(n))
f1 = (m^e)^3 + a*(m^e) - magic^3 - a*magic - gy[0]^2 + gy[1]^2
f2 = ((m+magic)^e)^3 + a*(m+magic)^e - magic^3 - a*magic - gy[2]^2 + gy[1]^2
f3 = magic - t
res = Ideal([f1,f2,f3]).groebner_basis()
print(res)

flag = n - 8963244108103857378610473916499685337958102994866002007958751917348709988813159260063838668865808163331396353132849773965877550546775678652844675901977223
print(long_to_bytes(flag))

#secpunk{baby_crypt000_checkin}



fastmix

题目:

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
from Crypto.Util.number import *
from secret import flag

assert len(flag) == 48
gift = b'yX~\xe1\xd3\xe7\xcdw_)/G\xdc\x0er\x18\xc0\xb2\xc1sKv\xd4\x857\x94D\xf91\xc2\x98\x873\x8bG\xc3hG\xbbC\x98\x16e\xe8\x11C\n\x04'
block_size = 16
date = bytes_to_long(b'2023-1-31 10:00')
f1 = lambda x: (x << 1) ^ 0b110100011 if x & 0x80 else x << 1
f2 = lambda x: x ^ f1(f1(x))
f3 = lambda x: f1(f1(f1(x))) ^ f1(f1(x))


def slow_func(init, time):
tmp = init
for _ in range(time):
tmp = sum([[
f3(tmp[j]) ^ f2(tmp[j+1]) ^ f2(tmp[j+2]) ^ f1(tmp[j+3]),
f1(tmp[j]) ^ f3(tmp[j+1]) ^ f1(tmp[j+2]) ^ f2(tmp[j+3]),
f3(tmp[j]) ^ f2(tmp[j+1]) ^ f3(tmp[j+2]) ^ f2(tmp[j+3]),
f2(tmp[j]) ^ f1(tmp[j+1]) ^ f2(tmp[j+2]) ^ f3(tmp[j+3])
] for j in range(0, 16, 4)], [])
return bytes(tmp)


v = b''
for i in range(0, len(flag), block_size):
block = gift[i:i+block_size]
v += slow_func(block, date)

assert flag == v

speedup类型的题目,只要跑完这个程序就能拿到flag。但是由于有:

1
for _ in range(time):

这个语句,而time是:

1
date = bytes_to_long(b'2023-1-31 10:00')

所以直接跑是没办法的,需要加速。而加速主要需要关注的就是如下部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
f1 = lambda x: (x << 1) ^ 0b110100011 if x & 0x80 else x << 1
f2 = lambda x: x ^ f1(f1(x))
f3 = lambda x: f1(f1(f1(x))) ^ f1(f1(x))


def slow_func(init, time):
tmp = init
for _ in range(time):
tmp = sum([[
f3(tmp[j]) ^ f2(tmp[j+1]) ^ f2(tmp[j+2]) ^ f1(tmp[j+3]),
f1(tmp[j]) ^ f3(tmp[j+1]) ^ f1(tmp[j+2]) ^ f2(tmp[j+3]),
f3(tmp[j]) ^ f2(tmp[j+1]) ^ f3(tmp[j+2]) ^ f2(tmp[j+3]),
f2(tmp[j]) ^ f1(tmp[j+1]) ^ f2(tmp[j+2]) ^ f3(tmp[j+3])
] for j in range(0, 16, 4)], [])
return bytes(tmp)

先看这三个lambda函数,其实对AES比较熟悉的话,会看出来这个与列混合那一步的有限域乘法很相似。而这题也就是换了个模多项式。具体来说,如果把x的8bit看作是模2下的多项式系数,那么x本身就可以看作是一个多项式,记为g(x)。那么f1、f2、f3就分别等价于:

f1是乘x很好想通,因为在这个GF(2^8)的域中,2就代表的是x。而f2、f3其实也就分别代表5和12对应的元素,也就是x^2 + 1和x^3+x^2。同时,所有运算都在下面的商环下进行:

那么之后的事也很简单,因为异或就是这个有限域中的加法,所以slow_func中的主要运算就可以看作是元素为多项式的矩阵乘法,比如对于第一次运算,就是如下过程:

其中si就是初始状态构成的向量,那么最终flag的运算结果就是:

而由于可以进行矩阵快速幂,所以就可以加速得到结果了。

exp:

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 *

gift = b'yX~\xe1\xd3\xe7\xcdw_)/G\xdc\x0er\x18\xc0\xb2\xc1sKv\xd4\x857\x94D\xf91\xc2\x98\x873\x8bG\xc3hG\xbbC\x98\x16e\xe8\x11C\n\x04'
block_size = 16
date = bytes_to_long(b'2023-1-31 10:00')

PR2.<a> = PolynomialRing(Zmod(2))
R2 = PR2.quotient(1+a+a^5+a^7+a^8,'x')

x_1 = R2([0,1]) #f1:*x
x_2 = R2([1,0,1]) #f2:*(x^2+1)
x_3 = R2([0,0,1,1]) #f3:*(x^3+x^2)

poly_matrix = Matrix(R2,[[x_3,x_2,x_2,x_1],
[x_1,x_3,x_1,x_2],
[x_3,x_2,x_3,x_2],
[x_2,x_1,x_2,x_3]])

def convert_to_vec(num):
temp = list(map(int,bin(num)[2:].zfill(8)[::-1]))
return R2(temp)

def fast_func(init,time):
for i in range(0, 16, 4):
tmp = vector(R2,list(map(convert_to_vec,[init[i],init[i+1],init[i+2],init[i+3]])))
final = (poly_matrix^(time))*tmp
for j in final:
temp = list(map(str,list(j)[::-1]))
print(chr(int("".join(temp),2)),end = "")

for i in range(0, len(gift), block_size):
block = gift[i:i+block_size]
fast_func(block, date)

#secpunk{checkin_but_@maz1ng_4lg3bra1c_5tructure}



n1lucky

这个题目Van1sh在公众号上写过好题分享,写的非常详细清楚,看那一篇就好了。



RealSignin

题目:

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
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)

def get_params(nbits):
p = getPrime(nbits)
q = getPrime(nbits // 2)
r = getPrime(nbits // 2)
if q < r:
q, r = r, q
e = 2023 + 666
n = p * q * r
phi = (p-1) * (q-1) * (r-1)
d = inverse(e, phi)
return e, n, d, p, q, r

def magic_process(dqr_):
# only the correct data can pass this magic process!
w = 11805048190103811318745740902058585490581588391715507077469771342521346595744141604699124341571677599846725074544467374849004088341619160922679491419964725
x = dqr_ + 666
y = dqr_ + 667
PR.<z> = PolynomialRing(ZZ)
f = w*(x*z+y*z-x*y) - 4*x*y*z
z = f.roots()[0][0]

assert w*(x*z+y*z-x*y) - 4*x*y*z == 0

e, n, d, p, q, r = get_params(512)

dqr = d % ((q-1) * (r-1))
dqr_ = (dqr >> 55) << 55
magic_process(dqr_)

print(f'e = {e}')
print(f'qr = {q % r}')
print(f'n = {n}')
print(f'c = {pow(m, e, n)}')

'''
e = 2689
qr = 47039394845246457267451844933135300719863788804596821520575305333413876649846
n = 102275105641047314957681561255971730180031931453885390971560104545784846810054168298038033889926837832908913447331571300831232278972182034546312860462560455575699889259884894407503661740178853200384106267596198200388045685183747251883536380886761864997738495990864526497955511125021398766971363828732464588761
c = 30057873321817268990724095993213394773233077509126537130493293224220768053789109305889627009912877888765075963369699610910695123551381348483962929764830148523075698671087735427795008522625385598116705013490990766089416767372146754468746664865469005120853463146265400060202176870467493380590559736303051981581
'''

题目先生成RSA的几个密钥相关量,n由三个素数p、q、r组成,其中p是512bit的素数,q、r分别为256bit且q>r,e为2689。

然后题目先计算出一个量:

然后抹去他的低55位,得到dqr’,然后用这个值构造x、y如下:

然后给出一个方程:

并且仅给出w的值。此外,题目还给了我们q%r的值qr,以及公钥n和flag密文c,要求还原明文。

理一下解题思路,首先肯定要知道dqr’的值,才有后续利用copper解出dqr、进而求出n的完整分解的机会。所以当务之急就是解决下面这个不定方程:

并且还知道一个信息是:

然后我这里的第一个思路是,注意到magic中有一句注释是:

1
# only the correct data can pass this magic process!

所以我在想,这是不是说方程有且仅有一个解的意思,也就是说dqr’的唯一整数解刚好就在对称轴上。于是我把这个不定方程的y消去,变成如下的形式:

把x视作主元,得到的就是一个关于x的一元二次方程,而如果符合我们猜想的话,这个二次方程的判别式就该等于0,也就是:

但是这个方程没有整数解,所以并不是我们猜想的那样,因此需要另谋他法。我的第二个思路是把方程化成下面这个形式:

z应该是个很大的数,所以是不是代表着4/w的连分数展开可能会覆盖到x组成的这个分数?但是遗憾的是也没有成功,应该是不满足勒让德理论。

之后我问了zima师傅,知道有原题目可以参考:

Cyber Apocalypse CTF 2021 Part 1 | CryptoHack Blog

大致思路就是说,首先把原不定方程化成如下形式(其实就是第二种思路中,不代入y=x+1):

接下来的步骤就有点想象力了,因为w是奇数,所以左边可以拆成:

所以就得到了符合要求的解。

然后这里我也有问yolbby师傅,他说他是类比成埃及分数做,我之前并不知道这个东西就去查了一下。埃及分数其实也就是分子为1的分数,那么之所以能类比,应该也是上面那个化简形式的存在:

然后对应的办法就是深搜迭代,但是由于数字很大,所以我自己瞎搜索了一下,没有实现出来这种办法。有兴趣的师傅可以自己试一试。

解出这个不定方程的之后就有dqr’,而为了得到完整的dqr,很显然需要copper解出其低55位。为此我们记这低55位为delta,构造下面这个方程:

展开成等式就有:

这里就和dq泄漏的思路类似(其实本质上来说没区别),注意到k肯定小于e,而e又仅有2689,因此遍历1到e一定存在一个正确的k。而我们又有q模r的值,并且知道q和r都是256bit,所以一定有:

那么代入上面那个式子:

展开:

那么在模r下就有:

然后理论上来说就可以在模n下用copper求解出delta的值了。不过有一些小问题:

  • r是256bit的因子并且比q小,因此beta最多就取到0.25
  • beta取0.25的话,epsilon即使取到0.01,根的上界也就只有50出头,达不到要求,可能还要爆破几位

但是首先epsilon取0.01就很慢了,再爆破几位更慢,而且最外层还要爆破k,更更慢。最主要的是,我电脑还没换,这破电脑没有装flatter啊!

然后想到了一点点优化,就是刚才这个式子里:

应该是转化到模q下求解小根的话,由于有q>r,所以beta能稍微大一点,也许根的上界可以略有提升?因此我构造出如下的多项式:

然后还有一点就是,由于d肯定是奇数,模一个偶数也不改变奇偶性,所以LSB肯定是1,所以还能减小1bit。不过除此之外确实没想到其他优化了,就硬来吧。要是有flatter就好了,换了电脑一定马上装。

爆了差不多一个半小时出了结果(也算是运气不错,完整的爆估计要8个小时,装flatter还是很必要)。有了完整的dqr过后就可以用刚才的方程求根得到q、r,就有了n的完整分解,然后解密就好了。

exp:

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
from Crypto.Util.number import *
from tqdm import *

e = 2689
qr = 47039394845246457267451844933135300719863788804596821520575305333413876649846
n = 102275105641047314957681561255971730180031931453885390971560104545784846810054168298038033889926837832908913447331571300831232278972182034546312860462560455575699889259884894407503661740178853200384106267596198200388045685183747251883536380886761864997738495990864526497955511125021398766971363828732464588761
c = 30057873321817268990724095993213394773233077509126537130493293224220768053789109305889627009912877888765075963369699610910695123551381348483962929764830148523075698671087735427795008522625385598116705013490990766089416767372146754468746664865469005120853463146265400060202176870467493380590559736303051981581

#part1 get dqr_
w = 11805048190103811318745740902058585490581588391715507077469771342521346595744141604699124341571677599846725074544467374849004088341619160922679491419964725
k = (w-1)//2
x = k
y = k+1
z = k*(k+1)*(2*k+1)
assert w*(x*z+y*z-x*y) - 4*x*y*z == 0
dqr_ = x-666


#part2 get dqr(use copper)
if(0):
for tt in range(4):
for k in trange(1,e):
PR.<delta> = PolynomialRing(Zmod(n))
f = e*(dqr_+2^3*delta+2*tt+1) - 1 - k*(1+qr)
f = f.monic()
res = f.small_roots(X=2^52,beta=0.25,epsilon=0.01)
if(res != []):
print(tt,k,res) #0 2046 [2593202029823482]
break
dqr = dqr_ + 2^3*2593202029823482 + 2*0 + 1
k = 2046


#part3 factor n
if(0):
PR.<r> = PolynomialRing(ZZ)
f = e*dqr - 1 - k*(r+qr-1)*(r-1)
res = f.roots()
print(res)
r = 67643325987256775010724943844390543569531594444330008512848332012702093716653
q = r + qr
p = n // q // r


#part4 get flag
phi = (p-1)*(q-1)*(r-1)
d = inverse(e,phi)
flag = pow(c,d,n)
print(long_to_bytes(int(flag)))

#secpunk{reallyreallyreallyreally_ez_signin..}



errorcc

题目:

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
import random
from Crypto.Util.number import *
from secret import flag

assert flag[:8]==b'secpunk{' and flag[-1:]==b'}'
flag = flag[8:-1]
m = bytes_to_long(flag)

p = getPrime(200)
a = random.randint(0, p-1)

while True:
b = random.randint(0, p-1)
E = EllipticCurve(Zmod(p), [a, b])
if isPrime(E.order()):
break

Ga = E.gens()[0]
gift = bytes_to_long(b'N1CTF Junior')
random.seed(gift)

G = []
for i in range(80):
r = random.randint(0,p-1)
G.append(tuple((r ^^ m)*Ga)[:-1])

for i in range(60):
r = random.randint(0,p-1)
G.append(tuple((r & m)*Ga)[:-1])

for i in range(60):
r = random.randint(0,p-1)
G.append(tuple((r | m)*Ga)[:-1])

f = open('output.txt','w')
f.write("Ga = "+str(tuple(Ga)[:-1])+"\n")
f.write("G = "+str(G))

output有点长,就不放在这里,需要的师傅可以找我要。

题目流程也很清晰:

  • 首先把flag的头尾去了,然后转成大整数m
  • 生成随机的200bit素数p,以及小于p的随机数a
  • 然后爆破出一个b,使其生成的如下曲线的阶是素数:
  • 然后取曲线上的生成元Ga,并以一个已知的gift作为随机数的种子,之后分别给出:

80个:

60个:

60个:

以及Ga,要求还原m。

首先肯定是要还原出曲线参数,这一部分很容易,因为所有给出的点都是曲线上的点,所以不论是手写一个消元或者是直接取groebner都能获得全部参数。然后需要注意的一点是,由于随机数种子给了我们,所以所有ri都已知。

有了参数a、b、p后就能计算其order。看到题目里保证其阶为素数,确实幻想过阶恰好为p然后直接smart attack,或者阶满足mov attack之类,但是的确都不行。也就是说这个ECC上的DLP是没办法求的,只能想办法利用给出的这些点来恢复m。

这里我首先就想到N1CTF的e2D1p一题,因为实在是非常类似:

Crypto趣题-Lattice | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

类似在哪里呢?在那个题目中,有多组如下形式的等式:

并且给出每个等式的ci、ri。我们忽略掉那个题目恢复p的步骤,直接进入其恢复flag的第二步,也就是把p当作已知,那么对应于这个题目中的给了多组如下的点来说:

ci对应Gi,e对应Ga,mi对应ri,flag对应m,p对应order,完全可以一一对应。也就是说,似乎除了把离散对数形式从数构成的乘法群移到点构成的加法群,别的都没什么区别。

所以我就想到用一模一样的思路逐bit还原m,具体的就看那篇文章就好了。不过我就这么做没有做出来,因为所有那个形式的矩阵方程都无解。思考了一下,确实不应该直接这样就能出,毕竟后面的&和|给的足足120个点都还没有用到。

这题之后更新吧,暂时没什么思路了。

(2.1更新)

从zima师傅那里要到了一份这个题目的exp,然后看着代码理解了一下出题人的思路,豁然开朗。

先放他的exp:

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
import random
import time
from functools import reduce

f = open("output.txt",'r')
f.read(5)
Ga = eval(f.readline())
f.read(4)
G = eval(f.readline())

PR.<a,b> = PolynomialRing(ZZ)
polys = []

for i in range(4):
x, y = G[i]
polys.append(x*a+b+(x^3-y^2))

gb = Ideal(polys).groebner_basis()
p = gb[-1]
a = -gb[0].coefficients()[-1]%p
b = -gb[1].coefficients()[-1]%p

E=EllipticCurve(Zmod(p),[a, b])
Ga=E(Ga)

def xormat(r, P):
mask = 1
v = []
for i in range(200):
if r & mask == 0:
v.append(1)
else:
v.append(-1)
P = P-mask*Ga
mask = mask << 1
return v, P

def andmat(r, P):
mask = 1
v = []
for i in range(200):
if r & mask == 0:
v.append(0)
else:
v.append(1)
mask = mask << 1
return v, P

def ormat(r, P):
mask = 1
v = []
for i in range(200):
if r & mask == 0:
v.append(1)
else:
v.append(0)
P = P-mask*Ga
mask = mask << 1
return v, P

L = []
R = []
random.seed(int.from_bytes(b'N1CTF Junior', 'big'))

print("===construct matrix begin===")
start = time.time()
for i in range(80):
rn = random.randint(0,p-1)
Q = E(G[i])
v, P = xormat(rn, Q)
L.append(v)
R.append(P)

for i in range(80,140):
rn = random.randint(0,p-1)
Q = E(G[i])
v, P = andmat(rn, Q)
L.append(v)
R.append(P)

for i in range(140,200):
rn = random.randint(0,p-1)
Q = E(G[i])
v, P = ormat(rn, Q)
L.append(v)
R.append(P)
print("===construct matrix end===")
end = time.time()
print("cost {}s".format(end-start))

q = E.order()
L = Matrix(Zmod(q), L)
m = ''
O = 0*Ga
for i in range(200):
u = vector(Zmod(q),[0]*i+[1]+[0]*(199-i))
coeff = L.solve_left(u).change_ring(ZZ)
S = 0*Ga
for i in range(200):
S += coeff[i]*R[i]
if S == O:
m = '0'+m
else:
m = '1'+m

print(bytes.fromhex(hex(int(m, 2))[2:]))

接下来就是讲这样做的道理是什么。

xor

首先,由于给出的都是位运算,因此所有式子都可以写成对于各bit的操作形式,我们就以xor举例,对于其中的某个式子,他本来是写成:

我们把m看作是200个未知bit组成的量(也就是按位,把它看作是200个变量),那么这个式子可以写成:

这对于后面的&和|也是同理的,但是又为什么要这样写呢?我们用如下写法,让表达式更清晰一点:

这样写出来之后,式子由原来的一个普通点乘计算,变成了两百个独立的点乘计算,并在最后相加。注意这里刻意强调的每个点乘计算的独立性,因为每个bit之间是完全不会相互影响的。

而对于我们来说,我们有r的200个bit的值,这就又给这个式子增加了一些额外信息。由于r的每个bit只有0、1两个取值,所以我们分开讨论:

  • r的当前bit(rj)为0,那么:
  • r的当前bit(rj)为1,那么:

明白了这两点后,仍然是注意到200个bit彼此独立,我们就随便取其中一bit来分析一下

我们需要关注的是,m的这一bit的取值,对于最终得到G的贡献是什么。如果rj为0,那么由刚才的式子知道,这个点乘就是:

而重点在于rj=1的时候,这个点会变成:

这个怎么处理呢?其实因为mj也只有两个取值,所以也可以先分别写出mj的两种情况对应的点乘:

  • mj为0,则为:
  • mj为1,则为:

重要的一步来了,我们只需要配凑一个-1,就能把式子变成一个统一的含mj变量的形式:

如此一来,把rj为0和1分别对应的mj形成的表达式分别代入最初那个式子中,就可以将m的200bit写在一个更清晰的表达式里了:

这里举个简单的例子帮助理解,比如r的bit序列为(由低到高):

结合刚才的表达式代入这个式子里,就得到:

移项就得到:

此时,等式左边是一个已知的点,等式右边是仅有m的200bit组成的算式。这其实就是一个涉及m的200个bit的方程了。那么由xor,我们可以得到80组这样的方程。

and ,or

其实xor想明白了,这两个异曲同工。因为我们要做的事情,仍然是根据r的200个bit的值,列出仅含m的200个bit的方程。那么对于&来说:

这个就很简单,因为讨论rj的两种取值的话,显然rj为0整个式子乘数就取0,rj为1整个式子乘数就取mj,仍然是用刚才的(0,1,…,0,1)的r的bit序列举个例子,G就等于:

对于|来说,分别讨论rj的两种取值,rj为1时,整个式子乘数取1,为0时取mj,因此对于作为例子的(0,1,…,0,1)的r的bit序列,G为:

移一下项就变成需要的方程形式:

如此一来,and和or又各提供60个方程,我们就拥有了关于m的200个bit变量的200个方程。

利用上述方程

接下来的问题就变成,已知关于m的200个bit的200个方程,如何求解m。很自然地会想到先用矩阵方程把这个式子表示出来,就像下面这样:

其中,L矩阵中的每一行,就是我们刚才每一个方程中Ga前的系数构成的向量,因为有200个方程所以是200x200的矩阵;而P向量中的每个元素就是列出的方程左边的点。

注意到,虽然矩阵L、点Ga以及向量P都是已知的,但是可以看出,这并不是一个普通的矩阵方程,因为它涉及到椭圆曲线的点乘,并且曲线难以求解dlp,所以不好统一转化到生成元上,从而变成纯数域的计算。所以是没有办法直接解矩阵方程得到解向量m的。

不过bit by bit的思路依然可以用,我们第一次求解如下矩阵方程:

求出这个X向量的意义在于,我们把x代回刚才的式子里:

那么也就是:

也就是:

所以只需要等式右边的点是不是0*Ga就能判断m的当前bit是不是0.如此就可以逐bit还原m了。

exp:

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
from errorcc_output import *
import random
from Crypto.Util.number import *
from tqdm import *

#part1 groebner to get a,b,p
if(0):
PR.<a,b> = PolynomialRing(ZZ)
F = []
for i in range(4):
f = G[i][1]^2-G[i][0]^3-a*G[i][0]-b
F.append(f)
res = Ideal(F).groebner_basis()
print(res)
p = 1287829304049714244524067710692915105281415000125398093331471
a = p-225347669189365890161624438870935953357140181565885210886229
b = p-270712467434746420425713635322490969521436540014940033725570
E = EllipticCurve(Zmod(p),[a,b])
ord = E.order()
Ga = E(Ga)
for i in range(len(G)):
G[i] = E(G[i])


#part2 construct L
gift = bytes_to_long(b'N1CTF Junior')
random.seed(gift)
L = Matrix(Zmod(ord),200,200)
P = []

## 2.1 xor
for i in trange(80):
ri = random.randint(0,p-1)
temp = bin(ri)[2:].zfill(200)[::-1]
tempG = G[i]
for j in range(len(temp)):
if(temp[j] == "0"):
L[i,j] = 1
else:
L[i,j] = -1
tempG -= 2^j*Ga
P.append(tempG)

## 2.2 and
for i in trange(80,140):
ri = random.randint(0,p-1)
temp = bin(ri)[2:].zfill(200)[::-1]
tempG = G[i]
for j in range(len(temp)):
if(temp[j] == "0"):
L[i,j] = 0
else:
L[i,j] = 1
P.append(tempG)

## 2.3 or
for i in trange(140,200):
ri = random.randint(0,p-1)
temp = bin(ri)[2:].zfill(200)[::-1]
tempG = G[i]
for j in range(len(temp)):
if(temp[j] == "0"):
L[i,j] = 1
else:
L[i,j] = 0
tempG -= 2^j*Ga
P.append(tempG)


#part3 bit by bit to recover flag
flag = ""
O = 0*Ga
for i in trange(200):
u = vector(Zmod(ord),[0]*i + [1] + [0]*(199-i))
temp = L.solve_left(u)
S = O
for j in range(len(temp)):
S += int(temp[j])*P[j]
if(S == O):
flag += "0"
else:
flag += "1"
print(long_to_bytes(int(flag[::-1],2)))

#secpunk{f4ult_1nj3cti0n~p0werfu1!}

很巧妙的思路,类似的就可以把这个解法也拓展到N1CTF的e2dlp上,虽然都是bit by bit求但是还是有细微差别。