皮蛋厂的学习日记 | 2022.9.18 w4n_y1ng|ECC椭圆曲线算法原理及题目解析

皮蛋厂的学习日记系列为山东警察学院网安社成员日常学习分享，希望能与大家共同学习、共同进步~

• 2021级 w4n_y1ng|ECC

• ECC

• 2022巅峰极客 point-power

2021级 w4n_y1ng|ECC

ECC

以前学ECDSA签名算法的时候了解过ECC的参数，这次深入了解有关ECC出题方面的一些算法，也能更好的理解，而且我

发现一般这种比较nb的算法，都是在sage中跑。。。

在有限域Fp中定义一个椭圆曲线，常用y2=x3+ax+b

而在Crypto中是一个个离散的点，那么就通过模运算来做到。最简单也是上面的式子，只不过是加上了模

y2=x3+ax+b mod p

而我们在sage中定义这个曲线一般是

E = EllipticCurve(GF(n), [0, 0, 0, a, b])

构造椭圆曲线

y**2+a1*xy+a3*y=x**3+a2*x**2+a4*x+a6

EllipticCurve([a1,a2,a3,a4,a6])

也就是我们平常所见到的最简单的

y2=x^3+ax+b

也就是前几个a赋值为0

在ECC中T=(p,a,b,G,n,h) 这是六个参数

我们先给出一个有限域Fp

有限域顾名思义就是有限个元素成为有限域。有限域元素的个数也就是有限域的阶

也就是一般有限域就是取模，曲线上的点也就是离散的

Fp 中只有p个元素

选择两个满足下列条件的小于p(p为素数)的非负整数a、b

4a3+27b2≠0　(mod p)

这里的a b 就是小于 p 且在表达式中的 a b

这里的n就是G的阶 阶的计算是如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，(无穷点远)则将n称为P的 阶，若n不存在，我们说P是无限阶的。

事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在

下面，我们给出一个有限域Fp，这个域只有有限个元素。

Fp中只有p（p为素数）个元素0,1,2 …… p-2, p-1

p a b 也就是用来确定一条椭圆曲线

x,y为G基点的坐标

n为点G基点的阶

这里对阶的理解是有限域中元素的个数称为有限域中的阶而我们一般在ECC式子中的模数一般就是阶了

公私钥的生成

选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

确定私钥k，K的范围(1,n-1) 生成公钥 K

K=kG

加密

将Ep(a,b) 这里的a b也就是椭圆曲线中的参数和公钥K ，基点G传出。

用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M

并产生一个随机整数r，这里r的范围一样，都是(1,n-1)

得到密文

C1=M+rK

C2=rG

将密文注意这里的密文是一个点对(C1,C2)传出

解密

接到信息后，计算C1-kC2，

结果就是点M

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

再对点M进行解码就可以得到明文。

2021第五空间 ECC

print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
    p = 146808027458411567
    A = 46056180
    B = 2316783294673
    E = EllipticCurve(GF(p),[A,B])
    P = E.random_point() 
    Q = num*P
    print E
    print 'P:',P
    print 'Q:',Q

def ECC2(num):
    p = 1256438680873352167711863680253958927079458741172412327087203
    #import random
    #A = random.randrange(389718923781273978681723687163812)
    #B = random.randrange(816378675675716537126387613131232121431231)
    A = 377999945830334462584412960368612
    B = 604811648267717218711247799143415167229480
    E = EllipticCurve(GF(p),[A,B])
    P = E.random_point() 
    Q = num*P
    print E
    print 'P:',P
    print 'Q:',Q
    factors, exponents = zip(*factor(E.order()))
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
    print primes
    dlogs = []
    for fac in primes:
        t = int(int(P.order()) / int(fac))
        dlog = discrete_log(t*Q,t*P,operation="+")
        dlogs += [dlog]
        print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
    print num
    print crt(dlogs,primes)
def ECC3(num):
    p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
    A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
    B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
    E = EllipticCurve(GF(p),[A,B])
    P = E.random_point() 
    Q = num*P
    print E
    print 'P:',P
    print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)

首先看代码就是定义了三个函数也就是三个部分flag分别在三个函数之中

那我们一个一个部分来看

(1)简单的离散对数

第一步我们直接离散对数求出num

p = 146808027458411567
A = 46056180
B = 2316783294673
E = EllipticCurve(GF(p), [A, B])
P=E(119851377153561800,50725039619018388)
Q=E(22306318711744209,111808951703508717)
P.discrete_log(Q)

13566003730592612

我这里P.order 求的是阶

(2)Pohlig-Hellman

应该是个板子了直接用即可

