（九千七-星河襟）椭圆曲线加密（ECC, Elliptic Curve Cryptography）及其例题

椭圆曲线加密（ECC）是一种基于椭圆曲线数学的公钥加密技术。它提供了一种高效的加密方法，能够在较小的密钥长度下实现与传统加密算法（如RSA）相同的安全级别。以下是ECC的主要特点和工作原理的总结：

1. 基本概念

椭圆曲线：ECC使用的是定义在有限域上的椭圆曲线。一条标准的椭圆曲线方程可以表示为：

[ y^2 = x^3 + ax + b ]

其中，a和b是常数，并且满足条件 (4a^3 + 27b^2 \neq 0) 以确保曲线没有奇点。

有限域：ECC通常在有限域上进行运算，最常见的有限域是素数域 (GF§) 和二进制扩展域 (GF(2^m))。有限域中的运算结果总是有限的，这使得它们适合用于加密。

椭圆曲线点加法：ECC的核心操作是椭圆曲线上点的加法。给定两个点 (P) 和 (Q)，可以通过几何方法或代数公式计算出第三个点 (R = P + Q)。如果 (P = Q)，则称为点的倍乘，记作 (2P)。

标量乘法：ECC中最常用的操作是标量乘法，即给定一个点 (P) 和一个整数 (k)，计算 (kP)。这个操作相当于将点 (P) 加到自身 (k) 次。标量乘法是ECC中最重要的单向函数，难以通过已知的结果反推出原始的 (k)。

2. 安全性和效率

安全性：ECC的安全性基于椭圆曲线离散对数问题（ECDLP），即给定椭圆曲线上的两个点 (P) 和 (Q)，找到一个整数 (k) 使得 (Q = kP) 是非常困难的。ECDLP的难度使得ECC在较小的密钥长度下也能提供高强度的安全性。

效率：相比传统的RSA加密，ECC可以在更短的密钥长度下提供相同的安全级别。例如，160位的ECC密钥提供的安全性相当于1024位的RSA密钥。因此，ECC具有更高的计算效率和更低的存储需求，特别适合用于资源受限的环境（如移动设备、物联网设备等）。

3. 应用场景

密钥交换：ECC广泛应用于Diffie-Hellman密钥交换协议（ECDH），允许双方在不安全的通信信道上安全地协商共享密钥。

数字签名：ECC用于生成数字签名（ECDSA, Elliptic Curve Digital Signature Algorithm），广泛应用于SSL/TLS协议、区块链（如比特币）等领域。

加密：ECC可以用于加密消息（ECIES, Elliptic Curve Integrated Encryption Scheme），结合对称加密算法（如AES）来实现高效的安全通信。

4. 主要算法

ECDH（Elliptic Curve Diffie-Hellman）：用于密钥交换，允许两方在不安全的通信信道上安全地协商共享密钥。

ECDSA（Elliptic Curve Digital Signature Algorithm）：用于生成和验证数字签名，确保消息的完整性和不可否认性。

ECIES（Elliptic Curve Integrated Encryption Scheme）：用于加密消息，结合ECDH和对称加密算法（如AES）来实现高效的安全通信。

5. 优点

高安全性：ECC在较小的密钥长度下提供高强度的安全性，抗量子计算攻击的能力也比传统加密算法更强。

高效性：ECC的计算复杂度较低，适合用于资源受限的设备和高性能要求的应用场景。

灵活性：ECC支持多种有限域和曲线参数，可以根据具体需求选择合适的曲线和参数。

6. 缺点

实现复杂性：ECC的实现相对复杂，尤其是需要处理有限域上的运算和椭圆曲线点的加法。如果实现不当，可能会引入安全漏洞。

专利问题：某些特定的椭圆曲线和算法可能受到专利保护，使用时需要注意法律问题。不过，近年来许多常用的曲线（如NIST推荐的曲线）已经不再受专利限制。

侧信道攻击：ECC实现中可能存在侧信道攻击的风险，特别是当标量乘法的实现不够优化时。因此，实现时需要考虑防侧信道攻击的措施。

7. 常用椭圆曲线

NIST曲线：美国国家标准与技术研究院（NIST）推荐的一系列椭圆曲线，如P-256、P-384、P-521等。

Brainpool曲线：由Brainpool联盟提出的一系列椭圆曲线，旨在提供更高的安全性并避免专利问题

Edwards曲线：如Ed25519和Ed448，这些曲线具有更好的性能和安全性，广泛应用于现代加密协议中。

Montgomery曲线：如Curve25519，这类曲线在标量乘法方面具有高效的实现，广泛应用于Diffie-Hellman密钥交换。

8. 总结

ECC作为一种高效的公钥加密技术，已经在现代密码学中占据了重要地位。它通过较小的密钥长度提供了高强度的安全性，适用于各种应用场景，特别是在资源受限的环境中表现出色。尽管实现复杂性较高，但随着硬件和软件的不断进步，ECC的应用范围正在不断扩大。

CTF例题：

**[第五空间 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)

'''
Try to solve the 3 ECC
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)
'''

题目将flag分成了三份，我们一个个来求。

第一部分：

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
#Try to solve the 3 ECC
#Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
#P: (119851377153561800 : 50725039619018388 : 1)
#Q: (22306318711744209 : 111808951703508717 : 1)

数比较小，我们可以直接使用_discretelog()求出：

