Cryptography Reference
In-Depth Information
Die Erfüllung der Kongruenz in (4.4-14) zeigt die folgende Kontrollrechnung. Dabei wird
m=d·+r·s+i·(p1), i
¢ , aus (4.4-11) gewonnen und in (4.4-14) eingesetzt:
g
md
g
3
r s
i (p
1)
g
d
3
r s
(g )
d
3
(g )
r
s
e
3
s
(mod p)
(4.4-15)
Bei der zweiten Kongruenz wird davon Gebrauch gemacht, dass in der Arithmetik mod p auf
die Exponenten die Arithmetik mod (p1) angewendet werden kann (Kleiner Satz von Fermat,
(4.1-11) in Abschn. 4.1.2.2). Bei der letzten Kongruenz werden (4.4-2) und (4.4-10) verwen-
det. Damit ist gezeigt, dass (4.4-14) für eine gültige, signierte Nachricht erfüllt sein muss.
Anmerkungen
1.) Die Nachricht m muss kleiner als p1 sein: m<p1. D.h. die Länge l m der Nachricht darf
die Länge l p des Moduls nicht übersteigen. Andernfalls würde eine konstruierte Nachricht
* mmi (p )
mit
i
¢
(4.4-16)
die Bedingung (4.4-15) ebenfalls erfüllen, wenn die Signatur von m verwendet wird. In einer
Anwendung wird üblicherweise nicht die Nachricht m direkt, sondern ihr Hash-Wert h(m)
signiert. Für den Hash-Wert kann h(m)<p1 ohne Einschränkung erfüllt werden. In den For-
meln dieses Abschnitts ist dann m durch h(m) zu ersetzen, ausgenommen in (4.4-13): Die
Nachricht m muss selbstverständlich übertragen werden, den Hash-Wert h(m) kann sich der
Empfänger aus m selbst ermitteln.
2.) Es ist wichtig, die Zufallszahl r mit r 1 und dem Nachrichtenbezeichner nur für eine
Nachricht m 1 keinesfalls für eine neue Nachricht m 2 zu verwenden. Wenn eine Zufallszahl
wieder verwendet wird, kann das Signaturelement s und -schlimmer noch- der private Schlüs-
sel d aus (4.4-11) berechnet werden. Übung : Stellen Sie das entsprechende Gleichungssystem
auf.
3.) Die digitale Signatur nach ElGamal liefert die Dienste der Verbindlichkeit (Nicht-
Abstreitbarkeit) und damit der Authentizität des Unterzeichners sowie der Integrität der Nach-
richt. Falls Vertraulichkeit gewünscht wird, muss die Nachricht m in (4.4-13) gesondert ver-
schlüsselt werden. Dazu kann der Schlüsselaustausch nach ElGamal verwendet werden
(Abschn. 4.4.1).
4.4.3 Effizienz des ElGamal-Verfahrens
Für den Schlüsselaustausch muss der Sender zwei Potenzierungen modulo p durchführen. Im
Vergleich zu RSA wird für den Modul p eine ähnliche Länge l p vorgeschlagen wie für die
Länge l n des Moduls n bei RSA. Bei RSA wird für die Verschlüsselung eines Sitzungsschlüs-
sels k nur eine Potenzierung benötigt. Für diesen Fall benötigt ElGamal den doppelten Auf-
wand.
Für die Entschlüsselung des Sitzungsschlüssels ist für ElGamal und RSA jeweils eine Poten-
zierung erforderlich. Für diesen Fall ist der Aufwand gleich.
Für die digitale Signatur benötigt ElGamal eine Zufallszahl r, die Berechnung der Inversen r 1
mit dem erweiterten Euklidischen Algorithmus, eine Potenzierung zur Berechnung von und
schließlich zwei Multiplikationen zur Berechnung von s. Verglichen mit einer Potenzierung
Search WWH ::




Custom Search