p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P=E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q=E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print(primes)
dlogs = []
for fac in primes:
    t = int(int(P.order()) // int(fac))
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
print(crt(dlogs,primes))

#[2, 27, 5, 7, 212117, 302426983]
factor: 2, Discrete Log: 1
factor: 27, Discrete Log: 10
factor: 5, Discrete Log: 4
factor: 7, Discrete Log: 6
factor: 212117, Discrete Log: 126450
factor: 302426983, Discrete Log: 211578426
16093767336603949

我们分解一下具体的步骤首先分解一下P的阶

按照我们前面所讲的，首先求得P的阶，然后将其分解，这点sage都可以直接帮我们完成

p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P=E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q=E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
P.order()
factor(P.order())

2 * 3^3 * 5 * 7 * 212117 * 302426983 * 10362951863095936421891634612647340060175499

模数 prime 素数

dlogs 余数

然后任务其实就是求分解后对应的阶下也就是P0对应的li了，这个我们也可以用sage里的discrete_log函数来直接完成得到dlos 这里的含义是余数 ，那我们得到模数和余数了 中国剩余定理不久能求出来了吗 在sage里面还定义了crt

中国剩余定理根本不需要我们再def了 直接用即可

sage中的crt直接就是中国剩余定理，比Python的简单多

print(crt([1,2,3,4],[11,3,5,7]))

exponents 指数 幂

p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P=E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q=E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print(primes)
dlogs = []
for fac in primes:
    t = int(int(P.order()) // int(fac))
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
print(crt(dlogs,primes))

p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p), [A, B])
P = E(550637390822762334900354060650869238926454800955557622817950, 700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830, 819973744403969324837069647827669815566569448190043645544592)
n = E.order()
plist = [2,5,7,27,212117,302426983]
klist = []
for p in plist:
    P1 = (n // p) * P
    Q1 = (n // p) * Q
    klist.append(discrete_log(Q1,P1,operation="+")) 
print(klist)
crt(klist, plist)

不要用最后一个数值t太大算不出来

基本都是// 整除

p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P=E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q=E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
primes=[2, 27, 35, 212117, 302426983 ]
dlogs=[]
for fac in primes:
    t=int(P.order()) // int(fac)
    dlog=discrete_log(t*Q,t*P, operation="+")
    dlogs+=[dlog]
    print(dlogs)
crt(dlogs,primes)

终于在改正n遍的脚本下得到了答案

这里 P.order 和E.order 效果一样

factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]

(2, 3, 5, 7, 212117, 302426983, 10362951863095936421891634612647340060175499)

(1, 3, 1, 1, 1, 1, 1)

2 * 3^3 * 5 * 7 * 212117 * 302426983 * 10362951863095936421891634612647340060175499

正常是这种然后分开了，然后又和上了。。。感觉没必要

for i in zip(*zipobj):
    print(i)

原理有点难…

(3)smart's attack

还是先看定义的这第三个函数

def ECC3(num):
    p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
    A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
    B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
    E = EllipticCurve(GF(p),[A,B])
    P = E.random_point() 
    Q = num*P
    print E
    print 'P:',P
    print 'Q:',Q

看上去和上面的一样其实还是不同的 最明显的区别就是数变大了很多，不能直接用离散对数的求法直接求出来，这里是要用到了smart’s attack

阶数与p相等

这里在sage中直接P.order可以求出来P的阶 这时候我们发现P的阶和p相等，那就有意思了

我们这里搬运一下前面的定义就能知道了

如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，则将n称为P的 阶，若n不存在，我们说P是无限阶的。

事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在 ，h 是椭圆曲线上所有点的个数m与n相除的整数部分

这个smart's attack攻击github上有代码，我们直接修改数据即可

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)
n=SmartAttack(P,Q,p)
assert(n*P==Q)
print(n)

19597596255129283097357413993866074145935170485891892

把三段数据整合

13566003730592612 16093767336603949 19597596255129283097357413993866074145935170485891892

三段还不能放在一起求

from Crypto.Util.number import *
a=13566003730592612
b=16093767336603949
c=19597596255129283097357413993866074145935170485891892
print(long_to_bytes(a)+long_to_bytes(b)+long_to_bytes(c))

b'025ab3d9-2521-4a81-9957-8c3381622434'

运算法则：任意取椭圆曲线上两点A、B （做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。我们规定A+B=R。

此处+不是简单的实数相加，是抽象出来的

O∞+P=P
O∞为零元
曲线上三个点A,B,C处于一条直线上，则A+B+C=O∞

这时候会有一种特殊情况

这时候就是做出来的就是一条经过P点的切线

2022巅峰极客 point-power

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

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

这题有个G=2*G，很像一个二倍点的问题

那我们先确定一下椭圆曲线方程

y2=x3+ax+b (mod p)

首先由二倍点

(x1,y1)=2(x2,y2)

y1^3=x1^3+aX1+b

y2^3=x2^3+aX2+b

这里由于是A和B相等的特殊情况那么就好算很多了

k=(3x1^2+a) /2y1

x2=-2x1+k^2

这个化简就很简单了

x2=k^2-2x1

k^2=x2+2x1

k*2y1=3x1^2+a

k^2*4y1^2=(3x1^2+a)^2

y1和k我们都能表示出来，那么就能化简出来了

4(x1^3＋ax1+b)(2x1+x2)^2-(3x1^2＋a)^2=0

联立解方程即可

这里学习一下sage的同余运算

R.<x> = Zmod(module)[]

相当于将x xx作为需要求得的未知数

Zmod()内填入同余运算的模数

f = x^3 + ...

将同余运算的所有项移到同一边，赋值给函数f来表示

f.roots()

需要求解

n^2≡p^3+a∗p^2+b∗p(mod moudle)

将同余式项全部移到一边

0≡p^3+a∗p^2+-n^2(mod moudle)

其中a , b , m o u d l e , n 已知

需要求解p那么在sage中

R.<p> = Zmod(moudle)   
f = p^3 + a*p^2 + b*p - n^2 
f.roots()

那么p的所有满足该同余式的解就会返回出来

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
PR.<a> = Zmod(p)[]
k = x2+2*x1
y1 = x1^3+a*x1+b
y2 = x2^3+a*x2+b
f = 4*k*y1-(3*x1*x1+a)^2
ans = f.roots()
print(ans)

在sage中我们跑出来后，再在Python中爆破

from Crypto.Util.number import *

ans=[(918875439627055594259552478508551728381826199399685938622511660790511287097297184191298481453657480331998130281110691444641445094194011219176724349745237973925436007792522611119050, 1), (56006392793430010663016642098239513811260175999551893260401436587175373756825079518464264729364083325, 1)]
for i in res:
    if b'flag' in long_to_bytes(int(i[0])):
        print(long_to_bytes(int(i[0])))

b'flag{fa76cfb1-0052-4416-914d-91517bcebd52}'