Beschreibung

Verfahren, Vorrichtung und System zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten

Die Erfindung betrifft ein Verfahren, eine Vorrichtung und ein System zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten.

Kryptographische Verfahren auf Basis elliptischer Kurven sind sehr effizient, was insbesondere daran liegt, dass bei diesen Verfahren im Gegensatz zu bisher bekannten kryptographischen Verfahren keine Angriffsmethoden mit subexponentieller Laufzeit bekannt sind. Anders ausgedruckt bedeutet dies, dass der Sicherheitsgewinn pro Bit der verwendeten Sicherheitsparameter bei Verfahren auf Basis elliptischer Kurven hoher ist und somit für praktische Anwendung deutlich kürzere Schlussellan- gen verwendet werden können.

Somit sind kryptographische Verfahren auf Basis elliptischer Kurven performanter und benotigen eine geringere Bandbreite zur übertragung der Systemparameter als andere kryptographische Verfahren bei vergleichbarem Grad an erreichbarer Sicherheit .

Als Beispiel sei hier das bekannte Diffie-Hellman-Verfahren zur Vereinbarung eines gemeinsamen Schlüssels zwischen zwei Kommunikationsteilnehmern basierend auf elliptischen Kurven umrissen. Hierbei kennt der erste Kommunikationsteilnehmer A einen Sicherheitsparameter r _a und der zweite Kommunikationsteilnehmer B einen Sicherheitsparameter r^ . Nachdem sich die beiden Kommunikationsteilnehmer auf eine elliptische Kurve und auf einen gemeinsamen Punkt P auf dieser elliptischen Kurve geeinigt haben, ermittelt der Kommunikationsteilnehmer A einen Wert

Qa = r _a * P und der Kommunikationsteilnehmer B einen Wert

^Q b = ^r b * ^p -

Im Anschluss hieran wird vom Kommunikationsteilnehmer A der Wert Q _a an den Kommunikationsteilnehmer B übertragen und der

Wert Q _b vom Kommunikationsteilnehmer B an den Kommunikationsteilnehmer A übertragen. In einer weiteren Skalarmultiplika- tion ermittelt nun der Kommunikationsteilnehmer A den gemeinsamen Schlüssel

K = r _a * Q _b = r _a * r _b * P

und der Kommunikationsteilnehmer B denselben gemeinsamen Schlüssel

K = r _b * Q _a = r _b * r _a * P.

Diese Skalarmultiplikationen bilden somit einen wesentlichen Baustein in kryptographischen Verfahren auf Basis ellipti- scher Kurven. Besonders vorteilhaft ist die Anwendung von elliptischen Kurven, da die Invertierungsoperation

^r a,b = ^Q a,b/ ^p

nur mit erheblichem Rechenaufwand berechnet werden kann. Nach heutigem Kenntnisstand ist die Skalarmultiplikation in poly- nomieller Zeit berechenbar aber nur in exponentieller Zeit invertierbar .

Die bekannten kryptographischen Verfahren auf Basis elliptischer Kurven sind jedoch hinsichtlich sog. Seitenkanalangrif- fe verletzbar.

Seitenkanalangriffe sind eine Klasse von Methoden zur Krypto- analyse. Im Gegensatz zu klassischen Angriffen auf kryp- tographische Anwendungen versucht ein Angreifer dabei nicht, den zugrunde liegenden abstrakten mathematischen Algorithmus zu brechen, sondern attaktiert eine spezielle Implementierung

eines kryptographischen Verfahrens. Dazu verwendet der Angreifer leicht zugangliche physikalische Messgroßen der konkreten Implementierung, wie z. B. die Laufzeit der Berechnung, den Stromverbrauch und die elektromagnetische Abstrah- lung des Prozessors wahrend der Berechnung oder das Verhalten der Implementierung bei induzierten Fehlern. Die physikalischen Messwerte einer einzelnen Berechnung können direkt analysiert werden, beispielsweise in einer einfachen Stromanalyse, SPA, oder ein Angreifer zeichnet die Messwerte mehrerer Berechnungen beispielsweise mit einem Speicheroszilloskop auf und wertet die Messwerte anschließend statistisch aus, beispielsweise in einer differentiellen Stromanalyse, DPA. Sei- tenkanalangriffe sind häufig wesentlich effizienter als kryp- toanalytische Techniken und können selbst Verfahren brechen, die aus Sicht der Algorithmen als sicher gesehen werden, wenn die Implementierung dieser Algorithmen nicht gegen Seitenka- nalangriffe abgesichert ist. Somit ist erkannt worden, dass die konkrete Implementierung von kryptographischen Verfahren, welche auf elliptischen Kurven basieren, für den schlussend- lieh resultierenden Grad an erreichbarer Sicherheit der jeweiligen Applikationen von erheblicher Bedeutung ist. Insbesondere für Smart Cards und Embedded Anwendungen sind derartige Gegenmaßnahmen gegen Seitenkanalangriffe unbedingt erforderlich.

