DE69431426T2

DE69431426T2 - System und Verfahren zur Nachrichtenauthentisierung in einem nicht-schmiedbaren Kryptosystem mit öffentlichen Schlüssel

Info

Publication number: DE69431426T2
Application number: DE69431426T
Authority: DE
Inventors: Cynthia Dwork; Simeon Naor
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1993-12-29
Filing date: 1994-12-21
Publication date: 2003-05-28
Anticipated expiration: 2014-12-22
Also published as: EP0661845B1; JP3504988B2; US5539826A; EP0661845A2; JPH07212357A; DE69431426D1; EP0661845A3

Description

Gebiet der Erfindung

Die vorliegende Erfindung betrifft im Allgemeinen das Gebiet der Verschlüsselung von Nachrichten zur Übertragung zwischen Kommunikationsknoten. Insbesondere betrifft die Erfindung ein Verfahren mit öffentlichem Schlüssel zur Berechtigungsüberprüfung der Quelle einer verschlüsselten Nachricht.

Grundlagen der Erfindung

Kommunikationssysteme werden häufig zum. Übertragen vertraulicher Nachrichten von einem Sender an einen Empfänger verwendet. Optimalerweise wird das Datengeheimnis durch physische Sicherheit bewahrt, d. h. durch Übertragen einer vertraulichen Nachricht auf eine solche Weise, dass niemand außer dem Sender oder Empfänger auf die Nachricht zugreifen kann, beispielsweise in einem versiegelten, persönlich überbrachten Paket, über eine Leitung oder mittels irgendeines anderen geschlossenen Kommunikationsmediums.
Die Vorteile von elektronischen Kommunikationsmedien, beispielsweise des öffentlichen Telefonnetzes oder der drahtlosen Übertragung, sind Geschwindigkeit und eine leichte Handhabung. Diese Medien gewährleisten jedoch keine physische Sicherheit. Das heißt, es ist möglich, dass eine durch diese Kommunikationsmedien übertragene Nachricht von Teilnehmern mitgehört wird, vor denen der Inhalt der Nachricht geheim gehalten werden muss.
Daher wurde dem Problem der Aufrechterhaltung eines Geheimhaltungsgrades von Nachrichten, der mit physischer Sicherheit vergleichbar ist, sehr viel Aufmerksamkeit gewidmet. Ein großer Teil dieser Aufmerksamkeit zeigt sich in der Verschlüsselungstechnologie. Verschiedene Attribute eines Kryptosystems haben Einfluss darauf, wie gut das System eine Nachricht geheim hält.
Insbesondere darf ein Kryptosystem nicht schmiedbar sein. Die Eigenschaft der Schmiedbarkeit (malleability) wird in Verbindung mit Kryptosystemen in Dolev, Dwork und Naor, "Non- Malleable Cryptography", ACM 089791-397-3/91/004/0542, Seiten 542 bis 552 (1991), erläutert. Zwei Attribute machen ein Kryptosystem nichtschmiedbar. Erstens ist das Kryptosystem semantisch sicher. Das heißt, falls irgendwelche gegebenen Informationen über den unverschlüsselten Text aus dem chiffrierten Text berechnet werden können, können diese gegebenen Informationen ohne den chiffrierten Text berechnet werden. Zweitens ist es unmöglich oder rechnerisch undurchführbar, bei einem gegebenen ersten chiffrierten Text einen zweiten chiffrierten Text so zu erzeugen, dass die unverschlüsselten Texte, die dem ersten und zweiten chiffrierten Text entsprechen, miteinander in Zusammenhang stehen.
Der Nachteil der Schmiedbarkeit wird folgendermaßen veranschaulicht: Wenn ein Satz von zusammenhängenden Nachrichten unter Verwendung eines algebraischen Kryptosystems verschlüsselt wird, weisen die sich ergebenden verschlüsselten Nachrichten manchmal einen entsprechenden (nicht unbedingt identischen) Zusammenhang auf. Falls ein Satz von Nachrichten beispielsweise eng beieinander liegende numerische Werte in einer steigenden numerischen Reihe aufweist, verschlüsseln einige schmiedbare Schlüssel die Nachrichten in einen Satz von verschlüsselten Nachrichten, die ebenfalls eng beieinander liegende Werte in einer steigenden Reihe aufweisen. Obwohl es möglicherweise immer noch schwierig ist, die Nachricht zu entschlüsseln, kann ein Horcher die verschlüsselte Nachricht immer noch unerlaubterweise verwenden.
Beispielsweise wird das Szenario einer Angebotsabgabe (contract bidding) betrachtet. Man stelle sich vor, dass eine Gemeinde für den Bau einer neuen Schule gestimmt hat, einen Entwurf gewählt hat und bekannt gibt, dass Baufirmen eingeladen werden, sich durch das Einreichen von Geboten um den Vertrag zu bewerben, die unter Verwendung eines schmiedbaren öffentlichen Schlüssels E verschlüsselt werden. Die Firma A verschlüsselt ein Gebot von $ 1.500.000 unter Verwendung von E und überträgt das Gebot über eine unsichere Leitung. Die Firma B empfängt das Gebot, kann jedoch das Gebot nicht entschlüsseln, weil sie den privaten Schlüssel der Gemeinde zur Entschlüsselung nicht hat.
Wenn die Firma B das verschlüsselte Gebot der Firma A erhält, kann sie jedoch eine eigene Nachricht erzeugen, die ein niedrigeres Gebot als das der Firma A ergibt, wenn sie unter Verwendung des Entschlüsselungsschlüssels der Gemeinde entschlüsselt wird. Das Kryptosystem ist schmiedbar, falls die Firma B bei gegebenem verschlüsselten Gebot der Firma A mit einer Wahrscheinlichkeit eine solche Nachricht erzeugen kann, die größer ist, als die Wahrscheinlichkeit wäre, wenn die Firma das verschlüsselte Gebot der Firma A nicht hätte. Die Firma B kann so die Firma A geringfügig unterbieten und den Vertrag erhalten, ohne das Gebot der Firma A oder sogar ihr eigenes verschlüsseltes Gebot kennen zu müssen. Die Interessen der Firma A werden durch die Verwendung eines nichtschmiedbaren Kryptosystems gewahrt, so dass die Firma B daran gehindert wird, auf diese Weise ein Gebot zu erzeugen.
Dieses Szenario veranschaulicht den Unterschied zwischen physischer Sicherheit, bei der die Firma B selbst auf das verschlüsselte Gebot der Firma A keinen Zugriff hat, und durch verschlüsselte Nachrichten erzeugter Geheimhaltung. In einigen Zusammenhängen, beispielsweise in diesem Szenario, ist eine bloße Geheimhaltung durch die Verwendung eines schmiedbaren Kryptosystems kein zufriedenstellender Ersatz für physische Sicherheit.
Ein bestimmter Bereich, in dem Geheimhaltung wünschenswerterweise gleichbedeutend mit physischer Sicherheit ist, ist der Bereich der Berechtigungsüberprüfung der Quelle einer verschlüsselten Nachricht. Wünschenswerterweise muss ein Berechtigungsüberprüfungsschema zwei Attribute haben. Als Erstes muss das Schema sicher vor dem Angriff durch einen Eindringling (interloper) sein. Das heißt, ein Eindringling darf nicht in der Lage sein, eine gezielte Falschinformation an einen Empfänger zu übertragen und die Nachricht mit der Falschinformation als eine gültige, von einem berechtigten Sender übertragene Nachricht anzuerkennen. Falls kein zuverlässiges Schema zur Berechtigungsüberprüfung von Nachrichten vorhanden ist, könnte eine von einem Empfänger R empfangene und die Quellenadresse eines Senders S enthaltende Nachricht in der Tat von einem Eindringling B übertragen worden sein. Folglich könnte B gezielte Falschinformationen über S an R übertragen.
Das zweite wünschenswerte Attribut eines Berechtigungsüberprüfungsschemas ist, dass es dem Empfänger R möglich sein muss, einen dritten Teilnehmer C zu überzeugen, dass die Nachricht in der Tat vom Sender S und nicht von einem Betrüger B übertragen wurde.
Ein Beispiel eines Szenarios, in dem eine Berechtigungsüberprüfung wünschenswert ist, ist ein als "Chessmaster Attack" oder "Mafia Scam" bezeichnetes Szenario. Der Name wird von einem Schachszenario abgeleitet, in dem ein Spieler gleichzeitig die weißen Figuren gegen einen Großmeister und die schwarzen Figuren gegen einen anderen spielt. Der Spieler lässt tatsächlich die beiden Großmeister gegeneinander spielen, indem die von jedem Großmeister gemachten Spielzüge gegen den jeweils anderen kopiert werden.
Der Chessmaster Attack wird in einem als "Identifizierung: Freund oder Feind" ("Identification: Friend oder Foe") oder IFF bezeichneten Szenario veranschaulicht. In einem möglichen IFF-Szenario kommunizieren ein verbündetes Flugzeug F und eine verbündete Bodenstation GF, und ein feindliches Flugzeug N versucht in Zusammenarbeit mit einer feindlichen Bodenstation GN, gezielte Falschinformationen zum verbündeten Flugzeug und zur verbündeten Bodenstation zu übertragen, indem es sich als diese ausgibt.
Ein herkömmlicher Versuch zum Einrichten von sicheren Übertragungen besteht darin, dem verbündeten Flugzeug einige geheime Informationen s zukommen zu lassen, die nur der verbündeten Bodenstation bekannt sind. Die verbündete Bodenstation wählt eine aus einer großen Anzahl von Abfragen (challenges) q und überträgt q zum verbündeten Flugzeug. Das verbündete Flugzeug antwortet mit einer Funktion F von s und q, die ohne s unmöglich berechnet werden kann.
Selbstverständlich kann das feindliche Flugzeug die Funktion ebenfalls empfangen. Falls die verbündete Bodenstation das feindliche Flugzeug später mit einer anderen Abfrage q' abfragt, kann die verlangte Antwort, eine Funktion von s und q', nicht einfach erzeugt werden, wenn nur q und F(s, q) bekannt sind.
In einem schmiedbaren Kryptosystem ist dieses Übertragungsprotokoll jedoch anfällig für Angriffe unter Verwendung eines Mafia-Scam-Verfahrens. Die folgende Nachrichtenfolge, in der der auf den Doppelpunkt folgende Ausdruck die vom ersten Teilnehmer an den zweiten Teilnehmer übertragene Nachricht ist (d. h. eine Abfrage oder eine Antwort), soll betrachtet werden:
In dieser Folge schalten sich ein feindliches Flugzeug und eine feindliche Bodenstation, die zusammenarbeiten, in der Art eines Mafia Scam zwischen die verbündete Bodenstation und das verbündete Flugzeug. Im vierten Schritt stellt das verbündete Flugzeug der feindlichen Bodenstation die verschlüsselte Antwort f(s, q) bereit. Im sechsten Schritt überträgt das feindliche Flugzeug sodann die verschlüsselte Antwort zur verbündeten Bodenstation, wobei die Abfrage von der verbündeten Bodenstation korrekt beantwortet wird.
Es ist möglich, dass die verbündete Bodenstation den Kopiervorgang des Feindes zunichte macht, indem sie spezielle, als q' bezeichnete Positionsgeberinformationen in die Abfrage einbaut, beispielsweise die Position des verbündeten Flugzeugs und einen Zeitstempel. Infolgedessen müsste das feindliche Flugzeug f(s, q') anstelle von f(s, q) übertragen, so dass ein bloßes Kopieren nicht ausreichen würde, um das verbündete Kommunikationssystem anzugreifen.
Die beiden Abfragungen q und q' sind jedoch gleich, mit Ausnahme der Position und des Zeitstempels. In einem schmiedbaren Kryptosystem sind f(s, q) und f(s, q') wahrscheinlich ähnlich. Bei bekanntem q, q' und f(s, q) kann es folglich möglich sein, dass der Feind f(s, q') erhält und das verbündete Kryptosystem besiegt.
Dementsprechend besteht ein Bedarf an einem Kryptosystem, das die Berechtigungsüberprüfung von geheimen Nachrichten erleichtert, nicht schmiedbar ist und daher für die oben beschriebene Art von Angriffen nicht anfällig ist.
EP-A-0 522 473 beschreibt bereits ein kryptografisches Identitätsüberprüfungssystem, dessen Aufgabe die Verhinderung der Fälschung von Überprüfungsaufzeichnungen (verification transcripts) ist, die während der Kommunikation zwischen einem Beweiser (prover) und einem Überprüfer (verifier) erstellt werden. Das System arbeitet unter der Steuerung eines vertrauenswürdigen Geschäftspartners (trusted centre), beispielsweise einer Kreditkartengesellschaft, die dem Beweiser eine Kennung ID und geheime Informationen S ausgibt. Der Beweiser erzeugt eine erste Nachricht X, die zum Überprüfer übertragen wird. Der Überprüfer erzeugt eine Zufallsnachricht M und eine Anfrage (enquiry) E aus der ersten Nachricht X und der Zufallsnachricht M. Die Anfrage E wird zum Beweiser übertragen, der prüft, ob die Anfrage E korrekt aus der ersten Nachricht X und der Zufallsnachricht M erzeugt wurde. Der Beweiser erzeugt aus der Anfrage E und den geheimen Informationen S eine Antwort Y, die mit der ersten Nachricht X in Zusammenhang steht. Der Überprüfer prüft, ob die Antwort Y gemäß der Anfrage E, der ersten Nachricht X und der Kennung ID gültig ist, und speichert eine Kopie, die die Kennung ID, die erste Nachricht X, die Zufallsnachricht M und die Antwort Y umfasst. Dieses System ist kein nichtschmiedbares Verschlüsselungssystem mit öffentlichem Schlüssel und dient nicht zur Bekämpfung eines Mafia-Scam-Angriffs.

