ECC smart attack 推导

考查ECC中的一类特殊攻击——smart attack，当椭圆曲线的阶等于p时，即
$$
E.order()\ =\ P
$$
椭圆曲线上的所有非零点可以构成一个循环群，简而言之，椭圆曲线上的所有点都是生成元。

例题：

# sage
from secrets import flag

p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
A = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
B = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
E = EllipticCurve(GF(p), [A, B])
P = E.random_point()
Q = flag * P

print(E)
print('P:', P)
print('Q:', Q)

# Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
# P: (5554022717099360648521077915206867958510713570728935648722513803012487951670103349974914076311463683401346041009548809409633656449393930718778345589173915 : 1266078318886560129287459416353113688542197996795961235340234481614474504159805769053978291478602425874624451558101353431723090978689270131228854203647770 : 1)
# Q: (2758577082514053081281256667519462531364634668223896872592517478354667723237248507295586566258918736939764700935831769480917509906899250634810284495146946 : 511778894973388402517121634149232729267586460552999583843974221520798491852352254441185282292648216492508999730064294835066451755699876682807265675847421 : 1)

我们知道，椭圆曲线是基于有限域上的离散对数问题，意味着 Q = flag * P 求flag是十分困难的

因此我们不妨看看椭圆曲线的阶为多少，

1 2	print(E.order() == p) #True

于是联想到了Smart attack

Smart attack的本质

Smart attack是一种利用椭圆曲线的同态性质和点的扩展域表示来破解密码

在椭圆曲线的同态结构中，我们将有限域提升为扩展域时，扩展域上的点提升

这时，我们在扩展域进行点操作，我们可以获得点的坐标比例

由于E.order() = p，所以椭圆曲线上的点构成一个循环群，所有点都可以表示为某个生成元的倍数

由于点乘的特殊性质，任意点P满足pP = O，其中O为无穷远点(单位元)，于是在p-进数域上计算p×P和p×Q后经过操作便可以求出k

接下来开始介绍：

我们知道P,Q均为椭圆曲线上的点，我们定义一个新的椭圆曲线
$$
E_{qp}\ =\ EllipticCurve(Q_p(p,2),[ZZ(t)+randint(0,p)*p\ \ for\ t\ \ in\ \ E.a_invariants()])
$$
接下来我们分别看看各部分的含义：

Q~p~(p,2)：该椭圆曲线域定义为2阶的p-进数域

E.a_invariants()：返回E.a_invariants()即椭圆曲线的Weierstrass形式的a-不变量

椭圆曲线方程 y^2^ = x^3^ + a~1~xy + a~2~x^2^ + a~3~y + a~4~x +

最后返回一个包含a-不变量的列表

ZZ(t)：ZZ表示整数环，ZZ(t)表示我们将不变量t转换为整数

randint(0,p) * p：生成一个随机整数(在0到p之间) * p

ZZ(t) + randint(0,p) * p ：将原始不变量加上一个p的倍数，得到新的不变量

经过一系列操作，我们实现定义了一个从有限域提升到p-进数域上的椭圆曲线
接着，我们需要将P点从原始的椭圆曲线提升到我们新的椭圆曲线之上，在新曲线上找到对应的P点
使用**Eqp.lift_x(ZZ(P.xy()[0]) , all=True )**在新的椭圆曲线上找到与原始曲线上点P的x坐标相对应的所有可能的点
在新的椭圆曲线上，找到x坐标为ZZ(P.xy()[0])的所有点，于是我们便得到了一个点的列表，定义为P_Qps
接着我们遍历所有P_Qps，如果其在有限域GF(p)上的y坐标与原始的点P的y坐标相等，我们便找到原始点P在新的椭圆曲线上对应的点P_Qp
同理，我们也可以找到Q的新点Q_Qp
接着，我们定义P的p倍点为p_times_P(其代表点P进行p次定义在椭圆曲线上的自加)
同理，p_times_Q = pQ_Qp
接着我们返回P,Q的p倍点的x,y坐标
我们定义
$$
\varphi(P)\ =\ -\frac{xP}{yP}\ ,\ \varphi(Q)\ =\ -\frac{xQ}{yQ}
$$
因为我们知道
$$
Q\ =\ kP
$$
我们不难推出
$$
p×Q\ =\ p×(kP)\ =\ k×(p×P)
$$
所以
$$
k\ =\ \frac{\varphi(Q)}{\varphi(P)}
$$

解密脚本如下：

p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
A = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
B = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
E = EllipticCurve(GF(p),[A,B])
P = E(5554022717099360648521077915206867958510713570728935648722513803012487951670103349974914076311463683401346041009548809409633656449393930718778345589173915,1266078318886560129287459416353113688542197996795961235340234481614474504159805769053978291478602425874624451558101353431723090978689270131228854203647770)
Q = E(2758577082514053081281256667519462531364634668223896872592517478354667723237248507295586566258918736939764700935831769480917509906899250634810284495146946,511778894973388402517121634149232729267586460552999583843974221520798491852352254441185282292648216492508999730064294835066451755699876682807265675847421)

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)(Q_Qp.xy()[1]) == Q.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)

flag = SmartAttack(P,Q,p)
print(long_to_bytes(flag))