Ein Beispiel dieser Seitenkanalangriffe ist die so genannte Fehleranalyse. Hierbei versucht ein Angreifer, durch gezielte Manipulation der Betriebsparameter einer Implementierung eines kryptographischen Verfahrens transiente oder permanente Fehler wahrend der kryptographischen Berechnung hervorzurufen. Der Angriff ist möglich, da die korrekte Funktion einer Komponente, wie beispielsweise einer Smart Card oder eines Embedded Systems, vom Hersteller nur innerhalb fest vorgegebener Umweltbedingungen garantiert werden kann. Es gibt folg- lieh eine große Bandbreite an technischen Möglichkeiten zur

Erzeugung solcher Fehler, als da waren Manipulation der Takterzeugung, Schwankungen der Versorgungsspannung, über- oder Untertemperatur, Lichtblitze oder gezielte Störung mittels

eines Lasers, partielle Zerstörung der elektrischen Schaltkreise, energetische Strahlung, usw. Die Unterschiede zwischen Ausgaben der Schaltung bei korrekter und fehlerhafter Arbeitsweise können einem Angreifer in Abhängigkeit vom ver- wendeten Fehlermodell der Implementierung Informationen über geheime Daten, wie beispielsweise über geheime Schlüssel, geben. Bei manchen Kryptoverfahren genügt ein einziges falsches Rechenergebnis, um zur sofortigen Preisgabe der geheimen Schlüssel zu führen. Daher müssen sicherheitsrelevante Imple- mentierungen geeignete Gegenmaßnahmen zum Schutz gegen Fehleranalyse haben.

Bisher bekannte Gegenmaßnahmen reichen von Sensoren, die die Umweltbedingungen überwachen und bei unzulässigen Betriebsbe- dingungen die Ausführung der kryptographischen Berechnungen verhindern bis hin zu algorithmischen Schutzmaßnahmen. Bei den algorithmischen Schutzmaßnahmen kann beispielsweise die kryptographische Berechnung zweimal ausgeführt und die beiden Ergebnisse miteinander verglichen werden. Dies hat jedoch den Nachteil eines verdoppelten Rechenaufwandes und damit einhergehend einer zumindest verdoppelten Rechenzeit. In einer weiteren bekannten Gegenmaßnahme zum Schutz gegen Fehleranalysen werden Invarianten in Zwischenergebnissen des kryptographischen Verfahrens eingeführt, welche während der kompletten Berechnung erhalten bleiben müssen. Bevor das Ergebnis der

Berechnung ausgegeben wird, überprüft das Gerät, ob die Invariante am Ende der Berechnung noch gültig ist. Falls ein Fehler auftrat, ist die Invariante mit großer Wahrscheinlichkeit nicht mehr erfüllt. Dieses Verfahren hat jedoch wiederum den Nachteil, dass mehrere zusätzliche Rechenschritte vorgenommen werden müssen und somit hohe Anforderungen an die erforderliche Rechenkapazität und den verfügbaren Speicherplatz gestellt werden.

In speziellen Umgebungen, auf denen kryptographische Verfahren implementiert werden sollen, wie beispielsweise Smart Cards oder RFID-Chips, sind jedoch spezielle Anforderungen hinsichtlich der verfügbaren Rechenkapazität und des vorhan-

denen Speicherplatzes zu berücksichtigen. In diesen Umgebungen haben die oben beschriebenen Verfahren zur Abwehr von Seitenkanalangriffen, insbesondere von Fehleranalysen, jedoch den Nachteil, dass sie in solchen Systemen aufgrund ihrer ho- hen Anforderungen an die Rechenkapazität und den verfügbaren Speicherplatz nicht eingesetzt werden können.

