DE19803939A1

DE19803939A1 - Verfahren zur Identifizierung von Zugangsbefugten

Info

Publication number: DE19803939A1
Application number: DE19803939A
Authority: DE
Inventors: Scott A Vanstone; Donald B Johnson
Original assignee: Certicom Corp
Current assignee: Certicom Corp
Priority date: 1997-01-31
Filing date: 1998-02-02
Publication date: 1998-08-13
Anticipated expiration: 2018-02-03
Also published as: GB2321834A; FR2759226A1; CA2228185C; DE19803939B4; GB9801792D0; US6446207B1; CH694603A5; FR2759226B1; US20020152385A1; GB2321834B; CA2228185A1; US7036015B2

Description

Die vorliegende Erfindung betrifft die Datenübermittlung und insbesondere Datenübermittlungssysteme, die die beteiligten Teilnehmer identifizieren.

Es ist Stand der Technik, Daten elektronisch zwischen einem Paar von Datenendeinrichtungen auszutauschen, beispielsweise einem Paar von Computerstationen oder einer Magnetkarte und ei ner Computerstation. Weitverbreitet ist ein derartiger Datenaustausch im Bankbereich, um Transaktionen durchzuführen.

Um die Vertraulichkeit solcher Transaktionen zu gewährleisten, ist es notwendig, ein System anzuwenden, das die Identität der Teilnehmer feststellen kann, und für diesen Zweck ist eine ganze Zahl von Kennungs-Übertragungsprogrammen entwickelt wor den. Derartige Programme basieren auf El Gamal Kennungs-Über tragungsprogrammen, die das Diffie-Hellman Verschlüsselungs schema mit öffentlichem Zugang verwenden. Ein allgemein benutz tes Verschlüsselungsschema ist das als RSA bekannte, um damit aber eine abgesicherte Übermittlung zu erreichen, muß ein um fangreicher Modul benutzt werden, der die Bandbreite erhöht und im allgemeinen unerwünscht ist, wenn nur eine begrenzte Rechen kapazität vorhanden ist. Ein robusteres Schema ist das als Ver schlüsselungssystem auf der Basis elliptischer Kurven (ECC) be kannte, das eine vergleichbare Sicherheit gegenüber dem RAS Verschlüsselungssystem liefert, aber mit reduziertem Modul.

Grundsätzlich hat jeder Teilnehmer einen Geheimschlüssel und einen Schlüssel mit öffentlichem Zugang, der von dem Geheim schlüssel abgeleitet ist. Normalerweise ist eine Nachricht für die Datenübertragung verschlüsselt mit dem Schlüssel mit öf fentlichem Zugang des gewünschten Empfängers und kann dann von diesem Empfänger mittels des Geheimschlüssels, der nur dem Emp fänger bekannt ist, entschlüsselt werden. Für Kennzeichnungs- und Identifizierungszwecke wird die Nachricht mit dem Geheim schlüssel des Senders versehen, so daß sie durch Bearbeitung mit dem Schlüssel mit öffentlichem Zugang des angegebenen Sen ders identifiziert werden kann. Da der Geheimschlüssel des Sen ders nur diesem bekannt sein sollte, bestätigt die erfolgreiche Entschlüsselung mit dem Schlüssel mit öffentlichem Zugang des Senders dessen Identität.

Die EL Gamal Kennungs-Übertragungsprogramme erhalten ihre Sicherheit aus der Schwierigkeit, diskrete Logarithmen in einem begrenzten Feld zu berechnen. Kennungen vom EL Ga mal-Typ arbeiten in irgendeiner Gruppen die Gruppen von elliptischen Kurven enthält. Ist beispielsweise die Gruppe elliptischer Kurven E(F_q) gegeben, dann reduziert sich für P ε E(F_q) und Q = aP die Frage nach dem diskreten Log arithmus darauf, die ganze Zahl a zu finden. Mit einer geeignet ausgewählten zugrundeliegenden Kurve ist diese Frage rechnerisch nicht zu beantworten und daher sind diese Verschlüsselungssysteme als sicher anzusehen.

Es existieren verschiedene Übertragungsprogramme zur Ausführung derartiger Systeme. Beispielsweise ist ein digitaler Algorith mus DSA eine Variante des EL Gamal Systems. In diesem System erzeugt jede von einem Paar von korrespondierenden Einheiten A und n einen Schlüssel mit öffentlichem Zugang und einen zugehö rigen Geheimschlüsse). Die Einheit A kennzeichnet eine Nach richt in von willkürlicher Lange mit ihrem Geheimschlüssel. Die Einheit B kann diese Kennung durch die Benutzung von A's Schlüssel mit öffentlichem Zugang identifizieren. In jedem Fall- wie auch immer - müssen beide, der Sender, Einheit A, und der Empfänger, Einheit B, umfangreiche Rechenoperationen, typischerweise eine Potenzierung, durchführen, um die Kennung zu erzeugen bzw. zu identifizieren. Wenn jeder Teilnehmer aus reichende Rechenkapazität zur Verfügung hat, macht das keine Probleme, wenn aber einer oder beide Teilnehmer nur eine be grenzte Rechenkapazität besitzen, so wie bei der Verwendung ei ner "smart card", können die Berechnungen Verzögerungen im Kennzeichnungs- und Identifizierungsprozeß hervorrufen.

