Kryptografische Protokolle

DSA-Signaturverfahren (Digital Signature Algorithm)

Das DSA-Signaturverfahren erzeugt für ein beliebig langes Dokument m eine Signatur (r, s), bestehend aus zwei Zahlen r und s jeweils der Länge 160 Bit.

Verfahren

Öffentlich bekannt sind die Hashfunktion h sowie die Zahlen p, q und g. Kommunikationspartner A verwendet diese Zahlen als Teil seines öffentlichen Schlüssels; hinzu kommt noch die Zahl e. Als privaten Schlüssel verwendet A eine zufällig gewählte Zahl d.

Um ein Dokument m zu signieren, bildet A zunächst den Hashwert h(m) des Dokuments mittels der Hashfunktion SHA-1. Dann berechnet A unter Verwendung seines privaten Schlüssels d und einer Zufallszahl k zwei Zahlen r und s. Diese beiden Zahlen stellen die Signatur des Dokuments m dar.

Anschließend sendet A das Tripel (m, r, s) an den Kommunikationspartner B. Dieser prüft die Signatur, indem er zunächst ebenfalls den Hashwert h(m) des empfangenen Dokuments m bildet und danach unter Verwendung von e, des öffentlichen Schlüssels von A, einen Wert z berechnet.

Kommunikationspartner B erkennt die Signatur als gültig an, wenn z = r gilt.

Mathematische Grundlage

Das DSA-Signaturverfahren verwendet eine Primzahl p sowie eine Primzahl q, die ein Teiler von p-1 ist.

Die multiplikative Gruppe ℤp* ist zyklisch, da p Primzahl ist, und sie hat p-1 Elemente. Da q ein Teiler von p-1 ist, enthält sie eine Untergruppe U mit q Elementen, also der Ordnung q.

Als Untergruppe einer zyklischen Gruppe ist U ebenfalls zyklisch, wird also von einem Element g mit ord(g) = q erzeugt.

Das DSA-Signaturverfahren verwendet ein solches erzeugendes Element g, das die Untergruppe U der Ordnung q von ℤp* erzeugt.

Ablauf des Verfahrens

 

         A          C          B
 Hashfunktion h 
 Primzahl p
Primzahl q mit  q | p-1
Zahl g ∈ ℤp* mit
ord(g) = q		 
Schlüssel erzeugen  
wählt
   Zufallszahl d ∈ {2, ..., q-2}
   (privater Schlüssel)		  
berechnet
   e = gd mod p
   (öffentlicher Schlüssel)		  
  
Schlüssel
veröffentlichen		  
             e 
Signatur erstellen  
wählt
   Zufallszahl k ∈ {2, ..., q-2}		  
berechnet
   r = gk mod p mod q
   s = (h(m) + d·r)·k-1 mod q		  
        
  Signatur prüfen
  berechnet
   u = s-1·h(m) mod q
   v = s-1·r mod q
  berechnet
   z = gu·ev mod p mod q
  vergleicht ob
   r = z

 

Bild 1: Ablauf des DSA-Signaturverfahrens

 

Nach dem DSA-Standard ist p eine Primzahl der Länge 1024 Bit und q eine Primzahl der Länge 160 Bit. Die Länge der Signatur (r, s) beträgt somit 320 Bit.

Als Hashverfahren h ist der SHA-1-Algorithmus vorgesehen. Die Länge der von SHA-1 berechneten Hashwerte beträgt 160 Bit.

Der DSA-Standard erlaubt auch noch höhere Sicherheit mit Längen für p von 2048 bzw. 3072 Bit und entsprechend für q von 224 bzw. 256 Bit und damit für die Signatur (r, s) von 448 bzw. 512 Bit. In diesen Fällen werden entsprechend Hashverfahren mit 224 bzw. 256 Bit langen Hashwerten verwendet.

Bemerkung:  Bei der Berechnung der Signatur wird modulo q gerechnet. Es kann sein, dass hierdurch der Wert s = 0 herauskommt. Dann wäre aber beim Prüfen der Signatur die Berechnung s-1 nicht möglich, daher ist der Wert s = 0 nicht zulässig. Auch für r ist der Wert 0 nicht zulässig. Wenn dies vorkommt, wird die Signatur einfach mit einer anderen Zufallszahl k erneut berechnet – so lange, bis r ≠ 0 und s ≠ 0 gilt. Bei der verwendeten sehr großen Zahl q ist es jedoch äußerst unwahrscheinlich, dass bei der Reduktion modulo q einer der Fälle r = 0 oder s = 0 auf­tritt.

Beispiel mit kleinen Zahlen

