Public Key Kryptografie, Verschlüsseln vs. Signieren

[creave]

Hallo erstmal,

Kryptografie ist so gar nicht meine Ecke, darf mich aber gerade damit auseinander setzen. Mein Anliegen ist keinesfalls schwer, eher im Gegenteil. Leider sind meine Quellen da sprachlich leider nicht immer eindeutig.

Zum Thema:

Public Key Verfahren, also asymmetrische Kryptoverfahren, basieren ja bekanntlich auf einem privaten und einem öffentlichen Schlüssel.

Der eine Weg ist mir klar:

Person A besitzt einen privaten Schlüssel und verteilt den passenden öffentlichen Schlüssel. Person B kann eine Nachricht mit dem öffentlichen Schlüssel von Person A verschlüsseln, und eben nur A kann die Nachricht mit dem privaten Schlüssel wieder entschlüsseln.

Jedoch ist mir der andere Weg, also das Signieren, nicht ganz klar. Es scheitert im Wesentlichen einfach schon am Begriff Signieren, bzw. am folgenden Verifizieren beim Empfänger.

Wieder ein Beispiel:

Person A besitzt einen privaten Schlüssel und verteilt den passenden öffentlichen Schlüssel. Person A kann jetzt eine Nachricht mit dem privaten Schlüssel signieren, Person B kann die Nachricht (oder deren Signatur) dann verifizieren, zwecks Integrität und Authentifizierung.

Doch was heißt Signieren genau? Handelt es sich beim Signieren nicht einfach nur wieder um Verschlüsseln?

Wie ich mir das bisher vorstelle: Person A signiert eine Nachricht mit dem privaten Schlüssel und schickt sie B - das heißt für mich bisher wenn ich nicht falsch liege: Person A verschlüsselt die Nachricht und schickt einmal das Original, einmal das verschlüsselte Original, an B. B kann jetzt das verschlüsselte Original mit dem öffentlichen Schlüssel entschlüsseln und mit dem Original abgleichen. Wenn identisch, dann ist alles ok, denn es kann ja nur Person A mit dem privaten Schlüssel etwas generieren, mit dem B mit dem öffentlichen Schlüssel etwas anfangen kann.

Passt das so? Heißt also Signieren nichts anderes als das Verschlüsseln der Originalnachricht mit anschließendem Versand des Originals und des verschlüsselten Originals?

Dass muss aber bedeuten, dass man mit beiden Schlüsseln ver- UND entschlüsseln kann.

Danke.

edit: ne, wartet mal, das macht keinen Sinn. Warum schickt man überhaupt ein Original und das verschlüsselte Original als Signatur. Da könnte man doch gleich nur die Signatur (für meine Begriffe also das verschlüsselte Original) versenden, denn wenn das klappt mit dem entschlüsseln kann es nur von A kommen

[Gast]

Richtig erkannt, Signieren ist im Prinzip nichts anderes als Verschlüsseln, allerdings halt mit dem privaten anstelle des öffentlichen Schlüssels.

Beim Signieren wird allerdings in der Regel nur ein Hash-Wert der eigentlichen Nachricht verschlüsselt, nicht die gesamte Nachricht.

Im Sicherheits-Unterforum hat neulich jemand nen Link gepostet:

http://nmichaels.org/rsa.py

Da kann man am Beispiel von RSA Operationen durchführen.

[creave]

Danke Gast.

Dass man beim Signieren nur einen Hashwert nimmt dürfte wohl die Antwort die Ursache auf mein edit aus dem Startpost sein? Der Empfänger verifiziert, in dem er den Hash entschlüsselt und das mitgeschickte Original hasht und vergleicht.

[AlecWhite]

Zwischen Signieren und Verschlüsseln besteht in erste Linie an Anwendungsunterschied: Die Signatur soll die Echtheit der Nachricht und des Absenders bestätigen (also das nichts verändert worden ist und das es wirklich vom Absender stammt).

Beim Verschlüsseln soll außerdem die Vertraulichkeit gewahrt bleiben. Ist also ein anderer Anwendungsfall.

Prinzipiell wird nur der Hash der Nachricht verschlüsselt, um den Overhead der verschlüsselten Nachricht möglichst gering zu halten. Außerdem lässt es sich schneller verifizieren etc. das man nur signiert, aber nicht verschlüsselt sind in der Regel Fragen der Performance. Ver- und Entschlüsseln sind relativ aufwendige Operationen.

[Mdk]

Das bisherige traf es eh schon ganz gut, wenn auch nicht völlig präzise, daher nochmal zusammengefasst:

*) Verschlüsselt wird mit dem öffentlichen Schlüssel

*) Signiert wird mit dem privaten Schlüssel.

*) Entschlüsselt wird mit dem privaten Schlüssel.

*) Verifiziert wird mit dem öffentlichen Schlüssel.

In der Praxis ist einem normalerweise daran gelegen, Operationen mit dem öffentlichen Schlüssel (also Verifikation bzw. Verschlüsselung) so schnell und effizient wie möglich zu gestalten, Operationen mit dem privaten Schlüssel (also Entschlüsselung bzw. Signaturgenerierung) sind üblicherweise um Größenordnungen aufwendiger.

Dazu kommt nach, dass, um den Overhead so gering wie möglich zu halten, für gewöhnlich nur ein eindeutiger Repräsentant der Nachricht signiert wird (üblicherweise ein Hashwert), es geht aber durchaus auch anders (Stichwort: signature schemes with message recovery).

Wie jetzt signieren und verschlüsseln technisch gelöst sind, kommt auf den exakten Algorithmus an. Am Simpelsten ist wohl RSA, wo beide Operationen durch eine modulare Exponentiation abgebildet werden (daher auch die Wahl des öffentlichen Exponenten als 2^16+1, damit das flott berechenbar ist).

