Digitálne podpisy
OBSAH
Digital signatures
ElGamal
DSA
Subliminal channels
Blind signatures
Undeniable signatures
One – Time signatures & Timestamping
ElGamal signature scheme
ElGamal sig. scheme
schéma digitálneho
podpisu
prvýkrát použitá
egyptským
kryptografom Dr. Taher
El Gamalom v roku
1984
1
ElGamal signature scheme
ElGamal sig. scheme 2
zvolíme prvočíslo p a celé čísla q, x také, že 1≤q≤x≤p
kde q je elemet zo Zp
*
zrátame y=qx
mod p
kľúč K(p,q,x,y)
verejná časť k = p,q,y
súkromná časť - x
ElGamal signature scheme
ElGamal sig. scheme 3
podpísanie správy w:
● náhodne zvolíme r; r ∈ Z p-1*
hodnotu uchováme tajnú
sig(w,r) = (a,b)
a = qr
mod p
b = (w-x*a)*r-1
mod (p-1)
overenie podpisu: ya
ab
≡ qw
mod p
ElGamal signature scheme - bezpečnosť
ElGamal sig. scheme 4
Predpokladajme, že sa Eve pokúsi sfalšovať
sig (a,b) bez toho aby poznala hodnotu x.
ak si zvolí hodnotu a, bude k nej musieť nájsť
korešpondujúcu hodnotu b spočítaním diskrétneho
logaritmu loga
qw
y-a
pretože platí:
a b
≡ q r (w - xa) r^(-1)
≡ q w - xa
≡ q w
y -a
ak si zvolí hodnotu b a bude chcieť nájsť hodnotu a
musí vyriešiť rovnicu:
y a
a b
≡ q xa
q rb
≡ q w
(mod p)
Nie je známe, či má predchádzajúca rovnica
efektívne riešenie pre ľubovolnú hodnotu a.
ElGamal signature scheme - bezpečnosť
ElGamal sig. scheme 5
Ak si Eve zvolí obe hodnoty a, b a bude chcieť
určiť správu w, musí zrátať diskrétny logaritmus
log q y a
a b
.
Preto nemôže podpísať náhodnú správu týmto
spôsobom.
Digital signature algorithm
DSA sig. scheme 6
bol navrhnutý v roku 1991 americkým inštitútom
NIST a v roku 1994 bol prijatý za štandard
autor: David W. Kravitz
algoritmus je založený na probléme výpočtu
diskrétneho logaritmu
modifikácia algoritmu ElGamal.
Návrh algoritmu
DSA sig. scheme 7
1. výber komponentov verejného kľúča:
p – náhodne zvolené l-bitové prvočíslo,
512 ≤ l ≤ 1024, l = 64k.
q – náhodne zvolené 160-bitové prvočíslo,
tak, že p-1 mod q = 0
r = h (p –1)/q
mod p, kde h je náhodný element zo Zp
r > 1
2. výber komponentov privátneho kľúča:
x – náhodne zvolené celé číslo, 0 < x < q
y – rx
mod p
3. Kľúč je K = (p,q,r,x,y)
Podpísanie správy a overenie podpisu
DSA sig. scheme 8
Podpísanie 160-bitového nešifrovaného textu w
náhodne zvolíme 0 < k < q tak, aby gcd(k, q) = 1
vypočítame a = (r k
mod p) mod q
vypočítame b = k -1
(w + xa) mod q kde kk -1
≡ 1 (mod
q)
podpis: sig(w, k) = (a, b)
Overenie podpisu (a,b)
vypočítame z = b -1
mod q
vypočítame u1 = wz mod q, u2 = az mod q
ver K(w, a, b) = true <=> ( mod p) mod q = ar
u1
y
u2
ElGamal vs. DSA
DSA sig. scheme 9
ElGamal
nie je bezpečnejší ako diskrétny logaritmus =>
nutnosť použiť veľké p (min. 512b)
Podpisy príliš veľké (min 1024b) pre určité
aplikácie (čipové karty)
DSA
redukcia exponentov r, y a a mod q bez
ovplyvnenia overovacej podmienky
y a
a b
= q w
DSA - použitie
DSA sig. scheme 10
široké využitie, napríklad v
OpenSSL
OpenSSH
GnuPG
Subliminal channels
ElGamal sig. scheme 11
proces skrývania tajnej správy do inej „nevinne“
vyzerajúcej správy.
objavil ich v digitálnych podpisoch v roku 1984 Gustavus
Simmons.
broadband channels
narrow-band channels
Subliminal channels - delenie
ElGamal sig. scheme 12
Broadband
"Hello, how do you do?" - môže reprezentovať tajnú správu
1
Dôvod??
Narrow-band
Využiteľné vo všetkých schémach digitálnych podpisov
Ong-Schnorr-Shamir subliminal channel
Ong-Schnorr-Shamir
ElGamal sig. scheme 13
Najprv sa zvolia n, k tak, že gcd(n,k) = 1
Spočítame h = mod n
Verejné kľúče h, n , sukromný kľúč k
Pre poslanie správy w' je potrebné spočítať
gcd(w,n) = gcd(w',n) = 1
k−1
2
Posiela sa (w ', S 1, S 2)
Tretia strana kontroluje, či sa platí w ' = S 1
2
– hS 2
2
(mod n)
Príjemca získa tajné w z nasledujúcej rovnice
( )
( ) nwS
nwS
w
wk
w
w
mod
mod
'
'
22
2
1
1
−⋅=
+⋅=
( ) .mod
2
1
1
'
nw SkS
w
−
+
=
Ong-Schnorr-Shamir - ukážka
ElGamal sig. scheme 14
Dané n= 4568, k= 3465, h= 913, w´= 15 a w= 9.
Ako prvé potrebujeme spočítať w -1
= 3553.
Následne podpisy
Verifikácia
Získanie tajnej správy
Blind signatures
Blind signatures 15
David Chaum
2 skupiny
Obsah správy je maskovaný (zaslepený)
Základný predpoklad: Signer na podnet Sendera
podpíše správu m bez toho, aby sa Signer
dozvedel, čo sa nachádza v správe m
Možnosť verejného overenia výsledného
slepého podpisu
Blind signatures – použitie
Blind signatures 16
Anonymita správy
Použitie v protokoloch kde záleží na súkromí
1. e-commerce
2. kryptografické volebné systémy
3. Digitálne platobné systémy
Nelinkovateľnosť – zabránenie prepojenia u
Signer-a medzi maskovanou správou a
nemaskovanou správou slúžiacou na overenie
Príklad – volebná obálka
Blind signatures – použitie
Blind signatures 17
Aby bolo možné podpísať (Signer vlastní tajný
podpisovací ľúč) správu m, Sender vypočíta, s
využitím postupu zamaskovania, m*, ktoré sa nedá
získať z m bez znalosti tajomstva, a pošle m*
Signer-ovi.
Signer podpíše m*, čím sa získa podpis sm* (z m*)
a pošle sm* Sender-ovi. Podpisovanie sa vykonáva
tak, že Sender môže potom vypočítať, s použitím
postupu odmaskovania, z podpisu Signer-a sm* z
m* - Signer-ov podpis sm z m.
Blind signatures – Chaumova schéma
Blind signatures 18
Využitie RSA a vlastnosti maskovania/odmaskovania
B (Bob) má verejný kľúč (n,e) a súkromný kľúč d
Nech m je správa, 0 < m < n
1. A (Alice) vyberie náhodné 0 < k < n s NSD(n,k)=1
2. A spočíta m* = mke
(mod n) [maskovanie správy] a
pošle B
3. B spočíta s* = (m*)d
(mod n) a pošle A [podpis
maskovanej správy]
4. A spočíta s = k-1
s* (mod n), aby získala B podpis md
správy m [A vykoná odmaskovanie m*]
Verifikácia je ekvivalentná RSA podpisovej schéme
Blind signatures – riziká
Blind signatures 19
Podpisovanie – dešifrovanie
Útočník pošle zašifrovanú správu, ktorú
odpozoroval a chce sa dozvedieť jej obsah
1. Odmaskovanie: m’’ = m’re
(mod n) = (me
(mod n).re
)
(mod n) = (mr)e
(mod n) [m’ je zašifrovaná správa
určená na podpis]
2. Získanie m: s’ = m’’d
(mod n) = ((mr)e
(mod n))d
(mod
n) = (mr)ed
(mod n) = m.r (mod n)
Útok funguje, pretože Signer podpisuje správu
priamo.
Nemožno použiť hash funkcie na správu,
Kľuč na podpisovanie – kľúč na dešifrovanie
Undeniable signatures
Undeniable signatures 20
Vlastnosti nepopierateľného podpisu:
podpis môže byť verifikovaný iba v kooperácii
s podpisovateľom
podpisovateľ nemôže poprieť korektnosť
podpisu
NP pozostáva z troch komponent:
podpisový algoritmus
verifikačný algoritmus
a tzv. Disawoval protocol
Undeniable signatures - použitie
Undeniable signatures 21
Nepopierateľný podpis chráni podpisovateľa
pred duplikovaním a distribuovaním dokumentov
bez jeho zvolenia
Chráni podpisovateľa pred popretím toho, čo už
v minulosti podpísal
Undeniable signatures - príklady
Undeniable signatures 22
Entita A (zákazník) chce získať prístup k
chránenej oblasti riadenej entitou B (banka).
Pokiaľ A použije nepopierateľný podpis, B
nemôže nikomu inému dokázať, že A použila
zariadenie bez jeho účasti.
A vytvorí zásielku, podpíše ju a pošle entite B. B
nemôže poslať zásielku C bez účasti entity A vo
verifikačnom procese.
Undeniable signatures – CAUSS schéma
Undeniable signatures 23
Chaum-van Antwerpen undeniable signature
scheme
Undeniable signatures – Disavowal protocol
Undeniable signatures 24
Undeniable signatures – dôsledok
Undeniable signatures 25
Bob môže presvedčiť Alicu, že neplatný podpis je
podvrh
stačí dokázať, že pokiaľ
potom:
Bob nemôže Alicu presvedčiť, že platný podpis je
podvrh (až na veľmi malú pravdepodobnosť)
One – time signature
One-time signatures & Timestamping 26
Lamport signature
One-time signatures & Timestamping 27
Lamport signature
One-time signatures & Timestamping 28
Lamport signature
One-time signatures & Timestamping 29
Lamport signature
One-time signatures & Timestamping 30
Timestamping
One-time signatures & Timestamping 31
Timestamping
One-time signatures & Timestamping 32
Timestamping
One-time signatures & Timestamping 33
Timestamping
One-time signatures & Timestamping 34
Ďakujeme za pozornosť