0xL4ugh的Private-Curve

发表于 更新于

拿了个一血，感觉这题也很不错，遂记录一下

题目：

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
from Crypto.Util.number import getPrime,bytes_to_long
from secret import flag, p,a,b

flag=bytes_to_long(flag)

E = EllipticCurve(GF(p), [a, b])
G = E.gens()[0]

P=G*flag
print('here is my 7 xs can u get my private key ?')
#print(P[0])
for i in range(7):
	PP=P+i*G
	print(PP[0])

'''
here is my 7 xs can u get my private key ?
127222731808447286384197097524849730324280912084690383123034174156693907296321941583008138816149304043198829099586978152639
540150767459876746741544981524050320567261340627105743010550795668800394677819357272612801849680099119164471834128771848184
378426912752589864658307848293724051252472266429208255456184007500868515338668653822829851730193370970777687937350186024739
114528622155057967694026934367142168000739167063266001591280862125480038107282641048998814104241182719055831758176542012114
322400405850331256663554456242498354334347017862265389196757152850674454034744292814021471167045908645361119988919752367867
496047308313146975448000924265615728665813401349451895964344399497579232646901690982051726266819379622021083585061713111901
339613985780778130822549050414603776860269549419836797423421156347303558845214120048926926114443864057942273222884788713615
'''

题目给出了椭圆曲线E:y2=x3+ax+bE:y^2=x^3+ax+b上的7个点QiQ_i的横坐标，且这7个点均满足$$Q_i=P+iG$$

我们可以将其改写成

Qi−Qi−1=P+iG−P−(i−1)G=GQ_i-Q_{i-1}=P+iG-P-(i-1)G=G

其中GG的横坐标可以表示为

Gx=k2−Qix−Qi−1xG_x = k^2 - {Q_i}_x - {Q_{i - 1} }_x

其中

k=Qiy−Qi−1yQix−Qi−1xk = \frac{ {Q_i}_y - {Q_{i-1} }_y} { {Q_i}_x-{Q_{i - 1} }_x}

又

y=x3+ax+by=x^3+ax+b

那么我们就可以把所有的yy转化成xx，即

Gx(Qix−Qi−1x)2+(Qix+Qi−1x)(Qix−Qi−1x)2−(Qix3+aQix+b)2−(Qi−1x3+aQi−1x+b)2=2QiyQi−1yG_x({Q_i}_x-{Q_{i-1} }_x)^2+({Q_i}_x+{Q_{i-1} }_x)({Q_i}_x-{Q_{i-1} }_x)^2-({Q_i}_x^3+a{Q_i}_x+b)^2-({Q_{i-1} }_x^3+a{Q_{i-1} }_x+b)^2=2{Q_i}_y{Q_{i-1} }_y

然后将此式子进行平方，我们就可以有多组仅包含a,b,pa,b,p的式子了，我们直接在利用Gröbner基即可解出来pp，然后在模pp下再次利用Gröbner基即可解出所有的参数

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

Q = [
    127222731808447286384197097524849730324280912084690383123034174156693907296321941583008138816149304043198829099586978152639,
    540150767459876746741544981524050320567261340627105743010550795668800394677819357272612801849680099119164471834128771848184,
    378426912752589864658307848293724051252472266429208255456184007500868515338668653822829851730193370970777687937350186024739,
    114528622155057967694026934367142168000739167063266001591280862125480038107282641048998814104241182719055831758176542012114,
    322400405850331256663554456242498354334347017862265389196757152850674454034744292814021471167045908645361119988919752367867,
    496047308313146975448000924265615728665813401349451895964344399497579232646901690982051726266819379622021083585061713111901,
    339613985780778130822549050414603776860269549419836797423421156347303558845214120048926926114443864057942273222884788713615,
]

def f():
    def y2(x,A,B):
        return x^3+A*x+B
    F=[]
    for i in range(5):
        f=xb*(Q[i+1]-Q[i])^2-y2(Q[i+1],A,B)-y2(Q[i],A,B)+(Q[i]+Q[i+1])*(Q[i+1]-Q[i])^2
        f=f^2-4*y2(Q[i+1],A,B)*y2(Q[i],A,B)
        F.append(f)
    Ideals=Ideal(F)
    I = Ideals.groebner_basis()

    res=[x.constant_coefficient() for x in I]
    return res
P.<xb,A,B>=PolynomialRing(ZZ)

res = f()
q = int(res[-1])
q = factor(q)[-1][0]
P.<xb,A,B>=PolynomialRing(Zmod(q))
res = f()
Gx,a,b=res
a = -a
b = -b
E = EllipticCurve(GF(q), [a, b])

得到EE之后，我们查看它的阶的因子

1
factor(E.order())

可以发现因子为

1
72227181939217 * 108661850383939 * 109941210688553 * 117077820297817 * 118416071094367 * 139218006249863 * 334433150059614707617624014507531496691

除了最后一个因子特别大，其它的都十分小，那么利用Pohlig-Hellman算法解出其在小因子下面的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PP = [E.lift_x(Q[i]) for i in range(3)]
P = PP[0]
G = PP[1]-P

primes = [109941210688553,117077820297817,118416071094367,72227181939217,108661850383939,139218006249863]
dlogs = []
for fac in primes:
    t = int(int(P.order()) // int(fac))
    dlog = (t*P).log(t*G)
    dlogs += [dlog]
    print('00')
l = crt(dlogs,primes)
print(l)
print(long_to_bytes(l))
# b'0xL4ugh{PREDICTING_GENERATOR_Paper}'