Montgomery Eğrisi

Montgomery Eğrisi Peter L. Montgomery tarafından 1987'de tanımlanmış, klasik Weierstrass formundan farklı bir eliptik eğri formudur. Belirli hesaplamalar için ve özellikle farklı kriptografi uygulamalarında kullanılır.

Tanımı

Montgomery eğrisinin denklemi;${\textstyle {\frac {1}{4}}y^{2}=x^{3}+2,5x^{2}+x}$

K cismi üzerinde Montgomery egrisi, belirli A, B ∈ K değerleri için ve B(A² − 4) ≠ 0 eşitsizliği sağlanıyorken, aşağıdaki eşitsizlikle tanımlanır:

$M_{A,B}:By^{2}=x^{3}+Ax^{2}+x$

Bu eğri genellikle bir K sonlu cismi üzerinde tanımlı olur. (örnek olarak q elemanın oluşturduğu bir sonlu cisim, K = F_q) Bu sonlu cismin karakteristiği 2'den farklı ve A ∈ K ∖ {−2, 2}, B ∈ K ∖ {0}, olması gerektiğine dikkat edelim. Aynı zamanda A ve B için aynı kısıtlamalara sahip rasyoneller üzerinde de düşünülür.

Montgomery Aritmetiği

Bir eliptik eğri üzerinde noktaları arasında, nokta toplama ve nokta ikileme işlemleri gerçekleştirilebilmektedir. Nokta Toplama; $P,Q$ eliptik eğrisi üzerinde tanımlı iki nokta olmak üzere $R=P+Q$; olacak şekilde $R$ noktası bulmak işlemidir. Nokta İkileme ise $[2]P=P+P$ işlemidir. (Kullanılan işlemler hakkında detaylı bilgi için bkz; elliptic eğri grup kuralları (eng: the group law))

$P=(x,y)$ noktası Montgomery formundaki $By^{2}=x^{3}+Ax^{2}+x$ eliptik eğrisi üzerinde bir nokta olmak üzere, bu noktanın Montgomery koordinatları $P=(X:Z)$ Burada $P=(X:Z)$ projektif koordinatlardır. ($x=X/Z$ ve $Z\neq 0$).

Bir nokta için bu tür bir temsilin(dönüşümün) bilgi kaybettiğine dikkat edin: gerçekten $(x,y)$ ve $(x,-y)$ (afin noktalarının kullanımında bir ayrım gözetilmez çünkü her iki noktanın kullanımı da bize $(X:Z)$ sonucunu verecektir. Ancak, bu gösterim(dönüşüm) ile bir $P=(X:Z)$ noktanın n sayısı ile çarpılmasını elde etmek mümkündür; $[n]P=(X_{n}:Z_{n})$

Şimdi, iki nokta dikkate alalım; $P_{n}=[n]P=(X_{n}:Z_{n})$ ve $P_{m}=[m]P=(X_{m}:Z_{m})$:

Bu iki noktanın toplamları aşağıdaki şekilde ifade edilir;

$P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})$

bu toplamın koordinatları:

$X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}$

$Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}$

Eğer $m=n$ ise bu işlem "nokta ikileme" işlemine dönüşür; $[2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})$ Koordinatları ise aşağıdaki eşitsizliklerle belirlenir;

$4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}$

$X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}$

$Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))$

Yukarıdaki ilk işlemin(toplama işleminin) maliyeti: (3M+2S) (Burada M, tanımlı eliptik eğrideki herhangi iki elemanın çarpımını, S ise tanımlı cisimdeki bir elemanın karesini ifade ediyor)

