Misplaced Pages

This is the current revision of this page, as edited by ShakespeareFan00 (talk | contribs) at 13:03, 26 November 2024 (Apologies for the interruption, but this page had appeared on a list of those containing a markup error, , misnested tags). The present address (URL) is a permanent link to this version.

Dijital İmza Algoritması dijital imza için bir FIPS standardıdır. Ağustos 1991’de National Institute of Standards and Technology (NIST) tarafından tasarlanmıştır. Dijital imza algoritması, El Gamal imza şemasının bir varyantıdır.

Anahtar Oluşturma

Anahtar oluşturma iki aşamadan oluşur. İlk aşama sistemdeki farklı kullanıcılar arasında paylaşılabilen “algoritma parametreleri”nin seçimiyken ikinci aşama tek bir kullanıcı için açık ve gizli anahtarların hesaplanmasıdır.

Parametre Oluşturma

• Onaylı bir kriptografik özüt fonksiyon H seç. H olarak SHA-1 kullanılırdı, fakat şuanki DSS’de daha güçlü olan SHA-2 kullanılmaktadır. Özüt fonksiyonun çıktısı anahtar ikilisinin boyutuna kısaltılabilir.
• Anahtar uzunluğu L ve N nin belirlenmesi. Bu, anahtarın kriptografik gücünün belirlenmesinin en önemli ölçümüdür. Orjinal Dijital İmza Standardı L’nin değerini 512 ile 1024’ün arasında 64’ün katı olarak kısıtlamıştır.
• N-bit uzunluğunda asal bir q' seç'. Nin uzunluğu özüt fonksiyonun çıktı değerinden kısa ya da eşit olmalıdır.
• p–1, q nun katı olacak şekilde L -bit uzunluğunda asal p' modülüsünü seç.
• Çarpımsal orderı modulo p de q olan bir g seç. Bu rasgele bir h (1 < h < p−1) değeri için g = h mod p ile yapılabilir. Eğer sonuç 1 olarak gelirse farklı h değerleri için dene. hnin çoğu değeri g' olarak kullanılabilir'; daha çok h=2 kullanılmaktadır.

Algoritma parametreleri olan (p, q, g) sistemdeki farklı kullanıcılar arasında paylaşılabilir.

Kullanıcı anahtarları

Parametre seti verildiğinde, ikinci aşamada tek bir kullanıcı için özel ve açık anahtarlar üretilir:

• Rassal olarak 0 < x < q olacak şekilde birx seç .
• y = g mod p hesapla.
• Açık anahtar (p, q, g, y). Özel anahtar x.

h mod p ve g mod p, modüler üslerini almak için etkili algoritmalar mevcuttur( exponentiation by squaring gibi).

İmzalama

H bir özüt fonksiyon ve m mesaj olsun :

• 0 < k < q olacak şekilde her bir mesaj için rassal bir k değeri üret
• r = (g mod p) mod q hesapla
• r = 0, ise farklı rassal bir k değeri ile tekrar baştan başla
• s = (k(H(m) + x•r)) mod q hesapla
• Eğer s = 0, ise farklı rassal bir k değeri ile tekrar baştan başla.
• İmza (r, s)

İlk iki adım kullanıcı anahtarı oluşturmaya yarar. İmzalama işleminin en pahalı kısmı moduler üs alma işlemidir.

knın modüler tersi  mod q ikinci en pahalı kısımdır. Genişletilmiş Öklid Algoritması ya da Fermat'ın küçük teoremi  k mod q kullanılarak hesaplanabilir.

Doğrulama

• Eğer 0 < r < q or 0 < s < q sağlanmazsa imzayı reddet.
• w = s mod q hesapla.
• u1 = H(m)•w mod q hesapla.
• u2 = r•w mod q hesapla.
• v = ((g•y) mod p) mod q hesapla
• Eğer v = r ise imza kabul edilir.

Algoritmanın Doğruluğu

Eğer doğrulayıcı gerçek imzaları her zaman kabul ediyorsa imza şeması doğrudur. Algoritmanın doğruluğu şu şekilde gösterilebilir:

İlk olarak, eğer g g = h mod p ise Fermat'ın küçük teoremi ile g ≡ h ≡ 1 (mod p) ‘dir. g > 1 ve q asal olduğundan, g’nin orderı  q’dur.

İmzalayan kişi

${\displaystyle s=k^{-1}(H(m)+xr)\mod {q}}$ hesaplar.

Böylece

${\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}$

gnin orderı q (mod p) q olduğundan

${\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u1}y^{u2}{\pmod {p}}\end{aligned}}}$

Sonuç olarak, Dijital İmza Algoritmasının doğruluğu aşağıdaki gibi hesaplanarak çıkar.

${\displaystyle {\begin{aligned}r&=(g^{k}\mod p)\mod q\\&=(g^{u1}y^{u2}\mod p)\mod q\\&=v\end{aligned}}}$

Duyarlılık

Dijital İmza Algoritmasında k rassal imza değerinin entropisi, gizliliği ve tek olması önemlidir. Bunlardan birinin olmaması halinde saldıran gizli anahtarı açığa çıkartabilir. . Aynı değer iki kez kullanılırsa (kyı gizli tutsa bile), tahmin edilebilir bir değer kullanılarak ya da birkaç imzadaki k nın bazı bitleri sızdırılarak Dijital İmza Algoritması kırılabilir.

See also

• Elliptic Curve DSA
• Modular arithmetic

References

1. The Debian PGP disaster that almost was.
2. DSA k-value Requirements

External links

• FIPS-186, the first version of the official DSA specification.
• FIPS-186, change notice No.1, the first change notice to the first version of the specification.
• FIPS-186-1, the first revision to the official DSA specification.
• FIPS-186-3, the third and current revision to the official DSA specification.
• FIPS-186-3 Approval, Approval announcement of the third revision to the official DSA specification.
• Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63