Montgomery Eğrisi

Montgomery Eğrisi Peter L. Montgomery tarafından 1987’de tanımlanmış, klasik farklı bir 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:

${\displaystyle 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; ${\displaystyle P,Q}$ eliptik eğrisi üzerinde tanımlı iki nokta olmak üzere ${\displaystyle R=P+Q}$; olacak şekilde ${\displaystyle R}$ noktası bulmak işlemidir. Nokta İkileme ise ${\displaystyle [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))

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

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

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

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

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

bu toplamın koordinatları:

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

${\displaystyle 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 ${\displaystyle m=n}$ ise bu işlem "nokta ikileme" işlemine dönüşür; ${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}$ Koordinatları ise aşağıdaki eşitsizliklerle belirlenir; 

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

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

${\displaystyle 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 ${\displaystyle (A+2)/4}$ değeri seçilebilir.

Algoritma ve Örnek

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

${\displaystyle 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.) 

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

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

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

Örnek

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

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

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

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

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

Nokta Toplama

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

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

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

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

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

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

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

${\displaystyle (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:

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

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

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

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

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

${\displaystyle 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}}}}$

${\displaystyle 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

 ${\displaystyle M_{A,B}}$ Montgomery Eğrisi üzerinde verilen bir ${\displaystyle P_{1}}$ noktası için, ${\displaystyle [2]P_{1}}$; Geometrik olarak eğri ile ${\displaystyle P_{1}}$'eğet olan doğru arasındaki kesişimi ifade eden üçüncü noktasını temsil eder;${\displaystyle P_{3}=2P_{1}}$ sağlayan ${\displaystyle 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 ${\displaystyle P_{1}}$ eğrisine teğet olmalıdır. Bu yüzden, eğer ${\displaystyle M_{A,B}:f(x,y)=0}$ ile

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

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

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

'ne göre yazılabilir.

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

${\displaystyle {\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 ${\displaystyle K}$ karakteristiği 2'den farkli bir cisim olsun.

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

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

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

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

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

 ${\displaystyle 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 gösterir:

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

Eşleme:

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

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

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

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

${\displaystyle (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 ${\displaystyle \psi }$ eşlemesi ${\displaystyle M_{A,B}}$'de ${\displaystyle v=0}$ ya da ${\displaystyle 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;

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

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

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

${\displaystyle 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 ${\displaystyle t-{\frac {A}{3B}}}$ değeri ile değiştirtirmek gerekir:

${\displaystyle 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:

${\displaystyle 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:

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

${\displaystyle (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,${\displaystyle \mathbb {F} }$ baz cismi üzerinde Weierstrass formunda bir eliptik eğri:

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

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

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

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

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

${\displaystyle (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

Notlar

1. ^ (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177). ss. 243-264. doi:10.2307/2007888. JSTOR 2007888. 
2. ^ , Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves (PDF). Springer-Verlag Berlin Heidelberg. ISBN . KB1 bakım: Birden fazla ad: yazar listesi () ^[]
3. ^ Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai (2000). Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications. Public Key Cryptography (PKC2000). 8 Mart 2018 tarihinde kaynağından . Erişim tarihi: 11 Nisan 2018. KB1 bakım: Birden fazla ad: yazar listesi ()

Kaynakça

• (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177). ss. 243-264. doi:10.2307/2007888. JSTOR 2007888. 
• , Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves (PDF). Springer-Verlag Berlin Heidelberg. ISBN . KB1 bakım: Birden fazla ad: yazar listesi () ^[]
• Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). (PDF). 29 Temmuz 2016 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 11 Nisan 2018.