Ist also d der private RSA Schlüssel und (e, n) der öffentliche, dann wird die Nachricht m _ver_schlüsselt durch c = m^e mod n und _ent_schlüsselt durch m = c^d mod n.
Signiert wird mittels s = m^d mod n, verifiziert durch m = s^e mod n.

Bei anderen Verfahren ist dieser Dualismus in der Form teilweise auch gegeben, teilweise differieren sie aber auch (Beispielsweise alle auf ElGamal basierenden Algorithmen wie auch der DSA).

mfg
mdk

[Gnafoo]

Ich würde es so beschreiben: Verschlüsseln und Signieren sind erst einmal zwei verschiedene Dinge mit unterschiedlichen Zielen.

Verschlüsselung: garantiert, dass niemand außer dem Empfänger die Nachricht lesen kann.
Signatur: garantiert, dass die Nachricht wirklich vom Absender stammt (Analogie zur Unterschrift) und nicht verändert wurde.


Dabei sind alle Kombinationen möglich:

Weder noch: das was man so üblicherweise per Mail kriegt.
Verschlüsselt: die Nachricht kann zwar nur der Empfänger einsehen, aber er kann nicht prüfen, ob nur die Hälfte ankam oder ob der Absender stimmt.
Signiert: es kann zwar jeder die Nachricht lesen, aber es lässt sich überprüfen, dass die Nachricht wirklich vom Absender kam, vollständig vorliegt und nicht verändert wurde.
Verschlüsselt + Signiert: nur der Empfänger kann die Nachricht lesen, er weiß dass sie nicht verändert wurde und dass sie tatsächlich vom ausgewiesenen Absender kam.


Technisch betrachtet heißt das:

Verschlüsselung: der Absender verschlüsselt die Nachricht mit dem öffentlichen Schlüssel des Empfängers. Nur der Empfänger kann sie wieder mit seinem privaten Schlüssel entschlüsseln und lesen.
Signatur: der Absender berechnet einen Hash der Nachricht und verschlüsselt diesen mit seinem privaten Schlüssel. Der Empfänger entschlüsselt den Hash mit dem öffentlichen Schlüssel des Absenders (Identität bestätigt) und vergleicht den Hash mit der Nachricht die er bekommen hat (Korrektheit/Vollständigkeit bestätigt).


Verschlüsseln kann ich sowohl mit dem privaten, als auch mit dem öffentlichen Schlüssel. Ich brauch dann aber wieder das jeweilige Gegenstück zum Entschlüsseln.

[Gast]

Jedes aktuellere Buch über Krypto wird dir sagen, dass Verschlüsselung
und Signieren unabhängige Ziele sind, und daher auch entsprechend niemals behaupten, dass Signieren = Verschlüsseln ist.

Rein theoretisch gesehen gibt es auch Grund zur Annahme, dass die sichere Verschlüsselung mehr benötigt als Signieren:
Sichere Signaturen existieren unter der Annahme von one-way functions (OWFs); für die (recht starke) IND-CCA2-Sicherheit von asym. Verschlüsselungsverfahren benötigt man jedoch zumindest trapdoor poly-to-one one-way functions, wenn ich mich richtig erinnere, von denen man vermutet (es gibt idealisierte Beweis, die die beiden Annahmen trennen können), dass sich deren Existenz nicht auf die Existenz von einfachen OWFs zurückführen lässt. Ob IND-CCA2 die "richtige" Forderung für asym. Versch. ist, ist eine andere Frage, da IND-CCA2 allerdings äquivalent zu vielen anderen sehr "netten" Sicherheitsdefinitionen ist (CCA-non-malleable,CCA-semantically secure), findet man das doch in manchen Büchern als die "richtige" Sicherheitsdefinition für asym Versch.

Man fährt also besser, die beiden Verfahren bzw. Anforderungen sprachlich auch zu trennen. Schon allein, weil man dann vielleicht nicht auf die Idee kommt, ein Schlüsselpaar für beide Verfahren zu verwenden.

Standard-RSA sollte man auch nicht als Verschlüsselungsverfahren sehen, sondern nur als schweres Problem (genauer: trapdoor one-way permutation).
Unter der entsprechenden Annahme der Härte des RSA-Problems lassen sich dann beweisbar sichere Verschlüsselungs- und Signaturverfahren konstruieren, wobei die in der Praxis verwendeten RSA-basierten Verfahren weitere Annahmen benötigen, z.B. die Kollisionsresistenz der verwendeten Hashfunktion.
Aktuelle RSA-basierte Verschlüsselungsverfahren wie RSA-OAEP verwenden z.B. das RSA-Problem zusammen mit einem randomisierten Paddingverfahren.

Das RSA-Problem macht ohne Hashen auch keinen Sinn als Signaturverfahren, da es "trivial" (zumindest von einem theoretischen Standpunkt aus) ist für eine gewählte Nachricht eine gültige Signatur zu fälschen, womit alle gewünschten Ziele (data origin authentication, identitiy authentication, non-repudiation) nicht erreicht werden.
Der Hash hat zwar den schönen Nebeneffekt, dass die Signatur feste (kleine) Größe besitzt, dient aber in erster Linie dazu, die algebraischen Eigenschaften von RSA zu "zerstören", siehe z.B. RSA-PSS.

RSA-OAEP und RSA-PSS gehen beide auf Arbeiten von Rogaway and Bellare zurück, und finden sich z.B. in den aktuellen RSA-Standards PKCS #1 v2.x beschrieben. Bellare hat auch ein paar sehr schöne Vorlesungsskripte bei sich auf der Homepage.