Zur Veranschaulichung der durchgeführten Berechnungen folgt ein Beispiel mit kleinen Zahlen. Der Hashwert h(m) des Dokuments m sei 13.

 

         A          C          B
 Hashfunktion h 
 Primzahl p =67
Primzahl q = 11 mit  q | p-1
Zahl g = 9 mit
g ∈ ℤp*, ord(g) = q		 
Schlüssel erzeugen  
wählt
   Zufallszahl d = 7
   (privater Schlüssel)		  
berechnet
   e = gd mod p =
   97 mod 67 = 40
   (öffentlicher Schlüssel)		  
  
Schlüssel
veröffentlichen		  
          e = 40 
Signatur erstellen  
wählt
   Zufallszahl k = 8		  
berechnet
   r = gk mod p mod q = 
   98 mod 67 mod 11 = 3
   s = (h(m) + d·r)·k-1 mod q =
   (13 + 7·3)·7 mod 11 = 7		  
        
  Signatur prüfen
  berechnet
   s -1 mod q = 7-1 mod 11 = 8
   u = s-1·h(m) mod q = 8·13 mod 11 = 5
   v = s-1·r mod q = 8·3 mod 11 = 2
  berechnet
   z = gu·ev mod p mod q = 
   95·402 mod 67 mod 11 = 3
  vergleicht ob
   r = z
   3 = 3

 

Bild 2: Veranschaulichung des DSA-Signaturverfahrens mit kleinen Zahlen

 

Korrektheit

Es ist zu zeigen, dass bei der Prüfung der Signatur die Bedingung r = z erfüllt ist.

Vorausgesetzt ist, dass s ≠ 0 gilt. Dann gilt

s  ≡  (h(m) + d·r)·k-1   (mod q)

Multiplikation mit k und s-1 ergibt

k  ≡  s-1·h(m) + d·s-1·r   (mod q)

Mit den beim Prüfen der Signatur verwendeten Variablen u und v ergibt dies

k  ≡  u + d·v   (mod q)

Weil g die Ordnung q in ℤp* hat, gilt

gk  ≡  gu + d·v  ≡  gu · gd·v   (mod p)

Mit der Beziehung e = gd mod p zwischen öffentlichem Schlüssel e und privatem Schlüssel d ergibt sich durch Einsetzen

gk  ≡  gu · ev   (mod p)

Indem beide Seiten modulo p reduziert werden, ergibt sich

gk mod p  =  gu · ev mod p

Eine weitere Reduktion modulo q ergibt

gk mod p mod q  =  gu · ev mod p mod q

Damit folgt

r  =  z

Sicherheit

Die Sicherheit beruht auf der Schwierigkeit, diskrete Logarithmen zu berechnen (Discrete Logarithm Problem – DLP). Bei den verwendeten großen Zahlen ist es undurchführbar, aus dem öffentlichen Schlüssel e den privaten Schlüssel d zu berechnen.

Des Weiteren ist zu beachten: Kommunikationspartner A muss die Zufallszahl k für jede zu erstellende Signatur neu wählen, er darf sie nicht wiederverwenden. Beim Prüfen der Signatur muss Kommunikationspartner B sicherstellen, dass die Bedingungen 0 < r < q und 0 < s < q gelten.

Berechnungsverfahren

Zu berechnen sind die Primzahlen p und q mit q | p-1 sowie das Element g der Ordnung q in ℤp*.

Primzahlen p und q

Zunächst wird in der folgenden Funktion findPrimes die kleinere Primzahl q zufällig gewählt. Ausgehend von q werden dann zufällige Vielfache von 2q daraufhin geprüft, ob sie gleich p-1 mit p Primzahl sind. Wenn nach 8192 Versuchen noch keine Primzahl p gefunden worden ist, wird eine neue Primzahl q gewählt und von vorne angefangen. Wenn dies nach 10 Durchläufen nicht zum Erfolg führt, bricht das Verfahren ab.

 

# Berechnet Primzahl p der Laenge lenp (z.B. 512) und 
# Primzahl q der Laenge lenq (z.B. 160) mit q | p-1
def findPrimes(lenp, lenq):
    for i in range(10):
        q=randomPrime(lenq)
        for j in range(8192):
            m=randomInt(lenp)
            mr=m % (2*q)
            p=m-mr+1
            if isPrime(p):
                return p, q
    return 0, 0

 

Die Funktionen randomInt, randomPrime und isPrime werden aus dem Modul Prime importiert.

Die Funktion lässt sich mit folgendem Programm testen:

# Test
if __name__ == "__main__":
    p, q=findPrimes(512, 160)
    print(p)
    print(q)

 

