PatentDe  


Dokumentenidentifikation DE102006025713A1 10.05.2007
Titel Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Rechenwerk, das kleiner ist als die Operanden
Anmelder Infineon Technologies AG, 81669 München, DE
Erfinder Fischer, Wieland, 80469 München, DE
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Anmeldedatum 01.06.2006
DE-Aktenzeichen 102006025713
Offenlegungstag 10.05.2007
Veröffentlichungstag im Patentblatt 10.05.2007
IPC-Hauptklasse G06F 7/52(2006.01)A, F, I, 20060601, B, H, DE
IPC-Nebenklasse G06F 7/72(2006.01)A, L, I, 20060601, B, H, DE   G06F 17/10(2006.01)A, L, I, 20060601, B, H, DE   
Zusammenfassung Zum Berechnen eines Ergebnisses einer modularen Multiplikation mit langen Operanden wird zumindest der Multiplikand in wenigstens drei kürzere Abschnitte aufgeteilt. Unter Verwendung der drei kürzeren Abschnitte des Multiplikanden, des Multiplikators und des Moduls wird eine modulare Multiplikation innerhalb einer kryptographischen Berechnung durchgeführt, wobei die Abschnitte des Multiplikanden, des Multiplikators und des Moduls Parameter der kryptographischen Berechnung sind. Die Berechnung wird sequentiell unter Verwendung der Abschnitte des Multiplikanden und unter Verwendung eines bei einer vorherigen Berechnung erhaltenen Zwischenergebnisses durchgeführt, bis alle Abschnitte des Multiplikanden abgearbeitet sind, um das Endergebnis der modularen Multiplikation zu erhalten.

Beschreibung[de]

Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Rechenwerk, das kleiner ist als die Operanden

Die vorliegende Erfindung bezieht sich auf Rechenwerke zum Berechnen einer modularen Multiplikation, deren verarbeitbare Wortbreite geringer ist als eine Wortbreite der Eingabe-Zahl oder des Moduls, wobei solche Anforderungen insbesondere bei kryptographischen Anwendungen auftreten.

Die modulare Multiplikation ist eine zentrale Operation, die in einer modularen Exponentiation eingesetzt wird, wie sie üblicherweise in der Kryptographie benutzt wird. So wird, wie es in 2a gezeigt ist, in der Public-Key-Kryptographie, also in der asymmetrischen Kryptographie, wie beispielsweise beim RSA-Verfahren, ein Schlüsselpaar erzeugt. Das Schlüsselpaar besteht aus einem öffentlichen Schlüssel e und einem privaten Schlüssel d. Der private Schlüssel ist nur einer Entität bekannt. Der öffentliche Schlüssel dient dieser Entität wird jedoch einer anderen Entität bereitgestellt, die z. B. verschlüsselte Daten zu der einen Entität schicken möchte, der der private Schlüssel gehört. Wie es in 2a gezeigt wird, findet eine Verschlüsselung einer unverschlüsselten Nachricht M in eine verschlüsselte Nachricht C dadurch statt, dass eine sogenannte modulare Exponentiation berechnet wird, bei der also die Nachricht mit dem öffentlichen Schlüssel potenziert wird, um dann bezüglich des Moduls N, der ebenfalls öffentlich bekannt ist, eine modulare Reduktion durchzuführen. Zur Entschlüsselung wird dieselbe Operation durchgeführt, nun jedoch mit dem privaten Schlüssel als Exponent, so dass die eine Entität, der der private Schlüssel gehört, und von der der öffentliche Schlüssel ursprünglich an die andere Entität verbreitet worden ist, wieder die Klartext-Nachricht M erhält.

Diese Public-Key-Verfahren können auch als Signatur/Verifikationsverfahren eingesetzt werden. Eine digitale Signatur erzeugt eine Entität dadurch, dass die zu signierende Nachricht M mit dem privaten Schlüssel dieser Entität verschlüsselt wird, um die Signatur S zu erzeugen, wie es ebenfalls in 2a dargestellt ist. Die Verifikation findet dann dadurch statt, dass die verifizierende Entität die Signatur mit dem öffentlichen Schlüssel e der signierenden Entität einer modularen Exponentiation unterzieht, um dann eine Klartextnachricht M zu erhalten, die mit der Klartextnachricht M verglichen werden kann, der die Signatur beigefügt ist. Stimmt die bei der Verifikation erhaltene Klartextnachricht mit der Klartextnachricht überein, der die Signatur beigefügt ist, so kann davon ausgegangen werden, dass das signierte Dokument authentisch ist.

Wie es bereits ausgeführt worden ist, wird eine kryptographische Berechnung, die eine modulare Exponentiation umfasst, wie es in 2b dargestellt ist, in mehrere modulare Multiplikationen zerlegt. So wird es üblicherweise bevorzugt, eine modulare Exponentiation zu berechnen, indem modulare Multiplikationen aufeinander folgend angewendet werden. Insbesondere aufgrund der erhöhten Sicherheitsanforderungen an den RSA-Algorithmus besteht ein Interesse dahingehend, dass eine modulare Multiplikation mit einer Breite von 2.048 Bits, also mit Schlüssellängen bzw. Modullängen von 2.048 Bits ausgeführt wird.

Generell stellen bei einer modularen Multiplikation im Rahmen einer kryptographischen Berechnung sowohl der Multiplikator A als auch der Multiplikand B sowie der Modul N Parameter der kryptographischen Berechnung dar, da von diesen Parametern die Endergebnisse wie Klartextnachricht, verschlüsselte Nachricht, Signatur etc. abhängen.

Wie es bereits ausgeführt worden ist, besteht ein Interesse dahingehend, die Schlüssellängen der Public-Key-Kryptographie stetig zu erhöhen, da damit sogenannte Brute-Force-Attacken mit immer schnelleren Prozessoren nach wie vor abgefangen werden können. So ist der Aufwand einer Brute-Force-Attacke mit der Schlüssellänge korreliert, so dass immer längere Schlüssel auch immer aufwendigere Brute-Force-Attacken bedingen, die mit derzeit verfügbaren Rechnern derart lang brauchen, dass ein kryptographischer Algorithmus als sicher betrachtet werden kann. Problematisch an immer größer werdenden Schlüssellängen ist jedoch, dass die Schlüssellänge, die ein Kryptocoprozessor in einer Chipkarte oder einem Computer (beispielsweise in einem TPM-Modul) hat, durch das Langzahlrechenwerk, das in diesem Kryptocoprozessor enthalten ist, begrenzt ist. Ein solches Langzahlrechenwerk ist beispielsweise in 4c gezeigt, wo eine sogenannte Bit-Slice-Struktur eines Langzahlrechenwerks dargestellt ist.

Bei dem in 4c gezeigten Ausführungsbeispiel umfasst jede Bit-Slice eine arithmetische Einheit, die beispielsweise ein Ein-Bit-Volladdierer sein kann, der einen Übertrag von einer niedrigeren Bit-Slice erhalten kann, und der einen Übertrag an eine höhere Bit-Slice ausgeben kann. Ferner ist einer solchen Bit-Slice wenigstens ein Register zugeordnet. Es wird jedoch bevorzugt, eine bestimmte Anzahl von Registern zuzuordnen, wie beispielsweise zwei oder noch besser z. B. fünf Register. Bei einem derzeit existierenden Kryptocoprozessor mit einer Bit-Slice-Anzahl von 1.408 Slices umfasst eine Bit-Slice fünf Register, nämlich das Register Z, das Register C, das Register N, das Register CR0 und das Register CR4, wie es in 4a im linken Teilbild angedeutet ist. Dann arbeitet dieser Prozessor im Langmodus. Mit dieser Anzahl von Bit-Slices ist der Prozessor gut geeignet, um RSA-Berechnungen mit Schlüssellängen von 1.024 Bits durchzuführen, da für eine Berechnung mit 1.024 Bits Schlüssellänge ein Rechenwerk, das ebenfalls nur 1.024 Bit-Slices hätte, nicht ganz ausreichen würde. So können in dem Rechenwerk mit 1.408 Bit-Slices auch etwas längere Schlüssellängen berechnet werden, es sollten jedoch immer etwas mehr Bit-Slices als Schlüsselbits vorhanden sein, um bestimmte Overflow- oder Underflow-Situationen abfangen zu können.

Das Rechenwerk 40, das in 4b gezeigt ist, kann durch eine Steuerung 41 mit Daten bzw. Ablaufsequenzen versorgt bzw. gesteuert werden. Ferner ist eine Registerkonfigurationseinrichtung 42 vorhanden, die die Register des Rechenwerks, also die fünf Register im Langmodus bei diesem Ausführungsbeispiel, auf zehn Register im Kurzmodus konfigurieren kann. Aus jedem Lang-Modus-Register einer bestimmten Länge werden somit bei diesem Ausführungsbeispiel zwei kurze Register der jeweils halben Länge, so dass zwei N-Register, zwei C-Register, zwei Z-Register und ein CR0-Register, ein CR2-Register, ein CR4-Register und ein CR6-Register entstehen. Nach wie vor hat jede Bit-Slice eine arithmetische Einheit, nämlich z. B. einen Ein-Bit-Volladdierer, der nun jedoch im Gegensatz zu der Situation in 4c, die den Lang-Modus darstellt, die verdoppelte Anzahl von Registern im Kurz-Modus hat.

Wenn der Kryptocoprozessor mit 1.408 Bits nun RSA-Schlüssellängen von z. B. 2.048 Bits berechnen soll, so wird dies nicht mehr ohne weiteres gehen, da zu wenig Bit-Slices vorhanden sind.

Daraus wird ersichtlich, dass eine Erhöhung der Schlüssellängen zwar von der Sicherheit her sehr wünschenswert ist, dass jedoch mit jeder Erhöhung der Schlüssellängen bereits existierende Coprozessoren nicht mehr ohne weiteres verwendungsfähig sind. Es müssten daher immer neue längere Rechenwerke entwickelt werden, was Entwicklungszeit und Kosten in Anspruch nimmt.

Um dies zu umgehen, wurden Methoden entwickelt, mit denen man auf kleineren Rechenwerken größere Zahlen verarbeiten kann. So existieren allgemein Verfahren zur Aufdopplung eines Rechenwerks in Software. Ein solches Verfahren ist beispielsweise die Berechnung der modularen Multiplikation unter Verwendung des chinesischen Restsatzes (CRT), wie er im Abschnitt 14.5 auf den Seiten 610–613 des „Handbook of Applied Cryptography", A. Menezes, P. van Oorschot, S. Vanstone, 1996, beschrieben ist. Allgemein wird unter Verwendung des chinesischen Restsatzes eine modulare Exponentiation mit einem langen Modul in zwei modulare Exponentiationen mit einem kurzen Modul aufgesplittet, wobei diese Ergebnisse dann zusammengefasst werden. Damit kann ein Rechenwerk gewissermaßen „softwaremäßig" aufgedoppelt werden.

Dieses Konzept ermöglicht jedoch nur die Aufdopplung, was für Situationen ungünstig ist, bei denen nicht unbedingt eine Aufdopplung der Schlüssellängen benötigt wird, sondern bei denen Schlüssellängen benutzt werden sollen, die vielleicht nur 50 % größer sind als die architektonische Rechenwerkslänge, also die Anzahl von Bit-Slices. Benutzt man solche 100 %-Aufdopplungsalgorithmen, so wird das Rechenwerk dann, wenn nur vielleicht um 50 % größere Schlüssellängen verarbeitet werden sollen, jeweils nur zu (100 + 50) %/2 = 75 % benutzt. Prinzipiell werden somit Hardware-Ressourcen verschenkt.

Zusätzlich zu der CRT-Aufdopplungsmethode existieren auch weitere Rechenwerk-Aufdopplungsalgorithmen, wie beispielsweise die Montgomery-Multiplikation, eine Multiplikation mit Karatsuba-Offman und nachfolgende Reduktion mittels beispielsweise der Barrett-Reduktion oder die Aufdopplungsmethode unter Verwendung der MultModDiv-Operation, wie sie beispielsweise in dem deutschen Patent DE 10219158 B4 dargestellt ist.

Wenn beispielsweise 4d betrachtet wird, so ist ein Rechenwerk für eine 1.024-Bit-Schlüssellänge bei 43 angedeutet. Eine Software-Aufdopplung unter Verwendung z. B. des chinesischen Restsatzes oder unter Verwendung einer der vorher genannten weiteren Methoden ist dann, wenn 2.048 Bits benötigt werden, wie es im Block 44 in 4d dargestellt ist, sinnvoll. So wird das ganze Rechenwerk ausgenutzt, es bleiben also keine unbenutzten Bit-Slices zurück. Soll jedoch eine Schlüssellänge mit z. B. 1.536 Bits genügen, so wird eine Software-Aufdopplung unter Verwendung z. B. des chinesischen Restsatzes (CRT) dazu führen, dass 2 × 768 Bits benötigt werden. Die restlichen 2 × 256 Bits würden in diesem Fall unbenutzt bleiben.

Im Stand der Technik fehlt somit ein alternatives Rechenwerk-Erweiterungskonzept, durch das flexiblere Schlüssellängen und damit eine flexiblere Rechenwerksausnutzung erreicht werden können.

Die vorliegende Erfindung betrifft unter anderem eine Vorrichtung zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Multiplikator, einem Multiplikanden und einem Modul, mit einer Einrichtung zum Bereitstellen des Multiplikanden in wenigstens drei Abschnitten, wobei jeder Abschnitt eine Anzahl von Stellen aufweist, die kleiner als eine halbe Anzahl von Stellen des Multiplikanden ist, und wobei die wenigstens drei Abschnitte sämtliche Stellen des Multiplikanden umfassen; und einer Einrichtung zum sequentiellen Berechnen, wobei die Einrichtung zum sequentiellen Berechnen ausgebildet ist, um unter Verwendung einer MultModAdd-(MMA-)Operation mit einem höherwertigen Abschnitts des Multiplikanden als Operanden ein erstes Zwischenergebnis zu berechnen, um unter Verwendung einer MultModAdd-(MMA-)Operation mit einem niedrigerwertigen Abschnitt des Multiplikanden und dem ersten Zwischenergebnis als Operanden ein zweites Zwischenergebnis zu berechnen, und um unter Verwendung einer MultModAdd-(MMA-)Operation mit einem noch niedrigerwertigen Abschnitts des Multiplikanden und dem zweiten Zwischenergebnis ein drittes Zwischenergebnis zu berechnen und zu speichern, wobei das dritte Zwischenergebnis das Ergebnis der modularen Multiplikation darstellt, wenn der Multiplikand in genau drei Abschnitte aufgeteilt ist, oder wobei das Ergebnis der modularen Multiplikation von dem dritten Zwischenergebnis durch eine weitere sequentielle Berechnung ableitbar ist, wenn der Multiplikand in mehr als drei Abschnitte aufgeteilt ist.

Nachfolgend wird Bezug nehmend auf die beiliegenden Zeichnungen eine detaillierte Beschreibung der bevorzugten Ausführungsbeispiele der vorliegenden Erfindung gegeben. Es zeigen:

1a eine schematische Darstellung der Vorrichtung zum Berechnen eines Ergebnisses einer modularen Multiplikation gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung;

1b eine Registerdarstellung der Operanden A, B, N von 1a und der Aufteilung der Operanden in Abschnitte;

1c eine schematische Darstellung der Funktionalität der erfindungsgemäßen Vorrichtung zum Zusammenfassen der Zwischenergebnisse;

1d eine Darstellung der modularen Multiplikationsoperation;

1e eine Darstellung der modularen Multiplikation mit Addition;

1f eine schematische Darstellung der Multiplikation mit Addition;

1g eine schematische Darstellung der Reduktionsoperation;

1h eine schematische Darstellung der sequentiellen Berechnung der Zwischenergebnisse;

2a eine allgemeine Darstellung des Einsatzgebiets der modularen Exponentiation;

2b eine schematische Darstellung der Zerlegung einer modularen Exponentiation in modulare Multiplikationen;

2c eine schematische Darstellung der Multiplikationsoperation;

2d eine spezielle Darstellung der erfindungsgemäßen MultAdd-Operation;

2e eine spezielle Darstellung der MultModAdd-Operation;

2f eine spezielle Darstellung der modularen Multiplikationsoperation;

2g eine schematische Darstellung der MultModDiv-Operation, die bei der vorliegenden Erfindung sequentiell verwendet wird;

3a eine allgemeine Darstellung der erfindungsgemäßen MultAdd-Operation;

3b eine Basisversion der Reduktionsoperation;

3c eine erste bevorzugte Version der Reduktionsoperation;

3d eine zweite bevorzugte Version der Reduktionsoperation;

3e eine dritte bevorzugte Version der Reduktionsoperation;

3f eine vierte bevorzugte Version der Reduktionsoperation;

4a eine Darstellung der Registersituation eines Rechenwerks im Lang-Modus und im Kurz-Modus;

4b eine schematische Darstellung eines konfigurierbaren Rechenwerks;

4c eine schematische Darstellung einer Bit-Slice-Struktur eines Rechenwerks;

4d eine schematische Darstellung der verschiedenen Möglichkeiten der Software-Aufdopplung im Vergleich zur erfindungsgemäßen Software-Erweiterung durch drei oder mehr Aufsplittungen;

4e ein tabellarischer Vergleich verschiedener Algorithmen;

5 ein Ablaufdiagramm der erfindungsgemäßen Berechnung zur Erläuterung der erfindungsgemäßen Vorrichtung und des erfindungsgemäßen Verfahrens;

6a eine bevorzugte Implementierung des modularen Multiplikationsalgorithmus;

6b eine bevorzugte Registerimplementierung des Algorithmus von 6a;

7a eine bevorzugte Implementierung der MMA-Operation;

7b eine alternative Implementierung der MMA-Operation;

7c eine Registerimplementierung der MMA-Operation;

8a eine bevorzugte Implementierung der MMA-Operation;

8b eine bevorzugte Registerimplementierung der MMA-Operation von 8a;

8c eine schematische Darstellung der Eingangs- und Ausgangsoperanden bei der vorliegenden Erfindung;

8d ein schematisches Blockschaltbild des Verfahrens und der Vorrichtung der vorliegenden Erfindung;

8e ein Rechenbeispiel für die vorliegende Erfindung, das die Registerbelegung der kurzen Hilfs- und Ergebnis-Register für jeden Zwischenschritt darstellt;

9a eine bevorzugte Implementierung der TC-Operation (TC = treat carry);

9b eine bevorzugte Implementierung der TB-Operation (TB = treat borrow);

9c eine bevorzugte Implementierung der Reduktionsoperation;

9d eine bevorzugte Implementierung auf Registerebene der Reduktionsoperation von 9c;

10a eine Darstellung der MMD-Operation;

10b eine bevorzugte Registerimplementierung der MMD-Operation;

11a eine Implementierung der MMD-Operation;

11b eine Registerimplementierung der MMD-Operation von 11a;

12 eine Registerimplementierung der Berechnung (Estimation) von &egr; bzw. e;

13a eine Implementierung einer Transformationsvorschrift für den Modul;

13b eine Implementierung der DIV-Operation;

13c eine schematische Darstellung eines Reduktionsalgorithmus für die abschließende Reduktion;

14 ein Rechenwerk mit einer maximal verarbeitbaren Zahl und einem zugeordneten Vorzeichenbit;

15 ein Blockschaltbild bzw. Ablaufdiagramm der Vorrichtung bzw. des Verfahrens zum Berechnen eines Ergebnisses einer Summe;

16 eine Zuordnung der Vorgehensweise zu der in den 8 und 9 beschriebenen modularen Multiplikation;

17a ein Rechenbeispiel;

17b ein Vergleichsbeispiel, das mit erheblichem Zeit/Komplexitäts-Nachteil berechenbar ist;

18 ein Rechenwerk, wie es bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung eingesetzt wird;

19a eine bevorzugte Implementierung der Einrichtung 184 zum Schätzen von 18 gemäß dem Algorithmus von 3d3f;

19b eine bevorzugte Implementierung der Einrichtung 184 zum Schätzen von 18 gemäß dem Algorithmus von 9c;

20a eine bevorzugte Implementierung der Einrichtung zum Berechnen von 18 gemäß dem Algorithmus von 3d3f;

20b eine bevorzugte Implementierung der Einrichtung zum Berechnen von 18 gemäß dem Algorithmus von 9c; und

21 eine bevorzugte Implementierung der Einrichtung zum Durchführen der Subtraktion von 20 gemäß dem Algorithmus von 9c.