Es gibt auch Gelegenheiten, bei denen ein Kennungsgeber seine eigene Kennung identifizieren muß. Zum Beispiel ist die Vertei lung der Schlüssel in einem Verschlüsselungssystem mit öffent lichem Zugang leichter als diejenige in einem symmetrischen Verschlüsselungssystem. Wie auch immer, die Vertraulichkeit der Schlüssel mit öffentlichem Zugang ist kritisch. Deshalb können die Einheiten in einem solchen System einen vertrauenswürdigen dritten Teilnehmer einschalten, der den Schlüssel mit öffentli chem Zugang jeder Einheit bestätigt. Dieser dritte Teilnehmer kann dann eine Betätigungs-Autorität (CA) sein, die einen all gemeinen Kennungs-Algorithmus S_T und einen Identifikations-Al gorithmus V_T hat, von denen angenommen wird, das sie allen Ein heiten bekannt sind. In der einfachsten Form liefert die CA eine Bestätigung, die die Identität einer Einheit an ihren Schlüssel mit öffentlichem Zugang bindet. Diese kann aus der Kennung einer Nachricht bestehen, die einen Identifizierer und den bestätigten Schlüssel mit öffentlichem Zugang der Einheit enthält. Von Zeit zu Zeit kann die CA jedoch wünschen, ihre ei genen Bestätigungen zu bestätigen oder zu identifizieren.

Wie oben angegeben, kann die Kennungs-Identifizierung rechne risch umfangreich sein und die Durchführung in einer angemesse nen Zeit eine erhebliche Rechenkapazität erfordern. Wenn einer der beteiligten nur eine begrenzte Rechenkapazität zur Verfü gung hat, was der Fall ist, wenn eine "smart card" als cash card benutzt wird, ist es vorzuziehen, ein Übertragungsprogramm einzuführen, das die Berechnungen auf der Karte minimiert. Ebenso ist, wenn eine große Zahl von Kennungen identifiziert werden muß, eine schnelle Identifizierungseinrichtung wün schenswert.

Deshalb ist es ein Ziel der vorliegenden Erfindung, ein Ken nungs- und Identifizierungs-Übertragungsprogramm zur Verfügung zu stellen, das die Benutzung von begrenzter Rechenkapazität für eine der Datenendeinrichtungen und die Identifizierung der Kennung erleichtert.

Allgemein ausgedrückt stellt die vorliegende Erfindung ein Ver fahren zur Erzeugung und Identifizierung einer Kennung zwischen einem Paar von Datenendeinrichtungen zur Verfügung, von denen jede an einer gemeinsamen Geheimzahl teilhat, wobei das Verfah ren die Schritte umfaßt, bei einer der Datenendeinrichtungen aus einer ausgewöblten ganzen Zahl einen Übermittlungsschlüssel zu erzeugen, einen Teil des vorgenannten Übermittlungsschlüs sels auszuwählen und mit diesem ausgewählten Teil eine Nach richt zu verschlüsseln, eine Kontrollsumme des vorgenannten ausgewählten Teils zu erzeugen, eine Kennungskomponente zu berechnen, die die vorgenannte gemeinsame Geheimzahl, die vor genannte Kontrollsumme und die vorgenannte ausgewählte ganze Zahl enthält, und die Kennungskomponente, die verschlüsselte Nachricht und die Kontrollsumme zur anderen Datenendeinrichtung zu schicken. Die ausgewählte ganze Zahl kann mittels der gemeinsamen Geheimzahl und dem verschlüsselten Übermittlungs schlüssel auf der Kennungskomponente wiederhergestellt werden. Der Rest des wiederhergestellten Übermittlungsschlüssels kann dann benutzt werden, um dem Empfänger bei Bedarf eine bestä tigte Identifizierungs-Anfrage zu übermitteln.

Eine Ausführungsform der Erfindung wird nun beispielhaft an Hand der zugehörigen Abbildungen beschrieben, wobei

Fig. 1 eine schematische Darstellung eines Datenübermitt lungssystems,

Fig. 2 ein schematisches Flußdiagramm eines Kennungs-Identi fizierungs-Programms,

Fig. 3 ein schematisches Flußdiagramm eines alternativen Programms und

Fig. 4 ein schematisches Flußdiagramm eines weiteren Pro gramms ist.

Die Fig. 1 zeigt ein Datenübermittlungssystem 10, das eine Mehrzahl von Datenendeinrichtungen 12a, 12b, . . ., 12 t (allgemein gekennzeichnet durch das Bezugszeichen 12) aufweist, die durch eine Datenübermittlungsleitung 16 untereinander ver bunden sind. Die Datenendeinrichtungen 12 sind typischerweise elektronische Terminals mit einer begrenzten Rechenkapazität und im vorliegenden Beispiel wird angenommen, daß die Datenend einrichtung 12 die Form einer smard card mit begrenztem Spei cher und begrenzter Rechenkapazität hat. Das Datenübermitt lungssystem 10 umfaßt außerdem eine Datenendeinrichtung 14, die im vorliegenden Beispiel ein Terminal in einer Bank sein soll, der mittels Datenübermittlungsleitung 16 mit den verschiedenen Terminals 12 verbunden ist. Eine solche Verbindung besteht ty pischerweise nur vorübergehend, wenn die Datenendeinrichtungen 12 das System 10 regelmäßig wiederkehrend beanspruchen, kann aber auch dauerhaft sein.

Die Datenendeinrichtungen 12, 14 haben jede eine Verschlüsse lungseinheit, die mit den Bezugszeichen 18, 20 gekennzeichnet sind und ein übliches Verschlüsselungssystem bilden. Im in Rede stehenden Beispiel wird dabei vorausgesetzt, daß die Verschlüsselungseinheiten 18, 20 ein Verschlüsselungssystem auf der Basis elliptischer Kurven mit festgelegten zugrundeliegen den Kurvenparametern und einem Ausgangspunkt P auf dieser Kurve ausführen.

