Informatik Security
Topic 5 RSA and DSA Digital Signatures
Topic 5 RSA and DSA Digital Signatures
Welches Problem lösen digitale Signaturen?
Die authentisierte Kommunikation zwei Parteien. Alice weiss, dass er mit Bob spricht.
Welche Bedingungen müssen erfüllt sein, damit Alice sich sicher sein kann, dass die Nachricht von Bob kommt.
Signing verification erfolgreich
Nur bob kennt private key
Alice verwendet public key von bob
Welche Funktionalitäten bieten Digitale Signaturen?
sender authenticity -> war 100% dieser absender der signiert hat
message integrity -> nachricht wurde nicht während der Übertragung manipuliert
non-repudiation -> nicht abweisbar
Aus was besteht ein digitales Signaturschema?
message space M
key generation: pk, sk <- keygen()
Signature genersation: s <- sign(m)
Verification: v= verify(s,m)
Was ist der Signature space S?
Alle von sign(m) gültig generierten signaturen
Zeichnen sie auf wie Alice eine signierte Nachricht generiert und diese an Bob zum überprüfen schickt.
Alice generiert keypair sk pk
Public key wird öffentlich bekannt gegeben
Alice generiert message aus message space
m wird mi sk signiert und generiert signatur
message und signatur wird an Bob übertragen
Bob kann nun verify auf message und signatur ausführen
Welche Applikationen / Beispiele verwenden digitale SIgnaturen?
Web Server Authentication
Secure mail
Code signing
Signed documents
digital certificates
timestamp server
etc
Wieso ist ist diese Art (encrypt-and-sign) von Verschlüsselung und signieren unsicher?
IND-CPA unsicher. Beim signieren kommt immer gleicher Hash raus von message
Entweder zuerst signieren, dann verschlüsseln oder umgekehrt.
Welche Sicherheitsmodelle müssen für digitale Signaturen existieren/berücksichtigt werden?
- Man kann/muss mit probabilistischen polynomialen (probabilistic polynomial-time (PPT)) Anrgreifern rechnen
- Existentially Unforgeability (EUF): mit einem pk, kann der Angreifen kein s und m generieren sodas verify(s,m)=true/1
- Choosen Message Attack (CMA): der Angreifer kann messages mittels einem Orakel signieren lassen.
- EUF-CMA = Existentially unforgeability under chosen-message attack (standard security model for digital signatures)
Wie sieht die Textbook RSA Signatur aus und was für Elemente beinhaltet diese?
wichtig: SOLLTE SO NICHT VERWENDET WERDEN
- n = multiplikative Gruppe Z*n
- e = multiplikative Gruppe von phi(n)
-d = e^-1 (multiplikatives inverses)
- pk = (n,e)
- sk = (n,d)
- Message space und Cypherspace = Z*n
verify () = true oder false
Wieso sollte die Textbook RSA Signatur nicht verwendet werden?
Nicht EUF-CMA sicher -> attacker kann einem Orakel messages zum signieren geben. Danach muss er selber eine Signatur zu einer Message finden die er dem Orakel noch nicht zum signieren gegeben hat.
Was sollte mit der Message gemacht werden bevor sie signiert wird?
Mit einer kollisionsressistentn Hashfunktion gehasht
Was ist RSA-SHA und wozu wird es verwendet?
Ist ein Verfahrung zum Authentisieren und Verschlüsseln. RSA wird für die Verschlüsselung verwendet und SHA256 für das Hasing der Message.
Egal wie gross der Input ist, der Output ist immer 2^256 bit lang.
Es gibt jedoch kein Beweis, dass er EUF-CMA sicher ist
Was ist RSA-FDH (full domain hash) / RSA-PSS (probabilistic signature scheme) und wozu wird es verwendet?
Ist ein Verfahrung zum Authentisieren und Verschlüsseln. RSA wird für die Verschlüsselung verwendet und Hashing für das Signieren.
Wobei eine Nachricht zuerst gehasht wird und anschließend eine beliebige Trapdoor-Einwegpermutation angewendet. Damit ist der Hash nicht deterministisch.
Da nicht deterministisch ist es EUF-CMA sicher unter der RSA Annahme.
Auf welches Problem basiert das DSA Verfahren?
Discrete logarithm problem
wie auch schnorr verfahren, eljamal/pointcheval verfahren
Was ist der grösste Vorteil von DL signatur schemas?
Man kan elliptische Kurven verwenden
Was ist der Vorteil von Elliptischen Kurven gegenüber Multiplikativen Zahlengruppen?
kürzere keys
kürzere signaturen
effizienter
vor allem für smartcard implementationen wichtig
Was ist der unterschied zwischen DSA und ECDSA?
ECDSA verwendet eulliptische Kurven für die Keygenerieren und DSA verwendet Z*n
Wie sieht die Keygeneriereun bei DSA aus und mit welchen Zahlen wird gearbeitet?
Zahlen Aus Gruppe G (und nicht Z*n) (kann jede Zahl sein) (n Zhalen möglich, jedoch Prim empfohlen)
q = Ordnung der Gruppe G
sk = zahlen von 0...q-1 da Zq (additive Gruppe)
g = generator von allen Elementen aus Gq
pk = Zahlen aus 1...q (element aus Gq )
z.B nehmen wir für G=11 da safe prime einfacher
11 = 2*q+1
q=5
Z*11 {1....10} -> multiplikative Gruppe von 11
Z5 {0....4} -> additive Gruppe von 5 -> Zq
Gq{1,3,4,5,9} da Generator g=4 all diese Zahlen in dieser Gruppe generieren kann mit g^sk -> Gq
Wie sieht die Signierung bei DSA aus und mit welchen Zahlen wird gearbeitet?
m = message
r = eine teilerfremde Zahl von q (ein Element aus Z*q)
s1 = hash(g^r) g^r wird gehasht
r^-1 = multiplikatives inverses von r
h = hash(m) message wird gehasht
s2 = r^1 * (h+sk * s1) mod q -> s2 muss zwingend elemnt von Z*q sein
s = kann ein Element von Zq oder von Z*q sein
Wie sieht die Verifizierung bei DSA aus und mit w2as für Zahlen wird gearbeitet?
h= hash der Nachricht aber Element von Zq
s^-1 = multiplikative Inverse von s2 und q = s^-1 ist Element aus Z*q
t = (g^h x pk^s1)s2-1 t ist Element von Gq
s = hash von t = entweder 1 oder 0
Ist DSA und ECDSA sicher? Wenn ja wie sicher und unter welcher Annahme?
EUF-CMA secure
Unter der DL annahme.
Bedingt aber, dass h1 und h2 randomisiert sind
Funktioniert DSA auch in Subgruppen? Wenn ja, in welchen?
Ja in Subgruppen von Gq von Z*p der Ordnung q
Wenn wir für p 3072 bit prim nehmen und für q 256 bit prim nehmen, wie gross ist die Signatur?
Wir übrigens für DSA empfohlen
2*256 = 512bit signatur
3072/256 security strenght s=128
ausserdem passen 256 perfekt für sha-256
Rechnen Sie folgendes Beispiel mit den DSA Algorithmen aus
-
- 1 / 25
-
Cartes-fiches
Welches Problem lösen digitale Signaturen?
Die authentisierte Kommunikation zwei Parteien. Alice weiss, dass er mit Bob spricht.
Welche Bedingungen müssen erfüllt sein, damit Alice sich sicher sein kann, dass die Nachricht von Bob kommt.
Signing verification erfolgreich
Nur bob kennt private key
Alice verwendet public key von bob
Welche Funktionalitäten bieten Digitale Signaturen?
sender authenticity -> war 100% dieser absender der signiert hat
message integrity -> nachricht wurde nicht während der Übertragung manipuliert
non-repudiation -> nicht abweisbar
Aus was besteht ein digitales Signaturschema?
message space M
key generation: pk, sk <- keygen()
Signature genersation: s <- sign(m)
Verification: v= verify(s,m)
Was ist der Signature space S?
Alle von sign(m) gültig generierten signaturen
Zeichnen sie auf wie Alice eine signierte Nachricht generiert und diese an Bob zum überprüfen schickt.
Alice generiert keypair sk pk
Public key wird öffentlich bekannt gegeben
Alice generiert message aus message space
m wird mi sk signiert und generiert signatur
message und signatur wird an Bob übertragen
Bob kann nun verify auf message und signatur ausführen
Welche Applikationen / Beispiele verwenden digitale SIgnaturen?
Web Server Authentication
Secure mail
Code signing
Signed documents
digital certificates
timestamp server
etc
Wieso ist ist diese Art (encrypt-and-sign) von Verschlüsselung und signieren unsicher?
IND-CPA unsicher. Beim signieren kommt immer gleicher Hash raus von message
Entweder zuerst signieren, dann verschlüsseln oder umgekehrt.
Welche Sicherheitsmodelle müssen für digitale Signaturen existieren/berücksichtigt werden?
- Man kann/muss mit probabilistischen polynomialen (probabilistic polynomial-time (PPT)) Anrgreifern rechnen
- Existentially Unforgeability (EUF): mit einem pk, kann der Angreifen kein s und m generieren sodas verify(s,m)=true/1
- Choosen Message Attack (CMA): der Angreifer kann messages mittels einem Orakel signieren lassen.
- EUF-CMA = Existentially unforgeability under chosen-message attack (standard security model for digital signatures)
Wie sieht die Textbook RSA Signatur aus und was für Elemente beinhaltet diese?
wichtig: SOLLTE SO NICHT VERWENDET WERDEN
- n = multiplikative Gruppe Z*n
- e = multiplikative Gruppe von phi(n)
-d = e^-1 (multiplikatives inverses)
- pk = (n,e)
- sk = (n,d)
- Message space und Cypherspace = Z*n
verify () = true oder false
Wieso sollte die Textbook RSA Signatur nicht verwendet werden?
Nicht EUF-CMA sicher -> attacker kann einem Orakel messages zum signieren geben. Danach muss er selber eine Signatur zu einer Message finden die er dem Orakel noch nicht zum signieren gegeben hat.
Was sollte mit der Message gemacht werden bevor sie signiert wird?
Mit einer kollisionsressistentn Hashfunktion gehasht
Was ist RSA-SHA und wozu wird es verwendet?
Ist ein Verfahrung zum Authentisieren und Verschlüsseln. RSA wird für die Verschlüsselung verwendet und SHA256 für das Hasing der Message.
Egal wie gross der Input ist, der Output ist immer 2^256 bit lang.
Es gibt jedoch kein Beweis, dass er EUF-CMA sicher ist
Was ist RSA-FDH (full domain hash) / RSA-PSS (probabilistic signature scheme) und wozu wird es verwendet?
Ist ein Verfahrung zum Authentisieren und Verschlüsseln. RSA wird für die Verschlüsselung verwendet und Hashing für das Signieren.
Wobei eine Nachricht zuerst gehasht wird und anschließend eine beliebige Trapdoor-Einwegpermutation angewendet. Damit ist der Hash nicht deterministisch.
Da nicht deterministisch ist es EUF-CMA sicher unter der RSA Annahme.
Auf welches Problem basiert das DSA Verfahren?
Discrete logarithm problem
wie auch schnorr verfahren, eljamal/pointcheval verfahren
Was ist der grösste Vorteil von DL signatur schemas?
Man kan elliptische Kurven verwenden
Was ist der Vorteil von Elliptischen Kurven gegenüber Multiplikativen Zahlengruppen?
kürzere keys
kürzere signaturen
effizienter
vor allem für smartcard implementationen wichtig
Was ist der unterschied zwischen DSA und ECDSA?
ECDSA verwendet eulliptische Kurven für die Keygenerieren und DSA verwendet Z*n
Wie sieht die Keygeneriereun bei DSA aus und mit welchen Zahlen wird gearbeitet?
Zahlen Aus Gruppe G (und nicht Z*n) (kann jede Zahl sein) (n Zhalen möglich, jedoch Prim empfohlen)
q = Ordnung der Gruppe G
sk = zahlen von 0...q-1 da Zq (additive Gruppe)
g = generator von allen Elementen aus Gq
pk = Zahlen aus 1...q (element aus Gq )
z.B nehmen wir für G=11 da safe prime einfacher
11 = 2*q+1
q=5
Z*11 {1....10} -> multiplikative Gruppe von 11
Z5 {0....4} -> additive Gruppe von 5 -> Zq
Gq{1,3,4,5,9} da Generator g=4 all diese Zahlen in dieser Gruppe generieren kann mit g^sk -> Gq
Wie sieht die Signierung bei DSA aus und mit welchen Zahlen wird gearbeitet?
m = message
r = eine teilerfremde Zahl von q (ein Element aus Z*q)
s1 = hash(g^r) g^r wird gehasht
r^-1 = multiplikatives inverses von r
h = hash(m) message wird gehasht
s2 = r^1 * (h+sk * s1) mod q -> s2 muss zwingend elemnt von Z*q sein
s = kann ein Element von Zq oder von Z*q sein
Wie sieht die Verifizierung bei DSA aus und mit w2as für Zahlen wird gearbeitet?
h= hash der Nachricht aber Element von Zq
s^-1 = multiplikative Inverse von s2 und q = s^-1 ist Element aus Z*q
t = (g^h x pk^s1)s2-1 t ist Element von Gq
s = hash von t = entweder 1 oder 0
Ist DSA und ECDSA sicher? Wenn ja wie sicher und unter welcher Annahme?
EUF-CMA secure
Unter der DL annahme.
Bedingt aber, dass h1 und h2 randomisiert sind
Funktioniert DSA auch in Subgruppen? Wenn ja, in welchen?
Ja in Subgruppen von Gq von Z*p der Ordnung q
Wenn wir für p 3072 bit prim nehmen und für q 256 bit prim nehmen, wie gross ist die Signatur?
Wir übrigens für DSA empfohlen
2*256 = 512bit signatur
3072/256 security strenght s=128
ausserdem passen 256 perfekt für sha-256
Rechnen Sie folgendes Beispiel mit den DSA Algorithmen aus
