DE10219164B4

DE10219164B4 - Vorrichtung und Verfahren zum Berechnen eines ganzzahligen Quotienten

Info

Publication number: DE10219164B4
Application number: DE2002119164
Authority: DE
Inventors: Wieland Dipl.-Math. Dr. Fischer; Jean-Pierre Dipl-.Inf. Dr. Seifert
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2002-04-29
Filing date: 2002-04-29
Publication date: 2004-12-02
Anticipated expiration: 2022-04-30
Also published as: TW200400442A; AU2003224137A1; WO2003093970A3; DE10219164A1; WO2003093970A2

Abstract

Vorrichtung zum Berechnen eines ganzzahligen Quotienten eines Terms (T) bezüglich eines Moduls (N), wobei der Term ein Produkt aus einem binären Multiplikator (M) und einem Multiplikanden (C) aufweist, mit folgenden Merkmalen:
einer Verarbeitungseinrichtung (10) zum Verarbeiten von Bits des Multiplikators (N) in mehreren Verarbeitungsschritten, wobei die Verarbeitungseinrichtung (10) ausgebildet ist, um in einem Verarbeitungsschritt ein bezüglich des Moduls reduziertes Zwischenergebnis (Z) zu berechnen, das von dem einen oder den mehreren Bits des binären Multiplikators abhängt, die in dem einen Verarbeitungsschritt betrachtet werden;
einer Einrichtung (12) zum Protokollieren von Reduktionsinformationen in dem einen Verarbeitungsschritt und zum Protokollieren von Ordnungsinformationen über durch eine oder mehrere durch den einen Verarbeitungsschritt betroffene Stellen des ganzzahligen Quotienten; und
einer Auswertungseinrichtung (14) zum Auswerten der Reduktionsinformationen und der Ordnungsinformationen aus den Verarbeitungsschritten, um den ganzzahligen Quotienten (Q) zu erhalten.

Description

Die vorliegende Erfindung bezieht sich auf Rechenalgorithmen und insbesondere auf Rechenalgorithmen, die für kryptographische Anwendungen benötigt werden.

Insbesondere in der Public-Key-Kryptographie, jedoch auch in anderen Kryptographiegebieten, wachsen die Schlüssellängen stetig. Dies ist darin begründet, daß auch die Sicherheitsanforderungen an solche kryptographische Algorithmen immer mehr zunehmen. Anhand des RSA-Verfahrens als Vertreter eines asymmetrischen Kryptographiekonzepts, also eines Public-Key-Verfahrens, nimmt die Sicherheit gegenüber sogenannten Brute-Force-Angriffen mit der verwendeten Schlüssellänge zu. Brute-Force-Angriffe sind Angriffe auf einen kryptographischen Algorithmus, bei dem durch Durchprobieren sämtlicher Möglichkeiten auf einen Schlüssel geschlossen werden soll. Es ist unmittelbar einsichtig, daß mit zunehmender Schlüssellänge die Zeit, die theoretisch für einen Brute-Force-Angriff benötigt wird, um alle Möglichkeiten durchzuprobieren, stark ansteigt.

In diesem Zusammenhang sei angemerkt, daß zu früheren Zeiten RSA-Anwendungen mit Schlüssellängen von 512 Bits als ausreichend angesehen wurden. Aufgrund technischer und mathematischer Fortschritte der „Gegenseite" wurden dann die Schlüssellängen für typische RSA-Anwendungen auf 1024 Bits erhöht. Inzwischen wird von manchen Seiten die Ansicht vertreten, daß auch diese Schlüssellänge nicht ausreichend ist, so daß RSA-Schlüssellängen von 2048 Bits angestrebt werden.

Wenn andererseits existierende kryptographische Coprozessoren, wie z. B. auf SmartCards, betrachtet werden, so ist zu sehen, daß selbstverständlich der Wunsch besteht, auch RSA- Anwendungen mit beispielsweise 2048 Bits Schlüssellängen auf kryptographischen Schaltungen laufen zu lassen, die eigentlich nur für Schlüssellängen von z. B. 1024 Bits entwickelt worden sind. So ist es gerade ein Kennzeichen von arithmetischen Coprozessoren für existierende SmartCard-Anwendungen, daß sie für eine feste Bitlänge entwickelt worden sind, die nicht für die neuesten Sicherheitsanforderungen geeignet sind, d. h. zu klein sind. Dies führt dazu, daß beispielsweise ein 2048-Bit-RSA-Algorithmus auf 1024 Bit-Coprozessoren nicht effizient gehandhabt werden kann. Für RSA-Anwendungen ist beispielsweise der Chinesische Restsatz (CRT; CRT = Chinese Remainder Theorem) bekannt, bei dem eine modulare Exponentiation mit großer Schlüssellänge in zwei modulare Exponentiationen mit halb so großer Schlüssellänge zerlegt wird, wonach die Ergebnisse der beiden modularen Exponentiationen halber Länge entsprechend zusammengefaßt werden.

In jüngster Zeit hat sich herausgestellt, daß der chinesische Restsatz besonders anfällig gegenüber DFA-Angriffen (DFA = Differential Fault Analysis) ist.

Ein Problem bei vielen Verfahren ist daher das „Aufdoppeln" der sogenannten modularen Multiplikation, die eine zentrale Operation in kryptographischen Berechnungen ist. So kann eine modulare Exponentiation in viele modulare Multiplikationen zerlegt werden, d. h. in eine Operation, bei dem ein Produkt eines ersten Operanden A und eines zweiten Operanden B in einer Restklasse bezüglich eines Moduls N berechnet wird. Wenn die Operanden A und B jeweils 2n Bits haben, so werden typischerweise Rechenwerke verwendet, die eine Länge von 2n Bits haben. Diese Rechenwerke werden aufgrund ihrer hohen Länge als Langzahlrechenwerke bezeichnet, im Gegensatz zu beispielsweise klassischen 8-, 16-, 32- oder 64-Bit-Architekturen, die z. B. für PC- oder Workstation-Prozessoren eingesetzt werden.

Wünsche bestehen daher dahingehend, eine modulare Multiplikation A·B mod N mit Zahlen A, B und N der Bit-Länge 2n auf einem n-Bit-Rechenwerk auszuführen. Dies ist sehr zeitaufwendig, da die Zahlen A, B, N, ... immer nur bruchstückweise geladen werden können, weshalb konventionelle Methoden, sofern sie nicht gänzlich versagen, organisatorisch aufwendig und fehleranfällig sind. In der Technik gibt es mehrere Verfahren, mit denen dieses Problem bisher gelöst worden ist. Diese Verfahren sind unter dem Stichwort Montgomery-Multiplikation, normale Multiplikation, z. B. mit Karatsuba-Ofman und späterer Reduktion, wie z. B. Barret-Reduktion, bekannt.

Ein weiteres Konzept, bei dem eine Montgomery-Rechnung in einem „CRT-Fenster" verwendet wird, ist in P. Pailler, „Lowcost double size modular exponentiation or how to stretch your cryptocoprocessor" dargelegt.

Sämtliche derartigen Konzepte sind aufwendig hinsichtlich der Rechenzeit und der Datenorganisation und daher nicht immer effizient.

