首页 CRYPTO

学了快两年 ctf 了 还是没入 ECC 的门┗|｀O′|┛ 嗷～～

# ECC

椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。与传统的基于大质数因子分解困难性的加密方法不同，
ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域
有以素数为模的整数域 GF (p) 和特征为 2 的伽罗华域 GF (2m2^m)。

# 有限椭圆曲线

椭圆曲线是连续的，并不适合用于加密，所以必须把椭圆曲线变成离散的点，把椭圆曲线定义在有限域上。

有限域上的椭圆曲线是指在椭圆曲线的定义式中，所有的系数都是在某个有限域 GF (p) 中的元素，其中 p 为一个大素数。

给出一个有限域 Fp，
1.Fp 中有 p（p 为质数）个元素 0,1,2,⋯,p−1;

2.Fp 的加法是 a+b≡c (modp);

3.Fp 的乘法是 a×b≡c (modp);

4.Fp 的除法是 ab≡c (modp)，即 a×b−1≡c(modp)a×b^−1≡c(modp)，b−1b^−1 为 b 的逆元，满足 b×b−1≡1(modp)b×b^−1≡1(modp);

5.Fp 的单位元是 1，零元是 O;

6.Fp 域内运算满足交换律、结合律、分配率。

椭圆曲线 Ep (a,b)

p 为质数，x,y∈[0,p−1]：y2=x3+ax+b(modp)y^2=x^3+ax+b(modp)，

选择两个满足下列约束条件的小于 p 的非负整数 a,b：4a3+27b2≠0(modp)4a^3+27b^2≠0(modp)。

Fp 上的椭圆曲线同样有加法：

无穷远点 O 是零元，有 O+O=O，O+P=P；

P (x,y) 的负元是 (x,−ymodp)=(x,p−y)，有 P+(−P)=O；

P(x1x_1,y1y_1),Q(x2x_2,y2y_2) 的和 R (x3x_3,y3y_3) 有如下关系：

x3≡k2−x1−x2(modp)x_3≡k^2−x_1−x_2(modp)

y3≡k(x1−x3)−y1(modp)y_3≡k(x_1−x_3)−y_1(modp)

若 P=Q 则k=3x12+a2y1(modpk=3x^2_1+a_2y_1(modp);

若 P≠Q 则 k=y2−y1x2−x1(modp)k=y_2−y_1x_2−x_1(modp)。

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

  • 加密原理
    考虑 K=kG ，其中 K,G 为椭圆曲线 Ep (a,b) 上的点，n 为 G 的阶（nG=O），k 为小于 n 的整数。

给定 k 和 G ，根据加法法则，计算 K 很容易，但反过来，给定 K 和 G，求 k 就非常困难。因为实际使用中的 ECC 原则上把 p 取得相当大，n 也相当大，要把 n 个解点逐一算出来列成上表是不可能的。

这就是椭圆曲线加密算法的数学依据。

点 G 称为基点 (base point)，k (k<n) 为私有密钥 (private key)，K 为公开密钥 (public key)。

  • 通信算法

1.Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37

2.Alice选择一个私有密钥p（p<n），并生成公开密钥K=pG 比如25, K= pG = 25G = (14,6）

3.Alice将E和点K、G传给Bob

4.Bob收到信息后，将待传输的明文编码到上的一点M（编码方法略），并产生一个随机整数r（r<n,n为G的阶数） 假设r=6 要加密的信息为3,因为M也要在E29(4,20) 所以M=(3,28)

5.Bob计算点C1=M+rK和C2=rG C1= M+6K = (3,28)+6*(14,6)=(3,28)+(27,27)=(6,12) C2= 6G =(5,7)

6.Bob将C1、C2传给Alice

7.Alice收到信息后，计算C1-kC2，结果就应该是点M C1-kC2 =(6,12)-25C2 =(6,12)-25*6G =(6,12)-2G =(6,12)-(27,27) =(6,12)+(27,2) =(3,28)

C1-kC2=M+rK-krG=M+rkG-krG=M

#Sage
a = 
b = 
p = 
#EllipticCurve([a1, a2, a3, a4, a6]) -- y^2+(a1)xy+(a3)y=x^3+(a2)x^2+(a4)x+(a6)
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
base = E([, ])
pub = E([, ])
c1 = E([, ])
c2 = E([, ])
X = base
#Bruteforce secret k
for i in range(1, n):
    if X == pub:
        k = i
        print("[+] secret k = ", i)
        break
    else:
        X = X + base
m = c2 - (c1 * k)
print("[+] x = ", m[0])
print("[+] y = ", m[1])
print("[+] x+y = ", m[0] + m[1])
# 常见攻击
  • Smart’s attack
适用情况：E.order ()=p。
p = 
A = 
B = 
E = EllipticCurve(GF(p),[A,B])
P = E(,)
Q = E(,)
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)
r = SmartAttack(P, Q, p)
print(r)
  • ECDLP
ECDLP 即椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem）。
椭圆曲线上离散对数问题 ECDLP 定义如下：给定素数 p 和椭圆曲线 E，对 Q=kP，在已知 P,Q 的情况下求出小于 p 的正整数 k。可以证明由 k 和 P 计算 Q 比较容易，而由 Q 和 P 计算 k 则比较困难。
将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，将椭圆曲线中的乘法运算与离散对数中的模幂运算相对应，我们就可以建立基于椭圆曲线的对应的密码体制。
#Sage Code 1
p = 
a = 
b = 
E = EllipticCurve(GF(p),[a,b])
P = E(, ) 
Q = E(, ) 
k = discrete_log(Q, P, operation='+') 
print(k)
#Sage Code 2
p = 
a = 
b = 
E = EllipticCurve(GF(p),[a,b])
P = E(, ) 
Q = E(, ) 
k = P.discrete_log(Q)
print(k)
  • Pohlig-Hellman 算法
整数域中 $$y=g^x mod p$$ 里的 xx 以及椭圆曲线离散对数问题中 GK=Q 的 G 的阶 n，这样就把对应的离散对数问题转移到了每个因子条件下对应的离散对数，然后可以利用中国剩余定理进行求解。
#Sage Code 1
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
l = crt(dlogs,primes)
print(l)
#Sage Code 2
p = 
a = 
b = 
gx = 
gy = 
px = 
py = 
E = EllipticCurve(GF(p), [a, b])
G = E(gx, gy)
n = E.order()
QA = E(px, py)
factors = list(factor(n))
m = 1
moduli = []
remainders = []
print(f"[+] Running Pohlig Hellman")
print(factors)
for i, j in factors:
    if i > 10**9:
        print(i)
        break
    mod = i**j
    g2 = G*(n//mod)
    q2 = QA*(n//mod)
    r = discrete_log(q2, g2, operation='+')
    remainders.append(r)
    moduli.append(mod)
    m *= mod
r = crt(remainders, moduli)
print(r)
# 例题
第五空间 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)
求 num1 就是 ECDLP
求 num2 是 Pohlig-Hellman 算法
求 num3 是 Smart’s attack
easy~