Twisted Edwards eğrisi - Twisted Edwards curve

Bükülmüş bir Edwards denklem eğrisi

İçinde cebirsel geometri, bükülmüş Edwards eğrileri uçak modelleridir eliptik eğriler bir genelleme Edwards eğrileri tarafından tanıtıldı Bernstein, Birkner, Joye, Lange ve Peters, 2008.[1] Eğri seti matematikçinin adını almıştır Harold M. Edwards. Eliptik eğriler, açık anahtarlı kriptografi ve bükülmüş Edwards eğrileri, adı verilen elektronik imza şemasının merkezinde yer alır. EdDSA diğer dijital imza şemalarında ortaya çıkan güvenlik sorunlarından kaçınırken yüksek performans sunar.

Tanım

Her biri bükülmüş Edwards eğrisi bir bükülme bir Edwards eğrisi Bükülmüş bir Edwards eğrisi üzerinde alan hangisi var bir afin denklemle tanımlanan düzlem eğrisi:

nerede farklı sıfır olmayan öğelerdir . Özel durum dır-dir bükülmemiş, çünkü eğri normal bir Edwards eğrisi.

Her bükülmüş Edwards eğrisi çiftleşme açısından eşdeğer eliptik bir eğriye Montgomery formu ve tam tersi.[2]

Grup hukuku

Tüm eliptik eğrilerde olduğu gibi, bükülmüş Edwards eğrisi için de, noktaları arasında iki tane eklemek veya birini ikiye katlamak (veya üçe katlamak) gibi bazı işlemler yapmak mümkündür. Bu işlemlerin sonuçları her zaman eğrinin kendisine ait noktalardır. Aşağıdaki bölümlerde, diğer iki nokta arasındaki bir toplamadan (toplama) kaynaklanan bir noktanın koordinatlarını veya bir eğri üzerindeki tek bir noktanın iki katına çıkmasından kaynaklanan noktanın koordinatlarını elde etmek için bazı formüller verilmiştir.

Bükülmüş Edwards eğrilerine ekleme

İzin Vermek alan olmak karakteristik 2'den farklı ve bükülmüş Edwards eğrisinde noktalar olun. Bükülmüş Edwards eğrisinin denklemi şu şekilde yazılır;

EE,a,d: .

Bu noktaların toplamı açık EE,a,d dır-dir:

Nötr eleman (0,1) ve negatif dır-dir

Bu formüller aynı zamanda ikiye katlamak için de çalışır. Eğer a bir Meydan içinde ve d bir kare olmayan içinde , bu formüller tamamlayınız: bu, istisnasız tüm puan çiftleri için kullanılabilecekleri anlamına gelir; böylece ikiye katlamak için de çalışırlar ve nötr öğeler ve olumsuzlar girdi olarak kabul edilir.[3][başarısız doğrulama ]

Ekleme örneği

Aşağıdaki bükülmüş Edwards eğrisi göz önüne alındığında a = 3 ve d = 2:

noktaları eklemek mümkündür ve yukarıda verilen formülü kullanarak. Sonuç bir P noktasıdır3 koordinatları olan:

Bükülmüş Edwards eğrilerinde ikiye katlama

İkiye katlama toplama ile tamamen aynı formülle gerçekleştirilebilir. (x1, y1) E eğrisindeE, bir, d dır-dir:

[2](x1,y1) = (x3,y3)

nerede

İkiye katlama örneği

Önceki örnekte verilen aynı bükülmüş Edwards eğrisi göz önüne alındığında, a = 3 ve d = 2 ile noktayı iki katına çıkarmak mümkündür. . 2P noktası1 Yukarıdaki formül kullanılarak elde edilen aşağıdaki koordinatlara sahiptir:

Bazı küçük hesaplamalarla şunu görmek kolaydır: eğriye ait .

Genişletilmiş koordinatlar

Bükülmüş Edwards eğrilerindeki bir noktanın gösterilebileceği başka bir tür koordinat sistemi vardır. açık olarak temsil edilir X, Y, Z, T aşağıdaki denklemleri karşılamak x = X/Z, y = Y/Z, xy = T/Z.

Noktanın koordinatları (X:Y:Z:T) denir genişletilmiş bükülmüş Edwards koordinatları. Kimlik öğesi (0: 1: 1: 0) ile temsil edilir. Bir noktanın negatifi (-X:Y:Z:−T).

Ters bükülmüş Edwards koordinatları

Noktanın koordinatları denir ters bükülmüş Edwards koordinatları eğri üzerindeile ; bu afin olanı gösteriyor açık EE,a,dBernstein ve Lange, bu ters çevrilmiş koordinatları, a = 1 durumu için tanıttılar ve koordinatların ek olarak zaman kazandırdığını gözlemlediler.

Projektif bükülmüş Edwards koordinatları

Projektif bükülmüş Edwards eğrisinin denklemi şu şekilde verilmiştir: İçin Z1 ≠ 0 nokta (X1: Y1: Z1) temsil etmek afin noktası (x1X1/Z1, y1 = Y1/Z1) üzerinde EE,a,d.

Bükülmüş Edwards biçiminde bir eliptik eğri ifade etmek, aynı eğri Edwards biçiminde ifade edilebildiğinde bile aritmetikte zaman kazandırır.

Projektif bükülmüş eğrilere ekleme

Bir projektif bükülmüş Edwards eğrisine ekleme şu şekilde verilir:

(X3: Y3: Z3) = (X1: Y1: Z1) + (X2: Y2: Z2)

ve maliyeti 10Multiplications + 1Squaring + 2D + 7 additions, burada 2D bir çarpımdır a ve tek tek d.

Algoritma
A = Z1 · Z2,
B = A2
C = X1 · X2
D = Y1 · Y2
E = dC · D
F = B - E
G = B + E
X3 = A · F ((X1 + Y1) · (X2 + Y2) - C - D)
Y3 = A · G · (D - aC)
Z3 = F · G

Projektif bükülmüş eğrilerde ikiye katlama

Projektif bükülmüş eğri üzerinde ikiye katlama şu şekilde verilir:

(X3: Y3: Z3) = 2 (X1: Y1: Z1).

Bu 3Multiplications + 4Squarings + 1D + 7additions, burada 1D ile çarpma a.

Algoritma
B = (X1 + Y1)2
C = X12
D = Y12
E = aC
F = E + D
H = Z12
J = F - 2H
X3 = (B - C - D) .J
Y3 = F · (E - D)
Z3 = F · J[1]

Ayrıca bakınız

Notlar

  1. ^ a b D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, Twisted Edwards Curves.
  2. ^ Daniel J. Bernstein; Peter Birkner; Marc Joye; Tanja Lange; Christiane Peters. "Twisted Edwards Curves" (PDF). Alındı 28 Ocak 2020.
  3. ^ Daniel J. Bernstein ve Tanja Lange, Eliptik eğrilerde daha hızlı ekleme ve ikiye katlama

Referanslar

Dış bağlantılar