Erfindungsgemäß wird wenigstens der Multiplikand in zumindest drei Abschnitte aufgeteilt wird, wobei jeder Abschnitt eine Anzahl von Stellen aufweist, die kleiner als eine halbe Anzahl von Stellen ist, wobei die wenigstens drei Abschnitte des Multiplikanden sämtliche Stellen des Multiplikanden umfassen. Ferner wird eine Einrichtung zum sequentiellen Berechnen vorgesehen, um sequentiell für jeden Abschnitt des Multiplikanden mit einer MMA-Operation ein Zwischenergebnis zu berechnen, und um dann unter Verwendung dieser Zwischenergebnisse ein Ergebnis der modularen Multiplikation zu erhalten.

Durch Aufsplittung des Multiplikanden in wenigstens drei Abschnitte kann vorzugsweise ein teilbares Rechenwerk verwendet werden, bei dem der Multiplikand und vorzugsweise auch der Multiplikator und der Modul in drei oder mehr Teile aufgeteilt wird, so dass jedes Drittel der Zahl in der Hälfte des Coprozessors Platz hat. Somit kann auch das Rechenwerk selbst zur vollen Länge ausgenutzt werden, und es werden keine Hardware-Ressourcen verschwendet.

Bei bevorzugten Ausführungsbeispielen findet eine Teilung sämtlicher Register des Rechenwerks statt, und zwar in Register gleicher Länge, und werden ferner sämtliche Operanden, also sowohl der Multiplikator als auch der Multiplikand als auch der Modul in ebenfalls drei oder mehr Teile aufgeteilt, so dass am Ende zur Berechnung der (langen) modularen Multiplikation lediglich logische und arithmetische Operationen benötigt werden, die mit Zahlen stattfinden, deren Länge, also deren Anzahl von Stellen, höchstens gleich der Anzahl von Stellen eines Abschnitts der Zahlen ist. Vorzugsweise wird, um eine optimale Ausnutzung eines Rechenwerks zu erhalten, der Abschnitt, in den eine Zahl aufgeteilt wird, also die Anzahl von Bit-Slices des Rechenwerks, das diese Operationen mit einer kleineren Anzahl von Stellen durchführen muss, derart gewählt, dass sie der Hälfte des teilbaren Rechenwerks entsprechen.

Bei einem weiteren bevorzugten Ausführungsbeispiel wird ein Rechenverfahren unter Verwendung der MultModDiv-Operation eingesetzt, bei der niemals mehr als zehn kurze Register des Rechenwerks verwendet werden, wobei zwei kurze Register des Rechenwerks im Kurz-Modus einem Register des Rechenwerks im Lang-Modus entsprechen.

Vorzugsweise wird im erfindungsgemäßen Rechenwerk und speziell bei der Reduktion im Rahmen der MMA-Operation das Ergebnis einer ganzzahligen Division der Eingabe-Zahl durch den Modul, auf deren Basis dann die modulare Reduktion durchgeführt wird, abgeschätzt, indem nicht die gesamte Zahl und der gesamte Modul verwendet werden, sondern nur ein höchstwertiger Abschnitt der Zahl und ein höchstwertiger Abschnitt des Moduls. Ferner wird zum Schätzen des Ergebnisses der ganzzahligen Division auch die Aufteilungszahl verwendet, auf deren Basis die höchstwertigen Abschnitte der Zahl und des Moduls festgelegt werden. Dieses geschätzte Ergebnis, das eine kurze Zahl ist, kann dann ohne weiteres in einem Register des Rechenwerks gespeichert werden und muss nicht gesondert behandelt werden. Das Reduktionsergebnis an sich wird dann basierend auf dem geschätzten Ergebnis und einer Subtraktion des Produkts aus dem Modul und einem Wert, der von dem geschätzten Ergebnis abgeleitet ist, von der Eingabe-Zahl ermittelt. Erfindungsgemäß wird also zur Reduktion zunächst der Reduktionsalgorithmus verwendet, der nicht einen Modul nach dem anderen subtrahiert und immer nach einer Subtraktion nachsieht, ob die Restklasse erreicht ist. Stattdessen wird unter Verwendung der höchstwertigen Abschnitte des Moduls und der Zahl gewissermaßen die Anzahl der Subtraktionen abgeschätzt, um dann auf der Basis einer Subtraktion des Produkts aus dem Modul und der geschätzten Anzahl das Reduktionsergebnis zu erhalten.

So hat sich herausgestellt, dass das Schätzergebnis der ganzzahligen Division, das nicht auf der Basis der gesamten Zahl und des gesamten Moduls durchgeführt wird, sondern nur auf der Basis eines höchstwertigen Abschnitts der Zahl und eines höchstwertigen Abschnitts des Moduls durchgeführt wird, bereits sehr nahe an dem exakten Ergebnis der ganzzahligen Division liegt, so dass bereits durch diese Maßnahme die Geschwindigkeit der modularen Reduktion erheblich erhöht werden kann, im Vergleich zu dem Fall, in dem immer einmal der Modul subtrahiert wird, und dann wieder zu überprüfen, ob dies ausreichend war oder nicht. Erfindungsgemäß wird damit auch die Sicherheit des Rechenwerks erheblich erhöht, da insbesondere dann, wenn die Einrichtung zum Berechnen des Reduktionsergebnisses das Ergebnis der Subtraktion wieder Schritt für Schritt verarbeitet, nur noch wenige Schritte erforderlich sind oder vielleicht sogar kein einziger Schritt erforderlich ist, um den beim Schätzen aufgetretenen Fehler „wieder gut zu machen".

So wird es jedoch bevorzugt, auch den Schätzfehler selbst abzuschätzen, und zwar so, dass der verbleibende Fehler, also die Diskrepanz zwischen dem geschätzten Fehler und dem tatsächlichen Fehler, höchstens gleich 1 oder gleich –1 ist.

Dies führt dazu, dass dann, wenn die Subtraktion unter Verwendung des geschätzten Ergebnisses und des geschätzten Schätzfehlers durchgeführt wird, immer nur lediglich eine einzige Endreduktion erforderlich ist, also eine Untersuchung dahingehend, ob die Ergebniszahl negativ ist, wobei dann ein Modul zu addieren wäre, oder ob die Zahl, die bei der Subtraktion erhalten wird, größer als der Modul ist, um dann den Modul einmal zu subtrahieren.

Bei einem weiteren bevorzugten Ausführungsbeispiel wird diese Subtraktion in mehrere einzelne MMD-Operationen, die entsprechenden Subtraktionsvorgängen vorausgehen, zerlegt, so dass sämtliche Berechnungen mit Zahlen durchgeführt werden, deren Wortbreite kleiner als die Breite des Moduls ist, und deren Wortbreite insbesondere gleich ist und bei einem bevorzugten Ausführungsbeispiel gleich einem Drittel der gesamten Wortbreite des Moduls ist. Insbesondere wird auch der Modul in einzelne Abschnitte aufgeteilt. Dies führt dazu, dass dann, wenn von einem Rechenwerk ausgegangen wird, das eine bestimmte maximale Wortlänge hat, effizient eine modulare Reduktion mit Zahlen durchgeführt werden kann, die das k-fache der Länge haben. Insbesondere wird es bevorzugt, mit einem Rechenwerk einer bestimmten Wortbreite Zahlen zu verarbeiten, die das 1,5-fache der Wortbreite des Rechenwerks selbst haben. Dies führt dazu, dass dann, wenn das Rechenwerk jeweils aufgeteilt wird, die Wortbreite der Zahl, die in Abschnitte aufgeteilt wird, gleich dem Dreifachen einer Einzel-Wortbreite des aufgeteilten Rechenwerks ist.

Selbstverständlich könnte jedoch auch dann, wenn eine genügend große Anzahl von Registern vorhanden ist, eine Zahlenmenge verarbeitet werden, die Zahlen aufweist, die nicht nur das 1,5-fache der Rechenwerks-Registerlänge betragen, sondern sogar gleich dem Dreifachen der Rechenwerks-Registerlänge sind. Die vorliegende Erfindung kann jedoch auch genauso auf noch höhere Zahlenlängen, also beispielsweise auch auf Zahlen, die das Vier- oder Fünffache der Rechenwerks-Registerlänge betragen, angewendet werden, wobei jedoch dann eine entsprechend größere Anzahl von Registern erforderlich ist, da die Anzahl von erforderlichen Registern mit dem Verhältnis zwischen der Länge der zu verarbeitenden Zahlen und der Länge der vom Rechenwerk zur Verfügung gestellten Einzelregister ansteigt.

Bei bevorzugten Ausführungsbeispielen wird in der MMA-Operation oder allgemein in einem Rechenwerk, in dem maximal Zahlen verarbeitet werden können, deren Betrag kleiner oder gleich einem Produkt aus einem Modul und einer Ganzzahl ist, die größer als 1 ist, dann, wenn eine Summe zweier Operanden bezüglich eines Moduls zu berechnen ist, und wenn ein Operand der beiden Operanden kleiner als der Modul ist, dieser Operand negativ gemacht, und zwar so, dass der modifizierte Operand gleich dem nicht-modifizierten Operanden weniger dem Modul ist. Dann wird eine Summe des einen Operanden mit dem modifizierten Operanden immer noch kleiner als die maximal verarbeitbare Zahl sein, obgleich die Summe der beiden Operanden ohne die Modul-Subtraktion, um einen Operanden negativ zu machen, eine Zahl ergeben hätte, die größer als die maximal verarbeitbare Zahl des Rechenwerks gewesen wäre.

Das Ergebnis der Summenberechnung gemäß der Erfindung ist somit nach wie vor innerhalb des erlaubten Zahlenbereichs. Dieses Ergebnis trägt allerdings einen Fehler im Vergleich zu der Zahl, die oberhalb der zu verarbeitenden Zahl ist.

Diese Fehler wird erfindungsgemäße jedoch dann eliminiert, wenn dieses Ergebnis modular reduziert wird, und zwar bezüglich des Moduls, der vorher vom Operanden abgezogen worden ist, um den modifizierten Operanden zu erreichen.

Die erfindungsgemäße Vorrichtung ist besonders dahingehend vorteilhaft, dass nunmehr in einem Rechenwerk, das ausgebildet ist, um negative und positive Zahlen zu verarbeiten, das also ein Vorzeichenbit verarbeitet, dann immer noch keine Überlauf-Abwehrmaßnahmen benötigt werden, selbst wenn die Summe der beiden zu berechnenden Operanden zu einem Zwischenergebnis führen würde, das größer als die maximal verarbeitbare Zahl des Rechenwerks ist.

Damit ist das erfindungsgemäße Rechenwerk schneller, und flexibler und insofern auch weniger fehleranfällig, da kein Überlauf erzeugt wird, und somit auch keine Überlauf-Handhabungsmaßnahmen erforderlich sind, die bereits per se das Rechenwerk erheblich verlangsamen. Erfindungsgemäß können somit auch komplexere Rechnungen, bei denen eine Summe und eine anschließende Reduktion der Summe benötigt wird, ausgerechnet werden, wobei immer nur Zwischenergebnisse auftreten, die kleiner als die maximal verarbeitbare Zahl sind, da die Summe, vor ihrer abschließenden Reduktion immer kleiner als die maximal verarbeitbare Zahl ist, da ein Summand negativ gemacht wird, während der andere Summand positiv ist. Vorzugsweise wird die Summe somit immer in eine Differenz transformiert, wobei der Differenzpartner durch Modulsubtraktion erhalten wird und der dabei eingeführte Fehler wird in der abschließenden modulare Reduktion bezüglich dieses Moduls wieder eliminiert.

Der einzige zusätzliche Schritt, der benötigt wird, ist, dass der zweite Operand negativ gemacht wird, und zwar durch Subtrahieren des Moduls von seinem eigentlichen Wert ohne diese Maßnahme. Dieser zusätzliche Schritt erfordert jedoch lediglich eine einfache Subtraktion des Moduls, findet somit allein auf arithmetischer Seite statt und bedingt keine Ausnahmehandhabungs- oder Überlauf-Handhabungsroutine. Damit wird keine Verlangsamung erreicht, was nicht wünschenswert ist.

Besonders bevorzugt wird es, wenn die erfindungsgemäße Reduktion um ein N „zu viel" in eine größere Reduktion eingebettet oder integriert ist, bei der reduziert wird, indem ein Vielfaches von N subtrahiert wird. In diesem Fall braucht das Vielfache einfach um Eins inkrementiert werden, wobei die anschließende Subtraktion dann unter Berücksichtigung des inkrementierten Vielfachen stattfindet.

Das Konzept ist ferner dahingehend vorteilhaft, da der Zwischenschritt des „Negativ-Machens" des zweiten Operanden unabhängig davon ausführbar ist, ob das Ergebnis der Summe der beiden Operanden tatsächlich oberhalb der maximal verarbeitbaren Zahl liegt oder nicht. Stattdessen wird es bevorzugt, unabhängig von den Werten des ersten und des zweiten Operanden vorzugehen, so dass kein werte-abhängiges Stormprofil der Schaltung nach außen hin sichtbar ist. Damit kann auch durch eine Seitenkanalattacke z. B. mittels einer Differential Power Analysis nicht ermittelt werden, ob ein Zwischenergebnis oberhalb der maximal verarbeitbaren Zahl ist oder nicht, da unabhängig davon, ob das Zwischenergebnis tatsächlich größer oder kleiner als die maximal verarbeitbare Zahl ist, immer dieselbe Schrittfolge und damit im Wesentlichen derselbe Leistungsverbrauch und damit auch im Wesentlichen derselbe Zeitverbrauch bzw. dasselbe Leistungs-/Zeitprofil von der Schaltung ausgegeben wird.

In diesem Zusammenhang sei darauf hingewiesen, dass die vorliegende Erfindung besonders für Langzahlrechenwerke geeignet ist, da diese Rechenwerke ohnehin schon für Operanden mit Längen (deutlich) oberhalb 300 Bits ausgelegt sind. Andererseits führen steigende Anforderungen an kryptographische Sicherheiten und insbesondere auch immens zunehmende Rechenleistungen, die mehr und mehr Brute-Force-Attacken immer durchführbarer werden lassen, zu immer längeren Schlüsseln und damit immer längeren Operanden bzw. zu verarbeitenden Zahlen. Jede Maßnahme, mit der Berechnungen durchgeführt werden können, obgleich die Zwischenergebnisse bereits „zu groß" für das Rechenwerk werden, sind also hochwillkommen, da diese Maßnahmen insgesamt insbesondere aufgrund des reduzierten Hardwareaufwands bei gleicher Sicherheit, also bei gleicher Schlüssellänge zu einem günstigeren Produkt führen. Speziell im Bereich von Chipkarten, welchen ein Massenprodukt sind, bei denen es um Cent-Beträge geht, wenn ein Produkt auf dem Markt überleben soll, sind die Anforderungen an Chipfläche (Hardwareaufwand), Sicherheitsfeatures und Preis besonders eng. Darüber hinaus spielen auch Zeitaspekte eine Rolle, da ein Kunde dann, wenn er sich mit seiner Chipkarte irgendwo authentifiziert, eigentlich nicht gewillt ist, lange zu warten. Diese Erwartung hält den Kunden jedoch nicht davon ab, von seiner Chipkarte einen maximalen Sicherheitsstandard zu erreichen.

Genau in diesem Spannungsfeld liegen die Vorteile der vorliegenden Erfindung, die nämlich eine maximale Sicherheit aufgrund der Zulässigkeit von eigentlich zu großen Zwischenergebnissen bei gleichzeitiger schneller Ausführung einer kryptographischen Berechnung liefert, da keine Überlauf-Maßnahmen gefahren werden, die ansonsten den Betrieb der Chipkarte erheblich verlangsamen würden.

Insbesondere wird bei der vorliegenden Erfindung, um die modulare Multiplikation zu berechen, die gesamte Aufgabe in drei sequentiell durchzuführende Multiplikations-Modul-Additions-Operationen aufgeteilt, wobei für jede dieser einzelnen Operationen ein anderer Abschnitt des Multiplikanden B verwendet wird. Jede solche Multiplikations-Modul-Additions-Operation wird wiederum in eine Multiplikations-Additions-Operation und eine anschließende Reduktions-Operation aufgeteilt, wobei in der Multiplikations-Additions-Operation immer der gerade betrachtete Abschnitt des Multiplikanden B verwendet wird und in einzelnen Iterationsschritten entsprechende Abschnitte des aus dem vorhergehenden Schritt vorliegenden Zwischenergebnisses C und des Multiplikators A eingesetzt werden.

So wird nunmehr diese Multiplikations-Additions-Operation in mehrere MultModDiv-Operationen aufgeteilt also in modulare Multiplikationen, die jeweils den ganzzahligen Quotienten, also das DIV-Ergebnis, und den Rest, also das MOD-Ergebnis, liefern. Sowohl das DIV-Ergebnis als auch das MOD-Ergebnis sind kurze Zahlen, die in kurzen Registern abgespeichert werden können. Die kurzen Register, in denen Ergebnisse der MMD-Operation abgespeichert werden, werden auch als Hilfsregister bezeichnet, da sie im Verlauf der iterativen Abarbeitung der Multiplikations-Additions-Operation mehrmals beschrieben werden. In anderen Worten ausgedrückt, werden die Ergebnisse einer MMD-Operation nur für die nachfolgende Aktualisierungsoperation benötigt, in der sukzessive ein Stück der Ergebniszahl, nämlich ein Abschnitt der Ergebniszahl, der in ein kurzes Register passt, berechnet wird. Insbesondere wird beim Aktualisieren das Ergebnis der vorherigen MMD-Operation unter Verwendung einer Addition von Abschnitten des dritten Operanden C, also des Zwischenergebnisses eines vorherigen Schritts, aktualisiert.

So liefert jeder Aktualisierungsschritt zwei Einträge in ein Ergebnisregister, wobei der höherwertige Eintrag in das Ergebnisregister bereits ein nicht mehr verändertes Endergebnis darstellt, während der niederwertige Eintrag der zwei erhaltenen Ergebnisse je nach vorliegender Zahlensituation durch ein Ergebnis eines Aktualisierungsschritts noch verändert wird.

Für die vorliegende Erfindung wird somit für eine Multiplikations-Additions-Operation nur ein Rechenwerk benötigt, das eine Wortbreite gleich der Länge nur eines Abschnitts und nicht der ganzen Länge eines Operanden ist, das also eine kurze Wortbreite hat. Anders ausgedrückt benötigt ein solches Rechenwerk nur innere Register der kurzen Länge und nicht der langen Länge. Darüber hinaus werden lediglich bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung lediglich zwei Hilfsregister und – für eine Aufteilung in drei Abschnitte – vier kurze Ergebnisregister benötigt. Die Multiplikations-Additions-Operation kann somit mit lediglich sechs kurzen Registern berechnet werden. In diesem Fall ist das Rechenwerk ein Bit-Slice-Stapel, wobei jeder Bit-Slice ein Volladdiererfunktion hat, also einen Übertrag von einem niedrigerem Bit-Slice erhält und einen Übertrag an einen höheren Bit-Slice weitergibt, wobei sich „höher" und „niedriger" auf die Wertigkeit der verarbeiteten Binärstellen bezieht. Wenn lediglich ein Rechenwerk mit sechs internen Registern zur Verfügung steht, so muss das Rechenwerk in der Lage sein, von einem äußeren Speicher noch die zusätzlichen Operanden zu erhalten, nämlich die Abschnitte des Zwischenergebnisses aus einem vorherigen Iterationsschritt und die benötigten Abschnitte des Multiplikators A und gegebenenfalls den aktuellen Abschnitt des Multiplikanden B.

Beim bevorzugten Ausführungsbeispiel der vorliegenden Erfindung genügt zur Berechnung der Multiplikations-Additions-Operation eine Anzahl von 10 oder 12 kurzen Registern, die durch Halbierung von fünf oder sechs langen Registern erhalten werden können, wobei ferner eine Arbeitsspeicher, der typischerweise „XDATA" genannt wird, zur Verfügung steht, in dem weitere Abschnitte gespeichert sind. Auf diesen Arbeitsspeicher muss jedoch in jedem Zyklus nur im Hinblick auf einen einzigen Abschnitt eines einzigen Operanden zugegriffen werden, so dass effizient und mit einer geringen Anzahl von Arbeitsspeicherzugriffen, aber mit einer maximalen Ausnutzung der inneren Register gearbeitet werden kann. Es sei darauf hingewiesen, dass das Konzept des Berechnens des Ergebnisses einer Multiplikations-Additions-Operation nicht nur im Rahmen einer modularen Multiplikation eingesetzt werden kann, sondern überall dort, wo unter Verwendung eines Prozessors, der nur kurze Wortlängen aufgrund seiner Konstruktion erlaubt, eine Multiplikations-Additions-Operation berechnet werden soll, die lange Operanden umfasst, also Operanden, die eine Wortlänge haben, die durch das Rechenwerk in einem Schlag nicht verarbeitet werden können.

Bevor detailliert anhand den 1 bis 13c auf die bevorzugte Verwendung des Konzepts im Rahmen der effizienten Berechnung einer modularen Multiplikation mit einem eigentlich zu kleinen Rechenwerk eingegangen wird, wird zunächst anhand der 14 bis 17b die vorliegende Erfindung dargestellt, wie sie auch in einem Rechenwerk einsetzbar ist, bei dem keine Aufteilung der Operanden stattfindet. Auch in einem solchen Rechenwerk, das z. B. Register bzw. eine Anzahl von Bit-Slices aufweist, die gleich den Stellen der maximal verarbeitbaren Zahl ist, bei der also keine Operandenaufteilung stattfindet, wird das Konzept ebenfalls zu einem Performance-Vorteil führen. Die bevorzugte Anwendung liegt jedoch in einer Vorrichtung bzw. einem Verfahren bzw. einem Computer-Programm, welche zum Berechnen der modularen Multiplikation einsetzbar sind, wobei eine Registeraufteilung stattfindet, derart, dass mit einem zu kurzen Rechenwerk lange Operanden und damit kryptographische Schlüssellängen berechnet werden können.

14 zeigt ein solches Rechenwerk 1400, das z. B. ein binäres Rechenwerk ist, wie es z. B. noch Bezug nehmend auf 4b dargestellt wird. Das Rechenwerk ist definiert durch eine maximal verarbeitbare Zahl, die im binären Fall typischerweise +/– 2n – 1 ist. Diese maximal verarbeitbare Zahl kann auch durch ein Produkt aus dem Modul N und einer Zahl Z dargestellt werden, wobei die Zahl Z eine Ganzzahl größer als 1 ist und bei bevorzugten Ausführungsbeispielen der vorliegenden Erfindung, die später noch beschrieben werden, dazu verwendet wird, um eine Aufteilung einer langen Zahl in mehrere kurze Zahlen zu erreichen.

Die Eigenschaft des Rechenwerks, nur Zahlen kleiner oder gleich einer maximal verarbeitbaren Zahl zu verarbeiten, wird in 14 durch ein beispielhaftes langes Register 1402 dargestellt, das beispielhaft als MSB ein Vorzeichen-Bit aufweist, das in gesetzten Zustand z. B. eine negative Zahl anzeigt, während es im ungesetzten Zustand eine positive Zahl anzeigt. Die Stellen der Zahl sind durch Stellen 1, 2, 3, 4, ..., n in 14 symbolisiert. Alternativ könnte das Rechenwerk jedoch auch z. B. ein Dezimalrechenwerk sein, in dem die Stellen genau den Stellen des Dezimalsystems entsprechen würden, wobei dann beide Berechnungen der maximal verarbeitbaren Zahl als Basis der Exponentiation nicht mehr die Zahl „2" sonder die Zahl „10" zu nehmen ist.

Nachdem das MSB bzw. die höchste Stelle der maximal verarbeitbaren Zahl ein Vorzeichenbit ist, umfasst das Rechenwerk auch eine Einrichtung 1404 zum Interpretieren des höchstwertigen Bits (MSB) bzw. die höchstwertige Stelle der maximal verarbeitbaren Zahl als Vorzeichen-Bit und nicht als „Werte-bit".

Wie es später noch dargestellt wird, kann das Rechenwerk ein solches langes Register umfassen. Das lange Register kann jedoch auch durch verschiedene kurze Register implementiert sein, wobei wieder das höchstwertige Bit des kurzen Registers, das den höchstwertigen Abschnitt bzw. die höchstwertige „Teilzahl" speichert, wiederum als Vorzeichenbit interpretiert wird. Im Hinblick auf die später noch dargestellte Aufteilung der Zahlen in Operanden würde dieser höchstwertige Abschnitt z. B. dem Abschnitt A2, B2 bzw. N2 eines Operanden A, eines Operanden B und eines Moduls N entsprechen.

Da eine lange Zahl nur ein einziges Vorzeichen hat, wird für die beiden restlichen Abschnitte, also z. B. A1, A0 bzw. B1 oder B0 kein eigenes Vorzeichenbit benötigt.

15 zeigt ein schematisches Blockschaltbild einer Vorrichtung bzw. eines Verfahrens zum Berechnen eines Ergebnisses, das bei 1500 erhalten wird, unter Verwendung einer Summe aus einem ersten Operanden X, der bei einer Einrichtung 1502 gespeichert wird, und eines zweiten Operanden Y, der von einer Einrichtung 1504 bereitstellbar ist. Bei dem in 5 gezeigten Ausführungsbeispiel ist der zweite Operand Y kleiner als der Modul N. Ferner wird die gesamte Berechnung der Summe modular durchgeführt, also es wird das Ergebnis der Summe bezogen auf die durch N definierte Restklasse gesucht, wie es bei 1506 in 15 dargestellt ist.

Wie es bereits anhand von 14 ausgeführt worden ist, ist das Rechenwerk 1400, das die in 15 gezeigten Elemente umfasst, ausgebildet, um Maximalzahlen zu verarbeiten, deren Betrag kleiner oder gleich einem Produkt aus dem Modul N und der Ganzzahl Z ist, die größer als 1 ist.

Insbesondere umfasst das Rechenwerk 1400 von 14 bzw. das in 15 dargestellte Rechenwerk die Einrichtung 1502 zu Speichern des ersten Operanden X in dem Rechenwerk, wobei ein Betrag des ersten Operanden kleiner oder gleich der maximal speicherbaren Zahl ist. Es wird darauf hingewiesen, dass dann, wenn der erste Operand X größer als die maximal speicherbare Zahl ist, eine Speicherung ohnehin nicht ohne spezielle weitere Maßnahmen möglich sein würde. Insbesondere wird bei dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung ferner davon ausgegangen, dass X positiv ist und kleiner als die maximal speicherbare Zahl ist, wie es rechts bezüglich des Blocks 1502 in 15 dargestellt ist. Für andere Alternativen kann der erste Operand X jedoch auch negativ werden, solange er einen Betrag hat, der kleiner als N mal Z ist, also die maximal speicherbare Zahl.

Die Vorrichtung umfasst ferner eine Einrichtung 1508 zum Berechnen eines modifizierten zweiten Operanden Y', wobei der modifizierte zweite Operand gleich den zweiten Operanden minus dem Modul N ist, so dass der modifizierte zweite Operand negativ ist. Eine spezielle integrierte Verwendung innerhalb der modularen Multiplikation dieser „Modulsubtraktion von einem bereits reduzierten Wert ist insbesondere in 1d oder in 9c bei „Red'" dargestellt und wird später noch näher erläutert.

Die Einrichtung 1508 sowie die Einrichtung 1502 speisen eine Einrichtung 1510 zum Berechnen einer Summe des ersten Operanden und des modifizierten zweiten Operanden oder des ersten Operanden und eines Produkts aus dem zweiten Operanden mal einem Faktor, der kleiner oder gleich der Ganzzahl Z ist. Das Ergebnis der Einrichtung 1510 zum Berechnen ist somit größer oder gleich dem Produkt aus dem Modul und der Ganzzahl und mit Sicherheit kleiner als das Produkt aus dem Modul und der Ganzzahl. Das Ergebnis der Summenberechnungseinrichtung 1510 ist somit nach wie vor noch innerhalb des erlaubten Bereichs, also kleiner als die maximal verarbeitbare Zahl trotz der Tatsache, dass die Summe des ersten Operanden X und des nicht-modifizierten zweiten Operanden Y eigentlich größer als die maximal verarbeitbare Zahl geworden wäre, nämlich im vorliegenden Fall größer oder gleich N, Z.

Die berechnete Summe wird schließlich einer Einrichtung 1512 zugeführt, die eine modulare Reduktion der Summe bezüglich des Moduls durchführt, um das Ergebnis 1500 zu erhalten, das wiederum größer oder gleich Null und auf jeden Fall kleiner als der Modul N ist, und das insbesondere im Vergleich zum Ausgangswert des Blocks 1508 nunmehr wieder positiv ist.

Anders ausgedrückt wird somit der durch die Einrichtung 1508 eingeführte Fehler aufgrund der weiteren Subtraktion eines Moduls von dem eigentlich bereits reduzierten zweiten Operanden durch die modulare Reduktion im Schritt 1512 wieder eliminiert. Dieser kleine Umweg zur Berechnung des modifizierten Operanden ermöglicht nunmehr jedoch, dass die Berechnung, wie sie in 15 dargestellt worden ist, auch ausgeführt werden kann, obgleich Zwischenergebnisse erreicht werden, die größer als die maximal verarbeitbare Zahl sind, wie es noch anhand eines Vergleichs von 17a und 17b dargelegt wird.

Lediglich beispielhaft ist in 17a und 17b eine Berechnung gezeigt, bei der die beiden Operanden X gleich 95 und Y gleich 7 bezüglich dem Modul N gleich 10 modular reduziert werden sollen. Die maximal verarbeitbare Zahl des Rechenwerks beträgt N mal Z. Anders ausgedrückt kann das Rechenwerk somit Zahlen zwischen –99 und +99 verarbeiten.

Die einfache Summe aus X + Y ergibt jedoch bereits 102, wobei die Zahl 102 nicht mehr verarbeitbar ist und zu einer Überlaufhandhabungsroutine bzw. sogar zu einem Fehler führen würde.

Es wird von dem zweiten Operanden Y der Modul subtrahiert, so dass aus der Zahl 7 eine negative Zahl –3 wird. Die Summe aus –3 und 95 ergibt nunmehr die Zahl 92, die ohne weiteres eine verarbeitbare Zahl ist. Die modulare Reduktion der Zahl 92 ergibt jedoch das gleiche Ergebnis wie die modulare Reduktion der nicht mehr verarbeitbaren Zahl 102, so dass der durch den Modulsubtraktionsschritt eingeführte Fehler am Ende aufgrund der modularen Reduktion wieder eliminiert wird.

An dieser Stelle sei ferner darauf hingewiesen, dass der zweite Operand Y = 7 bereits das Ergebnis einer vorausgehenden modularen Reduktion gewesen ist, dass dieser Wert also bereits in der Restklasse ist und daher eigentlich nicht noch einmal zu reduzieren bzw. einer Subtraktion des Moduls zu unterziehen ist. Allerdings würde ein Nicht-Ausführen der Subtraktion des Moduls von dem zweiten Operanden Y dazu führen, dass, wie im Vergleichsbeispiel, das Rechenwerk das Ergebnis der Summe aus dem ersten Operanden und dem zweiten Operanden bezüglich des Moduls nicht mehr berechnen kann.

Wie es bereits ausgeführt worden ist, wird die rechenwerkseffiziente Summenberechnung im Rahmen einer modularen Multiplikation ausgeführt, wie sie in 1d dargestellt ist. Insbesondere stellt die Berechnung zum Berechnen des Ergebnisses der Summe aus dem ersten und dem zweiten Operanden bezüglich eines Moduls die MMAZ-Operation für den zweiten Abschnitt des Operanden B1 und für den ersten Abschnitt B0 dieses Operanden dar, wie es auch an der „Korrespondenz" in 16 dargestellt ist. Das Ergebnis der Einrichtung 1512 zum Reduzieren der Summe bezüglich des Moduls N, das am Ausgang 1500 von 15 erhalten wird, entspricht somit dem Wert E + N in 7b, da durch die Reduktion Red'Z(D; N) die weitere Subtraktion des Moduls im Schritt 1508 bereits ausgeführt worden ist.

Die Einrichtung 1508 von 15 entspricht somit der Funktionalität zum Berechnen des Werts C des zweiten MMAZ-Schritts in 1d bzw. die Funktionalität des Schritts MMA'Z in 7b, wobei Red'Z ausgeführt wird, um den modifizierten zweiten Operanden E in 7b das Ergebnis des zweiten MMAZ-Schritts zu erhalten. Dann wird im letzten Schritt MMAZ die Summe aus D gemäß 7a berechnet, um dann durch die Reduktion im Block 1512 von 15 die Funktionalität RedZ D–N von 7a durchzuführen, um schließlich das Ergebnis C der modulare Multiplikation von 1d zu erhalten.

Nachfolgend wird auf eine bevorzugte Einbettung bzw. Implementierung des bevorzugten Konzepts, um Zwischenergebnisse unterhalb der maximal zu verarbeitenden Zahl zu halten, in Verbindung mit den 1a bis 13c besprochen, welche eine bevorzugte Implementierung der modularen Multiplikation mit einem Rechenwerk zeigt, das Register hat, die kürzer als die Operandenlänge sind.

1a zeigt eine schematische Darstellung einer erfindungsgemäßen Vorrichtung zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Multiplikator A, einem Multiplikanden B und einem Modul N. Ursprünglich sind der Multiplikator A, der Multiplikand B und der Modul jeweils Zahlen, die sich von einer niederstwertigen Stelle (im Binärfall dem LSB) zu einer höchstwertigen Stelle (im Binärfall dem MSB) erstrecken. Die Operanden A, B, N haben eine Länge kleiner oder gleich einer gewissen Anzahl von Bits, wie beispielsweise 1.536 Bits bei dem in 4d beschriebenen Szenario im Block 46.

Jeder Abschnitt des Multiplikanden B, der durch eine Einrichtung 10 zum Bereitstellen der Abschnitte geliefert wird, hat bei dem in 1b gezeigten Ausführungsbeispiel eine Länge von 512 Bits, also eine Länge gleich einem Drittel der ursprünglichen Länge des Multiplikanden B. Damit sind alle Abschnitte gleich lang. Die Zahl B kann dann so geschrieben werden, wie sie in 1b dargestellt ist. Die Zahl Z stellt die „Registerverschiebungszahl" oder den entsprechenden Multiplikator dar, der an den zweiten bzw. in quadrierter Form an den dritten Abschnitt zu multiplizieren ist, um die Zahl B aus den Abschnitten B0, B1, B2 wieder zusammenzusetzen. i bedeutet direkt die Anzahl von Stellen bzw. Anzahl von Bits, die ein Abschnitt hat. Es sei darauf hingewiesen, dass das in 1b gezeigte Ausführungsbeispiel für eine gleichmäßige Aufteilung einer Zahl in drei Abschnitte beispielhaft ist. Erfindungsgemäß können jedoch auch mehr als drei Abschnitte und vorzugsweise eine ungerade Anzahl von Abschnitten erzeugt werden, und können auch Abschnitte erzeugt werden, die ungleiche Längen haben, dass also z. B. der erste Abschnitt etwas kürzer als ein Drittel und der zweite Abschnitt dafür etwas länger als ein Drittel etc. ist. Es werden jedoch im Hinblick auf eine optimale Anpassung der Aufteilung in Abschnitte durch die Einrichtung 10 von 1a an das Rechenwerk gleich lange Abschnitte bevorzugt.

Die Abschnitte einer Zahl können somit die Zahl direkt darstellen, so dass die Abschnitte direkt die Stellen der Zahl haben und die Zahl ergeben, wenn sie gewissermaßen ausgeschnitten und zusammengestückelt werden. Alternativ und manchmal sogar bevorzugt wird die Zahl aus den Abschnitten unter Verwendung der Aufteilungszahl Z berechnet, so dass auch hier die Abschnitte die Zahl darstellen, die Darstellung aber nicht über ein direktes Zusammenstückeln erfolgt sondern über eine Berechnung mit der Aufteilungszahl Z, wie es in 1b unter „allgemein" angedeutet ist.

Die Einrichtung 10 zum Bereitstellen des Multiplikanden in wenigstens zwei Abschnitten empfängt somit eingangsseitig die Zahl B und liefert ausgangsseitig die drei oder mehr Abschnitte B0, B1, B2, wobei jeder Abschnitt eine Anzahl von Stellen aufweist, die kleiner als eine halbe Anzahl von Stellen ist, und wobei Einrichtung 10 zum Bereitstellen ferner ausgewählt ist, um die Abschnittsaufteilung so durchzuführen, dass die erzeugten Abschnitte zusammengenommen sämtliche Stellen des Multiplikanden umfassen.

Die Einrichtung 10 liefert die Abschnitte zu einer Einrichtung 12 zum sequentiellen Berechnen einer Sequenz von Schritten. Insbesondere ist die Einrichtung 12 zum sequentiellen Berechnen einer Sequenz von Schritten ausgebildet, um zur Verwendung eines höherwertigen Abschnitts des Multiplikanden ein erstes Zwischenergebnis zu berechnen, wie es in 1h bei 14 dargestellt ist. Dieses erste Zwischenergebnis wird dann dazu verwendet, um ebenfalls unter Verwendung eines niedrigerwertigen Abschnitts B1 ein zweites Zwischenergebnis zu berechnen. Dieses zweite Zwischenergebnis wird dann unter Verwendung eines wieder niedrigerwertigen Abschnitts B0 des Multiplikanden dazu verwendet, um ein drittes Zwischenergebnis zu berechnen. Das dritte Zwischenergebnis kann bereits das Ergebnis der modularen Multiplikation sein, wenn nur drei Abschnitte für den Multiplikanden verwendet worden sind. Das dritte Zwischenergebnis kann dann gemäß dem Prozedere, das in 1h gezeigt worden ist, weiter verarbeitet werden, wenn weitere Abschnittsaufteilungen vorgenommen worden sind, um dann schließlich das Endergebnis der modularen Multiplikation zu erhalten.

Obgleich bei bevorzugten Ausführungsbeispielen die Einrichtung 10 zum Bereitstellen ausgebildet ist, um nicht nur den Multiplikanden, sondern auch den Multiplikator und den Modul in einzelne Abschnitte bereitzustellen, bringt bereits das in 1a gezeigte Ausführungsbeispiel, bei dem lediglich ein Operand der Multiplikation aufgeteilt wird, einen Vorteil dahingehend, dass für den Multiplikanden selbst kein langes Register benötigt wird, sondern dass dort ein kurzes Register ausreicht, da aufgrund der sequentiellen Berechnungsnatur der Einrichtung 12 nie der gesamte Multiplikand benötigt wird, sondern immer nur ein Abschnitt des Multiplikanden.

Für Rechenwerke in Bit-Slice-Architektur wird jedoch, wie es nachfolgend noch dargelegt wird, eine Aufteilung in Abschnitte sämtlicher Operanden und des Moduls bevorzugt, um nur Register verwenden zu müssen, die die gleiche (kurze) Länge haben. In diesem Zusammenhang wird auch eine Aufteilung sämtlicher Parameter der modularen Multiplikation in gleich lange Abschnitte bevorzugt, da die beste Rechenwerksausnutzung erreicht wird, wenn gleich lange (kurze) Register eingesetzt werden.

Erfindungsgemäß wird es bevorzugt, dass ein Rechenwerk zum Durchführen der modularen Multiplikation eingesetzt wird, das wenigstens ein Register hat, das eine Länge hat, die kleiner als eine Länge des Multiplikanden ist, die aber größer oder gleich einem Abschnitt des Multiplikanden ist, wobei die Einrichtung zum Berechnen ausgebildet ist, um sequentiell einen Abschnitt des Multiplikanden in das Register zu laden oder von dem Register zu lesen.

Bei einem weiteren bevorzugten Ausführungsbeispiel wird eine Aufteilung der Zahlen in genau drei Abschnitte vorgenommen, und wird ein Rechenwerk verwendet, das in einem Kurz-Modus betrieben wird, das also in zwei Rechenwerkshälften aufgeteilt wird, in denen die drei Abschnitte der jeweiligen Zahlen verarbeitet werden.

Nachfolgend wird ein bevorzugtes Ausführungsbeispiel der vorliegenden Erfindung gegeben, bei dem eine 2.048-Bit-Multiplikation implementiert wird. Zunächst wird jedoch eine Übersicht über bestimmte verwendete Notationen und Operationen gegeben. Grundsätzlich geht es um die Berechnung der modularen Multiplikation, wie sie in 2f dargestellt ist.

  • • #N ist definiert, die Bitlänge von N zu sein, d. h. falls n = #N, dann N ∊ [2n-1, 2n[.
  • • A mod N bezeichnet den üblichen Rest von A modulo N, d. h. A mod N ∊ [0, N[.
  • • A mod 'N bezeichnet den negativen Rest von A modulo N, d. h. A mod'N ∊ ]–N, 0], d.h. A mod' N = A mod N – N, falls A mod N > 0 ist.
  • • Es werden mehrere Notationen für Ganzzahlen verwendet: Es sei Z ≥ 2 irgendeine Ganzzahl, dann wird für die Ganzzahl N ≥ 0 N = (N2|N1|N0)Z geschrieben, wobei N0 := N mod Z, N1 := (N div Z) mod Z, N2 := N div Z2.