Jede der Datenendeinrichtungen 12 umfaßt außerdem einen Spei cher 22, in dem jeweils eine spezielle Geheimzahl d gespeichert ist, die als Langzeit-Geheimzahl der Datenendeinrichtung 12 für eine Vielzahl von Transaktionen dient. Die Datenendeinrichtung 14 hat einen Schlüssel mit öffentlichem Zugang Q_B, und eine Zahl von vorberechneten Werten von dQ_B ist in einem adressier baren Speicher 24 bei der Datenendeinrichtung 12 gespeichert, um die Kennung zu erleichtern.

Auf jeder Karte ist ein Zahlengenerator 26 enthalten, um eine statistisch eindeutige, aber unvorhersagbare ganze Zahl beim Start jeder Übermittlung zu erzeugen, die als Kurzzeit-Geheim zahl dient, die bei jeder Transaktion wechselt.

Die Datenendeinrichtung 14 enthält in ähnlicher Weise einen Speicher 28 mit einer Datenbank, die die jeweilige Langzeit- Geheimzahl d jeder Datenendeinrichtung 12 speichert und mit der Identität jeder einzelnen der Datenendeinrichtungen 12 korre liert.

Um ein Identifizierungs-Übertragungsprogramm zu starten, formu liert eine der Datenendeinrichtungen 12 eine Nachricht m und erzeugt eine zufällige ganze Zahl k mit dem Generator 26, die als Kurzzeit-Geheimzahl während der Übermittlung dient. Unter Benutzung des Ausgangspunktes p berechnet sie einen Übermitt lungsschlüssel r, der mit kP korreliert ist. kP ist tatsächlich ein Punkt auf der zugrundeliegenden Kurve mit den Koordinaten (x, y).

Eine erste Kennungskomponente e wird durch Verschlüsselung ei ner Nachricht m erzeugt, wobei die binäre Darstellung der x-Ko ordinate benutzt wird, so daß e = E_x(m).

Eine zweite Kennungskomponente e' wird durch Kontrollsummenbil dung der x-Koordinate des Übermittlungsschlüssels r erzeugt, so daß e' = h(x). Dabei wird eine geeignete verschlüsselte Kon trollsummenfunktion benutzt, wie z. B. der Sicherungs-Kontroll summen-Algorithmus (SHA-1) nach dem Vorschlag des US National Institut for Standard and Technology (NIST).

Eine dritte Kennungskomponente s wird in der allgemeinen vorm B = ae+k (mod n) erzeugt, wobei a die Langzeit-Geheimzahl, e ein durch Kontrollsummenbildung eines Nachrichtenabschnitts ab geleiteter Wert und k der Kurzzeit-Geheimschlüssel ist. In diesem Ausführungsbeispiel) hat die Kennungskomponente s die spezielle Form

s = d.h(dQ_B || e')+k (mod n),

wobei n die Ordnung der zugrundeliegenden Kurve ist. Die Ken nungskomponente s wird erhalten durch Zurückholen des vorberechneten Wertes von dQ_B aus dem Speicher 24 der Datenend einrichtung 12 und deren Verknüpfung mit dem Kontrollsummen- Wert von x und anschließender Kontrollsummenbildung für das Resultat.

Eine Kennung, die die Kennungskomponenten s, e und e' umfaßt, wird dann der Datenendeinrichtung 14 geschickt. Nach dem Emp fang holt die Datenendeinrichtung 14 den Langzeit-Geheimschlüs sel d von der Datenbank 28 zurück, der auf der angezeigten Identität der Datenendeinrichtung 12 beruht, und berechnet zu sammen mit seinem eigenen Schlüssel mit öffentlichem Zugang Q_B und dem empfangenen Teil e' die Kontrollsumme h || dQ_B = e'. Da mit und mit der Kennungskomponente s kann ein Wert k' erhalten werden, der analog zu k sein sollte.

Mittels Benutzung des berechneten Wertes von k und dem Aus gangspunkt P kann eine Funktion erhalten werden, die mit dem berechneten Wert des Kurzzeit-Schlüssel, nämlich dem Wert der x-Koordinate von kP, x', verknüpft ist. Von dem berechneten Wert von x' wird dann die Kontrollsumme gebildet und ein Ver gleich durchgeführt, um zu prüfen, ob der resultierende Wert der Kontrollsumme mit dem empfangenen Wert von e' zusammen paßt. In diesem Stadium ist die Identifizierung der Datenend einrichtung erhalten worden und die einzige erforderliche Potenzierung ist die Ausgangsberechnung von kP.

Die Berechnung des Übermittlungsschlüssels r und der folgende Gebrauch eines Abschnitts dieses Übermittlungsschlüssels ermög licht eine sichere Bestätigung, die von der Datenendeinrichtung 14 zurückgeschickt wird. Wenn der Wert der Koordinate x berech net worden ist, kann die Datenendeinrichtung 14 die Koordinate y berechnen und diese benutzen, um eine Nachricht m' als Bestä tigung zu verschlüsseln. Die Datenendeinrichtung 14 antwortet so an die Datenendeinrichtung 12 durch Übersendung einer Nach richt, die Ey(m') enthält. Nach dem Empfang kennt die Datenend einrichtung 12 die y-Koordinate des Übermittlungsschlüssel R und kann die Nachricht m' zurückgewinnen, die zweckdienlicher weise eine Identifizierungsanfrage enthält. Die Datenendein richtung 12 entschlüsselt die Nachricht und sendet die Identi fizierungsantrage an die Datenendeinrichtung 14 zurück, so daß die Datenendeinrichtungen identifiziert und synchronisiert sind. Weitere Nachrichten können dann zwischen den Datenendein richtungen 12 und 14 übermittelt werden, wobei der Übermitt lungsschlüssel R für die Verschlüsselung benutzt wird.