Somit liegt der Erfindung das Problem zugrunde, ein Verfahren, eine Vorrichtung sowie ein System zur Abwehr von Seiten- kanalangriffen, insbesondere von auf Fehleranalysen basierenden Seitenkanalangriffen, anzubieten, bei dem gegenüber den bisher bekannten Lösungen eine weitere Reduktion an Rechenzeitbedarf sowie eine Reduktion an benötigtem Speicherplatz erreicht wird.

Erfindungsgemäß wird diese Aufgabe durch ein Verfahren, eine Vorrichtung und ein System mit den Merkmalen der Ansprüche 1, 9 und 10 gelöst. Vorteilhafte Weiterbildungen der vorliegenden Erfindung sind in den abhängigen Ansprüchen angegeben.

Erfindungsgemäß wird in einem Verfahren zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten eine elliptische Kurve bereitgestellt. Zumindest eine Koordinate mindestens eines ersten Punktes, der auf der elliptischen Kurve liegt, wird ausgewählt oder ermittelt. Dieser erste Punkt wird gemäß einem vorgegebenen Verfahren mit einem Skalar multipliziert, wobei bei dem gesamten vorgegebenen Verfahren nur eine Koordinate des ersten Punktes verwendet wird. Als Ergebnis der Skalarmultiplikation werden weitere Punkte erhalten, welche zumindest eine Koordinate des jeweiligen Ergebnisses des mit dem Skalar multiplizierten ersten Punktes und des mit einem um einen Wert erhöhten Skalar multiplizierten ersten Punktes umfassen. Die ermittelten Punkte umfassen somit den ersten Punkt und die weiteren Punkte. Anschließend wird über- prüft, ob die ermittelten Punkte auf einer Geraden liegen können. Die ermittelten Punkte werden als verifiziert erkannt, sofern sie auf einer Geraden liegen können. Das Verfahren ist in vorteilhafter Weise geeignet, in Umgebungen mit

begrenzten Rechnerressourcen eingesetzt zu werden, da eine Ermittlung, ob die ermittelten Punkte auf einer Geraden liegen, mit geringem Rechenaufwand erfolgt.

Vorzugsweise wird ein Polynom zur überprüfung der ermittelten Punkte ausgewertet, wobei die Auswertung des Polynoms genau dann einen bestimmten Wert ergibt, wenn die zu überprüfenden Punkte auf einer Geraden liegen. Dies hat die vorteilhafte Wirkung, dass das Verfahren zur Verifizierung mit einer wei- ter reduzierten Anzahl von Multiplikationen und Additionen auskommt und somit der erforderliche Rechenaufwand weiter verringert wird.

Nach einer weiteren vorteilhaften Ausgestaltung der vorlie- genden Erfindung wird nach einer vorgebbaren Anzahl von voll- standig abgearbeiteten Bits des Skalars eine Verifizierung der ermittelten Punkte vorgenommen. Dies bringt den Vorteil mit sich, dass eine Verifizierung nach jedem Schritt des Algorithmus vorgenommen werden kann und somit die Sicherheit weiter erhöht wird oder eine Verifikation beispielsweise erst nach Ablauf des Algorithmus vorgenommen werden kann, um somit die Geschwindigkeit der Skalarmultiplikation zu erhohen.

Gemäß der erfindungsgemaßen Vorrichtung zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten weist die Vorrichtung Mittel auf, die derart eingerichtet sind, dass folgende Verfahrensschritte durchfuhrbar sind: Es wird eine elliptische Kurve bereitgestellt und zumindest eine Koordinate mindestens eines ersten Punktes auf der elliptischen Kurve ausgewählt oder ermittelt. Der erste Punkt wird gemäß einem vorgegebenen Verfahren mit einem Skalar multipliziert, wobei bei dem gesamten vorgegebenen Verfahren nur eine Koordinate des ersten Punktes verwendet wird.

Als Ergebnis der Skalarmultiplikation werden weitere Punkte erhalten, welche zumindest eine Koordinate des jeweiligen Ergebnisses des mit dem Skalar multiplizierten ersten Punktes und des mit einem um einen Wert erhöhten Skalar multiplizierten ersten Punktes umfassen. Somit umfassen die ermittelten

