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ı == sağ|küçükresim|300x300pik|Montgomery eğrisinin denklemi;\frac{1}{4}y^2=x^3+2,5x^2+x cismi üzerinde Montgomery egrisi, belirli değerleri için ve 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 sonlu cismi üzerinde tanımlı olur. (örnek olarak elemanın oluşturduğu bir sonlu cisim, ) Bu sonlu cismin karakteristiği 2'den farklı ve olması gerektiğine dikkat edelim. Aynı zamanda ve 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 e 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_nZ_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_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n)) Yukarıdakı 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_2y_1-x_1y_2)^2}{x_1x_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{align} 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{align} == 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^2y^2, \, a,d\in K\smallsetminus\\{0\\}, \quad a eq 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: # z^3 + az + b = 0 en az bir \alpha \in \mathbb{F} köküne sahip; ve # 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), s v\right), A = 3 \alpha s, B = s . ==Ayrıca bakınız== * Curve25519 * Curve25519 * Eliptik egri kriptografisi == Notlar == ==Kaynakça== * * * Kategori:Eliptik eğriler