Daraus wird ersichtlich, daß in dein vorgenannten Programm ein Paar von Schlüsseln benutzt wird und die Datenendeinrichtung 14 die Kontrolle über einen der Schlüssel zurückbehält, der einen Langzeit-Geheimschlüssel zur Verfügung stellt und diesen dazu benutzt, den Kurzzeit-Übermittlungsschlüssel zu entschlüsseln, der von der Datenendeinrichtung 12 berechnet wurde. Der ent schlüsselte Kurzzeit-Schlüssel kann dann für die Iden tifizierung mit allen übermittelten Kennungskomponenten benutzt werden, zum Beispiel durch Prüfen von e'.

Alternativ kann die Struktur des entschlüsselten Wertes des Schlüssels auf die Identifizierung hinweisen, zum Beispiel durch das Muster, die Zahl oder die Verteilung der Ziffern, so daß der entschlüsselte Wert mit vorbestimmten Parametern für die Identifizierung verglichen werden kann. Aufgrund der Bezie hung zwischen dem entschlüsselten Teil und der übersandten In formation kann der andere Abschnitt des Übermittlungsschlüssel benutzt werden, um zu antworten und die Synchronisation herzu stellen.

Bei diesem Ausführungsbeispiel ist festzustellen, daß die Ken nungs-Identifizierung in einer rechnerisch zweckmäßigen Weise ohne Potenzierung und damit relativ schnell durchgeführt wird.

Es sei außerdem darauf hingewiesen, daß das System 10 als Ver schlüsselungssystem mit öffentlichem Zugang zwischen den Date nendeinrichtungen 12 oder den Datenendeinrichtungen 12, 14 funktionieren kann, wenn aber eine schnelle Identifizierung gefordert wird, kann es die Merkmale eines symmetrischen ver schlüsselten Übertragungsprogramms anwenden.

Wie weiter unten veranschaulicht wird, können alternative Ken nungen benutzt werden und im allgemeinen irgendeine El Gamal Kennungs-Gleichung benutzt werden. Ein alternatives Ausfüh rungsbeispiel von Kennungs-Identifizierung kann durchgeführt werden, indem das DSS Kennungs-Übertragungsprogramm wie in Fig. 3 gezeigt benutzt wird. In diesem Programm wird ein Kurzzeit- Schlüssel mit öffentlichem Zugang r durch Potenzierung des Gruppenerzeugers α mit einer zufälligen ganzen Zahl k, bei spielsweise r = α^k, abgeleitet. (Wenn ein Verschlüsselungssy stem auf der Basis einer elliptischen Kurve benutzt wird, dann wird die Potenzierung mittels einer k-fachen Addition des Aus gangspunktes P durchgeführt, so zum Beispiel r = kP).

Mit dem DSS-Übertragungsprogramm ist die Kennungskomponente s von der Form

s = k^-1(h(m)+dr) (mod n),

wobei d ein Langzeit-Geheimschlüssel und m die Nachricht ist. Die Werte der Kennungskomponenten s, r und die Nachricht m wer den von der Datenendeinrichtung 12 zur Datenendeinrichtung 14 geschickt.

Datenendeinrichtung 24 hat an dem Langzeit-Geheimschlüssel d teil und kann so den Kurzzeit-Geheimschlüssel aus der Identität k = s(h(m)+dr) zurückgewinnen.

Wenn die Werte von r, m und s gesendet worden sind und die Da tenendeinrichtung 14 d kennt, kann k berechnet werden.

Wie oben erwähnt, kann k so angeordnet sein, daß es eine spe zielle Struktur hat, beispielsweise ein spezielles Muster -oder eine bestimmte Zahl von 1-en, was dann für die Identifizierung benutzt werden kann. Alternativ kann die Identifizierung durch Berechnung einem Wertes von r aus dem entschlüsselten Ausdruck k (d. h.r=α^k) und Vergleich fit dem übermitteiten r getestet werden. Dieser Schritt erfordert eine Potenzierung und ist da her rechnerisch anspruchsvoller, kann aber benutzt werden, wenn es wünschenswert ist.

Wenn der Langzeit-Geheimsschlüssel d beiden Datenendeinrichtungen bekannt ist, kann eine Identifizierung wiederum in einer einfa chen aber wirksamen Weise durch Herausziehen des Kurzzeit-Ge heimschlüssels k erfolgen.

In jedem der vorgenannten Beispiele wird die Kennungs-Identifi zierung zwischen einem Paar von Datenendeinrichtungen durchge fährt. Die charakteristischen Merkmale des Programms können be nutzt werden, um eine Kennung zu identifizieren, die von einer Bestätigungs-Autorität CA, beispielsweise einer Bank, die die Datenendeinrichtung 14 darstellt, ausgegeben worden ist.

In diesem Ausführungsbeispiel empfängt die Datenendeinrichtung 14 eine Bestätigung, die besagt, daß sie von ihr selbst ausge geben worden ist. Die Datenendeinrichtung 14 identifiziert die Echtheit der Bestätigung mittels Benutzung des Langzeit-Geheim schlüssels d, um den Kurzzeit-Geheimschlüssel k herauszuziehen. Die Struktur des Geheimschlüssels k kann dann geprüft werden oder der Schlüssel k kann benutzt werden, um eine Information bezüglich des Kurzzeit-Schlüssels mit öffentlichem Zugang r, der in der Nachricht enthalten ist, abzuleiten. Die Identifi zierung kann wiederum ohne umfangreiche Berechnungen in einer zweckmäßigen Weise erhalten werden und erlaubt die Iden tifizierung von Bestätigungen, die von der Datenendeinrichtung 14, z. B. einer Bank oder einer Finanzinstitution, empfangen wird.

