Dijital İmza Algoritması

**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ı, ElGamal İmza Algoritması'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 özet fonksiyon olan *H*'yi seç. *H* olarak SHA-1 kullanılırdı, fakat şu anki DSS'de SHA-1'den daha güçlü olan SHA-2 kullanılmaktadır. Özet 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çütüdür. Orijinal 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' değeri seç. *N*nin uzunluğu özet 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 mertebesi modulo *p* de *q* olan bir g değeri seç. Bu rastgele bir  *h* (1 &lt; *h* &lt; *p*−1) değeri  için *g* = *h*(*p*–1)/*q* mod *p* ile yapılabilir. Eğer sonuç 1 olarak gelirse  farklı *h* değerleri için dene. *h*nin ç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 gizli ve açık anahtarlar üretilir:
* Rassal olarak  0 &lt; *x*&nbsp;<&nbsp;*q* olacak şekilde bir*x* seç .
* *y* = *gx* mod *p* değerini hesapla.
* Açık anahtar (*p*, *q*, *g*, *y*). Özel anahtar *x*.
*h*<sup>(*p*–1)/*q*</sup> mod *p* ve *gx* mod *p*, modüler üslerini almak için etkili algoritmalar mevcuttur( [[Exponentiation by squaring]] gibi).
== İmzalama ==
*H* bir özet fonksiyon ve *m* mesaj olsun :
*  0 &lt; *k* &lt; *q* olacak şekilde her bir mesaj için rassal bir *k* değeri üret.
* *r* = (*gk* mod *p*) mod *q* değerini hesapla.
* *r*&nbsp;=&nbsp;0, ise  farklı rassal bir *k* değeri ile tekrar baştan başla
* *s* = (*k*<sup>&minus;1</sup>(*H*(*m*) + *x*•*r*)) mod *q* değerini hesapla
* Eğer *s*&nbsp;=&nbsp;0, ise farklı rassal bir *k* değeri ile tekrar baştan başla.
* İmza (*r*,&nbsp;*s*)
İlk iki adım kullanıcı anahtarı oluşturmaya yarar. İmzalama işleminde hesaplaması en maliyetli kısım modüler üs alma işlemidir. 'k'nın modüler tersinin hesaplanması <sup>&minus;1</sup>&nbsp;mod&nbsp;*q* ikinci en maliyetli kısımdır. [[Genişletilmiş Öklid Algoritması]] ya da [[Fermat'nın son teoremi]]  *k*<sup>*q*−2</sup>&nbsp;mod&nbsp;*q* kullanılarak hesaplanabilir.

== Doğrulama ==
* Eğer 0 < *r* < *q* ya da 0 < *s* < *q* sağlanmazsa imzayı reddet.
* *w* = *s*<sup>&minus;1</sup> mod *q* değerini hesapla.
* *u*1 = *H*(*m*)•*w* mod *q* değerini hesapla.
* *u*2 = *r*•*w* mod *q* değerini hesapla.
* *v* = ((*g*<sup>*u*1</sup>•*y*<sup>*u*2</sup>) mod *p*) mod *q* değerini 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 ispatlanabilir:

İlk olarak, eğer g *g* = *h*<sup>(*p*&nbsp;&minus;&nbsp;1)/*q*</sup> mod *p*  ise 
[[Fermat'nın son teoremi]] ile *gq* ≡ *h*<sup>*p*&nbsp;&minus;&nbsp;1</sup> ≡ 1 (mod&nbsp;*p*) ‘dir.
*g*&nbsp;>&nbsp;1  ve *q* asal olduğundan, *g**nin mertebesi &nbsp;''q**dur.

İmzalayan kişi

:s=k^{-1}(H(m)+xr) \mod{q} değerini hesaplar.

Böylece

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


*g*nin mertebesi *q* (mod p) q olduğundan

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


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

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

## 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 (*k*yı 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.

## Ayrıca bakınız
* ElGamal İmza Algoritması
* Schnorr imzası

## Dış bağlantılar
* FIPS PUB 186-4: Dijital İmza Standardı (DSS), resmi DSA tanımlamasının dördüncü (ve güncel) sürümü.
* Anahtar yönetimi için öneri -- Bölüm 1: genel, NIST Özel Yayını 800-57, p.&nbsp;62–63