DE69600394T2 - Verfahren zum Erzeugen eines Fehlerkorrekturparameters bezüglich der Verwendung von modularen Operationen nach der Montgomery-Methode - Google Patents

Description

• Die Erfindung betrifft ein Verfahren zum Erzeugen eines Fehlerkorrekturparameters in Verbindung mit der Verwendung von modularen Operationen nach der Montgomery-Methode. Diese Methode erlaubt es, Modulo-Berechnungen in einem endlichen Körper GF(2n) (Galois-Körper) ohne Divisionen durchzuführen.
• Üblicherweise werden Modulo-Operationen in GF(2n) bei der Kryptographie für Anwendungen wie Authentifizierung von Nachrichten, Identifikation eines Nutzers und Austausch von Schlüsseln verwendet. Solche Anwendungsbeispiele sind z.B. in der französischen Patentanmeldung mit der Veröffentlichungsnummer 2 679 054 beschrieben.
• Kommerziell findet man integrierte Schaltkreise, die für diese Anwendungen hergestellt sind, z.B. von SGS-THOMSON MICROELECTRONICS S.A. den ST16CF54, gebaut um eine Verbindung vom Typ Zentraleinheit - arithmetischer Coprozessor herum und gedacht für den Einsatz bei Modulo-Berechnungen. Dieser Coprozessor erlaubt es, Modulo-Operationen durchzuführen unter Verwendung des Montgomery-Verfahrens. Weitere Informationen über diesen Coprozessor finden sich in der europäischen Patentanmeldung EP-A-0 601 907, die im folgenden als Schrift D2 bezeichnet wird, worauf sich die Darstellung in Figur 1 bezieht (diese Figur entspricht Figur 2 in der genannten europaischen Patentanmeldung), wobei dieser Schaltkreis der Gegenstand jener Anmeldung ist.
• Die Basisoperation von Modulo-Berechnungen nach dem Montgomery-Verfahren, genannt Pfield, besteht darin, aus drei binären Daten A (Multiplikand), B (Multiplikator) und N (Modulo), die in einer ganzen Zahl n von Bits kodiert sind, eine binäre Dateneinheit P(A, B)N zu erzeugen, die in n Bits kodiert ist, wie P(A, B)N = A B I mod N, wobei I ein Fehler des Montgomery-Verfahrens ist. Das Montgomery- Verfahren verwendet eine Rechenbasis aus k Bits und zerlegt die Worte aus n Bits in m Worte mit k Bits bei m k ≥ n > (m - 1) k. Das Montgomery-Verfahren läuft wie folgt ab, wobei i ein Index zwischen 0 und m - 1 ist:
• X - Si + Ai B,
• Y&sub0; = (X J&sub0;) mod 2k,
• Z = X + (N Y&sub0;)
• Si+1 = Z \ 2k, wobei \ eine ganze Division ist,
• wenn Si+1 größer als N ist, subtrahiert man also N von bei der nächsten Iteration,
• wobei Ai einem Wort aus k Bits der Zerlegung von A entspricht,
• Si einem aktualisierten Ergebnis der Pfield-Operation und Sm = (P(A, B)N = A B I mod N entspricht.
• Um eine modulare Multiplikation A B mod N durchzuführen, ist es notwendig, den Fehler I zu unterdrücken. Dieser Fehler I ist bekannt und beträgt 2-m k. Um ihn zu unterdrücken, führt man eine zweite Operation Pfield durch: P(Sm, H)N, wobei H eine binäre Dateneinheit ist, die in m Worte mit k Bits kodiert ist und den Wert 22m k mod N hat.
• Die Erzeugung eines Parameters H erfolgt üblicherweise durch sukzessive Subtraktion mit Hilfe eines mathematischen Coprozessors, wie er in der Schrift D2 beschrieben ist. Ein erstes Problem ist, daß es bei der Berechnung von H mit Hilfe eines Coprozessors erforderlich ist, daß der Prozessor Operationen mit Worten von m k Bits durchführen kann.
• Wenn man modulare Operationen durchführen möchte unter Verwendung von Operanden mit einer Größe, die über der liegt, für die der Coprozessor ausgelegt ist, wird man einen klassischen Prozessor mit 8, 16 oder 32 Bit verwenden, einen Speicher und einen Coprozessor, wobei der Coprozessor dazu dient, die Multiplikationen auszuführen. Es ist also nicht möglich, die Berechnung von H in dem Coprozessor durchzuführen. Die Berechnung von H muß daher im Prozessor durch sukzessive Subtraktionen erfolgen. Die klassischen Prozessoren sind nicht für diese Art von Operationen optimiert, sie erfordern einen relativ großen Speicherplatz, um den notwendigen Code abzuspeichern, und sie führen Operationen mit großen Zahlen sehr viel langsamer als ein spezieller Coprozessor durch. Die Erzeugung eines solchen Parameters ist daher nicht optimal.
• Die Erfindung schlägt ein Verfahren zur Berechnung einer Potenz von zwei vor, das sich auf alle möglichen Fälle bei der Berechnung von H anwenden läßt. Dieses Verfahren hat den Vorteil, daß die Berechnung von H bei großen Zahlen sehr viel schneller wird.
• Der Erfindung liegt daher als Aufgabe zugrunde, ein Verfahren zur Erzeugung eines Fehlerkorrekturparameters anzugeben, das in die Durchführung der Modulo-Berechnung durch integrierte Schaltkreise unter Verwendung des Montgomery- Verfahrens eingreift, wobei H der Fehlerkorrekturparameter wie H = 2(m+m") k mod N ist, wobei N eine ganze Zahl ist, die in m k Bits kodiert ist und deren Bit mit dem niedrigsten Gewicht nicht Null ist, wobei m" k in p Bits kodiert ist und H(i) ein aktualisierter Wert von H wie H(p-1) = H = 2(m+m") k mod N ist, wobei das Verfahren einen modulo-arithmetischen Coprozessor, einen Verarbeitungsprozessor und einen Speicher umfaßt, wobei das Verfahren die folgenden Schritte aufweist:
• - Erzeugen einer binären Dateneinheit mit dem Wert 2m k+1 mod N, genannt H(0), und Abspeichern dieser Dateneinheit in dem Speicher und/oder in einem Register des Coprozessors;
• - Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen 1 und p - 1 liegt, und die die folgenden Schritte umfaßt:
• -- Abarbeiten einer Operation Pfield(H(i-1), H(i-1)) unter Verwendung eines Multiplizierers des Coprozessors und Abspeichern des R(i) genannten Ergebnisses in dem Speicher oder in dem Register des Coprozessors,
• -- wenn das Bit mit dem Gewicht 2p-i-1 der Dateneinheit m k gleich 1 ist, dann Durchführen einer Operation Pfield(H(i-1), H(0)) unter Verwendung eines Multiplizierers des Coprozessors und Abspeichern des Ergebnisses H(i) in dem Speicher oder in dem Register des Coprozessors.
• Die Operationen Pfield sind Operationen, die bei großen Zahlen sehr viel Zeit in Anspruch nehmen. Jedoch ist es möglich, einen Coprozessor mit einer internen Taktfrequenz herzustellen, die über der eines klassischen Verarbeitungsprozessors liegt, womit bei den Pfield-Operationen Zeit gewonnen werden kann. Deswegen ist es unter bestimmten Bedingungen von Vorteil, das erfindungsgemäße Verfahren zur Berechnung von H heranzuziehen. Tatsächlich muß man bei einer Zahl, die in m k Bits kodiert ist, beim Stand der Technik maximal m" k Subtraktionen bzw. 2 log&sub2;(m" k) Pfield- Operationen bei der Erfindung durchführen. Je größer m" k ist, desto interessanter wird die Anwendung der Erfindung.
• Mehrere Fälle sind bei der Berechnung von H(0) möglich, so führt man wahlweise eine 2-Komplementierung von N oder eine Subtraktion von N von 0 durch, wobei 0 in m k Bits kodiert ist, um 2 mod N zu erhalten. Dann verschiebt man um eine Einheit nach links und führt eine Subtraktion zur Bestimmung von H(0) durch. Wenn darüber hinaus q Bits mit hohem Gewicht von N gleich 0 sind, muß man N um die Zahl von g Bits nach links verschieben, dann q + 1 sukzessive Subtraktionen kombiniert mit q + 1 Verschiebungen nach links um ein Bit durchführen, dann nach rechts um q Bits mit hohem Gewicht, die gleich 0 sind, verschieben. Die Subtraktionen können in dem Prozessor oder dem Coprozessor je nach Größe der zu bearbeitenden Zahlen erfolgen.
• Eine Verbesserung der Erfindung besteht darin, k m" in zwei ganze Zahlen u und v zu zerlegen, so daß u v = m" k gilt, wobei v in w Bits kodiert ist und das Verfahren dasjenige nach Anspruch 6 ist.
• Diese Verbesserung dient dazu, die Zahl an Iterationen zu verringern, die Pfield-Operationen verwenden, zugunsten einiger sukzessiver Subtraktionen, die bei der Berechnung weniger zeitaufwendig sind.
• Die Erfindung läßt sich besser verstehen und weitere Vorteile werden deutlich in der folgenden Beschreibung einer bevorzugten Ausführungsform, die lediglich als Beispiel ohne Einschränkung dient, wobei Bezug genommen wird auf die Zeichnungen, bei denen:
• - Figur 1 schematisch einen Coprozessor nach dem Stand der Technik darstellt, mit dem Modulo-Operationen auf Worten von m k Bits möglich sind,
• - Figur 2 schematisch einen Kryptographieschaltkreis darstellt, der Modulo-Operationen mit Worten der Größe m' k' Bits durchführt.
• Figur 1 zeigt einen Coprozessor 1 zur Durchführung von Modulo-Operationen.
• Er umfaßt:
• - drei Schieberegister 10, 11 und 12 mit seriellem Eingang und Ausgang. Diese Register umfassen jeweils die gleiche Anzahl n von Zellen, wobei n = m k gilt. Diese Register können unterteilbar sein, z.B. in Register mit n/2 Zellen und in Register von k Bits bei den Registern 10 und 12.
• - Multiplexer 13, 14 und 15, die jeweils vor den Registern 10, 11 und 12 angeordnet sind. Man wird ebenso Multiplexer hinter den Unterabschnitten der Register 10, 11 und 12 anordnen, wenn solche existieren.
• - Drei Register 16, 17 und 18, die jeweils k Zellen umfassen. Die Register 16 und 17 und 18 sind Register mit parallelem Ausgang und seriellem Eingang.
• - Zwei Multiplikationsschaltkreise 19 und 20, die jeweils einen seriellen Eingang, einen parallelen Eingang und einen seriellen Ausgang aufweisen. Der parallele Eingang des Multiplikationsschaltkreises 19 wird mit dem Ausgang des Registers 16 über eine Speicherkippstufe 21 mit k Zellen verbunden. Der parallele Eingang des Multiplikationsschaltkreises 20 ist mit einem der Ausgänge der Register 17 oder 18 über eine Speicherkippstufe 22 mit k Zellen verbunden. Diese Kippstufe 22 ist selbst mit einem der Ausgänge der Register 17 und 18 über einen Multiplexer mit zwei parallelen Eingängen und einem parallelen Ausgang verbunden.
• - Multiplexer 24, 25, 37, 26, 36 und 38;
• - einen Demultiplexer 39;
• - serielle Subtraktionsschaltkreise 27, 28 und 29;
• - serielle Additionsschaltkreise 30 und 31;
• - Verzögerungsschaltkreise 32, 33 und 34 zum Verzögern der Fortpflanzung binärer Daten um k Zyklen;
• - einen Schaltkreis 35 zum Speichern des Vergleichsergebnisses.
• Für weitere Einzelheiten sei auf die Schrift D2 verwiesen, insbesondere auf die Figuren 2 und 3 und auf die Abschnitte der Beschreibung, die sich darauf beziehen: Seite 15, Zeile 54 bis Seite 16, Zeile 13 und Seite 17, Zeile 50 bis Seite 18, Zeile 55.
• Der Coprozessor 1 kann Berechnungen mit Modulo-Operationen mit Zahlen von m k Bits durchführen, wie es in der Schrift D2 beschrieben ist. Es ist jedoch auch möglich, mit ihm klassische Multiplikationen A B mit Zahlen durchzuführen, die eine Größe bis zu m k Bits haben, indem man wie folgt vorgeht:
E1: Initialisierung:
• - Laden des Registers 17 k-mal mit 0,
• - Laden des Registers 10 mit B,
• - Laden der Register 11 und 12 mit m k-mal 0,
• - Laden des Registers 16 mit dem Wort A&sub0; mit k Bits von A,
• - Initialisierung des Multiplizierers 19,
• - Initialisierung der Additionsschaltkreise und Subtraktionsschaltkreise 28, 30, 31;
• E2: Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen l und m liegt:
• - Laden des Inhalts des Registers 16 in die Kippstufe 21,
• - Durchführen der Multiplikation von Ai-1 mit B und Addition des Inhalts des Registers 11 zu dem Produkt durch simultanes Verschieben der Register 10 und 11 nach rechts,
• - Speichern von k Bits mit niedrigem Gewicht des Ergebnisses in dem Register 12 durch Verschieben um k Bits nach rechts,
• - Speichern von m k Bits hohen Gewichts des Ergebnisses in dem Register 11,
• - Laden des Wortes Ai in das Register 16 während des Ablaufs der anderen Schritte.
• Am Ende eines solchen Verfahrens liegt dann das niedrige Gewicht des Ergebnisses in dem Register 12 und das hohe Gewicht des Ergebnisses in dem Register 11. Es ist für den Fachmann offensichtlich, daß ein Ausgangsanschluß am Register 12 vorgesehen werden muß, um das niedrige Gewicht des Ergebnisses ausgeben zu können.
• Es ist dem Fachmann außerdem klar, daß mit demselben Verfahren die Multiplikation einer Zahl B, die in m k Bits kodiert ist, mit einer Zahl A, die in m" k Bits kodiert ist, wobei m" irgendeine ganze Zahl ist, durchgeführt werden kann. Dazu arbeitet man die Schleife in Schritt E2 mit einem Index i zwischen 1 und m" ab. Alle m Iterationen gibt man den Inhalt des Registers 12 über einen Ausgangsanschluß aus.
• Es ist ebenso möglich, das Quadrat von Zahlen, die in m k Bits kodiert sind, mit Hilfe des Registers 10 ohne Laden des Registers 16 von außen durchzuführen. Tatsächlich reicht es, die für die folgende Iteration notwendigen k Bits während der Iteration zu dem Moment, wo die Bits des Registers 10 ausgegeben werden, in das Register 16 zu laden.
• Um Modulo-Berechnungen nach dem Montgomery-Verfahren durchzuführen, verwendet man den Aufbau nach Figur 2. Diese Figur 2 zeigt einen Kryptographieschaltkreis mit einem arithmetischen Coprozessor 1, einem Verarbeitungsprozessor 2, einem Speicher 3 und einem Kommunikationsbus 4, der die Verbindung der genannten Elemente 1, 2 und 3 herstellt. Der Speicher dient dazu, binäre Daten mit unterschiedlichen Formaten abzuspeichern. Der Verarbeitungsprozessor 2 dient dazu, den Austausch von Informationen zwischen dem Speicher 3, dem Coprozessor 1 und der Außenwelt des Kryptographieschaltkreises zu verwalten. Der Coprozessor 1 kann z.B. der gleiche wie der sein, der in Figur 1 gezeigt ist, wobei einige kleinere Modifikationen durchgeführt werden müssen, um die einfachen, oben beschriebenen Multiplikationen durchzuführen.
• Mit dem Kryptographieschaltkreis nach Fig. 2 ist es möglich, Operationen mit Worten durchzuführen, die in m' k' Bits kodiert sind, wobei k' gleich j k ist, j zwischen 1 und m liegt und m' irgendeine ganze Zahl ist, die durch die Größe des Speichers begrenzt wird, wobei die Größe durch den Fachmann festgelegt wird.
• In einem Beispiel wird bei dem für die Berechnung einer Operation Pfield(A, B)N = S verwendeten Algorithmus zurückgegriffen auf die folgenden Variablen:
• - A und B, die zwei ganze Zahlen sind, welche in n' Bits kodiert sind und in m' Worte von k' Bits zerlegt sind, welche mit A&sub0; bis Am'-1 und B&sub0; bis Bm'-1 bezeichnet werden,
• - N, welches eine ungerade ganze Zahl ist, die in n' Bits kodiert ist und in Form von m' Worten mit k' Bits dargestellt wird, die mit N&sub0; bis Nm'-1 bezeichnet werden,
• - S(i), welches eine ganze Zahl ist, die in (m' k') Bits kodiert ist und einen aktualisierten Wert des Ergebnisses während einer Iteration i darstellt,
• - X und Z, die zwei ganze Zahlen sind, welche in ((m' + 1) k') Bits kodiert sind,
• - Y&sub0;, welches eine ganze Zahl ist, die in k' Bits kodiert ist,
• - J&sub0;, welches eine ganze Zahl ist, die in k' Bits kodiert ist und bei welcher gilt ((J&sub0; N&sub0;) + 1) mod 2k' = 0.
• Der mathematische Algorithmus, welcher verwendet wird, ist der folgende:
• - Setzen von S(0) auf 0,
• - Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen 1 und m' liegt:
• B1: Berechnung von X = S(i-1) + (B Ai-1),
• B2: Berechnung von Y = (X J&sub0;) mod 2k', wo die Operation mod 2k' nur einem Abschneiden entspricht,
• B3: Berechnen von Z = X + (Y N),
• B4: Berechnen von S(i) = Z \ 2k', wobei das Symbol \ eine ganze Division bedeutet, es handelt sich dabei in der Tat um ein Abschneiden von k' Bits,
• B5: wenn S(i) größer als N ist, subtrahiert man N von S(i).
• - Man kann das Ergebnis S = S(m') = Pfield(A, B)N = A B 2-m' k' mod N holen.
• Selbstverständlich wird man, wenn k' m' ≤ k m gilt, vorzugsweise die Operationen Pfield innerhalb des Coprozessors in optimaler Art und Weise durchführen, indem man k' = k nimmt, wie es z.B. in der Schrift D2 beschrieben ist.
• Wenn man dagegen k' m' > k m hat, wird man die Operationen Pfield mit dem Verarbeitungsprozessor 2 durchführen, wobei die Multiplikationen mit Hilfe des Coprozessors 1 durchgeführt werden.
• Was auch immer die Größe k' m' der Operanden sei, so ist es notwendig, einen Fehlerkorrekturparameter H = 2 k' m' mod N zu erzeugen, wenn man eine Modulo-Multiplikation durchführen will, wobei A und B die Größe von N ist. Einen anderen Fall hat man, wenn je nach Ausführungsform eine Operation Pfield vorliegt, wenn A in k' ma Bits kodiert ist, B in k' mb Bits kodiert ist und N in k' m' Bits kodiert ist. Es ist möglich, Parameter H unterschiedlicher Formen zu haben, die sich je nach Optimierung der Modulo-Multiplikation ergeben. So kann man H = 2k' (ma+m') oder 2k' (mb+m') oder 2k' (ma+mb) haben. In der Tat läuft es darauf hinaus, daß man H = 2k' (m'+m") bei allen Fällen mit m" = ma oder mb oder ma + mb - m' hat. So definiert kann m" negativ sein, aber in der Praxis ist es immer positiv.
• In unserem Beispiel dient dieser Fehlerkorrekturparameter H dazu, den Fehler des Montgomery-Verfahrens mit dem Wert 2-m' k' zu unterdrücken. Um eine Multiplikation durchzuführen, führt man eine erste Operation Pfield mit den zwei Operanden der durchzuführenden Multiplikation durch und führt dann eine zweite Operation Pfield mit dem Ergebnis der ersten Operation Pfield und dem Fehlerkorrekturparameter H durch.
• Um den Korrekturparameter H zu erzeugen, wenn m' k' ≤ m k gilt, wird nach der Schrift D2 ein Verfahren von sukzessiven Subtraktionen verwendet, das vollständig in dem Coprozessor 1 durchgeführt werden kann.
• Wenn m' k' > m k gilt, kann daher die Berechnung von H nicht mehr vollständig in dem Coprozessor 1 durchgeführt werden. Wenn man ein Verfahren wünscht, das sukzessive Subtraktionen verwendet, muß dieses durch den Verarbeitungsprozessor 2 abgearbeitet werden, der ein Rechenprogramm verwendet. Ein solches Rechenprogramm beruht darauf, m" k' Iterationen durchzuführen, die jeweils im schlechtesten Fall der möglichen Berechnung aufweisen: eine Subtraktion in m' k' Bits, eine Verschiebung um ein Bit bei einem Wort von m' k' Bits und einen Vergleich von zwei Worten mit m' k' Bits. Somit ist die Rechenzeit für H proportional zu (m' k') (m" k').
• Um diese Dauer bei großen Operanden zu reduzieren, schlägt die Erfindung ein Rechenverfahren vor, das anders ist und anwendbar ist, was immer die Größe der Operanden sei. Das vorgeschlagene Verfahren ist insbesondere dann interessant, wenn m' k' und m" k' sehr groß wird.
• Das erfindungsgemäße Verfahren verwendet einen Schaltkreis, wie er in Figur 2 dargestellt ist. Dieses Verfahren macht die Kodierung von mit k' in p Bits notwendig und umfaßt die folgenden Schritte:
• - Erzeugung einer binären Dateneinheit mit dem Wert 2m' k'+1 mod N, genannt H(0), und Abspeichern dieser Dateneinheit in dem Speicher 3;
• - Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen l und p - 1 liegt, und die die folgenden Schritte umfaßt:
• -- Durchführen einer Operation Pfield(H(i-l), H(i-1)) und Abspeichern des R(i) genannten Ergebnisses,
• -- wenn das Bit mit dem Gewicht 2p-i-1 von m" k' gleich 1 ist, dann Durchführen einer Operation Pfield(H(i-1), H(0)) und Abspeichern des Ergebnisses H(i).
• Die oben abgearbeitete Schleife beruht darauf, eine Modulo- Potenzierung nach dem Montgomery-Verfahren und ohne Fehlerkorrektur von H(0) mit m" k' durchzuführen. Somit erfährt die Schleife log&sub2;(m" k') Iterationen (das Ergebnis wird abgeschnitten), wobei jede Iteration proportional zu m' k' ist. Selbstverständlich ist der Proportionalitätskoeffizient einer Iteration des Verfahrens größer als der Proportionalitätskoeffizient einer Iteration nach dem Stand der Technik.
• Was immer die Größe von m' k' sei, der Multiplizierer 19 des Coprozessors 1 wird bei Operationen Pfield damit befaßt werden. Die Ergebnisse R(i) und H(i) können in dem Speicher 3 abgelegt werden, aber es ist vorteilhaft, sie in dem Register 10 abzuspeichern, wenn m' k' ≤ m k gilt.
• Die binäre Dateneinheit H(0) wird in dem Speicher 3 abgelegt, wenn man jedoch dieses Verfahren bei Operanden verwendet, die kleiner als m k Bits sind, speichert man außerdem diese Dateneinheit in dem Register 10 des Coprozessors 1.
• Die Erzeugung dieser Dateneinheit H(0) = 2m' ki+1 mod N kann anders erfolgen bei dem Fall, der im folgenden dargestellt wird.
• Wenn bei N das Bit mit dem größten Gewicht gleich 1 ist, hat man zwei Möglichkeiten, um 2 zu erzeugen:
• - man bildet das 2-Komplement von N,
• - man führt die Operation 0 - N durch.
• Die zwei Möglichkeiten sind äquivalent, man bevorzugt jedoch die zweite Möglichkeit, wenn m' k' ≤ m k gilt, wobei diese Operation in dem Coprozessor 1 verdrahtet ist. Man muß die eine oder andere der Möglichkeiten je nach der Geschwindigkeit der Ausführung oder Aufwand bei der Implementierung gemäß den Einschränkungen, die dem Fachmann bei der Realisierung bekannt sind, auswählen.
• Danach erfolgt eine Verschiebung um eine Einheit nach links, gefolgt von einer Subtraktion von N, um H(0) zu erhalten.
• Wenn q Bits mit hohem Gewicht von N auf 0 sind, wird man die Berechnung von H(0) unter Bezug auf den vorangehenden Fall durchführen. Das heißt, man führt die folgenden Operationen durch:
• - Verschieben nach links um q Bits von N, wodurch sich N' ergibt, wobei die q Bits mit niedrigem Gewicht von N' gleich 0 sind;
• - Erzeugen einer Dateneinheit H'(0) durch Realisieren des 2-Komplements von N' (oder durch Subtraktion von N von 0);
• - Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen l und q liegt, die die folgenden Schritte umfaßt:
• -- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j) genannt wird,
• -- wenn H' (j) größer als N' ist, subtrahiert man N' von H'(j)
• - Verschieben von H'(q) um q Bits nach rechts, um H(0) zu erhalten.
• Es ist für den Fachmann selbstverständlich, daß die Verschiebungen nach links Multiplikationen mit einer Zweierpotenz entsprechen. Der Fachmann versteht außerdem, daß die Verschiebungen nach links fiktiv sein können, d.h., sie können erfolgen, indem Nullen am Bit mit niedrigem Gewicht anstelle der Dateneinheit geladen werden und so das Laden der Dateneinheit verschoben wird. Es ist außerdem möglich, daß die Subtraktion von N' von H'(j) seriell erfolgt, in diesem Fall entspricht das Verschieben nach links einem nicht durchgeführten Verschieben nach rechts.
• Wenn in der Praxis N in m' k' Bits kodiert ist, ist es selten, daß N mehr als 3 oder 4 Bits mit hohem Gewicht auf 0 hat. Bei großem m' k' schätzt man ab, daß die Berechnung von H(0) vernachlässigbar gegenüber einer Iteration der Schleife zur Berechnung von H unter Verwendung wenigstens einer Pfield-Operation ist. Somit geht man davon aus, daß die Erzeugung von H eine Dauer beansprucht, die proportional zu log&sub2;(m" k') (m' k') ist. Es ist für den Fachmann offensichtlich, daß die Berechnung von H bei Operanden, die in einer sehr großen Zahl von Bits kodiert sind, schneller erfolgt als mit einem Verfahren, das sukzessive Subtraktionen verwendet.
• Eine Verbesserung dieses Verfahrens besteht darin, m" k' in ein Produkt aus zwei Termen u v zu zerlegen, um u Iterationen durch sukzessive Subtraktionen und log&sub2;(v) Iterationen durch Potenzierung zu realisieren. Man führt dazu die folgenden Schritte durch, indem u und v als zwei ganze Zahlen gewählt werden, wie u v = m" k', und dabei v in w Bits kodiert wird:
• - Erzeugung einer binären Dateneinheit mit dem Wert 2m' k'+u mod N, genannt H(0), und Abspeichern dieser Dateneinheit;
• - Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen 1 und w - 1 liegt, und die die folgenden Schritte umfaßt:
• -- Abarbeiten einer Operation Pfield(H(i-1), H(i-1)) und Abspeichern des mit R(i) bezeichneten Ergebnisses,
• -- wenn das Bit mit dem Gewicht 2w-i-1 der Dateneinheit v gleich 1 ist, dann Abarbeiten einer Operation Pfield(H(i-1), H(0)) und Abspeichern des Ergebnisses H(i).
• Die Berechnung von H(0) mit dem Wert 2m' k'+u mod N wird durch die folgenden Schritte mit q Bits mit hohem Gewicht von N auf 0 durchgeführt:
• - Verschieben von N nach links um q Bits, wodurch sich N' ergibt, wobei die q Bits mit dem niedrigen Gewicht von N' gleich 0 sind;
• - Erzeugen einer Dateneinheit H'(0) durch Erzeugen des 2- Komplements von N' (oder durch Subtraktion von N von 0);
• - Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen l und q + u liegt, welche die folgenden Schritte umfaßt:
• -- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j) genannt wird,
• -- wenn H'(j) großer als N' ist, dann subtrahiert man N' von H'(j);
• - Verschieben von H'(q + u) um q Bits nach rechts, um H(0) zu erhalten.
• Selbstverständlich gilt in Analogie zu der Berechnung durch einfache Potenzierung, daß, wenn das Bit mit hohem Gewicht von N gleich 1 ist, die Schritte, die sich auf q Bits mit hohem Gewicht auf 0 beziehen, überflüssig sind.
• Vollständig in Analogie zu dem Verfahren der einfachen Potenzierung kann man für die Abspeicherung von Ergebnissen genausogut den Speicher wie das Register 10 verwenden. Desgleichen werden die Multiplikationen bei den Pfield-Operationen in dem Coprozessor durchgeführt.
• Eine solche Verbesserung reduziert einige Modulo-Potenzierungsiterationen zugunsten einiger sukzessiver Subtraktionsiterationen, die weniger aufwendig in bezug auf die Ausführungszeit sind.
• Als numerisches Beispiel mit den folgenden Werten k' = 512 = m k, m' = m" = 8 und q = 0 hat man in etwa die folgenden zeitlichen Ergebnisse:
• - Durch sukzessive Subtraktion in der Ordnung von 16 Miilionen Taktzyklen,
• - durch einfache Potenzierung in der Ordnung von 9 Millionen Taktzyklen,
• - durch Kombination der zwei Verfahren, indem man u = 8 nimmt, in der Ordnung von 7 Millionen Taktzyklen.
• Der Fachmann wird feststellen, daß es nicht immer wünschenswert ist, k' = k m zu wählen und daß es freisteht, die unterschiedlichen Parameter zu variieren, die im allgemeinen Prinzip der Erfindung wählbar sind.
• Die Erfindung erlaubt es, sehr große Zahlen zu verarbeiten, ohne dazu die Verarbeitungsschaltkreise zu vergrößern. In einer Chipkarte ist die Größe des integrierten Schaltkreises sehr niedrig. Nichtsdestotrotz müssen bei einigen Chipkarten große Speicher für unterschiedliche Funktionen vorgesehen werden. Die Erfindung kann daher einen Speicher verwenden, der mit anderen Elementen der Chipkarte geteilt wird. Die Lösung, die durch die Erfindung gegeben wird, ist daher insbesondere geeignet für die Implementierung bei Chipkarten.
• Da die Erfindung einen großen Speicher verwendet, ist es denkbar, daß dieser Speicher außerdem für andere Anwendungen verwendet wird.

Claims (8)

1. Verfahren zur Erzeugung eines Fehlerkorrekturparameters, das in die Durchführung von Modulo-Berechnungen durch integrierte Schaltkreise unter Verwendung des Montgomery-Verfahrens eingreift, wobei H der Fehlerkorrekturparameter wie H = 2(m+m") k mod N ist und N eine ganze Zahl ist, die in m k Bits kodiert ist und ihr Bit mit dem niedrigsten Gewicht nicht Null hat, m" k kodiert ist in p Bits und H(i) ein aktualisierter Wert von H wie H(p-1) = H = 2(m+m") k mod N ist, wobei das Verfahren einen modulo-arithmetischen Coprozessor (1), einen Verarbeitungsprozessor (2) und einen Speicher (3) verwendet, wobei das Verfahren die folgenden Schritte aufweist:

- Erzeugen einer binären Dateneinheit mit dem Wert 2m k+1 mod N, genannt H(0), und Abspeichern dieser Dateneinheit in dem Speicher (3) und/oder in einem Register (10) des Coprozessors (1);

- Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen 1 und p - 1 liegt, und die die folgenden Schritte umfaßt:

-- Abarbeiten einer Operation Pfield(H(i-1), H(i-1)) unter Verwendung eines Multiplizierers (19) des Coprozessors (1) und Abspeichern des R(i) genannten Ergebnisses in dem Speicher (3) oder in dem Register (10) des Coprozessors (1),

-- wenn das Bit mit dem Gewicht 2p-i-1 der Dateneinheit m k gleich 1 ist, dann Durchführen einer

Operation Pfield(H(i-1), H(0)) unter Verwendung eines Multiplizierers (19) des Coprozessors (1) und Abspeichern des Ergebnisses H(i) in dem Speicher (3) oder in dem Register (10) des Coprozessors (1).

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das Erzeugen einer binären Dateneinheit mit dem Wert 2m k+1 mod N die folgenden Schritte umfaßt:

- Initialisierung einer Dateneinheit, die in m k Bits kodiert ist, auf 0 in dem Speicher (3) oder in dem Register (10) des Coprozessors (1),

- Durchführen einer Subtraktion 0 - N in dem Verarbeitungsprozessor (2) oder in dem Coprozessor (1),

- Verschieben dieses ersten Resultats um ein Bit nach links,

- Subtraktion von N in dem Verarbeitungsprozessor (2) oder dem Coprozessor (1) von diesem verschobenen Ergebnis, wenn dieses größer als N ist, und

- Abspeichern von m k Bits niedrigen Gewichts von H(0) in dem Speicher (3) oder in dem Register (10) des Coprozessors (1).

3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das Erzeugen einer binären Dateneinheit mit dem Wert 2m k+1 mod N die folgenden Schritte umfaßt:

- Erzeugen des 2-Komplements von N,

- Verschieben dieses Komplements um ein Bit nach links,

- Subtraktion von N in dem Verarbeitungsprozessor (2) oder in dem Coprozessor (1) von diesem verschobenen Komplement, wenn dieses größer als N ist, und

- Abspeichern von m k Bits niedrigen Gewichts von H(0) in dem Speicher (3) oder in dem Register (10) des Coprozessors (1).

4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das Erzeugen einer binären Dateneinheit mit dem Wert 2m k+1 mod N erfolgt, wenn N q Bits mit dem höchsten Gewicht auf 0 hat:

- Initialisieren einer Dateneinheit auf 0, kodiert in m k Bits, in dem Speicher (3) oder in dem Register (10) des Coprozessors (1);

- Verschieben von N um q Bits nach links, wodurch sich N' ergibt, wobei die q Bits des niedrigen Gewichts nicht 0 sind;

- Ausführen einer Subtraktion 0 - N' in dem Verarbeitungsprozessor (2) oder in dem Coprozessor (1) und Abspeichern von m k Bits niedrigen Gewichts in H'(0);

- Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen 1 und q + 1 liegt, die die folgenden Schritte umfaßt:

-- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j) genannt wird,

-- wenn H'(j) größer als N' ist, dann wird N' von H'(j) in dem Verarbeitungsprozessor (2) oder in dem Coprozessor (1) abgezogen;

- Verschieben von H'(q + 1) um q Bits nach rechts, um H(0) zu erhalten.

5. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das Erzeugen der binären Dateneinheit mit dem Wert 2m k+1 mod N erfolgt, wenn N q Bits mit dem höchsten Gewicht auf 0 hat:

- Verschieben von N um q Bits nach links, wodurch sich N' ergibt, wobei die q Bits mit niedrigstem Gewicht nicht gleich 0 sind;

- Erzeugen einer Dateneinheit H'(0) durch Berechnen des 2-Komplements von N';

- Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen 1 und q + 1 liegt, die die folgenden Schritte umfaßt:

-- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j) genannt wird,

-- wenn H'(j) größer als N' ist, dann wird N' von H'(j) in dem Verarbeitungsprozessor (2) oder in dem Coprozessor (1) abgezogen;

- Verschieben von H'(q + 1) um q Bits nach rechts, um H(0) zu erhalten.

6. Verfahren zum Erzeugen eines Fehlerkorrekturparameters, das in die Durchführung von Modulo-Berechnungen durch integrierte Schaltkreise unter Verwendung des Montgomery-Verfahrens eingreift, wobei H der Fehlerkorrekturparameter wie H = 2(m+m") k mod N ist, wobei N eine ganze Zahl ist, die in m k Bits kodiert ist und deren Bit mit dem niedrigsten Gewicht nicht Null ist, bei welchem m" k = u v ist und u und v zwei ganze Zahlen sind, wobei v in w Bits kodiert ist und H(i) ein aktualisierter Wert von H wie H(w-1) = H = 2(m+m") k mod N ist, wobei das Verfahren einen modulo-arithmetischen Coprozessor (1), einen Verarbeitungsprozessor (2) und einen Speicher (3) verwendet, wobei das Verfahren die folgenden Schritte umfaßt:

- Erzeugen einer binären Dateneinheit mit dem Wert 2m k+u mod N, genannt H(0), und Abspeichern dieser Dateneinheit in dem Speicher (3) und/oder in einem Register (10) des Coprozessors (1);

- Abarbeiten einer Schleife, die mit einem Index i indiziert ist, wobei i zwischen 1 und w - 1 liegt, und die die folgenden Schritte umfaßt:

-- Abarbeiten einer Operation Pfield(H(i-1), H(i-1)) unter Verwendung eines Multiplizierers (19) des Coprozessors (1) und Abspeichern des R(i) genannten Ergebnisses in dem Speicher (3) oder in dem Register (10) des Coprozessors (1),

-- wenn das Bit mit dem Gewicht 2w-i-1 der Dateneinheit v gleich 1 ist, dann Ausführung einer Operation Pfield(H(i-1), H(0)) unter Verwendung eines Multiplizierers (19) des Coprozessors (1) und Abspeichern des Ergebnisses H(i) in dem Speicher (3) oder in dem Register (10) des Coprozessors (1).

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß das Erzeugen der binären Dateneinheit H(0) die folgenden Schritte umfaßt, wobei N' gleich N ist:

- Erzeugen einer Dateneinheit N' (0) durch Bestimmen des 2-Komplements von N' oder durch Subtraktion von N von in dem Prozessor (2) oder dem Coprozessor (1);

- Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen 1 und u liegt, die die folgenden Schritte umfaßt:

-- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j) genannt wird,

-- wenn H' (j) größer als N' ist, dann Subtraktion von N' von H'(j).

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß q Bits mit hohem Gewicht von N existieren, die nicht gleich 0 sind, und dadurch daß man die folgenden Schritte bei dem Erzeugen der binären Dateneinheit H(0) zu den bereits existierenden Schritten hinzufügt:

- Verschieben von N um q Bits nach links, wodurch sich N' ergibt, wobei die q Bits mit dem niedrigsten Gewicht von N' gleich 0 sind;

- Abarbeiten einer Schleife, die mit einem Index j indiziert ist, wobei j zwischen 1 und q liegt, die die folgenden Schritte umfaßt:

-- Verschieben um 1 Bit nach links, wobei das Ergebnis H'(j + u) genannt wird,

-- wenn H'(j + u) größer als N' ist, dann Subtraktion von N' von H'(j) in dem Prozessor (2) oder in dem Coprozessor (1);

- Verschieben von H'(q + u) um q Bits nach rechts, um H(0) zu erhalten.