Kryptografische Protokolle

RSA-Signatur

 aufwärts

Eine Signatur ist krypto­grafische Realisierung einer Unterschrift unter ein Dokument (daher auch elektronische Unterschrift genannt). Die Signatur soll mindestens so sicher sein wie eine herkömmliche Unterschrift.

Eigenschaften einer Unterschrift

Die Funktion einer herkömmlichen Unterschrift besteht darin, eine Verbindung zwischen einer Person und einem Dokument herzustellen.

Beispiels­weise verpflichtet sich A in einem Kaufvertrag für ein Auto, den Kaufpreis von 5000 Euro zu zahlen. Der Vertrags­partner B hält den unter­schriebenen Vertrag in den Händen und möchte seinen Anspruch gegenüber dem Unter­zeichner A geltend machen.

Im Normalfall geht alles gut, A erhält das Auto und B den Kaufpreis. Es sind aber verschiedene Szenarien denkbar, in denen die Vertrags­abwicklung schiefgeht. So könnte A behaupten, die Unterschrift unter dem Vertrag stamme nicht von ihm. A könnte mit Absicht eine falsche Unterschrift unter den Vertrag setzen, um von dem Vertrag zurücktreten zu können. Oder B könnte im Nachhinein den Kaufpreis fälschen, indem er eine 0 an den Betrag anhängt. Genauso könnte A behaupten, B hätte den Vertrag gefälscht und eine 0 an den Kaufpreis angehängt.

Die erforder­lichen Eigen­schaften einer Unterschrift sind damit folgende:

  1. Authentizität (die Unterschrift ist nur vom Unter­zeichner A zu leisten)

    Der Empfänger B oder ein Dritter kann die Unterschrift nicht fälschen. Dies ist schwierig zu realisieren, denn durch Üben gelingt es, eine Unterschrift nachzuahmen.

  2. Integrität (die Unterschrift ist mit dem zugehörigen Dokument untrennbar verbunden)

    Es ist nicht möglich, Teile des unter­schriebenen Dokuments zu verfälschen oder auszu­tauschen.

  3. Verifizier­barkeit (der Empfänger B kann sich davon überzeugen, dass die Unterschrift von A stammt)

    Beispiels­weise vergleicht die Bank die Unterschrift unter einer Überweisung mit der hinterlegten Unterschrift.

  4. Beweisbar­keit (der Empfänger B kann beweisen, dass die Unterschrift von A stammt)

    B klagt vor Gericht auf Vertrags­erfüllung, aber A streitet ab, den Vertrag unter­schrieben zu haben. Für den Beweis ist dann ein grapho­logisches Gutachten erforderlich; dieses hat allerdings nur begrenzte Aussagekraft.

RSA-Signatur

Das RSA-Signatur­verfahren ist die Umkehrung des RSA-Ver­schlüsselungsverfahrens.

Beim RSA-Ver­schlüsselungsverfahren ver­schlüsselt der Sender B die Nachricht m mit dem öffentlichen Schlüssel e des Empfängers A und erzeugt so die ver­schlüsselte Nachricht c:

c  =  me mod n

Der Empfänger A ent­schlüsselt die ver­schlüsselte Nachricht c mit dem eigenen privaten Schlüssel d und erhält so die Nachricht m:

m  =  cd mod n

 

Beim RSA-Signatur­verfahren ver­schlüsselt der Sender A das Dokument m mit dem eigenen privaten Schlüssel d und erzeugt so die Signatur s:

s  =  md mod n

Der Empfänger B ent­schlüsselt die Signatur s mit dem öffentlichen Schlüssel e des Senders A und erhält so das Dokument m:

m  =  se mod n

Der Empfänger B erhält das Dokument m erst dadurch, dass er die Signatur s mit dem öffentlichen Schlüssel des Senders A ent­schlüsselt. Stellt das Dokument m einen sinnvollen Text dar, so ist sicher­gestellt, dass A das Dokument signiert hat (vgl. unten­stehende Sicherheits­probleme).

Eigenschaften der RSA-Signatur

Wir betrachten inwieweit die RSA-Signatur die Eigen­schaften einer Unterschrift erfüllt.

  1. Authentizität (die Unterschrift ist nur vom Unter­zeichner A zu leisten)

    Nur der Unter­zeichner A kennt den privaten Schlüssel d, der das Gegenstück zu dem öffentlichen Schlüssel von A darstellt. Somit kann nur A von ihm signierte Dokumente erstellen.

  2. Integrität (die Unterschrift ist mit dem zugehörigen Dokument untrennbar verbunden)

    Das Dokument ergibt sich erst durch Ent­schlüsselung aus der Signatur.

  3. Verifizier­barkeit (der Empfänger B kann sich davon überzeugen, dass die Unterschrift von A stammt)

    Der Empfänger B muss sicher­stellen, dass der öffentliche Schlüssel e zu A gehört.

  4. Beweisbar­keit (der Empfänger B kann beweisen, dass die Unterschrift von A stammt)

    Der Empfänger B muss beweisen, dass A den öffentlichen Schlüssel e ver­öffentlicht hat. Außerdem muss m = se mod n einen sinnvollen Text ergeben.