Punkte zumindest den ersten Punkt und die weiteren Punkte. Anschließend wird überprüft, ob die ermittelten Punkte auf einer Geraden liegen können, wobei die ermittelten Punkte dann als verifiziert erkannt werden, wenn sie auf einer Gera- den liegen können.

Gemäß dem erfindungsgemäßen System zum Verifizieren von auf einer elliptischen Kurve ermittelten Punkten mit einem ersten Rechner und einem zweiten Rechner sind der erste Rechner und der zweite Rechner miteinander verbindbar. Zunächst wird eine elliptische Kurve und zumindest eine Koordinate mindestens eines ersten Punktes, der auf der elliptischen Kurve liegt, zwischen dem ersten Rechner und dem zweiten Rechner vereinbart. Der erste Rechner weist eine Prozessoreinheit auf, die derart eingerichtet ist, dass folgende Verfahrensschritte durchführbar sind: Der erste Punkt wird gemäß einem vorgegebenen Verfahren mit einem Skalar multipliziert, wobei bei dem gesamten vorgegebenen Verfahren nur eine Koordinate des ersten Punktes verwendet wird. Als Ergebnis der Skalarmultipli- kation werden weitere Punkte erhalten, welche zumindest eine Koordinate des jeweiligen Ergebnisses des mit dem Skalar multiplizierten ersten Punktes und des mit einem um einen Wert erhöhten Skalar multiplizierten ersten Punktes umfassen. Die ermittelten Punkte umfassen somit zumindest den ersten Punkt und die weiteren Punkte. Anschließend wird überprüft, ob die ermittelten Punkte auf einer Geraden liegen können. Die ermittelten Punkte werden als verifiziert erkannt, falls sie auf einer Geraden liegen können. Die ermittelten und verifizierten Punkte werden von dem ersten Rechner an den zweiten Rechner übermittelt, wobei für auf der elliptischen Kurve sich befindende Punkte jeweils nur die eine Koordinate des jeweiligen Punktes übertragen wird. Der zweite Rechner weist eine Prozessoreinheit auf, die derart eingerichtet ist, dass folgende Verfahrensschritte durchführbar sind: Die von dem ersten Rechner übermittelten Punkte werden empfangen und die empfangenen, ermittelten Punkte werden zusätzlich bearbeitet, wobei bei der gesamten zusätzlichen Bearbeitung nur die eine

Koordinate des jeweiligen Punktes auf der elliptischen Kurve verwendet wird.

Die vorliegende Erfindung wird nachfolgend an Ausführungsbei- spielen anhand der Zeichnung näher erläutert. Es zeigt

Figur 1 eine schematische Darstellung einer elliptischen Kurve über den reellen Zahlen.

Eine elliptische Kurve E wird allgemein durch eine kubische Gleichung der folgenden Form beschrieben

y2 + a]_ * x * y +a3 * y = χ3 + a2 * x + &/± * x + ag,

wobei a]_, a2, SL-I ₁ , azμ ag fixe Elemente eines endlichen Kör ^¬ pers K sind, welche die elliptische Kurve E parametrisieren . In diesem Zusammenhang ist anzumerken, dass in Abhängigkeit von der Charakteristik des Körpers K die Kurvengleichung der elliptischen Kurve E auf einfachere Kurvengleichungen trans- formiert werden kann.

Wie weiter oben schon angedeutet, bildet die Skalarmultipli- kation von Kurvenpunkten der elliptischen Kurve mit ganzen Zahlen die Grundlage aller kryptographischen Verfahren auf Basis elliptischer Kurven. Sei S eine ganze Zahl, P ein Punkt der elliptischen Kurve E und Q = n * P das n-fache des Punktes P. Sind die Punkte P und Q gegeben, so bezeichnet man die Berechnung eines geeigneten Skalar n mit Q = n * P als das diskrete Logarithmusproblem für elliptische Kurven. Bei ge- eigneter Wahl des endlichen Körpers K und der Parameter der elliptischen Kurve E ist es mit derzeitigen algorithmischen Mitteln nicht in akzeptabler Zeit möglich, das diskrete Logarithmusproblem zu lösen.

Ein Punkt P einer elliptischen Kurve E ist durch seine x-

Koordinate und seine y-Koordinate gegeben. Aufgrund der Kurvengleichung der elliptischen Kurve E existieren zu einem x- Wert höchstens zwei unterschiedliche y-Werte y]_ und Y2, so

dass die Punkte (x,y]_) und (x,Y2) Punkte auf der elliptischen

Kurve E sind. Um somit einen Punkt auf der elliptischen Kurve E eindeutig festzulegen, ist außer der x-Koordinate nur noch ein Bit an zusätzlicher Information erforderlich.

In dem Fall einer elliptischen Kurve E über endlichen Primkörpern genügt beispielsweise das sog. Least Significant Bit (LSB) der y-Koordinate oder das Vorzeichen der y-Koordinate des jeweiligen Punktes als zusätzliche Information.

Diese Eigenschaften von elliptischen Kurven macht man sich in dem sog. Montgomery-Leiter-Algorithmus zunutze, welcher eine gängige Methode zur Implementierung der Skalarmultiplikation auf elliptischen Kurven darstellt. Der Montgomery-Leiter Al- gorithmus lässt sich dergestalt implementieren, dass zur Berechnung der x-Koordinate eines skalaren Vielfachen eines Punktes P nur die x-Koordinate von P verwendet wird. Da die Montgomery-Leiter gleichzeitig eine sehr gute Methode ist, einfachen Stromanalysen entgegenzuwirken, wird sie häufig in Kryptosystemen, die auf Embedded Systemen laufen, implementiert.

Gemäß dem im Weiteren beschriebenen Verfahren eines Montgomery-Leiter-Algorithmus wird ein Vielfaches n * P eines Punktes P, der sich auf einer elliptischen Kurve befindet, berechnet.

Der Skalar n = (nl, ..., nl) , gegeben in Binärdarstellung, wird bitweise, beginnend beim sogenannten Most Significant Bit (MSB, Nl) abgearbeitet.

Bezeichne im Folgenden UJ_ den Wert der Binärdarstellung (n _] _,

..., n-j_) für alle i von 1 bis 1. Als Zwischenergebnisse werden in der jeweiligen i-ten Runde (i-ten Iteration) die Punkte Qj_ = UJ_ * P und Rj_ = (UJ_+ 1) * P berechnet gemäß folgender Vorschrift, welche in einem Pseudocode dargestellt ist:

