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ı 

 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: the group law))

 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
 
 
 

Eliptik eğriler