Dieses Ausführungsbeispiel kann veranschaulicht werden, indem der digitale Kennungs-Algorithmus DSA benutzt wird, der ein spezieller Fall des El Gamal Kennungsschemas ist. Für die Schlüssel-Erzeugung in dem El Gamal Kennungsschema erzeugt jede Datenendeinrichtung A und B einen Schlüssel mit öffentlichem Zugang und einen zugehörigen Geheimschlüssel. Um das zu grundeliegende Verschlüsselungssystem in einer Gruppe F_p fest zulegen, wählen die Einheiten A und B Primzahlen p and g so, daß q p-1 teilt. Ein Generator g wird so ausgewählt, daß er ein Element von der Ordnung g in F_p und die benutzte Gruppe {g°, g¹, g², . . . g^q-1} ist.

In dem digitalen Kennungs-Algorithmus (DSA) wird die Schlüssel- Erzeugung mittels Auswahl einer zufälligen ganzen Zahl d im Intervall [1,q-1] und Berechnung eines Langzeit-Schlüssels mit öffentlichem Zugang y = g^d mod p durchgeführt. Die Information des Schlüssels mit öffentlichem Zugang ist (p,q,g,y) und der Langzeit-Geheimschlüssel ist d, während in dem allgemeinen El Gamal-Schema die Information des Schlüssels mit öffentlichem Zugang (p,g,y) und der Geheimschlüssel d ist.

In einem DSA Kennungs-Schema werden die Kennungs-Komponenten r und s gegeben durch:
r = (g^k mod p) mod q und
s = k^-1(h(m)+dr) mod q,
wobei typischerweise gilt:
d ist eine zufällige ganze Zahl, der Langzeit-Geheim schlüssel des Kennungsgeber, und ist typischerweise 160 bits lang;
p ist typischerweise eine 1024 bit-Primzahl;
g ist eine 160-bit Primzahl, wobei q p-1 teilt;
g ist der Generator, so daß y = g^d mod p;
h(m) ist typischerweise eine SHA-1 Kontrollsumme der Nachricht m;
k ist ein zufällig ausgewählter 160-bit Wert für jede Kennung und die Kennung für in ist das Paar (r,s)

Normalerweise sollte der Empfänger B zur Identifizierung der Kennung (r,s) von A auf der Nachricht in die authentische Infor mation des Schlüssels mit öffentlichem Zugang (p,g,g,y) von A erhalten und identifizieren, daß 0<r<q und 0<s<q ist. Dann wer den die Werte w=s^-1 mod q und h(m) berechnet. Danach folgt die Berechnung von u₁=w.h(m) mod q und u₂=r.w mod q und v=(g^ul.y ^u2 mod p) mod q. Die Kennung wird akzeptiert, wenn und nur wenn v = r. Daraus ergibt sich, daß in einigen Fällen, wenn der Ei gentümer einer Kennung seine eigene Kennung zu einem späteren Zeitpunkt identifizieren will, es sehr zeitaufwendig sein kann, die Information des Schlüssels mit öffentlichem Zugang zurück zugewinnen und die vorstehenden Schritte durchzuführen, die ein Paar von Potenzierungen umfassen.

Eine schnelle Kennungs-Identifizierung durch die Bestätigungs- Autorität CA kann wie in Fig. 4 gezeigt ausgeführt werden, in dem der Langzeit-Geheimschlüssel d der Bestätigungs-Autorität als Identifizierung benutzt wird. In diesem Falle hat der ur sprüngliche Kennungsgeber Kenntnis von p,g,g,y,h(m), r und s. Dann braucht der Identifizierer nur den Kurzzeit-Geheimschlüs sel k, der in der Kennung benutzt ist, zu entschlüsseln und den so erhaltenen Wert k zu identifizieren, um die Kennung zu iden tifizieren. Der Identifizierer berechnet also z = (h(m)+dr) mod q. Dann wird der Wert z^-1 durch Invertierung von z mod q be rechnet und benutzt, um k'^-1 = s(z^-1) mod q zu berechnen. k' kann durch Invertierung von k'^-1 mod q bestimmt werden. Der Identifizierer berechnet dann r = g^k' mod p mod q und identi fiziert, das k = k' ist. Dabei ist zu sehen, daß dieser Identi fizierungsschritt statt des Langzeit-Schlüssel mit öffentlichem Zugang y vielmehr den Langzeit-Geheimschlüssel d benutzt, um das Potenzieren zu vermeiden. Natürlich können viele von den obengenannten Berechnungen durch Benutzung vorberechneter Ta bellen beschleunigt werden.

Eine alternative El Gamal-Kennungsmethode ist in Fig. 5 gezeigt und hat Kennungskomponenten (s,e), wobei:
r = g^k mod p;
e = h(m||r), wobei die || eine Verkettung anzeigen,
und
s = (de+k) mod p,
wobei p eine große öffentlich zugängliche Primzahl, g ein öf fentlich zugänglicher Generator, in eine Nachricht, a eine Kon trollsummen-Punktion, d ein Langzeit-Geheimschlüssel, y = g^d mod p der zugehörige Langzeit-Schlüssel mit öffentlichem Zugang und k eine geheime zufällige ganze Zahl ist, die als Kurzzeit- Geheimschlüssel verwendet wird.