In der am gleichen Tag eingereichten deutschen Patentanmeldung mit dem Titel „Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation", wird ein Konzept beschrieben, bei dem eine modulare Multiplikation für Operanden von 2n Bits in mehrere sogenannte MMD-Operationen umgesetzt werden, für die Operanden der halben Länge, also mit n Bits, ausreichend sind. Eine MMD-Operation liefert neben dem Rest, der sich durch A × B mod N ergibt, auch das Ergebnis der entsprechenden ganzzahligen Division, d. h. der DIV-Operation, wobei dieses Ergebnis auch als ganzzahliger Quotient Q bezeichnet ist.

Allgemein führt die Operation T mod N zu einem Rest R, wenn ein Term T bezüglich eines Moduls N reduziert wird. Die Operation T div N liefert dagegen den ganzzahligen Quotienten hinsichtlich des Moduls N, so daß der Term T aus Q × N + R rekonstruierbar ist. Die MMD-Operation (MMD = MultModDiv) dient daher einer Umrechnung eines beliebigen Terms T in einen ganzzahligen Quotienten Q und einen Rest R bezüglich eines Moduls N.

In der üblichen modularen Arithmetik, die für Kryptographietechniken verwendet wird, wird normalerweise das Ergebnis der DIV-Operation, also der ganzzahlige Quotient nicht benötigt und auch nicht berechnet. Das oben beschriebenen Konzept basiert jedoch darauf, auch die DIV-Information, also den ganzzahligen Quotienten zu verwerten. So können auch andere Anwendungen in der Technik existieren, bei denen nicht nur das Ergebnis der MOD-Operation, also der Rest, benötigt wird, sondern bei denen auch der ganzzahlige Quotient, also das Ergebnis der DIV-Operation benötigt wird.

Eine bekannte, effiziente und oft verwendete Möglichkeit, um die modulare Multiplikation zu berechnen, ist in der Technik als Montgomery-Multiplikation bekannt und z. B. im „Handbook of Applied Cryptography", Menezes, van Oorschot, Vanstone, CRC Press, Seiten 600–603, beschrieben. Die Montgomery-Reduktion ist eine Technik, die eine effiziente Implementation der modularen Multiplikation erlaubt, ohne daß der klassische modulare Reduktionsschritt explizit ausgeführt wird. Allgemein gesagt wird bei der Montogomery-Reduktion die Divisionsoperation durch einfache Verschiebungsoperationen ausgedrückt.

Mittlerweile ist auch eine Erweiterung der Montgomery-Multiplikationsoperation auf den elliptischen Körper GF(2ⁿ) bekannt. Diese Erweiterung ist in „Montgomery Multiplication in GF(2^k)", Koc, Azar, Designs, Codes and Cryptography, Bd. 14, 1998, S. 57–69, beschrieben. Diese Erweiterung ist ferner in „A Scalable and Unified Multiplier Architecture for Finite Fields Z/NZ and GF(2ⁿ)", Erkay Savas u. a., Cryptographic Hardware and Embedded Systems (CHESS 2000), S. 281-289, Springer Lecture Notes, beschrieben.

Nachteilig an der Montgomery-Multiplikation über Z/NZ oder GF(2ⁿ) ist die Tatsache, daß zwar die hardwaremäßig schlecht implementierbare Divisionsoperation zur modularen Reduktion durch Verschiebungsoperationen umgangen wird, aber keine Look-Ahead-Verfahren oder Vorausschau-Verfahren eingesetzt werden, um die modulare Multiplikationsoperation hardwaremäßig zu beschleunigen.

Die DE 3631992 C2 offenbart ein Verfahren, bei dem die modulare Multiplikation über Z/NZ unter Verwendung eines Multiplikations-Vorausschau-Verfahrens und unter Verwendung eines Reduktions-Vorausschau-Verfahrens beschleunigt werden kann. Das in der DE 3631992 C2 beschriebene Verfahren wird auch als ZDN-Verfahren bezeichnet und anhand von 6 näher beschrieben. Nach einem Startschritt 900 des Algorithmus werden die globalen Variablen M, C und N initialisiert. Ziel ist es, folgende modulare Multiplikation zu berechnen: Z = M·C mod N.

M wird als der Multiplikator bezeichnet, während C als der Multiplikand bezeichnet wird. Z ist das Ergebnis der modularen Multiplikation, während N der Modul ist.

Hierauf werden verschiedene lokale Variablen initialisiert, auf die zunächst nicht näher eingegangen werden braucht. Anschließend werden zwei Vorausschau-Verfahren angewandt. Im Multiplikations-Vorausschau-Verfahren GEN_MULT_LA wird unter Verwendung verschiedener Look-Ahead-Regeln ein Multiplikations-Verschiebungswert s_Z sowie ein Multiplikations-Vorausschau-Parameter a berechnet (910). Hierauf wird der gegenwärtige Inhalt des Z-Registers einer Links-Verschiebungs-Operation um s_Z-Stellen unterzogen (920).

Im wesentlichen parallel dazu wird ein Reduktions-Vorausschau-Verfahren GEN_Mod_LA (930) durchgeführt, um einen Reduktionsverschiebungswert s_N und einen Reduktions-Parameter b zu berechnen. In einem Schritt 940 wird dann der gegenwärtige Inhalt des Modul-Registers, also N, um s_N Stellen verschoben, um einen verschobenen Modulwert N' zu erzeugen. Die zentrale Drei-Operanden-Operation des ZDN-Verfahrens findet in einem Schritt 950 statt. Hierbei wird das Zwischenergebnis Z' nach dem Schritt 920 zu dem Multiplikanden C, der mit dem Multiplikations-Vorausschau-Parameter a multipliziert ist, und zu dem verschobenen Modul N', der mit dem Reduktions-Vorausschau-Parameter b multipliziert ist, addiert. Je nach aktueller Situation können die Vorausschau-Parameter a und b einen Wert von +1, 0 oder –1 haben.

Ein Fall besteht darin, daß der Multiplikations-Vorausschau-Parameter a +1 beträgt, und daß der Reduktion-Vorausschau-Parameter b –1 beträgt, so daß zu einem verschobenen Zwischenergebnis Z' der Multiplikand C hinzu addiert wird, und der verschobene Modul N' davon subtrahiert wird. a wird u. a. einen Wert gleich 0 haben, wenn das Multiplikations-Vorausschau-Verfahren mehr als eine voreingestellte Anzahl von einzelnen Links-Verschiebungen zulassen würde, also wenn s_Z größer als der maximal zulässige Wert von s_Z ist, der auch als k bezeichnet wird. Für den Fall, daß a gleich 0 ist, und daß Z' aufgrund der vorausgehenden modularen Reduktion, also der vorausgehenden Subtraktion des verschobenen Moduls noch ziemlich klein ist, und insbesondere kleiner als der verschobene Modul N' ist, muß keine Reduktion stattfinden, so daß der Parameter b gleich 0 ist.