Zusammenfassung der Erfindung

Eine Aufgabe der Erfindung ist daher die Bereitstellung eines nichtschmiedbaren Verfahrens und Systems zur Berechtigungsüberprüfung von Nachrichten.
Um diese und andere Ziele zu erreichen, werden gemäß der Erfindung ein Verfahren und ein System bereitgestellt, in denen ein Kryptosystem mit öffentlichem Schlüssel, das nichtschmiedbare öffentliche und private Schlüssel verwendet, zur Berechtigungsüberprüfung von Nachrichten verwendet wird. Es wird ein Berechtigungsüberprüfungsprotokoll für Nachrichten verwendet, das eine Berechtigungsüberprüfung bereitstellt, die vor Manipulationen durch einen Horcher/Eindringling sicher ist, wenn es mit dem nichtschmiedbaren Kryptosystem mit öffentlichem Schlüssel verwendet wird.
Gemäß der vorliegenden Erfindung wird nun ein Verschlüsselungsverfahren zur Berechtigungsüberprüfung einer Datennachricht bereitgestellt, die von einer ersten Kommunikationseinheit S an eine zweite Kommunikationseinheit R übertragen wird, wobei das Verfahren die folgenden Schritte umfasst: Übertragen einer Berechtigungsüberprüfungs- Anforderungsnachricht von der ersten Kommunikationseinheit S zur zweiten Kommunikationseinheit R; Antworten auf eine offenbar von der ersten Kommunikationseinheit S übertragenen Berechtigungsüberprüfungs-Anforderungsnachricht durch die zweite Kommunikationseinheit R, wobei die erste Einheit die Datennachricht offenbar übertragen hat, wobei der Schritt des Antwortens das Übertragen einer Antwortnachricht beinhaltet; Erzeugen einer Berechtigungsüberprüfungsnachricht durch die erste Einheit S; Übertragen der erzeugten Berechtigungsüberprüfungsnachricht durch die erste Einheit S; Erzeugen der Berechtigungsüberprüfungsnachricht durch die zweite Einheit und Überprüfen durch die zweite Einheit R, ob die empfangene Berechtigungsüberprüfungsnachricht mit der von der zweiten Einheit R erzeugten Berechtigungsüberprüfungsnachricht übereinstimmt; dadurch gekennzeichnet, dass das Verfahren ein Verschlüsselungsverfahren mit nichtschmiedbarem öffentlichen Schlüssel ist; der Schritt des Antwortens das Übertragen der Antwortnachricht beinhaltet, die mit dem nichtschmiedbaren öffentlichen Schlüssel der ersten Einheit verschlüsselt wird; das Verfahren einen Schritt des Entschlüsseins der verschlüsselten Antwortnachricht durch die erste Einheit S unter Verwendung ihres privaten Schlüssels beinhaltet, um die Antwortnachricht zu erhalten; und die von der ersten Einheit S erzeugte Berechtigungsüberprüfungsnachricht eine Funktion der Datennachricht und der entschlüsselten Antwortnachricht ist und eine von der ersten und der zweiten Einheit gegenseitig vereinbarte Funktion ist.
Gemäß der vorliegenden Erfindung wird außerdem ein Verschlüsselungssystem zur Berechtigungsüberprüfung einer von einer ersten Kommunikationseinheit S im System an eine zweite Kommunikationseinheit R im System übertragene Datennachricht bereitgestellt, wobei die erste Kommunikationseinheit Mittel zum Übertragen einer Berechtigungsüberprüfungs- Anforderungsnachricht an die zweite Kommunikationseinheit R umfasst; wobei die zweite Kommunikationseinheit R Mittel zum Antworten auf eine offenbar von der ersten Kommunikationseinheit S übertragenen Berechtigungsüberprüfungs-Anforderungsnachricht umfasst, wobei die erste Einheit die Datennachricht offenbar übertragen hat, wobei das Mittel zum Antworten ein Mittel zum Übertragen einer Antwortnachricht beinhaltet; wobei die erste Einheit S Mittel zum Erzeugen einer Berechtigungsüberprüfungsnachricht und zum Übertragen der erzeugten Berechtigungsüberprüfungsnachricht an, die zweite Einheit R umfasst; und wobei die zweite Einheit R Mittel zum Erzeugen der Berechtigungsüberprüfungsnachricht und zum Überprüfen umfasst, ob die empfangene Berechtigungsüberprüfungsnachricht mit der in der zweiten Einheit R erzeugten Berechtigungsüberprüfungsnachricht übereinstimmt; dadurch gekennzeichnet, dass das System ein Verschlüsselungssystem mit nichtschmiedbarem öffentlichem Schlüssel ist; das Mittel zum Antworten auf eine Berechtigungsüberprüfungs-Anforderungsnachricht Mittel zum Übertragen der mit dem nichtschmiedbaren öffentlichen Schlüssel der ersten Einheit verschlüsselten Antwortnachricht beinhaltet; die erste Einheit S Mittel zum Entschlüsseln der verschlüsselten Antwortnachricht durch unter Verwendung ihres privaten Schlüssels umfasst, um die Antwortnachricht zu erhalten; und die von der ersten Einheit S erzeugte Berechtigungsüberprüfungsnachricht eine Funktion der Datennachricht und der entschlüsselten Antwortnachricht ist.
Obwohl die Erfindung in erster Linie als ein Verfahren beschrieben wird, wird der Fachmann verstehen, dass eine Vorrichtung, beispielsweise ein herkömmlicher Datenprozessor, zu dem eine CPU, ein Speicher, Ein-/Ausgabeeinheiten, ein Programmspeicher, ein Verbindungsbus- und andere geeignete Komponenten gehören, programmiert oder auf andere Weise ausgestaltet werden könnte, um die Ausführung des Verfahrens der Erfindung zu erleichtern. Ein solcher Prozessor würde geeignete Programmmittel zur Ausführung des Verfahrens der Erfindung beinhalten.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Systemblockschaltbild, das die Kommunikationseinheiten S und R und einen Eindringling B zeigt.
Fig. 2 ist ein Flussdiagramm, das einen Austausch von Nachrichten für eine Berechtigungsüberprüfungsfolge gemäß dem Verfahren der Erfindung zeigt.
Fig. 3 ist ein Flussdiagramm, das einen Austausch von Nachrichten für eine Berechtigungsüberprüfungsfolge zwischen einem Sender und einem Empfänger zeigt, in der ein dritter Teilnehmer versucht, eine Nachricht als gültig anzuerkennen, die nicht vom Sender stammt.