Um eine Bestätigung zu erzeugen, kennzeichnet die Datenendein richtung 14 eine Nachricht in, die die Identität von einer der Datenendeinrichtung 12 enthält, und den Schlüssel mit öffentli chem Zugang dieser Datenendeinrichtung. Die Nachricht wird ge kennzeichnet, indem der Langzeit-Schlüssel mit öffentlichem Zu gang und ein Kurzzeit-Übermittlungsschlüssel k der Datenendein richtung 14 und eine Bestätigung, die der Datenendeinrichtung 12 zugeordnet wurde und die Kennungskomponente s, e enthält, benutzt werden. Die Information mit öffentlichem Zugang wird von der Datenendeinrichtung 14 aufbewahrt. Die Bestätigung kann von der Datenendeinrichtung 12 benutzt werden und von Empfän gern identifiziert werden, die den Schlüssel mit öffentlichem Zugang der Datenendeinrichtung 14 benutzen.

Wenn der Datenendeinrichtung 14 eine Bestätigung vorgelegt wird, kann mittels Benutzung des Langzeit-Geheimschlüssels d eine schnelle Identifizierung erhalten werden.

Bei schneller Kennungs-Identifizierung, die den Geheimschlüssel d benutzt, ist dem Identifizierer die Information mit öffentli chem Zugang aus p,g,y,h,m,r,e und der Geheimschlüssel d be kannt. So braucht der Identifizierer nur den Kurzzeit-Geheim schlüssel k zu entschlüsseln und k zu identifizieren, um die Kennung zu identifizieren. Der Identifizierer berechnet k' = (s-de) mod p, r'=g^k' mod p und e' = h (m||r'). Wenn e = e' ist, ist auch k = k' verwirklicht. Bei dieser Identifizierung ist nur eine Potenzierung erforderlich, was den Prozeß erleich tert. Alternativ können die charakteristischen Merkmale des entschlüsselten Wertes von k ausreichend sein, um der Identifi zierung zu genügen, wie oben diskutiert.

Daraus ergibt sich, daß es ein besonderer Vorteil der vorlie genden Erfindung ist, wenn ein Kennungsgeber Daten kennzeich net, die zum Beispiel in dem Computer des Kennungsgebers ver bleiben. Dies kann später ohne Benutzung des zugehörigen Schlüssel mit öffentlichem Zugang identifiziert werden, statt dessen kann der Kennungsgeber seinen Geheimschlüssel benutzen, um die Daten zu identifizieren. Dies ist auch sehr nützlich für manche Anwendungen mit begrenzter Rechenkapazität wie bei spielsweise bei smart cards.

In einem Datenaustauschsystem, das eine Bestätigungs-Autorität einschließt, wird die Bestätigungs-Autorität (CA) oder ein Schlüsselverteilungszentrum die Daten häufig mit einer Nennung versehen, bevor sie in die verschiedenen Kommunikationssysteme installiert sind, und könnte dann die Kennung später identifi zieren. So braucht die CA nicht die Information des Schlüssel mit öffentlichem Zugang, um die Kennung zu identifizieren, son dern benutzt einfach den Langzeit-Geheimschlüssel zum Identifi zieren, wenn alle anderen Parameter innerhalb des Sicherheits bereichs dem Kennungsgebers gespeichert sind. Es sei außerdem darauf hingewiesen, daß es, wenn der Langzeit-Geheimschlüssel d benutzt wird, nicht notwendig ist, den Kurzzeit-Geheimschlüssel k aufzubewahren, so daß der für das System erforderliche Ver waltungsaufwand minimiert wird.

Eine weitere Anwendung ist in der Identifizierung von Software wie in pay-per-use software-Anwendungen gegeben. Eine Anforde rung für den Zugang zu einem Server kann durch eine Bestätigung kontrolliert werden, die von dem Server ausgegeben wurde und von dem Benutzer der Software vorgelegt wird. Die Echtheit der Bestätigung kann identifiziert werden, indem der Geheimschlüs sel dem Servers in einer schnellen Art und Weise benutzt wird wie oben beschrieben.

Während die Erfindung in Verbindung mit speziellen Ausführungs beispielen und speziellen Benutzungsarten beschrieben worden ist, werden dem einschlägigen Fachmann verschiedene Weiterbil den davon offenbar werden, ohne daß sich diese vom Inhalt der Erfindung, so wie er in den anhängenden Patentansprüchen nie dergelegt ist, entfernen. Zum Beispiel ist in der vorstehenden Beschreibung von bevorzugten Ausführungsbeispielen von einer multiplikativen Notation Gebrauch gemacht worden, obwohl das Verfahren des Erfindungsgegenstandes in gleich guter Weise be schrieben werden kann, wenn eine additive Notation verwendet wird. Es ist beispielsweise allgemein bekannt, daß das Äquiva lent des DSA zum Algorithmus der elliptischen Kurven, d. h. der ECDSA, das Analogon von elliptischen Kurven zu einem diskreten Logarithmus-Algorithmus ist, die üblicherweise beschrieben wird durch die Festlegung von F''_p, die multiplikative Gruppe der ganzen Zahlen modulo einer Primzahl. Es gibt einen Zusammenhang zwischen den Elementen und Operationen der Gruppe F''_p und der Gruppe der elliptischen Kurven E(F_q). Darüber hinaus ist diese Kennungstechnik gleichermaßen gut anwendbar auf Funktionen, die in einem Feld verlaufen, das über F_2''definiert ist.

Die vorliegende Erfindung ist daher grundsätzlich mit einem Verschlüsselungsverfahren und -system und insbesondere einer Verschlüsselungsmethode und einem Verschlüsselungssystem auf der Basis elliptischer Kurven verbunden, in der bzw dem finite Feldelemente in einer prozessortauglichen Weise multipliziert werden. Das Verschlüsselungssystem kann irgendeine geeignete Prozessoreinheit enthalten wie beispielsweise einen geeignet programmierten Mehrzweck-Computer.

Claims

1. Verfahren zur Identifizierung einer digitalen Kennung, die von einem Kennungsgeber in einem Datenkommunikationssystem erzeugt wird, wobei diese Kennung Kennungskomponenten hat, die ein Paar von Geheimschlüsseln einschließen, und wobei die Methode die folgenden Schritte umfaßt:

- Anbringen eines ersten der vorgenannten Geheimschlüs sel in der vorgenannten Kennung zur Wiederherstellung eines Wertes, der zu einer mit einem zweiten der vor genannten Geheimschlüssel verknüpften Funktion äqui valent ist, und
- Vergleichen des vorgenannten wiederhergestellten Wer tes mit der vorgenannten Funktion, um die Echtheit der besagten Kennung festzustellen.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der vorgenannte wiederhergestellte Wert benutzt wird, um einen Wert von einer der vorgenannten Kennungskomponen ten zu berechnen und diesen berechneten Wert und die be sagte Kennungskomponente zu vergleichen, um die vorge nannte Kennung zu identifizieren.

3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Struktur des vorgenannten wiederhergestellten Wer tes mit vorgegebenen Parametern verglichen wird, um die besagte Kennung zu identifizieren.

4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß einer der vorgenannten Schlüssel ein Langzeitschlüssel und der andere der vorgenannten Schlüssel ein für jede Kennung erzeugter Kurzzeitschlüssel ist.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß der vorgenannte wiederhergestellte Wert dem vorgenann ten Kurzzeitschlüssel entspricht.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß der vorgenannte wiederhergestellte Wert benutzt wird, um einen Kurzzeitschlüssel mit öffentlichem Zugang zu be rechnen, der von dem vorgenannten Geheimschlüssel abgelei tet wird und in den vorgenannten Kennungskomponenten ent halten ist.

7. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß mindestens ein Teil des besagten wiederhergestellten Wertes mittels einer verschlüsselnden Kontrollsummenfunk tion aufsummiert und ein resultierender Kontrollsummenwert mit einer der vorgenannten Kennungskomponenten zur Identi fizierung verglichen wird.

8. Verfahren zur Identifizierung einer digitalen Kennung, die von einem Kennungsgeber in einem Computersystem erzeugt wird, wobei der Kennungsgeber einen Geheimschlüssel d und einen Schlüssel mit öffentlichem Zugang y hat, der von ei nem Element g und dem vorgenannten Geheimschlüssel d abge leitet ist, und wobei das Verfahren die folgenden Schritte zum Versehen einer Nachricht in mit einer Kennung in dem vorgenannten Computersystem umfaßt:

a) Erzeugung einer ersten Kennungskomponente durch Ver binden zumindest des vorgenannten Elements g und ei nem Kennungsparameter k gemäß einer ersten mathemati schen Funktion;
b) Erzeugung einer zweiten Kennungskomponente mittels mathematischem Verbinden der vorgenannten ersten Ken nungskomponente mit dem vorgenannten Geheimschlüssel d, der vorgenannten Nachricht in und dein vorgenannten Kennungsparameter k; und
der besagte Kennungsgeber die vorgenannte Kennung identi fiziert durch:
c) Wiederherstellung eines Wertes k' aus der vorgenann ten Kennung ohne Benutzung des besagten Schlüssels mit öffentlichem Zugang y und
d) Verwendung des vorgenannten wiederhergestellten Wer tes k' ihn der vorgenannten ersten mathematischen Funktion zur Ableitung einem Wertes r', um nachzuprü fen, daß die vorgenannten Kennungsparameter k und k' äquivalent sind.