Die Schritte 910 bis 950 werden so lange durchgeführt, bis sämtliche Stellen des Multiplikanden abgearbeitet sind, also bis m gleich 0 ist, und bis auch ein Parameter n gleich 0 ist, welcher angibt, ob der verschobene Modul N' noch größer als der ursprüngliche Modul N ist, oder ob trotz der Tatsache, daß bereits sämtliche Stellen des Multiplikanden abgearbeitet sind, noch weitere Reduktionsschritte durch Subtrahieren des Moduls von Z durchgeführt werden müssen.

Abschließend wird noch bestimmt, ob Z kleiner als 0 ist. Falls dies der Fall ist, muß, um eine abschließende Reduktion zu erreichen, der Modul N zu Z hinzuaddiert werden, damit schließlich das korrekte Ergebnis Z der modularen Multiplikation erhalten wird. In einem Schritt 960 ist die modulare Multiplikation mittels des ZDN-Verfahrens beendet.

Der Multiplikations-Verschiebungswert s_Z sowie der Multiplikations-Parameter a, welche im Schritt 910 durch den Multiplikations-Vorausschau-Algorithmus berechnet werden, ergeben sich durch die Topologie des Multiplikators sowie durch die eingesetzten Vorausschau-Regeln, die in der DE 3631992 C2 beschrieben sind.

Der Reduktions-Verschiebungswert s_N und der Reduktions-Parameter b werden, wie es ebenfalls in der DE 3631992 C2 beschrieben ist, durch Vergleich des gegenwärtigen Inhalts des Z-Registers mit einem Wert 2/3 mal N bestimmt. Aufgrund dieses Vergleiches trägt das ZDN-Verfahren seinen Namen (ZDN = Zwei Drittel N).

Das ZDN-Verfahren, wie es in 6 dargestellt ist, führt die modulare Multiplikation auf eine Drei-Operanden-Addition (Block 950 in 6) zurück, wobei zur Steigerung der Rechenzeiteffizienz das Multiplikations-Vorausschau-Verfahren und damit einhergehend das Reduktions-Vorausschau-Verfahren eingesetzt werden. Im Vergleich zur Montgomery-Reduktion für Z/NZ kann daher ein Rechenzeitvorteil um einen Faktor in der Größenordnung von 3 erreicht werden.

Nachteilig an den oben beschriebenen Multiplikationskonzepten ist, daß lediglich die Modulo-Operation berechnet wird, daß jedoch nicht die DIV-Operation berechnet wird, also die Operation, die den ganzzahligen Quotienten Q bezüglich des Moduls N des Produkts aus dem Multiplikator M und dem Multiplikanden C liefert, so daß das Produkt C × M = Q·N + Z darge stellt ist. Wie es jedoch ausgeführt worden ist, ist der ganzzahlige Quotient jedoch für bestimmte Anwendungen nützlich, wobei eine dieser Anwendungen, wie es vorstehend beschrieben worden ist, darin besteht, eine modulare Multiplikation mit Zahlen einer bestimmten Länge auf einem Rechenwerk der halben Länge effizient auszuführen.

Die DE 699 00 127 T2 offenbart ein verbessertes Verfahren zur Ausführung einer ganzzahligen Division, bei dem ein Wort in ein erstes Register geladen wird, bei dem Nullen in ein zweites Register geladen werden, bei dem Nullen ferner in ein drittes Register geladen werden, und bei denen ein anderes Wort in ein viertes Register geladen wird. Hierauf werden Schritte einer ganzzahligen Division, eines Ladens eines weiteren Worts in ein Register sowie einer Verschiebung von Inhalten von verschiedenen Registern, einer Subtraktion von Werten, einer, abhängig von dem Subtraktionsergebnis, erfolgenden Dekrementierung oder Ladung der Wörter in ein Register und eine entsprechende Verschiebung sowie weitere Schritte durchgeführt, um schließlich das Ergebnis einer ganzzahligen Division zu erhalten.

Die DE 698 02 016 T2 offenbart ein Verfahren und eine Vorrichtung zum Durchführen einer ganzzahligen Divisionsoperation mit einem modulo-arithmetischen Koprozessor auf der Basis des Montgomery-Verfahrens, wobei im Verlauf der Division wenigstens eines der Worte mit einer Anzahl von Bits des Zählers oder des Quotienten Bit für Bit in ein Register für das Verschieben von Bits geladen wird, und das Wort in das Register in einer ersten Reihenfolge eingegeben wird und Bit für Bit von dem Register in umgekehrter Reihenfolge gegenüber der ersten Reihenfolge ausgegeben wird.

Die Aufgabe der vorliegenden Erfindung besteht darin, ein Konzept zum einfach und effizient implementierbaren Berechnen eines ganzzahligen Quotienten zu schaffen.

Diese Aufgabe wir durch eine Vorrichtung nach Anspruch 1 oder ein Verfahren nach Anspruch 16 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß bei Prozessoren zum Berechnen des Rests Z eines Produkts aus einem Multiplikator und einem Multiplikanden – und optional aus einer Addition dieses Produkts mit einem dritten Operanden multipliziert mit dem Faktor 2ⁿ –, die die Bits des Multiplikators in mehreren Verarbeitungsschritten sequentiell abarbeiten oder „abscannen", der ganzzahlige Quotient ohne Eingriff in das Rechenwerk selbst und ferner ohne einen oder einen minimalen Eingriff in den Controlteil, das das Rechenwerk steuert, extrahierbar ist.

Bei der üblichen modularen Arithmetik ist der ganzzahlige Quotient, also das Ergebnis der DIV-Operation mangels geeigneter Verwendung immer ignoriert worden. Erfindungsgemäß wird der ganzzahlige Quotient unter Verwendung eines Prozessors zum Berechnen des Rests eines Terms bezüglich eines Moduls erhalten, derart, daß in jedem Verarbeitungsschritt, in dem der Prozessor ein bezüglich des Moduls reduziertes Zwischenergebnis berechnet, Reduktionsinformationen einerseits und Ordnungsinformationen andererseits, welche sich auf Stellen des ganzzahligen Quotienten beziehen, die in dem jeweiligen Verarbeitungsschritt betroffen sind, mitprotokolliert werden. Dann, nachdem die Multiplikatorbits mittels der mehrere Ver arbeitungsschritte abgearbeitet sind, werden die mitprotokollierten Reduktionsinformationen und Ordnungsinformationen von den jeweiligen Schritten ausgewertet, um daraufhin ohne aufwendige arithmetische Operationen den ganzzahligen Quotienten zu erhalten.

Bei einem bevorzugten Ausführungsbeispiel werden parallel zum Verarbeiten der Multiplikatorbits durch die Verarbeitungseinrichtung Protokollregister geführt, wobei Bits bestimmter Ordnung, die durch die Ordnungsinformationen bestimmt ist, unter Verwendung der Reduktionsinformationen nach jedem Verarbeitungsschritt gesetzt oder nicht gesetzt werden. Werden zwei oder mehrere solche Protokollregister eingesetzt, so ist die Einrichtung zum Auswerten in der Lage, durch einfaches Addieren oder Subtrahieren der Protokollregister nach der Abarbeitung sämtlicher Multiplikatorbits den ganzzahligen Quotienten zu erhalten.

Die Erfindung ist insbesondere dahin gehend vorteilhaft, daß keine Informationen benötigt werden, die über Informationen hinausgehen, die ohnehin von einer solchen Verarbeitungseinrichtung zum Berechnen der Modulo-Operation ausgegeben werden. Der ganzzahlige Quotient wird somit gewissermaßen „kostenlos" (insbesondere bezüglich der Rechenzeit) und ohne Eingriffe in das Rechenwerk der Verarbeitungseinrichtung erhalten. Lediglich eine Protokollierungseinrichtung muß vorgesehen werden, die die benötigten Reduktionsinformationen oder Ordnungsinformationen am Ende jedes Verarbeitungsschrittes aus dem Controlteil extrahiert.

Bei einer abschließenden Auswertung der Protokollinformationen durch eine Auswertungseinrichtung ergibt sich dann der ganzzahlige Quotient, ohne daß eine einzige Änderung am festverdrahteten Rechenwerk nötig war.

Diese Tatsache ist insbesondere dahin gehend von Bedeutung, daß kryptographische Rechenwerke typischerweise Langzahl- Rechenwerke sind, die auf bestimmte Operationen, wie z. B. die modulare Multiplikation, optimiert sind. Eingriffe in solche Langzahl-Rechenwerke, die typischerweise Addierer mit 1024 oder mehr Einzeladdierern oder „Bit-Slices" umfassen, sind im Entwurf aufwendig, fehleranfällig und dahin gehend nachteilhaft, daß wieder komplette Funktionstests durchzuführen sind. Insbesondere für sicherheitskritische Anwendungen, für die üblicherweise Kryptographie-Algorithmen eingesetzt werden, ist der Sicherheitsaspekt von besonderer Bedeutung, da sensible Informationen, wie beispielsweise Geldbeträge oder persönliche Informationen, verarbeitet werden, wenn z. B. an Smartcards oder allgemein Chipkarten gedacht wird.

