Kryptografische Protokolle

DSA-Signaturverfahren (Digital Signature Algorithm)

 aufwärts

Das DSA-Signatur­verfahren 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-Signatur­verfahren verwendet eine Primzahl p sowie eine Primzahl q, die ein Teiler von p-1 ist.

Die multi­plikative Gruppe ganze Zahlenp* 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 erzeugt.

Das DSA-Signatur­verfahren verwendet ein solches erzeugendes Element g, das die Untergruppe U der Ordnung q von ganze Zahlenp* erzeugt.

Ablauf des Verfahrens

 

         A          C          B
 Hashfunktion h 
 Primzahl p
Primzahl q mit  q | p-1
Zahl g Element ganze Zahlenp* mit
ord(g) = q
 
Schlüssel erzeugen  
wählt
   Zufallszahl d Element {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 Element {2, ..., q-2}
  
berechnet
   r = gk mod p mod q
   s = (h(m) + d·rk-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 Hash­verfahren 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 Hash­verfahren 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 ist aber beim Prüfen der Signatur die Berechnung s-1 nicht möglich. Auch für r ist der Wert 0 nicht zulässig. Damit dies nicht geschieht, wird die Signatur in einem derartigen Fall einfach erneut berechnet – so lange, bis r ≠ 0 und s ≠ 0 gilt. Bei der verwendeten sehr großen Zahl q ist es jedoch äußerst unwahr­scheinlich, dass bei der Reduktion modulo q einer der Fälle r = 0 oder s = 0 auf­tritt.

Beispiel mit kleinen Zahlen

Zur Ver­anschaulichung der durch­gefü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 Element ganze Zahlenp*, 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·rk-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.

Voraus­gesetzt ist, dass s ≠ 0 gilt. Dann gilt

s  kongruent  (h(m) + d·rk-1   (mod q)

Multi­plikation mit k und s-1 ergibt

k  kongruent  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  kongruent  u + d·v   (mod q)

Weil g die Ordnung q in ganze Zahlenp* hat, gilt

gk  kongruent  gu + d·v  kongruent  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  kongruent  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 Schwierig­keit, diskrete Logarithmen zu berechnen (Discrete Logarithm Problem – DLP). Bei den verwendeten großen Zahlen ist es undurch­führ­bar, 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 wieder­verwenden. Beim Prüfen der Signatur muss Kommunikationspartner B sicher­stellen, 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 ganze Zahlenp*.

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 Zertifizierungs­stelle erzeugen zu lassen.

Element g der Ordnung q

Gesucht ist ein erzeugendes Element g der Untergruppe U der Ordnung q von ganze Zahlenp*. 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.

Sei nun a ein erzeugendes Element von ganze Zahlenp* und sei r = (p-1)/q. Dann ist b = ar ein erzeugendes Element von U. Im Allgemeinen ist es jedoch schwer, ein erzeugendes Element a von ganze Zahlenp* zu berechnen, denn hierzu ist die Kenntnis von allen Teilern von p-1 erforderlich.

Indem einfach ein beliebiges Element c = ak Element ganze Zahlenp* hergenommen und g = cr = akr = bk berechnet wird, ergibt sich jedoch auch ein Element g Element U, und da alle Elemente von U erzeugende Elemente von U sind – bis auf die 1 – ist die Wahr­schein­lich­keit groß, dass g erzeugendes Element ist. Sicherheits­halber aber wird dies noch geprüft. Gegebenen­falls wird die Berechnung wiederholt – so lange, bis g ≠ 1 ist.

 

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

 

Mit normaler­weise 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 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()
    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 Pseudo­zufalls­zahl.

Signatur erstellen

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

 

def makeSignature(m):
    global r, s
    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

 

Um die Signatur zu prüfen, wird folgende Funktion verifySignature verwendet.

def verifySignature(m):
    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, r

 

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 über­einstimmen.

# Test
if __name__ == "__main__":
    setup()
    m="Hallo"
    makeSignature(m)
    z, r=verifySignature(m)
    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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 04.11.2018   Updated: 13.11.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik