DE602004006126T2

DE602004006126T2 - Verbesserte inversionsberechnungen

Info

Publication number: DE602004006126T2
Application number: DE602004006126T
Authority: DE
Inventors: Gerardus. T. M. Redhill HUBERT; Sander M. Redhill VAN RIJNSWOU
Original assignee: Koninklijke Philips Electronics NV
Current assignee: NXP BV
Priority date: 2003-06-21
Filing date: 2004-06-10
Publication date: 2007-12-27
Anticipated expiration: 2024-06-11
Also published as: CN1809807B; CN1809807A; ATE360853T1; EP1639448A2; WO2004114123A3; EP1639448B1; US20070016635A1; GB0314562D0; JP2007520728A; WO2004114123A2; DE602004006126D1

Description

Die vorliegende Erfindung bezieht sich auf ein Verfahren zur Durchführung einer Inversionsoperation und auf eine Vorrichtung zur Durchführung einer Inversionsoperation.
Elliptische Kurvenkryptographie (ECC) schließt den Gebrauch von Berechnungen bezüglich einer Elliptische-Kurve-Beziehung über GF(p) oder GF(2ⁿ) ein und erfordert die Multiplikation von Long Integers, welche während der Implementierung von beispielsweise public-key-Algorithmen in Verschlüsselungs-Prozessoren wiederholt durchgeführt werden.
Typischerweise müssen die Multiplikations-Operationen mehrere hundert Male durchgeführt werden, um eine Ver- oder Entschlüsselungs-Operation zum Abschluss zu bringen und deshalb ist es wichtig, dass die Kryptographie-Vorrichtungen, welche diese Operationen durchführen, die langen Multiplikationen schnell unter Verwendung eines Hochgeschwindigkeits-Multiplizierers durchführen.
ECC-Berechnungen schließen darüber hinaus eine Inversions-Berechnung ein, das heißt die Berechnung von Z^–1, sodass das Produkt Z·Z^–1= 1 mod N ist. Jede Punkt-Addition und Punkt-Verdopplungs-Berechnung benötigt eine solche Berechnung. Die derzeitigen Algorithmen sind rechenaufwändig.
Eine weitere Möglichkeit besteht darin, in dem so genannten projektiven Raum zu arbeiten. Dies verschiebt die Inversions-Berechnung an das Ende, und muss nur einmal durchgeführt werden, allerdings ist im Tausch dafür die Anzahl der Multiplikationen stark vergrößert.
Zunehmend werden derartige Kryptographie-Algorithmen in elektronischen Bauteilen wie zum Beispiel Smartcards verwendet und bei diesen Applikationen sind die Rechenkapazität und der Energieverbrauch stark beschränkt.
Eine herkömmliche Berechnungsverfahren ist das binäre GCD-System, welches mit Paaren von Hilfsvariablen arbeitet. Ein Paar wird, wenn es gerade ist, durch die Division durch Zwei, oder, wenn es ungerade ist, durch Subtraktion in der Größe reduziert.
Allerdings ist es im GCD-System oftmals notwendig, die Operation für das andere Paar durch die Addition der Hälfte des Teilungsrests zu korrigieren.
Ein weiteres konventionelles Berechnungsverfahren ist das Kaliski-System, welches wiederum zwei Paare von Hilfsvariablen verwendet, von denen ein Paar durch die Division durch Zwei reduziert wird, wenn es gerade ist, oder durch Subtraktion reduziert wird, wenn es ungerade ist.
Jedoch wird in diesem System jede notwendige Korrektur auf die zweite Ebene verschoben.
Ziel der vorliegenden Erfindung besteht demnach darin, eine effektivere Inversionsoperation zur Verfügung zu stellen.
Darüber hinaus ist Ziel der vorliegenden Erfindung, ein Inversionsverfahren zur Verfügung zu stellen, welches weniger Rechenschritte benötigt.
Weiterhin ist Ziel der vorliegenden Erfindung, eine Inversionsoperation zur Verfügung zu stellen, welche schneller, als in konventionellen Systemen abgeschlossen ist.
Gemäß einem Aspekt sieht die vorliegende Erfindung ein Verfahren gemäß Anspruch 1 vor.
Ein Vorteil der vorliegenden Erfindung besteht darin, dass die meisten Operationen nur für die höchstwertigen Datenwörter der Hilfsvariablen durchgeführt werden. Nach einer Anzahl derartiger Berechnungen werden eine Anzahl von Multiplikationen bei den vollkommenen Hilfsvariablen durchgeführt, welche einfacher sind.
Diese Vorteile resultieren darin, dass die Anzahl der notwendigen Operationen im Vergleich mit herkömmlichen Verfahren reduziert ist, wodurch sichergestellt ist, dass die Berechnungen schneller durchgeführt werden können.
Demnach besteht ein signifikanter Vorteil, welcher durch die vorliegende Erfindung bewirkt wird, darin, dass die Zeit, welche zur Durchführung der gesamten Berechnungsoperation notwendig ist, reduziert wird.
Darüber hinaus wird der Grad an Sicherheit, den das Verfahren der vorliegenden Erfindung ermöglicht, im Vergleich zu konventionellen Kryptographie-Verfahren beibehalten.
Vorzugsweise verfügt das Verfahren über vier Hilfsvariablen U, V, R und S für welche die Invarianzen: IS·V – R·UI = N S·Y = U mod N R·Y = V mod N. gelten.
Vorzugsweise arbeitet das Verfahren mit den höchstwertigen Datenwörtern der Variablen.
Dem entsprechend besteht ein Vorteil der vorliegenden Erfindung darin, dass die Berechnungs-Operationen schneller durchgeführt werden.
Gemäß einem weiteren Aspekt der vorliegenden Erfindung ist ein Computerprogramm-Produkt vorgesehen, welches direkt in den internen Speicher eines digitalen Computers geladen werden kann und über Software-Programmabschnitte verfügt, welche das Verfahren der vorliegenden Erfindung durchführen, wenn das Produkt auf einen Computer ausgeführt wird.
Gemäß einem weiteren Aspekt sieht die vorliegende Erfindung ein Computerprogramm vor, welches direkt in den internen Speicher eines digitalen Computers geladen werden kann und Software-Programmabschnitte umfasst, welche das Verfahren der vorliegenden Erfindung durchführen, wenn das Programm auf einem Computer ausgeführt wird.
Gemäß einem weiteren Aspekt sieht die vorliegende Erfindung einen Träger vor, welcher elektronische Signale für ein Computerprogramm gemäß der vorliegenden Erfindung enthalten kann.
Gemäß einem weiteren Aspekt sieht die vorliegende Erfindung eine elektronische Distribution eines Computerprogramm-Produkts oder eines Computerprogramms oder eines Trägers der vorliegenden Erfindung vor.
Gemäß einem weiteren Aspekt sieht die vorliegende Erfindung eine Vorrichtung, wie in Anspruch 13 definiert, vor.
Das Verfahren und die Vorrichtung der vorliegenden Erfindung sind sowohl für die Berechnungen über GF(p), GF(2ⁿ) als auch für Long-Integer-Division anwendbar.
Damit die vorliegende Erfindung leichter verstanden werden kann, wird im folgenden eine Beschreibung unter Zuhilfenahme von Beispielen und unter Bezugnahme auf die beigefügten Zeichnungen gegeben, von denen:
1 ein Blockdiagramm einer Applikation der Erfindung in einer Smartcard darstellt;
2 eine schematische Zeichnung einer Inversionsoperation gemäß der vorliegenden Erfindung darstellt;
3 eine Hardware-Implementierung der vorliegenden Erfindung darstellt,
4 eine weitere, detaillierte Hardware-Implementierung der vorliegenden Erfindung darstellt;
5 eine schematische Zeichnung einer weiteren Inversionsoperation der vorliegenden Erfindung darstellt;
6 eine schematische Zeichnung einer weiteren Inversionsoperation der vorliegenden Erfindung darstellt;
7 eine schematische Zeichnung einer weiteren Operation der vorliegenden Erfindung darstellt.
1 zeigt ein Blockdiagramm einer Hardware-Implementierung der vorliegenden Erfindung, welche eine Smartcard 50 mit folgenden Komponenten umfasst:

– Mikrocontroller 51 zur elementaren Steuerung der Kommunikation mit der äußeren Welt über das Interface. Es setzt Zeiger auf Daten im RAM/ROM und startet den Coprozessor.
– Interface zu der Außenwelt zur Herstellung einer Verbindung mit einer Smartcard z. B. gemäß Iso-7816-3.
– ein Read Only Memory (ROM) 52 für das Programm des Mikrocontrollers.
– ein programmierbarer Read Only Memory (Flash oder EEPROM) 53 zur permanenten Speicherung von Daten oder Programmen.
– RAM 54 zur Speicherung von nicht-permanenten Daten, wie zum Beispiel der Speicherung von Zwischenergebnissen während den Berechnungen.
– Coprozessor 55, welcher dazu ausgebildet ist, spezielle Hochgeschwindigkeitsanwendungen für EEC- oder RSA-Berechnungen durchzuführen. Wenn eine Anwendung beendet ist, wird die Steuerung an den Mikrocontroller zurückgegeben.

Gemäß einer Variante ist die vorliegende Erfindung in Software implementiert, mit einem Mikroprozessor, dessen ALU Addition, Subtraktion und Verschiebe-Operationen durchführt, in der Programmierung des Controllers implementiert, um logische Steuerung und Ordnungs-Erkennung durch das Schiebe-Register zu ermöglichen.
In Figur e ist eine Inversionsoperation der vorliegenden Erfindung dargestellt, welche weiter unten beschrieben ist.
Demnach schließt dieses Verfahren eine Berechnung über GF(p) die Operation
R = Y^–1 mod N ein,
welche vier Hilfsvariablen U, V, S und R mit
U = Y
V = N
S = 1
R = 0
aufweist, wobei U und V immer positiv sind.
Die Ordnung einer Hilfsvariablen ist die Anzahl der relevanten Bits, welche diese darstellen. Zum Beispiel ist die Ordnung von U = dU 6, wenn U = 111100 ist, und wenn V = 001110 ist, ist die Ordnung von V = dV 4.
Die Operation bedingt das Setzen von: B = dU – dV (Schritt S1);Und wenn b < 0 ist, die Durchführung der Operation (Schritt S2, S3):
(swap U, V)
(swap R, S)
(swap dU, dV)
b = –b
dann U = U – 2b·V S = S – Sb·R und wenn (U < 0),
dann (Schritt 4) U = –U
S = –S,
wenn (R < 0), dann R = R + N,
wenn (R > N), dann R = R – N.
Dem entsprechend gelten nach jeder Schleifeniteration für die Invarianzen:
gcd(U,V) = gcd(Y,N)
SY = U mod N
RY = V mod N
ISV – RUI = N.
In jedem Schritt wird entweder die Ordnung von U oder von V verkleinert. Dem entsprechend werden U und V immer kleiner, bis U in dem letzten Schritt zu 0 wird (U = 2^bV).
Weil U = 0 ist, impliziert die Invarianz gcd (U, V) = gcd (Y, N), dass V = gcd (Y, N) = 1 ist, weil Y und V teilerfremd sind.
Dann wird RY = 1 mod N oder R = Y^–1mod N.
Wenn U = 0, –N < R < 2N ist,
ergibt sich höchstens ein Korrekturschritt, nämlich: entweder Addieren oder Subtrahieren von N.
In der Praxis ist R immer größer als N, sodass die Subtraktion von N niemals auftritt.
Des weiteren ist gelegentlich ISVI < 2N und IRUI < 2N.
Weil alle Integer-Werte sind,
ISI < 2N;
IVI < 2N;
IRI < 2N;
IUI < 2N.
Für diese Variablen wird zu deren Darstellung nur ein Bit mehr als N benötigt.
Für S und R wird darüber hinaus ein Vorzeichen-Bit benötigt.
2 zeigt die Hardware-Implementierung des Verfahrens der vorliegenden Erfindung.
Register 10, 11, 12 und 13 enthalten die Variablen U, V, S, R. Die Addierer 14, 15 führen Addition, Subtraktion, Negation und mod 2 Additionen durch. V und R können um b Bits verschoben werden.
Die Steuerungslogik 16 steuert den Prozess. Es gibt zwei Ordnungs-Erkennungen 17, 18, eine für U und eine für V. Der dSubtrahierer 19 gibt die Differenz (b) aus.
Zunächst wird Y in U, N in V geladen und S wird zu 1 und R zu 0 gesetzt.
Dann wird das Verfahren gestartet.
Wenn b < 0 ist, tauschen U und V ihre Inhalte aus, S und R machen das gleiche und b wird negiert.
Beide Addierer werden auf Subtraktion und die Verschieber werden auf Verschiebung um b Bits eingestellt. Daraufhin wird die Subtraktion durchgeführt. Wenn U negativ ist, werden die Addierer dazu eingestellt, sowohl U, als auch S zu negieren.
Das Verfahren wird durchgeführt, solange U ≠ 0 ist. Wenn U = 0 ist und R < 0 oder R > N, wird S in N geladen. Daraufhin wird entweder R + N oder R – N berechnet.
Normalerweise bestehen die Operanden aus einer Anzahl von Datenwörtern. Gemäß einer Variante können die Berechnungen jedoch dadurch beschleunigt werden, dass nur das höchstwertige Datenwort zwei der Variablen und 4 Hilfsvariablen von der Größe eines Datenworts verwendet werden, wobei die Invarianzen gültig gehalten werden. Das spart auch Chipfläche und Energie. Das Resultat wird als Schätzfunktion für die nachfolgenden Berechnungen und die gesamten Operanden verwendet.
3 zeigt die detailliertere Hardware-Implementierung. Register 30 bis 35, jedes mit einer Kapazität von einem Datenwort, enthält U_H, V_H, uu, uv, vu und vv.
U_H und V_H werden zunächst mit dem höchstwertigen Datenwort von U und V geladen. U = uu·U0 – uv·V0 V = vu U0 – vv·V0 S = uu·S0 - uv·R0 R = vu·S0 – vv·R0 Uu, uv vu und vv sind Datenwörter von geeigneter Größe.
Das Verfahren startet mit uu = 1, vv = –1 und uv = vu = 0,
U₀ = Y;
V₀ = N;
S₀ = 1;
R₀ = 0.
Angenommen, dass die Gleichungen nach einer Anzahl von Schritten immer noch korrekt sind. Nach der nächsten Berechnung sind die Gleichungen immer noch korrekt. Weil sie am Anfang korrekt waren, bleiben sie korrekt.
Bei der Berechnung von U' = U – 2^bV und S' = S – 2^bR, wird uu' = uu – 2bvu uv' = uv – Zbvv vu' = vu vv' = vvgewählt.
Wenn notwendig ist, U' = U + 2^bV und S' = S + 2^bR zu berechnen, wird uu' = uu – 2bvu uv' = uv – 2bvv vu' = vu vv' = vvgewählt.
Wenn erforderlich, werden uu und vu, sowie uv und vv getauscht.
Dadurch werden sowohl U und V als auch R und S getauscht.
Um die Operanden zu aktualisieren, starte mit dem Laden von U_H mit MSW von U und von V_H mit dem MSW von V. Dann ist
uu = 1, vv = –1 und uv = uv = 0.
Daraufhin wird eine Anzahl von Berechnungen durchgeführt, wobei die Anzahl von der Größe der Datenwörter und davon abhängt, wie viele brauchbare Bits übrig geblieben sind.
Da V_H verschoben ist, wird es mit Nullen aufgefüllt anstelle von (unbekannten) richtigen Bits, sodass U_H und V_H immer kleiner werden. Das Verfahren wird gestoppt, wenn fast keine Bits mehr übrig sind. Auch wird die Bestimmung des Vorzeichens inkorrekt.
Dann berechne U, V, S und R mit Hilfe uu...vv und U₀...S₀.
Dies liefert neue reduzierte Werte von U und V, für die immer noch die Invarianzen gelten
Als nächstes setze U₀ zu U, V₀ zu V, und tu das gleiche für S₀ und R₀. Setze wieder uu = 1, vv = –1 und uv = vu = 0.
Dann wiederhole diese Prozedur. Jedes Mal werden U und V kleiner bis sie in das U_H und das V_H Register passen.
Nun ist die Berechnung nicht länger eine Schätzung, sondern eine exakte Berechnung und endet mit dem korrekten Ergebnis. Abschließend muss nur R nachgerechnet werden, um Y^–1 zu bestimmen.
Gemäß einer Variante zu dem Verfahren aus den 1 bis 4 gestattet das Berechnungsverfahren negative Werte für U und V und entfernt den Korrigierschritt, wenn U negativ ist (siehe 5).
Die Ordnung von positiven Zahlen ist die Anzahl von Bits nach der Entfernung aller voranstehenden Nullen und die Ordnung von negativen Zahlen ist die Anzahl von Bits nach Entfernung aller vorangestellten Einsen.
Wiederum sind Hilfsvariablen:
U = Y;
V = N;
S = 1;
R = 0;
während (U ≠ 0) ist und
wenn (b < 0), führe aus
{swap (U, V); swap (R, S) swap (dU, dV); b = –b};
wenn (Vorzeichen(U) = Vorzeichen (V)), führe aus
{U = U – 2^b·V; S = S – 2b·R;}
sonst
{U = U + 2^b·V; S = S + 2^b·R;}
dU = Ordnung(U);
wenn (R < 0), dann R = R + N;
wenn (R > N), dann R = R – N.
6 zeigt eine zweite Ausführungsform, welche ein Berechnungsverfahren über GF(2ⁿ) ist, wobei der Hauptunterschied darin liegt, dass:
α die Variable der Polynome U, V, S und R ist;
N das nicht reduzierbare Polynom ist;
der Algorithmus simpler ist, weil es keine negativen Werte und nur eine mod 2 Addition gibt.
Deshalb mit
U = Y;
V = N;
S = 1;
R = 0;
während (U > 0)
b = dU – dV
wenn (b < 0 {swap (u, V); swap (R, S); swap (dU, dV); b = –b;} U = U⊕αb·V; S = S⊕αb·R;d = Ordnung(U)
wenn (R > N) R = R⊕N.
Auf diese Weise wird zunächst Y in U, N in V geladen, S wird zu 1 und R zu 0 gesetzt. Daraufhin wird das Verfahren gestartet (Schritt S10 – S12).
Wenn b < 0 ist, tauschen U und V ihre Inhalte aus, S und R tun das gleiche und b wird negiert.
Beide Addierer werden immer auf die Addition mod 2 eingestellt. Die Verschieber werden auf Verschiebung um b Bits eingestellt. Dann wird die Addition durchgeführt.
Der Vorgang wird solange durchgeführt, solange U ≠ 0 ist.
Wenn U = 0 und R = R > N ist, wird S mit N geladen, und daraufhin wird R ⊕ N berechnet.
7 zeigt eine dritte Ausführungsform, welche ein Berechnungsverfahren für Long-Integer-Divisionen ist, wobei der Hauptunterschied darin liegt, dass zunächst X in U, Y in V geladen wird, S zu 0 und R zu 1 gesetzt wird.
Wenn U > 0 ist, wird der UV-Addierer auf Subtraktion und der RS-Addierer auf Addition eingestellt, oder das Gegenteil wird, wenn sachgemäß, getan. Die Verschieber werden dazu eingestellt, um b Bits zu verschieben. Dann wir die Additions-/Subtraktionsoperation durchgeführt.
Das Verfahren wird solange durchgeführt, solange U ≠ 0 und b ≥ 0 ist.
Wenn der Prozess zum Ende gekommen ist und U < 0 ist, wird b auf 0 gesetzt. Dann wird eine Addition/Subtraktion durchgeführt (U = U + V; S = S – R).
Dann ist U der Rest von R' und S ist der Quotient Q, X = Q·Y + R' mit 0 ≤ R' < Y.

Claims

Verfahren zur Durchführung einer Inversionsoperation in einer kryptographischen Berechnung in einem elektronischen Bauteil mit wenigstens zwei Hilfsvariablen U und V, um R = Y^–1 mod N zu berechnen, wobei das Verfahren umfasst: – Setzen von U = Y und V = N und verschieben einer Variablen, daraufhin – Durchführen einer Reduktion (S3), durch Subtrahieren dieser Variable von einer größeren Variable, wobei die Reduktion mit Hilfe einer Operation U = U – 2^bV für GF(p) und mit einer Operation U = U⊕α^b·V für GF(2ⁿ) durchgeführt wird, wobei b = dU – dV ist, und dU und dV die Ordnungen von U bzw. V sind, und α eine Variable der Polynome ist, welche durch die Hilfsvariablen dargestellt sind.
Verfahren gemäß Anspruch 1, bei dem die Variablen die gleichen Ordnungen aufweisen.
Verfahren gemäß einem der Anspruche 1 oder 2, umfassend eine Aktualisierung einer Vielzahl von zusätzlichen Variablen, sodass Invarianzen gültig bleiben.
Verfahren gemäß einem der vorangehenden Ansprüche, mit vier Hilfsvariablen U, V, R und S, für welche folgende Invarianzen gelten: |S·V – R·U| = N S·Y = U mod N R·Y = V mod N.
Verfahren gemäß Anspruch 4, umfassend Vermindern der Größe von U und V Schritt für Schritt, bis U = 1 ist.
Verfahren gemäß Anspruch 5, umfassend ein Anwenden entweder der Operation R·Y = 1 mod N oder R = Y^–1 mod N, je nachdem, welche angemessen ist.
Verfahren gemäß einem der vorangehenden Ansprüche, welches mit den höchstwertigen Datenwörtern der Variablen durchgeführt wird.
Verfahren gemäß einem der vorangehenden Ansprüche, welches ein Verfahren zur Long-Integer-Division umfasst.
Computerprogrammprodukt, das direkt in den internen Speicher eines digitalen Computers geladen werden kann und Softwareprogrammabschnitte umfasst, welche das Verfahren gemäß einem oder mehreren der Ansprüche 1 bis 8 durchführt, wenn das Produkt auf einem Computer ausgeführt wird.
Computerprogramm, das direkt in den internen Speicher eines digitalen Computers geladen werden kann und Softwareprogrammabschnitte umfasst, welche das Verfahren gemäß einem der Ansprüche 1 bis 8 durchführt, wenn das Programm auf einem Computer ausgeführt wird.
Träger, der elektronische Signale eines Computerprogramms gemäß Anspruch 10 enthalten kann.
Elektronische Distribution eines Computerprogrammprodukts gemäß Anspruch 9 oder eines Computerprogramms gemäß Anspruch 10 oder eines Trägers gemäß Anspruch 11.
Vorrichtung zum Durchführen einer Inversionsoperation in einer kryptographischen Berechnung mit wenigstens zwei Hilfsvariablen U und V, um R = Y^–1 mod N zu berechnen, wobei die Vorrichtung Mittel umfasst, U = Y und V = N zu setzen, Mittel umfasst, eine Variable (V, R) zu verschieben, und Mittel (10–17) umfasst, um eine Reduktion durch eine Subtraktion oder Addition dieser Variable von bzw. zu einem größeren Wert durchzuführen, dadurch gekennzeichnet, dass die Reduktion durch eine Operation U = U – 2^bV für GF(p) und eine Operation U = U⊕α^b·V für GF(2ⁿ) ausgeführt wird, wobei b = dU – dV ist und dU und dV die Ordnungen von U bzw. V sind und α die Variable der Polynome ist, welche durch die Hilfsvariablen dargestellt sind.
Vorrichtung gemäß Anspruch 13, wobei die Variablen (V, R) ohne Verschiebung die gleiche Ordnung aufweisen.
Vorrichtung gemäß Anspruch 13 oder 14, welche Mittel zur Aktualisierung einer Vielzahl von zusätzlichen Variablen umfasst, derart, dass Invarianzen gültig bleiben.