Das erfindungsgemäße Verfahren ist ferner dahin gehend vorteilhaft, daß es außerdem wenig rechenzeitintensiv ist, was insbesondere dann von Bedeutung ist, wenn aufwendige kryptographische Algorithmen zu berechnen sind, und zwar mit Prozessoren, die aufgrund der Tatsache, daß ihre Chipfläche begrenzt ist, wenn wieder an Chipkarten gedacht wird, begrenzte Rechen- und Speicherressourcen haben.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend bezug nehmend auf die beiliegenden Zeichnungen detailliert erläutert. Es zeigen:
1 ein Blockschaltbild einer erfindungsgemäßen Vorrichtung zum Berechnen eines ganzzahligen Quotienten;
2 ein Ablaufdiagramm eines einfachen modularen Multiplikationsalgorithmus;
3 ein Ablaufdiagramm des in 2 gezeigten einfachen Multiplikationsalgorithmus, bei dem neben der Modulo-Operation auch die DIV-Operation ausgeführt wird;
4 ein zusammengefaßtes Ablaufdiagramm des bekannten ZDN-Algorithmus;
5 ein Ablaufdiagramm des ZDN-Algorithmus zum zusätzlichen Berechnen des ganzzahligen Quotienten; und
6 ein detailliertes Ablaufdiagramm des bekannten ZDN-Algorithmus.
1 zeigt ein Blockschaltbild einer erfindungsgemäßen Vorrichtung zum Berechnen eines ganzzahligen Quotienten eines Terms T bezüglich eines Moduls N, wobei der Term ein Produkt aus einem binären Multiplikator M und einem binären Multiplikanden C aufweist. Die Vorrichtung umfaßt eine Verarbeitungseinrichtung 10, die sich in ein Rechenwerk 10a und ein Controlteil 10b aufgliedert. Das Rechenwerk besteht typischerweise aus einem Langzahladdierer für zwei oder mehr Operanden, während der Controlteil 10b ausgebildet ist, um das Rechenwerk zu steuern, damit dasselbe sequentiell die Multiplikatorbits abarbeitet und schließlich, wenn alle Multiplikatorbits abgearbeitet sind, das Ergebnis Z der modularen Reduktion des Terms, der das Produkt C·M aufweist, liefert.
Die erfindungsgemäße Vorrichtung umfaßt ferner eine Protokollierungseinrichtung 12 zum Protokollieren von Reduktionsinformationen in den jeweiligen Schritten und zum Protokollieren von Ordnungsinformationen über durch eine oder mehrere durch den jeweiligen Verarbeitungsschritt betroffene Stellen des ganzzahligen Quotienten. Die Protokollierungseinrichtung 12 ist wirksam mit dem Controlteil 10b gekoppelt, um die Protokollierungsinformationen für jeden Schritt zu extrahieren. Wenn der Controlteil 10b einer ferner vorgesehenen Auswertungseinrichtung 14 signalisiert, daß alle Multiplikatorbits abgearbeitet sind und das Endergebnis Z vorliegt, greift die Auswertungseinrichtung 14 auf die Protokollierungseinrichtung 12 zu, um die Reduktionsinformationen und die Ordnungsinfor mationen auszuwerten, um schließlich den ganzzahligen Quotienten Q auszugeben.
Hardware-technisch wird es bevorzugt, die modulare Reduktion durch Subtraktion des Moduls durchzuführen, wobei in einem Verarbeitungsschritt je nach Implementierung des Rechenwerks 10a eine oder mehrere Modul-Subtraktionen stattfinden können. Werden, wie es nachfolgend erläutert wird, Multiplikations-Look-Ahead-Algorithmen und ferner noch Reduktions-Look-Ahead-Algorithmen eingesetzt, so kann in einem Verarbeitungsschritt der Fall auftreten, daß ein Modul zu dem Zwischenergebnis hinzuaddiert wird. Diese Reduktionsinformationen, also ob ein Modul subtrahiert wird, ob ein Modul addiert wird, oder ob, was ebenfalls auftreten kann, weder eine Addition des Moduls noch eine Subtraktion des Moduls auftritt, können von der Protokollierungseinrichtung 12 in jedem Verarbeitungsschritt protokolliert werden. Die Ordnungsinformationen beziehen sich darauf, welche Stellen des Quotienten durch den jeweiligen Verarbeitungsschritt tangiert werden. So werden die Multiplikatorbits typischerweise von oben, also vom MSB aus (MSB = Most Significant Bit) ausgehend abgearbeitet oder abgescannt. Die Ordnungsinformationen können bei einfacheren modularen Multiplikationsalgorithmen direkt der Ordnung des in einem Schritt betrachteten Multiplikatorbits entsprechen. Wird lediglich ein Multiplikations-Look-Ahead-Algorithmus eingesetzt, so werden in einem Verarbeitungsschritt mehrere Bits des Multiplikators betrachtet und verarbeitet. In diesem Fall werden die Ordnungsinformationen von den mehreren Bits des Multiplikators abhängen. Im Falle gekoppelter Multiplikations-Look-Ahead-Algorithmen und Reduktions-Look-Ahead-Algorithmen hängen die Ordnungsinformationen indirekt von der Ordnung der in einem Verarbeitungsschritt betrachteten Multiplikatorbits ab. Dieser Zusammenhang ist, wie es für Look-Ahead-Algorithmen typisch ist, einerseits datenabhängig und andererseits von der Vorgeschichte bestimmt.
Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung ist die Protokollierungseinrichtung aufgrund der Hardware-technischen einfachen Implementierbarkeit als Registersatz mit einem oder mehreren Registern ausgebildet, welche Schritt für Schritt beschrieben werden und schließlich, nach der Verarbeitung des kompletten Multiplikators durch die Auswertungseinrichtung in geeigneter Weise ausgewertet, wie z. B. addiert oder subtrahiert, werden, um den ganzzahligen Quotienten Q zu erhalten.
Im nachfolgenden wird Bezug nehmend auf 2 ein einfacher Multiplikationsalgorithmus dargestellt, der auch als „Schulbuchalgorithmus" bekannt ist. Dieser Algorithmus erhält als Eingabe den Modul N, den Multiplikanden C, welcher definitionsgemäß kleiner als der Modul N ist, und den Multiplikator M, der aus binären Multiplikatorbits M₀ (lsb) bis M_m–1 (msb) besteht und größer als 0 ist. Dieser Algorithmus liefert als Ausgabe Z = C × M mod N. In einem ersten Initialisierungsschritt wird die Ordnung des Multiplikators i auf m – 1 initialisiert. Ferner wird das Z-Register, das während der Verarbeitung als Zwischenergebnisregister und schließlich als Endergebnisregister fungiert, ebenfalls initialisiert (20). Hierauf wird in einer Stufe 21 untersucht, ob das gerade betrachtete Bit des Multiplikators, also M_i gleich 0 oder 1 ist. Ist das Bit gleich 0, so wird lediglich eine Multiplikation mit dem Faktor 2 oder eine Verschiebung um eine Stelle im Z-Register durchgeführt (22a). Ist das Bit dagegen gleich 1, so wird der Inhalt des Registers um eine Stelle nach links verschoben, was einer Multiplikation mit 2 entspricht, und es wird ferner, wie es aus einem Block 22b ersichtlich ist, der Multiplikand C hinzuaddiert. Die modulare Reduktion findet dahin gehend statt, daß zunächst in einer Stufe 23 untersucht wird, ob der Inhalt des Zwischenergebnisregisters Z größer oder gleich N ist. Wird diese Frage bejaht, so wird ein erstes Mal der Modul N von dem Zwischenergebnisregister Z subtrahiert (24). Dann wird erneut untersucht, ob der jetzige Inhalt des Zwischenergebnisregisters Z größer oder gleich N ist (25). Wird diese Frage wieder bejaht, so wird ein weiteres Mal der Modul N subtrahiert (26). Dieses Prozedere wird wiederholt, bis i gleich 0 ist, was in einem Block 27 überprüft wird. Wird die Frage mit Ja beantwortet, so ist der Algorithmus zu Ende. Wird diese Frage dagegen mit Nein beantwortet, so wird i in einem Block 28 um „1" dekrementiert, und es wird eine weitere Iterationsschleife unter Verwendung der Blöcke 21 bis 27 durchlaufen.
Nachfolgend wird anhand von 3 die erfindungsgemäße Erweiterung des in 2 gezeigten Algorithmus, also die Funktionalität der Protokollierungseinrichtung 12 von 1 und der Auswertungseinrichtung 14 von 1 erläutert. Elemente in 3, die die gleichen Bezugszeichen tragen wie in 2 haben dieselbe Funktion und werden nicht erneut erläutert. Die Protokollierungseinrichtung umfaßt bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung zur Erweiterung des in 2 gezeigten bekannten „Schulbuchalgorithmus" zwei Hilfsregister Q und Q', die in einem Schritt 20' initialisiert werden. Abhängig von der Beantwortung der Frage im Block 23, also ob das Zwischenergebnis Z, das durch den Schritt 22a und den Schritt 22b erhalten worden ist, größer oder gleich N ist, werden Bits der Ordnung i in dem ersten Hilfsregister Q_i oder im zweiten Hilfsregister Q'_i mit „0" beschrieben. Die Reduktionsinformationen bestehen hier in den „Nullen", die an durch die Ordnungsinformationen bestimmten Stellen i der Register eingetragen werden. War das Zwischenergebnis Z kleiner als N, wie es im Block 23 bestimmt worden ist, wurde keine Modulsubtraktion durchgeführt, was sich unmittelbar darin äußert, daß die entsprechenden Hilfsregisterbits gleich 0 gesetzt werden. Wird dagegen eine Modulsubtraktion (Schritt 24) durchgeführt, so wird das Bit i des ersten Hilfsregisters Q auf 1 gesetzt, während das Bit des zweiten Hilfsregisters Q'_i auf 0 gesetzt wird, wie es in einem Block 30b zu sehen ist.
Wird eine zweite Modulsubtraktion durchgeführt (Block 26 von 3), so werden sowohl das Bit i des ersten Hilfsregisters Q als auch das Bit i des zweiten Hilfsregisters Q' auf 1 gesetzt, wie es durch einen Block 30c zu sehen ist. Dieses Prozedere wird für jeden Verarbeitungsschritt durchgeführt, bis im Block 27 bestimmt worden ist, daß i gleich 0 ist. Dann wird die Auswertungseinrichtung 14 von 1 aktiv, um die beiden Register Q und Q' zu addieren, wie es in einem Block 32 dargestellt ist, um als Ergebnis schließlich den ganzzahligen Quotienten Q zu erhalten. Die Funktionalität der Protokollierungseinrichtung wird somit durch die Blöcke 30a, 30b, 30c implementiert, während die Funktionalität durch die Auswertungseinrichtung 14 von 1 durch den Block 32 in 3 implementiert wird.
Aus 3 wird ersichtlich, daß keine Änderung am grundsätzlichen Algorithmus erforderlich ist, um die Quotienteninformation zu erhalten. Im Hinblick auf 1 bedeutet dies, daß sowohl das Rechenwerk 10a als auch der Controlteil 10b der Verarbeitungseinrichtung 10 nicht geändert werden müssen und somit zur Berechnung der Quotienteninformation nicht neu entwickelt und getestet werden müssen.
Aus 3 wird ferner ersichtlich, daß das Mit-Protokollieren der Reduktionsinformationen und der Ordnungsinformationen keinen weiteren Rechenschritt benötigt. Lediglich die Auswertungseinrichtung, die die beiden Register addieren muß, benötigt einen Addierzyklus, der jedoch nicht ins Gewicht fällt, wenn bedacht wird, daß die Größen N, C, M z. B. 1024 Stellen haben, was bei dem in 3 gezeigten Algorithmus bedeutet, daß die Iterationsschleife 1024 Mal durchlaufen werden muß.
Der in 3 gezeigte Algorithmus kann einfach dahin gehend erweitert werden, um nicht nur den Term C × M zu verarbeiten, sondern einen Term C × M + D × 2ⁿ. Dies kann einfach dadurch erreicht werden, daß in dem Initialisierungsschritt 20' das Zwischenergebnis Z nicht auf 0 initialisiert wird, sondern auf D initialisiert wird. Aus diesem Grund trägt die Operation, die durch die in 3 gezeigte Schaltung ausgeführt wird, den Namen Initialisierungs-MMD-Operation, wenn das Zwischenergebnisregister Z vor dem ersten Iterationsschritt auf einen Wert D initialisiert wird. In diesem Zusammenhang steht MMD für MultModDiv, um anzuzeigen, daß der in 3 gezeigte Algorithmus sowohl das modular reduzierte Ergebnis des Terms als auch den ganzzahligen Quotienten des Terms C × M + D × 2ⁿ liefert, wobei sich für D gleich 0 die übliche Multiplikation ergibt.
4 zeigt eine etwas komprimierte Darstellung von 6, nämlich den bekannten ZDN-Algorithmus, der vorstehend erläutert worden ist. Ein Initialisierungsblock 40 zeigt die für die vorliegende Erfindung bedeutsamen Größen i, Z und c. Wieder kann Z entweder auf 0 oder auf D initialisiert werden, um entweder eine MMD-Operation oder eine Initialisierungs-MMD-Operation auszuführen.
Wie es durch einen nachfolgenden Block dargestellt ist, erzeugt die ZDN-Einrichtung 910, 920, 930 von 6 einen Multiplikations-Verschiebungswert s_Z, der üblicherweise immer größer 0 ist, einen Multiplikator-Bit-Wert s_M, der anzeigt, wie viele Multiplikator-Bits in einem Look-Ahead-Schritt verarbeitet worden sind, den Reduktions-Verschiebungswert s_N, sowie den Multiplikations-Look-Ahead-Parameter a und den Reduktions-Look-Ahead-Parameter b. Die Multiplikator-Bit-Ordnungszahl i wird nach jedem Schritt um s_M reduziert. Die Größe c gibt an, an welcher Stelle eines Puffers für den Modul das Komma des Moduls, also das LSB des ursprünglichen Moduls steht. Die Größe c wird nach jedem Schritt durch c + s_N geändert.
In einem Schritt 940 findet dann die Modul-Verschiebung statt, die durch Multiplikation des alten Inhalts des Modul-Registers N mit einem Faktor 2^s _N darstellbar ist. In einem Schritt 950 findet dann die bereits Bezug nehmend auf 6 beschriebene 3-Operanden-Addition statt, die so lange fortgesetzt wird, bis i gleich 0 ist und c ebenfalls gleich 0 ist (Block 42). Ist dies der Fall, wird in einem Schritt 44 untersucht, ob das Zwischenergebnisregister Z kleiner als 0 ist. Ist dies der Fall, so wird noch einmal der Modul N hinzuaddiert (Block 46), da der Rest der modularen Multiplikation, also Z, per Definition größer als 0 sein muß. Wird dagegen Block 42 mit Ja beantwortet, wo wird eine weitere Iteration durchgeführt, um eines oder mehrere Multiplikatorbits, je nach Look-Ahead-Eigenschaft des Multiplikators zu verarbeiten.
Im nachfolgenden wird anhand von 5 die erfindungsgemäße Erweiterung des in den 4 und 6 gezeigten bekannten ZDN-Algorithmus dargestellt. Gleiche Bezugszeichen in den 4 und 5 bedeuten gleiche Elemente. Aus diesem Grund werden diese Elemente nicht noch einmal erläutert. Der durch einen Block 910, 920, 930 bezeichnete ZDN-Prozessor liefert wieder s_Z, s_N, a und b. Hierauf wird der in dem Initialisierungsblock 40' initialisierte Quotienten-Ordnungswert j, welcher auf m initialisiert worden ist, in einem Block 50 verringert, und zwar um die Differenz aus dem Multiplikations-Verschiebungswert s_Z und dem Reduktions-Verschiebungswert s_N. Stellt der Multiplikations-Look-Ahead-Algorithmus, welcher für den Multiplikations-Verschiebungswert s_Z verantwortlich ist, fest, daß das Zwischenergebnis nach oben verschoben werden soll, also zu höherwertigen Bits hin, so wird dies hinsichtlich der Ordnungsinformationen der Protokollierungseinrichtung, welche durch Block 50 dargestellt ist, dahin gehend berücksichtigt, daß geringerwertige Bits des Quotienten betroffen sind. Die Ordnung eines Quotientenbits im aktuellen Schritt ist daher um (s_Z – s_N) niedriger als die Ordnung des entsprechenden Quotientenregisterbits aus dem vorherigen Schritt.
Ist dagegen ein positiver Reduktions-Verschiebungswert s_N vorhanden, so bedeutet dies, daß der Inhalt des Modul-Registers N um den Faktor 2^s _N größer ist als im vorherigen Schritt. Wenn ein solcher „vergrößerter" Modul subtrahiert wird, was durch einen Reduktions-Look-Ahead-Parameter b von „–1" bewirkt wird, so wird dies in den Ordnungsinformationen (Block 50, Parameter j) dahin gehend berücksichtigt, daß höherwertige Bits des ganzzahligen Quotienten betroffen sind, als im vorherigen Iterationsschritt.
Die Reduktionsinformationen sind tabellarisch in einem Block 52 von 5 dargestellt. Die Protokollierungseinrichtung verwendet wieder zwei Hilfsregister Q und Q', wobei die Bitwerte in den beiden Registern von dem Reduktions-Parameter b abhängen. Ist b durch die ZDN-Einrichtung zu 0 berechnet worden, so findet überhaupt keine Reduktion statt. Daher werden die Bits der Ordnung j beider Register Q und Q' auf 0 gesetzt. Ist der Reduktions-Parameter b dagegen gleich „1", so wurde in der 3-Operanden-Operation zum aktuellen Zwischenergebnis ein Modul hinzuaddiert. Dies wird im Block 52 dadurch berücksichtigt, daß das entsprechende Bit j des zweiten Hilfsregisters Q' zu 1 gesetzt wird, während das entsprechende Bit des ersten Hilfsregisters zu 0 gesetzt wird. Wird dagegen ein Modul subtrahiert, also tatsächlich eine Reduktion durchgeführt, was durch einen Reduktions-Parameter von „–1" dargestellt wird, so äußert sich dies in den beiden Hilfsregistern dahin gehend, daß das entsprechende Bit j des ersten Hilfsregisters Q zu 1 gesetzt wird, während das entsprechende Bit j des zweiten Hilfsregisters Q' zu 0 gesetzt wird. In einem Block 54 wird eine Korrektur gewissermaßen ähnlich zu dem Fall von b gleich 1 durchgeführt. Wenn in dem Block 44 herausgefunden worden ist, daß das Zwischenergebnis Z nach der Abarbeitung sämtlicher Multiplikatorbits kleiner 0 war, so bedeutet dies, daß eine Reduktion zu viel stattgefunden hat. Z wird im Block 46 daher um N erhöht. Dies wird in den Reduktionsinformationen dahin gehend berücksichtigt, daß im Block 54 das niedrigste Bit Q₀ des zweiten Hilfsregisters Q' zu 1 gesetzt wird.
Die Auswertungseinrichtung 14 von 1 wird schließlich dahin gehend aktiv, daß sie von dem ersten Hilfsregister Q das zweite Hilfsregister Q' abzieht (Block 56), um den ganzzahligen Quotienten Q in binärer Form zu erhalten. Die Subtraktion im Block 56 ist dahin gehend zu verstehen, daß das Register Q einen Zählwert für alle tatsächlich durchgeführten Modulsubtraktionen in der 3-Operanden-Operation umfaßt, wobei diese Zahl zu hoch ist, wenn Z kleiner als 0 wird (Block 44), so daß der Inhalt des zweiten Hilfsregisters Q' und insbesondere das niederstwertige Bit, das im Block 54 gesetzt wird, wieder abgezogen werden muß. Das selbe trifft für den Fall zu, bei dem der Reduktions-Parameter b gleich 1 ist. Hier wird kein Modul subtrahiert, sondern ein Modul addiert. Dies muß im ganzzahligen Quotienten wieder dahin gehend berücksichtigt werden, daß das Hilfsregister von dem ersten Hilfsregister subtrahiert wird. Für Fachleute ist es ersichtlich, daß, wenn die Bits des zweiten Hilfsregisters Q' statt auf „+1" auf „ –1" gesetzt werden würden, in dem Block 56 durch die Auswertungseinrichtung keine Subtraktion, sondern eine Addition vorgenommen werden müßte.
Aus dem Vorstehenden ist für Fachleute ersichtlich, daß die Erfindung besonders für eine Hardwaretechnische Realisierung geeignet ist. Dies ist vorteilhaft, da eine Software-technische Realisierung des MMD-Befehls Performance- und Verwaltungsaufwand kostet.
Die Erfindung ersetzt eine solche Software-technische Realisierung. Insbesondere kann das vorgestellte Konzept günstig in bestehende Kryptoprozessoren integriert werden, wobei hier nur VHDL-Änderungen des Krypto-Controllers nötig sind, um sowohl die Protokollierungseinrichtung als auch die Auswertungseinrichtung in die bestehende Verarbeitungseinrichtung einzufügen. Der üblicherweise vorhandene modulare Multiplikationsbefehl kann somit einfach und wenig fehleranfällig um das Er gebnis der DIV-Operation, also den ganzzahligen Quotienten, ergänzt werden.