Hinweis: Ab ungefähr lenp=680 wird der Algorithmus langsam. In der Praxis ist es sinnvoll, die Primzahlen bei der Erstellung eines Zertifkats durch eine Zertifizierungsstelle erzeugen zu lassen.

Element g der Ordnung q

Gesucht ist ein erzeugendes Element g der Untergruppe U der Ordnung q von ℤp*. Da q Primzahl, enthält U keine weiteren Untergruppen außer {1} und sich selbst. Damit ist jedes Element von U außer der 1 ein erzeugendes Element von U.

Ein erzeugendes Element u von U lässt sich ausgehend von einem erzeugenden Element a von ℤp* bestimmen. Mit y = (p-1)/q ist nämlich u = ay ein erzeugendes Element von U. Wie aber findet man ein erzeugendes Element a von ℤp*? Im Allgemeinen ist dies schwer, denn hierzu ist die Kenntnis von allen Teilern von p-1 erforderlich.

Indem jedoch einfach ein beliebiges Element b = ax ∈ ℤp* hergenommen und by = axy = ux = g berechnet wird, ergibt sich auch ein Element g ∈ U, und da alle Elemente von U erzeugende Elemente von U sind – bis auf die 1 – ist die Wahrscheinlichkeit groß, dass g erzeugendes Element ist. Sicherheitshalber aber wird dies noch geprüft. Gegebenenfalls wird die Berechnung wiederholt – so lange, bis g ≠ 1 ist.

 

# berechnet ein erzeugendes Element g der
# Untergruppe der Ordnung q von Zp*
def findGeneratingElement(p, q):
    while True:
        b=randint(2, p-2)
        y=(p-1)//q
        g=modexp(b, y, p)
        if g!=1:
            return g

 

Mit normalerweise lediglich einer modularen Exponention ist die Funktion sehr schnell.

Die Funktionen randint und modexp werden aus dem Modul BasicFunctions importiert.

 

Die Funktion lässt sich mit folgendem Programm einmal probeweise testen:

# Test
if __name__ == "__main__":
    g=findGeneratingElement(67, 11)
    print(g)
    assert g in [9, 14, 59, 62, 22, 64, 40, 25, 24, 15]

 

 

In einer Funktion setup werden die beiden obigen Funktionen aufgerufen, um die Primzahlen p und q sowie das erzeugende Element g festzulegen. Zusätzlich werden noch der private Schlüssel d und der öffentliche Schlüssel e erzeugt.

 

def setup():
    global p, q, g, d, e
    p, q=findPrimes(512, 160)
    g=findGeneratingElement(p, q)
    d=truerandint(2, q-2)
    e=modexp(g, d, p)

 

Die Variablen p, q, g, d, e werden als globale Variablen vereinbart, damit in den folgenden Funktionen darauf zugegriffen werden kann. Die Funktion truerandint aus dem Modul BasicFunctions liefert eine nicht vorhersehbare Pseudozufallszahl.

Signatur erstellen

Die folgende Funktion makeSignature erstellt eine Signatur (r, s) für ein Dokument m. Sie verwendet die weiter unten angegebene Funktion hash, um den SHA-1-Hashwert des Dokuments m zu erzeugen.

 

def makeSignature(m):
    h=hash(m)
    while True:
        k=randint(2, q-2)
        r=modexp(g, k, p) % q
        s=(h + d*r) * modinverse(k, q) % q
        if r!=0 and s!=0:
            break
    return r, s

 

Um die Signatur (r, s) eines Dokuments m zu prüfen, wird folgende Funktion verifySignature verwendet.

def verifySignature(m, r, s):
    assert 0<r<q and 0<s<q
    h=hash(m)
    w=modinverse(s, q)
    u=w*h % q
    v=w*r % q
    z=modexp(g, u, p)*modexp(e, v, p) % p % q
    return z

 

Es folgt noch die Funktion hash.

def hash(m):
    s=sha1(str(m))
    d=s.hexdigest()
    h=int(d, 16)
    return h

Das gesamte Programm lässt sich mit folgendem Testprogramm testen. Die beiden ausgegebenen Zahlen müssen übereinstimmen.

# Test
if __name__ == "__main__":
    setup()
    m="Hallo"
    r, s=makeSignature(m)
    z=verifySignature(m, r, s)
    print(z)
    print(r)
    assert z==r

 

Literatur

[PP 10]   C. Paar, J. Pelzl: Understanding Crytography. Springer (2010)

[Web 1]   https://csrc.nist.gov/publications/detail/fips/186/4/final   Digital Signature Standard (DSS) (2013)

 

Weiter mit:   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 04.11.2018   Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden