2. Ön Bilgiler

2.1. Gösterim

Asal p modülünde a ve b tamsayılarının çarpımı ab (mod p) veya a * b (mod p) şeklindedir. Bölme a/b (mod p) şeklindedir ve ab^-1 (mod p) olarak hesaplanır. inv(a) (mod p) ifadesini, a 0 değilken a^-1 (mod p) döndürecek, a 0 iken de 0 döndürecek şekilde tanımlarız. Bu, Fermat'ya göre [7] inv(a) = a^(p-2) (mod p) şeklinde hesaplanabilir. ceil() ve floor() işlevleri en yakın tamsayıya yukarı veya aşağı yuvarlar.

Eliptik eğri noktaları A ve B'nin toplanması ve çıkarılması A + B ve A - B şeklindedir. Bir a tamsayısının bir eliptik eğri noktası B ile skaler çarpımı C = aB biçiminde yeni bir nokta verir.

Tamsayı değişkenleri küçük harfle yazılır (x, y). Noktalar ve diğer değişkenler büyük harfle yazılır (P, Q). Tamsayı sabitleri, geleneği izleyen Montgomery eğrisi sabiti A hariç küçük harftir.

Bayt dizileri koyu yazılır (x, P). Koyu yazılmış bir tamsayı veya eliptik eğri noktası, değeri kodlayan sabit uzunlukta bir bayt dizisini temsil eder. Kodlama ve çözümleme ayrıntıları için Bölüm 2.4'e bakın. Bayt dizileri x ve P'nin birleştirilmesi x || P'dir.

Tamsayıların veya noktaların eşitliği a == b ile denetlenir. Bayt dizileri X ve Y'nin eşitliği bytes_equal(X, Y) ile denetlenir.

2.2. Eliptik eğri parametreleri

XEdDSA veya VXEdDSA ile kullanılan bir eliptik eğri aşağıdaki parametrelere sahiptir:

p modülündeki bir tamsayı "alan elemanı"dır. q modülündeki bir tamsayı "skaler"dir.

Bir eliptik eğri, alan elemanlarından oluşan ikililerin kümesidir. Her ikili bir "nokta"dır; bir noktanın içerdiği alan elemanları "koordinatlar"dır ve her noktanın koordinatları eğriyi tanımlayan bir denklemi sağlamalıdır. on_curve(P) işlevi, sözde bir P noktasının eğri denklemini sağlayıp sağlamadığını doğru olarak döndürür.

Eliptik eğri ayrıca noktalar arasında bir toplama işlemi ve noktaları tersine çevirme işlemi tanımlar. Kimlik noktasıyla birlikte bu işlemler, eğrinin noktaları üzerinde bir grup yapısı tanımlar. Bir P noktasını kendisiyle k kez toplamak (P + P + P + ...) k skaleriyle skaler çarpımdır ve kP olarak gösterilir.

XEdDSA ve VXEdDSA, (x, y) ile gösterilen noktalardan oluşan twisted Edwards eğrileri için tanımlanmıştır. Bir twisted Edwards eğrisi, (u, v) ile gösterilen noktalardan oluşan bir Montgomery eğrisiyle birasyonel olarak denktir [8]. Esas olarak twisted Edwards eğrisiyle ilgileneceğiz; bu yüzden taban nokta B ve kimlik noktası I hakkında konuştuğumuzda twisted Edwards eğrisi üzerindeki noktalardan söz ediyoruz.

u_to_y işlevi, Montgomery eğrisi üzerindeki bir noktanın u-koordinatını, twisted Edwards eğrisi üzerindeki eşdeğer noktanın y-koordinatına dönüştürmek için eğriye özgü bir birasyonel dönüşüm uygular.

2.3. Eliptik eğri dönüşümleri

Eliptik eğri Diffie-Hellman çoğu zaman Montgomery ladder kullanılarak hesaplanır. Bu, zamanlama yan kanallarına doğal olarak dirençli basit ve verimli bir hesaplama sağlar. Montgomery ladder ayrıca her iki tarafın açık anahtarının bir Montgomery u-koordinatı olmasına da imkân tanır. Tüm nokta yerine tek koordinat kullanmak, nokta çözümlemenin getirdiği maliyet olmadan açık anahtarları küçültür.

Ancak EdDSA imzaları twisted Edwards eğrileri üzerinde tanımlanır; burada açık anahtar, twisted Edwards y-koordinatı ile 0 veya 1 olan bir işaret biti s'den oluşan sıkıştırılmış bir noktadır. Bir twisted Edwards y-koordinatı ve işaret biti, bir twisted Edwards noktasının alternatif gösterimini sağlar ve [1] veya [2]'de belirtildiği gibi x-koordinatını belirler.

Bir Montgomery u-koordinatından twisted Edwards noktası P'ye dönüşüm aşağıdaki convert_mont işleviyle yapılabilir. Bu işlev önce u'dan fazla yüksek bitleri maskeler; bu, Curve25519 Montgomery açık anahtarları için standart uygulamadır ve [4]'te belirtilmiştir. İşlev daha sonra twisted Edwards y-koordinatını hesaplamak için eğriye özgü bir birasyonel dönüşüm uygular ve son olarak işaret bitini sıfır olarak seçer.

convert_mont(u):
    u_masked = u (mod 2^|p|)
    P.y = u_to_y(u_masked)
    P.s = 0
    return P

convert_mont, Montgomery v değerine sahip olmadığından twisted Edwards işaret biti için iki olasılığı ayırt edemez. İşaret bitini sıfıra zorlamak Jivsov'dan gelen bir fikirdir [9].

Özel anahtarları bu dönüşümle uyumlu hâle getirmek için twisted Edwards özel anahtarını, twisted Edwards açık anahtarı A = aB sıfır işaret bitine sahip olacak şekilde bir a skaleri olarak tanımlarız (burada B'nin twisted Edwards taban noktası olduğunu anımsayın). Bir Montgomery özel anahtarının herhangi bir skaler olmasına izin veririz.

Bir Montgomery özel anahtarı k'yi twisted Edwards açık anahtar ve özel anahtar çiftine (A, a) dönüştürmek calculate_key_pair işleviyle yapılabilir (buradaki "A" açık anahtardır, Montgomery eğrisi sabiti değildir). Bu işlev, Montgomery özel anahtarı k'yi twisted Edwards taban noktası B ile çarpar, ardından [9]'u izleyerek gerektiğinde özel anahtarı sıfır işaret biti üretecek şekilde ayarlar.

calculate_key_pair(k):
    E = kB
    A.y = E.y
    A.s = 0
    if E.s == 1:
        a = -k (mod q)
    else:
        a = k (mod q)
    return A, a

2.4. Bayt dizileri

Kalın yazılmış bir tamsayı, little-endian biçimde tamsayıyı kodlayan b bitlik bir bayt dizisini temsil eder. Kalın yazılmış bir eliptik eğri noktası (örn. P), P.y değerini b-1 bit uzunluğunda little-endian bir tamsayı olarak, ardından P.s için bir bit gelecek biçimde kodlar.

2.5. Özet işlevleri

XEdDSA ve VXEdDSA kriptografik bir özet işlevi gerektirir. Varsayılan özet işlevi SHA-512'dir [10].

hash'i, kriptografik özeti bir girdi bayt dizisine uygulayan ve çıktıyı little-endian biçimde çözümleyerek elde edilen bir tamsayı döndüren işlev olarak tanımlarız. hash ile eğri sabitleri p ve b verildiğinde, 2^|p| - 1 - i > p olacak biçimde negatif olmayan i tamsayılarıyla indekslenen bir özet işlevleri ailesi tanımlarız.

hash_i(X):
    return hash(2^b - 1 - i || X)

Böylece hash_0, girdi bayt dizisi X'ten önce b/8 bayt 0xFF özetler; hash_1 ilk baytı 0xFE yapar; hash_2 ilk baytı 0xFD yapar; ve bu böyle devam eder.

Farklı hash_i değerleri, kriptografik alan ayrımı sağlamak amacıyla farklı amaçlar için kullanılacaktır. hash_i'nin ilk b bitleri geçerli bir skaleri veya eliptik eğri noktasını kodlayacak şekilde hiçbir zaman hash çağırmayacağını unutmayın; çünkü ilk |p| bitleri p'den büyük bir tamsayıyı kodlar. Ayrıca hash_0'ın başka belirtimler için ayrıldığını ve bu belgede kullanılmadığını da not edin.

2.6. Elligator 2 ile bir noktaya özetleme

VXEdDSA, bir girdinin bir eliptik eğri noktasına eşlenmesini gerektirir; bu da Elligator 2 eşlemesi [11] kullanılarak yapılır.

[11]'deki açıklama özlüdür ve farklı gösterim kullanır; bu yüzden Elligator 2'yi kısaca gözden geçiriyoruz. (u, v) noktaları için Montgomery eğrisi denklemi v^2 = u(u^2 + Au + 1) (mod p) biçimindedir; burada A eğriye özgü bir sabittir. Elligator 2, bir r tamsayısını, u(u^2 + Au + 1) ifadesi için p modülünde karekök v bulunan bir u değerine eşler. Aşağıdaki lemma kullanılır.

Lemma (Bernstein, Hamburg, Krasnova, Lange). u_2 = -A - u_1 ve herhangi bir r ile sabit kare olmayan n için u_2/u_1 = nr^2 olacak şekilde u_1 ve u_2 p modülünde tamsayılar ise, v^2 = u(u^2 + Au + 1) Montgomery eğrisi denkleminin u = u_1 veya u = u_2 için, ya da her ikisi için bir çözümü vardır.

Kanıt. u_1 ve u_2 verildiğinde w_1 = u_1(u_1^2 + Au_1 + 1) ve w_2 = u_2(u_2^2 + Au_2 + 1) tanımlansın. v^2 = w_1 veya v^2 = w_2 için bir çözümün var olduğunu kanıtlamalıyız. w_2/w_1'in ya sıfır ya da kare olmayan olduğunu göstereceğiz; bu da ya w_2'nin sıfır olduğunu ve dolayısıyla kare olduğunu ya da w_2 ile w_1'den birinin kare olduğunu ima eder.

w_2/w_1 = u_2(u_2^2 + Au_2 + 1) / u_1(u_1^2 + Au_1 + 1)

w_2/w_1 = (u_2/u_1) (u_2^2 + Au_2 + 1) / (u_1^2 + Au_1 + 1)

u_2 = -A - u_1 uygulanırsa:

w_2/w_1 = u_2/u_1

u_2/u_1 = nr^2 uygulanırsa:

w_2/w_1 = nr^2

r sıfırsa w_2 mutlaka sıfırdır ve bu karelidir. r sıfır değilse, r^2 kare ve n kare olmayan olduğundan w_2/w_1 kare olmayandır; bu da w_2 veya w_1'den birinin kare olduğunu ima eder; böylece kanıt tamamlanır.

Lemmadan, u_1 = -A/(1 + nr^2) ve u_2 = -Anr^2/(1 + nr^2) sonucu çıkar. Dolayısıyla r verildiğinde u_1 ve u_2 kolayca hesaplanabilir ve hangi değerin kare w verdiğini seçmek için Legendre simgesi [12] kullanılabilir. elligator2 işlevi, bu r tamsayısından u tamsayısına eşlemeyi uygular.

elligator2(r):
    u_1 = -A * inv(1 + nr^2) (mod p)
    w_1 = u_1(u_1^2 + Au_1 + 1) (mod p)
    if w_1^((p-1)/2) == -1 (mod p):
        u_2 = -A - u_1 (mod p)
        return u_2
    return u_1

(inv işlevi burada güvenli şekilde kullanılır; çünkü r^2 = -1/n iken inv(0) çağrısı yalnızca r'yi geçerli bir Montgomery u-koordinatı olan u=0 üzerine eşler.)

Bir bayt dizisini Edwards noktasına eşlemek için, bayt dizisini özetler ve özet çıktısını çözümleyerek bir alan elemanı r ve bir işaret biti s elde ederiz. Elligator 2, r'yi bir Montgomery u-koordinatına dönüştürür. Birasyonel dönüşüm, Montgomery u-koordinatını bir Edwards noktasına dönüştürür. Son olarak Edwards noktasını cofactor c ile çarparız; böylece noktanın taban nokta B'nin ürettiği mertebe q alt grubunda yer alması sağlanır. hash_to_point işlevi bu adımları uygular.

hash_to_point(X):
    h = hash_2(X)
    r = h (mod 2^|p|)
    s = floor((h mod 2^b) / 2^(b-1))
    u = elligator2(r)
    P.y = u_to_y(u)
    P.s = s
    return cP