10: Verarbeitungseinrichtung
10a: Rechenwerk
10b: Controlteil
12: Protokollierungseinrichtung
14: Auswertungseinrichtung
20: Initialisierungsschritt
20': Initialisierung
21: Bituntersuchungsschritt
22a, 22b: Zwischenergebnisberechnung
23: Erster Modulvergleich
24: Erste Modulsubtraktion
25: Zweiter Modulvergleich
26: Zweite Modulsubtraktion
27: Indexuntersuchung
28: Indexinkrementierung
30a: Reduktionsinformationen ohne Modulsubtraktion
30b: Reduktionsinformationen nach einer Modul-Subtraktion
30c: Reduktionsinformationen nach zwei Modul-Subtraktionen
32: Addition der Hilfsregister
40: Initialisierung
40': Initialisierung
42: Iterationsuntersuchung
44: Zwischenergebnisuntersuchung
46: Moduladdition
50: Ordnungsinformationsberechnung
52: Reduktionsinformationsberechnung
54: Reduktionsinformationskorrektur
56: Subtraktion der Hilfsregister
900: Start des ZDN-Algorithmus
910: Multiplikations-Look-Ahead-Algorithmus
920: Zwischenergebnis-Verschiebung
930: Reduktions-Look-Ahead-Algorithmus
940: Modulverschiebung
950: 3-Operanden-Operation
960: Ende des ZDN-Algorithmus