/* Initialisierung * /

for i <— 1 to £ do /* Hauptschleife * / if n- _j _ = 1 then

^■ —^ ^™ 7_ Q _1-1 + R _1-1 ;

^R i <- 2 ^• Ri _ i ; eise

R ₁ <- Ri_! + Q ₁ .!,-

fi od I return Qp;/* Ergebnis n • P * /

Gemäß dem oben dargelegten ersten Teil-Verfahren wird zunächst einem Initialisierungspunkt Qo der Wert O zugeordnet, was einer Initialisierung dieser Variablen entspricht.

Einer zusätzlichen Variablen R wird in einem zusätzlichen I- nitialisierungsschritt als Initialisierungsvariable Ro der Wert des Punktes P zugeordnet.

In einem zusätzlichen Schritt wird in der eigentlichen Berechnungsschleife in jeder Iteration für den jeweils berücksichtigten Skalarwert nj_ für den Fall, dass der Skalarwert nj_ den Wert 1 aufweist, dem Wert einer ersten Zwischenvariablen Q zu der Iteration i (bezeichnet als Qi) die Summe des Wertes der ersten Zwischenvariable Qi-i zu der vorangegangen Iteration i-1 und dem Wert der zweiten Zwischenvariable Ri-I zu der vorangegangen Iteration i-1 zugeordnet. Dem Wert der zweiten Zwischenvariable Ri in der Iteration i wird der zweifache Wert der zweiten Zwischenvariablen zu der vorangegangen Iteration i-1 zugeordnet.

Ist der Wert des Skalar ni nicht gleich 1, so wird der zweiten Zwischenvariablen Ri in der Iteration i die Summe der Werte der Summe der ersten Zwischenvariablen Ri-i in der vo- rangegangen Iteration i-1 und dem Wert der ersten Zwischenvariablen Qi-i in der vorangegangen Iteration i-1 zugeordnet.

Der ersten Zwischenvariablen Qi zu der Iteration i wird der zweifache, das heißt der verdoppelte Wert der ersten Zwischenvariablen Qi-i zu der vorangegangenen Iteration i-1 zu- geordnet.

Gemäß dem oben beschriebenen Pseudocode wird der sich ergebende Wert der Zwischenvariablen Q _] _ in der letzten Iteration

1 als Ergebniswert dieser Operation ausgegeben, wenn alle Skalarwerte nj_ des Skalars n abgearbeitet sind. Wahlweise können die Zwischenvariablen R _j _ und Q _j _ nach jeder Iteration oder nach einer vorgebbaren Anzahl von Iterationsschritten als Zwischenergebniswert ausgegeben werden. Bei fehlerfreier Berechung der Ergebnisse in dem Montgomery-Leiter-Algorithmus liegen nach jedem Iterationsschritt die Zwischenvariablen in der Form

Ri=(ui+1)-P und Qi=Ui-P

vor, welche sich in der Differenz nur um den Punkt P unterscheiden .

Demnach berechnet die Montgomery-Leiter gleichzeitig die x- Koordinaten der Punkte n * P sowie (n+1) * P. Da die y- Koordinate der Differenz der beiden Ergebnisse bekannt ist, kann am Ende der Schleife aus den berechneten x-Koordinaten der vollständige Punkt n * P rekonstruiert werden.

Ausgehend hiervon ist eine einfache Methode zur Absicherung einer Skalarmultiplikation auf elliptischen Kurven, am Ende der Berechnung zu testen, ob das Ergebnis noch einen Punkt auf der elliptischen Kurve darstellt. Dazu muss lediglich überprüft werden, ob die Koordinaten des Ergebnispunktes die Gleichung der elliptischen Kurve erfüllen.

In speziellen Umgebungen, auf denen kryptographische Verfahren implementiert werden sollen, wie beispielsweise Smart

Cards oder RFID-Chips, sind jedoch spezielle Anforderungen hinsichtlich der verfügbaren Rechenkapazität und des vorhandenen Speicherplatzes zu berücksichtigen. In diesen Umgebungen hat das oben beschriebene Verfahren zur Verifizierung der ermittelten Punkte auf der elliptischen Kurve jedoch den

Nachteil, dass eine vollständige Rekonstruktion des Ergebnispunktes und ein anschließendes Einsetzen in die elliptische Kurvengleichung erhebliche Anforderungen an die vorhandene Rechnerstruktur stellt und somit einen wesentlich erhöhten Rechenzeitbedarf zur Folge hat.

Ein weiteres Verfahren zum Verifizieren von ermittelten Punkten auf einer elliptischen Kurvengleichung ausgehend von dem Montgomery-Leiter-Algorithmus wäre, auf die y-Koordinaten zu verzichten, so dass man in diesem Fall gezwungen ist, nach

Einsetzen der x-Koordinate die Lösbarkeit einer quadratischen Gleichung in y zu überprüfen. Auch dieses Verfahren hat den wesentlichen Nachteil, dass es in Systemen mit begrenzten Rechenressourcen nicht umsetzbar ist.

Im Folgenden wird das erfindungsgemäße Verfahren zur Verifizierung von auf einer elliptischen Kurve ermittelten Punkten in einem Ausführungsbeispiel näher beschrieben.

Nach dem Additionsgesetz der elliptischen Kurve folgt, dass bei fehlerfreier Berechnung der Ergebnisse die Punkte u-j_-P, -

-(u- _j _+l)-P und P auf einer Geraden liegen.

Dies ist exemplarisch in der Figur 1 zu sehen. Die Figur 1 zeigt eine elliptische Kurve 1, in der die Punkte 2 P]_ = P, 3

P2 = n * P und 4 P1+P2 = (n+1) * P gekennzeichnet sind. Für diese Punkte gilt:

^P l ^+P 2 = P + n*P = (n+1) * P.

Wie aus dem Additionsgesetz der elliptischen Kurve folgt und aus der Figur 1 ersichtlich wird, liegen die Punkte P]_, P2 und - (ε'i+ε'2) auf einer Geraden 5. Dieses Phänomen wird in dem

erfindungsgemäßen Verfahren zu Verifizierung von auf einer elliptischen Kurve ermittelten Punkten genutzt. Dazu wird ein quadratisches Polynom. Ist dieses quadratische Polynom nun für die ermittelten Koordinaten der Punkte des Montgomery- Leiter-Algorithmus P ₁ +P ₂ =Ri= (UJ_+ 1) -P ,P ₂ =Qi=U-L-P und P ₁ =P erfüllt, werden die ermittelten Punkte als verifiziert erkannt.

Bei einem Angriff durch fehlerhafte Ergebnisse der Skalarmul- tiplikation versucht ein Angreifer gezielt, einen Fehler in- nerhalb der Montgomery-Leiter zu induzieren. Bei einer Smart Card oder einem RFID-Chip erfolgt dies zum Beispiel durch Temperatur- oder Spannungsschwankungen, durch Aussetzen einer Strahlung usw. Wird der Fehler erst innerhalb der Berechnung der Montgomery-Leiter induziert, sind vor allen Dingen zwei Fälle zu unterscheiden:

Im ersten Fall verursacht der induzierte Fehler, dass das Ergebnis nach einem Durchlauf der Schleife innerhalb der Montgomery-Leiter kein gültiger Punkt der Kurve ist. Dies bedeu- tet, dass mindestens eines der beiden Ergebnisse Rj_ und Qj_ keine x-Koordinate eines Punktes auf der elliptischen Kurve besitzen. In diesem Fall wird der Test mit dem quadratischen Polynom diesen Fehler offen legen.

Im zweiten Fall wird zwar ein Fehler erfolgreich induziert, die Ergebnisse bleiben jedoch weiterhin gültige x-Koordinaten von Punkten auf der elliptischen Kurve. In diesem Ausführungsbeispiel nehmen wir an, dass vor dem Fehler die Eingabe u-j_-P und (u-j_+l)-P ist. Nach dem nächsten Schleifendurchlauf erhält man unter der Annahme, dass der Fehler in die ersten Komponenten induziert wird, n'-P und (2u-j_ _{+ 1} +2) -P beziehungsweise n'-P und (2u-j_ _{+ 1} +l) -P, je nach Wert des abgearbeiteten

Bits. Es folgt, dass diese beiden Ergebnisse sich nicht mehr um P unterscheiden und daher die Punkte P, n'-P und - (2u-j__|_]_+2 ) -P beziehungsweise - (2UJ__|_ _] _ + 1) -P nicht mehr auf einer

Geraden liegen können. Daher wird auch in diesem Fall das quadratische Polynom diesen Fehler aufdecken.

Dieses Verfahren zur effizienten Verifikation der Integrität eines Berechnungsergebnisses bildet einen wichtigen Baustein zur Formulierung von fehlerresistenten asymmetrischen Low- Cost- Kryptographieprotokollen, welche beispielsweise in Smart Cards, RFID-Chips oder embedded Systemen eingesetzt werden. Nach dem üblicherweise in diesen Protokollen auf y- Koordinaten verzichtet wird, ist ein Test einer x-Koordinate, ob sie eine Komponente eines gültigen Punktes ist, nur mit der Lösung einer quadratischen Gleichung möglich. Dieser Test umfasst einige rechenaufwändige Operationen, so dass er für ein Low-Cost-Protokoll nicht in Frage kommt. Die Auswertung des quadratischen Polynoms kann wie im Folgenden gezeigt mit geringem Rechenaufwand erfolgen, so dass dieses Verfahren besonders geeignet ist, um Anwendung in einer Low-Cost- Anwen- düng zu finden.

Im Folgenden werden beispielhaft quadratische Polynome angegeben, die zur einfachen Verifizierung des Ergebnisses einer Skalarmultiplikation mittels der Montgomery-Leiter verwendet werden können. Dabei wird die Charakteristik des Körpers unterschieden, über den die elliptische Kurve definiert ist.

Bei einer Charakteristik des Körpers K=2 ist die elliptische Kurve durch die Gleichung

y2 + xy = χ3 + a2X + ag

gegeben. Die Werte X]_, X2, X3 können genau dann x-Koordinaten von Punkten sein, die auf einer Geraden liegen, wenn das Po- lynom

p(x]_, X2, X3) = X3 ^■ (x]_+X2) + Xl X2 ^X 3 ^{+ x} l ^X 2 ^+a 6

den Wert 0 annimmt. In projektiver Koordinatendarstellung gilt der unendlich ferne

Punkt besitzt die Darstellung X ≠ 0 und Z = O. Somit ergibt sich in der projektiven Darstellung das folgende Polynom zur Verifikation :

P(X ₁ , X ₂ , X ₃ , Z ₁ , Z ₂ , Z ₃ )= X ₃ ² (X ₁ Z ₂ +X ₂ Z ₁ ) ² + X ₁ X ₂ X ₃ Z ₁ Z ₂ Z ₃ +

X ₁ 2χ ₂ 2 _Z3 2 + _S6 Z ₁ ² Z ₂ ² Z ₃ ²

Hat der Körper K die Charakteristik 3 ist die elliptische Kurve durch die Gleichung

y2 _{= X} 3 +a ₂ x ² +a5

gegeben. Die Werte xl, x2, x3 können genau dann x-Koordinaten von Punkten sein, die auf einer Geraden liegen, wenn das Polynom

P(X ₁ , x ₂ , x ₃ ) = x ₃ ² ( _Xl -χ ₂ )2 + _X3 (X ₁ X ₂ (x ₁ +x ₂ -a ₂ ) -ag) + x ₁ ² χ ₂ 2 - ag (x]_+x ₂ +a ₂ )

den Wert 0 annimmt.

In der projektiven Koordinatendarstellung ergibt sich das folgende Polynom zur Verifikation:

P(X ₁ , X ₂ , X ₃ , Z ₁ , Z ₂ , Z ₃ ) = X ₃ ² (X ₁ Z ₂ -X ₂ Z ₁ ) ² + X ₃ Z ₃ (X ₁ X ₂ (X ₁ Z ₂ +X ₂ Z ₁ - a ₂ Z ₁ Z ₂ )-a ₆ Z ₁ ² Z ₂ ² ) + Z ₃ ² (X ₁ ² X ₂ ² - ^a 6 ^z l ^z 2 ^(χ l ^z 2 ^+x 2 ^z l+ ^a 2 ^z l ^z 2 ^{) )}

Bei einer Charakteristik des Körpers K > 3 ist die elliptische Kurve durch die Gleichung

y2 _{= χ} 3 _|_ _a ^ _χ _|_ _g g

gegeben. Die Werte X ₁ , x ₂ , x ₃ können genau dann x-Koordinaten von Punkten sein, die auf einer Geraden liegen, wenn das Polynom

P(X ₁ , x ₂ , x ₃ ) = X ₃ ² U ₁ -X ₂ ) ² - 2x ₃ (2ag+ (34+X ₁ X ₂ ) (x ₁ +x ₂ ) ) +

(x ₁ x ₂ -a4) ² - 4ag(x ₁ +x ₂ )

den Wert 0 annimmt.

In projektiver Koordinatendarstellung ergibt sich folgendes Polynom zur Verifikation:

P(X ₁ , X ₂ , X ₃ , Z ₁ , Z ₂ , Z ₃ ) =

X ₃ ² (X ₁ Z ₂ -X ₂ Z ₁ ) ² - 2X ₃ Z ₃ ^a ₆ Z ₁ ² Z ₂ ² + (a ₄ Z ₁ Z ₂ +X ₁ X ₂ ) (X ₁ Z ₂ +X ₂ Z ₁ ) ) + Z ₃ ² (X ₁ X^a ₄ Z ₁ Z ₂ ) ² - 4B ₆ Z ₁ Z ₂ Z ₃ ² (X ₁ Z ₂ +X ₂ Z ₁ )

Für alternative projektive Darstellungen, beispielsweise jacobische Koordinaten, müssen die Darstellungen entsprechend angepasst werden. Es zeigt sich jedoch schon hier, dass gemäß der vorliegenden Erfindung die Verifizierung von auf einer elliptischen Kurve ermittelten Punkten über eine Anzahl von Multiplikationen und Additionen vorgenommen werden kann und somit im Vergleich zu bisher bekannten Lösungen eine erhebliche Rechenaufwandsreduktion zu verzeichnen ist.

Die vorliegende Erfindung ist nicht auf die hier beschriebenen Ausführungsbeispiele beschränkt.