Eliptik Eğri Dijital İmza Algoritması - Elliptic Curve Digital Signature Algorithm

Gelen kriptografi , eliptik eğri dijital imza algoritması ( ECDSA ) 'in bir varyantı sunmaktadır dijital imza algoritması kullanır (DSA), eliptik eğri şifreleme .

Anahtar ve imza boyutu

Genel olarak eliptik eğri kriptografi ile olduğu gibi, bit büyüklüğü ve genel anahtarı ECDSA iki katı büyüklüğünde olan için gerekli olduğuna inanılan bir güvenlik seviyesi bit. Örneğin, 80 bitlik bir güvenlik seviyesinde (yani bir saldırganın özel anahtarı bulmak için maksimum yaklaşık işlem yapması gerekir) bir ECDSA özel anahtarının boyutu 160 bit olurken, bir DSA özel anahtarının boyutu en az 1024'tür. bit. Öte yandan, imza boyutu hem DSA hem de ECDSA için aynıdır: yaklaşık olarak bit, burada güvenlik seviyesi bit olarak ölçülür, yani 80 bitlik bir güvenlik seviyesi için yaklaşık 320 bit. ${\ Displaystyle 2^{80}}$${\ Displaystyle 4t}$${\görüntüleme stili t}$

İmza oluşturma algoritması

Alice'in Bob'a imzalı bir mesaj göndermek istediğini varsayalım . Başlangıçta, eğri parametreleri üzerinde anlaşmaları gerekir . Eğrinin alanına ve denklemine ek olarak, eğri üzerinde asal mertebeden bir taban noktasına ihtiyacımız var ; noktanın çarpım sırasıdır . ${\displaystyle ({\textrm {CURVE}},G,n)}$${\görüntüleme stili G}$${\görüntüleme stili n}$${\görüntüleme stili G}$

Parametre
EĞRİ	eliptik eğri alanı ve kullanılan denklem
G	eliptik eğri taban noktası, eğri üzerinde büyük asal mertebeden bir alt grup oluşturan bir nokta n
n	G'nin tamsayı sırası , kimlik öğesinin nerede olduğu anlamına gelir . ${\görüntüleme stili n\kez G=O}$${\görüntüleme stili O}$
${\görüntüleme stili d_{A}}$	özel anahtar (rastgele seçilmiş)
${\ Displaystyle Q_{A}}$	ortak anahtar (eliptik eğri ile hesaplanır)
m	gönderilecek mesaj