Claims

Vorrichtung zum Berechnen eines ganzzahligen Quotienten eines Terms (T) bezüglich eines Moduls (N), wobei der Term ein Produkt aus einem binären Multiplikator (M) und einem Multiplikanden (C) aufweist, mit folgenden Merkmalen: einer Verarbeitungseinrichtung (10) zum Verarbeiten von Bits des Multiplikators (N) in mehreren Verarbeitungsschritten, wobei die Verarbeitungseinrichtung (10) ausgebildet ist, um in einem Verarbeitungsschritt ein bezüglich des Moduls reduziertes Zwischenergebnis (Z) zu berechnen, das von dem einen oder den mehreren Bits des binären Multiplikators abhängt, die in dem einen Verarbeitungsschritt betrachtet werden; einer Einrichtung (12) zum Protokollieren von Reduktionsinformationen in dem einen Verarbeitungsschritt und zum Protokollieren von Ordnungsinformationen über durch eine oder mehrere durch den einen Verarbeitungsschritt betroffene Stellen des ganzzahligen Quotienten; und einer Auswertungseinrichtung (14) zum Auswerten der Reduktionsinformationen und der Ordnungsinformationen aus den Verarbeitungsschritten, um den ganzzahligen Quotienten (Q) zu erhalten.
Vorrichtung nach Anspruch 1, bei der die Verarbeitungseinrichtung (10) ein festverdrahtetes Rechenwerk (10a) zum Berechnen des modular reduzierten Zwischenergebnisses (Z) aufweist, bei der die Verarbeitungseinrichtung ferner ein Controlteil (10b) zum Steuern des fest-verdrahteten Rechenwerkes (10a) aufweist; und bei dem die Protokollierungseinrichtung mit dem Controlteil (10b) gekoppelt ist, um die Reduktionsinformationen und die Ordnungsinformationen von dem Controlteil zu erhalten.
Vorrichtung nach Anspruch 1 oder 2, bei der ein Zwischenergebnisregister (Z) auf 0 initialisiert ist (20'; 40'), so daß der Term (T) gleich dem Produkt des ersten Operanden und des zweiten Operanden ist.
Vorrichtung nach Anspruch 1 oder 2, bei dem ein Zwischenergebnisregister (20'; 40') auf einen dritten Operanden (D) initialisierbar ist, so daß der Term gleich C × M + D × 2ⁿ ist, wobei C der Multiplikand ist, wobei M der Multiplikator ist, wobei D der dritte Operand ist, und wobei n eine maximale Länge von A, B und D in Bits ist.
Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Verarbeitungseinrichtung (10) ausgebildet ist, um ausgehend von einem höchstwertigen Multiplikatorbit bis zu einem niederstwertigen Multiplikatorbit zu arbeiten.
Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Verarbeitungseinrichtung ausgebildet ist, um in jedem Verarbeitungsschritt ein Bit zu verarbeiten, bei der die Einrichtung zum Protokollieren (30a, 30b, 30c) eine Registereinrichtung mit zwei Hilfsregistern (Q, Q') aufweist, wobei die Reduktionsinformationen (30a, 30b, 30c) bestimmen, ob eines oder mehrere Bits in der Registereinrichtung gesetzt sind oder nicht, und wobei die Ordnungsinformationen bestimmen, welches eine oder welche mehreren Bits in einem Verarbeitungsschritt betroffen sind, und bei dem die Auswertungseinrichtung (32) ausgebildet ist, um die Registereinrichtung auszuwerten, um den ganzzahligen Quotienten auszugeben.
Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Verarbeitungseinrichtung (10) ausgebildet ist, um in jedem Verarbeitungsschritt ein Bit des Multiplikators zu verarbeiten (28), ein Zwischenergebnis abhängig von den Multiplikatorbits zu berechnen (22a, 22b), das berechnete Zwischenergebnis zu untersuchen (23), ob es größer als der Modul ist, falls es größer als der Modul ist, ein neues Zwischenergebnis zu berechnen (24), indem der Modul von dem Zwischenergebnis subtrahiert wird, das neue Zwischenergebnis zu untersuchen (25), ob es größer als der Modul ist, und falls es größer als der Modul ist, ein weiteres neues Zwischenergebnis zu berechnen (26), indem der Modul ein weiteres Mal subtrahiert wird.
Vorrichtung nach Anspruch 7, bei der die Protokollierungseinrichtung (12) ausgebildet ist, um als Reduktionsinformationen die Anzahl der Subtraktionen des Moduls zu verwenden, und um als Ordnungsinformationen ei ne Ordnung (i) des gerade verarbeiteten Multiplikatorbits zu verwenden.
Vorrichtung nach Anspruch 7 oder 8, bei der die Protokollierungseinrichtung (12) ausgebildet ist, um ein Bit mit einer Ordnung gleich einer Ordnung des verarbeiteten Multiplikatorbits eines ersten Hilfsregisters zu setzen (30b), wenn der Modul ein erstes Mal subtrahiert wird (24), ein Bit einer Ordnung gleich einer Ordnung des gerade verarbeiteten Multiplikatorbits eines zweiten Hilfsregisters (Q') zu setzen (30c), wenn der Modul ein zweites Mal subtrahiert wird (26), und bei dem die Auswertungseinrichtung (14) ausgebildet ist, um das erste und das zweite Hilfsregister zu addieren (32), um den ganzzahligen Quotienten zu erhalten.
Vorrichtung nach einem der Ansprüche 1 bis 5, bei der die Verarbeitungseinrichtung (10) ausgebildet ist, um einen Multiplikations-Look-Ahead-Algorithmus (910) auszuführen, so daß in einem Verarbeitungsschritt eine Mehrzahl von Multiplikatorbits betrachtet werden, wenn die Mehrzahl von Multiplikatorbits eine von dem Look-Ahead-Algorithmus abhängige Eigenschaft hat, und bei der die Protokollierungseinrichtung (12) ausgebildet ist, um bei den Reduktionsinformationen und den Ordnungsinformationen den Multiplikations-Look-Ahead-Algorithmus (910) zu berücksichtigen.
Vorrichtung nach Anspruch 10, bei der die Verarbeitungseinrichtung (10) ausgebildet ist, um neben dem Multiplikations-Look-Ahead-Algorithmus (910) einen Reduktions-Look-Ahead-Algorithmus (930) zu verwenden, und bei der die Protokollierungseinrichtung (12) ausgebildet ist, um bei den Reduktionsinformationen und den Ordnungsinformationen den Reduktions-Look-Ahead-Algorithmus zu berücksichtigen.
Vorrichtung nach Anspruch 11, bei der die Verarbeitungseinrichtung (10) ausgebildet ist, um das reduzierte Zwischenergebnis (Z) unter Verwendung einer 3-Operanden-Addition (950) zu berechnen, wobei ein erster Operand (Z) ein Zwischenergebnis aus einem vorherigen Verarbeitungsschritt ist, ein zweiter Operand der Multiplikand (C) ist, und ein dritter Operand der Modul (N) ist, wobei zwei der drei Operanden in der 3-Operanden-Addition mit Faktoren gewichtet sind, die durch einen Faktor 2 hoch jeweiligen Verschiebungswerten (s_Z, s_N) gewichtet sind, und wobei der Modul (N) mit einem Reduktions-Look-Ahead-Parameter (b) beaufschlagt ist, wobei der Reduktions-Look-Ahead-Parameter (b) Werte von „0", „+1", „–1" haben kann, und bei der die Protokollierungseinrichtung (12) ausgebildet ist, um die Ordnungsinformationen (50) basierend auf einem Verschiebungswert (s_Z, s_N) zu bestimmen, und die Reduktionsinformationen (52) auf der Basis des Reduktions-Look-Ahead-Parameters (b) zu bestimmen.
Vorrichtung nach Anspruch 12, bei der die Protokollierungseinrichtung (12) zwei Hilfsregister (Q, Q') aufweist, wobei durch die Ordnungsinformationen bestimmte Bits (j) der zumindest zwei Register als Reduktionsinformationen folgendermaßen gesetzt werden (52): wenn b gleich 0 ist, dann ist Q_j gleich Q'_j gleich 0 wenn b gleich 1 ist, dann ist Q_j gleich 0, Q'_j gleich 1, und wenn b gleich –1 ist, dann ist Q_j gleich 1, Q'_j gleich 0, wobei b der Reduktions-Look-Ahead-Parameter ist, wobei Q_j ein Bit j des ersten Hilfsregisters (Q) ist, und wobei Q'_j ein Bit j des zweiten Hilfsregisters (Q') ist.
Vorrichtung nach Anspruch 12 oder 13, bei der dem Modul (N) ein Reduktions-Verschiebungswert (s_N) zugeordnet ist, bei der dem Zwischenergebnis ein Multiplikations-Verschiebungswert (s_Z) zugeordnet ist, und bei der die Protokollierungseinrichtung (12) ausgebildet ist, um als Ordnungsinformationen eine Ordnung (j) der Bits des ersten Hilfsregisters und des zweiten Hilfsregisters aus einer Differenz zwischen Ordnungsinformationen eines vorhergehenden Schritts und einer Differenz zwischen dem Multiplikations-Verschiebungswert (s_Z) und dem Reduktions-Verschiebungswert (s_N) zu bestimmen.
Vorrichtung nach Anspruch 13 oder 14, bei der die Auswertungseinrichtung (14) ausgebildet ist, um nach einer Abarbeitung der Multiplikatorbits durch die Verarbeitungseinrichtung (10) das zweite Hilfsregister (Q') von dem ersten Hilfsregister (Q) zu subtrahieren (56), um den ganzzahligen Quotienten zu erhalten.
Verfahren zum Berechnen eines ganzzahligen Quotienten eines Terms (T) bezüglich eines Moduls (N), wobei der Term ein Produkt aus einem binären Multiplikator (M) und einem Multiplikanden (C) aufweist, mit folgenden Schritten: Verarbeiten (10) von Bits des Multiplikators (N) in mehreren Verarbeitungsschritten, wobei die Verarbeitungseinrichtung (10) ausgebildet ist, um in einem Verarbeitungsschritt ein bezüglich des Moduls reduziertes Zwischenergebnis (Z) zu berechnen, das von dem einen oder den mehreren Bits des binären Multiplikators abhängt, die in dem einen Verarbeitungsschritt betrachtet werden; Protokollieren (12) von Reduktionsinformationen in dem einen Verarbeitungsschritt und Protokollieren von Ordnungsinformationen über durch eine oder mehrere durch den einen Verarbeitungsschritt betroffene Stellen des ganzzahligen Quotienten; und Auswerten (14) der Reduktionsinformationen und der Ordnungsinformationen aus den Verarbeitungsschritten, um den ganzzahligen Quotienten (Q) zu erhalten.