Beschreibung der bevorzugten Ausführungsformen

Die folgende Erläuterung kann auf jedes Kommunikationssystem angewandt werden, in dem ein Sender eine Nachricht an einen Empfänger überträgt, wobei der Ursprung der Nachricht als gültig anerkannt werden muss und wobei ein Eindringling am Versuch gehindert werden muss, eine angeblich vom Sender stammende gezielte Falschinformation an den Empfänger zu übertragen. Die genaue Beschaffenheit des Kommunikationsmediums und des Senders, des Empfängers und des Eindringlings sind für die Erfindung nicht wesentlich. Fig. 1 ist eine Blockschaltbilddarstellung, die ein solches System schematisch zeigt, zu dem ein Sender S. ein Empfänger R und ein Eindringling B gehören.
Das Verfahren zur Berechtigungsüberprüfung von Nachrichten gemäß der Erfindung beinhaltet die Verwendung eines Kryptosystems mit öffentlichem Schlüssel. Ein Kryptosystem mit öffentlichem Schlüssel wurde erstmals in Diffie und Hellman, "New Directions in Cryptography", I. E. E. E. Transactions on Information Theory, Band IT-22, Nr. 6, Seiten 644 bis 654 (Nov. 1976), beschrieben.
In einem Kryptosystem mit öffentlichem Schlüssel, das von einer Vielzahl von Kommunikationsknoten ausgeführt werden kann, gibt es für jeden Knoten A einen öffentlichen Schlüssel EA zur Verschlüsselung, der allen anderen Koten bekannt ist. Jeder öffentliche Schlüssel EA zur Verschlüsselung beschreibt eine Prozedur zum Verschlüsseln von Nachrichten, die zum entsprechenden Knoten A übertragen werden müssen. Für jeden öffentlichen Schlüssel zur Verschlüsselung gibt es einen entsprechenden privaten Schlüssel zur Entschlüsselung, der nur dem entsprechenden Knoten bekannt ist und der nicht hergeleitet werden kann, wenn der öffentliche Schlüssel zur Verschlüsselung bekannt ist. Falls eine Nachricht unter Verwendung des öffentlichen Schlüssels EA zur Verschlüsselung codiert wird, kann daher nur der Knoten A sie entschlüsseln, obwohl jeder andere Knoten die verschlüsselte Nachricht empfangen kann. Selbst der sendende Knoten kann die Nachricht nicht entschlüsseln, sobald sie verschlüsselt worden ist.
Kryptosysteme mit öffentlichem Schlüssel, die erstmals in Diffie et al. vorgestellt wurden, beruhen auf der Schwierigkeit des Berechnens von Logarithmen mod q, wobei q eine Primzahl von Elementen ist, die ein Feld bilden. Für eine als eine Bitnummer b darstellbare Größe, wobei q eine Primzahl ist, die etwas kleiner als 2b ist, verlangt eine Verschlüsselung oder Entschlüsselung unter Verwendung von Schlüsseln, wie sie in Diffie et al. beschrieben werden, eine Potenzierung, die höchstens 2b Multiplikationen mod q benötigt. Das Entschlüsseln eines chiffrierten Textes ohne den Schlüssel erfordert die Verwendung von Logarithmen mit 2(b/2) Operationen. Bezüglich einer berechtigten Verschlüsselung oder Entschlüsselung durch Teilnehmer, die die entsprechenden Schlüssel kennen, erfordert eine Kryptoanalyse (cryptanalysis) folglich einen Rechenaufwand, der exponentiell ansteigt.
Aufgrund der Abhängigkeit von der Modulo-Arithmetik sind chiffrierte Texte, die aufsteigenden unverschlüsselten Texten entsprechen, jedoch teilweise aufsteigend. Folglich ist die herkömmliche Kryptographie mit öffentlichem Schlüssel von Diffie et al. schmiedbar und anfällig für die oben beschriebenen Angriffe. Gemäß der Erfindung wird dieser Nachteil durch die Verwendung eines nichtschmiedbaren Kryptosystems überwunden. Obwohl jedes nichtschmiedbare Kryptosystem gemäß der Erfindung verwendet werden kann, wird das nichtschmiedbare Kryptosystem bevorzugt, das im Abschnitt 4 von Dolev et al., "Non-Malleable Cryptography", beschrieben wird, der in den Grundlagen zitiert wurde.
Diffie et al. erläutern das Problem der Berechtigungsüberprüfung und schlagen ein Ein-Wege- Berechtigungsüberprüfungssystem (one-way authenticitation system) vor, in dem ein Sender die zu übertragende Nachricht unter Verwendung des privaten Schlüssels des Senders "dechiffriert". Der Empfänger verwendet sodann den öffentlichen Schlüssel des Senders, um die "entschlüsselte" Nachricht zu "verschlüsseln", um die Nachricht selbst wiederherzustellen. Da nur der Sender den privaten Schlüssel des Senders verwendet haben könnte, ist die Wiederherstellung der Nachricht unter Verwendung des öffentlichen Schlüssels des Senders der Beweis, dass der Sender die Nachricht übertragen hat.
Bei einem geeigneten nichtschmiedbaren Kryptosystem funktioniert das Verfahren der Erfindung, wie im Flussdiagramm von Fig. 2 dargelegt wird. Die Schritte von Fig. 2 zeigen den Nachrichtenverkehr zwischen einem Sender S und einem Empfänger R. Das Ziel ist die Berechtigungsüberprüfung einer Datennachricht m, die von S an R übertragen werden muss.
In einem ersten Schritt 2 überträgt der Sender S eine Berechtigungsüberprüfungs-Anforderungsnachricht, die anzeigt, dass S eine Berechtigungsüberprüfung der Datennachricht m ausführen möchte. Die Berechtigungsüberprüfungs- Anforderungsnachricht kann die Datennachricht m selbst beinhalten oder eine Befehlsnachricht gemäß einem geeigneten Befehlsformat oder Protokoll sein, das mit dem den Sender S und den Empfänger R unterstützenden Kommunikationssystem verwendet wird. In diesem letzteren Fall wird vorausgesetzt, dass die Datennachricht m selbst gesondert übertragen wird. In der Tat ist die Berechtigungsüberprüfungs- Anforderungsnachricht eine Erklärung "Ich bin S, und ich möchte eine Berechtigungsüberprüfung der Datennachricht m ausführen, die ich Ihnen sende".
Im Schritt 4 antwortet der Empfänger R, indem er eine Antwortnachricht überträgt, vorzugsweise eine willkürliche Zeichenfolge st, die unter Verwendung des öffentlichen Schlüssels Es des Senders verschlüsselt wird. Die Zeichenfolge st wird vorzugsweise willkürlich ausgewählt oder kann auf einer festgelegten Formel beruhen. Beispielsweise könnte sich die Zeichenfolge auf einen Datum- oder Zeitstempel beziehen.
Im Schritt 6 überträgt der Sender S dem Empfänger R schließlich eine Berechtigungsüberprüfungsnachricht, aus der der Empfänger R ermitteln kann, ob die Identität des Senders der Datennachricht m in der Tat der Sender S ist. In einer bevorzugten Ausführungsform der Erfindung erfolgt die Berechtigungsüberprüfungsnachricht in der Form Auth(m, st), wobei Auth eine vom Sender S und vom Empfänger R gegenseitig vereinbarte Funktion ist. Auth ist vorzugsweise eine einfach berechnete Funktion, die als Argumente eine Nachricht, beispielsweise die als gültig anzuerkennende Nachricht m, und eine Zeichenfolge nimmt, beispielsweise st. Auth erzeugt eine Ausgabe, vorzugsweise in Form einer kurzen Zeichenfolge. Diese Ausgabe oder kurze Zeichenfolge wird tatsächlich vom Sender S an den Empfänger R übertragen. Für alle Zeichenfolgen st und st' muss die Wahrscheinlichkeit gering sein, dass Auth(m, st) gleich Auth(m.st') ist.
Außerdem wird es bevorzugt, dass der Empfänger R bei bekanntem m, st und der Ausgabe oder der kurzen Zeichenfolge problemlos überprüfen kann, dass Auth(m, st) gleich der als Berechtigungsüberprüfungsnachricht von S an R übertragenen. Ausgabe ist. Wenn R prüft, ob die empfangene Berechtigungsüberprüfungsnachricht mit der Auth-Funktion der von R bereits empfangenen Datennachricht m und der von R an S übertragenen Zeichenfolge st übereinstimmt, prüft R folglich dabei, ob die Identität des Senders der Datennachricht m tatsächlich S ist.
Es wird bevorzugt, dass der öffentliche Schlüssel des Empfängers R vom Sender S zum Verschlüsseln der Berechtigungsüberprüfungs-Anforderungsnachricht (unter der Voraussetzung, das die verschlüsselte Datennachricht m gesondert übertragen wurde) und der Berechtigungsüberprüfungsnachricht Auth(m, st) verwendet wird, obwohl dies für die Erfindung nicht wesentlich ist.
Um einen Versuch eines Betrügers B zu vereiteln, sich für den Sender S auszugeben, muss der öffentliche Schlüssel Es zur Verschlüsselung nicht schmiedbar sein. Andernfalls wäre diese Berechtigungsüberprüfungsfolge anfällig für Angriffe, beispielsweise durch Mafia Scam. Die Funktionsweise eines solchen Angriffs wird im Flussdiagramm von Fig. 3 gezeigt.
Angenommen, S überträgt eine Datennachricht m an R, und der Betrüger B möchte anstelle der Nachricht m von S eine Nachricht m' mit gezielten Falschinformationen an R übertragen und m' als von S stammend als gültig anerkennen. Die Nachricht m' mit gezielten Falschinformationen hängt mit der Datennachricht m zusammen, d. h. m' = f(m). Da der öffentliche Schlüssel Es des Senders S für diese Darstellung schmiedbar ist, ist es für B ziemlich einfach, bei bekanntem Es (st'), m und m' ein Es (st) zu berechnen, so dass ein Zusammenhang zwischen st und st' besteht.
Der Austausch durch Mafia Scam erfolgt auf die in Fig. 3 gezeigte Weise. Im Schritt 8 überträgt der Sender S eine an den Empfänger R gerichtete Berechtigungsüberprüfungsanforderung zur. Berechtigungsüberprüfung einer Datennachricht m. Die Anforderung wird von B abgefangen. Im Schritt 10 überträgt B eine Berechtigungsüberprüfungsanforderung an R, wobei er sich selbst als S ausgibt und eine Berechtigungsüberprüfung einer Nachricht m' mit gezielten Falschinformationen anfordert, die einen gegebenen Zusammenhang mit m aufweist.
Im Schritt 12 antwortet R auf die Anforderung von B, indem er eine Zeichenfolge st' überträgt, die unter Verwendung des öffentlichen Schlüssels von S verschlüsselt wird. B kann die verschlüsselte Zeichenfolge nicht entschlüsseln. Falls der öffentliche Schlüssel von S gemäß der Erfindung nichtschmiedbar ist (Schritt 13), gelangt der Versuch von B Anerkennen der Gültigkeit von m' nicht über diesen Punkt hinaus. Der Versuch von B wird vereitelt, und das Verfahren der Erfindung hat die Kommunikationssicherheit erfolgreich aufrechterhalten (Schritt 14).
Falls der öffentliche Schlüssel von S jedoch schmiedbar ist, kann B Es (st') manipulieren, um eine verschlüsselte Nachricht Es (st), wobei Auth(m, st) = g(Auth(m, st)) für eine einfach zu berechnende Funktion g zu erzeugen. Im Schritt 15 überträgt B Es (st) an S.
Im Schritt 16 versucht S sodann, die Berechtigungsüberprüfung durch das Übertragen von Auth(m, st) durchzuführen. B fängt diese Nachricht wiederum ab, wendet die Funktion g auf diese an, um Auth(m', st') zu erzeugen, und überträgt im Schritt 18 die letztere an R. R glaubt sodann, dass S die Nachricht m' mit gezielten Falschinformationen als gültig anerkannt hat, und B war bei seinem Mafia Scam erfolgreich.
Der Erfolg des Mafia Scam hängt jedoch von der Schmiedbarkeit des öffentlichen Schlüssels Es von S ab. Falls der öffentliche Schlüssel gemäß der Erfindung nichtschmiedbar ist, kann B Es (st) nicht aus Es (st') erzeugen, und der Mafia Scam schlägt fehl. Folglich schützt die Erfindung diese Berechtigungsüberprüfungsfolge vorteilhafterweise vor Angriffen.

Claims

1. Verschlüsselungsverfahren zur Berechtigungsüberprüfung einer von einer ersten Kommunikationseinheit S an einezweite Kommunikationseinheit R übertragenen Datennachricht, wobei das Verfahren die folgenden Schritte umfasst:

Übertragen (2) einer Berechtigungsüberprüfungs- Anforderungsnachricht von der ersten Kommunikationseinheit S zur zweiten Kommunikationseinheit R;

Antworten (4) auf eine offenbar von der ersten Kommunikationseinheit S übertragenen Berechtigungsüberprüfungs-Anforderungsnachricht durch die zweite Kommunikationseinheit R, wobei die erste Einheit die Datennachricht offenbar übertragen hat, wobei der Schritt des Antwortens das Übertragen einer Antwortnachricht beinhaltet;

Erzeugen einer Berechtigungsüberprüfungsnachricht durch die erste Einheit S;

Übertragen (6) der erzeugten Berechtigungsüberprüfungsnachricht durch die erste Einheit S;

Erzeugen der Berechtigungsüberprüfungsnachricht durch die zweite Einheit und

Überprüfen durch die zweite Einheit R, ob die empfangene Berechtigungsüberprüfungsnachricht mit der von der zweiten Einheit R erzeugten Berechtigungsüberprüfungsnachricht übereinstimmt;

dadurch gekennzeichnet, dass

das Verfahren ein Verschlüsselungsverfahren mit nichtschmiedbarem öffentlichen Schlüssel ist;

der Schritt des Antwortens (4) das Übertragen der Antwortnachricht beinhaltet, die mit dem nichtschmiedbaren öffentlichen Schlüssel der ersten Einheit verschlüsselt wird;

das Verfahren einen Schritt des Entschlüsseins der verschlüsselten Antwortnachricht durch die erste Einheit S unter Verwendung ihres privaten Schlüssels beinhaltet, um die Antwortnachricht zu erhalten; und

die von der ersten Einheit S erzeugte Berechtigungsüberprüfungsnachricht eine Funktion der Datennachricht und der entschlüsselten Antwortnachricht ist und eine von der ersten und der zweiten Einheit gegenseitig vereinbarte Funktion ist.

2. Verfahren nach Anspruch 1, wobei die Antwortnachricht eine willkürliche Zeichenfolge ist.

3. Verfahren nach Anspruch 1 oder 2, wobei die beim Erzeugen der Berechtigungsüberprüfungsnachricht verwendete Funktion so gewählt wird, dass die Wahrscheinlichkeit gering ist, dass die Funktion für zwei verschiedene Argumente der Zeichenfolge dieselbe Ausgabe erzeugt.

4. Verschlüsselungssystem zur Berechtigungsüberprüfung einer von einer ersten Kommunikationseinheit S im System an eine zweite Kommunikationseinheit R im System übertragene Datennachricht,

wobei die erste Kommunikationseinheit Mittel zum Übertragen (2) einer Berechtigungsüberprüfungs- Anforderungsnachricht an die zweite Kommunikationseinheit R umfasst;

wobei die zweite Kommunikationseinheit R Mittel zum Antworten (4) auf eine offenbar von der ersten Kommunikationseinheit S übertragenen Berechtigungsüberprüfungs-Anforderungsnachricht umfasst, wobei die erste Einheit die Datennachricht offenbar übertragen hat, wobei das Mittel zum Antworten ein Mittel zum Übertragen einer Antwortnachricht beinhaltet;

wobei die erste Einheit S Mittel zum Erzeugen einer Berechtigungsüberprüfungsnachricht und zum Übertragen (6) der erzeugten Berechtigungsüberprüfungsnachricht an die zweite Einheit R umfasst; und

wobei die zweite Einheit R Mittel zum Erzeugen der Berechtigungsüberprüfungsnachricht und zum Überprüfen umfasst, ob die empfangene Berechtigungsüberprüfungsnachricht mit der in der zweiten Einheit R erzeugten Berechtigungsüberprüfungsnachricht übereinstimmt;

dadurch gekennzeichnet, dass

das System ein Verschlüsselungssystem mit nichtschmiedbarem öffentlichem Schlüssel ist;

das Mittel zum Antworten auf eine Berechtigungsüberprüfungs-Anforderungsnachricht Mittel zum Übertragen (4) der mit dem nichtschmiedbaren öffentlichen Schlüssel der ersten Einheit verschlüsselten Antwortnachricht beinhaltet;

die erste Einheit S Mittel zum Entschlüsseln der verschlüsselten Antwortnachricht durch unter Verwendung ihres privaten Schlüssels umfasst, um die Antwortnachricht zu erhalten; und

die von der ersten Einheit S erzeugte Berechtigungsüberprüfungsnachricht eine Funktion der Datennachricht und der entschlüsselten Antwortnachricht ist.

5. System nach Anspruch 4, wobei die Antwortnachricht eine willkürliche Zeichenfolge ist.

6. System nach Anspruch 4 oder 5, wobei die im Mittel zum Erzeugen verwendete Funktion so gewählt wird, dass die Wahrscheinlichkeit gering ist, dass die Funktion für zwei verschiedene Argumente der Zeichenfolge dieselbe Ausgabe erzeugt.