from Crypto.Util.number import *
p = 146808027458411567
a = 46056180
b = 2316783294673
E = EllipticCurve(GF(p),(a,b))
P = E(119851377153561800,50725039619018388)
Q = E(22306318711744209,111808951703508717)

num1 =  discrete_log(Q,P,operation = '+')

第二部分：

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)
==============
#Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
#P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
#Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============

题目中以及给出，让我们用_pohlighellman算法求

p = 1256438680873352167711863680253958927079458741172412327087203
a = 377999945830334462584412960368612
b = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[a,b])
P = E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592) 
# Q = k * P
n = E.order()

def Pohlig_Hellman(n,P,Q):
    factors, exponents = zip(*factor(n))
    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
    num2 = crt(dlogs,primes)
    return num2

num2 = Pohlig_Hellman(n,P,Q)

第三部分：

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

我们可以发现椭圆曲线阶数与p相等，用_smart’ sattack可以求出_

p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P = E(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q = E(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)

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)

num3 = SmartAttack(P, Q, p)

最后输出一下：

print(long_to_bytes(num1)+ long_to_bytes(num2)+ long_to_bytes(num3))

:::info
flag：NSSCTF{025ab3d9-2521-4a81-9957-8c3381622434}

:::

[2023愚人杯]ecc_mini

题目如下：

from Crypto.Util.number import *
from secret import flag
flag=bytes_to_long(flag)
a =getPrime(256)
b =getPrime(256)
p =getPrime(256)
m1=int(str(flag)[:5])-4585
m2=int(str(flag)[5:])
#EllipticCurve([a1, a2, a3, a4, a6]) -- y^2+(a1)xy+(a3)y=x^3+(a2)x^2+(a4)x+(a6)
E = EllipticCurve(GF(p), [a, b])
X=E.lift_x(m1)
Y=7*X
m = E.random_point()
G = E.random_point()
k = getPrime(256)
K = k * G
r = getPrime(256)
c1 = m + r * K
c2 = r * G
w2=m[0]*m2
print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"k = {k}")
print(f"E = {E}")
print(f'Y = {Y}')
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"w2 = {w2}")
'''
p = 71397796933602469825964946338224836258949974632540581233301840806613437378503
a = 106105288190268015217241182934677375171023341761047638573248022053052499733117
b = 76170541771321874396004434442157725545076211607587599314450304327736999807927
k = 58155941823118858940343657716409231510854647214870891375273032214774400828217
E = Elliptic Curve defined by y^2 = x^3 + 34707491256665545391276236596452538912073367128507057339946181246439062354614*x + 4772744837719404570039488103932889286126236975047018081148463521123562429424 over Finite Field of size 71397796933602469825964946338224836258949974632540581233301840806613437378503
Y = (33237936857741483513705672980652927705102229733798436323453609986072499230366 : 52619411226266177137991318059937693955038910547834999771526408984808553907338 : 1)
c1 = (37414446283406201193977113266234367761786780230360175925999700345196415953455 : 17037724145039910971426670298726906655653040365428438334942732090559637519851 : 1)
c2 = (60560423732267272277570046154733119097475794979191838027420415113112056962844 : 54372226143125971429691267751299496959531971082475860532181772357190222938465 : 1)
w2 = 16315249811700998894876359855091105114973337718373913477026230968747515636405
'''

flag被分成了两个部分，第一部分只有5个字节，代码第一部分给定Y，且Y=7X求X，由于椭圆曲线没有除法，所以不能直接除，不过由于参数很小，我们可以爆破：

p = 71397796933602469825964946338224836258949974632540581233301840806613437378503
a = 106105288190268015217241182934677375171023341761047638573248022053052499733117
b = 76170541771321874396004434442157725545076211607587599314450304327736999807927
k = 58155941823118858940343657716409231510854647214870891375273032214774400828217
w2 = 16315249811700998894876359855091105114973337718373913477026230968747515636405
#爆破m1
for i in range(10000, 99999):
    if i%1000 == 0:
        print('.')
    try:
        tmp = E.lift_x(i - 4585)
        ty = 7*tmp
        if ty == Y:
            print(i)
            break
    except:
        pass

求得m1 = 62428

m2我们已知k，c1，c2，w2，有m = c1 - k * c2， m2 = w2 * inverse(int(m[0]),p)%p

我们构造代码：

from Crypto.Util.number import inverse, long_to_bytes
p = 71397796933602469825964946338224836258949974632540581233301840806613437378503
a = 106105288190268015217241182934677375171023341761047638573248022053052499733117
b = 76170541771321874396004434442157725545076211607587599314450304327736999807927
k = 58155941823118858940343657716409231510854647214870891375273032214774400828217
c1 = (37414446283406201193977113266234367761786780230360175925999700345196415953455, 17037724145039910971426670298726906655653040365428438334942732090559637519851)
c2 = (60560423732267272277570046154733119097475794979191838027420415113112056962844, 54372226143125971429691267751299496959531971082475860532181772357190222938465)
w2 = 16315249811700998894876359855091105114973337718373913477026230968747515636405

E = EllipticCurve(GF(p), [a, b])

m1 = 62428
c1 = E(c1)
c2 = E(c2)
m = c1 - k * c2
m2 = w2 * inverse(int(m[0]), p) % p
print(m2)
print(long_to_bytes(int(str(m1) + str(m2))))