DE10156708B4

DE10156708B4 - Verfahren und Vorrichtung zum Multiplizieren und Verfahren und Vorrichtung zum Addieren auf einer elliptischen Kurve

Info

Publication number: DE10156708B4
Application number: DE2001156708
Authority: DE
Inventors: Wieland Dr./Dipl.-Math. Fischer; Jean Pierre Dr./Dipl.-Inf. Seifert
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2001-11-19
Filing date: 2001-11-19
Publication date: 2005-09-29
Anticipated expiration: 2021-11-20
Also published as: AU2002342820A1; WO2003044653A2; TW580654B; DE10156708A1

Abstract

Verfahren zum Addieren zweier Punkte auf einer elliptischen Kurve y² = x³ + a·x + b innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei ein erster Punkt der zwei Punkte eine erste projektive Koordinate X_P und eine dritte projektive Koordinate Z_P aufweist, wobei der zweite Punkt eine erste projektive Koordinate X_Q und eine dritte projektive Koordinate Z_Q aufweist, mit folgenden Schritten:
Berechnen (31) einer ersten projektiven Koordinate X_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: XP' = 2(XPZQ + XQZP)(XPXQ + aZPZQ) + 4bZP 2ZQ 2 + xD(XPZQ – XQZP)2; undBerechnen (30) einer dritten projektiven Koordinate Z_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: ZP' = (XPZQ – XQZP)2,wobei a und b Parameter der elliptischen Kurve sind, und wobei x_D eine affine...

Description

Die vorliegende Erfindung bezieht sich auf kryptographische Algorithmen und insbesondere auf die Elliptische-Kurven-Kryptographie.
Im Gegensatz zur klassischen Kryptographie, wie z. B. dem RSA-Verfahren, bei dem die modulare Exponentiation eine zentrale Rechenoperation ist, ist bei der Elliptische-Kurven-Kryptographie die Multiplikation eines Punktes P auf der elliptischen Kurve mit einem ganzzahligen Faktor die entsprechende wesentliche Operation.
Beispielsweise kann der klassische DSA (DSA = Digital Signature Algorithm), wie er im „Handbook of Applied Cryptography", Menezes u. a., CRC Press, beschrieben ist, zum EC-DSA (EC-DSA = Elliptic Curve Digital Signature Algorithm) modifiziert werden, wie er im IEEE P 13.63 beschrieben ist.
Ein weiterer kryptographischer Algorithmus, der auch auf elliptische Kurven ausgedehnt werden kann, ist das sogenannte Diffie-Hellman-Key-Exchange-Verfahren, wie es im Handbook of Applied Cryptography beschrieben ist.
Wollen zwei Parteien A, B einen gemeinsamen geheimen Schlüssel über einen unsicheren Kanal austauschen, so können sie dabei wie folgt vorgehen.
Zunächst wählen beide Parteien eine elliptische Kurve sowie einen generierenden Punkt P dieser Kurve.
Partei A wählt nun einen konstanten Faktor d_A und berechnet das Produkt Q_A = d_A P und sendet diesen Punkt Q_A über den unsicheren Kanal zu B.
Analog dazu wählt nun die Partei B einen konstanten Faktor d_B und berechnet das Produkt Q_B = d_B P und sendet diesen Punkt Q_B über den unsicheren Kanal zu A.
Hiernach besitzen beide Parteien einen geheimen Schlüssel, nämlich das Produkt d_A d_B P. Diesen geheimen Schlüssel können die beiden Parteien nunmehr grundsätzlich für ein symmetrisches Block-Verschlüsselungs-Verfahren verwenden.
Es ist nicht möglich, die konstanten Faktoren d_A und d_B aus der Kenntnis von Q_A, Q_B, P und der elliptischen Kurve effizienter als durch bloßes Ausprobieren zu berechnen. Dies bedeutet in anderen Worten, daß die konstanten Faktoren d_A, d_B vor Angriffen bei der Partei A bzw. der Partei B zu schützen sind.
Im nachfolgenden wird auf 6 Bezug genommen, um den bekannten Double-&-Add-Algorithmus darzustellen, der auch für die Berechnung der Multiplikation eines Punkts auf der elliptischen Kurve mit einem konstanten Faktor eingesetzt werden kann. Im Gegensatz zur üblichen Arithmetik, unterscheiden sich bei der Elliptische-Kurven-Arithmetik die Formeln zum Addieren zweier Punkte auf der elliptischen Kurve bzw. die Formeln zum Multiplizieren eines Punkts auf der elliptischen Kurve mit dem Faktor 2. Diese Additionsformeln bzw. Multiplikationsformeln hängen von der jeweils gewählten elliptischen Kurve ab.
Der Double-&-Add-Algorithmus berechnet allgemein als Ergebnis E die Multiplikation einer Ganzzahl d mit einem Punkt B auf der elliptischen Kurve, wie es in einem Block 100 in 6 dargestellt ist. Als Eingabe benötigt der Algorithmus die Länge n des Multiplikators d, eine Inkrementierungsgröße i sowie ein Register E, das zu Anfang des Algorithmus auf den Wert 0 initialisiert wird, wie es in einem Block 102 dargestellt ist. Zunächst wird untersucht, ob das betrachtete Bit i des Multiplikators 0 oder 1 ist (Block 104). Wird festgestellt, daß das gerade betrachtete Bit eine 1 ist, wird der rechte Zweig von 6 genommen. Wird dagegen festgestellt, daß das betrachtete Bit eine 0 ist, so wird der linke Zweig genommen. Der Double-&-Add-Algorithmus bedingt für den Fall, daß das gerade betrachtete Bit des Multiplikators 1 ist, daß der aktuelle Inhalt des Registers E verdoppelt wird (Block 106), und daß dann zu dem Wert E der Punkt B der elliptischen Kurve hinzuaddiert wird, um den neuen Wert E des Registers für das Ergebnis E zu erhalten (Block 108). Wird dagegen festgestellt, daß das aktuelle gerade betrachtete Bit d_i gleich 0 ist, so wird nur ein Verdopplungsschritt (Block 110) durchgeführt, und es findet kein Additionsschritt statt.
Nach der Beendigung der Schleife bzw. nach dem Berechnen von E wird die Laufvariable i um 1 inkrementiert (Block 112). Dann wird überprüft, ob i kleiner als n ist (Block 114). Ist i kleiner als n, so wird die Schleife (Blöcke 104, 106, 108, 110) erneut durchlaufen. Wird dagegen festgestellt, daß sämtliche Bits des ganzzahligen Multiplikators d abgearbeitet sind, so wird der aktuelle Wert des Registers E als das Ergebnis der Multiplikation des ganzzahligen Faktors d mit dem Punkt B auf der elliptischen Kurve ausgegeben (Block 116). Wie es bekannt ist, wird zunächst das höchstwertige Bit des Multiplikators d betrachtet, woraufhin im nächsten Durchlauf das zweithöchste Bit betrachtet wird etc. Die Bits des ganzzahligen Multiplikators werden daher von höchstwertigen Bits ausgehend zu niederwertigen Bits verarbeitet, bis das niederstwertige Bit erreicht wird, was in dem Block 114 festgestellt wird. Nach der Verarbeitung des niederstwertigen Bits kann das Ergebnis durch den Block 116 ausgegeben werden.
Nachteilig an dem in 6 beschriebenen Double-&-Add-Algorithmus ist die Tatsache, daß die Berechnung in den beiden Zweigen hinsichtlich der Anzahl der Schritte unterschiedlich ist, je nach dem, ob das gerade aktuell betrachtete Bit d_i gleich 1 ist oder gleich 0 ist. Daher ist es für bestimmte Angriffe auf den kryptographischen Algorithmus möglich, anhand des Leistungsverbrauchs bzw. der Zeitdauer, die für die Berechnung einer Iteration benötigt wird, festzustellen, ob das gerade betrachtete Bit eine 1 oder eine 0 war. Wie es ausgeführt worden ist, ist der Skalar, der mit einem Punkt auf der elliptischen Kurve multipliziert wird, typischerweise die geheime Information bzw. der geheime Schlüssel einer Partei, der vor Angriffen zu schützen ist.
Als Gegenmaßnahme gegen eine solche Attacke auf den kryptographischen Algorithmus könnte in dem Double-&-Add-Algorithmus im linken Zweig von 6 eine Dummy-Addition 118 eingefügt werden, deren Ergebnis nicht verwendet wird. Diese Dummy-Addition 118 stellt sicher, daß der Zeitaufwand und der Leistungsverbrauch des Kryptochips für beide Fälle, d. h. für d_i = 1 und d_i = 0, gleich sind, so daß Timing-Attacken oder einfache Power-Analysis-Attacken fehlschlagen werden.
Rechenregeln zum Berechnen der Summe zweier Punkte auf einer elliptischen Kurve oder zum Berechnen der Multiplikation eines Punkts auf einer elliptischen Kurve mit dem Faktor 2 bzw. zum Multiplizieren eines Punkts auf der elliptischen Kurve mit einem konstanten Faktor sind für allgemeine elliptische Kurven der Form y² = x³ + a·x + b in Carl Pomerance, „Prime Numbers", Springer-Verlag, 2001, Kapitel 7.2, beschrieben. Ferner wird in diesem Fachbuch ein Überblick über die verschiedenen Koordinaten gegeben. Hierbei werden affine Koordinaten, projektive Koordinaten, modifizierte projektive Koordinaten sowie X-, Z-Koordinaten, die auch als Montgomery-Koordinaten bezeichnet werden, beschrieben. Projektive Koordinaten [X, Y, Z] können in affine Koordinaten (x, y) folgendermaßen umgerechnet werden: x = X/Z und y = Y/Z.
Ferner wird in demselben Fachbuch die sogenannte Lucas-Kette erläutert, die darin besteht, das Produkt k mal P mittels einer Additionskette zu berechnen, wobei immer dann, wenn zwei ungleiche Punkte P₁, P₂ miteinander addiert werden, die Differenz P₁ – P₂ bekannt ist. An Zwischenschritten liegt daher ein Paar [m] P, [m + 1] P vor. Aus diesem Paar wird entweder das Paar [2m] P, [2m + 1] P oder das Paar [2m + 1] P, [2m + 2] P gebildet, und zwar abhängig von den Bits des Skalars k. In jedem Fall wird eine Verdopplung und eine Addition durchgeführt. Für die Addition selbst ist bereits die Differenz der zwei addierten Punkte bekannt, nämlich P selbst.
Die Lucas-Kette ermöglicht es, daß die x-Koordinate eines Ergebnispunkts auf der elliptischen Kurve unabhängig von der y-Koordinate dieses Punkts berechnet werden kann. So existieren beispielsweise Kryptographieverfahren, bei denen die y-Koordinate gar nicht benötigt wird, wie z. B. das EC-DSA-Verfahren, während wieder andere Kryptographieverfahren vorhanden sind, bei denen die y-Koordinate benötigt wird, wie z. B. das Diffie-Hellman-Verfahren.
Nachteilig an dem klassischen Double-And-Add-Algorithmus ist jedoch, daß keine Parallelisierung möglich ist. So kann der Schritt 108 erst dann ausgeführt werden, wenn der Schritt 106 gerechnet ist. Der Double-&-Add-Algorithmus kann daher in seiner in 6 gezeigten Form nicht parallelisiert werden. Darüber hinaus werden durch den Dummy-Schritt 118 Rechenressourcen lediglich aus Sicherheitsgründen „verschwendet", ohne daß das Ergebnis, für dessen Erlangen die Rechenressourcen aufgewendet worden sind, verwendet werden würde.
Insbesondere bei Kryptographiealgorithmen auf Chipkarten, bei denen enge Rechenressourcen- und Speicherkapazitätsbeschränkungen bestehen, ist jedoch neben der Sicherheit des Algorithmus auch die Effizienz des Algorithmus von wesentlicher Bedeutung. So ist die Fläche eines Chips auf einer Chipkarte durch „äußere" Spezifikationen auf eine bestimmte Chipfläche begrenzt. Dem Entwickler steht es dann frei, diese zur Verfügung gestellte Gesamt-Chipfläche für seine Anwendungen als Speicher oder als Rechenwerk zu verwenden. Andererseits wird eine Akzeptanz von Chipkarten nur dann vorhanden sein, wenn digitale Unterschriften natürlich sicher aber auch schnell erzeugt werden, da ein Kunde nicht mehrere Minuten auf eine Authentifikation beispielsweise an einem Bankautomaten warten möchte.