İkinci işlemin(ikileme) maliyeti : 2M + 2S + 1D, (Burada D herhangi bir elemanın bir $(A+2)/4$ değeri seçilebilir.

Algoritma ve Örnek

Montgomery formunda bir eliptik eğrininin bir noktasının $P_{1}=(X_{1}:Z_{1})$ nokta ikilemesi, aşağıdaki algoritma ile gösterilebilir;

$Z_{1}=1$ varsayıldığı durumda bu implementasyonun maliyeti; 1 + 2 + *1 + 3add + 1*4. (Burada M gerekli çarpma işlemlerini, S ise kare alma işelemlerini, a ise A ile çarpma işlemlerini belirtir.)

$XX_{1}=X_{1}^{2}\,$

$X_{3}=(XX_{1}-1)^{2}\,$

$Z_{3}=4X_{1}(XX_{1}+aX_{1}+1)\,$

Örnek

Kabul edelim ki $P_{1}=(2,{\sqrt {3}})$ noktası, $2y^{2}=x^{3}-x^{2}+x$ eğrisi üzerinde bir nokta olsun. Koordinatları; $(X_{1}:Z_{1})$ ; $x_{1}=X_{1}/Z_{1}$, $P_{1}=(2:1)$ O halde:

$XX_{1}=X_{1}^{2}=4\,$

$X_{3}=(XX_{1}-1)^{2}=9\,$

$Z_{3}=4X_{1}(XX_{1}+AX_{1}+1)=24\,$

Sonuç olarak bulduğumuz nokta; $P_{3}=(X_{3}:Z_{3})=(9:24)$ dikkat edilirse, $P_{3}=2P_{1}$.

Nokta Toplama

$P_{1}=(x_{1},y_{1})$$P_{2}=(x_{2},y_{2})$ afin koordinatlarda Montgomery eğrisi $M_{A,B}$ üzerinde iki nokta olmak üzere, 

$P_{3}=P_{1}+P_{2}$ şeklinde belirlenen nokta geometrik olarak $M_{A,B}$ ile $P_{1}$ ve $P_{2}$ noktalarını birleştiren doğrunun kesimini ifade eden üçüncü bir noktadır. Bu noktanın koordinatları $(x_{3},y_{3})$ aşağıdaki şekilde belirlenir:

1) 2 boyutlu afin uzayda, $~y=lx+m$ doğrusunun $P_{1}$ ve $P_{2}$ noktalarından geçtiğini varsayalım.(bu varsayımdan yararlanarak),

$l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$ ve $m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}$; elde edilir.

2) Doğru ile $M_{A,B}$, eğri denklemindeki $~y$ değişkeni $~y=lx+m$ ile değiştirilirse aşağıdaki 3. dereceden denklem elde edilir:

$x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.$

Daha önce gözlemlenebildiği gibi, bu denklem $P_{1}$, $P_{2}$ ve $P_{3}$ noktalarının x koordinatlarına göre üç köke sahiptir. Öyleyse denklem;

$(x-x_{1})(x-x_{2})(x-x_{3})=0$ şeklinde yazılır.

3) Yukarıda verilen iki özdeş denklemin katsayılarının, özellikle de ikinci mertebeden olanın terimlerinin katsayılarının karşılaştırılmasıyla aşağıdaki denklem elde edilir:

$-x_{1}-x_{2}-x_{3}=A-Bl^{2}$.

Böylelikle,$x_{3}$ terimi $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ terimleri cinsinden aşağıdaki biçimde yazılabilir:

$x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.$

4) $P_{3}$ noktasının $~y$ koordinatını bulabilmek için, $x_{3}$ değerini  $~y=lx+m$ doğrusunda yerine koymak yeterlidir. Bunun doğrudan $P_{3}$ noktasını vermeyeceğine dikkat edin. Gerçekten, bu yöntemle, $R+P_{1}+P_{2}=P_{\infty }$,  sağlayan $~R$ noktasının koordinatları bulunur. Eğer  $P_{1}$ ve $P_{2}$ nokta ekleme işleminin sonuç noktasına ihtiyaç duyulursa, $R+P_{1}+P_{2}=P_{\infty }$ ancak ve ancak$-R=P_{1}+P_{2}$ olması durumunu göz önüne almak gereklidir. Bu yüzden, verilen $~R$ noktası için $~-R$ noktasını bulmak gereklidir. Bu işlem verilen $~R$ nin y koordinatının işaretini değiştirerek kolaylıkla yapılabilir. Başka bir deyişle, doğru denkleminde $x_{3}$ ün yerine konulmasıyla elde edilen $~y$ koordinatının işaretini değiştirmek yeterli olacaktır.

Öyleyse $P_{3}=(x_{3},y_{3})$ noktasının koordinatları,$P_{3}=P_{1}+P_{2}$ şunlardır:

$x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}={\frac {B(x_{2}y_{1}-x_{1}y_{2})^{2}}{x_{1}x_{2}(x_{2}-x_{1})^{2}}}$

$y_{3}={\frac {(2x_{1}+x_{2}+A)(y_{2}-y_{1})}{x_{2}-x_{1}}}-{\frac {B(y_{2}-y_{1})^{3}}{(x_{2}-x_{1})^{3}}}-y_{1}$

Nokta İkileme

 $M_{A,B}$ Montgomery Eğrisi üzerinde verilen bir $P_{1}$ noktası için, $[2]P_{1}$; Geometrik olarak eğri ile $P_{1}$'eğet olan doğru arasındaki kesişimi ifade eden üçüncü noktasını temsil eder;$P_{3}=2P_{1}$ sağlayan $P_{3}$ noktasının koordinatlarını bulabilmek için, 'nokta toplama' metodundakine benzer bir yol izlenir; ancak, bu durumda, y = lx + m  doğrusu $P_{1}$ eğrisine teğet olmalıdır. Bu yüzden, eğer $M_{A,B}:f(x,y)=0$ ile

