Montgomery Eğrisi

[bullvar_katip]

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; cismi üzerinde Montgomery egrisi, belirli değerleri için ve eşitsizliği sağlanıyorken, aşağıdaki eşitsizlikle tanımlanır: 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; eliptik eğrisi üzerinde tanımlı iki nokta olmak üzere ; olacak şekilde noktası bulmak işlemidir. Nokta İkileme ise işlemidir. (Kullanılan işlemler hakkında detaylı bilgi için bkz; elliptic eğri grup kuralları (eng: )) noktası Montgomery formundaki eliptik eğrisi üzerinde bir nokta olmak üzere, bu noktanın Montgomery koordinatları Burada projektif koordinatlardır. ( ve ). Bir nokta için bu tür bir temsilin(dönüşümün) bilgi kaybettiğine dikkat edin: gerçekten ve (afin noktalarının kullanımında bir ayrım gözetilmez çünkü her iki noktanın kullanımı da bize sonucunu verecektir. Ancak, bu gösterim(dönüşüm) ile bir noktanın n sayısı ile çarpılmasını elde etmek mümkündür; Şimdi, iki nokta dikkate alalım; ve : Bu iki noktanın toplamları aşağıdaki şekilde ifade edilir; bu toplamın koordinatları: Eğer ise bu işlem "nokta ikileme" işlemine dönüşür; Koordinatları ise aşağıdaki eşitsizliklerle belirlenir; 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 değeri seçilebilir. Algoritma ve Örnek Montgomery formunda bir eliptik eğrininin bir noktasının nokta ikilemesi, aşağıdaki algoritma ile gösterilebilir; 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.) Örnek Kabul edelim ki noktası, eğrisi üzerinde bir nokta olsun. Koordinatları; ; , O halde: Sonuç olarak bulduğumuz nokta; dikkat edilirse, . Nokta Toplama afin koordinatlarda Montgomery eğrisi üzerinde iki nokta olmak üzere, şeklinde belirlenen nokta geometrik olarak ile ve noktalarını birleştiren doğrunun kesimini ifade eden üçüncü bir noktadır. Bu noktanın koordinatları aşağıdaki şekilde belirlenir: 1) 2 boyutlu afin uzayda, doğrusunun ve noktalarından geçtiğini varsayalım.(bu varsayımdan yararlanarak), ve ; elde edilir. 2) Doğru ile , eğri denklemindeki değişkeni ile değiştirilirse aşağıdaki 3. dereceden denklem elde edilir: Daha önce gözlemlenebildiği gibi, bu denklem , ve noktalarının x koordinatlarına göre üç köke sahiptir. Öyleyse denklem; ş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: . Böylelikle, terimi , , , terimleri cinsinden aşağıdaki biçimde yazılabilir: 4) noktasının koordinatını bulabilmek için, değerini doğrusunda yerine koymak yeterlidir. Bunun doğrudan noktasını vermeyeceğine dikkat edin. Gerçekten, bu yöntemle, , sağlayan noktasının koordinatları bulunur. Eğer ve nokta ekleme işleminin sonuç noktasına ihtiyaç duyulursa, ancak ve ancak olması durumunu göz önüne almak gereklidir. Bu yüzden, verilen noktası için noktasını bulmak gereklidir. Bu işlem verilen nin y koordinatının işaretini değiştirerek kolaylıkla yapılabilir. Başka bir deyişle, doğru denkleminde ün yerine konulmasıyla elde edilen koordinatının işaretini değiştirmek yeterli olacaktır. Öyleyse noktasının koordinatları, şunlardır: Nokta İkileme Montgomery Eğrisi üzerinde verilen bir noktası için, ; Geometrik olarak eğri ile 'eğet olan doğru arasındaki kesişimi ifade eden üçüncü noktasını temsil eder; sağlayan noktasının koordinatlarını bulabilmek için, 'nokta toplama' metodundakine benzer bir yol izlenir; ancak, bu durumda, y=lx+m doğrusu eğrisine teğet olmalıdır. Bu yüzden, eğer ile Doğrunun eğimini temsil eden l değeri aşağıdaki gibi verilir: kapalı fonksiyon teoremi'ne göre yazılabilir. Yani ve , Bükülmüş Edwards eğrileri ile denkliği Kabul edelim ki karakteristiği 2'den farkli bir cisim olsun. Yine kabul edelim ki Montgomery formunda bir eliptik eğri olsun: , ve kabul edelim ki bükülmüş Edwards formunda bir eliptik eğri olsun: Aşağıdaki teoremi Mongomery eğrileri ile bükülmüş Edwards eğrileri arasındaki birasyonel denkliği gösterir: Teorem (i) üzerinde, her bükülmüş Edwards eğrisi bir Montgomery eğrisine birasyonel denktir. Özellikle, bükülmüş Edwards eğrisi, Montgomery eğrisine; ve sağlanıyorken birasyonel denktir. Eşleme: 'den ' ye birasyonel denklik, tersi; : Dikkat edilirse, iki eğri arasındaki bu denklik her yerde geçerli değildir: gerçekten de eşlemesi 'de ya da 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; : aşağıdaki şekilde dönüştürülebilir: 'nin her bir terimini 'e bölüp ve x,y değerlerine, , dönüşümü uygulanırsa, Bir kısa Weierstrass formu elde edebilmek için burada u'yu değeri ile değiştirtirmek gerekir: Sonuç olarak: Dolayısıyla eşleme şöyle verilir: : aksine, baz cismi üzerinde Weierstrass formunda bir eliptik eğri: : Montgomery formuna ancak ve ancak mertebesi 4'e bölünebilirse ve aşağıdaki koşulları sağlarsa dönüştürülebilir: en az bir köküne sahip; ve 'de bir ikinci dereceden rezidü. Bu şartlar sağlandığında, için aşağıdaki eşlemeye sahip olunur; : . Ayrıca bakınız Curve25519 Curve25519 Eliptik egri kriptografisi Notlar Kaynakça Kategori:Eliptik eğriler