Die WO 00/25204 A1 offenbar ein kryptographisches Konzept, das gegen Leistungssignaturattacken resistent ist. Ein Mehrfaches eines Punktes auf einer elliptischen Kurve, die über einem Feld definiert ist, wird berechnet. Hierzu wird die Zahl, die das Mehrfache des Punktes bestimmt, als Binärvektor dargestellt, wobei ein geordnetes Paar von Punkten gebildet wird, wobei sich die Punkte voneinander unterscheiden, und wobei die Bits des Vektors in Sequenz gewählt werden. Ein neuer Satz von Punkten wird berechnet, indem ein erster Punkt verdoppelt wird und dann der verdoppelte Punkt mit dem zweiten Punkt addiert wird. Die Verdopplungen und Addierungen werden immer in der gleichen Reihenfolge für jedes Bit durchgeführt, wodurch Timing-Attacken abgewehrt werden.

Die WO 99/49386 A1 bezieht sich auf beschleunigte Operationen auf einer elliptischen Kurve. Zur Multiplikation eines Punktes auf einer elliptischen Kurve mit einem Wert k wird der Wert k als Vektor binärer Zahlen dargestellt. Ferner wird eine Sequenz von Punktpaaren gebildet. Die Berechnungen werden ohne Verwendung der y-Koordinate der Punkte durchgeführt. Die y-Koordinate wird dann am Ende der Berechnungen extrahiert, wodurch keine Invertierungs-Operationen nötig sind.

Das US-Patent Nr. 6,263,081 B1 offenbart eine schnelle Berechnung von Mehrfachen auf einer elliptischen Kurve. Eine Multiplikationsberechnungseinheit erzeugt Vorberechnungs-Tabellen für Mehrfache von Zahlen an Ein-Wort-Intervallen und für Mehrfache von Zahlen an Halb-Wort-Intervallen. Mehrfache von Punkten auf einer elliptischen Kurve werden unter Verwendung eines Verdopplungsprozesses berechnet, jedoch mit einer reduzierten Anzahl von Additionen.

Die Fachveröffentlichung „A Small and Fast Software Implementation of Elliptic Curve Cryptosystems over GF (p) on a 16-Bit Microcomputer", T. Hasegawa u.a., IEICE Trans. Fundamentals, Vol. I82-A, Nr. 1, Januar 1999, Seiten 98–106, offenbart einen neuen Typ einer Prim-Charakteristik eines Basisfeldes, die für kleine und schnelle Implementierungen geeignet ist. Diese Prim-Charakteristik wird verwendet, um eine Galois-Feld-Multiplikation mit einem kleineren Code durchzuführen.

Die Aufgabe der vorliegenden Erfindung besteht darin, ein Konzept zum Multiplizieren einer Zahl mit einem Punkt auf einer elliptischen Kurve im Rahmen einer kryptographischen Berechnung zu schaffen, das einerseits effizient und andererseits sicher ist.

Diese Aufgabe wird durch ein Verfahren zum Addieren zweier Punkte gemäß Patentanspruch 1, ein Verfahren zum Multiplizieren gemäß Patentanspruch 2, eine Vorrichtung zum Addieren gemäß Patentanspruch 3, eine Vorrichtung zum Addieren gemäß Patentanspruch 5, eine Vorrichtung zum Multiplizieren gemäß Patentanspruch 6 oder ein Verfahren zum Addieren gemäß Patentanspruch 7 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß von dem Double-&-Add-Algorithmus weggegangen werden muß, und daß statt dessen die Multiplikation eines Skalars mit einem Punkt auf der elliptischen Kurve unter Verwendung zweier Hilfsgrößen berechnet werden muß, wobei eine Hilfsgröße immer gleich dem Doppelten des vorherigen Werts der Hilfsgröße ist, während die andere Hilfsgröße immer gleich der Summe der beiden vorherigen Hilfsgrößen ist. Je nach dem, ob das gerade betrachtete Bit des Skalars, d. h. des Multiplikators, eine 1 oder eine 0 ist, wird das Doppelte der einen Hilfsgröße berechnet, oder wird das Doppelte der anderen Hilfsgröße berechnet. Dies bedeutet, daß für beide Fälle, also für den Fall daß das Bits des Skalars gleich 0 oder daß das Bit des Skalars gleich 1 ist, immer eine Addition und eine Multiplikation mit 2 durchgeführt wird. Damit sind Timing-Attacken oder Power-Analysis-Attacken von vornherein nicht wirkungsvoll. Darüber hinaus können die beiden Hilfsgrößen unabhängig voneinander, also parallel berechnet werden, was zu einem Performancegewinn führt. Hierzu sind zwar zwei parallele Rechenwerke vonnöten. Wenn diese zwei parallelen Rechenwerke jedoch ohnehin im Kryptoprozessor beispielsweise auf der Smart Card aus anderen Gründen vorhanden sind, spielt dies keine Rolle. Zurück bleibt die Verdopplung des Durchsatzes gegenüber dem einfachen Double-&-Add-Algorithmus bei erhöhter Sicherheit.

Das erfindungsgemäße Verfahren zum Multiplizieren einer Zahl mit einem Punkt bezieht sich auf eine elliptischen Kurve y² = x³ + a·x + b, wobei x eine erste Koordinate der elliptischen Kurve ist, wobei y eine zweite Koordinate der elliptischen Kurve ist, und wobei die elliptischen Kurve über einem Körper mit einer Charakteristik p größer als 3 definiert ist. In diesem Zusammenhang bedeutet dies, daß sämtliche Koordinaten auf der elliptischen Kurve einer Modulo-Operation mit der Charakteristik p unterzogen werden. Es sei darauf hingewiesen, daß das erfindungsgemäße Verfahren nicht für elliptischen Kurven mit Charakteristika von 3 oder kleiner als 3 anwendbar ist.

Ein Vorteil der vorliegenden Erfindung besteht darin, daß keine Timing-Attacken oder Leistungs-Attacken zielführend sind, da der Verarbeitungsaufwand für ein Bit des Multiplikators unabhängig davon ist, ob das Bit eine 0 oder eine 1 hat.

Ein weiterer Vorteil der vorliegenden Erfindung besteht darin, daß der erste und der zweite Hilfspunkt auf der elliptischen Kurve in jedem Iterationsschritt parallel berechnet werden können, so daß ein Geschwindigkeitsgewinn mit einem Faktor in der Größenordnung von 1,9 (theoretisch 2) gegenüber dem Double-&-Add-Algorithmus mit Dummy-Addition erreichbar ist.

Darüber hinaus ist die Erfindung dahingehend vorteilhaft, daß explizite Additions-Formeln zum Berechnen des ersten und des zweiten Hilfspunkts angegeben werden können, die in sich selbst wiederum parallelisiert werden können, was insgesamt zu einem Leistungsgewinn mit einem Faktor in der Größenordnung von 2,6 resultiert.

Darüber hinaus ist die Erfindung dahingehend vorteilhaft, daß ihre Anwendbarkeit für beliebige elliptische Kurven anwendbar ist, solange die Charakteristik des zugrundeliegenden Körpers der elliptischen Kurve größer als 3 ist.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeichnungen detailliert erläutert. Es zeigen:

1 ein Blockdiagramm des erfindungsgemäßen Verfahrens zum Multiplizieren einer Zahl mit einem Punkt auf einer elliptischen Kurve;

2 ein schematisches Blockschaltbild eines Addierers zum Addieren zweier Punkte auf der elliptischen Kurve, um den ersten Hilfspunkt zu erhalten;

3 ein Prinzipblockschaltbild eines Multiplizierers zum Multiplizieren eines Punkts auf der elliptischen Kurve mit dem Faktor 2, um den zweiten Hilfspunkt zu erhalten;

4 ein Blockschaltbild eines Rechenwerks zum Addieren und Multiplizieren mit einem Faktor 2 und parallelisierter Funktionalität;

5 ein Übersichtsdiagramm der Funktionalität der Ablaufsteuerung von 4; und

6 ein Übersichtsdiagramm des Double-&-Add-Algorithmus ohne und mit Dummy-Addition.

1 zeigt ein Übersichtsdiagramm über den erfindungsgemäßen Algorithmus zum Multiplizieren einer Zahl d mit einem Punkt B auf einer elliptischen Kurve der folgenden Form: y2 = x3 + a·x + b,wobei a und b für Konstanten stehen. Die elliptische Kurve ist für Charakteristika p größer als 3 definiert (Block 10). Darüber hinaus werden zwei unterschiedliche Punkte P und Q betrachtet, die beide ungleich 0 sind. Die affinen Koordinaten für den Punkt P lauten (x_P, y_P). Die projektiven Koordinaten des Punkts P lauten (X_P : Y_P : Z_P), wobei der Punkt P aus A² = P² – P¹ ist. Für diese Koordinaten gibt es u. a. die Beziehungen X_P = x_P·Z_P und Y_P = y_P·Z_P.
In einem Initialisierungsblock 12 wird zunächst die Länge in Bit n des Multiplikators d (d₀, d₁, d₂, ..., d_n) festgelegt, wobei d₀ das höchstwertige Bit des Multiplikators ist. Ferner wird eine Laufvariable i auf 0 initialisiert. Darüber hinaus wird der erste Hilfspunkt P auf den Nullpunkt der elliptischen Kurve initialisiert, und wird der zweite Hilfspunkt Q auf B initialisiert. Hierauf wird in die Iteration von 1 eingetreten.
Alternativ kann der erste Iterationsschritt des obigen Verfahrens bereits in die Initialisierung aufgenommen werden, da Bits oberhalb des höchstwertigen Bits im Multiplikatorregister gleich Null sind und das höchstwertige Bit des Multiplikators immer gleich Eins ist. In diesem Fall wird P auf B initialisiert, und wird Q auf 2B initialisiert.
In einem Block 14 wird zunächst überprüft, ob das aktuell betrachtete Bit des Multiplikators d gleich 0 ist oder nicht. Wird diese Frage mit Ja beantwortet, so wird in die rechte Schleife von 1 eingetreten. Wird diese Frage dagegen mit Nein beantwortet, so wird in die linke Schleife von 1 eingetreten.
Ist das Bit d_i des Multiplikators gleich 0, so wird der neue Wert P_neu des ersten Hilfspunkts berechnet, indem die beiden aktuellen Hilfspunkte P und Q addiert werden (Block 16). Der zweite Hilfspunkt Q_neu wird dadurch berechnet, daß der alte zweite Hilfspunkt Q mit dem Faktor 2 multipliziert wird (Block 18).
Wird dagegen im Block 14 bestimmt, daß das aktuelle Bit d_i des Multiplikators d gleich 1 ist, so wird der neue erste Hilfspunkt P_neu dadurch berechnet, daß der alte erste Hilfspunkt P mit dem Faktor 2 multipliziert wird (20). Der neue Wert des zweiten Hilfspunkts Q_neu wird dadurch berechnet, daß der alte erste Hilfspunkt P und der alte zweite Hilfspunkt Q summiert werden (Block 22).
Hierauf wird am Ausgang der Iterationsschleife die Zählvariable i um 1 inkrementiert (Block 24), um dann in einem Block 26 zu überprüfen, ob i kleiner als n ist. Wird diese Frage mit Ja beantwortet, wird, wie es in 1 gezeigt ist, zurückgesprungen, um das nächste Bit des Multiplikators d zu untersuchen. Wird die Frage von Block 26 dagegen mit Nein beantwortet, so wird als Ergebnis E der erste Hilfspunkt P in einem Block 28 ausgegeben.
Wie es bereits ausgeführt worden ist, wird für bestimmte kryptographische Algorithmen lediglich die x-Koordinate des Ergebnispunkts E auf der elliptischen Kurve benötigt. Die in den Blöcken 12, 16, 18, 20 und 22 dargestellten Berechnungen müssen in diesem Fall lediglich für die x-Koordinate durchgeführt werden, die aufgrund der Gesetze der Lucas-Kette unabhängig von den y-Koordinaten der Hilfspunkte P, Q berechnet werden können.
Je nach dem, ob die y-Koordinate des Punkts E benötigt wird, kann diese auf effiziente Weise berechnet werden, wie es später ausgeführt wird.
Im nachfolgenden wird auf die Berechnung des „Double-&-Add"-Paars eingegangen. Der Vollständigkeit halber wird noch einmal darauf hingewiesen, daß eine elliptische Kurve über einem Körper der Charakteristik größer als 3 mit folgender Bestimmungsgleichung zugrunde gelegt wird. y2 = x3 + ax + b (1)
Die beiden Hilfspunkte P' bzw. P_neu und Q' bzw. Q_neu berechnen sich aus den alten Hilfspunkte P und Q im Falle eines Bits d_i folgendermaßen (rechter Zweig des Algorithmus von 1): (P',Q'):= (P + Q,2Q) (2)
Es sei darauf hingewiesen, daß dieselbe Berechnung analog für den linken Iterationszweig von 1 durch Koordinatenaustausch durchgeführt werden kann.
Zusätzlich wird ein Wert D gleich der Differenz zwischen P und Q bzw. Q und P eingeführt, wobei darauf hingewiesen wird, daß das Vorzeichen der Differenz D nicht benötigt und daher im nachfolgenden nicht berücksichtigt wird. Ferner wird darauf hingewiesen, daß die Differenz in jedem Iterationsschritt gleich ist und ferner immer gleich B selbst ist, da im ersten Iterationsschritt die Differenz zwischen P und Q gleich B ist.
Die affine x-Koordinate x_P' des ersten Hilfspunkts auf der elliptischen Kurve berechnet sich folgendermaßen aus den affinen x-Koordinaten der alten Hilfspunkte P und Q:
Die affine x-Koordinate x_D der Differenz aus P und Q berechnet sich folgendermaßen:
Die affine x-Koordinate x_Q' des zweiten Hilfspunkts Q' berechnet sich folgendermaßen:
Werden nun die Gleichungen 3 und 4 miteinander addiert und wird y 2 / P und y 2 / Q unter Verwendung der Gleichung (1) substituiert, wird folgender Ausdruck erhalten: (xP' + xD)(xP – xQ)2 = 2(xP + xQ)(xPxQ + a) + 4b (6)
Schließlich wird y 2 / P mittels der Gleichung (1) substituiert, wodurch sich aus Gleichung (5) folgende Gleichung ergibt: 4xQ'(xQ 3 + axQ + b) = (xQ 2 – a)2 – 8bxQ (7)
Nunmehr wird X_P/Z_P für x_P substituiert, und wird X_Q/Z_Q für x_Q substituiert. Damit ergibt sich aus Gleichung (6) folgende Gleichung: XP'(XPZQ – XQZP)2 = ZP'(2(XPZQ + XQZP)(XPXQ + aZPZQ) + 4b2P Z2Q – xD(XPZQ – XQZP)2) (8)
Mit denselben Substitutionen ergibt sich aus Gleichung (7) folgende Gleichung: XQ'4(XQZQ(X2Q + aZ2Q ) + bZ4Q ) = ZQ'((X2Q – aZ2Q )2 – 8bXQZ3Q (9)
Damit ergeben sich folgende expliziten Formeln für die Addition, also für X_P' und Z_P', d. h. für die erste und die dritte projektive Koordinate des ersten Hilfspunktes: XP' = 2(XPZQ + XQZP)(XPXQ + aZPZQ) + 4bZP 2ZQ 2 – xD(XPZQ – XQZP)2 ZP' = (XPZQ – XQZP)2 (10a)
Für die Double-Formel, also zur Berechnung des zweiten Hilfspunkts Q', ergeben sich folgende Gleichungen: XQ' = (XQ 2 – aZQ 2)2 – 8bXQZQ 3 ZQ' = 4(XQZQ(XQ 2 + aZQ 2) + bZQ 4) (10b)
Durch die Gleichungen (10a) und (10b) sind explizite Formeln gegeben, um die projektiven X-, Z-Koordinaten des ersten Hilfspunkts P und des zweiten Hilfspunkts Q zu berechnen. Diese Koordinaten hängen lediglich von bekannten Größen ab, nämlich von den entsprechenden Koordinaten der „alten" Hilfspunkte P, Q aus dem vorherigen Iterationsschritt, wenn 1 betrachtet wird.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird nunmehr Bezug nehmend auf 2 ein Addierer gezeigt, um zwei Punkte P und Q auf einer elliptischen Kurve zu addieren, um einen aktuellen Hilfspunkt P' zu berechnen. Der Addierer benötigt, wie es in 1 gezeigt ist, eine Einrichtung zum Berechnen von X_P' und Z_P', wobei als Eingangsgrößen X_P, Z_P, X_Q, Z_Q und die Parameter a und b der elliptischen Kurve verwendet werden. Ferner wird darauf hingewiesen, daß auch der Wert x_D, der bei der Berechnung von x_P' verwendet wird, von den affinen Koordinaten x_P, y_P sowie x_Q und y_Q der beiden Punkte P und Q abhängt, wie es aus Gleichung (4) ersichtlich wird.
Der erfindungsgemäße Addierer umfaßt somit eine Einrichtung 30 zum Berechnen von Z_P' und eine Einrichtung 31 zum Berechnen von X_P', wobei die in 2 gezeigten expliziten Formeln entweder hardwaremäßig oder softwaremäßig ausgewertet werden.
3 zeigt einen erfindungsgemäßen Multiplizierer zum Multiplizieren eines Punkts auf einer elliptischen Kurve mit dem Faktor 2. Der erfindungsgemäße Multiplizierer umfaßt eine Einrichtung zum Berechnen der projektiven X-Koordinate des Ergebnispunkts Q', die in 3 mit dem Bezugszeichen 32 bezeichnet ist sowie eine Einrichtung 34 zum Berechnen von Z_Q', wobei die Einrichtungen 32 und 34 eine software- oder hardwaremäßige Ausgestaltung der in 3 gezeigten Formeln durchführen.
Wie es bereits ausgeführt worden ist, ist der in 1 gezeigte erfindungsgemäße Multiplikationsalgorithmus dahinge hend vorteilhaft, daß die beiden Hilfspunkte P_neu bzw. P' und Q_neu bzw. Q' parallel berechnet werden können, da Q' nicht von P' abhängt und umgekehrt.
4 zeigt ein Rechenwerk hierzu. Das Rechenwerk umfaßt eine Parallel-ALU 40, die aus zwei SUB-ALUs besteht, wobei jede SUB-ALU eine Additionsfähigkeit, eine Subtraktionsfähigkeit und eine Multiplikationsfähigkeit hat.
Die Parallel-ALU 40 wird über einen Eingangsbus 41 mit Eingangsdaten versorgt und liefert ihre Ergebnisse auf einen Ausgangsbus 42. Der Eingangsbus 41 ist mit einem Register-Ausgangsbus 43 (RAUS) gekoppelt, während der Ausgangsbus 42 der ALU 40 mit einem Register-Eingangsbus 44 (REIN) gekoppelt ist. Der erfindungsgemäße Prozessor umfaßt ferner einen Registerblock 45 mit acht Registern R0, R1, R2, R3, R4, R5, R6 und R7. Der Prozessor umfaßt ferner eine Initialisierungseinrichtung 48 zum Laden der Register R0 bis R7 des Registerblocks 45 vor Beginn einer Addition und/oder einer Multiplikation mit dem Faktor 2 auf der elliptischen Kurve.
Als zentrales Element umfaßt der Prozessor schließlich eine Ablaufsteuerung 46 zum Steuern der Parallel-ALU 40, des Register-Eingangsbusses 44, des Register-Ausgangsbusses 43 und der Initialisierungseinrichtung 45. Die Parallel-ALU 40 hat ferner Zugriff auf einen Registerspeicher 47 zum Speichern der Parameter a, b der elliptischen Kurve und ferner zum Speichern der affinen x-Koordinate x_D der Differenz von P und Q gemäß Gleichung (4). Der Wert für x_D kann entweder durch die Parallel-ALU 40 selbst berechnet werden, oder kann in jedem Iterationsschritt beispielsweise durch eine separate CPU berechnet werden, wenn der in 4 gezeigte Kryptoprozessor ein Coprozessor in einem Gesamtsystem ist.
Im nachfolgenden wird anhand von 5 auf eine bevorzugte Ausführungsform der Ablaufsteuerung 46 eingegangen, bei der die Berechnung der Koordinaten X_P', Z_P', X_Q' und Z_Q' unter Ver wendung der acht Register R0 bis R7 des Registerblocks 45 parallel durchgeführt wird. In 5 zeigt ein Block 50 zunächst einen Registerinitialisierungsschritt. Das Register R0 wird mit der aktuellen projektiven Koordinate X_P des ersten Hilfspunkts P geladen. Das Register R1 wird mit der projektiven z-Koordinate Z_P des ersten Hilfspunkts P geladen. Das Register R2 wird mit der projektiven x-Koordinate X_Q des zweiten Hilfspunkts Q geladen. Schließlich wird das Register R3 mit der projektiven z-Koordinate Z_Q des zweiten Hilfspunkts Q geladen. Die anderen Register R4 bis R7 können auf 0 initialisiert werden.
In einem Block 51 von 5 sind die Rechenoperationen für die Parallel-ALU 40, die eine erste SUB-ALU 1 und eine zweite SUB-ALU 2 aufweist, gegeben. In der linken Hälfte des Blocks 51 sind nacheinander die von der SUB-ALU 1 abzuarbeitenden Schritte gegeben, während in der rechten Hälfte von Block 51 die für die SUB-ALU 2 abzuarbeitenden Schritte gegeben sind. Insbesondere werden die in 5 nebeneinander stehenden Schritte parallel von beiden ALUs abgearbeitet. Am Beispiel der ersten Zeile von 5 bedeutet dies, daß die SUB-ALU 1 den Inhalt der Register R1 und R2 multipliziert und in das Register R6 lädt. Parallel dazu multipliziert die SUB-ALU 2 den Inhalt des Registers R0 mit dem Inhalt des Registers R3 und lädt das Ergebnis in das Register R7. In einem nächsten Schritt lädt die SUB-ALU 1 dann die Summe des Inhalts des Registers R7 und des Registers R6 in das Register R4. Parallel dazu lädt die SUB-ALU 2 den Inhalt des Registers R7, von dem der Inhalt des Registers R6 subtrahiert ist, in das Register R5. Dieses Prozedere wird in der in Block 51 von 5 gegebenen Reihenfolge fortgesetzt, bis die SUB-ALU 1 in einem letzten Schritt die Differenz des Registers R6 und des Registers R0 in das Register R6 lädt, und die SUB-ALU 2 die Summe des Registers R7 und des Registers R1 in das Register R7 lädt. Dann, in einem Schritt 52, werden die Ergebnisse ausgegeben. Die projektive x-Koordinate X_P' des aktualisierten ersten Hilfspunkts P' ist in dem Register R4 zu finden. Die projektive z-Koordinate Z_P' des aktualisierten ersten Hilfspunkts ist im Register R5 zu finden. Die projektive x-Koordinate X_Q' des aktualisierten zweiten Hilfspunkts ist in dem Register R6 zu finden, und die projektive z-Koordinate des aktualisierten zweiten Hilfspunkts, d. h. Z_Q', ist im Register R7 zu finden.
Selbstverständlich könnte die Folge von Schritten, die im Block 51 dargestellt ist, auch durch eine Seriell-ALU ausgeführt werden, wobei die Sequenz durch die jeweilige Ziffer in Klammern hinter einer Registeroperation gegeben ist. Eine Seriell-ALU könnte dann, falls keine Parallel-ALU verfügbar ist, die Schritte (1) bis (33) in der gegebenen Reihenfolge durchführen und würde zu denselben Ergebnissen, wie sie im Block 52 dargestellt sind, gelangen.
Der erfindungsgemäße Algorithmus benötigt zum Berechnen eines Iterationsschritts (entweder der linke Zweig oder der rechte Zweig in 1) lediglich acht Register R0 bis R7 und ist, wie es ausgeführt worden ist, für eine Parallel-ALU geeignet, die über den Register-Ausgangsbus 43 bzw. den Register-Eingangsbus 44 einen Zugriff auf alle Register hat.
Der in 5 im Block 51 gezeigte Algorithmus, der 19 Multiplikationen und 14 Additionen umfaßt, benötigt, wenn er auf einer Parallel-ALU ausgeführt wird, d. h. mittels einer Parallelarchitektur implementiert wird, die Zeit von zehn Multiplikationen und acht Additionen. Wenn der in Block 51 gezeigte Algorithmus auf einer Seriell-ALU mit einem einzigen Rechenwerk ausgeführt wird, werden, wie es ausgeführt worden ist, die 33 Schritte durchgeführt, d. h. es wird eine Zeit von 19 Multiplikationen und 14 Additionen benötigt.
Nach der skalaren Multiplikation k·P bzw. d·P, liegt die projektive X-Koordinate und die projektive Z-Koordinate des Punkts auf der elliptischen Kurve, der durch k·P gegeben ist, vor. Es gilt: k·P = (XkP : YkP : ZkP)
Um die affinen Koordinaten von k·P zu erhalten, wird folgende Transformation verwendet: kP = (XkP,YkP,ZkP) ↦ kP = (XkP/ZkP,YkP/ZkP) = (xkP,ykP)
Auf ähnliche Weise kann die affine x-Koordinate von (k + 1)·P erhalten werden: (k + 1)P = (X(k+1)P/Z(k+1)P,Y(k+1)P/Z(k+1)P)
Um die affine y-Koordinate des Punkts k·P zu erhalten, wird folgende Gleichung verwendet, wenn y_kP ² und y_P ² mittels Gleichung (1) in Gleichung (3) substituiert werden, wobei die folgende Gleichung verwendet wird: (k + 1)P = kP + P
Die Bestimmungsgleichung für y_kP lautet somit folgendermaßen: 2yPykP = –(xP – xkP)2x(k+1)P + (a + x2P )xkP + (a + xkP 2)xP + 2b (11)
Wenn nunmehr x_kP durch X_kP/Z_kP substituiert wird, und wenn ferner x_(k+1)P durch X_(k+1)P/Z_(k+1)P substituiert wird, wird folgende Bestimmungsgleichung für y_kP erhalten, wobei der Buchstabe P weggelassen worden ist:
Wie es ausgeführt worden ist, wird die y-Koordinate nur bei manchen Algorithmen benötigt. Wenn die y-Koordinate benötigt wird, ist es wesentlich effizienter, die in 1 gezeigte Iteration lediglich für die x-Koordinate durchzuführen und dann die y-Koordinate des Ergebnis-Punkts auf der elliptischen Kurve mittels der Gleichungen (11) und (12) zu berechnen, d. h. unter Verwendung des Punkts (k + 1) P auf der elliptischen Kurve.
Die vorliegende Erfindung ist dahingehend vorteilhaft, daß die Zeit und das Stromprofil durch den in 1 gezeigten Algorithmus homogenisiert werden und daß ferner eine parallele Implementation möglich ist, ohne daß Dummy-Operationen benötigt werden. Im Vergleich zu der klassischen Standardmethode mit Dummy-Addition wird zudem ein effizienteres Verfahren erreicht, da erfindungsgemäß lediglich 19 Multiplikationen im Vergleich zu 26 Multiplikationen pro Bit des skalaren Multiplikators benötigt werden.
Ferner ist, wie es ausgeführt worden ist, das erfindungsgemäße Konzept im Gegensatz zur Standardmethode, die in 6 beschrieben worden ist, parallelisierbar, so daß gegenüber der sicheren Standardmethode mit Dummy-Addition ein Performancegewinn von einem zusätzlichen Faktor von 1,9 erzielt wird, was insgesamt einen Faktor von 2,6 ergibt.
Schließlich ist das erfindungsgemäße Konzept für beliebige elliptische Kurven anwendbar, so lange die Charakteristik der Kurve p größer als 3 ist.
Obwohl es im einzelnen nicht an jeder Stelle ausgeführt ist, sei darauf hingewiesen, daß sämtliche beschriebenen Berech nungen auf eine Restklasse bezüglich eines Moduls bezogen sind, wobei der Modul gleich der Charakteristik p der zugrunde gelegten elliptischen Kurve ist. Die modulare Reduktion kann nach jeder Addition, Multiplikation etc. durchgeführt werden, was vorteilhaft ist, da die Zwischenergebnisse keine großen Zahlen sind. Alternativ wäre es jedoch auch möglich, z. B. eine Addition oder auch die gesamte Multiplikation durchzuführen und erst am Ende mit dem gegebenen Modul zu reduzieren. Dies würde jedoch immens große Register für die Zwischenergebnisse erfordern, weshalb es bevorzugt wird, z. B. nach jedem der im Block 51 von 5 gezeigten Schritte mit dem Modul zu reduzieren. Eine modulare Reduktion am Ende jeder Iteration dient dazu, die Zwischenergebnisse und damit auch die Register zu deren Speicherung klein zu halten.

10: Multiplikationsoperation auf der elliptischen Kurve
12: Initialisierungsschritt
14: Untersuchungsschritt
16: Berechnen des ersten Hilfspunkts, falls d_i gleich 0 ist
18: Berechnen des zweiten Hilfspunkts, falls d_i gleich 0 ist
20: Berechnen des ersten Hilfspunkts, falls d_i gleich 1 ist
22: Berechnen des zweiten Hilfspunkts, falls d_i gleich 1 ist
24: Inkrementieren der Zählvariable
26: Abbruchkriterium
28: Ausgabeschritt
30: Berechnen der projektiven z-Koordinate des ersten
: Hilfspunkts
31: Berechnen der projektiven x-Koordinate des ersten
: Hilfspunkts
32: Berechnen der projektiven x-Koordinate des zweiten
: Hilfspunkts
34: Berechnen der projektiven z-Koordinate des zweiten
: Hilfspunkts
40: Parallel-ALU
41: ALU-Eingangsbus
42: ALU-Ausgangsbus
43: Register-Ausgangsbus
44: Register-Eingangsbus
45: Registerblock
46: Ablaufsteuerung
47: Register für a, b, x_D
48: Initialisierungsblock
50: Initialisierungsblock für Ablaufsteuerung
51: Arbeitssequenz der Ablaufsteuerung
52: Ausgabeschritt der Ablaufsteuerung
100: Double-&-add-Algorithmus
102: Initialisierungsschritt
104: Multiplikator-Untersuchung
106: Verdopplungsschritt falls d_i gleich 1 ist
108: Addierschritt, falls d_i gleich 1 ist
110: Verdopplungsschritt, falls d_i gleich 0 ist
112: Inkrementierungsschritt
114: Abbruchkriterium
116: Ausgabeschritt
118: Dummy-Additionsschritt, falls d_i gleich 0 ist

Claims

Verfahren zum Addieren zweier Punkte auf einer elliptischen Kurve y² = x³ + a·x + b innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei ein erster Punkt der zwei Punkte eine erste projektive Koordinate X_P und eine dritte projektive Koordinate Z_P aufweist, wobei der zweite Punkt eine erste projektive Koordinate X_Q und eine dritte projektive Koordinate Z_Q aufweist, mit folgenden Schritten: Berechnen (31) einer ersten projektiven Koordinate X_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: XP' = 2(XPZQ + XQZP)(XPXQ + aZPZQ) + 4bZP 2ZQ 2 + xD(XPZQ – XQZP)2; undBerechnen (30) einer dritten projektiven Koordinate Z_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: ZP' = (XPZQ – XQZP)2,wobei a und b Parameter der elliptischen Kurve sind, und wobei x_D eine affine Koordinate eines Punkts auf der elliptischen Kurve ist, der sich ergibt, wenn eine Differenz des ersten Punkts (P) und des zweiten Punkts (Q) berechnet wird.
Verfahren zum Multiplizieren eines Punkts auf einer elliptischen Kurve y² = x³ + a·x + b mit einem Faktor 2 inner halb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei der Punkt eine erste projektive Koordinate X_P und eine dritte projektive Koordinate Z_P aufweist, mit folgenden Schritten: Berechnen (32) einer ersten projektiven Koordinate X_Q' eines Ergebnispunkts durch folgende Gleichung: XQ' = (XQ 2 – aZQ 2)2 – 8bXQZQ 3; undBerechnen (34) einer dritten projektiven Koordinate Z_Q' eines Ergebnispunkts (Q') durch folgende Gleichung: ZQ' = 4(XQZQ(XQ 2 + aZQ 2) + bZQ 4),wobei a und b Parameter der elliptischen Kurve sind.
Vorrichtung zum Addieren zweier Punkte auf einer elliptischen Kurve y² = x³ + a·x + b innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei ein erster Punkt (P) durch eine projektive x-Koordinate X_P und durch eine projektive z-Koordinate Z_P gegeben ist, wobei der zweite Punkt durch eine projektive x-Koordinate X_Q und eine projektive z-Koordinate Z_Q gegeben ist, und zum Multiplizieren des zweiten Punkts (Q) mit einem Faktor von 2, um als Ergebnis der Addition einen ersten Ergebnispunkt (P') zu erhalten, der durch eine erste projektive x-Koordinate X_P' und durch eine projektive z-Koordinate Z_P' gegeben ist, und um als Ergebnis der Multiplikation einen zweiten Ergebnispunkt (Q') zu erhalten, der durch eine projektive x-Koordinate X_Q' und durch eine projektive z-Koordinate Z_Q' gegeben ist, mit folgenden Merkmalen: einem Rechenwerk (40) zum Multiplizieren, Addieren und Subtrahieren zweier Eingangswerte; einer Anzahl von acht Registern R0, R1, R2, R3, R4, R5, R6, R7; und einer Ablaufsteuerung (46) zum Steuern der Register und des Rechenwerks gemäß den folgenden Schritten: (0) Initialisieren des Registers R0 mit X_P, des Registers R1 mit Z_P, des Registers R2 mit X_Q und des Registers R3 mit Z_Q; (1) R6 ← R2·R1; (2) R7 ← R3·R0; (3) R4 ← R7 + R6; (4) R5 ← R7 – R6; (5) R5 ← R5·R5; (6) R7 ← R1·R3; (7) R1 ← a·R7; (8) R6 ← R7·R7; (9) R0 ← R0·R2; (10) R6 ← b·R6; (11) R0 ← R0 + R1; (12) R6 ← R6 + R6; (13) R0 ← R0·R4; (14) R1 ← x_D·R5; (15) R4 ← R0 + R6; (16) R4 ← R4 + R4; (17) R6 ← R2 + R2; (18) R4 ← R4 – R1; (19) R7 ← R3 + R3; (20) R0 ← R6·R7; (21) R1 ← R3·R3; (22) R2 ← R2·R2; (23) R3 ← a·R1; (24) R6 ← R2 – R3; (25) R7 ← R2 + R3; (26) R1 ← R1 + R1; (27) R2 ← b·R1; (28) R7 ← R7·R0; (29) R1 ← R2·R1; (30) R0 ← R0·R2; (31) R6 ← R6·R6; (32) R6 ← R6 – R0; (33) R7 ← R7 + R1; (34) Ausgeben eines Inhalts von R4, um die projektive x-Koordinate X_P' des Ergebnispunkts der Addition zu erhalten, Ausgeben des Inhalts von R5 um die projektive z-Koordinate Z_P' der Addition zu erhalten, Ausgeben des Registers R6, um die projektive x-Koordinate X_Q' des Ergebnispunkts der Multiplikation zu erhalten, und Ausgeben des Inhalts des Registers R7, um die projektive z-Koordinate Z_Q' des Ergebnispunkts der Multiplikation zu erhalten, wobei das Symbol „·" eine Multiplikation darstellt, wobei das Symbol „+" eine Addition darstellt, wobei das Symbol „–" eine Subtraktion darstellt, wobei a, b Parameter der elliptischen Kurve sind, wobei x_D eine affine x-Koordinate eines Punkts ist, der sich ergibt, wenn der erste Punkt P vom zweiten Punkt Q subtrahiert wird, und wobei das Symbol „←" bedeutet, daß das Register, auf das die Pfeilspitze gerichtet ist, mit einem Wert geladen wird, der sich aus der arithmetischen Operation ergibt, die an einem Fußpunkt des Pfeils steht.
Vorrichtung nach Anspruch 3, die ferner ein weiteres Rechenwerk aufweist, und bei dem die Ablaufsteuerung (46) angeordnet ist, um das Rechenwerk (SUB-ALU 1) und das weitere Re chenwerk (SUB-ALU 2) zum parallelen Ausführen der folgenden Schritte zu veranlassen: – Schritt (1) parallel zu Schritt (2); – Schritt (3) parallel zu Schritt (4); – Schritt (5) parallel zu Schritt (6); – Schritt (7) parallel zu Schritt (8); – Schritt (9) parallel zu Schritt (10); – Schritt (11) parallel zu Schritt (12); – Schritt (13) parallel zu Schritt (14); – Schritt (16) parallel zu Schritt (17); – Schritt (18) parallel zu Schritt (19); – Schritt (20) parallel zu Schritt (21); – Schritt (22) parallel zu Schritt (23); – Schritt (24) parallel zu Schritt (25); – Schritt (27) parallel zu Schritt (28); – Schritt (29) parallel zu Schritt (30); und – Schritt (32) parallel zu Schritt (33).
Vorrichtung zum Addieren zweier Punkte auf einer elliptischen Kurve y² = x³ + a·x + b innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei ein erster Punkt der zwei Punkte eine erste projektive Koordinate X_P und eine dritte projektive Koordinate Z_P aufweist, wobei der zweite Punkt eine erste projektive Koordinate X_Q und eine dritte projektive Koordinate Z_Q aufweist, mit folgenden Merkmalen: einer Einrichtung zum Berechnen (31) einer ersten projektiven Koordinate X_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: XP' = 2(XPZQ + XQZP)(XPXQ + aZPZQ) + 4bZP 2ZQ 2 – xD(XPZQ – XQZP)2; undeiner Einrichtung (30) zum Berechnen einer dritten projektiven Koordinate Z_P' eines Ergebnispunkts auf der elliptischen Kurve durch folgende Gleichung: ZP' = (XPZQ – XQZP)2,wobei a und b Parameter der elliptischen Kurve sind, und wobei x_D eine affine Koordinate eines Punkts auf der elliptischen Kurve ist, der sich ergibt, wenn eine Differenz des ersten Punkts (P) und des zweiten Punkts (Q) berechnet wird.
Vorrichtung zum Multiplizieren eines Punkts auf einer elliptischen Kurve y² = x³ + a·x + b mit einem Faktor 2 innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei der Punkt eine erste projektive Koordinate X_P und eine dritte projektive Koordinate Z_P aufweist, mit folgenden Merkmalen: einer Einrichtung zum Berechnen (32) einer ersten projektiven Koordinate X_Q' eines Ergebnispunkts durch folgende Gleichung: XQ' = (XQ 2 – aZQ 2)2 – 8bXQZQ 3; undeiner Einrichtung zum Berechnen (32) einer dritten projektiven Koordinate Z_Q' eines Ergebnispunkts (Q') durch folgende Gleichung: ZQ' = 4(XQZQ(XQ 2 + aZQ 2) + bZQ 4),wobei a und b Parameter der elliptischen Kurve sind.
Verfahren zum Addieren zweier Punkte auf einer elliptischen Kurve y² = x³ + a·x + b innerhalb eines kryptographischen Algorithmus, wobei x und y Koordinaten von Punkten auf der elliptischen Kurve sind, und wobei die elliptische Kurve über einem Körper mit einer Charakteristik größer als 3 definiert ist, wobei ein erster Punkt (P) durch eine projektive x-Koordinate X_P und durch eine projektive z-Koordinate Z_P gegeben ist, wobei der zweite Punkt durch eine projektive x-Koordinate X_Q und eine projektive z-Koordinate Z_Q gegeben ist, und zum Multiplizieren des zweiten Punkts (Q) mit einem Faktor von 2, um als Ergebnis der Addition einen ersten Ergebnispunkt (P') zu erhalten, der durch eine erste projektive x-Koordinate X_P' und durch eine projektive z-Koordinate Z_P' gegeben ist, und um als Ergebnis der Multiplikation einen zweiten Ergebnispunkt (Q') zu erhalten, der durch eine projektive x-Koordinate X_Q' und durch eine projektive z-Koordinate Z_Q' gegeben ist, unter Verwendung von acht Registern R0, R1, R2, R3, R4, R5, R6 und R7, mit folgenden Schritten: (0) Initialisieren des Registers R0 mit X_P, des Registers R1 mit Z_P, des Registers R2 mit X_Q und des Registers R3 mit Z_Q; Durchführen der folgenden Registeroperationen: (1) R6 ← R2·R1 (2) R7 ← R3·R0 (3) R4 ← R7 + R6 (4) R5 ← R7 – R6 (5) R5 ← R5·R5 (6) R7 ← R1·R3 (7) R1 ← a·R7 (8) R6 ← R7·R7 (9) R0 ← R0·R2 (10) R6 ← b·R6 (11) R0 ← R0 + R1 (12) R6 ← R6 + R6 (13) R0 ← R0·R4 (14) R1 ← x_D·R5 (15) R4 ← R0 + R6 (16) R4 ← R4 + R4 (17) R6 ← R2 + R2 (18) R4 ← R4 – R1 (19) R7 ← R3 + R3 (20) R0 ← R6·R7 (21) R1 ← R3·R3 (22) R2 ← R2·R2 (23) R3 ← a·R1 (24) R6 ← R2 – R3 (25) R7 ← R2 + R3 (26) R1 ← R1 + R1 (27) R2 ← b·R1 (28) R7 ← R7·R0 (29) R1 ← R2·R1 (30) R0 ← R0·R2 (31) R6 ← R6·R6 (32) R6 ← R6 – R0 (33) R7 ← R7 + R1; und (34) Ausgeben eines Inhalts von R4 um die projektive x-Koordinate des Ergebnispunkts der Addition zu erhalten, Ausgeben des Inhalts von R5 um die projektive z-Koordinate Z_P' der Addition zu erhalten, Ausgeben des Registers R6, um die projektive x-Koordinate X_Q' des Ergebnispunkts der Multiplikation zu erhalten, und Ausgeben des Inhalts des Registers R7, um die projektive z-Koordinate Z_Q' des Ergebnispunkts der Multiplikation zu erhalten, wobei das Symbol „·" eine Multiplikation darstellt, wobei das Symbol „+" eine Addition darstellt, wobei das Symbol „–" eine Subtraktion darstellt, wobei a, b Parameter der elliptischen Kurve sind, wobei x_D eine affine x-Koordinate eines Punkts ist, der sich ergibt, wenn der erste Punkt P vom zweiten Punkt Q subtrahiert wird, und wobei das Symbol „←" bedeutet, daß das Register, auf das die Pfeilspitze gerichtet ist, mit einem Wert geladen wird, der sich aus der arithmetischen Operation ergibt, die an einem Fußpunkt des Pfeils steht.
Verfahren nach Anspruch 7, bei dem folgende Schritte parallel ausgeführt werden: – Schritt (1) parallel zu Schritt (2) – Schritt (3) parallel zu Schritt (4) – Schritt (5) parallel zu Schritt (6) – Schritt (7) parallel zu Schritt (8) – Schritt (9) parallel zu Schritt (10) – Schritt (11) parallel zu Schritt (12) – Schritt (13) parallel zu Schritt (14) – Schritt (16) parallel zu Schritt (17) – Schritt (18) parallel zu Schritt (19) – Schritt (20) parallel zu Schritt (21) – Schritt (22) parallel zu Schritt (23) – Schritt (24) parallel zu Schritt (25) – Schritt (27) parallel zu Schritt (28) – Schritt (29) parallel zu Schritt (30) – Schritt (32) parallel zu Schritt (33).
Verfahren nach Anspruch 7 oder 8, bei dem nach einer Addition, Multiplikation und/oder Subtraktion eine modulare Reduktion mit der Charakteristik der elliptischen Kurve als Modul durchgeführt wird.