三种常见椭圆曲线变换

常见形式

维尔斯特拉斯曲线：

椭圆曲线的一般形式可表示为：

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 + dv^2*w2

其中a,d != 0,a != d。

椭圆曲线间的转换：

维尔斯特拉斯曲线、蒙哥马利曲线、扭曲爱德华曲线这三类椭圆曲线之间可以相互转换。

蒙哥马利曲线 <-> 维尔斯特拉斯曲线

任何椭圆曲线都可以写为维尔斯特拉斯形式。反之，当满足特定条件时，维尔斯特拉斯椭圆曲线可以转换为蒙哥马利椭圆曲线。具体转换条件参见《Montgomery Curve》的Equivalence with Weierstrass curves部分。

扭曲爱德华曲线 <-> 蒙哥马利曲线

所有扭曲爱德华曲线都与蒙哥马利曲线双向有理等价（Birationally Equivalent），反之亦然。所谓双向有理等价，可以理解为除了个别点外，扭曲爱德华曲线的点和蒙哥马利曲线的点存在相互映射关系。


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 =73101304688827564515346974949973801514688319206271902046500036921488731301311self.c =78293161515104296317366169782119919020288033620228629011270781387408756505563self.d =37207943854782934242920295594440274620695938273948375125575487686242348905415self.p =101194790049284589034264952247851014979689350430642214419992564316981817280629def add(self, P, Q):(x1, y1) = P(x2, y2) = Qx3 = (x1 * y2 + y1 * x2) * inverse(self.c * (1 +self.d * x1 * x2 * y1 * y2), self.p) % self.py3 = (y1 * y2 - self.a * x1 * x2) * inverse(self.c* (1 - self.d * x1 * x2 * y1 * y2), self.p) % self.preturn (x3, y3)def mul(self, x, P):Q = INFx = x % self.pwhile x > 0:if x % 2 == 1:Q = self.add(Q, P)P = self.add(P, P)x = x >> 1return 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 gmpy2def Twist_Edwards_to_Montgomery(a,d,G,p):A = (2*(a+d))*inverse_mod(a-d,p) % pB = 4 * inverse_mod(a-d,p) % pu = (1+G[1]) * inverse_mod(1-G[1],p) % pv = ((1+G[1]) * inverse_mod((1-G[1])*G[0], p)) % preturn(A,B,(u,v))
def Twist_Montgomery_to_Weierstrass(A,B,G,p):t = ((3 * G[0] + A) * inverse_mod(3*B, p))%pv = (G[1] * inverse_mod(B, p))%pa = ((3-A^2) * inverse_mod(3*B^2, p))%pb = ((2*A^3-9*A) * inverse_mod(27*B^3, p))%preturn (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^4A_,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))