Taban noktasının sırası asal olmalıdır . Aslında, halkanın sıfır olmayan her elemanının tersinir olduğunu varsayıyoruz , bu yüzden bu bir alan olmalıdır. Bunun asal olması gerektiğini ima eder (cf. Bézout'un kimliği ). ${\görüntüleme stili n}$${\görüntüleme stili G}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\görüntüleme stili n}$

Alice , aralıkta rastgele seçilen bir özel anahtar tamsayısından oluşan bir anahtar çifti yaratır ; ve bir ortak anahtar eğri noktası . Eliptik eğri nokta çarpımını bir skaler ile belirtmek için kullanırız . ${\görüntüleme stili d_{A}}$${\görüntüleme stili [1,n-1]}$${\displaystyle Q_{A}=d_{A}\times G}$${\görüntüleme stili \kez }$

Alice'in bir mesajı imzalaması için şu adımları takip eder: ${\görüntüleme stili m}$

1. Hesapla . (Burada HASH, çıktısı bir tamsayıya dönüştürülmüş SHA-2 gibi bir kriptografik karma işlevidir .)${\displaystyle e={\textrm {HASH}}(m)}$
2. Izin olması en sol bit , grup için bit uzunluğu . (Not olabilir büyüktür fazla değil artık .)${\görüntüleme stili z}$${\displaystyle L_{n}}$${\görüntüleme stili e}$${\displaystyle L_{n}}$${\görüntüleme stili n}$${\görüntüleme stili z}$${\görüntüleme stili n}$
3. içinden kriptografik olarak güvenli bir rastgele tamsayı seçin .${\görüntüleme stili k}$${\görüntüleme stili [1,n-1]}$
4. Eğri noktasını hesaplayın .${\displaystyle (x_{1},y_{1})=k\times G}$
5. Hesapla . ise 3. adıma geri dönün.${\displaystyle r=x_{1}\,{\bmod {\,}}n}$${\görüntüleme stili r=0}$
6. Hesapla . ise 3. adıma geri dönün.${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$${\görüntüleme stili s=0}$
7. İmza çifttir . (Ayrıca geçerli bir imzadır.)${\görüntüleme stili (r,s)}$${\displaystyle (r,-s\,{\bmod {\,}}n)}$

Standart notlarda belirtildiği gibi, sadece gizli olmak için gerekli değildir , aynı zamanda farklı imzalar için farklı seçmek de çok önemlidir , aksi takdirde 6. adımdaki denklem özel anahtar için çözülebilir : iki imza verilir ve , aynı bilinmeyen farklı bilinen mesajlar için ve , bir saldırganın hesaplayabilir ve , ve o zamandan beri (bu paragrafta tüm işlemler bitti modülo vardır ) saldırgan bulabilirsiniz . Çünkü saldırgan artık özel anahtarı hesaplayabilir . ${\görüntüleme stili k}$${\görüntüleme stili k}$${\görüntüleme stili d_{A}}$${\görüntüleme stili (r,s)}$${\görüntüleme stili (r,s')}$${\görüntüleme stili k}$${\görüntüleme stili m}$${\görüntüleme stili m'}$${\görüntüleme stili z}$${\displaystyle z'}$${\displaystyle s-s'=k^{-1}(z-z')}$${\görüntüleme stili n}$${\displaystyle k={\frac {z-z'}{s-s'}}}$${\displaystyle s=k^{-1}(z+rd_{A})}$${\displaystyle d_{A}={\frac {sk-z}{r}}}$

Bu uygulama hatası, örneğin, PlayStation 3 oyun konsolu için kullanılan imzalama anahtarını çıkarmak için kullanıldı .

ECDSA imzasının özel anahtarları sızdırmasının başka bir yolu , hatalı bir rastgele sayı üreteci tarafından oluşturulduğu zamandır . Rastgele sayı üretimindeki böyle bir başarısızlık, Ağustos 2013'te Android Bitcoin Cüzdan kullanıcılarının fonlarını kaybetmesine neden oldu. ${\görüntüleme stili k}$

Bunun her mesaj için benzersiz olduğundan emin olmak için, rasgele sayı üretimini tamamen atlayabilir ve hem mesajdan hem de özel anahtardan türetilerek deterministik imzalar üretilebilir . ${\görüntüleme stili k}$${\görüntüleme stili k}$

İmza doğrulama algoritması

Bob'un Alice'in imzasını doğrulaması için, Alice'in açık anahtar eğri noktasının bir kopyasına sahip olması gerekir . Bob, aşağıdaki gibi geçerli bir eğri noktası olduğunu doğrulayabilir : ${\ Displaystyle Q_{A}}$${\ Displaystyle Q_{A}}$

1. O kimlik öğesine eşit olmadığını ve koordinatlarının aksi takdirde geçerli olup olmadığını kontrol edin.${\ Displaystyle Q_{A}}$
2. Eğrinin üzerinde olduğunu kontrol edin${\ Displaystyle Q_{A}}$
3. Şunu kontrol et ${\görüntüleme stili n\kez Q_{A}=O}$

Bundan sonra Bob şu adımları takip eder:

1. r ve s'nin içinde tamsayılar olduğunu doğrulayın . Aksi takdirde imza geçersizdir.${\görüntüleme stili [1,n-1]}$
2. HASH'ın imza oluşturmada kullanılan aynı işlev olduğu yerde hesaplayın .${\displaystyle e={\textrm {HASH}}(m)}$
3. Let Z olması en soldaki bit e .${\displaystyle L_{n}}$
4. Hesaplayın ve .${\displaystyle u_{1}=zs^{-1}\,{\bmod {\,}}n}$${\displaystyle u_{2}=rs^{-1}\,{\bmod {\,}}n}$
5. Eğri noktasını hesaplayın . Eğer o zaman imza geçersiz.${\displaystyle (x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}}$${\displaystyle (x_{1},y_{1})=O}$
6. İmza varsa geçerlidir , aksi takdirde geçersizdir.${\displaystyle r\eşdeğer x_{1}{\pmod {n}}}$

Etkili bir uygulamanın tersini yalnızca bir kez hesaplayacağını unutmayın . Ayrıca, Shamir'in hilesi kullanılarak, iki skaler çarpmanın toplamı, bağımsız olarak yapılan iki skaler çarpmadan daha hızlı hesaplanabilir. ${\displaystyle s^{-1}\,{\bmod {\,}}n}$${\displaystyle u_{1}\times G+u_{2}\times Q_{A}}$

Algoritmanın doğruluğu

Doğrulamanın neden düzgün çalıştığı hemen belli değil. Nedenini görmek için , doğrulamanın 5. adımında hesaplanan eğri noktasını C olarak belirtin ,

${\displaystyle C=u_{1}\times G+u_{2}\times Q_{A}}$

Genel anahtarın tanımından şu şekilde , ${\displaystyle Q_{A}=d_{A}\times G}$

${\displaystyle C=u_{1}\times G+u_{2}d_{A}\times G}$

Eliptik eğri skaler çarpımı toplama üzerinde dağıldığı için,

${\displaystyle C=(u_{1}+u_{2}d_{A})\times G}$

Tanımını genişletilmesi ve doğrulanması adım 4'den, ${\görüntüleme stili u_{1}}$${\ Displaystyle u_{2}}$

${\displaystyle C=(zs^{-1}+rd_{A}s^{-1})\times G}$

Ortak terimi toplamak , ${\görüntüleme stili ^{-1}}$

${\displaystyle C=(z+rd_{A})s^{-1}\times G}$

İmza adımından s tanımını genişletmek ,

${\displaystyle C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G}$

Tersinin tersi orijinal eleman olduğundan ve bir elemanın tersi ile elemanın çarpımı özdeşlik olduğundan, elimizde

${\görüntüleme stili C=k\times G}$

r tanımından , bu 6. adım doğrulamadır.

Bu, yalnızca doğru şekilde imzalanmış bir iletinin doğru şekilde doğrulanacağını gösterir; güvenli bir imza algoritması için diğer birçok özellik gereklidir.

Ortak anahtar kurtarma

Bir m mesajı ve Alice'in bu mesajdaki imzası verildiğinde, Bob (potansiyel olarak) Alice'in genel anahtarını kurtarabilir: ${\görüntüleme stili r,s}$

1. r ve s'nin içinde tamsayılar olduğunu doğrulayın . Aksi takdirde imza geçersizdir.${\görüntüleme stili [1,n-1]}$
2. Bir eğri noktası hesaplayın biri , , vb (Resim alan öğesi için çok büyük değildir) ve eğri denklemi tatmin şekilde bir değerdir. Bu koşulları karşılayan birkaç eğri noktası olabileceğini ve her farklı R değerinin ayrı bir kurtarılmış anahtarla sonuçlanabileceğini unutmayın.${\displaystyle R=(x_{1},y_{1})}$${\görüntüleme stili x_{1}}$${\görüntüleme stili r}$${\görüntüleme stili r+n}$${\görüntüleme stili r+2n}$${\görüntüleme stili x_{1}}$${\görüntüleme stili y_{1}}$
3. HASH'ın imza oluşturmada kullanılan aynı işlev olduğu yerde hesaplayın .${\displaystyle e={\textrm {HASH}}(m)}$
4. Let Z olması en soldaki bit e .${\displaystyle L_{n}}$
5. Hesaplayın ve .${\displaystyle u_{1}=-zr^{-1}\,{\bmod {\,}}n}$${\displaystyle u_{2}=sr^{-1}\,{\bmod {\,}}n}$
6. Eğri noktasını hesaplayın .${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$
7. İmza, Alice'in genel anahtarıyla eşleşirse geçerlidir .${\ Displaystyle Q_{A}}$
8. Tüm olası R noktaları denendiyse ve hiçbiri Alice'in açık anahtarıyla eşleşmediyse imza geçersizdir .

Geçersiz bir imzanın veya farklı bir iletiden alınan imzanın, yanlış bir ortak anahtarın kurtarılmasına neden olacağını unutmayın. Kurtarma algoritması, yalnızca imzalayanın ortak anahtarı (veya karma değeri) önceden biliniyorsa imzanın geçerliliğini kontrol etmek için kullanılabilir.

Kurtarma algoritmasının doğruluğu

Kurtarma adımı 6'nın tanımıyla başlayın , ${\ Displaystyle Q_{A}}$

${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$

4. adımın imzalanmasındaki tanımdan , ${\displaystyle R=(x_{1},y_{1})=k\times G}$

${\displaystyle Q_{A}=u_{1}\times G+u_{2}k\times G}$

Eliptik eğri skaler çarpımı toplama üzerinde dağıldığı için,

${\displaystyle Q_{A}=(u_{1}+u_{2}k)\times G}$

Tanımını genişletmek ve geri kazanım aşamasından 5'ten, ${\görüntüleme stili u_{1}}$${\ Displaystyle u_{2}}$

${\displaystyle Q_{A}=(-zr^{-1}+skr^{-1})\times G}$

İmza adımından s tanımını genişletmek ,

${\displaystyle Q_{A}=(-zr^{-1}+k^{-1}(z+rd_{A})kr^{-1})\times G}$

Bir elemanın tersinin çarpımı ve eleman özdeşlik olduğundan, elimizde

${\displaystyle Q_{A}=(-zr^{-1}+(zr^{-1}+d_{A}))\times G}$

Birinci ve ikinci terim birbirini götürür,

${\displaystyle Q_{A}=d_{A}\times G}$

tanımından , bu Alice'in ortak anahtarıdır. ${\displaystyle Q_{A}=d_{A}\times G}$

Bu, r imza değerinden eğri noktasını benzersiz bir şekilde hesaplamak için ek bilgilerin paylaşılması şartıyla, doğru imzalanmış bir mesajın doğru ortak anahtarı kurtaracağını gösterir . ${\displaystyle R=(x_{1},y_{1})}$

Güvenlik

Aralık 2010'da, kendini fail0verflow olarak adlandıran bir grup , Sony tarafından PlayStation 3 oyun konsolu için yazılım imzalamak için kullanılan ECDSA özel anahtarının kurtarıldığını duyurdu . Ancak bu saldırı, yalnızca Sony'nin algoritmayı düzgün bir şekilde uygulamadığı için işe yaradı, çünkü rastgele değil statikti. Yukarıdaki İmza oluşturma algoritması bölümünde belirtildiği gibi, bu , tüm algoritmayı işe yaramaz hale getirerek çözülebilir hale getirir . ${\görüntüleme stili k}$${\görüntüleme stili d_{A}}$

29 Mart 2011'de iki araştırmacı, bir zamanlama saldırısı yoluyla ikili alan üzerinden Eliptik Eğriler DSA ile kimlik doğrulaması yapan OpenSSL kullanan bir sunucunun TLS özel anahtarını almanın mümkün olduğunu gösteren bir IACR belgesi yayınladı . Güvenlik açığı OpenSSL 1.0.0e'de düzeltildi.

Ağustos 2013'te, Java sınıfı SecureRandom'un bazı uygulamalarındaki hataların bazen değerde çarpışmalar oluşturduğu ortaya çıktı . Bu, bilgisayar korsanlarının , Java kullanan ve kimlik doğrulaması için ECDSA'ya dayanan bazı Android uygulama uygulamalarında PS3 imzalama anahtarını ortaya çıkarmak için kullanılanla aynı istismarı kullanarak, meşru anahtarların sahipleri ile bitcoin işlemleri üzerinde aynı kontrolü sağlayarak özel anahtarları kurtarmalarına izin verdi. işlemler. ${\görüntüleme stili k}$

Bu sorun , örneğin RFC 6979 tarafından açıklandığı gibi deterministik bir prosedür gibi öngörülemeyen bir nesil tarafından önlenebilir . ${\görüntüleme stili k}$

endişeler

ECDSA hakkında ifade edilen bazı endişeler:

1. Politik kaygılar : NSA'nın yazılıma, donanım bileşenlerine ve yayınlanmış standartlara isteyerek arka kapılar eklediğinin ortaya çıkmasından sonra NIST tarafından üretilen eğrilerin güvenilirliği sorgulanıyor ; tanınmış kriptograflar, NIST eğrilerinin nasıl tasarlandığına dair şüphelerini dile getirdiler ve gönüllü lekelenme geçmişte zaten kanıtlandı. (Ayrıca libssh eğrisi25519 girişine bakın .) Bununla birlikte, NIST eğrilerinin nadir görülen bir zayıflıktan yararlandığına dair bir kanıt henüz yok.
2. Teknik kaygılar : Standardı düzgün bir şekilde uygulamanın zorluğu, yavaşlığı ve yetersiz defansif uygulamalarda güvenliği azaltan tasarım kusurları.

Uygulamalar

Aşağıda, ECDSA için destek sağlayan şifreleme kitaplıklarının bir listesi bulunmaktadır:

• Botanik
• Şişme kale
• cryptlib
• kripto++
• libgcrypt
• GnuTLS
• OpenSSL
• wolfCrypt
• LibreSSL
• mbed TLS
• Microsoft Şifreleme API'si
• Kripto API'si (Linux)

Örnek kullanım

Wikipedia.org, aşağıdaki kısaltılmış dökümde gösterildiği gibi, kendisini web tarayıcılarında doğrulamak için bir TLS şifre paketinde ECDSA kullanır.

$ date
Wed Mar  4 10:24:52 EST 2020
$ openssl s_client -connect wikipedia.org:443  # output below has DELETIONS for brevity
CONNECTED(00000003)
depth=2 O = Digital Signature Trust Co., CN = DST Root CA X3
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3
verify return:1
depth=0 CN = *.wikipedia.org
verify return:1
---
Certificate chain
 0 s:/CN=*.wikipedia.org
   i:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
 1 s:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
   i:/O=Digital Signature Trust Co./CN=DST Root CA X3
---
Server certificate
-----BEGIN CERTIFICATE-----
MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2/mMA0GCSqGSIb3DQEBCwUA
     ... many lines DELETED ....
kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw=
-----END CERTIFICATE-----
subject=/CN=*.wikipedia.org
issuer=/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
---
No client certificate CA names sent
Peer signing digest: SHA256
Server Temp Key: ECDH, P-256, 256 bits
---
SSL handshake has read 3353 bytes and written 431 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-ECDSA-AES256-GCM-SHA384
Server public key is 256 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-ECDSA-AES256-GCM-SHA384
    Session-ID:  ... DELETED ...
    Session-ID-ctx: 
    Master-Key:     ... DELETED ...
    Key-Arg   : None
    PSK identity: None
    PSK identity hint: None
    SRP username: None
    Start Time: 1583335210
    Timeout   : 300 (sec)
    Verify return code: 0 (ok)
---
DONE

Ayrıca bakınız

• EdDSA
• RSA (kriptosistem)

Referanslar

daha fazla okuma

• Akredite Standartlar Komitesi X9 , ASC X9 Açık Anahtar Kriptografisi/ECDSA için Yeni Standart Yayınladı , 6 Ekim 2020. Kaynak
• Accredited Standards Committee X9 , American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA) , 16 Kasım 2005.
• Certicom Research, Verimli kriptografi için standartlar, SEC 1: Eliptik Eğri Şifreleme , Sürüm 2.0, 21 Mayıs 2009.
• López, J. ve Dahab, R. Eliptik Eğri Kriptografisine Genel Bir Bakış , Teknik Rapor IC-00-10, Campinas Eyalet Üniversitesi, 2000.
• Daniel J. Bernstein , Pippenger'in üs alma algoritması , 2002.
• Daniel RL Brown, Genel Gruplar, Çarpışma Direnci ve ECDSA , Tasarımlar, Kodlar ve Kriptografi, 35 , 119–152, 2005. ePrint sürümü
• Ian F. Blake, Gadiel Seroussi ve Nigel Smart , editörler, Advances in Elliptic Curve Cryptography , London Mathematical Society Ders Notu Serisi 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S. ; Menezes, A. (2004). Eliptik Eğri Şifreleme Kılavuzu . Springer Profesyonel Bilgisayar. New York: Springer . doi : 10.1007/b97644 . ISBN'si 0-387-95273-X. S2CID  720546 .

Dış bağlantılar

• Dijital İmza Standardı; ECDSA hakkında bilgi içerir
• Eliptik Eğri Dijital İmza Algoritması (ECDSA); ECDSA hakkında derinlemesine bir kılavuz sağlar . geri dönüş bağlantısı