Dijital İmza Algoritması

Dijital İmza Algoritması daha iyi bilinen, kısaltması DSA bir olan algoritma ait sayısal imza standardize tarafından NIST içinde ABD'de zaman, RSA bile oldu patentli . Bu algoritma, 1993'te kabul edilen Dijital İmza Standardı (en) için DSS belirtiminin bir parçasıdır (FIPS 186). 1996'da küçük bir revizyon yayınlandı (FIPS 186-1) ve standart 2002'de FIPS 186-2'de geliştirildi. Eski bir NSA çalışanı olan David Kravitz'e verilen ABD Patenti No. 5,231,668 (26 Haziran 1991) kapsamındadır ve ücretsiz olarak kullanılabilir .

genel bakış

DSA, 1989'da Claus-Peter Schnorr (en) tarafından geliştirilen başka bir imza türüne benzer . Ayrıca ElGamal imzasıyla ortak noktaları vardır . İşlem üç adımda gerçekleştirilir:

anahtar üretimi;
belgenin imzası;
imzalanan belgenin doğrulanması.

Anahtar Nesil

Güvenlikleri, sonlu bir grupta ayrık logaritma probleminin zorluğuna dayanmaktadır.

Uzunlukları seçin ve ile 64 ile bölünebilir Bu uzunluklar ile doğrudan anahtarının güvenlik seviyesini tanımlar. NIST 800-57 seçerek önerir ve 128 için eşdeğer güvenlik ısırdı. $L$ $DEĞİL$ $L$ ${\ görüntü stili L = 3072}$ ${\ görüntü stili N = 256}$
Bir asal uzunluk sayısı seçin . $p$ $L$
Asal sayı seçin uzunlukta olacak şekilde, birlikte, bir tamsayı. $q$ $DEĞİL$ ${\ görüntü stili p-1 = qz}$ $z$
Seç ile, böylece . $h$ ${\ görüntü stili 1 <h <p-1}$ ${\ displaystyle g = h ^ {z} {\ bmod {p}}> 1}$
Rastgele birini oluşturabilir ile . $x$ ${\ görüntü stili 0 <x <q}$
Hesapla . ${\ displaystyle y = g ^ {x} {\ bmod {p}}}$
Genel anahtar ise . Özel anahtar ise . ${\ görüntü stili (p, q, g, y)}$ $x$

İmza

gibi rastgele bir sayı seçin . $s$ ${\ görüntü stili 1 <s <q}$
Hesaplamak ${\ displaystyle s_ {1} = (g ^ {s} \ mod p) \ mod q}$
Başka biriyle yeniden başlarsa ${\ görüntü stili s1 = 0}$ $s$
Hesaplama , örneğin, bir şifreleme karma sonucudur SHA-256 mesajı, ${\ displaystyle s_ {2} = (H (m) + s_ {1} x) s ^ {- 1} \ mod q}$ ${\ görüntü stili H (m)}$ $m$
Başka biriyle yeniden başlarsa ${\ görüntü stili s2 = 0}$ $s$
imza $(s_ {1}, s_ {2})$

Doğrulama

Doğrulanmışsa veya doğrulanmamışsa imzayı reddet ${\ görüntü stili 0 <s_ {1} <q}$ ${\ görüntü stili 0 <s_ {2} <q}$
Hesaplamak ${\ displaystyle w = s_ {2} ^ {- 1} {\ bmod {q}}}$
Hesaplamak ${\ displaystyle u_ {1} = H (m) \ cdot w {\ bmod {q}}}$
Hesaplamak ${\ displaystyle u_ {2} = s_ {1} \ cdot w {\ bmod {q}}}$
Hesaplamak ${\ displaystyle (v = g ^ {u_ {1}} \ cdot y ^ {u_ {2}} {\ bmod {p}}) {\ bmod {q}}}$
İmza geçerliyse ${\ görüntü stili v = s_ {1}}$

algoritma geçerliliği

Bu imza ilkesi, doğrulayıcının her zaman gerçek imzaları kabul edeceği anlamında doğrudur. Bu, pratik bir örnekle aşağıdaki şekilde gösterilebilir:

Gönderen ve takip eden: ${\ görüntü stili p-1 = qz}$ ${\ displaystyle g = h ^ {z} {\ bmod {p}}}$

${\ displaystyle g ^ {q} \ eşdeğer h ^ {qz} \ eşdeğer h ^ {p-1} \ eşdeğer 1 {\ bmod {p}}}$ göre Fermat'ın küçük teoremi . Yana ve asal olduğunu, izler için eşit bir emir vardır . $g> 1$ $q$ $g$ $q$

İmzayı gerçekleştiren kişi şunları elde eder:

{\ displaystyle s_ {2} = s ^ {- 1} (H (m) + xs_ {1}) \ mod {q}.}

Yani

{\ displaystyle {\ start {matrix} s & \ equiv & H (m) s_ {2} ^ {- 1} + xs_ {1} s_ {2} ^ {- 1} \\ & \ equiv & H (m) ) w + xs_ {1} w {\ pmod {q}}. \\\ end {matris}}}

Yana g sırası ait q , sahip:

{\ displaystyle {\ başlangıç ​​{matris} g ^ {s} & \ eşdeğer & g ^ {{\ rm {H}} (m) w} g ^ {xs_ {1} w} \\ & \ eşdeğer & g ^ {{ \ rm {H}} (m) w} y ^ {s_ {1} w} \\ & \ eşdeğer & g ^ {u1} y ^ {u2} {\ pmod {p}}. \\\ end {matris} }}

Son olarak, DSA'nın geçerliliğini elde ederiz:

{\ displaystyle s_ {1} = (g ^ {s} \ mod p) \ mod q = (g ^ {u1} y ^ {u2} \ mod p) \ mod q = v.}

Notlar ve referanslar

(fr) Bu makale kısmen veya tamamen alınır İngilizce Vikipedi başlıklı makalesinde " Dijital İmza Algoritması " ( yazarların listesini görmek ) .

Guillot, Philippe. , Kriptoloji: Gizli Kodların Sanatı , EDP Bilimleri,2013, 196 s. ( ISBN 978-2-7598-0995-0 ve 2759809951 , OCLC 854569776 , çevrimiçi okuyun ) , s. 60

Ekler

İlgili Makaleler