常见形式
维尔斯特拉斯曲线:
椭圆曲线的一般形式可表示为:
E:y^2 = x^3 + A*x + B
A,B属于Fp,4A^3 + 27B^2 != 0,一般称上式为维尔斯特拉斯形式的椭圆曲线方程.
蒙哥马利曲线:
蒙哥马利形式的椭圆曲线方程定义为:
Kt^2 = s^3 + Js^2 + s
其中K,J属于Fp,B(A^2 - 4) != 0。
扭曲爱德华曲线:
扭曲爱德华形式的椭圆曲线方程定义为:
av^2 + w^2 = 1 + dv2*w2
其中a,d != 0,a != d。
椭圆曲线间的转换:
维尔斯特拉斯曲线、蒙哥马利曲线、扭曲爱德华曲线这三类椭圆曲线之间可以相互转换。
蒙哥马利曲线 <-> 维尔斯特拉斯曲线
任何椭圆曲线都可以写为维尔斯特拉斯形式。反之,当满足特定条件时,维尔斯特拉斯椭圆曲线可以转换为蒙哥马利椭圆曲线。具体转换条件参见《Montgomery Curve![屏幕截图 2023-08-27 224205](F:\资料\crypto文本\ECC\屏幕截图 2023-08-27 224205.png)》的Equivalence with Weierstrass curves部分。
扭曲爱德华曲线 <-> 蒙哥马利曲线
所有扭曲爱德华曲线都与蒙哥马利曲线双向有理等价(Birationally Equivalent),反之亦然。所谓双向有理等价,可以理解为除了个别点外,扭曲爱德华曲线的点和蒙哥马利曲线的点存在相互映射关系。
![屏幕截图 2023-08-27 224113](F:\资料\crypto文本\ECC\屏幕截图 2023-08-27 224113.png)
2022 NCTF spurecc
题目:
# 题目
from Crypto.Util.number import *
from secrets import INF, flag
assert flag[:5] == b'nctf{'
class super_ecc:
def __init__(self):
self.a =73101304688827564515346974949973801514688319206271902046500036921488731301311
self.c =78293161515104296317366169782119919020288033620228629011270781387408756505563
self.d =37207943854782934242920295594440274620695938273948375125575487686242348905415
self.p =101194790049284589034264952247851014979689350430642214419992564316981817280629
def add(self, P, Q):
(x1, y1) = P
(x2, y2) = Q
x3 = (x1 * y2 + y1 * x2) * inverse(self.c * (1 +self.d * x1 * x2 * y1 * y2), self.p) % self.p
y3 = (y1 * y2 - self.a * x1 * x2) * inverse(self.c* (1 - self.d * x1 * x2 * y1 * y2), self.p) % self.p
return (x3, y3)
def mul(self, x, P):
Q = INF
x = x % self.p
while x > 0:
if x % 2 == 1:
Q = self.add(Q, P)
P = self.add(P, P)
x = x >> 1
return Q
flag = bytes_to_long(flag[5:-1])
ecc = super_ecc()
G =(30539694658216287049186009602647603628954716157157860526895528661673536165645,64972626416868540980868991814580825204126662282378873382506584276702563849986)
S = ecc.mul(flag, G)
print(S)
#(98194560294138607903211673286210561363390596541458961277934545796708736630623,58504021112693314176230785309962217759011765879155504422231569879170659690008)
wp:
from Crypto.Util.number import *
import gmpy2
def Twist_Edwards_to_Montgomery(a,d,G,p):
A = (2*(a+d))*inverse_mod(a-d,p) % p
B = 4 * inverse_mod(a-d,p) % p
u = (1+G[1]) * inverse_mod(1-G[1],p) % p
v = ((1+G[1]) * inverse_mod((1-G[1])*G[0], p)) % p
return(A,B,(u,v))
def Twist_Montgomery_to_Weierstrass(A,B,G,p):
t = ((3 * G[0] + A) * inverse_mod(3*B, p))%p
v = (G[1] * inverse_mod(B, p))%p
a = ((3-A^2) * inverse_mod(3*B^2, p))%p
b = ((2*A^3-9*A) * inverse_mod(27*B^3, p))%p
return (a,b,(t,v))
a = 73101304688827564515346974949973801514688319206271902046500036921488731301311
c = 78293161515104296317366169782119919020288033620228629011270781387408756505563
d = 37207943854782934242920295594440274620695938273948375125575487686242348905415
p = 101194790049284589034264952247851014979689350430642214419992564316981817280629
G = (30539694658216287049186009602647603628954716157157860526895528661673536165645,64972626416868540980868991814580825204126662282378873382506584276702563849986)
Q = (98194560294138607903211673286210561363390596541458961277934545796708736630623,58504021112693314176230785309962217759011765879155504422231569879170659690008)
G_ = (G[0]*inverse_mod(c,p)%p,G[1]*inverse_mod(c,p)%p)
Q_ = (Q[0]*inverse_mod(c,p)%p,Q[1]*inverse_mod(c,p)%p)
d_ = d * c^4
A_,B_,G1 = Twist_Edwards_to_Montgomery(a,d_,G_,p)
a_,b_,G1 = Twist_Montgomery_to_Weierstrass(A_,B_,G1,p)
A,B,Q1 = Twist_Edwards_to_Montgomery(a, d_, Q_, p)
a_1,b_1,Q1 = Twist_Montgomery_to_Weierstrass(A, B, Q1, p)
# print(G1,a_,b_)
E = EllipticCurve(GF(p),[a_,b_])
G1 = E(G1)
Q1 = E(Q1)
print(G1,Q1)
x = G1.order()
print(factor(G1.order())[:-2])
fac_,rc = [],[]
for i,j in factor(x)[:-2]:
print(i,j)
fac = int(i)^int(j)
# print(fac)
k = int(x) // fac
# print(k)
fac_.append(fac)
dis = discrete_log(k*Q1,k*G1,operation = "+")
rc.append(dis)
print(fac_,rc)
print("_____")
m = crt(rc,fac_)
print(m)
m = 1558115275100082829946
from Crypto.Util.number import*
print(long_to_bytes(m))