$f(x,y)=x^{3}+Ax^{2}+x-By^{2},$

Doğrunun eğimini temsil eden l değeri aşağıdaki gibi verilir:

$l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}$

kapalı fonksiyon teoremi'ne göre yazılabilir.

Yani $l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}$ ve $P_{3}$, $P_{3}=2P_{1}$

${\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\&={\frac {(x_{1}^{2}-1)^{2}}{4By_{1}^{2}}}={\frac {(x_{1}^{2}-1)^{2}}{4x_{1}(x_{1}^{2}+Ax_{1}+1)}}\\[8pt]y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}$

Bükülmüş Edwards eğrileri ile denkliği

Kabul edelim ki $K$ karakteristiği 2'den farkli bir cisim olsun.

Yine kabul edelim ki $M_{A,B}$ Montgomery formunda bir eliptik eğri olsun:

$M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u$

 $A\in K\smallsetminus \{-2,2\}$, $B\in K\smallsetminus \{0\}$

ve kabul edelim ki $E_{a,d}$ bükülmüş Edwards formunda bir eliptik eğri olsun: 

$E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,$

 $a,d\in K\smallsetminus \{0\},\quad a\neq d.$

Aşağıdaki teoremi Mongomery eğrileri ile bükülmüş Edwards eğrileri arasındaki birasyonel denkliği gösterir:

Teorem (i) $K$ üzerinde, her bükülmüş Edwards eğrisi bir Montgomery eğrisine birasyonel denktir. Özellikle, $E_{a,d}$ bükülmüş Edwards eğrisi, $M_{A,B}$ Montgomery eğrisine;   $A={\frac {2(a+d)}{a-d}}$ ve $B={\frac {4}{a-d}}$ sağlanıyorken birasyonel denktir.

Eşleme:

$\psi \,:\,E_{a,d}\rightarrow M_{A,B}$

$(x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)$

$E_{a,d}$'den $M_{A,B}$' ye birasyonel denklik, tersi;

$\psi ^{-1}$: $M_{A,B}\rightarrow E_{a,d}$

$(u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right),a={\frac {A+2}{B}},d={\frac {A-2}{B}}$

Dikkat edilirse, iki eğri arasındaki bu denklik her yerde geçerli değildir: gerçekten de $\psi$ eşlemesi $M_{A,B}$'de $v=0$ ya da $u+1=0$ noktalarında tanımlı değildir.

Weierstrass eğrileri ile denkliği

Tüm eliptik eğriler Weierstrass formunda yazılabilir. Özellikle, Montgomery formundaki eliptik eğriyi ele alalım;

$M_{A,B}$: $By^{2}=x^{3}+Ax^{2}+x,$

aşağıdaki şekilde dönüştürülebilir:

$M_{A,B}$'nin her bir terimini $B^{3}$'e bölüp ve x,y değerlerine, $u={\frac {x}{B}}$, $v={\frac {y}{B}}$ dönüşümü uygulanırsa,

$v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.$

Bir kısa Weierstrass formu elde edebilmek için burada u'yu $t-{\frac {A}{3B}}$ değeri ile değiştirtirmek gerekir:

$v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);$

Sonuç olarak:

$v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).$

Dolayısıyla eşleme şöyle verilir:

$\psi$: $M_{A,B}\rightarrow E_{a,b}$

$(x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}$

aksine,$\mathbb {F}$ baz cismi üzerinde Weierstrass formunda bir eliptik eğri:

$E_{a,b}$: $v^{2}=t^{3}+at+b$

Montgomery formuna ancak ve ancak $E_{a,b}$ mertebesi 4'e bölünebilirse ve aşağıdaki koşulları sağlarsa dönüştürülebilir:

1. $z^{3}+az+b=0$ en az bir $\alpha \in \mathbb {F}$ köküne sahip; ve
2. $3\alpha ^{2}+a$ $\mathbb {F}$'de bir ikinci dereceden rezidü.

Bu şartlar sağlandığında, $s=({\sqrt {3\alpha ^{2}+a}})^{-1}$ için aşağıdaki eşlemeye sahip olunur;

$\psi ^{-1}$: $E_{a,b}\rightarrow M_{A,B}$

$(t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s$.

Ayrıca bakınız

• Curve25519
• Curve25519
• Eliptik egri kriptografisi

Kaynakça

• Peter L. Montgomery (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177). ss. 243-264. doi:10.2307/2007888. JSTOR 2007888. 
• Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves (PDF). Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-68159-5. KB1 bakım: Birden fazla ad: yazar listesi (link)
• Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). "Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation" (PDF). 29 Temmuz 2016 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 11 Nisan 2018.