Schnorr kimlik doğrulama protokolü
Gelen kriptografi , kimlik doğrulama protokolü Schnorr (in) (genellikle kısaltılan protokol Schnorr ) a, sıfır bilgi açıklama dayanıklı olan güvenlik sorununun zorluk dayanır Schorr tarafından 1989 de tarif ayrık logaritma ve ayrı bir logaritma bilgisini göstermek için kullanılır, verilen yani biz üs biliyoruz kanıtlamak, bir de grubun ürettiği .
gde{\ görüntü stili g ^ {a}}
de{\ görüntü stili a}
G{\ görüntü stili G}
g{\ görüntü stili g}![g](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
Bu protokol bir içine elde edilebilir dijital imza geçirmez hale getirerek etkileşimli olmayan tarafından Fiat-Shamir sezgisel . Bu dijital imza şeması, ABD'de 4,995,082 sayılı ABD Patenti altında patenti alınmıştır .Şubat 2008.
Diğer sıfır bilgi kanıtları gibi , Schnorr'un protokolü bir Σ protokolüdür: üç aşamada iki etkileşimli algoritma P ve V (Prover ve Verifier için) arasında bir protokol : katılım, meydan okuma ve yanıt.
Genel ayarlar
- Bir asal sayı . Aşağıda çarpma ile gösterilen, tarafından oluşturulan bir sipariş grubunu tanımladığını not ediyoruz .q{\ görüntü stili q}
G{\ görüntü stili G}
q{\ görüntü stili q}
g{\ görüntü stili g}![g](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
- Bir grup elemanı , sıra Bu, bir sıra alt grubunun bir oluşturucusudur .g{\ görüntü stili g}
q.{\ görüntü stili q.}
q{\ görüntü stili q}
G{\ görüntü stili G}
-
q,g{\ görüntü stili q, g}
halka açıktır.
Yalnızca Prover'ın bildiği veriler
- gelen rastgele bir tamsayı .s{\ görüntü stili s}
Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}![{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6eb475735278e18e2f0afe2927e312b6cc3865cd)
- Prover hesaplamakta ve bir tarafından onaylı, kamuoyuna açıklanmadan güvenilen otorite iken, gizli tutulur.v=gs{\ displaystyle v = g ^ {s}}
v{\ görüntü stili v}
s{\ görüntü stili s}![s](https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632)
İlk olarak, P bir katılım adımı başlatır:
-
P rasgele bir tam sayıyı çizer den .r{\ görüntü stili r}
Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}![{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6eb475735278e18e2f0afe2927e312b6cc3865cd)
-
P hesaplar ve gönderir için V$=gr{\ görüntü stili R = g ^ {r}}
${\ görüntü stili R}
Ardından meydan okuma aşaması başlar:
-
V bir tamsayıyı çeker içinde ve gönderir Pvs{\ görüntü stili c}
Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}
Son olarak, yanıt aşaması:
-
P hesaplar ve V'ye gönderir .de=r-vs⋅s{\ displaystyle a = rc \ cdot s}
![{\ displaystyle a = rc \ cdot s}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbad72a10dd03134c979e9865dc8d3da475c19a4)
V , ancak ve ancak protokolün sonunda ilişki doğrulanırsa kabul eder.
$=gde⋅vvs{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}![{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/feeee30bd943057678d12feaf69e13e07a2a8f73)
Güvenlik kanıtı
Bir protokolün Σ güvenliğini kanıtlamak için, dürüst bir doğrulayıcı altında eksiksizliği, özel sağlamlığı ve bilgi mülkiyetinin ifşa edilmediğini kanıtlamak yeterlidir.
eksiksizlik
Tamlık (veya doğruluk), protokolün dürüst bir seyri için doğrulayıcının her zaman tatmin olmasını gerektirir.
Bu, protokolün dürüstçe gerçekleştirilip gerçekleştirilmediği her zaman doğrulanan, şunu veren V kabul koşulu ile doğrulanır.
gde⋅vvs=gr-vs⋅s⋅gs⋅vs=gr=${\ displaystyle g ^ {a} \ cdot v ^ {c} = g ^ {rc \ cdot s} \ cdot g ^ {s \ cdot c} = g ^ {r} = R}![{\ displaystyle g ^ {a} \ cdot v ^ {c} = g ^ {rc \ cdot s} \ cdot g ^ {s \ cdot c} = g ^ {r} = R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5115d7e31d94d5e3b6639dda66d293f68a420bc7)
Özel sağlamlık
Özel sağlamlık, iki kabul eden transkripsiyon verildiği gibi polinom zamanında ve aynı genel parametreler altında çalışan bir bilgi çıkarıcı olduğunu söyler , daha sonra çıkarıcı sırrı döndürür .
($,vs,de){\ görüntü stili (R, c, a)}
($,vs′,de′){\ görüntü stili (R, c ', a')}
s{\ görüntü stili s}![s](https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632)
Schnorr protokolü durumunda aşağıdaki gibi çıkarıcı oluşturulur: Bu hesaplar ve dönecektir , çünkü bu değer karşılık ayrı logaritmasına par . Nitekim, transkripsiyonları ve kabul ediliyor, ilişkiler ve böylece vererek doğrulanır beri .
de-de′vs′-vs{\ görüntü stili {\ frac {a-a '} {c'-c}}}
v{\ görüntü stili v}
g{\ görüntü stili g}
($,vs,de){\ görüntü stili (R, c, a)}
($,vs′,de′){\ görüntü stili (R, c ', a')}
$=gde⋅vvs{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}
$=gde′⋅vvs′{\ displaystyle R = g ^ {a '} \ cdot v ^ {c'}}
g(de-de′vs′-vs)=v{\ displaystyle g ^ {\ sol ({\ frac {a-a '} {c'-c}} \ sağ)} = v}
vs≠vs′{\ görüntü stili c \ değil = c '}![{\ görüntü stili c \ değil = c '}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53108ffb10ad48ee6cd2d040769e05455617bf55)
Dürüst bir doğrulayıcı altında bilginin ifşa edilmemesi
Bu özellik, polinom zamanında çalışan, doğru bir sorgulama olarak nerede dağıtıldığı verildiğinde , simülatörün için gerçek bir transkripsiyon olarak dağıtılmış bir transkripsiyon döndüren olasılıklı bir simülatörün varlığı ile karakterize edilir . Simülatörün gizliliğe ihtiyacı olmadığını unutmayın.
(v,vs){\ görüntü stili (v, c)}
vs{\ görüntü stili c}
($,vs,de){\ görüntü stili (R, c, a)}
v{\ görüntü stili v}![v](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
Burada, simülatör bu nedenle taahhütten önce yanıtı üretecektir: tekdüze bir şekilde çekilecek ve üretecek, böylece kabul koşulunu kontrol edecek, yani , ve geri dönecektir . Tabana göre ayrık logaritması olduğu için düzgün dağıldığını görebiliriz . Ve inşaat tarafından kabul edilen bir yanıt olarak dağıtılır .
de{\ görüntü stili a}
Zq⋆{\ displaystyle \ mathbb {Z} _ {q} ^ {\ yıldız}}
${\ görüntü stili R}
$=gde⋅vvs{\ displaystyle R = g ^ {a} \ cdot v ^ {c}}
($,vs,de){\ görüntü stili (R, c, a)}
${\ görüntü stili R}
g{\ görüntü stili g}
de{\ görüntü stili a}
($,vs){\ görüntü stili (R, c)}![{\ görüntü stili (R, c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/560155e86fc0cdcb7cf24a64e84bc3fd4b7eeb18)
parametre boyutu
Patent spesifikasyon grubu belirtir bir grubun en az 140 bit bir alt grubu olarak seçilmelidir güvenlik 72 bit 512 bitlik bir asal sayıdır.
G{\ görüntü stili G}
Zp{\ displaystyle \ matematik {Z} _ {p}}
p{\ görüntü stili p}![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
imza şeması
Fiat-Shamir buluşsal yöntemi, tanımlama şemasını dijital imzaya dönüştürmek için kullanılabilir .
Bunun için, bir kriptografik (aile) hash fonksiyonu kamu parametrelerde dahil edilmesi ve meydan, rasgele seçim sırasında değerlendirilmesi ile değiştirilir mesaja karşılık imzalanacak. İmza çifte karşılık gelir ; doğrulama sırasında, doğrulayıcı, bu doğrulamanın geçip geçmediğini test eder ve kabul eder olarak yeniden hesaplanır . Tam açıklama aşağıda verilmiştir.
H:G×{0,1}∗→Zq⋆{\ displaystyle {\ matematik {H}}: G \ kez \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ yıldız}}
vs{\ görüntü stili c}
vs←H($,m){\ displaystyle c \ alır {\ matematik {H}} (R, m)}
m∈{0,1}∗{\ displaystyle m \ in \ {0,1 \} ^ {*}}
(vs,de){\ görüntü stili (c, a)}
${\ görüntü stili R}
$′=gde⋅vvs{\ displaystyle R '= g ^ {a} \ cdot v ^ {c}}
H($′,m)=vs{\ görüntü stili {\ matematik {H}} (R ', m) = c}![{\ görüntü stili {\ matematik {H}} (R ', m) = c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cbbbf8787ee432b6188ff622d181c9aad7b75b7)
Açıklama
Dijital imza, üçlü bir algoritma (GenClefs, Signer, Verify) tarafından verilir .
Anahtar üretimi:
- Genel parametreler ( ve ), Σ protokolüyle aynı şekilde oluşturulur.q{\ görüntü stili q}
g{\ görüntü stili g}![g](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3556280e66fe2c0d0140df20935a6f057381d77)
- Daha sonra bir hash işlevi oluşturulur ve genel parametrelere eklenir.H:G×{0,1}∗→Zq⋆{\ displaystyle {\ matematik {H}}: G \ kez \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ yıldız}}
![{\ displaystyle {\ matematik {H}}: G \ kez \ {0,1 \} ^ {*} \ to \ mathbb {Z} _ {q} ^ {\ yıldız}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81169dc3879f7f21b4acc6fdc50cdfb2c1d0a02f)
- Bir çift anahtar (vk, sk) ( doğrulama için v ve imza için s) oluşturmak için, imzalayan tek tip bir sayı çekerek başlar ve bunu kendi gizli anahtarı olarak tanımlar.s∈Zq⋆{\ displaystyle s \ in \ mathbb {Z} _ {q} ^ {\ yıldız}}
![{\ displaystyle s \ in \ mathbb {Z} _ {q} ^ {\ yıldız}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b9c0ab06124de5187595cbf94195bc74deb257f)
- İmzalayan daha sonra hesaplayacak ve bunu kendi genel anahtarı olarak yayınlayacaktır.v=gs{\ displaystyle v = g ^ {s}}
![{\ displaystyle v = g ^ {s}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f75674005ee930da1ebc2f701fde9a0e22ceda5c)
İmza ( sk, m ):
- Bir mesajı imzalamak için, imzalayan rasgele bir sayı çizerek başlayacak ve tanımlayacaktır .r∈Zq⋆{\ displaystyle r \ in \ mathbb {Z} _ {q} ^ {\ yıldız}}
$=gr{\ görüntü stili R = g ^ {r}}![{\ görüntü stili R = g ^ {r}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36b6fbb4593ec895bdeb7834ee5ec0789578d8bd)
- "Meydan okuma" daha sonra olarak oluşturulacak ve yanıt olarak hesaplanacaktır .vs=H($,m){\ görüntü stili c = {\ matematiksel {H}} (R, m)}
de=r-vs⋅sk∈Zq{\ displaystyle a = rc \ cdot {\ mathsf {sk}} \ in \ mathbb {Z} _ {q}}![{\ displaystyle a = rc \ cdot {\ mathsf {sk}} \ in \ mathbb {Z} _ {q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f18a4bac6e60c484a6c697c0cbabec5ba9c4da7)
- Sonunda imza döndürülür: .σ=(vs,de){\ görüntü stili \ sigma = (c, a)}
![{\ görüntü stili \ sigma = (c, a)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14c65b1b1128ab8eee4417d78b1d09ff28688cc0)
Doğrulama ( vk, m, σ ):
- İmzayı doğrulamak için , bir kullanıcı önce genel anahtarı kullanarak yeniden hesaplar : .σ=(vs,de){\ görüntü stili \ sigma = (c, a)}
${\ görüntü stili R}
$′=gde⋅vkvs{\ displaystyle R '= g ^ {a} \ cdot {\ mathsf {vk}} ^ {c}}![{\ displaystyle R '= g ^ {a} \ cdot {\ mathsf {vk}} ^ {c}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64d19de028d4130e34b229db957725b8106952f5)
- Kullanıcı daha sonra ancak ve ancak .H($′,m) =? vs{\ displaystyle {\ matematik {H}} (R ', m) ~ {\ taşan {?} {=}} ~ c}
![{\ displaystyle {\ matematik {H}} (R ', m) ~ {\ taşan {?} {=}} ~ c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1de466fbeebd18b6a6cfdc5553e6ba05f0eacd0)
verimlilik
Bu , 72 bit güvenlik için minimum patent önerilerini izleyen bir imza boyutuyla sonuçlanır .
|vs|+|de|=280 bit=35 bayt{\ displaystyle | c | + | a | = 280 {\ mbox {bits}} = 35 {\ mbox {bytes}}}![{\ displaystyle | c | + | a | = 280 {\ mbox {bits}} = 35 {\ mbox {bytes}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/790569f895ef8f02cef2f3447a4f70fb90638f10)
Kanıtlanmış güvenlik
Pointcheval ve Stern 1996'da, eğer altta yatan tanımlama şeması güvenliyse , rastgele kehanet modelinde Fiat-Shamir buluşsal yönteminin güvenli olduğunu gösterdi .
Notlar ve referanslar
-
Schnorr 1989 .
-
Feige, Fiat ve Shamir 1988 .
-
Fiat ve Shamir 1986 .
-
Damgård 2010 .
-
Pointcheval ve Stern 1996 .
Ekler
bibliyografya
- [Feige Fiat ve Shamir 1988] (tr) Uriel Feige, Amos Fiat ve Adi Shamir , “ Zero-knowledgeproofs ofkimlik ” , Journal of Cryptology ,1988( DOI 10.1007 / BF02351717 )
- [Fiat ve Shamir 1986] (tr) Amos Fiat ve Adi Shamir , “ Kendinizi Nasıl Kanıtlarsınız: Kimlik ve İmza Sorunlarına Pratik Çözümler ” , Crypto 1986 ,1986( çevrimiçi okuyun [PDF] )
- [Schnorr 1989] (tr) Claus-Peter Schnorr , “ Akıllı Kartlar için Etkin Tanımlama ve İmza ” , Kriptoloji Teorisi ve Uygulaması , Springer,1989( çevrimiçi okuyun )
- [Pointcheval ve Stern 1996] (tr) David Pointcheval ve Jacques Stern , " İmza Planları için Güvenlik Kanıtları " , Eurocrypt ,1996( çevrimiçi okuyun [PDF] )
İlgili Makaleler
Dış bağlantılar
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">