Sicherheitsprobleme

Einige Details sind bei der Verwendung der RSA-Signatur zu berück­sichtigen.

  1. Jeder Angreifer C kann ein "von A signiertes Dokument" m mit Signatur s erstellen. Hierzu wählt C zufällig eine Zahl s und berechnet m = se mod n, indem er den öffentlichen Schlüssel e von A verwendet. Er kann nun behaupten, m sei ein von A signiertes Dokument. Zwar wird m ein unsinniger Text sein, aber damit verhindert dieser Angriff, dass A zufällig aussehende Texte wie z.B. Schlüssel signieren kann.
  2. Ein Empfänger B möchte ein Dokument m, das von A mit Signatur s signiert ist, in ein verändertes Dokument m'' mit gültiger Signatur s'' verfälschen. Hierzu veranlasst er A unter einem Vorwand, das Dokument m' = m-1·m'' zu signieren. A schöpft keinen Verdacht, weil m' völlig zufällig und unsinnig zu sein scheint. B erhält die zu m' gehörige Signatur s' und bildet (modulo n gerechnet)

    s''   =   s·s'   =   md·m' d   =   (m·m')d   =   (m·m-1·m'')d   =   m'' d

    Damit hat B eine gültige Signatur s'' für m'' erlangt.

  3. Ein Angreifer C hat einen Geheimtext c, der an A gesendet worden ist, abgefangen und möchte ihn ent­schlüsseln. Es handelt sich bei dem Geheimtext c um einen Klartext m, der mit dem öffentlichen Schlüssel e von A ver­schlüsselt worden ist:

    c  =  me mod n

    Der Angreifer bittet hierzu einfach A unter einem Vorwand, das Dokument c zu signieren. Treuherzig berechnet A die Signatur

    s  =  cd mod n  =  m

    und C erhält den gewünschten Klartext m. Jedoch könnte A Verdacht schöpfen, weil die Signatur ein Klartext ist, der ihm bekannt vorkommt. Darum geht C geschickter vor und veranlasst A zum Signieren des Dokuments

    c'  =  xe·c mod n

    wobei x Element ganze Zahlenn* eine von C gewählte Zahl ist. Nun bildet A die Signatur (modulo n gerechnet)

    s'  =  c'd  =  (xe·c)d  =  xed·cd  =  x·m

    und erkennt an der Signatur s' nicht, dass er einen Geheimtext ent­schlüsselt hat. C berechnet (modulo n)

    x-1·s'  =  x-1·x·m  =  m und erhält somit den ent­schlüsselten Geheimtext m.

In der Praxis jedoch entfallen diese Möglich­keiten, wie im Folgenden dargestellt wird.

Hash-Signatur

In der bisherigen Darstellung muss das gesamte Dokument, auch wenn es mehrere Megabyte lang ist, mit dem privaten Schlüssel des Senders ver­schlüsselt werden, um es zu signieren. Dies ist für die Praxis natürlich ungünstig; ferner werden weitere Sicherheits­probleme aufgeworfen, wenn das Dokument in Teilstücke zerlegt wird, die Zahlen  < n entsprechen.

Daher wird nicht das gesamte Dokument signiert, sondern nur eine Art Finger­abdruck des Dokuments, der mithilfe einer krypto­grafischen Hashfunktion gebildet wird. Ein solcher Finger­abdruck hat eine feste Länge von beispiels­weise lediglich 32 Byte, während das Dokument beliebig lang sein kann. Der Vorteil besteht darin, dass die Signatur entsprechend wesentlich kürzer ist, ohne dass sie wesentlich unsicherer wird – im Gegenteil, die oben angegebenen Angriffe auf die RSA-Signatur sind jetzt nicht mehr möglich. Das Dokument selbst wird zusätzlich als Klartext übermittelt.

Zunächst bildet der Sender A mithilfe einer öffentlich bekannten Hashfunktion h vom Dokument m einen Hashwert x = h(m) und signiert diesen. Er bildet also

s  =  (h(m))d mod n.

und sendet sodann das Paar (m, s) an den Empfänger.

Der Empfänger B berechnet mit der öffentlich bekannten Hashfunktion h seinerseits den Wert x = h(m), außerdem berechnet er

y  =  se mod n

Anschließend überprüft B, ob x und y über­einstimmen (Bild 1).

 

         A C          B
 
Hash-Funktion h
 
   
Schlüssel ver­öffentlichen  
 n, e 
Signatur erstellen  
berechnet
   Hashwert x = h(m)
  
berechnet
   Signatur s = (h(m))d mod n
  
 Dokument m und Signatur s 
  Signatur prüfen
  berechnet
   x = h(m)
  berechnet
   y = se mod n
  prüft
   ob x = y
Bild 1: Erstellen und Prüfen einer RSA-Signatur für ein Dokument m

Literatur

[BNS 05]A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)
[Bu 00]J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[RSA 78]R.L. Rivest, A. Shamir, L.M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21, 2, 120-126 (1978)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das RSA-Verfahren finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Diffie-Hellman-Schlüsselvereinbarung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 08.03.2010   Updated: 07.11.2016
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