9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß g ein Element von der Ordnung g in einem Feld F''_p.

10. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß g ein Punkt von der Primzahlordnung n in E(F_q) ist, so daß E eine elliptische Kurve ist, die über das Feld F_q definiert ist.

11. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß das vorgenannte Element g ein Punkt auf einer ellipti schen Kurve über einem begrenzten Feld Fq_n ist.

12. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß der vorgenannte Kennungsparameter k eine zufällig ausgewählte ganze Zahl im Intervall [1,q-1] ist und die vorgenannte erste Kennungskomponente eine durch r=g^k mod p mod q definierte Form hat, wobei p und q solche Primzahlen sind, daß q p-1 teilt.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, daß es die Berechnung eines Wertes e = h(m) umfaßt, wobei h eine Kontrollsummenfunktion und die vorgenannte zweite Kennungskomponente s = k^-1(e+dr) mod q ist.

14. Verfahren nach Anspruch 13, dadurch gekennzeichnet, daß der besagte Schritt der Wiederherstellung des vorge nannten Wertes k' folgendes einschließt

a) Berechnung eines Wertes z = (h(m)+dr) mod q;
b) Berechnung von z^-1 durch Invertierung von z mod q;
c) Berechnung von k'^-1 = s(z^-1) mod q und
- (d) Berechnung von k' durch Invertierung von k'^-1 mod q.

15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß der vorgenannte Schritt der Nachprüfung von k die Schritte der Berechnung von r' = g^k' mod p mod q und des Vergleichs von r' mit r umfaßt, um k = k' zu bestätigen.

16. Verfahren nach Anspruch 15, dadurch gekennzeichnet, daß die vorgenannten Berechnungen die Benutzung vorberech neter Tabellen einschließen.

17. Verfahren nach Anspruch 10, dadurch gekennzeichnet, daß der Kennungsparameter k eine statistisch eindeutige und unvorhersagbare ganze Zahl k ist, die aus dem Inter vall [2,n-2] ausgewählt wird, und die vorgenannte erste Kennungskomponente eine durch r = x mod n definierte Form hat, wobei n eine n-te Koordinate eines Geheimschlüssels ist.

18. Verfahren nach Anspruch 17, dadurch gekennzeichnet, daß es die Berechnung eines Wertes e = h(m) umfaßt, wobei h eine Kontrollsummenfunktion und die vorgenannte zweite Kennungskomponente durch s = k^-1(e+dr) mod n gegeben ist.