Obwohl die Notation N = N2·Z2 + N1·Z + N0= (N2, N1, N0)Z verwendet werden kann, impliziert diese letztere Notation nicht, dass N1 und N0 modulo Z reduziert werden, während die erste Notation (N2|N1|N0)Z dies impliziert: Bei dieser Notation sind N1 und N0 in [0,Z[. N2 kann aber größer als Z sein, und zwar in dem Fall von N ≥ Z3. Äquivalent dazu kann N2 in dem Fall von N < 0 negativ sein.

  • • Außerdem werden die Verallgemeinerungen (Nm-1|...|N0)Z sowie (Nm-1, ..., N0)Z analog auf die offensichtliche Weise verwendet.
  • • Es sei Z als eine Potenz von zwei angenommen, z. B. Z = 21024. Es ist jedoch nicht nötig, dass Z eine Potenz von zwei ist und auch keine nicht-triviale Potenz einer Ganzzahl!

Die folgenden Grundalgorithmen sind grundlegend und werden immer verwendet. Ihre Implementierung wird im Folgenden erörtert. Es sei K ∊ N.

Die übliche Multiplikation: A·B

Die modulare Multiplikation von Bitlänge K: A·B mod N

Die MultModDiv-Operation (2g) von Bitlänge K: (A·B div N, A·B mod N)

Außerdem wird der MultAdd-Algorithmus (2d) benötigt: A·B + C·2K sowie der MultModAdd (2e): A·B + C·2K mod N

Es wird oft geschrieben:

MK(A, B) = A·B,

MMK(A, B; N) = A·B mod N,

MMDK(A, B; N) = (A·B div N, A·B mod N).

Die Performance bzw. Geschwindigkeit dieser Algorithmen, die an dieser Stelle nicht weiter klassifiziert wird, hängt von ihrer Implementierung ab. Somit wird sie im Folgenden durch mK, mmK, mmdK usw. bezeichnet.

Es sei darauf hingewiesen, dass der Index auf eine sehr freie Weise verwendet wird, manchmal, wenn das exakte K nicht wichtig ist, wird der Index weggelassen, manchmal wird K durch die tatsächliche Zahlenbasis 2K ersetzt. Es werden sogar andere Basen verwendet. Mehr darüber ist in den folgenden Abschnitten ausgeführt.

Anmerkung 1: Es sei auf die sehr wichtige Tatsache hingewiesen, dass für (Q, R) := MMDK(A, B; N) folgende Identität vorliegt A·B = Q·N + R.

Dies ist ein grundlegendes Faktum für viele folgende Implementierungen.

In diesem Abschnitt werden einige Hinweise darauf gegeben, wie die Grundalgorithmen bei Crypto@1408 implementiert werden – wenn sie auf eine direkte Weise implementiert werden können. Außerdem werden einige sehr grundlegende und allgemeine Verfahren erörtert, um eine lange Ganzzahlarithmetik in kleinere Teile zu zerlegen.

Multiplikation

Bei Crypto@1408 sind Multiplikationen einer Länge von bis zu 1400 Bits (einschließlich Vorzeichenbits) möglich, d. h. A B für #A + #B ≤ 1400. Die Durchschnittsperformance bei Crypto@1408 für diese Operation ist gegeben durch

Für mehr zu diesem Multiplikationsalgorithmus sei auf [5, 6, 8] verwiesen. Normalerweise wird, um eine lange Multiplikation in kleinere Teile zu zerlegen, die bekannte Schulmethode verwendet: Es sei z. B. Z := 2k für irgendein geeignetes k gesetzt und A = (Am-1, ..., A0)Z sowie B = (Bm-1, ..., B0)Z geschrieben, dann kann das Verfahren grob beschrieben werden, wie es in 2c gezeigt ist.

Die Zeile in der Schleife wird auf folgende Weise gelesen werden: Der alte Wert der Partialganzzahl (Ci+j+1, Ci+j)Z = Ci+j+1·Z + Ci+j wird zu dem Partialprodukt Mk(Ai, Bj) addiert, was das Ergebnis X ergibt. Dann wird Ci+j+1 := X div Z und Ci+j := X mod Z gesetzt. Natürlich sind in diesen Anweisungen Behandlungen von Überträgen versteckt, die hier nicht näher erörtert werden.

Es gibt schnellere Möglichkeiten, eine Multiplikation zu implementieren, z. B. mit KARATSUBA-OFFMANN, vgl. [9]. Aber obwohl diese Algorithmen in der theoretischen Performance sehr gut sind, fehlt ihnen oft, dass sie nicht optimal für die Implementierung sind, z. B. benötigen sie sehr viele Ressourcen, wie z. B. Speicher.

Modulare Multiplikation

Bei Crypto@1408 sind modulare Multiplikationen einer Länge von bis zu 1400 Bits möglich, d. h. A·B mod N für LR := #N + 1 ≤ 1400. Die Realisierung erfolgt über den sogenannten ZDN-Algorithmus – [11]. Die Durchschnittsperformance bei Crypto@1408 für diese Operation ist gegeben durch

Der Faktor &agr; = &agr;LR ist ein Parameter, der von den statistischen Eigenschaften des ZDN-Algorithmus abhängt. Für &agr;LR hat man gewöhnlich Werte zwischen 2,5 und 2,7.

Eine Art, die Multiplikation für längere Bitlängen zu implementieren, besteht darin, sie in kleinere Stücke zu zerlegen. Wird die Gleichung für m = 3 betrachtet A·B mod N = A(B2Z2 + B1Z + B0) mod N = (((A·B2 mod N)Z + A·B1 mod N)Z + A·B0) mod N so ist zu erkennen, dass eine modulare Multiplikation A·B mod N wie in 1d realisiert werden kann, wobei die Operation MMA in 1e gezeigt ist.

Natürlich ist dies nur eine Möglichkeit. Einige abgeleitete Versionen davon sind in dieser Schrift präsentiert.

Die MultModDiv-Operation

Die MultModDiv-Operation ist eine kürzlich eingeführte Operation, vgl. [7], die etwas mehr macht als eine modulare Multiplikation: Sie berechnet nicht nur das modulare Produkt (A·B mod N), sondern auch den Quotienten (A·B div N). In HW implementiert ist der zusätzliche Implementierungsmehraufwand gering, da diese letzte Ganzzahl nur ein Protokoll davon ist, was die modulare Reduktion während der modularen Multiplikation gemacht hat. In SW ist der Mehraufwand erheblich, überraschenderweise jedoch nur 100 %! Der Algorithmus kann implementiert werden, wie in 10a gezeigt ist.

Es sei darauf hingewiesen, dass dieser Algorithmus nur für positive und reduzierte A und B funktioniert. Er wird später auch für einen (reduzierten) negativen Multiplikanden benötigt, aber in diesem Fall wird nur die negative Ganzzahl invertiert, der letztere Algorithmus angewandt und schließlich die Ausgabe invertiert. Auch ist es möglich, die zwei modularen Multiplikationen parallel (Modus) auszuführen, falls der Modul klein genug ist. Dies bedeutet erneut ein Verdoppeln der Performance. Näheres dazu später bezugnehmend auf die 11a und 11b. Wie es dort ersichtlich ist, ist die Performance für MMDk gegeben durch:

In den Algorithmusdarstellungen steht, gemäß üblicher Pseudo-Code-Notation der Ausdruck „Input" für die Algorithmus-Eingangsparameter. Der Ausdruck „Output" steht für die Algorithmus-Ausgabe. Der Ausdruck „Return" steht für „Rücksprung bzw. Rückgabe des entsprechenden Werts zu einem hierarchisch höherstehenden Programm, das den Algorithmus aufgerufen hatte. Das Argument von „Return" ist somit das eigentliche Ergebnis des Algorithmus, das ausgerechnet worden ist. Ferner steht „for" für eine Wiederholungsschleife, die ausgehend von einem Startparameter bis („to") zu einem Endparameter etwas ausführen soll, was durch den Ausdruck „do" angegeben wird. „End" steht für das Ende einer Schleife. Ferner steht „if" für ein „wenn", also eine bedingte Schleife, wobei „then" angibt, was zu tun ist, wenn die Bedingung der If-Schleife erfüllt ist. Entsprechend gibt „else if" eine weitere Bedingung an, die statt einer ersten Bedingung erfüllt sein muss, um eine bestimmte Berechnung, die durch „then" eingeleitet wird, durchzuführen. Der Ausdruck „treat carry" steht für Behandeln eines Übertrags, wobei Borrow für einen negativen Übertrag, also gewissermaßen einen „Vortrag" steht.

Nachfolgend werden ferner einige Registerimplementierungen angegeben, wie sie z. B. in 6b zu sehen sind. Unter „Crypto@1408" finden sich die Register des vorzugsweise verwendeten Kryptocoprozessors mit 1.408 Bit-Slices, die jedoch aufgrund der Teilung in der Mitte im Kurz-Modus betrieben werden. Die Register-Notation ist in allen Registerimplementierungen so, wie sie in 4a im rechten Teilbild dargestellt ist. So bedeutet beispielsweise das zweite Feld in der rechten Spalte das Register CR0 des Prozessors. Ferner bedeuten die in den Feldern stehenden Zahlen die entsprechenden Werte, die in das entsprechende Register eingespeichert werden. Befinden sich „Sterne" in einem Register, so bedeutet dies, dass das Register unbenutzt ist, d. h. das Register kann mit unbestimmten Zahlen belegt sein, die aber keine weitere Rolle spielen. Ferner steht die senkrechte Spalte von Feldern, die mit „XDATA" beschrieben ist, für einen externen Speicher, also bezieht sich auf einen RAM-Arbeitsspeicher des Prozessors, während die zwölf Register die internen Register des Speichers sind. Sollen also Daten vom externen RAM-Speicher in die Register des Coprozessors geladen werden, so sind Datenbewegungsbefehle (Move-Befehle) nötig.

Registerarchitektur von Crypto@1408

Im Folgenden werden die Implementierungen der Algorithmen mit den Zuweisungen der Krypto-Register mit den Zwischenergebnissen dargestellt. Dort wird Crypto@1408 in den zwei Modi gezeigt, nämlich dem langen Modus und dem parallelen Modus (4a).

  • • Bei dem langen Modus gibt es 5 Register der Länge 1.408 Bit: Z, C, N, CR0 und CR4.
  • • Bei dem parallelen Modus gibt es 10 Register der Länge 704 Bit: CR0, CR2, CR4 und CR6 sowie drei Register Z, C, N für jede Seite.

Die Grundkonfigurationen sind dargestellt, wie es in 4a gezeigt ist:

Bewegen von Daten

Abhängig davon, dass die Daten in dem Cachespeicher oder in dem XRAM (externen Speicher) liegen können, kann es mehr oder weniger lang dauern, eine Ganzzahl in Crypto@xxxx hinein oder aus demselben heraus zu bewegen. Für das Folgende wird ein durchschnittlicher Wert für die Performance movk, um eine k-Bit-Ganzzahl in Krypto hinein oder aus demselben heraus zu bewegen. Einige Beispiele zeigen, dass die Bewegungen eine erhebliche Zeit benötigen, die mit Multiplikationen vergleichbar ist.

Die Modularmultiplikationsalgorithmen

Es gibt mehrere Algorithmen zum Implementieren einer modularen Multiplikation auf der Basis von einfacheren Elementen, wie z. B. (kleinen) Multiplikationen oder einer kleineren modularen Multiplikation. Aufgrund von diesen Algorithmen ist es möglich, eine modulare Exponentiation durch „quadrieren und multiplizieren" oder Lucas-Kettenverfahren (Montgomery-Leiter) zu implementieren. Es wird nicht der Weg eines Auffindens optimaler Performancealgorithmen für Quadrieren bzw. Multiplizieren beschritten, da dies die Möglichkeit einer sicheren Implementierung von RSA ausschließt, falls dies nötig ist.

Obwohl das Interesse eigentlich auf dem Algorithmus MM2048 liegt, ist ersichtlich, dass A·B mod N = A(B2Z2 + B1Z + B0) mod N, oder dieser Ausdruck kann äquivalent geschrieben werden als ((A·B2 mod N) Z + A·B1 mod N) Z + A·B0 mod N. Deshalb kann die Implementierung von MMK manchmal in einige „kleinere" Algorithmen, wie z. B. MMAk, für einige k < K, zerlegt werden.

Obwohl diese Algorithmen bisweilen zusätzliche Daten benötigen (deshalb können einige Vorberechnungen nötig sein), wird dies nicht berücksichtigt und dieselben werden nicht gezählt. Normalerweise haben sie keine Auswirkung auf die Performance der vollen RSA-Berechnung. Sie können jedoch eine Wirkung auf die Performance einer „kurzen" RSA haben, wie z. B. eine Verifizierung mit einem kleinen Exponenten F4 = 216 + 1.

Montgomery-Multiplikation

Ohne Zweifel ist der berühmteste Algorithmus zum Implementieren einer modularen Multiplikation die Montgomery-Multiplikation [10]. Dieser Multiplikationsalgorithmus implementiert eigentlich nicht den Algorithmus MMK(A, B; N) = AB mod N, sondern vielmehr A·B·2–K mod N

Ohne ins Detail zu gehen, kann mit dieser seltsamen Art von modifizierter Multiplikation eine K-Bit-RSA-Berechnung mit der gleichen Anzahl von Multiplikationen wie bei den gewöhnlichen Implementierungen, die MMK verwenden, implementiert werden.

Multiplikation mit Barrett-Reduktion

Momentan wird auf eine Erörterung dieses Verfahrens verzichtet, da die Barrett-Reduktion normalerweise die gleiche Performance wie das letzte Verfahren aufweist. Es wird nicht erwartet, dass es in diesem Zusammenhang eine sehr viel bessere Implementierung gibt als diejenige im letzten Abschnitt.

Algorithmus von Fischer-Sedlak-Seifert mit MMD

Dieser Algorithmus wurde konzipiert, um einen 1k-Bit-RSA-Coprozessor zu 2k-Bit-Operationen zu befähigen, wobei nur ein geringfügiger Hardwarezusatz erforderlich ist. Der Algorithmus, der in [7,2] beschrieben ist, wird speziell zum Verdoppeln der Bitlänge verwendet. Er verwendet den MultModDiv-Algorithmus, der in die Hardware eingebaut werden muss, vgl. [4], oder in Software emuliert werden kann, vgl. [3], mit zwei modularen Multiplikationen.

Erfindungsgemäßer bevorzugter Algorithmus mit MMD

Dieser Algorithmus implementiert die modulare Multiplikation auf die klassische Weise durch ein Berechnen von

Aus praktischen Gründen und aufgrund von Architekturbeschränkungen erfolgt dies jedoch in drei Schritten – wie im Vorhergehenden beschrieben – durch ein Implementieren für K = m·k mit m = 3 und k = [K/3]. Somit wird MMK implementiert wie in 1d.

Nun ist MMAZ der Algorithmus, der gegeben ist (1e).

N2 liegt sehr nahe an Z. Momentan werden aber keine Einschränkungen bezüglich der Ganzzahl Z gemacht, außer dass Z in etwa die richtige Größe von k Bits aufweisen muss. Mehr dazu wird später ausgeführt.

Erneut wird dieser letzte Algorithmus in zwei Schritten implementiert, nämlich: Zuerst wird die Multiplikation durchgeführt, die in 1f gezeigt ist.

Es wird auf die folgende Schätzung verwiesen.

Anmerkung 5: Für die Ausgabe von MAZ ergibt sich

Nach dem Multiplikationsschritt kommt die Reduktion aus 1g.

Nachfolgend wird zunächst die mathematische Beschreibung von MAZ und RedZ mit etwas Theorie präsentiert, was für die Implementierung wichtig sein wird.

Beschreibung des Algorithmus

Von nun an werden jegliche Algorithmen für den Fall von m = 3 gegeben. Denn das ist der bevorzugte Fall. k wird noch nicht festgelegt.

Die Multiplikationsoperation MAZ (3a), d. h.

(A2|A1|A0)Z·Bi + (C2|C1|C0)Z·Z

oder äquivalent dazu

(A2|A1|A0)Z·Bi + (C2|C1|C0|0)Z

wird auf die einfache Weise implementiert: ABi + CZ = A0Bi + (A1Bi + C0)Z + (A2Bi + C1)Z2+ (A2Bi + C2)Z3+ C3Z3

Da Aj·Bi eine 2k-Ganzzahl ist, wird dieses Produkt geschrieben als Aj·Bi = (BAij)1·Z + (BAij)0 und deshalb ergibt sich für das Ergebnis (BAi0)0+ ((BAi0)1 + (BAi1)0 + C0)Z + ((BAi1)1 + (BAi2)0 + C1)Z2+ ((BAi2)1 + C2)Z3

Es sei darauf hingewiesen, dass die großen Klammern immer noch ≥ Z sein können!

Die Reduktionsoperation RedZ (3b), d. h. E:= D mod N wird implementiert als E := D – [D div N]·N.

Hier

Da jedoch Q0 := D div N nicht direkt berechnet werden kann, besteht die Strategie darin, sich zuerst Q0 durch Q~ 0 zu approximieren, wobei Q~0 := D3·Z div N2.

Daher kann Q0 = Q~0 + &egr; geschrieben werden. Eine Berechnung zeigt, dass &egr; ∊ {–2, –1, ..., 4}, und in diesem Kontext gilt sogar

&egr; ∊ {–2, –1, 0, 1, 2, 3}.

Anmerkung 6: Tatsächlich wird &egr; = –2, 3 fast nie auftreten und &egr; = 2 nur sehr selten.

Somit gilt, dass die erste Version des schlichten (Basis-) Algorithmus aus 3b wie in 3c sein wird.

Anmerkung 7: Der Bereich von Q0 ist gegeben durch:

Leider wurde das Problem der genauen Berechnung der Division nur aufgeschoben. Aber da dies sehr gut funktioniert hat, wird es ein zweites Mal durchgeführt: Es wird sich &egr; durch &egr;~ genähert, derart, dass &dgr; := &egr; – &egr;~ ∊ {–1, 0, 1}.(2)

Dann sieht die Reduktion wie in 3d aus.

Wie approximiert man nun &egr;? Es sei folgende Gleichung betrachtet: (D – Q~0N) mod N = D mod N = (D – Q~0N) – &egr;N

Dies ergibt &egr; = (D – Q~0N) div N, und deshalb wird berechnet D – Q~0N: Es sei gesetzt Q~0 := D3Z div N2 und R~0 := D3Z mod N2, so dass D3Z = Q~0N2 + R~0. Nun D – Q~0N = (D2 + R~0 – (Q~0N1)1)Z2 + (D1 – (Q~0N1)0 – (Q~0N0)1)Z + (D0 – (Q~0N0)0

Hier wurde die Notation (Q~0Ni)1 := Q~0Ni div Z und (Q~0Ni)0 := Q~0Ni mod Z verwendet, so dass Q0Ni = (Q~0Ni)1Z + Q~0Ni)0.

Daraus kann nun eine Näherung für &egr; gegeben werden durch ein Berechnen von &egr;~ := (D2 + R~0 – (Q~0N1)1) div N2.

Tatsächlich approximiert man sich die Operanden durch ihre obersten (z. B.) 16 Bits. Es bleibt noch die Arbeit zu beweisen, dass &dgr; := &egr; – &egr;~ ∊ {–1, 0, 1} gilt.

Dies wird später gezeigt. Nun ist es möglich, die folgende Version von RedZ zu geben, die in 3e gezeigt ist.

Es sei die folgende Berechnung betrachtet: D – Q~0N – &egr;~N = (D2 + R~0 – (Q~0N1)1&egr;~N2)Z2 + (D1 – (Q~0N1)0 – (Q~0N0)1&egr;~N1)Z + (D0 – (Q~0N0)0&egr;~N0) = (D2 + R~0 – Q'0N1)1&egr;~N2)Z2 + (D1 – (Q'0N1)0 – (Q'0N0)1)Z + (D0 – (Q~0N0)0

Aufgrund dieser Berechnung kann die Endversion des Algorithmus gegeben werden, wie in 3f gezeigt ist.

Anmerkung 8: Es sei auf den kleinen Unterschied in den ersten Zeilen hingewiesen: (Q~0, R~0) := MMD (D3, Z; N2) wurde ersetzt durch (Q~0, R~0) := MMD(D3, Z – N2; N2 Q0 := Q0 + D3

Zunächst ist einfach zu prüfen, dass diese neue Gleichung immer noch gilt! Diese Veränderung wurde vorgenommen, da nicht gewünscht wird, dass Operanden größer sind als der Modul, und in diesem Fall Z > N. Da jedoch oder genauer ist sicher, dass Aufgrund von Gleichung 1 liegt jedoch der erste Operand in [–Z, Z[, es wird aber ersichtlich, dass dies kein Problem ist, da

Es sei ferner auf Folgendes hingewiesen:

Anmerkung 9: Aufgrund von Anmerkung 7 und Gleichung (2) ergibt sich Q'0 ∊ [–Z –1, Z].(3)

Mathematische Performance

Für den ersten Teil MAk werden 3mmdk benötigt, für den zweiten Teil Redk werden ebenfalls 3mmdk benötigt. Da diese Berechnung drei Mal durchgeführt werden muss, ergibt sich mmK = 18·mmdk.

Implementierung für (m, k) = (3, k)

Die Implementierung des Algorithmus ist ab 5 gezeigt.

Systemperformance für (m, k) = (3, k)

Es ist ersichtlich, dass die Implementierung des Algorithmus MAk 3mmdk + movk benötigt und die Implementierung von Redk 3mmdk benötigt. Dies wird drei Mal verwendet, und danach muss das Ergebnis außerhalb des Krypto bewegt werden, so dass die Performance ist: 3 (6mmdk + movk) + movK, d. h.

Der Bereich von &egr;

Der Parameter &egr; wurde definiert, um zu sein, wobei D ∊ [–NZ, NZ[, insbesondere D3 ∊ [–Z, Z[. Um eine Schätzung von &egr; zu geben, wird zunächst die reelle Zahl berechnet und dann das folgende Lemma verwendet.

Lemma 1 Für r, s ∊ R, gilt immer

Nun wird gesetzt und es ergibt sich

Deshalb wird ⌊e⌋ ∊ {–2, ..., 3} erhalten und aufgrund des Lemmas &egr; ∊ {–2, ..., 4}. Trotzdem, falls angenommen wird, dass dann

So ist ersichtlich, dass in diesem Fall ⌊e⌋ ∊ {–2, –1, 0, 1, 2} und &egr; ∊ {–2, –1, 0, 1, 2, 3}.

Wie &egr; zu schätzen ist

Es wurde ersichtlich, dass &egr; = aZ2 + bZ + c, wobei a = (D2 + R~0 – (Q~0N1)1), b = (D1 – (Q~0N1)0 – (Q~0N0)1), c = (D0 – (Q~0N0)0), und es wurde definiert &egr;~ := a div N2 . Nun sei gesetzt:

Dann

Offensichtlich –4Z < a < 3Z –5Z < b < Z –Z < c < Z

Dann

Es zeigt sich, dass x = r – s tatsächlich sehr klein ist, da Z in dem Bereich von 2700 ist! So ergibt sich praktisch nie der Fall dass &egr; ≠ &egr;~ (für allgemeine Ganzzahlen).

Die tatsächliche Näherung erfolgt durch ein Berechnen von s nur unter Verwendung der obersten (z. B.) 16 Bits der beteiligten Ganzzahlen, deshalb wird ein Fehler von etwa der Größe 2–16 gemacht. Dies ist immer noch sehr klein, und nur bei wenigen Fällen wird die Schätzung von &egr;~ um 1 inkorrekt sein. Aus diesem Grund wird ein Endreduktionsschritt am Ende von Red benötigt.

Analyse des Algorithmus

In diesem Abschnitt werden die drei Algorithmen verglichen, die in den vorstehenden Abschnitten beschrieben wurden. Diese Multiplikationsverfahren werden als Algorithmus I, Algorithmus II bzw. Algorithmus III bezeichnet.

Vergleich der Algorithmen

Performancewerte – nur für die zeitaufwändigen Teile der Algorithmen – sind in 4e gegeben. Natürlich braucht eine reale Implementierung etwa 10–20 % länger für all den Softwaremehraufwand, der hier nicht beschrieben ist.

Vorteile/Nachteile

  • • Unter 2.064 Bit ist die schnellste Multiplikation der Algorithmus III.
  • • Über 2.065 Bit ist der einzige funktionierende Algorithmus der Algorithmus II.
  • • Algorithmus III benötigt am wenigsten externen Speicher.

Implementierungsaspekte

In diesem Abschnitt wird die 2.048-Bit-RSA-Implementierung bei Crypto@1408/SLE88 im Detail beschrieben. Natürlich liegt das Hauptaugenmerk auf der Implementierung der modularen Multiplikation. Es ist klar, wie die Multiplikation in dem Rahmen einer Exponentiation zu setzen ist. Dies wird deshalb nur sehr kurz beschrieben. Die modulare Multiplikation A·B mod N, die hier präsentiert ist, hat eine gewisse Einschränkung: Die Ganzzahlen A, B und N müssen in eine spezielle Form umgewandelt werden, es hat nämlich von der binären Form in die Z-äre Form gebracht, z. B. (A2, A1, A0)Z mit drei „Stellen". A und B müssen natürlich reduziert werden. Die Vorberechnung entscheidet zuerst die Länge k des Basisparameters Z, wandelt die Eingangswerte A, B und N in die richtige Form um, derart, dass sie für den Modularmultiplikationsalgorithmus verwendbar ist. Hier werden A und B nur von der binären Form in die Zäre gebracht. Der Modul N wird – wie es für die übliche Implementierung von RSA bei Crypto@xxxx bekannt ist – mit einer bestimmten Ganzzahl multipliziert, und die Exponentiation wird mit diesem Vielfachen von N durchgeführt. Nach der Exponentiation ist es nötig, die Endreduktion modulo das ursprüngliche N vorzunehmen. Und das Ergebnis in Z-ärer Form wird zurück in die alte binäre Form berechnet.

Es ist überflüssig zu erwähnen, dass dieser Algorithmus mit der Vor- und Nachberechnung nicht gut für eine einzige modulare Multiplikation geeignet ist, obwohl es möglich ist. Andererseits benötigen alle anderen Multiplikationsalgorithmen, z. B. die hier vorgestellten, normalerweise irgendeine Art von Vor- und Nachberechnung, und tatsächlich gibt es keine wirklich bessere Möglichkeit, eine einfache modulare Multiplikation vorzunehmen.

Struktur der RSA-Implementierung

Der Rahmen der RSA-Implementierung ist gleich jeder beliebigen anderen Implementierung. Zuerst gibt es die Vorberechnung, ein Umwandeln der Eingangparameter baseB* und modulus N* in die richtige Form B und N. Dann beginnt die eigentliche RSA-Implementierung: Es wird entschieden, ob ein Quadrieren oder die Multiplikation mit der Basis vorgenommen wird. Aufgrund dieser Entscheidung wird entweder die Operation A ← MM(A, A, N) oder A ← MM(A, B, N) ausgeführt. Es wird nicht beschrieben, wie diese Entscheidung getroffen wird – dabei handelt es sich um einen Standard für eine RSA-Implementierung. Am Ende, in der Nachberechnung, wird das Ergebnis A modulo den Eingangsmodul N* reduziert und zurück in die binäre Form umgewandelt, die für die Ausgabe nötig ist.

Im Folgenden wird die Implementierung von A ← MM(A, B, N) beschrieben. Für das Quadrieren, d. h. A ← MM(A, A, N), kann A für den Parameter B verwendet werden. Es kann sogar den gleichen zugeteilten Speicher aufweisen, da das Ergebnis ganz am Ende in den Container von A kopiert wird.

Es sei darauf hingewiesen, dass die Exponentiation/modulare Multiplikation nur einen externen Speicher für A2, A1, A0, B2, B1, B0, N1 und N0 benötigt, also maximal Bytes.

Ein Überblick über den Algorithmus ist in 5 gegeben.

5 zeigt also gewissermaßen ein Ablaufdiagramm des erfindungsgemäßen modularen Multiplikationsalgorithmus für drei Abschnitte. Die Verarbeitungsrichtung bzw. Zeitrichtung ist in 5 mit einem Pfeil 50 dargestellt. Um eine modulare Multiplikation durchzuführen, sind also, wie es z. B. anhand von 1d dargestellt worden ist, drei aufeinander folgend durchzuführende MMA-Operationen gezeigt, die in 5 mit 51, 52 und 53 bezeichnet sind. Für die MMA-Operation 51 wird der höchstwertige Abschnitt B2 des Multiplikanden verwendet. Für die zweite MMA-Operation 52 wird das Ergebnis der ersten MMA-Operation sowie der nächstniederwertige Abschnitt B1 des Multiplikanden verwendet. Das Ergebnis der zweiten MMA-Operation wird schließlich zusammen mit dem niedrigstwertigen Abschnitt B0 des Multiplikanden verwendet, um das Endergebnis der modularen Multiplikation zu erhalten. Hierauf werden mittels eines Move-Befehls 54, das Ergebnis aus den internen Registern, also E2, E1 und E0, ausgelesen, um die internen Register für eine neue modulare Multiplikation freizumachen.

Jede MMA-Operation, beispielsweise die MMA-Operation 51, teilt sich in eine MA-Operation 55a und eine Reduktionsoperation 55b auf, wobei die MA-Operation ihrerseits wieder in verschiedene Operationen, die in 5 dargestellt sind, aufgeteilt wird, während die Reduktionsoperation ebenfalls entsprechend aufgeteilt wird.

Der Modularmultiplikationsalgorithmus

Die Eingabe für diese modulare Multiplikation ist der Modul N, der Multiplikand A ∊ [0, N[ und der Multiplizierer B ∊ [0, N[. Formell gibt es einen Eingangsparameter k, der die Länge der Berechnung definiert. Die Ausgabe ist A·B mod N, die an der Stelle von A gespeichert wird, das sich in dem externen Speicher befindet.

Die Eingabebedingungen für diesen Algorithmus, die bereits im Vorhergehenden erörtert wurden, sind

N ist in drei Ganzzahlen N2, N1 und N0 codiert, derart, dass Ni ∊ [0, Z[und N = N2·Z2 + N1·Z + N0, kurz geschrieben als N = (N2, N1, N0)Z.

Außerdem N2 ∊ [0, Z[, derart, dass N2 gemäß der Crypto@xxxx-Architektur umgewandelt wird.

A ist als drei Ganzzahlen A2, A1 und A0 codiert, derart, dass Ai ∊ [0, Z[und A = A2·Z2 + A1·Z + A0, kurz geschrieben als A = (A2, A1, A0)Z

B ist in drei Ganzzahlen B2, B1 und B0 codiert, derart, dass Bi ∊ [0, Z[und B = B2·Z2 + B1·Z + B0, kurz geschrieben als B = (B2, B1, B0)Z.

Der Modularmultiplikationsalgorithmus ist in 6a gezeigt.

Er ist in der 6b veranschaulicht.

Im externen Speicher XDATA befinden sich jeweils die Abschnitte des Multiplikators A und des Multiplikanden B sowie der niederstwertige und der nächst höherwertige Abschnitt N1 und N0, während der höchstwertige Abschnitt N2 des Moduls bereits im CR6-Register des Kryptocoprozessors, der im Kurz-Modus betrieben wird, sitzt. Die anderen drei Register CR4, CR2 und CR0 sind zu Null gesetzt. Das Zwischenergebnis der ersten MMA'-Operation, also E1', E2', E0', ersetzt dann die Nullen in den entsprechenden Registern vor dem ersten MMA'-Schritt. Der zweite MMA'-Schritt führt dazu, dass die Werte E0', E1' und E2' durch E0'', E1'' und E2'' ersetzt werden. Durch die nächste MMA-Operation findet wiederum ein Ersetzen statt, so dass dann, nach der dritten MMA-Operation, das Endergebnis der modularen Multiplikation in Form des niedrigsten Abschnitts E0, des nächst höheren Abschnitts E1 und des höchsten Abschnitts E2 vorliegt. Dieses Ergebnis E wird also durch den Algorithmus in 6a erhalten, und zwar ebenfalls abschnittsweise.

Die Ergebnis-Abschnitte E2, E1 und E0 ersetzen im Arbeitsspeicher A2, A1 und A0, so dass das Ergebnis eines vorherigen modularen Multiplikationsschritts nunmehr den neuen Multiplikator A für den nächsten modularen Multiplikationsschritt liefert, der wieder genauso ablaufen wird, wobei nun jedoch der ursprüngliche Operand A durch den neu berechneten Operanden E ersetzt ist.

Bei diesem Algorithmus wird neben dem bereits bekannten MMA-Algorithmus eine Variation desselben, nämlich MMA' verwendet. Grob ist der Unterschied zwischen den beiden Algorithmen in der Formel MMA' = MMA – N gegeben. Sie sind definiert wie in 7a und 7b gezeigt.

Die Registerimplementierung ist in 7c veranschaulicht.

Beide Variationen verwenden die Algorithmen MAZ und RedZ, wobei der letzte wieder zwei Varianten hat, nämlich RedZ selbst und Red'Z. Grob ist der Unterschied zwischen den beiden Algorithmen in der Formel Red' = Red – N gegeben.

Es wird zuerst der Algorithmus MAZ erörtert. Der Algorithmus ist in 8a dargestellt.

Die Registerimplementierung des Algorithmus von 8a ist in 8b dargestellt. Eine bevorzugte Implementierung des erfindungsgemäßen Konzepts, das in 8a algorithmisch dargestellt ist, ist in 8d gezeigt, wobei die Registerbewegungen, auf die in 8d Bezug genommen wird, in 8c zusammengefasst sind, und wobei in 8e ein Beispiel für den erfindungsgemäßen Multiplikations-Additions-Algorithmus und die Verwendung der zwei Hilfsregister und der vier Ergebnisregister gegeben ist. Bevor detailliert auf den Algorithmus eingegangen wird, wird zunächst anhand von 8c die Bedeutung des Ausdrucks „kurze Registerlänge" und „lange Zahlenlänge" dargestellt. Hierzu ist ein Registerblock 800 dargestellt, der lediglich aus Übersichtlichkeitsgründen neun Register umfasst. Jedes Register dieser neun Register hat eine bestimmte Zahlenlänge bzw. eine Anzahl von Binärstellen und kann somit höchstens einen Abschnitt Ai, Bi, Ci des Operanden A, des Operanden B und des Operanden C speichern. Bei dem hier gezeigten Beispiel wird jeder Operand in drei Abschnitte aufgeteilt. Der Index i hat somit die Werte 0,1, 2.

Wenn man jedes Register für sich auffassen möchte, so hat jedes Register eine Zahl zwischen Null und 2k-1. Wenn jedoch per Konvention, was in der Rechenwerkstechnik üblich ist, dem niederstwertigen Bit eines Registers eine bestimmte Anfangswertigkeit gegeben wird, so kann man durch entsprechendes Interpretieren der Zahlen in Registern aus diesen kleinen Registern gewissermaßen ein großes Register nachbilden. Genauso könnte nämlich eine Zeile des Registerblocks bei 800 in 8c als ein einziges großes Register umfassen, das eine Länge hat, die gleich dem dreifachen einer kurzen Registerlänge ist. In diesem Fall müsste z. B. dem mittleren kurzen Register, in dem A1 oder B1 oder C1 gespeichert ist, eine Anfangswertigkeit von 2k bzw. allgemein gesagt eine Anfangswertigkeit einer Zahl Z (dem vierten Operanden) gegeben werden, während die Anfangswertigkeit des entsprechenden niederstwertigen Registers, in dem A0, B0, C0 gespeichert ist, gleich 20 betragen würde. Entsprechend würde die Anfangswertigkeit eines Registers, in dem A2, B2 oder C2 gespeichert ist, gleich 22k oder Z2 betragen.

Entsprechend sind auch die Konventionen bei den einzelnen Ausgabe- oder Ergebnisregistern 802. Hier handelt es sich wieder um vier Register mit kurzer Registerlänge, in denen jeweils ein Abschnitt D0, D1, D2 oder D3 des Ergebniswerts gespeichert ist, wobei je nach Position bzw. Identifikation eines kurzen Registers eine Anfangswertigkeit von 20, Z, Z2oder Z3 vorliegt, die einem Registerinhalt dann gegeben werden muss, wenn es auf die insgesamte (absolute) Zahl und nicht nur auf eine Zahl innerhalb eines Registers ankommt.

Bei 804 ist ein Beispiel für eine Multiplikations-Additions-Operation gezeigt, also eine Operation zwischen einem ersten Operanden A, einem zweiten Operanden Bi, einem dritten Operanden C und einem vierten Operanden Z, wobei der erste Operand A und der dritte Operand C länger als der zweite Operand Bi oder der vierte Operand Z sind, und wobei Abschnitte des ersten Operanden A oder des dritten Operanden C kürzer als der erste Operand oder der dritte Operand an sich sind. In den einzelnen Ergebnisregistern 802a, 802b, 802c, 802d sind iterativ berechnete Ergebnisse gespeichert, wobei in den Registern 802a bis 802c aktualisierte MOD- bzw. DIV-Ergebnisse von 3 MMD-Operationen gespeichert sind, und wobei im niederstwertigen kurzen Register 802d das MOD-Ergebnis der letzten (dritten) MMD-Operation gespeichert ist.

Es sei darauf hingewiesen, dass eine beliebige Anzahl von Iterationen verwendet werden kann, dass also die langen Operanden nicht notwendiger in drei Abschnitte aufgeteilt werden müssen, sondern auch in zwei Abschnitte oder in mehr als 3 Abschnitte, wie beispielweise 4 oder 5 Abschnitte aufgeteilt werden könnten. Entsprechend würde dann die Anzahl der Iterationen steigen. Es wird jedoch nicht die Anzahl der Hilfsregister steigen. Die Anzahl der benötigten Ergebnisregister würde sich jedoch gemäß der Anzahl der Abschnitte (+1) erhöhen. Dennoch wird im nachfolgendem ein Ausführungsbeispiel diskutiert, bei dem die langen Operanden in drei Abschnitte gleicher Länge aufgeteilt werden, obgleich auch die Aufteilung in gleiche Länge nicht unbedingt nötig ist. Es führt zwar zu einer gleichmäßigen und gut handhabbaren Wertsituation der Anfangswertigkeiten der einzelnen Register, ist jedoch nicht unbedingt Voraussetzung. Werden Abschnitte ungleicher Länge gewählt, so werden die Anfangswertigkeiten der einzelnen kurzen Register entsprechend eingestellt, damit das „Zusammensetzen" der Ergebniszahl aus den einzelnen Abschnitten richtig vonstatten geht.

8d veranschaulicht das erfindungsgemäße Konzept anhand einer Vorrichtung bzw. eines Verfahrens zum Berechnen des Ergebnisses 802 eine Multiplikations-Additions-Operation 804 zwischen einem ersten Operanden A, einem zweiten Operanden Bi, einem dritten Operanden C und einem vierten Operanden Z, wobei der erste und der dritte Operand länger als der zweite oder der vierte Operand sind, und wobei Abschnitte des ersten oder dritten Operanden kürzer als der vierte Operand, also gewissermaßen die Zahl, die die Anfangswertigkeit angibt, sind.

Die erfindungsgemäße Vorrichtung umfasst eine Einrichtung 810 zum Berechnen von Ergebnissen einer MMD-Operation unter Verwendung des zweiten Operanden, eines höherwertigen Abschnitts A2 des ersten Operanden und des vierten Operanden als Modul. Diese Ergebnisse umfassen ein DIV-Ergebnis, das den ganzzahligen Quotienten der Operation liefert, und ein MOD-Ergebnis, das den Rest der ganzzahligen Division ergibt. Diese beiden Ergebnisse werden, wie es in 8d gezeigt ist, einer Einrichtung 811 zum Speichern der Ergebnisse zugeführt. Die Einrichtung 811 ist ausgebildet, um die Ergebnisse in Form von U1 und U0 in zwei kurzen Hilfsregistern 812a, 812b zu speichern. Die in den kurzen Hilfsregistern gespeicherten Werte, also die Ergebnisse der ersten MMD-Operation werden dann an eine Einrichtung 813 zum Aktualisieren des DIV-Ergebnisses und des MOD-Ergebnisses zugeführt, wobei die Aktualisierung unter Verwendung einer Addition von Abschnitten des dritten Operanden durchgeführt wird. Diese Aktualisierung berücksichtig somit den Additions-Term der Multiplikations-Additions-Operation, wie sie bei 804 in 8c gezeigt ist. Die Einrichtung 813 zum Aktualisieren ist ferner ausgebildet, um Aktualisierte Ergebnisse in einem vierten Ergebnisregister 814a und einem dritten Ergebnisregister 814b zu speichern. Der Speicherinhalt des Ergebnisregisters 814a wird als D3' bezeichnet, während der Abschnitt des Ergebnisses im dritten Ergebnisregister als D2' bezeichnet wird.

Je nach Aussehen der Abschnitte des dritten Operanden C führt die Aktualisierung in der Einrichtung 813 zum Aktualisieren zu einer Veränderung des eingespeisten DIV-Ergebnisses oder des eingespeisten MOD-Ergebnisses oder nicht. Ist die gesamte Situation des dritten Operanden beispielsweise so, dass das DIV-Ergebnis oder das MOD-Ergebnis der ersten MMD-Operation nicht verändert wird, so kann der entsprechende Wert U1 oder U0 in dem Hilfsregister 812a, 812b direkt in ein Ergebnisregister 814a, 814b eingetragen werden. In diesem Fall bedeutet das „Aktualisieren" also, dass keine Veränderung des Ergebnisses der MMD-Operation stattgefunden hat. Wenn jedoch der dritte Operand derart ist, dass die Ergebnisse der MMD-Operation, die bei 810 ausgeführt wird, verändert werden, so führt dies zu einer Änderung der Hilfsregister-Werte und dazu, dass die geänderten Hilfsregister-Werte in entsprechende Ergebnis-Register, wie beispielsweise 814a, 814b, eingespeist werden.

Die vorliegende Erfindung umfasst ferner eine Einrichtung 815 zum erneuten Ausführen der MMD-Operation und der Aktualisierung unter Verwendung eines anderen Abschnitts des ersten Operanden, bis alle Abschnitte des ersten Operanden abgearbeitet sind. Die Register, in denen aktualisierte Ergebnisse gespeichert sind, und ein Register, in dem ein MOD-Ergebnis einer letzten MMD-Operation gespeichert ist, liefern dann zusammen gemäß der den Registern zugeordneten Anfangswertigkeit das Ergebnis der Multiplikations-Additions-Operation, wie es bei 802 gezeigt ist.

Die Einrichtung 815 zum erneuten Ausführen kann als Iterationseinrichtung ausgebildet sein, die die Einrichtungen 810, 811, 813 in einer zyklischen Verarbeitung erneut aktiviert, jedoch mit den entsprechenden anderen Abschnitten der Operanden versorgt. Alternativ kann dann, wenn keine iterative Abarbeitung gewünscht ist, die Einrichtung 815 zum erneuten Ausführen auch als einfache Verdoppelung bzw. Verdreifachung der Elemente 810, 811, 813 ausgebildet sein, die jedoch mit entsprechend anderen Werten gespeist werden. Aus Effizienzgründen wird jedoch das Ausführungsbeispiel bevorzugt, bei dem die Einrichtung 815 zum erneuten Ausführen die vorhandenen Einrichtungen 810, 811, 813 erneut, jedoch mit anderen Eingangsoperanden ansteuert, bis sämtliche Abschnitte des ersten Operanden A abgearbeitet sind.

Im ersten Schritt werden als Eingangsoperanden Aj, Bi und Z sowie Cj, Cj-i benötigt.

Im zweiten Schritt werden als Eingangsoperanden Aj-1, Z und Cj-2 benötigt.

Im dritten Schritt werden als Eingangsoperanden Aj-1, Bi und Z benötigt.

Wird eine Aufteilung in nur 2 Abschnitte vorgenommen, so ist die Berechnung bereits nach 2 Schritten fertig.

Sollte jedoch eine Aufteilung in mehr als 3 Abschnitte vorgenommen, so wird im zweiten Schritt neben Cj-2 auch Cj-3 verwendet werden und wird im dritten Schritt Aj-3 sowie Cj-4 verwendet werden, und würde es einen vierten und letzten Schritt geben, in dem Aj-4 verwendet werden würde.

In diesem Fall hätte auch das Ergebnisregister fünf einzelne kurze Ergebnisregister anstatt der für den Fall von 3 Abschnitten verwendeten vier einzelnen Ergebnisregister, in denen die Ergebniswerte D3', D2'' und D0 gespeichert sind, wobei W0 das MOD-Ergebnis der letzten MMD-Operation darstellt, während die anderen drei Einträge in das gesamte Ergebnisregister 802 aktualisierte MMD-Ergebnisse sein werden.

In 8e ist zu Illustrationszwecken ein Beispiel dargestellt sowie die drei Iterationsschritte zum Berechnen des Ergebnisses der Multiplikations-Additions-Operation anhand eines beliebig gewählten Beispiels dargestellt.

Für jeden Schritt ist die Belegung der beiden Hilfsregister 812a, 812b sowie der in diesen Schritten erhaltenen Inhalte der Ergebnisregister 802a bis 802d dargestellt. Bei dem in 8e gezeigten Ausführungsbeispiel werden immer nur Register benötigt, die eine einzige Zehnerstelle speichern können, es werden nie Register benötigt, die zwei Zehnerstellen speichern müssen.

Die Registerimplementierung ist in 8b veranschaulicht.

Der Hauptteil des Algorithmus besteht also aus den MMD-Operationen. Ihre Implementierung wird in einem folgenden Abschnitt erörtert. Neben diesen gibt es eine Elementaroperation, nämlich ein Addieren von Komponenten von Ganzzahlen und ein Behandeln eines möglichen Übertrags. (D'3|D'2)Z := (C2 + U1, C1 + U0)Z bedeutet D'2 := C1 + U0 D'3 := C2 + U1 (D'3, D'2) := TC(D'3, D'2) und (D''2|D'1)Z := (D'2 + V1, C0 + V0)Z bedeutet D'1 := C0 + V0 D''2 := D'2 + V1 (D''2|D'1) := TC(D''2, D'1) [(D'3, D''2) := TC(D'3, D''2)]

Hier wurde die letzte Aktion in Klammern gesetzt, da dies nicht wirklich nötig ist: Falls es nötig wäre, würde der Übertrag in dem letzten Schritt aufgelöst. Da nämlich D''2 ≤ 2(Z – 1), ist es trotzdem möglich, den Übertrag von dem nächsten Schritt zurückzuhalten, und er kann ohne zusätzliche Probleme aufgelöst werden. Schließlich kann (D''1|D0)Z := (D'1 + W1, W0)Z implementiert werden als D0 := W0 D''1 := D'1 + W1 (D''2, D''1) := TC(D''2, D''1)

Der Algorithmus TC ist nichts anderes als ein einfaches Behandeln eines Übertrags in der Z-ären Ganzzahldarstellung, wie in 9a gezeigt ist.

Bei dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird der Algorithmus TC im Rahmen des Aktualisierungs-Schritts durchgeführt, also nach der erfolgten Addition und vor der Belegung der Ergebnisregister 814a, 814b in 8d. Der Algorithmus für TC in 9a gezeigt. Der Algorithmus TC greift erst dann ein, wenn der zweite Input X, also bei dem in 8a gezeigten Algorithmus der Wert aus (C1 + U0) größer als Z ist. Ist dieser Wert kleiner als Z, so gibt es keinen Übertrag, um die Funktion TC aus 9a ist transparent. Ist jedoch die Bedingung X größer als Z oder gleich Z der Fall, so wird Z von X abgezogen, und wird, um den Übertrag zu berücksichtigen Y um „+1" implementiert. Der Wert Y stellt dann den Inhalt des vierten Registers D3' dar, während der Wert X den Inhalt D2' des dritten Registers 814b in 8d darstellt.

Es sei darauf hingewiesen, dass dann, wenn solche Zahlen berechnet werden, bei denen niemals ein Übertrag auftritt, die TC-Funktion nicht benötigt wird. Im Sinne einer universellen Anwendbarkeit wird diese Funktion jedoch bevorzugt und im Rahmen der Einrichtung zum Aktualisieren nach der Addition von Abschnitten des dritten Operanden C eingesetzt.

Nachfolgend wird ein Ablauf des erfindungsgemäßen Verfahrens anhand einer bevorzugten Registerimplementierung detaillierter dargestellt. Ausgegangen wird von der Registersituation eines Rechenwerks mit 5 langen Registern, die in zehn kurze Register aufgeteilt sind. Die Registerbelegung beim Start des Algorithmus ist in 8b bei 840 dargestellt. Es ist zu sehen, dass nur die oberen vier Register mit N2, C1, C2 und C0 belegt sind. N2 ist der oberste Abschnitt des transformierten Moduls, der für die Multiplikations-Additions-Berechnung an sich nicht benötigt wird, der jedoch aufgrund den vorherigen bzw. nachfolgenden Berechnungen bereits im Register steht. Prinzipiell wird er jedoch für die Ausführung der Multiplikations-Additions-Operation nicht benötigt.

Ferner ist in 8b der Zustand des externen Speichers bzw. Arbeitsspeichers XDATA 850 gezeigt. Der externe Speicher 850 umfasst drei Abschnitte des ersten Operanden A, drei Abschnitte des zweiten Operanden B und den mittleren und den untersten Abschnitt des transformierten Moduls N, welche jedoch für die Multiplikations-Additions-Operation ebenfalls nicht benötigt werden.

In einem Speicherbelegungsschritt Movk wird nunmehr der interne Registerspeicher geladen, und zwar mit dem vierten Operanden Z in der vierten Zeile und der linken Spalte bei 840'gezeigt. Die Zahlen Z + 1 sowie die erneute Ladung von Bi in einen weiteren kurzen Speicher werden für die Multiplikations-Additions-Operation in ihrer prinzipiellen Ausführung nicht benötigt. Hierauf wird durch die Einrichtung 810 die erste MMD-Operation durchgeführt. Die Ergebnisse U0, U1 werden in die beiden noch freien Registerspeicher eingespeist, wie es bei 841 dargestellt ist. Nunmehr wird aktualisiert, was durch eine Additions-Funktion und eine TC-Funktion in 8b dargestellt ist. Hierbei werden die Register C2 und C1 mit den Werten D3' und D2' überschrieben. Dies ist möglich, da die Werte C2 und C1 nicht mehr benötigt werden, wie es aus 8a ersichtlich ist. Ferner ist in 8b dann, nach dem ersten Aktualisierungsschritt (Add, TC) die Speicherbelegung derart dargestellt, dass die beiden Hilfsregister, in denen U0, U1 gespeichert waren, wieder gelöscht sind, wie es bei 841' dargestellt ist.

Dann wird die zweite MMD-Operation durchgeführt, und die Ergebnisse V0, V1 werden wieder in die beiden Hilfsregister gespeichert, wie es bei 842 zu sehen ist. Dann wird aktualisiert, es wird also eine Additions-Operation und eine TC-Operation ausgeführt, um zu einer Speicherbelegung 842' zu kommen. Es ist zu sehen, dass der Registerspeicher, in dem Co stand, durch D1' überschrieben worden ist, da Co nach der zweiten Aktualisierung (Add, TC) nicht mehr benötigt wird.

Ferner wird die dritte und letzte MMD-Operation durchgeführt, um eine Belegung des Registerspeichers zu erhalten, wie sie bei 843 gezeigt ist. Wieder wird eine Belegung der beiden Hilfsregister durch W0 und W1, also die Ergebnisse der MMD-Operation erreicht, wobei dann ein letztes Mal aktualisiert wird, um eine Speicherbelegung zu erhalten, wie sie bei 843' dargestellt ist. Bei dem in 8b gezeigten Ausführungsbeispiel wurde der Wert N2 verschoben, und wurde W0 als niederstwertiger Ergebnis-Registerwert eingetragen.

Ein abschließender Treat-Carry-Schritt zur Verwendung des Inhalts des Speichers, wie er bei 843' gezeigt ist, führt zum letztendlichen Output-Zustand, der bei 844 dargestellt ist.

Es sei darauf hingewiesen, dass die interne Speicherbelegung so gewählt worden ist, dass der Prozessor, also die Einrichtung zum Berechnen der MMD-Operation 810 oder die Einrichtung 813 zum Aktualisieren, die ein und das selbe Rechenwerk sein können, oder die getrennte Rechenwerke sein können, immer nur auf einen einzigen Wert im externen Speicher zugreifen muss. Im ersten MMD-Schritt ist dies der Wert A2. Im zweiten MMD-Schritt ist dies der Wert A1, und im dritten MMD-Schritt ist dies der Wert A0.

Im Falle eines Prozessors, der keinen externen Zugriff ausführt, sondern der nur mit seinen internen Registern arbeiten soll, müsst der Wert für A2, A1 bzw. A0 vor jeder Ausführung der MMD-Operation in ein zur Verfügung stehendes kurzes Register eingespeichert werden, oder könnten alle drei Werte im #Rahmen von Movk am Anfang geladen werden.

Später wird der zu TC analoge Algorithmus zum Behandeln eines negativen Übertrags (Borrow) nach einer Subtraktion verwendet. Er ist in 9b gezeigt.

Der abschließende Reduktionsschritt muss nur die oberen zwei Teile von D berücksichtigen, da die unteren zwei Teile in dem letzten Schritt behandelt wurden, also wird (D3|D2|D1|D0)Z := (D'3, D''2, D''1, D0)Z (auch mit TC bezeichnet) tatsächlich implementiert als D1 := D''1 (D3, D2) := TC(D''3, D''2)

Es sei daran erinnert, dass D3 positiv oder negativ werden kann, so dass es „frei floatend" ist.

Schließlich ist ein weiterer Teil des ganzen Algorithmus der Modularreduktionsschritt. Er hat zwei Versionen, eine, die den gewöhnlichen Rest ∊ [0, N[ berechnet, und eine, die den Rest berechnet, der durch N dekrementiert ist, d. h. ∊ [–N, 0]. Die zwei Algorithmen werden in einem Schritt gezeigt, da die Unterschiede nur in der Berechnung von &egr;~ und in der Endreduktion liegen (9c).

Die Registerimplementierung ist in 9d dargestellt.

Bei der Registerimplementierung, wie sie in 9d dargestellt ist, sind sowohl die internen Register bei 900 sowie eine Belegung von externen Registern xdata bei 902 zu Beginn der Berechnung von 9c bzw. 3f dargestellt.

In der Ausgangslage sind die Register des Kryptoprozessors mit den vier Abschnitten D0, D1, D2, D3 der zu reduzierenden Zahl D und mit dem höchstwertigen Abschnitt N2 des Moduls geladen. In dem Arbeitsspeicher 902 befindet sich neben den Operanden A und B, die für die vorliegende Reduktion nicht benötigt werden, auch die beiden anderen Abschnitte N1 und N0 des Moduls N. Hierauf werden erste Berechnungen durchgeführt, um zu den Werten zu gelangen, die für die erste MMD-Operation bei 903 benötigt werden. Die Registerbelegung nach der ersten MMD-Operation 903 ist bei 904 gezeigt. Hierauf werden die Berechnungen bei 905 in 9c bzw. 3f durchgeführt, um die Registerbelegung 906 zu erhalten, die die Ausgangslage für die Schätzung von &egr; 907 ist. Die Registerbelegung nach der Schätzung von &egr; ist bei 908 in 9d gezeigt. Insbesondere sind bei dem in 9d gezeigten Ausführungsbeispiel auch im Wege der Berechnung 907 die beiden weiteren Berechnungen für D ''2 und Q ''0 durchgeführt worden. Dann wird die erste MMD-Operation 909 durchgeführt. Das Ergebnis dieser MMD-Operation ist bei 910 gezeigt. Die daran anschließende Subtraktion bzw. Übertrag- oder Borrow-Behandlung ist bei 911 in 9d schematisch dargestellt. Das Ergebnis vor der zweiten MMD-Operation 913 ist bei 912 dargestellt. Hierauf wird eine Registerbelegung 914 erhalten, die noch einer weiteren Subtraktion 915 mit entsprechender Übertrag/Borrow-Behandlung unterzogen wird, um eine Registerbelegung 916 zu erhalten, die entweder unmittelbar oder nach einer Umsortierung, um die Registerbelegung 917 zu erhalten, als Ausgangspunkt für die Endreduktion verwendet wird.

Für die Endreduktion sind in 9d zwei Möglichkeiten gezeigt. Die erste Möglichkeit bei 950 stellt die Schritte bzw. Registerbelegungen dar, die erforderlich sind, wenn eine Reduktion zu einer Zahl benötigt wird, die zwischen 0 und N ist. Dagegen sind bei 960 die Schritte bzw. Registerbelegungen dargestellt, die benötigt werden, wenn das Ergebnis zwischen 0 und –N sein soll. Insbesondere ist ersichtlich, dass dann, wenn die beiden Entscheidungen 951 und 952 jeweils mit Nein (No) beantwortet werden, keine weiteren Berechnungen nötig sind und das Ausgangsergebnis dieselbe Registerbelegung 953 hat, wie sie bei 917 als Ergebnis der Berechnung 915 erhalten worden ist. Stellt der erste Entscheidungsprozess 951 jedoch fest, dass das Ergebnis E zu groß ist, dass also E2 – N2 größer als Null ist, wird der Rest des Moduls, also N1, N2 über einen Ladevorgang 954 in das Register geladen, um die Registerbelegung 955 zu erhalten. Dann wird bei 956 der Modul N subtrahiert, um ein Ergebnis 957 zu erhalten. Wird dann im Entscheidungsblock 952 festgestellt, dass E2 nicht kleiner als Null ist, so ist das Endergebnis erreicht.

Wird jedoch die erste Entscheidung 951 mit Nein beantwortet und wird die zweite Entscheidung 952 mit Ja beantwortet, so wird bei 958 dieselbe Operation durchgeführt, wie sie bei 954 durchgeführt worden ist. Hierauf wird eine Registerbelegung 959 erreicht. Nach Addition des Moduls bei 975 wird eine Registerbelegung 976 erreicht, die bereits die richtigen Werte für E2, E1 und E0 aufweist.

Die Funktionalitäten für die alternative Reduktion, bei der ein Ergebnis erhalten wird, das kleiner als Null und größer als –N ist, sind ähnlich den in 950 beschriebenen Vorgängen. Allerdings sind die Entscheidungskästen bei 961 und 962 unterschiedlich ausgebildet. Die Entscheidung bei 961 stellt fest, ob das Ergebnis zu klein ist, also ob das Ergebnis kleine als –N ist. Dies wird dadurch festgestellt, dass –E2 – N2 gebildet wird und untersucht wird, ob das Ergebnis größer oder gleich Null ist. Ist dies der Fall, so werden die Modulabschnitte N1, N0 bei 964 in das Register geladen, um eine Belegung bei 965 zu erhalten. Dann wird bei 966 der Modul addiert, um eine Belegung 967 zu erhalten, mit der dann das Endergebnis bei 963 erhalten wird.

Wenn dagegen die Entscheidung im Block 961 mit Nein beantwortet wird und die Entscheidung im Block 962 mit Ja beantwortet wird, so bedeutet dies, dass E2 größer als Null ist. Dann muss wiederum der Rest des Moduls, also N1, N0 in das Register geladen werden, um die Belegung bei 969 zu erhalten. Bei 985 wird dann ein Modul subtrahiert, um die Belegung bei 986 zu erhalten, die dann im Hinblick auf E2, E1 und E0 dem Endergebnis entspricht.

Erneut besteht der Hauptteil der Algorithmus aus den drei MMD-Operationen. Ihre Implementierung wird in einem folgenden Abschnitt erörtert. Der verbleibende Teil besteht aus der Schätzung von &egr;, die in einem späteren Abschnitt erörtert wird, und einigen Elementaroperationen von Addition oder Subtraktion von Komponenten und dem Behandeln von möglichen Überträgen oder negativen Überträgen.

Die ersten zwei Additionen Q'0 := Q0 + D3 und D'2 := D2 + R0 werden keiner Übertragbehandlung unterzogen. In jedem Fall wurde in Anmerkung 7 ersichtlich, dass Q0 nicht viel größer als Z wird. Andererseits kann D '0 so groß wie 2Z werden, aber es ist nicht negativ und deshalb muss diese Ganzzahl als eine Ganzzahl ohne Vorzeichen interpretiert werden! Bezugnehmend auf 12 wird gezeigt, wie die nächsten drei Zeilen zusammen zu implementieren sind: &egr; := estimate(D'2 – (Q'0N1)1 div N2)[+1] D''2 := D'2 – &egr;N2 Q''0 := Q'0 + &egr;

Die Subtraktion (D'1|D'0)Z := (D1 – U1, D0 – U0)Z erfolgt auf eine ähnliche Weise wie bei dem MAZ-Algorithmus, mit dem Unterschied, dass negative Überträge anstelle von Überträgen behandelt werden müssen. Es sei jedoch darauf hingewiesen, dass, falls Q ''0 < 0, dann auch U1 und U0 negativ sind, somit ist die Subtraktion eigentlich eine Addition und man muss wieder Überträge behandeln:

Natürlich besteht eine Möglichkeit, die Reihenfolge der Operationen zu ändern. Auf die gleiche Weise wird die andere Subtraktion (D'''2|D''1)Z := (D''2 – V1, D'1 – V0)Z

Natürlich besteht eine Möglichkeit, die Reihenfolge der Operationen zu ändern. Auf die gleiche Weise wird die andere Subtraktion (D'''2|D''1)Z := (D''2 – V1, D'1 – V0)Z behandelt als:

Es sei daran erinnert, dass D '''2 noch nicht aufgelöst wird. Dies erfolgt in dem Endreduktionsschritt, der nun folgt:

Bei RedZ ist es erwünscht, ein Ergebnis E ∊ [0, N[ zu erhalten. Manchmal ist das Ergebnis aber etwas größer als N oder kleiner als 0. In diesem Fall muss N einmal subtrahiert oder addiert werden. Um zu prüfen, ob E > N, muss E von N subtrahiert werden. Aber leider liegt N nicht voll in Crypto@1408. So wird E2 – N2 berechnet und geprüft, ob diese Differenz ≥ 0 ist. Falls E > N, ist dies sicher der Fall. Es sei darauf hingewiesen, dass auch E2 – N2 = 0 ein Hinweis darauf sein kann, dass E > N, da es immer noch möglich ist, dass E1 > N1. Dies kann jedoch nicht sofort geprüft werden, da zuerst das volle N in Crypto@1408 geladen werden muss. Nur in sehr wenigen Fällen passiert es, dass E2 = N2, während E ≤ N. Da all dies sehr selten auftritt, wird die Zeit aufgebracht und das komplette N in den Crypto@1408 geladen und die Endreduktion durchgeführt: N wird von E subtrahiert. Falls dann die neue Ganzzahl E2 ≥ 0, ist das der Abschluss. Falls E2 negativ wird, muss erneut N addiert werden. Falls E2 von Anfang an negativ war – was ebenfalls sehr selten vorkommt – dann wird auch N in den Crypto@1408 geladen und zu E addiert. Dieser Algorithmus ist formell gegeben durch

Es sei darauf hingewiesen, dass normalerweise, in 99,9 % aller Fälle, beide falls- bzw. if-Bedingungen nicht erfüllt sein werden. Also soll die Implementierung diese Tatsache berücksichtigen. Es soll vermieden werden, das volle N in den Crypto@1408 zu laden, wenn nicht eine der Bedingungen wahr ist, da dies viel Zeit beansprucht! Für Red'Z ist die Endreduktion ziemlich ähnlich

In beiden Fällen muss man sich immer Überträgen und negativer Überträge bewusst sein und sie wie bei den früher in diesem Abschnitt beschriebenen Additionen und Subtraktionen auflösen. Schließlich sei auf die folgende wichtige Anmerkung verwiesen.

Anmerkung 11: Aufgrund der Gleichung (3) gilt Q''0 ∊ [–Z – 1, Z]. Da bei der zweiten und dritten MMD-Operation der zweite Faktor definitiv mod Z reduziert wird, hat das Produkt Q''0 ·Ni immer einen Absolutwert ≤ (Z + 1)(Z – 1) = Z2 – 1.

Implementierung von MMDk

Eingabe für den MMD-Algorithmus ist ein umgewandelter Modul N (in diesem Fall ist dies N2 oder Z), der Multiplikand X (in diesem Fall Bi, D3, Q ''0 ) und der Multiplizierer Y (Ai, Z, Z – N2 und Ni), die in den meisten, aber nicht in allen Fällen außerhalb von Crypto@1408 liegen werden.

1. Falls #N =: k > 704 – 8 – 1 = 695 (Vorzeichenbit, nicht gezählt), muss die MMD-Operation in dem langen Modus von Crypto@1408 berechnet werden. Ansonsten kann der parallele Modus verwendet werden, der im Folgenden erörtert ist. In dem langen Modus ist der Algorithmus in 10a angegeben.

Für den Crypto@1408 ist der Algorithmus in der folgenden 10b veranschaulicht.

2. Zumindest in einem Fall wird der Algorithmus für einen negativen Multiplikanden benötigt. Dies ist jedoch kein Problem, solange X ∊ ]–N, 0]: In diesem Fall wird (Q, R) := MMD(–X, Y; N) berechnet und (–Q + 1, N – R) zurückgegeben, falls R > 0, und (–Q, –R), falls R = 0. Dies ist legitim durch die folgende Beobachtung: Falls –X·Y = Q·N + R, mit R ∊ [0, N[, dann X·Y = –Q·N – R = (–Q + 1)·N + (N – R).

Tatsächlich reicht es in diesem Fall aus, nur (–Q, –R) zurückzugeben, da dieser Algorithmus in diesem Teil mit einem negativen Rest R wirksam ist.

3. Es ist sogar nicht wirklich notwendig, dass X und Y ∊ [0, N[ (oder allgemeiner in ]–N, N[). Es genügt, dass das Produkt X·Y in [0, N2[ liegt. Deshalb kann es zulässig sein, dass X oder Y etwas größer als N ist, solange

  • • Crypto@1408 die Ganzzahl nicht auf eine falsche Weise interpretiert (Vorzeichenbit).
  • • das Produkt X·Y nicht zu groß ist, d. h. in [0, N2[ liegt.

    In 11a ist der Algorithmus in der Weise gegeben, in der er vorzugsweise verwendet wird.

    Der Algorithmus, der bei Crypto@1408 implementiert ist, ist in 11b veranschaulicht.

Vornehmen der Seitenberechnung

In diesem Abschnitt wird eine Implementierung der drei Zeilen &egr; := estimate (D'2 – (Q'0N1)1 div N2) D''2 := D'2 – &egr;N2 Q''0 := Q'0 + &egr; von Red gegeben.

Der Hauptpunkt bei dieser Implementierung ist die Schätzung von D'2 – (Q'0N1)1 div N2 . Durch die gleiche Technik, die bereits mehrere Male verwendet wurde, kann eine Näherung einer Division erhalten werden, indem nur die obersten Bits eines Dividenden und eines Divisors verwendet werden. In diesem Fall werden die 16 obersten (top) Bits (einschließlich Vorzeichenbits) verwendet, d. h. es wird verwendet: D'top2 := D'2 div 2k-16 Q'top2 := Q'2 div 2k-16 Ntop1 := N'1 div 2k-16 Ztop := Z div 2k-16 Ntop2 := ZtopN2 div 2k-16

Da (...)1 bei (Q '0 N1)1 eine Division durch Z bedeutet, wird der Bruch mit Z multipliziert und es erfolgt somit eine Näherung auf die folgende Weise: &egr; := (ZtopD'top2 – Q'top0Ntop1)divNtop2

D 'top2 und Q 'top0 werden durch ein Lesen des höchstwertigen Wortes von D2 und Q '0 erhalten. Die obersten zwei Bytes – erweitertes Vorzeichen – werden in irgendein CPU-Register geladen.

Auch N top1 wird auf die gleiche Weise vorbereitet, aber in diesem Fall muss dies nur einmal während der gesamten Exponentiation erfolgen. (Vorberechnung!) Dann wird das Produkt Q'top0 Ntop1 berechnet. Es ist ein 32-Bit-Wort und wird von Ztop D'top2 subtrahiert. Das Ergebnis sei X genannt. Dieses Ergebnis wird mit N top2 verglichen, das auf die gleiche Weise vorbereitet wird wie N top1 , aber mit einem zusätzlichen Faktor von Ztop. Der Rest ist offensichtlich und in der 11 gezeigt.

Anmerkung 12: Es sei darauf hingewiesen, dass für Red' in jedem Fall ein zusätzlicher Block D'2 := D'2 – N2 Q'0 := Q'0 + 1 hinzugefügt werden muss.

Vorberechnung

Die Vorberechnung erhält die Basis B* und den Modul N* für die Exponentiation. N* hat eine Bitlänge K, d. h. N* ∊ [2K-1, 2K[. Da die Vorberechnung für die Performance nicht relevant ist, werden die Implementierungsaspekte nicht zu detailliert behandelt. Nur einige Hinweise und Anmerkungen zu diesen Punkten:

Umwandeln von N* zu (N2|N1|N0):

Nun sei W := 2k-1 die größte Zweierpotenz kleiner Z gesetzt und geschrieben N* = (N*2|N*1|N*0)W , d. h. N* sei in drei (k – 1)-Bit-Blöcke geteilt. Die Transformation in eine Z-äre Darstellung (N2|N1|N0) := N* ist in 13a gegeben:

Es sei darauf hingewiesen, dass Z umgewandelt wird, so dass wirklich die MMD-Implementierung von 11a und 11b verwendet werden kann. Die zwei Additionsteile werden genau wie bei der Hauptimplementierung, die ab 6 vorgestellt ist, vorgenommen: Die Addition wird komponentenweise durchgeführt und der Übertrag behandelt!

Umwandeln von B* zu (B2|B1|B0)Z

Dies funktioniert auf genau die gleiche Weise wie bei dem letzten Punkt.

Durchführen der Endreduktion (Nachberechnung)

Die Endreduktion nimmt die Ausgabe (A2|A1|A0)Z der letzten modularen Multiplikation der reinen Exponentiation, reduziert diese Zahl modulo N* = (N'2|N'1|N'0)Z := N* und wandelt sie zurück in die binäre Darstellung A* um. So ergibt sich

  • 1. (A '2 |A '1 |A '0 )Z := (A2|A1|A0)Z mod (N '2 |N '1 |N '0 )Z
  • 2. A* := (A '2 |A '1 |A '0 )Z
wobei (N '2 |N '1 |N '0 )z aus Abschnitt 5.5 bekannt ist.

Zu 1. Die Reduktion

wird auf die bereits bekannte Weise durchgeführt: A := A – [A div N]·N, so dass der Algorithmus gegeben werden kann, wie es in 13c gezeigt ist.

Die Division ist diejenige aus dem letzten Abschnitt und es wird die gesamte bereits bekannte Technik verwendet.

Zu 2. Umwandeln in binäre Form

Dies ist eigentlich nur die Berechnung A := A'2·Z2 + A'1·Z + A'0

Es wurden drei unterschiedliche Verfahren beschrieben, um eine 2.048-Bit-RSA-Berechnung zu implementieren. Außerdem wurde die Performance einer derartigen Implementierung des Algorithmus bewertet, wobei einige Systemaspekte, die performancesdominierend sind, berücksichtigt wurden, wie z. B. ein Bewegen von Ganzzahlen in Crypto@1408 hinein und aus demselben heraus. Es stellte sich heraus, dass der erfindungsgemäße bevorzugte Algorithmus hinsichtlich Geschwindigkeit und Verwendung von externem Speicher der beste ist. Obwohl er für m = 3 nur geeignet ist, um RSA bis zu 2048 Bits (+ 16 zur Randomisierung) zu implementieren. Falls ein Bedarf an längeren Bitlängen besteht, dann scheint der Algorithmus II (Fischer-Sedlak-Seifert mit MMD) das beste angemessene Verfahren zu sein. Alternativ kann auch m = 4, 5, ... gewählt werden.

Nachfolgend wird Bezug nehmend auf 18 das erfindungsgemäße Rechenwerk zum Reduzieren einer Eingabe-Zahl D bezüglich eines Moduls N erläutert. Das Rechenwerk 180 umfasst einen Rechenwerks-Eingang für die Eingabe-Zahl D, der mit 181 bezeichnet ist, sowie einen Rechenwerkseingang 182 für den Modul N. Sowohl der Modul als auch die Eingabe-Zahl liegen in Abschnitten vor, wie sie vorzugsweise rechts von dem Rechenwerk 180 in 18 dargestellt sind. Insbesondere umfassen die Abschnitte N0, N1, N2 unterschiedliche Wertigkeiten. Die höchste Wertigkeit hat der Abschnitt N2, wie es anhand eines Registerblocks 183 gezeigt ist, der die Abschnitte in absteigender Wertigkeit von links nach rechts speichert. Somit hat bezüglich des Moduls der Abschnitt N2 die höchste Wertigkeit. Der Abschnitt N1 hat eine kleinere Wertigkeit und der Abschnitt N0 die niedrigste Wertigkeit. Entsprechend ist es bei der zu reduzierenden Eingabe-Zahl D, die sehr wahrscheinlich einen dritten höchstwertigen Abschnitt aufweist, da sie ja deutlich größer als der Modul N sein kann. Wieder ist der Abschnitt D3 der höchstwertige Abschnitt. Der niederwertige Abschnitt D2 folgt dem höchstwertigen Abschnitt. Ein wieder niederwertiger Abschnitt D1 folgt dem Abschnitt D2 in der Wertigkeit, und der niedrigstwertige Abschnitt D0 wird, wie es ebenfalls in 18 dargestellt ist, durch modulare Reduktion der Eingabe-Zahl mit der Aufteilungszahl Z als Modul gebildet. Die Abschnitte stellen somit unter Berücksichtigung der Aufteilungszahl Z die Eingabe-Zahl D bzw. den Modul N dar.

Insbesondere umfasst das Rechenwerk 180 ferner eine Einrichtung 184 zum Schätzen eines Ergebnisses einer ganzzahligen Division der Eingabe-Zahl durch den Modul unter Verwendung eines höchstwertigen Abschnitts der Zahl, eines höchstwertigen Abschnitts des Moduls und der Aufteilungszahl. Die Einrichtung 184 ist ferner ausgebildet, um das geschätzte Ergebnis, also z. B. Q~ 0, oder einen von dem geschätzten Ergebnis abgeleiteten Schätzwert Q'0 (3d, 3e, 3f) oder Q''0 (9c) an einem Ausgang 185 auszugeben bzw. über einen Ausgang 185 zu speichern. Die Speicherung findet vorzugsweise in einem Register des Rechenwerks statt, wobei hier nur ein kurzes Register benötigt wird, da die Zahl Q~ 0 Q'0 (3d, 3e, 3f) oder Q''0 (9c) kleiner als der höchstwertige Abschnitt N2 des Moduls ist. Die Einrichtung 184 zum Schätzen führt vorzugsweise die Funktionalität von „Evaluate &egr;", wie es in 3c dargestellt ist, aus.

Das Rechenwerk 180 umfasst ferner eine Einrichtung 186 zum Berechnen eines Reduktionsergebnisses, das an einem Rechenwerksausgang 187 ausgebbar ist, wobei die Einrichtung 186 ausgebildet ist, um basierend auf einer Subtraktion eines Produkts aus dem Modul und dem geschätzten Ergebnis oder dem Schätzwert, der von der Einrichtung 184 geliefert wird, von der Zahl ihr Ergebnis zu berechnen. Die Einrichtung 186 ist somit ausgebildet, um ausgehend von dem geschätzten Ergebnis der ganzzahligen Division vorzugsweise die Funktionalität auszuführen, die für E in 3c dargestellt ist. Der Wert E ist somit das Reduktionsergebnis bei dem in 3c gezeigten Ausführungsbeispiel der vorliegenden Erfindung.

Wie es bereits anhand der 3c und 3d ausgeführt worden ist, wird es bevorzugt, einen weiteren Schätzvorgang durchzuführen, nämlich zusätzlich zu der Schätzung des Ergebnisses der ganzzahligen Division, die durch eine Schätzeinrichtung 184a, die Teil der Einrichtung 184 in 18 ist, auch eine Schätzung des Schätzfehlers, der durch die Einrichtung 184a gemacht wird, durchzuführen. Diese Schätzung des Schätzfehlers wird durch eine Einrichtung 184b erreicht, wie sie in 19a für den Algorithmus von 3d bis 3f dargestellt ist. 19b zeigt den analogen Fall für den Algorithmus von 9c. In beiden Figuren ist ein Addierer 184c vorgesehen, der ausgebildet ist, um die Ausgaben der Einrichtungen 184a und 184b wie in den Figuren gezeigt zu addieren, um den Schätzwert aus dem geschätzten Ergebnis abzuleiten.

Vorzugsweise ist die Einrichtung 184b zum Schätzen des Schätzfehlers ausgebildet, um einen Schätzwert &egr;~ zu erhalten, der höchstens um &dgr; vom tatsächlichen Schätzfehler &egr; abweicht. Bei dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird der Schätzfehler &egr;~ so abgeschätzt, dass der höchste Restfehler gleich –1,0 oder +1 ist. Bei dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung wird zur Berechnung des Schätzfehlers &egr;~ die in 3e dargestellte Berechnung für &egr;~ durchgeführt, die dahingehend besonders ist, dass zur Schätzung des Schätzfehlers lediglich kurze Zahlen benötigt werden, wie beispielsweise D2, also den zweit-höchstwertigen Abschnitt der Zahl D, R~ 0, also den Rest der modularen Reduktion von dem Produkt aus D3, der Zahl Z und bezüglich des obersten Abschnitts N2 des Moduls. Ferner wird noch der Ausdruck (Q~0N1)1 verwendet, welcher gleich dem Ergebnis der ganzzahligen Division durch die Zahl Z von dem Produkt von Q~ 0 und N1 ist. An dieser Stelle sei darauf hingewiesen, dass N1 der zweit-höchstwertige Abschnitt des Moduls N ist, wie es dargelegt worden ist.

Zur Schätzung des Schätzfehlers werden somit Abschnitte des Moduls außer dem niedrigstwertigen Abschnitt N0 benötigt, und werden von der Zahl D lediglich der zweithöchste Abschnitt benötigt. Andere Abschnitte werden nicht benötigt.

Alternativ kann der Schätzfehler &egr;~ auch derart berechnet werden, wie es für &egr;~ in 3f ausgebildet ist. Der Unterschied bedingt sich aus der unterschiedlich definierten MMD-Operation, die in 3f gezeigt ist.

Generell ist die Einrichtung zum Schätzen des Schätzfehlers jedoch ausgebildet, um den Schätzfehler lediglich unter Verwendung des zweithöchsten Abschnitts D2 der Zahl sowie den beiden höchsten Abschnitten des Moduls N zu berechnen, wobei vorzugsweise die in 19a bzw. 3e oder 3f dargestellten Gleichungen eingesetzt werden. Alternativ wird es bevorzugt, die Funktionalität der 19b zu implementieren, die auf dem Algorithmus in 9c basiert.

Nach der Schätzung des Schätzfehlers, durch die der geschätzte Schätzfehler &egr;~ erhalten wird, muss noch die Funktionalität der Einrichtung 186 von 18 ausgeführt werden. Hierzu ist die Einrichtung 186 in vorzugsweise zwei Funktionalitäten 186a und 186b ausgeführt. Die Einrichtung 186a ist dazu da, um die Subtraktion durchzuführen, nämlich die Subtraktion, wie sie beispielsweise in 3e für den Wert E dargestellt ist, wobei Q '0 gleich dem geschätzten Ergebnis Q~ 0 für die ganzzahlige Division plus dem geschätzten Schätzfehler ist, der durch die Einrichtung 184b von 19a oder 19b berechnet worden ist. Das hierbei erhaltene Ergebnis kann dann noch einer Endreduktion unterzogen werden, um gewissermaßen den zulässigen Schätzfehler &dgr; zu berücksichtigen. Wenn insbesondere E größer oder gleich N ist, dann muss N von dem Ergebnis E subtrahiert werden, um das endgültige Reduktionsergebnis zu erhalten. Wenn jedoch E kleiner als Null ist, dann muss ein Modul N hinzuaddiert werden, um das Reduktionsergebnis am Ausgang der Einrichtung 186b zu erhalten, wie es in 3e dargestellt ist.

Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung ist die Einrichtung 186a zum Durchführen der Subtraktion ausgebildet, wie es in 3f oder in 9c dargestellt ist. Die Implementierungen der Einrichtung 186a auf die Art und Weise, wie sie in 3f oder in 9c dargestellt ist, stellt sicher, dass für sämtliche Berechnungen, die in dieser Implementierung vorkommen, lediglich Abschnitte von Zahlen benötigt werden, deren Länge immer kleiner als die Zahl Z ist, so dass für sämtliche Berechnungen, die in diesen Implementierungen vorkommen, immer nur ein Rechenwerk mit einer Länge benötigt wird, die kleiner als die Zahl Z ist.

Die „Aufsplittung" der Subtraktion, wie sie allgemein Bezug nehmend auf 20a für 3f oder bezugnehmend auf 20b für 9c bei 186a mit langen Zahlen dargestellt ist, wird erfindungsgemäß durch MMD-Operationen und Subtraktionsoperationen erreicht. Insbesondere kann die Aufsplittung der „langen" Subtraktion in kürzere Subtraktionen damit erreicht werden, dass – ausgehend von dem niederwertigen Abschnitt N0 des Moduls N – eine erste MMD-Operation durchgeführt wird, wie es bei 200a in 21 für den Algorithmus von 9c beispielhaft dargestellt ist. Die Ergebnisse der ersten MMD-Operation, die so ausgebildet ist, wie es z. B. in 9c in der sechstletzten Zeile dargestellt ist, werden dann einer Einrichtung 200b zum Durchführen einer ersten Subtraktion zugeführt.

Die Einrichtung zum Durchführen der ersten Subtraktion erhält ferner den niedrigstwertigen Abschnitt D0 und den bezüglich der Wertigkeit folgenden höherwertigen Abschnitt D1 der zu reduzierenden Zahl. Die Einrichtung 200b zum Durchführen der ersten Subtraktion liefert damit bereits den niedrigstwertigen Abschnitt der reduzierten Zahl D '0 , der dann, wenn die Endreduktion nicht nötig ist, bereits das Ergebnis ist, oder der nur noch zusammen mit den restlichen Abschnitten der Zahl D2 der Endreduktion unterzogen werden muss. Lediglich beispielhaft ist der niederstwertige Abschnitt D '0 , der durch die Einrichtung 186a von 20b, deren speziellere Ausgestaltung in 21 dargestellt ist, in 21 mit 210 angedeutet.

Die Einrichtung 186a zum Durchführen der Subtraktion umfasst ferner eine Einrichtung 200c zum Durchführen einer zweiten MMD-Operation, die ausgebildet ist, um unter anderem nunmehr einen höherwertigen Abschnitt N1 des Moduls zu erhalten. Die Ergebnisse V1, V0 der zweiten MMD-Operation 200c, wie sie beispielsweise durch die viertletzte Zeile von 9c berechnet wird, werden dann einer Einrichtung 200d zum Durchführen einer zweiten Subtraktion zugeführt, die die beiden höherwertigen Abschnitte D ''1 und D '''2 der Ergebniszahl liefert, die in dem Register 210 gespeichert ist. Die Zahl, die durch die Abschnitte D '''2 , D ''1 und D '0 dargestellt ist, muss nunmehr noch einer (positiven oder negativen) Endreduktion bzw. Überprüfung unterzogen werden, um den noch zugelassenen Schätzfehler &dgr; von –1,0, +1 zu berücksichtigen bzw. zu „eliminieren".

Dann wird in einem Ergebnisregister 212 das Reduktionsergebnis, wie es durch die Einrichtung 186b in 20b erhalten wird, als Endergebnis E geliefert, wobei das Endergebnis wieder durch Abschnitte E0, E1, E2 erhalten, die wiederum zusammen Bezug nehmend auf die Aufteilungszahl Z das endlich gesuchte Ergebnis darstellen.

Wie es bereits vorstehend dargelegt worden ist, wird es für bestimmte Anwendungen bevorzugt, das MMD-Ergebnis subtrahiert um ein Modul N zu erhalten. Hierzu wird auf 1d bzw. auf die 1417 verwiesen. Diese „spezielle" Reduktion, die eigentlich um ein „N" zu viel reduziert, kann durch die erfindungsgemäße Implementierung ohne weiteres einfach integriert werden, indem, wie es in 9c bei 220 dargestellt ist, der geschätzte Schätzfehler &egr; einfach um „+1" im Vergleich zu seinem berechneten Wert, der gemäß der in 9c dargestellten Gleichung erhalten wird, inkrementiert wird.

Ferner wird für diese spezielle Reduktion RedZ bei der Endreduktion dieser Sachverhalt berücksichtigt, indem dann, wenn das Ergebnis, wie es z. B. von 21 erhalten wird, dann einer Subtraktion mit dem Modul N unterzogen wird, wenn das Ergebnis größer als Null ist. Ist das Ergebnis jedoch kleiner als –N, so wird ein Modul N hinzuaddiert.

Der Übersichtlichkeit halber wurde in den 3d, 3e, 3f und 9c die bevorzugte aber beispielhafte Aufteilung der Algorithmuszeilen auf die einzelnen Einrichtungen 184a, 184b, 184c, 186a und 186b durch waagrechte Linien in den einzelnen Figuren eingezeichnet.

Abhängig von den Gegebenheiten kann das erfindungsgemäße Verfahren zum Berechnen eines Ergebnisses in Hardware oder in Software implementiert werden. Die Implementierung kann auf einem digitalen Speichermedium, insbesondere einer Diskette oder CD mit elektronisch auslesbaren Steuersignalen erfolgen, die so mit einem programmierbaren Computersystem zusammenwirken können, dass das Verfahren ausgeführt wird. Allgemein besteht die Erfindung somit auch in einem Computer-Programm-Produkt mit einem auf einem maschinenlesbaren Träger gespeicherten Programmcode zur Durchführung eines erfindungsgemäßen Verfahrens, wenn das Computer-Programm-Produkt auf einem Rechner abläuft. In anderen Worten ausgedrückt kann die Erfindung somit als ein Computer-Programm mit einem Programmcode zur Durchführung des Verfahrens realisiert werden, wenn das Computer-Programm auf einem Computer abläuft.

  • [1] W. Fischer, „Vorrichtung und Verfahren zum Berechnen eines Ergebnisses aus einer Division", DE Patent #102,05,713, 7. Aug. 2003.
  • [2] W. Fischer, H. Sedlak, J.-P. Seifert, „Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation", DE Patent #102,19,158, 9. Dez. 2004
  • [3] W. Fischer, J.-P. Seifert, „Vorrichtung und Verfahren zum Umrechnen eines Termes", DE Patentanmeldung #102,19,161,A1, 20. Nov. 2003.
  • [4] W. Fischer, H. Sedlak, J.-P. Seifert, „Vorrichtung und Verfahren zum Berechnen eines ganzzahligen Quotienten", DE Patent #102,19,164, 2. Dez. 2004.
  • [5] W. Fischer, H. Sedlak, J.-P. Seifert, „Vorrichtung und Verfahren zum Berechnen einer Multiplikation mit der Verschiebung des Multiplikanden, insbesondere bei der kryptographischen Berechnung", DE Patent #102,60,655, 24. Jun. 2004.
  • [6] W. Fischer, H. Sedlak, J.-P. Seifert, „Modulare Multiplikation mit paralleler Berechnung der Look-Ahead-Parameter u.s. bei der kryptographischen Berechnung", DE Patent #102,60,660, 9. Jun. 2004.
  • [7] W. Fischer, J.-P. Seifert, „Increasing the bitlength of a crypto-coprocessor", Proc. of CHES '02, Springer LNCS, Bd. 2523, S. 71–81, 2002.
  • [8] W. Fischer, J.-P. Seifert, „Unfolded modular multiplication", Proc. of ISAAC '03, Springer LNCS, 2003.
  • [9] A. Menezes, P. van Oorschot, S. Vanstone, „Handbook of Applied Cryptography", CRC Press, 1997.
  • [10] P. L. Montgomery, „Modular multiplication without trial division", Math. of Computation, 44: 519–521, 1985.
  • [11] H. Sedlak, „The RSA cryptographic Processor: The first High Speed One-Chip Solution", Proc. of EUROCRYPT '87, Springer LNCS, Bd. 293, S. 95–105, 198.


Anspruch[de]
Vorrichtung zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Multiplikator (A), einem Multiplikanden (B) und einem Modul (N), mit folgenden Merkmalen:

einer Einrichtung (10) zum Bereitstellen des Multiplikanden (B) in wenigstens drei Abschnitten (B0, B1, B2), wobei jeder Abschnitt eine Anzahl von Stellen aufweist, die kleiner als eine halbe Anzahl von Stellen des Multiplikanden ist, und wobei die wenigstens drei Abschnitte sämtliche Stellen des Multiplikanden umfassen; und

einer Einrichtung (12) zum sequentiellen Berechnen, wobei die Einrichtung (12) zum sequentiellen Berechnen ausgebildet ist,

um unter Verwendung einer MultModAdd-(MMA-) Operation (51) mit einem höherwertigen Abschnitts (B2) des Multiplikanden (B) als Operanden ein erstes Zwischenergebnis zu berechnen (14),

um unter Verwendung einer MultModAdd-(MMA-) Operation (52) mit einem niedrigerwertigen Abschnitt (B1) des Multiplikanden (B) und dem ersten Zwischenergebnis als Operanden ein zweites Zwischenergebnis zu berechnen (16), und

um unter Verwendung einer MultModAdd-(MMA-) Operation (53) mit einem noch niedrigerwertigen Abschnitts (B0) des Multiplikanden (B) und dem zweiten Zwischenergebnis ein drittes Zwischenergebnis zu berechnen und zu speichern, wobei das dritte Zwischenergebnis das Ergebnis der modularen Multiplikation darstellt, wenn der Multiplikand in genau drei Abschnitte aufgeteilt ist, oder wobei das Ergebnis der modularen Multiplikation von dem dritten Zwischenergebnis durch eine weitere sequentielle Berechnung ableitbar ist, wenn der Multiplikand in mehr als drei Abschnitte aufgeteilt ist.
Vorrichtung nach Anspruch 1,

bei der die Einrichtung (10) zum Bereitstellen ausgebildet ist, um wenigstens ein Register zu haben, das eine Länge hat, die kleiner als eine Länge des gesamten Multiplikanden (B) ist, die aber größer oder gleich einem Abschnitt des Multiplikanden ist,

und wobei die Einrichtung (12) zum Berechnen ausgebildet ist, um einen Abschnitt des Multiplikanden in das Register während einer Berechnung zu laden.
Vorrichtung nach Anspruch 1 oder 2,

bei der die Einrichtung (10) zum Bereitstellen ausgebildet ist, um auch den Multiplikator (A) und den Modul (N) in jeweils wenigstens drei Abschnitte aufzuteilen, und

wobei die Einrichtung (12) zum Berechnen ausgebildet ist, um sowohl die Abschnitte des Multiplikators (A) als auch des Moduls (N) für eine oder mehrere Berechnungen zu verwenden.
Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (12) zum sequentiellen Berechnen ausgebildet ist, um zehn oder weniger Register mit einer Länge aufzuweisen, die wenigstens so groß ist wie eine Länge eines Abschnitts, und die kleiner als eine gesamte Länge des Moduls (N) ist. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (12) zum sequentiellen Berechnen ausgebildet ist, um folgende Gleichung auszuführen: C = [(A·B2 mod N)·Z + A·B1 mod N]·Z + A·B0 mod N, wobei C das dritte Zwischenergebnis ist, wobei A der Multiplikator ist, wobei Z = 2i ist, wobei i eine Anzahl von Stellen der Abschnitte ist, wobei B2 der höchstwertige Abschnitt des Multiplikanden ist, wobei B1 ein niedrigerwertiger Abschnitt des Multiplikanden ist, wobei B0 der niederstwertige Abschnitt des Multiplikanden ist, wobei N der Modul ist, und wobei mod eine modulare Reduktionsoperation anzeigt. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung zum Berechnen ausgebildet ist, um folgende Berechnung auszuführen: C1 := MMA(A, B2, 0; N) – N C2 := MMA(A, B1, C1; N) – N C3 := MMA(A, B0, C2; N), wobei N der Modul ist, wobei A der Multiplikator ist, wobei B2 der höchstwertige Abschnitt des Multiplikanden ist, wobei B1 ein niedrigerwertiger Abschnitt des Multiplikanden ist und wobei B0 ein niedrigstwertiger Abschnitt des Multiplikanden ist, wobei C1 das erste Zwischenergebnis ist, wobei C2 das zweite Zwischenergebnis ist, und wobei C3 das dritte Zwischenergebnis ist, und wobei MMA die MultModAdd-Operation mit einem jeweiligen Abschnitt des Multiplikanden darstellt. Vorrichtung nach einem der vorhergehenden Ansprüche, die als konfigurierbares Rechenwerk (40) ausgebildet ist, wobei das Rechenwerk eine Bit-Slice-Struktur aufweist, wobei jeder Bit-Slice einen Rechenwerkteil und einen Registerteil aufweist, wobei das konfigurierbare Rechenwerk ferner eine Registerkonfigurationseinrichtung (42) aufweist, die ausgebildet ist, um das Rechenwerk (40) in einen Lang-Modus oder einen Kurz-Modus zu konfigurieren, wobei das Rechenwerk (40) im Lang-Modus eine bestimmte erste Anzahl von langen Registern hat, wobei das Rechenwerk (40) im Kurz-Modus eine zweite Anzahl von kurzen Registern hat, wobei die zweite Anzahl größer als die erste Anzahl ist, und wobei eine Länge eines kurzen Registers derart ist, dass ein Abschnitt des Multiplikanden in dem kurzen Register speicherbar ist. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die MMA-Operation eine Multiplikations-Additions-Operation (55a) und eine nachfolgende Reduktionsoperation (55b) aufweist, die auf ein Ergebnis der Multiplikations-Additions-Operation ausgeführt wird. Vorrichtung nach Anspruch 8, bei der die Einrichtung zum Berechnen ausgebildet ist, um folgende Multiplikations-Additions-Operation durchzuführen: D := A·Bi + C·Z ∈ [–NZ, NZ[, wobei D ein Ergebnis der Multiplikations-Additions-Operation ist, wobei Bi ein Abschnitt des Multiplikanden ist, wobei C ein Zwischenergebnis ist und wobei Z = 2i ist, wobei i eine Anzahl von Stellen des Abschnitts ist. Vorrichtung nach Anspruch 8 oder 9, bei der die Einrichtung zum Berechnen ausgebildet ist, um folgende Reduktionsoperation durchzuführen:

D mod N,

wobei D ein zu reduzierender Wert ist, wobei N der Modul ist und wobei mod eine modulare Reduktionsoperation darstellt.
Vorrichtung nach Anspruch 9, bei der die Einrichtung (12) zum Berechnen ausgebildet ist, um eine MMD-Operation auszuführen, wobei die MMD-Operation folgendermaßen lautet: MMD(A, B) = (A·B div N, A·B mod N), wobei A der Multiplikator ist, wobei B der Multiplikand ist, wobei N der Modul ist, wobei div das ganzzahlige Ergebnis einer Division liefert und wobei mod eine modulare Reduktion darstellt. Vorrichtung nach einem der vorhergehenden Ansprüche, die ausgebildet ist, um die modulare Multiplikation innerhalb einer kryptographischen Berechnung durchzuführen, wobei der Multiplikator (A), der Multiplikand (B) und der Modul (N) Parameter der kryptographischen Berechnung sind. Vorrichtung nach Anspruch 12, bei der die kryptographische Berechnung eine Verschlüsselung, eine Entschlüsselung, eine Signaturerzeugung oder eine Signaturverifikation ist. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der alle Abschnitte des Multiplikanden dieselbe Anzahl von Stellen aufweisen. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (12) zum Berechnen ausgebildet ist, um nur eine Multiplikation von Zahlen eine Länge durchzuführen, die kleiner oder gleich der Anzahl von Stellen in einem Abschnitt ist. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (10) zum Bereitstellen ausgebildet ist, um genau drei Abschnitte für den Multiplikanden bereitzustellen. Vorrichtung nach Anspruch 8, bei der die Einrichtung (10) zum Berechnen ausgebildet ist, um die Multiplikations-Additions-Operation (MAZ) folgendermaßen auszuführen: wobei A der Multiplikator ist, wobei Bi ein Abschnitt des Multiplikanden ist, wobei C ein Zwischenergebnis eines vorherigen Schritts ist, wobei N der Modul ist, wobei Z = 2i ist wobei i eine Anzahl von Stellen des Abschnitts darstellt, wobei D ein Ergebnis der Multiplikation-Addition ist, wobei i und j Laufindizes sind, wobei MMD eine MultModDiv-Operation darstellt, wobei treat carry eine Übertragbehandlungsfunktion ist,. Vorrichtung nach Anspruch 8, bei der die Reduktionsoperation folgendermaßen durchgeführt wird oder folgendermaßen durchgeführt wird oder folgendermaßen durchgeführt wird oder folgendermaßen durchgeführt wird oder folgendermaßen durchgeführt wird: wobei D ein zu reduzierender Wert ist, wobei N der Modul ist, wobei div eine Ganzzahl-Divisionsoperation ist, wobei Q0 ein Ergebnis der Ganzzahldivision ist und wobei E ein Ergebnis der Reduktionsoperation ist, wobei Z = 2i, wobei i gleich eine Anzahl von Stellen des Abschnitts ist, wobei N2 ein höchstwertiger Abschnitt des Moduls ist, wobei &egr; eine Hilfsgröße ist, wobei Q~ 0 ein Schätzwert für ein ganzzahliges Ergebnis ist, wobei D3 ein höchstwertiger Abschnitt der zu reduzierenden Größe ist, wobei &egr;~ ein weiterer Schätzwert ist, wobei „if" ein Bedingungsoperand ist, wobei „else if" ein weiterer Bedingungsparameter ist, wobei „end" eine Schleife beendet, wobei MMD eine MultModDiv-Operation ist, wobei Q~ 0 und R~ 0 Hilfsgrößen sind, wobei D2 ein niederwertiger Abschnitt des zu reduzierenden Parameters ist, wobei D0 ein niederstwertiger Abschnitt des zu reduzierenden Parameters ist, wobei „treat borrow/carry" Funktionen zum Behandeln eines negativen bzw. positiven Übertrags ist. Vorrichtung nach einem der vorhergehenden Ansprüche,

bei der die Einrichtung (12) zum Berechnen ausgebildet ist, um folgende Sequenz von Schritten durchzuführen: C := MMA'Z(A, B2, 0; N) C' := MMA'Z(A, B1, C; N) E := MMAZ(A, B0, C'; N), wobei MMA 'Z eine modifizierte MMA-Operation ist, die ein Ergebnis liefert, das durch Subtraktion des Moduls von dem Ergebnis von einer nicht-modifizierten MMA-Operation erhalten wird, wobei A der Multiplikator ist, wobei B2 der höchstwertige Abschnitt des Multiplikanden ist, wobei B1 ein niederwertiger Abschnitt des Multiplikanden ist und wobei B0 ein niederstwertiger Abschnitt des Multiplikanden ist, wobei C das erste Zwischenergebnis ist, wobei C' das zweite Zwischenergebnis ist und wobei E das dritte Zwischenergebnis bzw. Endergebnis ist.
Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Einrichtung (12) zum Berechnen ausgebildet ist, um zunächst eine Modultransformation als Vorberechnung durchzuführen, und um eine Modulrücktransformation als Nachberechnung durchzuführen. Vorrichtung nach einem der vorhergehenden Ansprüche, die ferner einen externen Speicher aufweist, wobei der externe Speicher ausgebildet ist, um die Abschnitte des Multiplikators, des Multiplikanden und des Moduls zu speichern, wobei ein höchstwertiger Abschnitt des Moduls nicht im externen Speicher, sondern in einem rechenwerksinternen Register gespeichert ist. Vorrichtung nach Anspruch 21, die ausgebildet ist, um das Ergebnis der modularen Multiplikation ebenfalls in einer Anzahl von Abschnitten zu liefern, wobei die Einrichtung (12) zum Berechnen ferner ausgebildet ist, um nach Abschluss einer modularen Multiplikation die Abschnitte des Ergebnisses der modularen Multiplikation in den externen Speicher anstelle von Abschnitten gleicher Wertigkeit des Multiplikators zu speichern. Vorrichtung nach einem der vorhergehenden Ansprüche, die als Rechenwerk ausgebildet ist,

bei der die Einrichtung zum sequentiellen Berechnen ausgebildet ist, um ein Ergebnis der MultModAdd-(MMA-) Operation unter Verwendung von drei Operanden und einem Modul gemäß folgender Gleichung zu berechnen, MMA(V, W, X; Y) = [VW + XZ] mod Y, wobei V, W, X der erste, zweite bzw. dritte Operand sind,

wobei Y der Modul ist, und wobei Z eine Aufteilungszahl ist, gemäß der der Multiplikand (B) in Multiplikandenabschnitte (B0, B1, B2) aufgeteilt ist, wobei ein Multiplikandenabschnitt in einer MMA-Operation der zweite Operand ist, und

wobei ein Register des Rechenwerks kürzer als eine Zahlenlänge des Multiplikanden (B) und größer oder gleich einer Zahlenlänge des Multiplikandenabschnitts (B0, B1, B2) ist.
Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation mit einem Multiplikator (A), einem Multiplikanden (B) und einem Modul (N), mit folgenden Schritten:

Bereitstellen (10) des Multiplikanden (B) in wenigstens drei Abschnitten (B0, B1, B2), wobei jeder Abschnitt eine Anzahl von Stellen aufweist, die kleiner als eine halbe Anzahl von Stellen des Multiplikanden ist, und wobei die wenigstens drei Abschnitte sämtliche Stellen des Multiplikanden umfassen; und

sequentielles Berechnen (12), wobei der Schritt des sequentiellen Berechnens (12) ausgeführt wird,

indem unter Verwendung einer MultModAdd-(MMA-)Operation (51) mit einem höherwertigen Abschnitts (B2) des Multiplikanden (B) als Operanden ein erstes Zwischenergebnis berechnet wird (14),

indem unter Verwendung einer MultModAdd-(MMA-)Operation (52) mit einem niedrigerwertigen Abschnitt (B1) des Multiplikanden (B) und dem ersten Zwischenergebnis als Operanden ein zweites Zwischenergebnis berechnet wird (16), und

indem unter Verwendung einer MultModAdd-(MMA-)Operation (53) mit einem noch niedrigerwertigen Abschnitts (B0) des Multiplikanden (B) und dem zweiten Zwischenergebnis ein drittes Zwischenergebnis berechnet und gespeichert wird, wobei das dritte Zwischenergebnis das Ergebnis der modularen Multiplikation darstellt, wenn der Multiplikand in genau drei Abschnitte aufgeteilt ist, oder wobei das Ergebnis der modularen Multiplikation von dem dritten Zwischenergebnis durch eine weitere sequentielle Berechnung ableitbar ist, wenn der Multiplikand in mehr als drei Abschnitte aufgeteilt ist.
Computer-Programm mit einem Programmcode zum Durchführen des Verfahrens nach Patentanspruch 23, wenn das Computer-Programm auf einem Rechner abläuft.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com