Digitale Signaturen - Kryptografie - page 207

Mathematik des DSA
Um die Funktionsweise des DSA zu verstehen, müssen wir noch einmal auf die in
Abschnitt 11.1.1 behandelten mathematischen Grundlagen zurückgreifen. Dort
haben Sie erfahren, dass jede Gruppe vom Typ Z( p ,·) Untergruppen besitzt. Zu
jedem Teiler von p -1 gibt es genau eine Untergruppe. Zu jeder Untergruppe gibt es
mindestens einen Generator. Für uns ist nun folgende Fragestellung wichtig: Es sei
g ein Generator einer Untergruppe von Z( g ,·), b sei ein Element der von g generier-
ten Untergruppe und es gelte g x = b (mod p ). Ist unter diesen Voraussetzungen x
(der diskrete Logarithmus) einfacher zu berechnen, als wenn - wie bei Diffie-Hell-
man und ElGamal gefordert - g ein Generator von Z( g ,·) selbst ist? Man kann zei-
gen, dass die Antwort nein lautet. Die Kenntnis der generierten Untergruppe bietet
keinen Vorteil bei der Berechnung des diskreten Logarithmus - lediglich eine voll-
ständige Schlüsselsuche wird einfacher, aber das fällt nicht ins Gewicht, wenn die
Untergruppe groß genug ist. Diese Tatsache wird beim DSA ausgenutzt.
Funktionsweise des DSA
Für eine DSA-Signatur benötigen Alice und Bob wiederum eine große Primzahl p .
Außerdem wählt Alice eine Primzahl q , die ein Teiler von p -1 ist. q hat laut DSS-
Spezifikation eine Länge von 160 Bit, allerdings wäre auch eine andere Länge
sinnvoll möglich. Der Trick beim DSA gegenüber dem ElGamal-Verfahren
besteht darin, dass in der Untergruppe mit q Elementen gerechnet wird (es gibt
nur eine solche). Aus dieser Untergruppe wählt Alice einen Generator g . Nun
berechnet Alice ihr Schlüsselpaar. Sie wählt dazu einen privaten Schlüssel x < q ,
aus dem sie den öffentlichen Schlüssel g x (mod p ) berechnet. Diese Vorgehens-
weise entspricht der des ElGamal-Verfahrens, nur dass x < q gelten muss. Den
öffentlichen Schlüssel lässt Alice Bob zukommen, er benötigt ihn zum Verifizieren
von Alices Unterschriften.
Immer wenn Alice eine Nachricht m unterschreiben will, berechnet sie eine
Zufallszahl y , die kleiner als q ist. Aus y berechnet sie die Zahl
r =( g y (mod p )) (mod q ) und stellt anschließend folgende Gleichung auf:
m = y · s - x · r (mod q )
Hierbei sind x , y , m, r und g bekannt. Die neu eingeführte Variable s ist von die-
sen Größen abhängig und kann durch eine algebraische Umformung berechnet
werden. Die beiden Zahlen r und s bilden zusammen die digitale Signatur zur
Nachricht m . Beachten Sie, dass diese Gleichung der des ElGamal-Verfahrens
ähnelt. Es wird jedoch modulo q gerechnet, um in der Untergruppe der Größe q
zu bleiben. Außerdem sieht der DSA ein Minuszeichen statt einem Pluszeichen
vor - dieser Unterschied hat jedoch keine tiefere Bedeutung, sondern ist eine von
vielen Variationsmöglichkeiten für die Verifikationsgleichung. Die Verifikation
führt Bob dann mit folgender Gleichung durch:
g m = r s / g x· r (mod p )