19. Verfahren nach Anspruch 18, dadurch gekennzeichnet, daß das vorgenannte Wiederherstellen des besagten Wertes k' folgendes einschließt:

a) Berechnung eines Wertes z = (h(m)+dr) mod n;
b) Berechnung von z^-1 durch Invertierung von z mod n;
c) Berechnung von k'^-1 = s(z^-1) mod n und
d) Berechnung von k' durch Invertierung von k'^-1 mod n.

20. Verfahren nach Anspruch 19, dadurch gekennzeichnet, daß der vorgenannte Schritt der Nachprüfung von k die Schritte der Berechnung von r' = g^k' mod n und des Ver gleichs von r' mit r umfaßt, um k = k' zu bestätigen.

21. Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß der vorgenannte Kennungsparameter k eine zufällig aus gewählte ganze Zahl aus dem Intervall [1,p-1] ist und die vorgenannte erste Kennungskomponente eine durch e = h(m||r) definierte Form hat, wobei r = g^k mod p ist, h eine Kontrollsummenfunktion ist und die || eine Ver knüpfung bezeichnen.

22. Verfahren nach Anspruch 21, dadurch gekennzeichnet, daß die vorgenannte zweite Kennungskomponente durch s = (de+k) mod p definiert wird.

23. Verfahren nach Anspruch 22, dadurch gekennzeichnet, daß der vorgenannte Schritt der Wiederherstellung des be sagten Wertes k' folgendes einschließt:

a) Berechnung eines Wertes k' = (s-de) mod p;
b) Berechnung eines Wertes r'= g^k' mod p;
c) Berechnung eines Wertes e'= h(m||r') und
d) Vergleichen des vorgenannten Wertes e' mit e, um k' = k zu bestätigen.

24. Verfahren zur Identifizierung der Echtheit einer Bestäti gung, die von einer Bestätigungs-Autorität in einem elek tronischen Datenkommunikationssystem erteilt wird, wobei dieses Verfahren die folgenden Schritte einschließt:

- Die vorgenannte Bestätigungs-Autorität schließt in die vorgenannte Bestätigung ein Paar von Kennungskom ponenten ein, die von einem Paar von Geheimschlüsseln abgeleitet: sind,
- die vorgenannte Bestätigungs-Autorität behält einen der vorgenannten Geheimschlüssel zurück,
- die vorgenannte Bestätigungs-Autorität empfängt die besagte Bestätigung und wendet den vorgenannten Ge heimschlüssel auf die vorgenannten Kennungskomponen ten an, um davon einen Wert abzuleiten, der einer Funktion des anderen der besagten Geheimschlüssel entspricht, und vergleicht diesen abgeleiteten Wert mit der vorgenannten Funktion, um die Echtheit der vorgenannten Bestätigung festzustellen.

25. Verfahren nach Anspruch 24, dadurch gekennzeichnet, daß der vorgenannte abgeleitete Wert mit vorgegebenen Pa rametern verglichen wird, um die Echtheit der besagten Be stätigung festzustellen.

26. Verfahren nach Anspruch 24, dadurch gekennzeichnet, daß der vorgenannte abgeleitete Wert dem besagten anderen Schlüssel entspricht.

27. Verfahren nach Anspruch 26, dadurch gekennzeichnet, daß der vorgenannte eine Schlüssel ein Langzeit-Geheim schlüssel ist, der für eine Vielzahl von Kennungen verwen det wird und der vorgenannte andere schlüssel ein für jede Kennung abgeleiteter Kurzzeitschlüssel ist.

28. Verfahren nach Anspruch 26, dadurch gekennzeichnet, daß die vorgenannten Kennungskomponenten einen Schlüssel mit öffentlichem Zugang einschließen, der von dem vorge nannten anderen Schlüssel abgeleitet wird, und daß das vorgenannte Verfahren den Schritt der Ableitung eines ent sprechenden Schlüssels mit öffentlichem Zugang von dem vorgenannten abgeleiteten Wert und des Vergleichs des vor genannten Schlüssels mit öffentlichem Zugang in den vorge nannten Kennungskomponenten mit dem besagten entsprechen den Schlüssel mit öffentlichem Zugang einschließt.

29. Datenkommunikationssystem mit einem Paar von durch eine Datenkommunikationsleitung verbundenen Datenendeinrichtun gen, wobei jede der vorgenannten Datenendeinrichtungen eine Verschlüsselungsfunktion zum Ausführen eines öffent lich zugänglichen Verschlüsselungsschemas, das ein Paar von Geheimschlüsseln verwendet, von denen der eine für eine Vielzahl von Übermittlungen zwischen den vorgenannten Datenendeinrichtungen verwendet wird und der andere der vorgenannten Geheimschlüssel bei einem der vorgenannten Datenendeinrichtungen bei jeder Übermittlung erzeugt wird, wobei der vorgenannte eine Geheimschlüssel beiden vorgenannten Datenendeinrichtungen zugehört, um zu gestatten, daß der andere der vorgenannten Geheimschlüssel bei der vorgenannten anderen Datenendeinrichtung von einer digitalen Kennung wiederhergestellt werden kann, die bei der vorgenannten einen Datenendeinrichtung erzeugt und mit einer Kennungskomponente der besagten digitalen Kennung verglichen wird, um die Berechtigung der vorgenannten einen Datenendeinrichtung zu identifizieren.

30. Datenkommunikationssystem nach Anspruch 29, dadurch gekennzeichnet, daß die besagte Verschlüsselungsfunktion ein Verschlüsse lungssystem auf der Basis elliptischer Kurven ausführt.