ALRUTZ, Herbert (Reichsgrafenstrasse 2, Freiburg, 79102, DE)
SENGER, Christian (Karlsruherstrasse 51, Hockenheim, 68766, DE)
LAZICH, Dejan (Jasminweg 5, Stutensee, 76297, DE)
ALRUTZ, Herbert (Reichsgrafenstrasse 2, Freiburg, 79102, DE)
SENGER, Christian (Karlsruherstrasse 51, Hockenheim, 68766, DE)
Patentansprüche:
1. Verfahren zur Durchführung der modularen Multiplikation R N [ab] von ganzen Zahlen bezüglich eines Modulus N und der modularen Multiplikation
1 λ N(X)L α V λ y k -'V λ yj v ui i I υiy i iui nci i uctuy noi ι cn ioo iϊiuuuιuopuι; ι ιuπ ιo ι i — i i y/λy , wobei die ganzen Zahlen a < N, b < N, und N bezüglich einer Radix p dargestellt sind, während die Polynome a = a(x) mit Grad(a(x)) < Grad(N(x)), b = b(x) mit Grad(b(x)) < Grad(N(x)) und N(x) bezüglich Potenzen der freien Variablen x und mit Koeffizienten aus einem ganzzahligen Restklassenring Z M dargestellt sind, umfassend die Schritte:
- Berechnung eines ergänzten Produktkettenbruchs c = (ab+jN)/t durch Ergänzungen von einzelnen Zählern eines als Kettenbruch dargestellten Produktbruchs (ab)/t, wobei im ersten Fall der Berechnung mit ganzen Zahlen, c und j ebenfalls ganze Zahlen sind sowie t = p* " , während im zweiten Fall der Berechnung mit Polynomen, c = c(x) und j = j(x) ebenfalls Polynome mit Koeffizienten aus Z M sind sowie t = t(x) =x 5r und wobei in beiden Fällen 9C eine ganze Zahl größer oder gleich der Länge £p{a) des im Kettenbruch zerlegten Operanden a ist
- Berechnung eines zweiten ergänzten Produktkettenbruchs r = (cd+kN)/t aus dem vorab berechneten modularen Rest d = R N [t 2 ] und dem Ergebnis c der im oben genannten Schritt durchgeführten Rechnung, wobei im ersten Fall r, k und d ganze Zahlen sind und im zweiten Fall r = r(x) = R N(x) [a(x)b(x)], k = k(x) und d = d(x) Polynome mit Koeffizienten aus Z M sind.
2. Verfahren nach Anspruch 1 , dadurch gekennzeichnet, dass eine modulare Multiplikation R N [ab] von ganzen Zahlen bezüglich eines Modulus N durchgeführt wird, in einem zusätzlichen Schritt nach der Berechnung der ergänzten Produktkettenbrüche c und r jeweils überprüft wird, ob die ergänzten Produktkettenbrüche c und r kleiner als der Modulus N sind, und wenn dies nicht der Fall ist, so oft der Modulus N subtrahiert wird, bis die ergänzten Produktkettenbrüche c und r kleiner als der Modulus N sind.
3. Schaltung für die modulare Arithmetik mit mindestens einer Einheit zur Berechnung und Ergänzung von einzelnen Zählern eines als Kettenbruch dargestellten Produktbruchs ab/t, umfassend
- ein Register Reg b mit 9C Registerzellen bo,^,...^^ für alle Digits des Multiplikanten b
- ein Register Reg N mit 9C Registerzellen N 01 N 1 N^ 1 für alle Digits des Modulus N
- ein Arbeitsregister Reg w mit 7<~+2 Zellen w o ,Wi,...,w κ+ i oder einen über eine p Bit breite Datenbus-Schnittstelle zugänglichen Arbeitsspeicher RAM, wobei ein Mikroprozessor μC vorhanden ist, der Arbeitsspeicher Datenbus-Schnittstelle steuert und kontrolliert
- eine Speicherzelle a o für ein Digit des Multiplikanten a
- eine Speicherzelle i o für einen Ergänzungsfaktor
- einen Schaltungsblock Con zur Bestimmung des Ergänzungsfaktors zur Ergänzung von Zählern des Produktkettenbruchs
- TC Multiplizierer Mb 0 , Mbi,... Mb 5 ^ 1 für Multiplikationen von Digits bo.bi b^ mit einem Digit des Multiplikanten a
- 9C Multiplizierer MN 0 , MN 1 ,... MN-^ 1 für Multiplikationen von Digits N 01 N 1 , ...,H 9CA mit dem Ergänzungsfaktor
- ^ " Addierer A 01 A 1 ,... ,A^ 1 für die Addition von einzelnen Ergebnissen der Multiplikation mit einem Digit des Multiplikanten a und der Multiplikation mit dem Ergänzungsfaktor wobei
- bei jedem Multiplizierer Mb k ein Eingang des Multiplizierers Mb k mit dem Ausgang der Registerzelle b k verbunden ist, ein anderer Eingang des Multiplizierers Mb k mit dem Ausgang der Speicherzelle a 0 verbunden ist, zwei Ausgänge des Multiplizierers mit nur dafür vorgesehenen Eingängen des Addierers A k verbunden sind und die Ausgänge des Multiplizierers Mb 0 zusätzlich mit Eingängen des Schaltungsblocks Con verbunden sind
- bei jedem Multiplizierer MN k ein Eingang des Multiplizierers MN k mit dem Ausgang der Registerzelle N k verbunden ist, ein anderer Eingang des Multiplizierers MN k mit dem Ausgang der Speicherzelle i 0 verbunden ist und zwei Ausgänge des Multipliers MN k mit nur dafür vorgesehenen Eingängen des Addierers A k verbunden sind
- bei jedem Addierer A k ein Ausgang des Addierers A k mit der Registerzelle w k verbunden ist, für k < TCA zwei andere Ausgänge des
Addierers A k
mit nur dafür vorgesehenen Eingängen des Addierers A k+1
verbunden sind, und bei dem Addierer A^ 1
ein nur dafür vorgesehener Ausgang mit dem Eingang der Registerzelle w^- verbunden ist und ein nur dafür vorgesehener Ausgang mit dem Eingang der Registerzelle
- ein Ausgang des Schaltungsblocks Con mit dem Eingang der Speicherzelle i 0 verbunden ist.
4. Schaltung für die modulare Arithmetik gemäß Anspruch 3, dadurch gekennzeichnet, dass die Schaltung das Arbeitsregister Reg w mit 7C+2 Registerzellen w o ,Wi,...,Wκ+i aufweist.
5. Schaltung für die modulare Arithmetik gemäß Anspruch 4, dadurch gekennzeichnet, dass die Addierer A k (k = 0,1, ....7CA) für jedes Eingangsdigit der in sie eingespeisten zweistelligen Werte (C 1 C 0 ), (P 1 Po), (S 1 S 0 ) und des in sie eingespeisten einstelligen Wertes E einen separaten Eingang aufweisen und jeweils pro Addierer drei Digit-Ausgänge (O 2 O 1 O) vorgesehen sind, um das durch digitweise Addition der Digits Co,p o ,s o , E mit übertrag gefolgt von digitweiser Addition der Digits C 11 P 11 S 1 , und des übertrags gegeben Ergebnis der Berechnung (O 2 O 1 O) = C T C O +Pφ O +S^ O +E auszugeben.
6. Schaltung für die modulare Arithmetik gemäß Anspruch 4, dadurch gekennzeichnet, dass die Multiplizierer Mb k und MN k (k = 0,1, ....9CA) als UND-Gatter ausgeführt sind.
7. Schaltung für die (nodulare Arithmetik gemäß Anspruch 4,
U d u u i U li y c ι\c ιι ιι z. c ι oιι ιι c ι, uoas uic nuuici cι r\y [t\ — u, ι , ....y\- ι ) als XOR-Gatter ausgeführt sind.
8. Schaltung für die modulare Arithmetik gemäß einem der Ansprüche 4 bis 7, dadurch gekennzeichnet, dass der Schaltungsblock Con als XOR-Gatter ausgeführt ist.
9. Schaltung für die modulare Arithmetik gemäß einem der Ansprüche 4 bis 8, dadurch gekennzeichnet, dass die Ausgänge der Registerzellen w k der Schaltung derart mit Eingängen der Addierer A k ' einer weiteren Schaltung gemäß Anspruch 2 verbunden sind, dass für k > 0 der Ausgang der Registerzelle w k mit einem nur dafür vorgesehenen Eingang des Addierers A k-1 ' verbunden ist und der Ausgang der Registerzelle W 1 zusätzlich mit dem Schaltungsblock Con' verbunden ist.
10. Schaltung für die modulare Arithmetik gemäß einem der Ansprüche 4 bis 8, dadurch gekennzeichnet, dass zusätzlich vorgesehen sind
- ein Register Reg a mit 9C Zellen a o ,...,ajpi, in das die Speicherzelle a 0 als erste Speicherzelle des Registers integriert ist und
- ein Taktgeber zur Ansteuerung der Register Reg a und Reg w, wobei die Ausgänge der Registerzellen w r der Schaltung derart mit Eingängen der Addierer A r der Schaltung verbunden sind, dass für r > 0 der Ausgang der Registerzelle w r mit einem nur dafür vorgesehenen Eingang des Addierers A M verbunden ist und der Ausgang der Registerzelle Wi zusätzlich mit dem Schaltungsblock Con verbunden ist.
11. Schaltung für die modulare Arithmetik gemäß Anspruch 10, dadurch gekennzeichnet, dass die Schaltung durch zusätzliche Zwischenspeicherzellen Za m , ZO 2m , ZOi m und Z im in Pipeline-Stufen zerlegt wird, die jeweils dieselbe Anzahl von Registerzellen umfassen, und so in die Schaltung eingefügt sind, dass die Speicherung der Bits des Operanden a, mit dem in der Pipeline-Stufe die letzte Multiplikation durchgeführt wurde in der Zwischenspeicherzelle Za m , die Speicherung der dabei entstandenen LJ- berträge O 2 und O 1 in den Zwischenspeicherzellen ZO 2m und ZOi m sowie die Speicherung des dabei benutzten Ergänzungsfaktors in der Zwischenspeicherzelle Z im erfolgt. |
Schaltungen für die modulare Arithmetik basierend auf der Ergänzung von Kettenbrüchen
Stand der Technik
Die Erfindung betrifft ein Verfahren, bzw. eine Schaltung, für die modulare Arithmetik gemäß dem Oberbegriff des Anspruchs 1 bzw. Anspruchs 2.
Grundlagen der Public Key Kryptographie
Die 1976 von Diffie und Hellman eingeführte Public Key Kryptographie (PKK) [1] hat sich zum Standardverfahren für den verschlüsselten und signierten Austausch von Daten entwickelt. Bei PKK-Systemen besitzt jeder Kommunikationsteilnehmer einen geheimen privaten Schlüssel (engl, private key) sowie einen öffentlichen Schlüssel (engl, public key). Nachrichten, welche mit dem öffentlichen Schlüssel verschlüsselt wurden, können nur mit dem dazugehörigen privaten Schlüssel wieder entschlüsselt werden. Umgekehrt können Signaturen mit dem privaten Schlüssel nur mit dem dazugehörigen öffentlichen Schlüssel verifiziert werden. Auf diese Art und Weise kann eine sichere Kommunikation stattfinden, ohne dass die Kommunikationspartner vorher ein gemeinsames Geheimnis ausgetauscht haben müssen. Sie müssen sich nur den richtigen und aktuellen öffentlichen Schlüssel des gewünschten Kommunikationspartners aus einer vertrauenswürdigen öffentlichen Quelle beschaffen und den eigenen privaten Schlüssel geheim halten. Die asymmetrischen PKK-Verfahren beheben damit ein grundlegendes Problem der klassischen symmetrischen Kryptoverfahren - den sicheren Austausch eines gemeinsamen Geheimschlüssels [4].
Neben der verschlüsselten Kommunikation und den elektronischen Signaturen verwendet man die Methoden der PKK noch für folgende kryptografische Aufgaben:
• Passwort- und Identifikationssysteme - Authentisierung für den Zugriff auf Daten oder Einrichtungen (überprüfung, ob jemand derjenige ist, der er vorgibt zu sein)
• Unabstreitbarkeit - die Kommunikationspartner können ihre bereits durchgeführten Transaktionen im Informationsaustausch nachträglich nicht bestreiten
• Austausch von gemeinsamen Geheimnissen - z.B. Schlüssel für symmetrische Kryptoverfahren
• Erzeugung von Pseudozufallszahlen - z.B. bei der Suche nach einem passenden PKK-Schlüsselpaar
• Bit-Festlegung (engl, bit commitment) - Festlegung von gewissen Kryptopara- metern, an die sich die Kommunikationspartner unbedingt halten müssen
• Geteiltes Geheimnis (engl, secret Sharing) - gemeinsame Wahrung einer Geheiminformation
• Beweis ohne Wissensvermittlung (engl, zero knowledge proof) - ermöglicht, jemanden davon zu überzeugen, dass man ein Geheimnis kennt, ohne jedoch Information über das Geheimnis selbst preiszugeben.
All diese Aufgaben werden durch verschiedene kryptografische Protokolle realisiert, die den genauen Ablauf von einzelnen Aktionen und Transaktionen der Kommunikationspartner vorschreiben. Zusammen mit einer Public-Key-Infrastruktur ermöglichen sie viele praktische Anwendungen, von der Geheimhaltung von Nachrichten bis zu e- lektronischen Zahlungssystemen und sichere Wahlen. Diese praktischen Anwendungen werden immer öfter durch eine direkte Einbettung von PKK-Algorithmen in integrierte Schaltungen (ICs) realisiert.
Grundbausteine der PKK-Systeme [8] sind mathematische Einwegfunktionen, die man üblicherweise durch eine ausreichend große Anzahl von Wiederholungen einer bestimmten mathematischen Operation auf Eingangsdaten berechnet. Für Befugte, die diese Anzahl der Wiederholungen (den geheimen Schlüssel) kennen, soll die Rückberechnung der Eingangsdaten einfach, für Unbefugte dagegen, die den geheimen Schlüssel nicht kennen, sehr schwer (praktisch unmöglich) sein. Ein wichtiges Beispiel für mathematische Einwegfunktionen ist die Potenzierung (wiederholte Multiplikation) in endlichen zyklischen Gruppen mit ihrer Umkehrung (ohne Kenntnis des geheimen Schlüssels), dem diskreten Logarithmus. In bestimmten entsprechend großen zyklischen Gruppen ist der diskrete Logarithmus sehr schwer zu berechnen. Die Suche nach der Lösung des diskreten Logarithmus in diesen Gruppen wurde das Diskrete Logarithmus- oder auch DLOG-Problem genannt, und es existieren einige PKK-Verfahren, deren Sicherheit auf der Schwierigkeit des DLOG-Problems basiert (DLOG- Verfahren). Zu nennen sind hier insbesondere der Diffie-Hellman-Schlüsselaustausch [1], das Chiffrier- und Signierverfahren von EIGamal [3] sowie einige daraus abgeleitete Variationen [4]. Die Sicherheit des bekanntesten PKK Chiffrier- und Signierverfahrens, das nach seinen Entdeckern Rivest, Shamir und Adelman RSA-Verfahren genannt wurde, ist jedoch von der Schwierigkeit des bis heute ungelösten Faktorisie- rungsproblems abhängig [2].
Bei der praktischen Umsetzung der asymmetrischen Kryptoalgorithmen spielen, wie weiter unten ausführlicher beschrieben wird, modulare Rechenoperationen jeweils eine fundamentale Rolle, denn die modulare Arithmetik (oder Restklassenarithmetik)
bildet eine Basis für die Rechnung in Restklassenringen modulo N sowie in endlichen Körpern. Wenn diese natürliche Zahl N eine Primzahl p ist, definieren die arithmetischen Regeln für die modulare Arithmetik genau die Regeln für die Rechnung in Primkörpern Fp (oder GF(P)).
Dabei sind auf moduierer Addition und einfacher modularer Multiplikation basierende Konstruktionen von Verschlüsselungsfunktionen keine gute Wahl, da sich so definierte Verschlüsselungsmethoden mit überschaubarem Aufwand brechen lassen; sehr wohl geeignet sind aber die Potenzierung und ihre Umkehrung, der diskrete Logarithmus.
So kann z.B. die überführung eines unverschlüsselten Textes (Klartextes) U unter Verwendung eines öffentlichen Schlüssels K p einer Kommunikationseinrichtung E durch die Gleichung
V = U Kp mod N beschrieben werden, wobei die vorberechneten Zahlen K p und N durch die Einrichtung E veröffentlicht werden. Die Entschlüsselung des verschlüsselten Textes (Chiffretextes) V erfolgt dann durch die Einrichtung E mittels der Gleichung
U = V 1 ^ mOd N, wobei die vorberechnete Zahl K s eine geheime, von E verwaltete Information ist (geheimer Schlüssel). Auch eine solche Verschlüsselungsmethode ist aber nur dann sicher, wenn es sich bei dem geheimen Schlüssel um eine hinreichend große Zahl handelt. Was „hinreichend" in diesem Zusammenhang bedeutet ist abhängig vom exakten verwendeten Verschlüsselungsalgorithmus, typische Werte für gängige Verfahren werden weiter unten angegeben.
Modulare Arithmetik kann also verwendet werden, um die Verschlüsselung und die Entschlüsselung von Informationen, sowie andere kryptografische Aufgaben praktisch durchzuführen. Im Rahmen der modularen Arithmetik lässt sich auch mit Polynomen rechnen. Wenn das Moduluspolynom N(x) über F p irredυzibel ist, mit N(x) = p(x) und Grad(p(x)) = m e N \{0) (d.h. p(x) kann man nicht als Produkt von Polynomen über F P darstellen), so definieren die arithmetischen Regeln für die modulare Arithmetik über Polynomen genau die Regeln für die Rechnung in endlichen Erweiterungskörpern F p m (oder GF(p m )). Hier rechnet man mit Polynomen modulo p(x) und noch zusätzlich komponentenweise modulo p (d.h. in F p ).
Neben der Arithmetik in Restklassenringen Z N (N keine Primzahl) und in endlichen Körpern F P und F p m kann man auch noch die Gruppenarithmetik der elliptischen und
hyperelliptischen Kurven verwenden. Die dort definierten Gruppenoperationen sind aus mehreren arithmetischen Operationen auf den endlichen Körpern F P oder F p m zusammengesetzt. Ein Beispiel für ein entsprechendes Verfahren ist der DE 698 29 967 T2 zu entnehmen.
Die Motivation zur Verwendung von derart einsetzbaren Rechenoperationen hängt damit zusammen, dass die Sicherheit des geheimen Schlüssels in entscheidender Weise von seiner Bitlänge abhängt. Dem RSA- und den DLOG-Verfahren ist beispielsweise gemein, dass sie nur bei der Verwendung sehr großer Zahlen als private (geheime) Schlüssel (heutzutage 300-600 Dezimalstellen, etwa 1000-2000 Bit lang) eine ausreichende Sicherheit bieten [7] (praktisch unmögliche Rekonstruktion der geheimen Eingangsdaten ohne Kenntnis des geheimen Schlüssels und praktisch unmögliche Rekonstruktion des geheimen Schlüssels selbst). Kommen kleinere Schlüssellängen zum Einsatz, so können sowohl das RSA- als auch die DLOG-Verfahren auf heutigen Rechnern durch Einsatz von bestimmten Algorithmen [4] oder manchmal auch durch einfaches Durchprobieren aller möglichen geheimen Schlüssel gebrochen werden.
Jedoch wird durch den Einsatz von langen privaten Schlüsseln auch die Berechnung der Einwegfunktion entsprechend lang und dadurch nicht mehr ohne größere Rechenleistung möglich. Für eine ausreichend schnelle Berechnung von Einwegfunktionen mit langen privaten Schlüsseln haben die eingebetteten Systeme meistens sowohl eine zu geringe Rechenleistung als auch zu wenig Speicherkapazität. Es besteht darum ein Bedarf an PKK-Verfahren, welche eine möglichst hohe Sicherheit bei möglichst geringer Schlüssellänge liefern - also letztendlich eine höhere Sicherheit pro privatem Schlüsselbit.
Einen Ansatz dazu liefert die Kryptographie mit elliptischen Kurven (engl. Elliptic Cur- ve Cryptography, ECC) [9 bis 11] und mit hyperelliptischen Kurven (engl. Hyper- Elliptic Curve Cryptography, HECC) [5]. Elliptische Kurven sind durch bestimmte Polynomgleichungen festgelegte Punktmengen über einem Grundkörper, für die man Punktaddition (Addition von zwei Punkten), eine Punktverdopplung sowie eine Multiplikation eines Punktes mit einer natürlichen Zahl definieren kann. Punktaddition und Punktverdopplung werden dabei aus mehreren Operationen des Grundkörpers zusammengesetzt. Die Multiplikation eines Punktes mit einer natürlichen Zahl besteht wiederum aus mehreren Punktadditionen und Punktverdopplungen. Man nutzt die Tatsache aus, dass die Punkte auf einer elliptischen Kurve eine endliche zyklische Gruppe bezüglich der Multiplikation eines Punktes mit einer natürlichen Zahl bilden
und das DLOG-Problem daher auf die Punkte einer elliptischen Kurve übertragbar ist. Es wird in diesem Zusammenhang auch vom EC-DLOG-Problem gesprochen. Durch die zusätzliche Arithmetikebene scheitern sämtliche in der Literatur bekannten Verfahren zur Lösung des DLOG-Problems [4], wenn man sie auf das EC-DLOG-Problem anwendet, schon bei der Verwendung von relativ kurzen Schlüssellängen. Man kann somit also die verwendete Schlüssellänge bei gleicher Sicherheit reduzieren. Es gilt heute als allgemein anerkannt, dass ein ECC-Verfahren mit 160 Bit langen privaten Schlüsseln in etwa die gleiche Sicherheit liefert wie das RSA-Verfahren mit 1024 Bit langen privaten Schlüsseln. Zugunsten einer weiter verkürzten Schlüssellänge bei vergleichbarer Sicherheit verwendet man die neuerdings im Forschungsinteresse stehende Kryptographie auf hyperelliptischen Kurven [5].
Diese höhere Sicherheit pro Bit des privaten Schlüssels wird jedoch durch die komplizierten Verfahren zur Multiplikation eines Punktes mit einer natürlichen Zahl erkauft. Abhängig vom Grundkörper der Kurve und der Darstellung ihrer Punkte sind für eine solche Multiplikation zahlreiche Operationen im Grundkörper erforderlich, insbesondere auch aufwändige Invertierungen. Durch die geringe Rechenleistung eingebetteter Systeme ist man aus diesem Grund auf äußerst effiziente Realisierungen der Operationen im Grundkörper angewiesen. Diese sind im Grunde Operationen der langzahligen modularen Arithmetik, deren Softwarerealisierungen meistens zu aufwändig für eingebettete Systeme sind. Aus diesem Grund besteht in der Public Key Kryptographie für eingebettete Systeme ein Bedarf an effizienten Verfahren und Schaltungen für die langzahlige modulare Arithmetik [12,13].
Grundlagen der modularen Arithmetik
Die Grundaufgabe der modularen Arithmetik ist das Auffinden eines Rests R = R N [n] einer ganzen Zahl n e Z = {... , -2, -1, 0, 1 , 2,...} bezüglich einer anderen ganzen Zahl
N e Z\{0} ungleich 0 (dem Modulus), sodass R e N = {0, 1 , 2,...} diejenige natürliche
Zahl ist, welche nach Abzug des größtmöglichen ganzzahligen Vielfachen der Zahl N von n entsteht.
Drei einfache Beispiele veranschaulichen die Berechnung von Resten:
R 7 [23] = 2 = 3 * 7 + 2 ; R 7 [-23] = 5 = -4 • 7 + 5 und R -7 [23] = 2 = (-3 ). (-7) + 2.
In der Literatur wird neben der hier verwendeten Operatordarstellung R = R N [n] des
Rests häufig auch die Schreibweise R = n mod N verwendet, welche im weiteren Ver-
lauf dieses Dokumentes wegen möglicher Undeutlichkeiten in komplexeren Ausdrücken nicht mehr benutzt wird.
Nach dem Divisionssatz von Euklid gibt es für n e Z und N e Z \{0} genau ein Paar bestehend aus Quotient q e Z und Rest R e N, sodass n = q - N + R (1 ) mit |N| > R > 0 (2) gilt. Für einen festen Wert N e Z \{0) befinden sich alle Werte von R bezüglich n e Z im
Restklassen ring modulo N, der mit Z N = {0, 1 , 2 N-1} bezeichnet wird.
Aus dem Divisionssatz von Euklid kann man einige Eigenschaften von Resten ableiten. Die wichtigsten sind:
R N [-π] = R N [N - R N [n]] (3)
R. N [n] = R N [n] (4)
R N [J-N] = 0 (5)
R N [n+j-N] = R N [n] (6)
R N [π] = n, wenn N > n > 0 (7)
R N [R N [π]] = R N [n], (8) wobei n, j e Z und N e Z \{0}.
Wie man sehen kann, ist die Suche nach Resten von negativen Zahlen und die Suche nach Resten bezüglich negativer Moduli mit den beiden Eigenschaften (3) und (4) auf den jeweils positiven Fall rückführbar. Es genügt also, wenn man sich auf die Betrachtung von natürlichen Zahlen beschränkt.
Die modulare Arithmetik lässt sich in analoger Weise auch auf die Rechnung mit Polynomen n(x) = n g- rx 9'1 + n g-2 «x 9'2 + ... + n 2 »x 2 + n^x 1 + n o «x°
N(X) = N G-1 . χG - 1 + N G -2-x G"2 + ... + N 2 . χ2 + N 1 * 1 + N 0 » x°
anwenden, wobei g, G e N \{0} die Längen X(n(x)) und X(N(X)) des jeweiligen Polynoms sind und g-1 , G-1 die jeweiligen Polynomgrade Grad(n(x)) und Grad(N(x)), wenn n g- i φ 0 und N G- i φ 0. Die Potenzierung x k mit einer natürlichen Zahl k e N entspricht der k-Mal wiederholten Multiplikation der freien Variablen x. Ein Polynom mit Koeffizienten, die alle den Wert Null haben, wird als Nullpolynom 0 bezeichnet.
Die Koeffizienten n 0 , m, n 2 , ... , n g-1 sowie N 0 , Ni, N 2 , ... , N G -i der jeweiligen Polynome entstammen einem festgelegten kommutativen Ring - einer Menge auf der zwei arithmetische Operationen mit bestimmten Eigenschaften definiert sind (z.B. komplexe Zahlen C mit komplexer Addition und Multiplikation, reelle Zahlen IR mit reeller Addition und Multiplikation, rationale Zahlen O mit deren Addition und Multiplikation, ganze Zahlen Z mit deren Addition und Multiplikation usw.).
Als Ausgangspunkt werden hier Polynome über den Restklassenringen modulo N, d.h. über Z N , betrachtet.
Die Grundaufgabe der modularen Arithmetik mit Polynomen ist das Auffinden eines Restpolynoms R(x) eines Polynoms n(x) bezüglich eines anderen Polynoms N(x) φ 0, wobei R(x) dasjenige Polynom ist, welches man erhält, indem man das größtmögliche polynomiale Vielfache des Moduluspolynoms N(x) von n(x) abzieht. Um zwischen skalaren Operationen mit Elementen aus C, IR, Q, oder Z, die wie üblich mit +, -, und • bezeichnet sind, und Operationen mit Polynomen zu unterscheiden, werden polynomiale Addition, Subtraktion und Multiplikation mit El, B und El bezeichnet. Bei der Addition und Subtraktion der Polynome werden die überträge (im Gegensatz zu skala- rem + und -) nicht berücksichtigt. Es wird also nur komponentenweise in Z N
ohne ü- berträge gerechnet. Da eine polynomiale Multiplikation aus polynomialen Additionen zusammengesetzt ist, wird hier auch die Betrachtung der überträge weggelassen. Nach dem Divisionssatz von Euklid für Polynome existiert für zwei Polynome n(x) und N(x) φ 0 mit
n(x) = q(x)ξN(x) ξ R(x) (9)
Grad(N(x)) > Grad(R(x)) > 0 (10) gilt.
Für R(x) wird die Operatordarstellung R(x) = R N ( X )[n(x)] benutzt. Für ein festes Moduluspolynom N(x) befinden sich alle Werte von R(x) bezüglich n(x) im Restklassenpolynomring modulo N(x) über Z N , der mit Z N [X] N ( X ) bezeichnet wird. Aus dem Divisionssatz von Euklid für Polynome kann man die Eigenschaften von Resten über Z N [x] N(x) ableiten. Die wichtigsten Eigenschaften sind:
RN[BII(X)] = R N (X)[N(X) B R NM [n(x)]] (11 )
RBN(X)[π(X)] = RN(X)MX)] (12)
R N(x) 0(x)HN(x)] = 0 (13)
R NM [n(x)ξj(x)ξN(x)] = R N( x)[n(x)] (14)
R N ( x ) [n(x)] = n(x), wenn Grad(N(x)) > Grad(n(x)) ≥ 0 (15)
R N(X)[R N(x)[n(x)]] = RN(X)[II(X)], (16)
wobei n(x), j(x) e Z N [x] N(x) , N(x) e Z N [x] N ( X )\{0} und B N(x) = 0 B N(x).
In der modularen Arithmetik ist es neben der Ermittlung von Resten ganzer Zahlen und Polynome (was in der Literatur häufig als modulare Reduktion bezeichnet wird) auch erforderlich, Reste von bestimmten arithmetischen Funktionen zu berechnen. Diese Funktionen sind bei ganzen Zahlen aus arithmetischen Grundoperationen wie +, -, • und Potenzierung mit einer natürlichen Zahl zusammengesetzt (z.B. RN.ni+n 2 ], oder R N .ni«n 2 ]; n 1 t n 2 ε Z). Bei Polynomen über Z N [X]N(X) entspricht dies den Operationen B, B, El und der Potenzierung mit einer natürlichen Zahl (z.B. R N (x)[ni(x)Bn 2 (x)], oder RN(x)[n(x) k ]; n(x), n^x), n 2 (x) e ZN[X]NM, ke N ). Die Hauptregeln für die Berechnung der Reste von arithmetischen Funktionen, welche aus Operationen mit ganzen Zahlen zusammengesetzt sind, lauten:
RN [ni + n 2 ] = R N [RN Cn 1 ] + R N [n 2 ]] (17a)
RN In 1 • n 2 ] = R N [RN [ni] • R N [II 2 ]] (18a)
= R N [ ni . R N [n 2 ]] (18b)
= R N
[R N
[π I
] TI 2
] (18c)
wobei n, ni, n 2 e Z , k e N und N e Z \{0}.
Die Hauptregeln für die Berechnung der Reste von Funktionen, welche aus Operationen mit Polynomen über Z N [X] N M zusammengesetzt sind, lauten:
RN(X)[πI(X) ξ n 2 (x)] = R NM [ni (x)] B R N( x)[n 2 (x)] (20a)
= RN(X)[RN(X)[πI(X)] B R N (x)[n 2 (x)]] (20b)
= R N (x)[ni(x) B RN ( X)[π 2 (X)]] (20C)
= RN(X)[RN(X)[πI(X)] B n 2 (x)] (2Od)
RN(X)[II 1 (X) E ] n 2 (x)] = RN(X)[RN(X)[πI(X)] □ R NM [n 2 (x)]] (21a)
= RN(X)[πI(X) ξ RN(X)[π 2 (X)]] (21 b)
= RN (X )[RN[πI(X)] □ n 2 (x)] (21c)
RN(X )[n(x) k ] = RN(χ)[RN ( x)[n(x)] k ], (22a)
R k [m]
R x M[x m ] = (22b)
wobei n(x), In 1 (X), n 2 (x) e Z N [X]N( X ), k e N, m e N \{0} und N e Z \{0).
In der modularen Arithmetik sind die (nodulare Addition R N [a + b], a, b e Z und die (nodulare Subtraktion R N [a - b] über den ganzen Zahlen im Vergleich zur modularen Reduktion des größeren Operanden als nicht aufwändiger zu bewerten, da durch Addition und Subtraktion Zwischenergebnisse entstehen, welche die gleiche Größenordnung haben wie der größere Operand (die Größenordnungen beziehen sich auf absolute Werte). Zum Beispiel ist R 103 [38571 + 99] = R 103 [38670] nicht aufwändiger zu berechnen als Ri O3 [38571].
Wenn zusätzlich der Modulus und der größere Operand die gleiche Größenordnung haben, so ist die erforderliche modulare Addition (Subtraktion) trivial, da nur ein kleines Vielfaches des Modulus abzuziehen ist. Dies kann durch wiederholte Subtraktion des Modulus durchgeführt werden. Zum Beispiel Ri O22 3[38571 + 99] = R 10223 [38670] = 38670 - 3»10223 = 8001. Besonders einfach ist die modulare Addition von zwei Repräsentanten a und b einer Restklasse modulo N (wo a < N und b < N gilt) die der Ungleichung 0 <a + b <2»(N - 1) genügen. Also ist höchstens eine einfache Subtraktion von N ausreichend für die notwendige modulare Reduktion.
Ist einer der Operanden jedoch wesentlich größer als der Modulus, handelt es sich dabei um ein nichttriviales Problem, da dann potenziell eine sehr große Anzahl von Subtraktionen durchzuführen wäre. In dem Beispiel R 103 [38571 + 99] = R 103 [38670] = 38670 - 375*103 = 45 wäre 375-mal 103 abzuziehen, was nicht praktikabel ist. Durch Teilen von 38670 durch den Modulus 103 bekommt man die Lösung schneller, jedoch für größere Zahlen immer noch wesentlich langsamer als bei der trivialen Reduktion. In der modularen Arithmetik über Polynomen haben die modulare Addition R N(x) [a(x)ξb(x)] und die modulare Subtraktion R N ( X )[a(x)Eb(x)], a(x), b(x) e Z[x], gleiche Ergebnisse wie die Grundoperationen El und B selbst, wenn Grad(a(x)) < Grad(N(x)) und Grad(b(x)) < Grad(N(x)). Wenn der längere Operand länger als das Moduluspoly- nom ist, dann sind die modulare Addition und Subtraktion genauso komplex wie die modulare Reduktion des längeren Operanden, da bei komponentenweiser Addition
und Subtraktion in der Durchführung der Operationen El und B keine überträge entstehen. Ist einer der Operanden jedoch wesentlich länger als der Modulus, handelt es sich dabei um ein nichttriviales Problem, da dann potenziell eine sehr große Anzahl von Subtraktionen durchzuführen wäre.
Im Gegensatz zur modularen Addition und Subtraktion entstehen bei der modularen Multiplikation (R N [a»b] bzw. R N ( x )[a(x) ξb(x)]) und Potenzierung (d.h. Potenzierung mit einer natürlichen Zahl (R N [a k ] bzw. R N (χ)[a(x) k ] mit ke N\{0, 1})) Zwischenergebnisse, welche ein Vielfaches der Länge der Operanden und des Modulus erreichen können. Zur Veranschaulichung betrachtet man hier die Abschätzungsrelation für die Multiplikation von zwei Repräsentanten a und b einer Restklasse modulo N (a < N und b < N). Dabei gilt die Ungleichung 0 < a»b < (N - 1) 2 . Die Reduktion durch wiederholte Subtraktion des Modulus kommt in diesem Fall offensichtlich nicht mehr in Frage, da bis zu (N - 1) Subtraktionen notwendig wären. Zum Beispiel: R 3 i 2 [111*256] = R 3 i 2 [28416] = 28416 - 91*312 = 24. Das Vielfache 91 ist zu groß um das Ergebnis durch wiederholte Subtraktion des Modulus zu gewinnen.
Die Komplexität der erforderlichen modularen Reduktion bei der modularen Multiplikation und Potenzierung steigt bedeutend an und führt dazu, dass das getrennte Verfahren (Multiplikation bzw. Potenzierung mit einer natürlichen Zahl und nachträgliche Reduktion) zu aufwändig wird. Bei der Verwendung von großen Exponenten ist die getrennte modulare Potenzierung praktisch nicht mehr umsetzbar. Die modulare Potenzierung lässt sich jedoch auf die mehrfache modulare Multiplikation zurückführen. Eine vorteilhafte Berechnungsmethode ist bekannt unter der angelsächsischen Abkürzung S&M (Square-and-Multiply)-Verfahren [4]. Gemäß dieser Methode werden zunächst alle Radixpotenzen des Exponents berechnet, anschließend werden die zwischen diesen Radixpotenzen notwendigen Multiplikationen realisiert.
Die modulare Division lässt sich mit Hilfe des kleinen Satzes von Fermat auf die vorstehend definierten Operationen zurückführen. Er besagt, dass die (N-2)-te Potenz jedes Elements eines endlichen Körpers das modulare Inverse eben dieses Elements ist. Mit dieser Vorgehensweise kann die modulare Invertierung und somit auch die modulare Division auf die mehrfache Ausführung der modularen Multiplikation zurückgeführt werden.
Die modulare Potenzierung und die modulare Division (Invertierung) reduzieren sich also auf die mehrfache Durchführung der modularen Multiplikation. Das Hauptproblem der langzahligen modularen Multiplikation ist die modulare Reduktion, welche - bei getrennter Vorgehensweise (Reduktion nach Multiplikation) - einer allgemeinen modu-
laren Reduktion von viel größeren Zahlen als dem Modulus entspricht und dadurch sehr aufwändig sein kann. Erst durch eine algorithmisch gleichzeitige Durchführung von Multiplikation und modularer Reduktion ergeben sich nutzbare Verfahren. Basierend auf dieser Grundidee existieren in der Literatur zahlreiche Lösungsstrategien [14 bis 27]. Diese reichen von mehr oder weniger exakten Methoden zur Schätzung des Quotienten q bis hin zu raffinierten mathematischen Transformationen, welche erst durch abschließende passende Rücktransformation ein korrektes Ergebnis für die modulare Reduktion bzw. Multiplikation liefern.
Eine Auswahl dieser Lösungsansätze, die den Stand der Technik wiedergibt, wird nachstehend diskutiert.
Bestehende Lösungsansätze
Wie vorstehend bereits erwähnt, ist eine für die Durchführung kryptografischer Verfahren kritische Operation die Berechnung der Größe Rufa 6 ], die auf modulare Multiplikation zurückgeführt werden kann. Dabei können die einzelnen Variablen für nach heutigem Standard sichere Verschlüsselungen eine Länge von über 1000 Bit haben. Bisherige Lösungsansätze für eine schnelle Berechnung dieser Größe setzen vor allem bei einer Beschleunigung der als Verkettung von Multiplikationen realisierten Potenzierung an.
So gibt es Ansätze, das bereits vorstehend erwähnte S&M-Verfahren, das durch geschickte Zusammenfassung von Multiplikationen die Zahl der zur Berechnung einer hohen Potenz notwendigen Multiplikationen deutlich verringert, zu beschleunigen, beispielsweise durch seine Parallelisierung. Diese bringt allerdings einen hohen Hardware-Aufwand und insbesondere die Notwendigkeit mit sich, eine große Zahl von Registern zur Speicherung der Zwischenergebnisse vorzusehen. Ein anderer, in der DE69633253 T2 als Stand der Technik bekannter Ansatz zur Beschleunigung des S&M-Verfahrens besteht in der von Brickel et al. vorgeschlagenen BGKW-Methode, die die Multiplikationszahl weiter senkt, aber die Vorausberechnung zahlreicher Konstanten erzwingt und damit ebenfalls den Speicherplatzbedarf drastisch erhöht.
Eine alternative Methode, die der DE69633253 T2 zu entnehmen ist, besteht darin, durch geschickte Wahl der Exponenten die Zahl der notwendigen Multiplikationen zu reduzieren. Kriterium dabei ist das Hamming-Gewicht des betreffenden Exponenten. Nachteilig dabei ist allerdings, dass implizit der Raum, aus dem dieser Bestandteil des
Schlüssels ausgewählt wird, reduziert wird, was die Anfälligkeit gegenüber einem „brüte force approach" erhöht.
Zusammenfassend haben diese Ansätze zur weiteren Beschleunigung des S&M- Verfahrens den Nachteil, dass sie, soweit sie nicht eine indirekte Schwächung des Kryptocodes darstellen, bei ihrer Umsetzung so hohe Anforderungen an den Speicherbedarf stellen, dass sie insbesondere im Hinblick auf die Verwendung in eingebetteten Systemen nur beschränkt tauglich sind.
Eine andere populäre Vorgehensweise zur Durchführung einer Kette von modularen Multiplikationen, die im Spezialfall gleicher Operanden die modulare Potenzierung darstellt, beruht auf der Anwendung des Montgomery-Verfahrens [17]. Bei diesem Verfahren wählt man eine zum Modulus N teilfremde Zahl r > N, d.h. ggT(r, N) = 1. Mit dem Erweiterten Euklidischen Algorithmus berechnet man dann die ganze Zahlen r "1 und N "1 , sodass r» r "1 + N • N '1 = 1 und R N [r- r "1 ] = 1 ; R r [ISN N "1 ] = 1 gilt. Das Montgomery-Produkt AWVb] von natürlichen Zahlen ni und n 2 ist mit
AW[IVn 2
]
Hilfe einer zusätzlichen Rücktransformation, die auch ein Montgomery-Produkt darstellt, folgendermaßen ausdrücken
RNDV n 2 ] = AWAWiVn 2 J • RN[I "2 ]]. (23a)
Das Montgomery-Produkt selbst lässt sich wiederum folgendermaßen berechnen c ; wenn c<N AW 1 Vb] = c - N ; wenn c≥N, wobei c = (nτn 2 + N»R r [ni»n 2 »N '1 ])/r. (23b)
Wenn man die Zahl r als eine Zweierpotenz wählt, d.h. r = 2 k > N; k e N, werden die Division durch r und die Reduktion R r [ ] in (23b) sehr einfach (Verschiebung um k Stellen, bzw. Entfernung von k LS-Bits) und damit vemachlässigbar gegenüber die drei übrigen nichtmodularen Multiplikationen in (23b): n 1 «n 2 = b, N»R r [ ] und b»N '1 , sowie eine nichtmodulare Addition. Mit dem Montgomery-Verfahren wird also eine modulare Multiplikation durch drei einfache (nichtmodulare) Multiplikationen und eine einfache Addition ersetzt.
In der Praxis kryptografischer Anwendungen mit einem k-Bit-Modulus N bietet sich r = 2 k an, da als Modulus gängigerweise eine große Primzahl oder das Produkt zweier großer Primzahlen verwendet werden, also eine Größe, für die ggT(r, N) = 1.
Der Vorteil der Methode ergibt sich hier daraus, dass die üblicherweise durchzuführende modulare Potenzierung R N [a e ] unter Verwendung von Montgomery-Produkten mit einem Aufwand von nur log 2 e durchgeführt werden kann. Allerdings ist zum Schluss noch die Durchführung einer Rücktransformation notwendig. Ein weiterer Vorteil der Montgomery-Methode liegt darin, dass einige der nötigen Rechenoperationen vorab berechnet werden können (preprocessing). Dies ist z.B. in einem System zur Durchführung modularer Arithmetik, das in der US 5499299 offenbart wird, der Fall. Es basiert auf dem Montgomery-Verfahren, das aber in diesem Fall dadurch beschleunigt wird, dass vorab berechnete, in einer „Lookup-Table" tabellierte Werte verwendet werden. Damit wachsen aber die Speicheranforderungen an die Umsetzung beträchtlich, so dass der Einsatz in eingebetteten Systemen problematisch wird.
Ein verwandter Ansatz besteht darin, ein Look-ahead-Verfahren (Vorausschauverfahren) einzusetzen, wie es in der DE 3631992 C2 für die Z N Arithmetik und in der DE 10107376 A1 für Arithmetik auf GF(2 n ) offenbart ist.
Noch eine weitere Möglichkeit zur Beschleunigung des Montgomery-Verfahrens, die auf geschickter Bit-Manipulation beruht, ist der DE 69818798 T2 zu entnehmen. Ganz allgemein haben die auf dem Montgomery-Verfahren basierenden Systeme den Nachteil, dass sie nur für teilerfremde Zahlen r und N anwendbar sind. Darüber hinaus stellt sich auch hier in den meisten Fällen das Problem, dass eine Beschleunigung der Berechnung insbesondere mit erhöhtem Speicherbedarf erkauft wird. Allgemein hat es sich als vorteilhaft erwiesen, zur schnellen Durchführung modularer Rechenoperationen und insbesondere der modularen Multiplikation auf spezielle Hardwarelösungen (Schaltungen) und nicht nur auf eine Softwareimplementierung zurückzugreifen. Eine solche ideale Schaltung sollte die folgenden Eigenschaften besitzen:
• Komplett - alle fünf modularen Grundoperationen Addition, Subtraktion, Multiplikation, Inversion (Teilen) und Potenzierung mit einer natürlichen Zahl sollen sowohl mit ganzen Zahlen als auch mit Polynomen möglichst einfach berechnet werden
• PKK-universell - einfach anwendbar sowohl für RSA, ECC als auch HECC (soll für Restklassenringe z m sowie Primkörper F P und Erweiterungskörper F p m , insbesondere binäre Erweiterungskörper F 2 m geeignet sein)
• Skalierbar- soll nicht nur auf bestimmte Operandenlänge und bestimmte Kurvenparameter beschränkt sein
• Konform - möglichst alle bekannten Kryptostandards sollen unterstützt werden
• IC-synthetisierbar- implementierbar ausschließlich unter Verwendung standardisierter Bauelemente der herkömmlichen hochintegrierten Schaltkreise, die im Semicustom-Design synthetisiert werden
• Unkompliziert - jede modulare Grundoperation soll in möglichst geringer Anzahl von Taktzyklen durchgeführt werden
• Hochgetaktet - hohe Taktraten sind einsetzbar
• Platzsparend - in einer im IC eingebetteten Schaltung
• Energieeffizient - geringer Stromverbrauch der eingebetteten Schaltung
• Implementierungsflexibel - soll als eigenständige Schaltung, als Schaltung, die durch Mikrocontroller gesteuert ist, oder als reines Software-Modul für den Mik- rocontroller eingesetzt werden
• Implementierungsuniversell - größere unspezifische Teile der Schaltung sollten auch für andere häufig verwendete Kryptoalgorithmen benutzt werden
• Angriffsresistent - Resistenz gegen Implementierungs- und Hardware-Attacken [29], insbesondere gegen alle bekannten Seitenkanalangriffe [28 bis 34], die in den letzten Jahren entdeckt wurden.
Beispielsweise ist der bereits vorstehend erwähnten DE 3631992 auch ein Krypto- Prozessor zu entnehmen, der für die Durchführung des RSA-Verfahrens optimiert - also gerade nicht PKK-universell ist. Insbesondere wird bei diesem Prozessor die modulare Multiplikation durch eine Folge von Additionen umgesetzt. Einen anderen Prozessor, der eine hardwarebasierte Durchführung einer Montgome- ry-Multiplikation in einem speziell dafür ausgelegten Coprozessor erlaubt, ist der US5961578 zu entnehmen.
Ein anderer modularer Multiplizierschaltkreis und ein Kryptosystem sind aus der DE 10 2005 028 518 A1 bekannt. Dieser Schaltkreis zeichnet sich dadurch aus, dass ein in ihm enthaltener Montgomery-Multiplizierer mit einer Bitlänge arbeitet, die der durchzuführenden Multiplikation angepasst ist. Dies trägt zu einer Erhöhung der Sicherheit und zu einer verkürzten Berechnungszeit bei.
Beschreibung der Erfindung
Der Erfindung liegt folglich die Aufgabe zugrunde, ein Verfahren zur modularen Arithmetik zu schaffen, das in optimierter Weise in einer Vorrichtung in Form einer integrierten Schaltung tatsächlich umgesetzt werden kann.
Diese Aufgabe wird gelöst durch das Verfahren zur modularen Multiplikation gemäß Anspruch 1 bzw. die Vorrichtung zur modularen Multiplikation gemäß Anspruch 2. Der Erfindung liegt die Erkenntnis zugrunde, dass das Produkt a»b, das im Allgemeinen viel größer als der Modulus N ist, noch während seiner Berechnung schrittweise (TC-MaI) durch einfaches Teilen durch die Radix p (Verschiebung um eine Digit-Stelle) stark vermindert wird. Damit will man erreichen, dass das Ergebnis {aλήlp* möglichst nahe an N herankommt, sodass eine triviale Reduktion ermöglicht wird. Ist der Produktbruch (a»b)/p^eine ganze Zahl, dann kann man durch eine triviale Reduktion, bei der gelegentlich ein kleines Vielfaches λ≥ O des Modulus abzuziehen ist, und nach einer gleichartigen Rücktransformation R N [{R N [a*b] / p^φ 2 ^] das modulare Produkt
R N [a«b] unverzüglich erhalten. Da der Produktbruch (a'bj/p^ leider nur in Ausnahmefällen eine ganze Zahl ist, muss man verhindern, dass die Zwischenergebnisse in der Berechnung von (a^bj/p^als echt rationale Zahlen vorkommen, für welche die Regeln der modularen Arithmetik nicht gültig sind. Deshalb werden die Zwischenergebnisse in der Berechnung von (a^byp^ ständig ergänzt, sodass am Ende ein ergänzter Produkt- bruch ε N (a»b/p^) als ganze Zahl resultiert. Bei dieser Ergänzung muss man jedoch noch berücksichtigen, dass das Ergebnis in einer speziellen Form S^a^b/p^ = (a-b+j'Nyp^ e F**; j e N vorliegt. Nur dann ist es möglich durch eine identische Rücktransformation und eine nachträgliche triviale Reduktion das korrekte Ergebnis RN[a»b] zu erhalten. Die Darstellung von (a^bj/p^in Form eines endlichen Kettenbruchs ermöglicht, die Bedingungen und die Ergänzungsregeln, die zu der obigen speziellen Form führen, zu erkennen und damit die so eingeführte Kettenbruchtransformation in der Berechnung der modularen Multiplikation zu verwenden. Die eingeführte Kettenbruchtransformation bringt im Vergleich zu anderen Transformationen, wie z. B. der Montgomery-Transformation oder der schnellen Fourier- Transformation einige Vorteile, welche bei der Realisierung in integrierten Schaltungen ausgenutzt werden können. Sie unterliegt dabei nicht den Einschränkungen, welche beispielsweise für die Montgomery-Transformation vorausgesetzt werden, die nur bezüglich Zahlen r, die zum Modulus N teilerfremd sind, durchgeführt werden kann. Im Vergleich zur Fourier-Transformation und zu den direkten Methoden für modulare Multiplikation (die keine Rücktransformation benötigen) kann die Kettenbruchtransforma-
tion bei den in der PKK üblichen Berechnungen und Zahlenlängen mit geringerem Rechenaufwand eingesetzt werden. Außerdem lässt sich die eingeführte Kettenbruch- transformation mit einer Schaltung sowohl für ganze Zahlen als auch für Polynome berechnen. Somit ist die wesentliche Forderung nach einer kompletten Schaltung erfüllt.
In der folgenden detaillierten Beschreibung der Erfindung werden die Symbole für natürliche und ganze Zahlen fett gekennzeichnet, während einzelne Digits (Ziffern) bezüglich einer Radix p (Zahlenbasis) im normalen Schriftbild gesetzt werden. Eine natürliche Zahl a e N (symbolisch dargestellt) kann man in gewichteter Form a = a κ -,«p κ - 1 + a κ -2 ' P K2+ ... + a 2 «p 2 + a,«p 1 + a 0 , oder kürzer, in Radixdarstellung a — (3κ-i 3κ-2 . .. O2 3i QOJp
quantitativ angeben, wobei a k e {0, 1, ... ,p-l}; k = 0,... ,K-1 die zugehörigen Digits bezüglich der Radix p sind. Konkret für p = 10 ist z.B. 321 darstellbar als 3 « 10 2 +2 * 10 1 +1 « 10°. Bei ganzen Zahlen ist in beiden Angabeformen mit einem Vorzeichen ( + oder -) gekennzeichnet, ob a > 0 oder a < 0 (fehlendes Vorzeichen wird hier, wie üblich, + bedeuten). Die Zahlenlänge von a (in Digits) ist mit £ p (a) bezeichnet. Wenn a κ ., φ 0 und a„ = 0 für alle k > K -1 , dann £ p (a) = K e N\{0}.
Ausführungsformen der Erfindung sind in den Zeichnungen dargestellt und werden nachfolgend beschrieben. Die Zeichnungen zeigen in beispielhafter Weise:
Figur 1. a) Produktkettenbruch (a»b)/p* " für K = K dargestellt mittels Digits der ganzen Zahl a der Länge £p(a) = K Digits bezüglich der Radix p; b) Erzeugung eines Produktkettenbruchs durch die Zerlegung der ganzen Zahl a (welche in gewichteter Form angegeben ist).
Figur 2. a) Ergänzung der einzelnen Zähler in (24). Das Zeichen i | n bedeutet, dass die ganze Zahl i die ganze Zahl n teilt, während i X n bedeutet, dass i die ganze Zahl n nicht teilt; b) Auswertung des ergänzten Kettenbruchs β N (a*b/p '7f ) in Form einer
Rekursion (25) mit der Ergänzungsfunktion (26); c) Ergänzter Produktkettenbruch ε N (a«b/p <7C ) als Kettenbruch (27) dargestellt.
Figur 3. Berechnung der Kettenbruchtransformation. a) Ein Beispiel mit p = 10; b) Produktkettenbruch und ergänzter Produktkettenbruch; c) Berechnung des ergänzten Produktkettenbruchs und der Kettenbruchtransformation als Schulalgorithmus dargestellt; d) überprüfung nach (29) und (30).
Figur 4. Berechnung der Kettenbruchrücktransformation. a) Beispiel aus Fig. 3 b) Direkte Rücktransformation c) Rücktransformation mit der Kettenbruchrücktransformation d) Kettenbruchrücktransformation als Schulalgorithmus dargestellt; e) überprüfung nach (29) und (30).
Figur 5. Berechnung der binären Kettenbruchtransformation. a) Gleiches Beispiel wie in Fig. 3, hier mit p = 2; b) Kettenbruchtransformation als Schulalgorithmus dargestellt; c) Direkte Rücktransformation mitp = 10 (nur für die überprüfung des Ergebnisses). Figur 6. Berechnung der modularen Multiplikation mit der Kettenbruchtransformation. a) Ein Beispiel für Polynome aus Z 2 [x] P ( X ); b) Produktkettenbruch und ergänzter Produktkettenbruch; c) Berechnung des ergänzten Produktkettenbruchs und der Kettenbruchtransformation als Schulalgorithmus dargestellt; d) Direkte Rücktransformation (nur für die überprüfung des Ergebnisses).
Figur 7. Vorgehensweise für die Berechnung von Operationsketten in modularer A- rithmetik ohne und mit übergang in den Raum der Transformierten. Figur 8. Schaltung für die Berechnung des Zählers Z 0 1 im ergänzten Produktkettenbruch (27). Figur 9. a) Multiplizierer für zwei 1-Digit-Eingänge (aι) p und (bj) p . b) Addierer für einen 1-Digit-Eingang (E) p und drei 2-Digit-Eingänge für (pψo^ und (SiS 0 )p aus zwei Multiplizierern, sowie für die überträge (C 0 C 1 ^ aus dem vorhergehenden Addierer. Der Ausgang des Addierers besteht aus dem Ausgangsdigit O, sowie den überträgen θi und O 2 für den nächsten Addierer. c) Digit-Struktur der Addition bei größtmöglichen Eingangswerten mit Beispielen fürp = 10 und p = 2.
Figur 10. Schaltung für die Berechnung des Zählers Z 1 1 im ergänzten Produktkettenbruch (27).
Figur 11. Vorgehensweise für die Berechnung eines beliebigen Zählers Z m ' im ergänzten Produktkettenbruch (27).
Figur 12. Allgemeine parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs ε N (a«b/p* r ) oder £ NM (a(x)»b(x)/** " ).
Figur 13. Addierer bestehend aus zwei verketteten Volladdierern mit einem Steuerungseingang für die Auswahl der Additionsform: mit einer 1 am Steuerungseingang
G/P werden ganze Zahlen für p = 2 aufaddiert (mit Rücksicht auf die überträge), mit einer O am Steuerungseingang G/P werden binäre Polynome über Z 2 [x] N ( X ) aufaddiert (ohne Rücksicht auf die überträge), was einem XOR Gatter mit drei Eingängen entspricht.
Figur 14. Binäre parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs £ N
(a»b/2* "
) oder £ N
( X
)(a(x)»b(x)/x ;ir
) mit ungeradem Modulus (N 0
=I). Figur 15. Binäre parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs ε N(x)
(a(x)»b(x)/x ir
) mit ungeradem Modulus (N 0
=I). Figur 16. Allgemeine seriell-parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs
Figur 17. Binäre seriell-parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs ß N (a»b/2 sr ) oder £ N ( x )(a(x)»b(x)/x ir ) mit ungeradem Modulus (N 0 =I).
Die Bits des Operanden a sind in der Anfangsposition angegeben. Figur 18. Binäre seriell-parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs £ N (x)(a(x) φ b(x)/x 5r ) (nur für Polynome wenn N 0 =I). Die Bits des Operanden a sind in der Anfangsposition angegeben. Figur 19. Binäre seriell-parallele Schaltung für die Berechnung des ergänzten Pro- duktkettenbruchs & H {^bl2 9C ) oder £ N ( x) (a(x)»b(x)/x ir ) mit ungeradem Modulus (N 0 =I) aufgeteilt in Pipeline-Stufen.
Figur 20. Strukturelle Darstellungen der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs, a) Struktur basierend auf Registern, b) Struktur basierend auf MAT-Zellen.
Figur 21. Eine Pipeline-Stufe der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs.
Figur 22. Letzte Pipeline-Stufe der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs mit einer Verlängerung der arithmetischen Einheit (VAE).
Figur 23. Verbindung der Steuerungseinheit mit der ersten Pipeline-Stufe sowie eine MAT-ZeIIe der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs.
Figur 24. Prinzip der Taktverteilung in der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs.
Figur 25. Eine Pipeline-Stufe der binären seriell-parallelen Schaltung mit Multiplexem für die zusätzliche Berechnung der modularen Addition und Subtraktion. Figur 26. Letzte Pipeline-Stufe der binären seriell-parallelen Schaltung mit Multiplexem und Erweiterung des Registers Reg b für die zusätzliche Berechnung der modularen Addition und Subtraktion.
Figur 27. Die Register-Struktur der binären seriell-parallelen Schaltung für die Berechnung des ergänzten Produktkettenbruchs erweitert für die Berechnung der modularen Addition und Subtraktion.
Figur 28. Binäre serielle Schaltung für die Berechnung des ergänzten Produktkettenbruchs e N (a»b/2 ir ) oder 8 N (x)(a(x)«b(x)/x :ir ) mit ungeradem Modulus (N 0 =I).
Mit Hilfe der Figuren 1 bis 7 wird das erfindungsgemäße Verfahren beispielhaft erläutert.
Unter Bezugnahme auf Figur 1a wird zunächst exemplarisch der erste Schritt der erfindungsgemäßen Vorgehensweise erläutert. Ausgangspunkt des Verfahrens ist die überführung des Produkts a»b von zwei ganzen Zahlen a, b ε Z in einen speziellen Produktbruch (a»b)/t mit eine Radixpotenz t = p*; Tf e N\{0}, wie er im eingekästelten
Teil der Figur 1a Wr TC= K dargestellt ist. Zweckmäßigerweise zerlegt man dazu einen der Operanden, z.B. a mit £ p (a) = K, in eine bzgl. einer Radix p gewichtete Form, wie das in der ersten Zeile der Figur 1a angegeben ist.
Anhand der Figur 1 b lässt sich Schritt für Schritt nachvollziehen, wie man aus dieser Zerlegung die in der Figur 1a (für 1 K= K) im größten Kasten dargestellte, mit dem Formelzeichen (24) versehene Darstellung, d.h. einen Produktkettenbruch, erhält. Dabei werden zunächst Exponenten der Radixpotenz t = p*; Tf e N\{0) und der mit der
Radix p gewichteten Form des Operanden a zusammengefasst, wie in den ersten drei Zeilen der Figur 1b dargestellt. Anschließend wird iterativ im m-ten Schritt jeweils p "1 aus den Gliedern der Terme ausgeklammert, wobei der Kettenbruch, wenn man am Ende dieser Iteration bei Digit a 0 angekommen ist, in einer algebraischen Schreibweise ohne Verwendung von Bruchstrichen dargestellt wird.
Figur 2 veranschaulicht den nächsten Schritt des erfindungsgemäßen Verfahrens. Während sich beliebige Zahlen als Produktkettenbruch darstellen lassen, stellt sich hier das Problem, dass das Ergebnis eines Produktkettenbruchs eine echt rationale Zahl (aty/p* e Q sein kann, für die die modulare Arithmetik nicht definiert ist. Daher ist
es nötig, die einzelnen Zähler Z 0 , Z 1 ,..., Z κ- i in den Stufen des Produktkettenbruchs (24) so zu ergänzten Zählern Z 0 ', Z 1 ', Z 2 ',... , Z κ- i' zu ergänzen, dass so ein ergänzter Produktkettenbruch, bezeichnet mit S N (a*b/p*), stets eine ganze Zahl ist.
Dies ist mit Hilfe eines einfachen Rekursionsschemas, das in den Figuren 2a bis 2c für 'K = K verdeutlicht wiiu, müyiich. Als Stäftwβrt ist die Ergänzung dss zürn klcinstsn signifikanten Digit a 0 gehörenden Zählers Z 0 = a o »b zu berechnen. Dazu ist festzustellen, ob die Radix p den Zähler Z 0 teilt. Die formelmäßige Darstellung der vom Ergebnis dieser Auswertung abhängigen Konsequenzen ist in der oberen Hälfte der Figur 2a gezeigt: Ist dies der Fall, gilt Z 0 ' = Z 0 . Andernfalls muss ein Ergänzungsterm e 0 = i o »N/v zu Z 0 mit dem Modulus N hinzuaddiert werden, um Z 0 ' zu erhalten. In analoger Weise ist die Ergänzung des m-ten Zählers zu berechnen, wobei zu beachten ist, dass jeweils der übertrag aus dem (m-1)-ten Zähler zu berücksichtigen ist. Für die formelmäßige Darstellung kann hier auf die untere Hälfte der Figur 2a Bezug genommen werden. Die Zahl i m e N wird m-ter Ergänzungsfaktor und die Zahl v=p τ e N\{0}; Te N Modulusteiler genannt .
Verallgemeinert lässt sich also unter Voraussetzung eines geeigneten „ZV eine rekursive Vorgehensweise definieren. Mit Hilfe der Ergänzungsfunktion Con(i m »N/v) in Figur 2b ist die Auswertung des ergänzten Produktkettenbruchs S^'b/p*) in Form einer einzelnen Rekursion dargestellt, welche sich wiederum selbst als ergänzter Produktkettenbruch (27) gemäß Figur 2c darstellen lässt. Die einzelnen Zähler Z 0 ', Z 1 ', Z 2 ',... ,
Z κ-1 ' für K = K in den Stufen des ergänzten Produktkettenbruchs β N (a«b/p % ) sind so ergänzt, dass sie durch p teilbar sind und somit Sufob/p*) e Z stets eine ganze Zahl ist.
Die einzelnen Ergänzungsfaktoren werden nach der folgende Verfahrensweise bestimmt.
Der m-te noch nicht ergänzte Zähler Z m
*, der Modulus N und der durch den Modulusteiler dividierte Wert N' werden zunächst in ihre Digit-Darstellung gebracht, wobei die Länge der jeweiligen Darstellungen bezüglich der Basis p durch £p{ Z m
*) = ζ{rr\) , XP(N) = μ und />(N') =£p(Wv) = μ -T; v=p τ
e N\{0} gegeben ist. Damit ergibt sich für die Radix-Angaben von Z m
* = Z m-1
'/p + a m
»b, N und N' in (25) und (26):
N = (NU NU ... N 1 N 0 ) P ;
N' = N/v = (NU 1 NW, ... NT , NT.,... N 1 N.) p .
Man sollte beachten, dass N' für T > 0 (v>l) eine dezimale Zahl ist (siehe die Komma zwischen Nl τ und N τ .,).
Falls das LSD (engl.: Least Significant Digit) z m ,„* von Z m * gleich Null ist, dann teilt p die Zahl Z m * (bezeichnet mitp | Z m *) mit dem Ergebnis
Zm Ip ~ Z m =
[Z mζimy
, Z m αm
y2 ... Z n
, 1 )p £ 2, d.h. Z m
* wird um eine Digit-Stelle in Richtung des LSD verschoben um Z n
,' (als eine ganze Zahl) zu erhalten. Falls z m0
*≠ 0, dann p teilt Z m
* nicht (bezeichnet mit p-rZ m
* ; Z m
*/p £ Z) und Z m
* muss ergänzt werden. Der Ergänzungsterm e m
= i m
»N/v = i m
»N' ist im Allgemeinen eine dezimale Zahl (für T > 0 (v >l) ) mit einer Radix-Angabe e m
Der m-te Ergänzungsfaktor i m und der Modulusteiler v = p τ sollen so gewählt werden, dass nach der Ergänzung
Z m ' = Z m * + i m .N/v = Z m * + i m .N' = Z m * + e m
= (z mλm) ., * z m αm>2 * ... z m 1 * z m0 * ) P + i m # (N p-τ-1 N„_τ_ 2 ...Nτ , NT-,... N 1 N 0 ) P
= (Z 1
^/ Z n
^ 2 1
... z m t
' 0) p
; £p{ Z m
') = 0(m) (28) mindestens das LSD in Z m
' gleich Null wird (z m0
' = 0). Mit dieser Ergänzung teilt p Z m
' und somit lässt sich durch Verschiebung von Z m
' um eine Digit-Stelle in Richtung des LSD das Ergebnis
Beispiel 1. Seien v = 1, N' = N = (31) l0 ; C£>(N) = μ = 2) und Z m * = (358) 10 ; (Xp(Z m *) = ζ{m) = 3). Da p-rZ m * (10+358), muss der noch nicht ergänzte Zähler Z m * durch Aufaddieren des Ergänzungsterms i m «N = i m »N' = e m ergänzt werden. Um nach der Ergänzung und nach dem Teilen durch p eine ganze Zahl zu erhalten, sollte man i m = 2 wählen, da 2.31 = 62 und 62 + 358 = 420 = Z m ', sodass Z 1n Vp= 42. Beispiel 2. Seien N = (35) 10 ; und Z m * = (358) 10 . In diesem Fall soll man die dezimale
Zahl N' = N/p = (3,5) 10 (v =p = 10) nehmen, da für v = l der Ergänzungsterm i m «N nur 0 oder 5 als mögliche LSDs hat und man damit nicht alle möglichen Werte von Z m * ergänzen kann. Weil p-rZ m * (10-1-358), muss der noch nicht ergänzte Zähler Z m * durch
Aufaddieren des Ergänzungsterms i m »N' = e m ergänzt werden. Um nach Teilen durch P = 10 eine ganze Zahl zu erhalten, soll man i m = 12 wählen, da 12*3,5 = 42 und 42 +
358 = 400 = Z m ', sodass Z 1n Vp = 40.
Neben der Bedingung (28) muss noch eine weitere Bedingung (30) erfüllt sein, um den ergänzten Pfüuukikθtt6fιbrüch O N (ö*U/P*) für die Sθrθchπ'uπg der modulcrcn Multiplikation nutzen zu können.
Seien m 0 , mi,... ,m L (K-1 > m L > m L- i > ... >rrii > m 0 > 0; K-1 > L > 0) die Indizes derjenigen Zähler in (27), in welchen die Ergänzungsfunktion (26) Con(i m »N/v) Werte ungleich Null annimmt und seien im 0 , im,,... , im L die entsprechenden Ergänzungsfaktoren. Dann lässt sich der ergänzte Produktkettenbruch (27) als eine Summe aus dem ursprünglichen Produktkettenbruch (a»b)/p* " und den umskalierten Ergänzungstermen umschreiben
ε N
(a-b aa-bb j J' 1
NN
Wenn der Modulusteiler v die gebildete natürliche Zahl j 1 teilt
V| j' J j'
£ N (a'b/p*) = (a-b + J-NVp* e N; j e N . (31 )
Das ist die ausreichende Bedingung um den ergänzten Produktkettenbruch für die Berechnung der modularen Multiplikation nutzen zu können. Mit einem Wert für K ≥ K und nach Teilen von a»b + j«N e Z durch p* wird bezüglich des Produkts a»b das Ergebnis (31) wesentlich verringert und der ergänzte Produktkettenbruch β N (a»b/p*) wird nur noch ein relativ kleines Vielfaches λdes Modulus N beinhalten, oder wird sogar kleiner als N, d.h. λ= 0. Wenn λ > 0 reicht eine triviale Reduktion durch λ- faches Abziehen des Modulus N vom ergänzten Produktkettenbruch Sufob/p*) aus, sodass
R N [£ N (a-b/p*)] = ε N (a » b/p*) - λ • N (32)
gilt, wobei λ e N mit einer relativ kleinen oberen Schranke λ e N existiert (λ ≤λ). Diese spezielle Form des Rests vom ergänzten Produktkettenbruch (32) wird, sofern j e R! (d.h. (30)) gilt, die Kettenbruchtransformation genannt. Sie wird allgemein mit TC N .* [a.b] = R N [ß N (a.b/p*)] = (a-b + j-N)/p* - λ • N (33)
bezeichnet. Die Transformation TC N, *: [a-b] ist eine Funktion von a und b, der Radix p, dem Modulus N, dem Modulusteiler v sowie den Ergänzungsfaktoren {i m | m = 1 , ... , 7C-1}. Sie ermöglicht die Berechnung des modularen Produkts R N [a-b] durch die zusätzliche Berechnung eines anderen modularen Produkts
R N
[a.b] = R N
[ct],
Diese direkte Rücktransformation (34) hat nicht die gleiche Form wie die Kettenbruchtransformation (33) und müsste mit einem anderen Algorithmus berechnet werden, was ein Nachteil für den Schaltungsaufbau wäre.
Dennoch ermöglicht es eine identische Rücktransformation (wie die Kettenbruchtransformation nur mit anderen Argumenten), die Berechnung des modularen Produkts auszuführen. Dabei wird die Kettenbruchtransformation 7C N1K -[OCI] berechnet, wobei c = TC N, * [a»b] und t 2 =p 2 * " , sodass
7C N, *[o t 2 ] = R N [a-b] = 7C N, *[7C N .*[a.b] .p 2 *] (35a) gillt.
Die Formel (35a) lässt sich in eine äquivalente Form umschreiben
R N [a.b] = R N [TC N ,* [a-b] -p*] = R N [TC N ,* [a-b] -P 2 V] = R N [CP 25 V]. (35b)
Da c eine ganze Zahl ist, ist auch der Produktbruch c
R N
[a.b] =
Da die Kettenbruchtransformation einen modularen Rest darstellt, nach der Eigenschaft (18b) und (35d) gilt weiter:
RN[a » bj = 'λ " N ,κ-[c » R N [rjj, (36a) oder kurz geschrieben
R N [a.b] = ft^tcd] = TC N, * [d-c], (36b) wobei c = < 7C N, , f [a»b] und d = R^t 2 ] = R N [p 2 *]. Die Kettenbruchtransformation (36) wird mit Kettenbruchrücktransformation bezeichnet.
Somit folgt, dass das Transformationspaar
Produkt R N [a»b] mit (36b) ergibt, wenn der Radixexponent K. e N\{0} in der Transformation Kn x [a»b]=c und in der Rücktransformation % κ% [c«d] den gleichen Wert TC > K hat. Am Anfang dieses Abschnitts in (24) wurde TC = K angenommen, wobei K gleich der Länge des zerlegten Operanden ist (der in gewichteter Form angegeben wird). Wenn der zerlegte Operand in der Kettenbruchrücktransformation länger als K ist (TC < K), liefert diese Annahme ein falsches Ergebnis. Zum Beispiel gilt nach der früher verwendeten Schreibweise (dass immer der erste Operand im Produkt in gewichteter Form angegeben ist) die Kommutativität in (35a) nicht, d.h. TC N . K JP 2 *» TC N ,*- [a«b]] wird im
Allgemeinen nicht R N [a»b] liefern (weil £p(p 2<κ ) = K = 27C > K).
Um diese unpraktische Abhängigkeit von Operandenlängen zu vermeiden, kann man für den Radixexponent TC einen ausreichend großen Wert 7C- K festlegen, sodass
TC > £p(z) (37) gilt, wobei £p{z) die Länge des längeren zerlegten Operanden z in einem Transformationspaar
(engl.: Most Significant Digit) mit Nullen bis zur ^T-ten Digit-Stelle ergänzt. So wird ein
ergänzter Produktkettenbruch (29) immer in genau TC Rekursionsschritten durchgeführt.
Wenn die Länge des unzerlegten Operanden in einem ergänzten Produktkettenbruch größer als die Länge des Modulus />(N) ist, kann die Schranke λfür λin (32) zu groß werden und damit die triviale Reduktion zu aufwändig. Das kann in (35a) vorkommen.
Wegen der Eigenschaft (2) ist das in (36a) ausgeschlossen, sodass für praktische
Einsätze nur die Kettenbruchrücktransformation (36a) benutzt wird.
Wenn allerdings die Beschränkungen a, b < N gelten und v = 1 , kann man den Wert λ
= 1 für die Schranke für λ in (32) garantieren. Der Wert 1 dieser Schranke bedeutet, dass es genügt, den Modulus N höchstens einmal vom ergänzten Produktkettenbruch in (32) abzuziehen, um dessen Rest bezüglich N zu erhalten.
Die Auswahl des Modulusteilers v und die Berechnung der Ergänzungsfaktoren {i m | m = 1 ,... , 7C-Vj ist vom Modulus N und von der Radix p abhängig. Für manche Parameterkombinationen p und N ist diese Berechnung einfach, für andere hingegen etwas komplexer und bei einigen sogar unmöglich.
Sehr einfach ist sie beispielsweise für p = 2 und N ungerade. Es gilt dann i m e {0, 1} mit v= l. Ein Ergänzungsfaktor i m ist gleich 1 , falls im vorherigen Rekursionsschritt eine ungerade Zahl aufgetreten ist, wie das im Beispiel aus der Figur 5 gezeigt ist. Der soeben beschriebene binäre Fall deckt bereits die meisten Moduli ab, wie sie in der asymmetrischen Kryptographie verwendet werden - nämlich die ungeraden Moduli.
Auch für einige gerade Moduli fürp = 2 ist das modulare Produkt mit der vorgestellten Methode einfach zu berechnen. Das ist der Fall wenn ein gerader Modulus in der Binärdarstellung mit nur einer Null endet (d.h. N 0 = 0 und das vorletzte Gewicht 2 1 ist mit N, =1 multipliziert). Hier wird v =p = 2 gewählt und die Berechnung der Ergänzungsfaktoren ist gleich wie bei N ungerade, falls die Operanden a oder b (oder beide) gerade sind. Wenn dagegen a und b ungerade sind, kann man aus der Bedingungen (29) und (30) einfach feststellen, dass die Ergänzung nach (31 ) nicht möglich ist. Man kann in solchen Fällen den Operanden a durch a' = a +1 ersetzen (a' wird dann gerade und somit R N [a'»b] einfach zu berechnen). Eine nachträgliche Korrektur R N [a'»b] - b und, falls notwendig, die Berücksichtigung von (3), führt auch in diesem Fall relativ einfach zum Ergebnis R N [a«b].
Wenn ein gerader Modulus für p = 2 mit J >1 aufeinander folgenden Nullen endet, muss v =p J = 2 J gewählt werden, um die Ergänzungsfaktoren zu bestimmen. Aus den Bedingungen (29) und (30) kann man einfach feststellen, dass die Ergänzung des Kettenbruchs aφ/p^mit Ergänzungsfaktoren nur dann möglich ist, wenn der zerlegte O- πoranrt a αi irh mit I αi ifoinanHor fnlπonrlon Mi illon onH«-t Für rlie» πhriπon Fälle knnnto man a durch die nächstliegende solche Zahl a' ersetzen und eine nachträgliche Korrektur durchführen, diese wäre aber nicht mehr so einfach wie im vorstehendem Fall. Die Auswahl des Modulusteilers v und die Berechnung der Ergänzungsfaktoren {i m | m = 1 ,... , 9CA) für nichtbinäre Radixwerte p > 2 ist sehr einfach, wenn N ungerade ist und sein LS-Digit N 0 die Radix p nicht Teilt. Die Ergänzungsfaktoren bestimmt man dann als i m »N mit v = 1 wie das im Beispiel aus Figuren 3 und 4 gezeigt ist. Wenn N ungerade ist und sein LS-Digit N 0 die Radix p teilt oder bei geraden N mit N 0 ungleich Null, bestimmt man die Ergänzungen als i m »N/p mit v =p, (siehe vorstehendes Beispiel 2) aber die notwendige Bedingung (30) muss nicht immer erfüllt sein. Für diese Fälle und besonders wenn N mit J > 0 aufeinander folgenden Nullen endet, kann die Berechnung der passenden Ergänzungsfaktoren komplex werden und Lösungen mit nachträglichen Korrekturen notwendig.
Die vorstehend beschriebenen erfindungsgemäßen Verfahrensschritte lassen sich anhand von zwei Ausführungsbeispielen verdeutlichen, deren erstes in Figur 3 zusam- mengefasst ist. Dabei wird die modulare Multiplikation der Zahlen a = 321 und b = 585 bzgl. des Modulus N = 611 berechnet, wobei eine Darstellung bzgl. der Radix p = 10 gewählt wird.
Die Figur 3a zeigt die Zerlegung der vorkommenden Zahlen in die bei dieser Radix auftretenden Digits. Im einfachen Beispiel ist die direkte Berechnung der Lösung ohne größeren Aufwand möglich: Es ist bekannt, dass gelten muss:
0 < R 6n [321 - 585]= 321 - 585 - q - 611 < 611 . wobei der zugehörige Quotient q zu bestimmen ist. Berechnet man (321 >585)/611 , erhält man 307,34..., also ist q = 307 und der gesuchte Rest durch 321 « 585 - 307 « 611 = 208 gegeben. Dieser Wert muss also unter Verwendung des erfindungsgemäßen Verfahrens reproduziert werden. Zunächst ist der Produktkettenbruch zu bestimmen wie in Figur 2b, um zu überprüfen ob er im konkreten Fall eine ganze Zahl ist. Der Operand a besteht aus den Digits a 2 = 3, a^ - 2 und a 0 = 1 , so dass die Laufvariable m die Werte 0,1 und 2 durchläuft und sich für K = K der Wert 3 ergibt. Dementsprechend
ist der Zähler Z 0 gegeben durch 1 « 585, der Zähler Zi durch Z 0 /10+2 « 585 = 58,5+1170 = 1228,5 und der Zähler Z 2 durch Zi/10+3 -585 = 122,85+1755 = 1877,85. Der gesamte Kettenbruch wird dargestellt durch Z 2 /10 = 187,785, was offenbar keine ganze Zahl ist, aber den Wert a • blp* darstellt. f>o rliα δ ri+hmαHLr fι"ιr or<ht roti<->nαlo 7αhlon nifht Hofiniort ict mι ICC nι in rlor ergänzte Produktkettenbruch gebildet werden. Dazu ist die Zahl b, also 585 mit den jeweiligen Digits der Zahl a zu multiplizieren. Bei jeder Multiplikation ist das Ergebnis, falls notwendig, so mit einem Vielfachen des Modulus zu ergänzen, dass der ergänzte Zähler durch die Radix teilbar wird, wobei der jeweilige ergänzte Zähler nach Verschieben in LSD-Richtung in die folgende Berechnung als Additionswert einfließt. Im konkreten Beispiel in Figur 3c gilt:
Für das Digit a 0 =1 ist 585 mit 1 zu multiplizieren. Damit aus dem Resultat 585 eine durch 10 teilbare Zahl entsteht, muss das Produkt i O 'N = i o « 611 auf 5 enden. Die kleinste Zahl i 0 , die diese Bedingung erfüllt ist 5, also muss 5*611 = 3055 zu 585 ergänzt werden und i 0 ist gefunden. Da der ergänzte LSD-Zähler Z 0 ' = 3055 + 585 = 3640 beträgt, ergibt sich nach Verschieben in LSD-Richtung als Additionswert 364. Aus der Multiplikation von 585 mit dem Digit ai =2 erhält man die Zahl 1170, zu der der Additionswert 364 zu addieren ist, was 1534 ergibt. Diese Zahl muss mit einem Vielfachen ii von N so ergänzt werden, dass das Resultat durch die Radix 10 teilbar ist. Also muss h « 611 auf 6 enden, was für h = 6 erstmalig erfüllt wird. Zu ergänzen ist somit 6*611 = 3666, der erste ergänzte Zähler ist Z 1 ' = 1534 + 3666 = 5200, nach Verschieben in LSD-Richtung (durch Division durch 10) ergibt sich als Additionswert 520.
Analog verläuft die Rechnung für das dritte Digit: Die Multiplikation mit a 2 = 3 ergibt 585 »3 = 1755; nach Addition des Additionswerts 520 erhält man 1755 + 520 = 2275; das zu ergänzende Vielfache von 611 muss auf 5 enden, was für i 2 = 5 erfüllt ist, so dass 3055 zu ergänzen ist; 2275 + 3055 ergibt 5330 und nach Division durch p =10 erhält man für den ergänzten Produktkettenbruch S^blp*) = £ 611 (321«585/1O J ) =
533, und somit - wie gewünscht - eine ganze Zahl. Zu beachten ist hier, dass es möglich ist, eine Zahl zu erhalten, die größer als der Modulus ist. Falls dies der Fall ist, ist so lange der Modulus von dem Ergebnis abzuziehen, bis das Ergebnis kleiner ist als der Modulus. Da 533 < 611 ist, beträgt die Kettenbruchtransformation 'K^ia'b] =
K " „i, , j[321«585] = 533.
Anhand der Figur 3d vollzieht man leicht nach, dass das so bestimmte Ergebnis in der Tat dazu führt, dass der ergänzte Produktkettenbruch eine ganze Zahl darstellt, mit j' = 565 im umskalierten Ergänzungsterm aus (29).
Damit ist jedoch erst der erste Schritt zur Bestimmung des Ergebnisses der modularen Multiplikation erfolgt.
Die weiteren Schritte, die noch für die Lösung der modularen Multiplikation benötigt werden, d.h. die notwendige Rücktransformation, ausgehend von den Ergebnissen der Transformation, sind in Figur 4 abgebildet. Dabei reproduziert Figur 4a noch einmal das Ergebnis der direkten Berechnung, um den Vergleich mit den Lösungen gemäß dem erfindungsgemäßen Verfahren zu erläutern.
In der Figur 4b ist die direkte Rücktransformation (34) dargestellt. Das korrekte Ergebnis ergibt sich direkt, wenn man die modulare Multiplikation zwischen dem zuvor erhaltenen Ergebnis TC 611 . ,[321 »585] = 533 und der Radixpotenz p κ = 10 3 ausführt. Damit wäre aber nichts gewonnen, denn diese Berechnung hat nicht die gleiche Form wie die Kettenbruchtransformation (33) und müsste mit einem anderen Algorithmus berechnet werden.
Stattdessen kann man die Rücktransformation mittels einer zweiten Kettenbruchtransformation (36) durchführen, wie der Figur 4c zu entnehmen ist. Dies ist auch im Hinblick auf eine schaltungstechnische Umsetzung vorteilhaft, weil man auf dieselbe Hardware-Implementierung zurückgreifen kann.
Zwar ist auch hier zunächst zumindest eine modulare Reduktion einer relativ großen Zahl durchzuführen - im konkreten Fall d = Ru\p 2<κ ] = Ren[10 6 ] = 404, diese kann aber vorab berechnet werden. Die konkret auszuführende Berechnung lässt sich anhand der Figur 4d Schritt für Schritt nachvollziehen.
Figur 4d zeigt wieder den Ablauf der Berechnung im Detail. Das Verfahren entspricht exakt dem anhand der Figur 3c ausführlich demonstrierten Vorgehen: Der Operand d = R 6 ii[10 6 ] = 404 wird in seine Digits d 2 = 4, ό-i = 0, d o = 4 zerlegt. Beginnend mit dem Digit d 0 beginnt dann wieder die Abfolge der Operationen Multiplikation mit dem Digit, Addition des Additionswertes, ggf. Ergänzung mit dem kleinsten Vielfachen des Modu- lus, das zu einer durch die Radix teilbaren Zahl führt, Verschieben in LSD-Richtung. Anzumerken ist, dass hier in der Tat ein Ergebnis £ 6 n (404*533/10 J ) = 819 erzielt wird, das größer als der Modulus-Wert 611 ist, also ist dieser Wert einmal vom Ergebnis abzuziehen (819 - 611 = 208). Wie es sein sollte, stellt man fest, dass das Ergebnis
der direkten Berechnung, wie es in den Figuren 3a bzw. 4a dargestellt ist, richtig reproduziert wird.
Anhand der Figur 4e vollzieht man leicht nach, dass das so bestimmte Ergebnis in der Tat dazu führt, dass der hier ergänzte Produktkettenbruch eine ganze Zahl j = j' = 988 (für v = 1) im umskalierten Ergänzungsterm aus (29) ergibt.
Die Figur 5 zeigt detailliert die analoge Berechnung für dasselbe modulare Produkt bei Verwendung der Radix p = 2. Diese Wahl ist deshalb besonders interessant, weil sich, wie nachfolgend detailliert dargestellt wird, in der Hardware-Implementierung signifikante schaltungstechnische Vereinfachungen ergeben, die insbesondere auf der Möglichkeit zur Division durch die Radix mittels Bit-Shift und der einfachen Bestimmung der Ergänzungsterme sowie einer einheitlichen Berechnung für alle Modulus-Werte basieren.
Figur 5a zeigt die Darstellungen der Operanden in einer auf die Radix p = 2 bezogenen Zerlegung. In Figur 5b lassen sich die einzelnen Schritte bei der Berechnung des ergänzten Produktkettenbruches nachvollziehen. Insbesondere muss stets einmal der Modulus ergänzt werden, wenn das letzte Bit des nicht ergänzten Zählers eine 1 ist. Insbesondere ist die Tatsache zu betonen, dass die Kettenbruchtransformation desselben Produkts in einer Darstellung bezüglich einer anderen Radix zu einem anderen Ergebnis führt. Erst die entsprechende Rücktransformation, die auf direktem Weg für p = 10 in Figur 5c dargestellt ist, führt wieder auf das richtige Endergebnis. Die vorgestellte Methode für die Berechnung der modularen Multiplikation mit Kettenbruchtransformation (33) lässt sich auch für die Rechnung mit Polynomen herleiten, wenn man die Radixpotenz p^ durch x^ ersetzt und zusätzlich berücksichtigt, dass bei der polynomialen Addition s und Subtraktion B keine überträge betrachtet werden. Aus diesem Grund ist das Vielfache λ immer gleich Null, wenn man die Bedingung (40) und die Eigenschaft (20a) berücksichtigt. Also unter dieser Bedingung bei der Kettenbruchtransformation mit Polynomen ist eine nachträgliche triviale Reduktion durch λ- faches Abziehen des Modulus N(x) überflüssig. Nach (33) die Kettenbruchtransformation für zwei Polynome a(x), b(x) eZ N [x] NW , lautet dann
7C m [a(x) H b(x)] = R N(x) [ε N(x) (a(x)ξb(x) /x^)]
= (a(x)ξb(x) Sj(X)HN(X)) /x*. (38)
In Figur 6 ist ein Beispiel für die hier eingeführte Methode der modularen Multiplikation mit Kettenbruchtransformation auf Polynomen aus -Z 2 [X] N (X) dargestellt.
Als konkretes Beispiel wird das modulare Produkt der Polynome a(x) = x 2 +x+1 und b(x) = x 2 +1 bezüglich des irreduziblen Moduluspolynoms N(x) = p(x) = x 3 +x+1 berechnet.
Die direkte Lösung R N ( X )[a(x)ξb(x)] = x 2 +x erhält man durch eine Polynomdivision (mit dem Rest), die in Figur 6a auf der rechte Seite dargestellt ist. Zu beachten ist hier, dass mit den Koeffizienten der Potenzen von x bei Addition und Multiplikation binär und ohne übertrag gerechnet wird, was auch durch die Verwendung des speziellen Additions- und Multiplikationszeichens (B und H) angedeutet wird. Während das Ergebnis der „konventionellen" Berechnung (über dem Ring von ganzen Zahlen Z N [x]) des Produktes der beiden Polynome (x 2 +x+1)*(x 2 +1) = x 4 +x 3 +2x 2 +x+1 ergibt, erhält man beim Rechnen mit binären Koeffizienten (über dem Ring Z 2 [X]) das Ergebnis x 4 +x 3 +x+1.
Wie bereits aus den vorangehenden Beispielen bekannt, besteht der erste Schritt darin, die einzelnen Digits der Operanden zu bestimmen, wobei hier die „Radix" x ist. Dementsprechend ergeben sich für a(x) die Digits a 2
= 1 ,
Bei der bisherigen Betrachtung der modularen Arithmetik wurde die Durchführung der modularen Multiplikation durch die Kettenbruchtransformation eingeführt. Neben der modularen Multiplikation sind für die vollständige modulare Arithmetik zusätzlich noch die modulare Addition, modulare Subtraktion sowie die Invertierung (bzw. Division) in endlichen Körpern nötig. Wie bereits oben erwähnt, ist die Realisierung von modularer Addition und Subtraktion einfach, wenn die Operanden dieselbe Größenordnung haben wie der Modulus. Wenn man diese Annahme noch verschärft, indem man voraussetzt, dass die beiden Operanden kleiner als der Modulus sind (in Zeichen a, b < N),
so muss bei der modularen Addition und Subtraktion höchstens einmal der Modulus abgezogen werden, um das modulare Ergebnis zu erhalten.
Die entsprechende Annahme für die Rechnung mit Polynomen bezieht sich auf die Polynomgrade und bedeutet, dass die Grade der beiden Operandenpolynome kleiner als der Grad des Moduluspolynoms (in Zeichen Grad(a(x)), Grad(b(x)) < Grad(N(x))) sein müssen. Für die Arithmetik in endlichen Körpern und Restklassenringen sind diese Annahmen stets erfüllt, da die einzelnen Elemente oder deren Grad allesamt kleiner als der jeweilige Modulus oder sein Grad sind. Aus diesem Grund werden im weiteren Verlauf dieses Dokumentes die Bedingungen a, b < N (39) und
Grad(a(x)), Grad(b(x)) < Grad(N(x)) (40) berücksichtigt.
Die modulare Division in endlichen Körpern ist auf die modulare Invertierung rück- führbar, indem man eine modulare Multiplikation mit dem modularen Inversen des Divisors durchführt. Die modulare Invertierung ist die Operation, welche zu einer gegebenen Zahl a eine inverse Zahl a '1 ermittelt, für welche R N [a • a '1 ] = 1 gilt. In Z hat diese Gleichung keine allgemeine Lösung, vielmehr ist sie nur für bestimmte Kombinationen von N und a lösbar. In endlichen Körpern F p und F p m hat sie jedoch immer eine Lösung.
Eine Möglichkeit zum praktischen Auffinden von a '1 (bzw. a(x) "1 bei Polynomen) liefert der kleine Satz von Fermat. Er besagt, dass die (N-2)-te Potenz jedes Elements eines endlichen Körpers das modulare Inverse eben dieses Elements ist. Mit dieser Vorgehensweise kann die modulare Invertierung und somit auch die modulare Division auf die mehrfache Ausführung der modularen Multiplikation zurückgeführt werden. Eine alternative Möglichkeit bieten Verfahren, welche auf dem Erweiterten Euklidischen Algorithmus basieren.
Für die modulare Potenzierung mit einer natürlichen Zahl wird häufig die Square-and- Multiply-Methode benutzt, oder einige Verallgemeinerungen dieser Methode die auf Additionsketten basieren [6].
Bisher wurden alle fünf Grundoperationen der modularen Arithmetik für ganze Zahlen sowie für Polynome über Z N [X] N M eingeführt. Die modulare Multiplikation wurde anhand der Kettenbruchtransformation vorgestellt, welche immer eine abschließende Kettenbruchrücktransformation verlangt. Prinzipiell gibt es jedoch, wie in Figur 7 verdeutlicht wird, zwei verschiedene Vorgehensweisen, wenn man das vorstehend für die
Durchführung einer modularen Operation beschriebene Verfahren auf mehrere nacheinander folgende modularen Grundoperationen übertragen will. Die modulare Multiplikation mit Verwendung der Kettenbruchtransformation verlangt immer eine abschließende Kettenbruchrücktransformation. Bei Hintereinanderausführung mehrerer modularer Rechenoperationen gibt es daher einerseits die direkte Vorgehensweise, die auf der linken Seite der Figur 7 dargestellt ist, und bei der für jeden Rechenschritt einzeln eine Hin- und eine Rücktransformation durchgeführt werden müssen. Diese Vorgehensweise kann in Ketten von mehreren modularen Grundoperationen, d.h. modularen Operationsketten, in einer anderen, der rechten Seite der Figur 7 zu entnehmenden Reihenfolge durchgeführt werden, was in manchen Fällen weniger Rechenaufwand benötigt. Anstelle einer Kettenbruchrücktransformation nach jeder einzelnen Kettenbruchtransformation eines modularen Produkts in der Operationskette, erfolgt die Rücktransformation erst am Ende der Berechnungen für die ganze Operationskette. Dabei muss man jedoch am Anfang dieser Berechnungsmethode alle verschiedenen Operanden, die in der Operationskette vorkommen mit einer Kettenbruchtransformation transformieren. Das erfolgt durch die Betrachtung der beteiligten Operanden O als Produkte mit einem Identitätsoperator (O = O * 1) und durch anschließende Kettenbruchtransformation dieses formalen Produkts. Danach werden alle modularen Grundoperationen, die in der Operationskette vorkommen, mit diesen Transformierten durchgeführt und das Ergebnis mit einer einzelnen Kettenbruchrücktransformation in das Endergebnis überführt.
Diese Vorgehensweise mit dem übergang in den Raum der Transformierten ist nicht für alle modularen Operationsketten empfehlenswert, da insbesondere für Operationsketten mit vielen verschiedenen Operanden und einem kleinen Anteil modularer Multiplikation der Aufwand für den übergang in den Raum der Transformierten die Vorteile überwiegt. Dagegen sind bei langen Operationsketten mit einem großen Anteil an modularer Multiplikation und wenig Anfangsoperanden, wie z.B. bei modularer Potenzierung mit einer natürlichen Zahl, die Vorteile der auf der rechten Seite der Figur 7 vorgestellten Methode überwiegend.
Beginnend mit der Figur 8 wird nun im Detail dargestellt, wie eine schaltungstechnische Ausführung des vorstehend beschriebenen Verfahrens umgesetzt werden kann. Die Umsetzung der Kettenbruchtransformation nach (33) und (38) in einer digitalen Schaltung ist zurückzuführen auf die Umsetzung des ergänzten Produktkettenbruchs 6 N (a»b/p ir ) für ganze Zahlen a und b, einen Modulus N sowie für eine Radix p gemäß
(27). Die Umsetzung für Polynome erfolgt nach dem gleichen Prinzip und wird im Folgenden nicht gesondert im Detail betrachtet. Im weiteren Verlauf dieses Dokuments werden alle Schaltungen nur für den Fall v = 1 (N' = N) dargestellt, da sich die andere Fälle v > 1 ; v=p τ e N\{0}; Te N nur durch eine entsprechende Verschiebung des Mo- dulus N um T Digits in der LSD Richtung unterscheiden.
Weiterhin werden auch die folgenden früher angenommenen Beschränkungen berücksichtigt: a, b < N, Xp(N) = μ, μ < 9C, sodass K 1 I < TC , wobei K = £p(a) und I =
£p(b). Die Radixdarstellungen aller Argumente werden einheitlich mit einer maximalen Länge von 9C Digits angegeben:
N = (N 3T ., N^ 2 ... N 1 No) p ; a = (a*,, a« ... a, a o ) p ; b = (b*,, b*, ... b, b o ) p , wobei die Digits N„ für 9C > k > μ in N, die Digits a„ für TC > k > K in a und die Digits b„ für TC > k > I in b den Wert Null haben.
Der erste Zähler Z' o = a o *b + Con[i 0 «N] des ergänzten Produktkettenbruchs ist gemäß (27) in Fig. 2 direkt durch eine Schaltung wie in Figur 8 zu berechnen. Sie besteht aus drei Registern Reg b, Reg N und Reg w, wobei die ersten beiden an je eine Reihe von Multiplizierern mit zwei 1-Digit-Eingängen (siehe Fig. 9a) angeschlossen sind. Die Ausgänge der Multiplizierer sind wiederum an eine Kette von Addierern angeschlossen, deren Ausgänge O mit dem Arbeitsregister Reg w verbunden sind. In diesem Register wird ZO als Zwischenergebnis der Berechnung des ergänzten Produktkettenbruchs gespeichert. Die genaue Struktur der einzelnen Addierer ist in Figur 9b gesondert gezeigt. In Figur 9c ist die Digit-Struktur der Addition bei größtmöglichen Eingangswerten mit zwei Beispielen (für p =10 und p= 2) dargestellt. Aus den Forderungen a < N und b < N folgt, dass Reg b höchstens so lang sein muss wie Reg N. Aus Figur 9c folgt, dass die Länge des Arbeitsregisters Reg w nur höchstens zwei Digits größer sein muss als die Länge 9C von Reg N, damit die beiden überträge (engl. carries) aus dem höchstwertigen Addierer der Kette aufgenommen werden können. Die Ergänzungsschaltung Con für die Ergänzungsfunktion (26) bestimmt, abhängig von p und N 1 den Ergänzungsfaktor i 0 . Die Eingänge E der Addierer werden in dieser Schaltung nicht benutzt (logische Nullen sind angeschlossen), da Z' o der erste Zähler des ergänzten Produktkettenbruchs ist und keine Vorgänger hat. Die Eingänge E der Addierer werden für die nächste Stufe benötigt.
Der nächste Zähler Z 1 ' des ergänzten Produktkettenbruchs (27) in Fig. 2 wird durch eine parallele Schaltung umgesetzt werden. Zur soeben beschriebenen Schaltung
wird ein identischer Schaltungsblock hinzugefügt und die Ausgänge von Reg w im ersten Block mit den Eingängen E der Addierer im zweiten Block verbunden. Diese Verbindung wird um eine Stelle in Richtung des LSD verschoben, wodurch eine Division durch p ausgeführt wird, wie in Figur 10 dargestellt. Die Ergänzungsschaltung Con des ersten Blocks erzwingt durch den Ergänzungsfaktor i 0 , dass der durch die verschobene Verbindung frei gebliebene Ausgang von W 0 in Reg w des ersten Blocks stets eine 0 liefert. Die Ergänzungsschaltung Con des zweiten Blocks erzeugt den Ergänzungsfaktor J 1 , der nach (28) vom Ergebnis des Produkts a^bo sowie von Z 01 * abhängt. Da Z 01 * in W 1 des ersten Blocks gespeichert ist, sollte der Ausgang von W 1 des ersten Blocks mit dem Eingang der Ergänzungsschaltung Con des zweiten Blocks verbunden werden. Wie im ersten Block erzwingt die Ergänzungsschaltung Con des zweiten Blocks durch den Ergänzungsfaktor J 1 , dass der Ausgang von W 0 in Reg w des zweiten Blocks stets eine 0 liefert. Um das verschobene (durch p geteilte) höchstwertige Digit aus dem W^ +1 des ersten Blocks, im zweiten Block auf die Stelle "7C aufaddieren zu können, muss der zweite Block mit einem zusätzlichen Addierer /\<κ erweitert werden
(siehe Fig. 10). In Figur 10 entspricht die Verschiebung um eine Stelle in Richtung des LSD einer Verschiebung um eine Stelle nach links. Aufgrund obiger einfacher Erklärung sind Reg b und Reg N in der Figur 10 doppelt dargestellt, obwohl nur je eins benötigt wird.
Die soeben beschriebene Vorgehensweise für den Zähler Zi' kann wie in Figur 11 auf die nachfolgenden Zähler des ergänzten Produktkettenbruchs (27) erweitert werden. Das Arbeitsregister Reg w kann man in allen Schaltungsblöcken weglassen, da man bei paralleler Ausführung die einzelnen Zwischenergebnisse Z m ' direkt (ohne Speicherung) in den nächsten Schaltungsblock weiterleiten kann. Dadurch erhält man eine rein kombinatorische parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs und damit auch für die Berechnung der Kettenbruchtransformation nach (33) und (38). Dafür fehlt jedoch noch die Realisierung der Restberechnung, welche nach (32) in Form von λ-fachem Abziehen des Modulus N erfolgt. Die Umsetzung dieser Subtraktion wird später (im Rahmen der Erklärung der Umsetzung von modularer Addition und Subtraktion) im Detail beschrieben.
Eine allgemeine parallele Version der Schaltung für die Berechnung des ergänzten Produktkettenbruchs ist in Figur 12 dargestellt. Als rein kombinatorische Schaltung hat sie zwar Vorteile in Bezug auf ihre Geschwindigkeit, die Anzahl der benötigten Korn-
ponenten ist jedoch (bei entsprechender Länge von N) für viele Anwendungen zu groß.
Mit etwas weniger Aufwand kann man diese parallele Schaltung für den binären Fall realisieren, wenn also die Radix p = 2 verwendet wird. Die allgemeinen Digit-Multipli- zierer in Figur 9 werden in diesem Fall zu einfachen UND-Gattern, während die Ergänzungsfunktion Con durch ein einfaches XOR-Gatter realisiert werden kann, wenn der Modulus N ungerade ist (siehe Beispiel in Figur 5). Die Addierer bestehen nur aus zwei verketteten Volladdierern wie in Figur 13 gezeigt. Eine solche binäre parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs mit ungeradem Modulus ist in Figur 14 dargestellt.
Bei der Ausführung der modularen Addition mit binären Polynomen über Z 2 [x] N ( X ) wird, wie oben schon erwähnt, komponentenweise ohne überträge gerechnet. Für diese Berechnungen sind die Addierer einfache XOR-Gatter (siehe Fig. 13). Für die Berechnungen des ergänzten Produktkettenbruchs ausschließlich für die binären Polynome über Z 2 [X] N ( X ) mit ungeradem Modulus (oder präziser definiert, mit einem Modulus N(x), bei dem der freie Koeffizient N 0 ungleich Null ist) ist die parallele Schaltung noch einfacher, wie in Figur 15 zu sehen ist.
Eine Version mit wesentlich geringerem Bedarf an Komponenten erhält man, wenn man die parallelen Schaltungsblöcke in Figur 11 durch eine Struktur mit rückgekoppelten Ausgängen des Arbeitsregisters Reg w ersetzt und damit nur einen einzigen Block mehrmals benutzt. Zu diesem Zweck müssen die Digits des Operanden a einzeln und durch einen Takt gesteuert in die Schaltung eingeschoben werden. Die einfache Rückkopplungsregel folgt direkt aus der zuvor beschriebenen parallelen Schaltung und wird in Figur 16 gezeigt. Diese Schaltung wird als allgemeine seriell-parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs bezeichnet. Besonders günstig zu realisieren ist diese rückgekoppelte Schaltung im binären Fall, wenn also die Radix p = 2 verwendet wird. Wie in der parallelen binären Version werden die Digit-Multiplizierer in diesem Fall zu einfachen UND-Gattern, während die Ergänzungsfunktion Con durch ein einfaches XOR-Gatter realisiert werden kann, wenn der Modulus N ungerade ist. Die einzelnen Speicherelemente der benötigten Register werden zu einfachen D-Flipflops und die Addierer bestehen nur aus zwei verketteten Volladdierern wie in Figur 13 gezeigt. Aufgrund dieser strukturellen Eigenschaften ist diese binäre seriell-parallele Schaltung für die Berechnung des ergänzten Produktkettenbruchs mit ungeradem Modulus einfach zu realisieren. Sie ist als Sonderfall der Schaltung in Figur 17 dargestellt.
Im weiteren Verlauf dieses Dokuments wird nur der binäre Fall (p = 2) und N ungerade betrachtet. Für p = 2 mit N gerade und für andere Radixwerte muss zu Beginn die Ergänzungsfunktion (26) bestimmt werden, welche vom Modulus N und Radix p abhängt. Wie oben bereits beschrieben kann die Bestimmung dieser Funktion sehr einfach sein (wie etwa im binären Fall und N ungerade) für manche Parameterkombinationen p und N etwas komplexer und bei einigen sogar unmöglich. Falls man die Bestimmung der Ergänzungsfunktion (26) bewerkstelligen kann und somit die Ergänzungsschaltung Con spezifiziert ist, so ist die weitere Struktur der Schaltung für die Fälle p = 2 und N gerade sowie p ≠ 2 identisch mit dem im folgenden Sonderfall (für p = 2 und N ungerade). Aus diesem Grund werden diese Fälle nicht mehr betrachtet. In der Version der Schaltung in Figur 17 ist die maximale Taktrate der Schaltung bei der Ausführung der modularen Arithmetik mit ganzen Zahlen durch die dort auftretende Verbreitung von überträgen zwischen den einzelnen Addierern stark limitiert. Ist die Operandenlänge hinreichend groß, so sind aus diesem Grund nur niedrige Taktraten möglich. Bei der Ausführung der modularen Multiplikation mit binären Polynomen über Z 2 [X] N ( X ) tritt dieses Problem nicht auf, da in diesem Fall keine überträge zu betrachten sind: Es wird ja, wie oben erwähnt, komponentenweise ohne überträge gerechnet. Für diese Berechnungen sind die Addierer durch den Steuerungseingang G/P umschaltbar (siehe Fig. 13). Für die Berechnungen des ergänzten Produktkettenbruchs ausschließlich für die binären Polynomen über Z 2 [x] N (x) mit ungeradem Modulus (oder präziser definiert, mit einem Modulus N(x), bei dem der freie Koeffizient N 0 ungleich Null ist) ist die binäre seriell-parallele Schaltung wesentlich einfacher, wie in Figur 18 zu sehen ist.
Aufgrund der gewünschten Universalität der vorher beschriebenen binären seriellparallelen Schaltung muss jedoch die Problematik der überträge stets berücksichtigt werden. In der Schaltung in Figur 17 wird in jeder Taktperiode eine Multiplikation des Operanden b mit dem aktuellen Bit a t des Operanden a und eine gleichzeitige Ergänzung mit dem entsprechenden Ergänzungsfaktor i t durchgeführt. Um ein korrektes Ergebnis zu erhalten, muss man abwarten bis sich die überträge durch alle 7C+λ Addierer verbreitet haben. Diese Verbreitung der überträge durch eine lange Kette von Addierern beschränkt die Taktrate wesentlich.
Um dem Problem der limitierten Taktraten im Fall der Betrachtung von überträgen (d. h. bei modularer Multiplikation mit ganzen Zahlen) zu entgegnen, soll im Folgenden eine Pipeline-Struktur beschrieben werden, welche trotz Berücksichtigung von überträgen mit hohen Taktraten getrieben werden kann. Diese Struktur wird durch den Ein-
satz von Zwischenspeichern ermöglicht, welche in bestimmten, äquidistanten Abständen in die binäre seriell-parallele Schaltung (Fig. 17) eingefügt werden sollen. Siehe dazu Figur 19.
Die Blöcke, welche durch Einfügen der Zwischenspeicher (ZS) entstehen, werden Pipeline-Stufen (PS) genannt. Ihre Länge in Bit wird mit p bezeichnet und die Anzahl der Pipeline-Stufen in der gesamten Schaltung mit P. Daraus ergibt sich, dass das
Produkt p«P = TC genau die maximale Länge der Operanden (in Bit) ergeben muss.
Abgesehen von der letzten Pipeline-Stufe sind alle Pipeline-Stufen identisch. In der letzten Stufe werden in einer Verlängerung der arithmetischen Einheit (VAE) die überträge des Addierers A 9C - I in zwei zusätzlichen D-Flipflops über einen zusätzlichen Addierer A- X - aufgefangen. Die Zwischenspeicher sind in der letzten Stufe mangels einer nachfolgenden Stufe nicht mehr erforderlich.
Der ersten Pipeline-Stufe vorgeschaltet ist eine Steuerungseinheit (SE), in welcher der benötigte Takt erzeugt und gezählt wird. Zusätzlich wird in der Steuerungseinheit die Ergänzungsfunktion Con berechnet, die im hier betrachteten Fall mit p = 2 und N ungerade aus einem einfachen XOR-Gatter besteht. Außerdem ist ein D-Flipflop (mit FFa bezeichnet) für die Zwischenspeicherung des jeweils zuletzt eingeschobenen Bits a t des Operanden a in der Steuerungseinheit enthalten. Mit diesem Bit werden die ersten p Bits des Operanden b multipliziert und gleichzeitig wird eine Ergänzung mit dem entsprechenden Ergänzungsfaktor i, in der ersten Pipeline-Stufe durchgeführt. Um ein korrektes Ergebnis zu erhalten, muss man abwarten bis sich die überträge (jetzt nur noch) durch p Addierer der ersten Pipeline-Stufe verbreitet haben. Dieses Ergebnis wird dann im Arbeitsspeicher der ersten Pipeline-Stufe gespeichert (in den ersten p D-Flipflops des Registers Reg w), während die überträge am Ausgang des p- ten Addierers A p-1 der ersten Pipeline-Stufe im Zwischenspeicher ZSi gespeichert werden.
Jeder ZS besteht aus vier D-Flipflops bezeichnet mit Za 1 Zo 2 , Zθi und Zi. Der D-Flipflop Za speichert das Bit des Operanden a, mit dem in der Pipeline-Stufe die letzte Multiplikation durchgeführt wurde. Die dabei entstandenen überträge O 2 und O 1 des letzten Addierers in der Pipeline-Stufe werden in den D-Flipfllops Zo 2 und Zo 1 gespeichert, während der D-Flipflop Zi den Ergänzungsfaktor speichert, der dabei benutzt wurde.
Die in ZS 1 gespeicherten Bits werden in der zweiten Pipeline-Stufe benutzt. Dort wird die Multiplikation des in Za gespeicherten Bits a t mit den nächsten p Bits des Ope-
randen b und die entsprechende Ergänzung mit i t durchgeführt. Dies kann schon beginnen nachdem sich die überträge durch p Addierer der ersten Pipeline-Stufe verbreitet haben. Gleichzeitig startet die Multiplikation von a t+ i mit den ersten p Bits des Operanden b (und die entsprechende Ergänzung mit i t+ i) in der ersten Pipeline-Stufe. Nach demselben Prinzip funktionieren alle weiteren Pipeline-Stufen und beschleunigen dadurch, je nach gewählter Länge p der Pipeline-Stufen, mehr (für kleinere p - Werte) oder weniger (für größere p - Werte) die Arbeit der binären seriell-parallelen Schaltung.
Die gesamte binäre seriell-parallele Schaltung mit Pipeline-Struktur kann durch 6 funktionale Einheiten dargestellt werden: Die Register Reg a, Reg b und Reg N, die a- rithmetische Einheit (AE) bestehend aus der Addiererkette mit Zwischenspeicher und dem damit gekoppelten Arbeitsregister Reg w, die Taktverteilungseinheit (TVE), die durch Taktverteilungsstufen (TVS) die einzelnen Pipeline-Stufen treibt, sowie die Steuerungseinheit (SE), die den Takt generiert, zählt und alle zusätzlich üblichen Steuerungsfunktionen umsetzt (z.B. eine Rücksetzfunktion der Schaltung, oder den Start einer bestimmten modularen Operation). Einige einfach realisierbare Steuerungsfunktionen werden hier zugunsten einer besseren übersichtlichkeit des Wesentlichen nicht betrachtet. Es werden in SE noch zwei Multiplexer Mi und M 2 mit je drei
Eingängen hinzugefügt, die eine wichtige Rolle bei der Umsetzung von modularer Addition und Subtraktion spielen. Ihre Funktion wird später im Detail erklärt. Die gesamte binäre seriell-parallele Schaltung mit der Pipeline-Struktur ist in Figur 19 gezeigt. Ihre Block-Struktur, die auf Registern basiert, ist in Figur 20a dargestellt. In Figur 21 ist eine Pipeline-Stufe im Detail dargestellt. In Figur 22 ist die letzte, mit VAE erweiterte, Pipeline-Stufe gezeigt.
Wie in Figur 21 zu erkennen ist, kann man eine Pipeline-Stufe auch in eine serielle Verbindung von identischen Elementarschaltungen zerlegen, die die atomaren Zellen für die Berechnung des ergänzten Produktkettenbruchs ß N (a»b/2 sr ) oder ß N(x) (a(x)«b(x)/x :ir ) für p= 2 darstellen. Eine solche Zelle multipliziert, addiert und teilt mit p = 2 und wird deshalb als MAT-ZeIIe bezeichnet (siehe Figur 23). Die Block- Struktur der binären seriell-parallelen Schaltung mit der Pipeline-Struktur, die auf MAT-Zellen basiert, ist in Figur 20b gezeigt. In Figur 23 ist, neben einer detailtreuen MAT-ZeIIe, auch die Steuerungseinheit und ihre Verbindung mit der ersten Pipeline- Stufe dargestellt.
In Figur 24 ist das Prinzip der Taktverteilung in den einzelnen Pipeline-Stufen (PS) für ein Beispiel mit der PS-Länge p = 4 und nur mit den ersten beiden PS dargestellt. Das ist für eine vollständige Erklärung der Taktverteilung bei der Berechnung des ergänzten Produktkettenbruchs ausreichend. Wie in Figur 21 gezeigt, gehört zu einer Pipeline-Stufe noch eine Taktverteilungsstufe (TVS) bestehend aus je einem D-Flipflop T m , einem UND-Gatter 1/ m und einem Inverter J m . Die TVS sind bei allen Pipeline-Stufen identisch und bilden in einer seriellen Verbindung die gesamte Taktverteilungseinheit (TVE). Nur die letzte Pipeline-Stufe ist ohne TVS. Die TVE (siehe Fig. 19) steuert die einzelnen Pipeline-Stufen, sodass minimale Verzögerungen bei der Berechnung des ergänzten Produktkettenbruchs entstehen und zu den richtigen Zeitpunkten das korrekte Endergebnis in Reg w abgefangen und gespeichert werden kann. Um die Zwischenergebnisse in der ersten Pipeline-Stufe immer rechtzeitig zu berechnen, wird der D-Flipflop FFa (in welchem sich das aktuell benutzte Bit a t des Operanden a befindet) mit den steigenden Flanken (Fi 1 F 2 F^) des Taktes T getaktet
(siehe Fig. 24). Da das Register Reg a vom selben Takt gesteuert ist, startet jede steigende Flanke von T eine neue Zwischenberechnung in der ersten Pipeline-Stufe PSi mit dem jeweils nächsten Bit des Operanden a. Die steigenden Flanken des Taktes T finden eine halbe Taktperiode früher statt als die steigenden Flanken (Fn, Fi 2 F ü r) des invertierten Taktes Ti. In dieser halben Taktperiode sollen sich alle überträge in der Additionskette (A 0 , Ai, A 2 , A 3 ) der PSi schon verbreitet haben um damit dem Arbeitsregister das korrekte Zwischenergebnis der aktuellen Zwischenberechnung (mit dem Bit a t ) übergeben zu können. Aus diesem Grund werden die D-Flipflops W 0 bis W 3 des Arbeitsregisters in PSi mit den steigenden Flanken des invertierten Taktes Ti getaktet. Mit den selben Flanken werden auch die D-Flipflops Za 1 , ZO2-,, ZOi 1 und Zi 1 des Zwischenspeichers ZSi getaktet. Damit werden die notwendigen Parameter des Zwischenergebnisses der aktuellen Zwischenberechnung in PS 1 sowie das Bit a t und der Ergänzungsfaktor i t der nächsten (zweiten) Pipeline-Stufe PS 2 ohne weitere Verzögerung übergeben. Somit kann PS 2 die Zwischenberechnungen mit a t und i t sofort starten, während PS 1 die Zwischenberechnungen mit a t+1 und i t+1 startet. In PS 2 werden jedoch die D-Flipflops W 4 bis w 7 des Arbeitsregisters und des Zwischenspeichers ZS 2 mit den steigenden Flanken des Taktes T getaktet (umgekehrt wie in PS 1 , wo dafür Ti benutzt wurde). Deshalb wird Ti mit J 1 invertiert um T in PS 2 zu erzeugen. Die dritte
Pipeline-Stufe wird dann genau wie die erste getaktet, die vierte wie die zweite, usw. bis zur letzten Pipeline-Stufe PS P .
Der Zähler Zä in der Steuerungseinheit (SE) liefert nach 9C gezählten Taktperioden von Ti einen Anhalteimpuls (fallende Flanke), welcher mit Hilfe der D-Flipflops in der TVE söCjuθπziθii jeweils noch einer halben Taktpθricdθ die Tsktuπg der cinzεlnsn Pipelinestufen stoppt, da aufgrund der Pipelinestruktur das korrekte Endergebnis im Arbeitsregister Reg w zu verschiedenen, sequenziellen Zeitpunkten verfügbar ist. So werden die D-Flipflops W 0 bis w 3 in der PSi getaktet bis der Zähler Zä in SE 9C Taktperioden vom Anfang der Berechnung des ergänzten Produktkettenbruchs (in dem invertiertem Takt Ti) gezählt hat. Danach wird über das UND-Gatter VQ die Zuführung des invertierten Taktes gestoppt und damit das Endergebnis von PSi in W 0 bis W 3 zur Verfügung gestellt. Dieser nach TC Taktintervallen gestoppte invertierte Takt ist in Figur 25 mit (Ti)- K - bezeichnet. Um die Endergebnisse von PS 2 zum richtigen Zeitpunkt zu erfassen, wird über das UND-Gatter 1/i die Zuführung des Taktes T nach 7C+1/2 Taktperioden gestoppt (das D-Flipflop 7i verzögert den Anhalteimpuls um eine halbe Taktperiode). Der nach Tf +1/2 Taktperioden gestoppte Takt ist in Figur 25 mit
(T)<κ + i/2 bezeichnet. Der weitere Verlauf der Taktverteilung wird in den nachfolgenden
Pipeline-Stufen bis zu PS P nach dem gleichen Prinzip durchgeführt. Nachdem der in halben Taktperioden durch TVE verbreitete Anhalteimpuls die letzte Pipeline-Stufe PS P gestoppt hat, kann man mit ihm die ganze Schaltung durch Rücksetzen (engl, reset) für eine neue Berechnung des ergänzten Produktkettenbruchs bereitstellen. Dafür müssen vorher die neuen Operanden in dem entsprechenden Register gespeichert werden.
Mit dem vorgestellten Prinzip der Taktverteilung ist die Berechnung des ergänzten Produktkettenbruchs nur von der Steuerungseinheit SE gesteuert. Die bisher beschriebene binäre seriell-parallele Schaltung mit der Pipeline-Struktur für die Berechnung des ergänzten Produktkettenbruchs ^(aφß* " ) oder (mit Polynomen) βN(x)(a(x) # b(x)/x* r ) mit ungeradem Modulus lässt sich durch einfache Maßnahmen um die modulare Addition R N [a+b] und die modulare Subtraktion R N [b-a] erweitern. Diese Maßnahmen sind auch für die abschließende Korrektursubtraktion des Modulus N gemäß (32) bei der Auswertung der Kettenbruchtransformation notwendig.
Dazu ist eine zusätzliche Multiplexer-Reihe At = { M m ; (m = 1,... , 7C)} mit je fünf Eingängen erforderlich um einen parallelen Zugriff auf den Operanden a, sein Komplement a c , den Modulus N, dessen Zweierkomplement N 20 sowie auf die Konstante 1 = (00....0Oi) 2 zu ermöglichen. Der Operand b ist in der bisher beschriebenen Schaltung ohnehin in paraiieief Form verfügbar. Weiterhin muss zusätzlich eine Verbindung zwischen den Ausgängen der Addierer A 0 ,... Ax- und dem Register Reg b geschaffen werden, da dieses die Ergebnisse von Addition und Subtraktion sowie Multiplikation aufnehmen soll. Bei der Multiplikation passiert das über den Umweg der abschließenden Korrektursubtraktion des Modulus gemäß (32) bei der Auswertung der Ketten- bruch(rück)transformation. Alle hier eingeführten Erweiterungen innerhalb einer PS m ; m = 2,... ,(P-1) zeigt Figur 25. Sie sind in allen PS identisch bis auf die erste und die letzte Pipeline-Stufe. Die eingeführten Erweiterungen in PS P sind gesondert in Figur 26 dargestellt, wobei die kleinen Unterschiede zwischen PS m m = 2,... ,(P-1) und PSi in Figur 25 gekennzeichnet sind. In Figur 27 ist die Register-Struktur der ganzen erweiterten Schaltung dargestellt und sie zeigt, welche Argumente in paralleler Form verfügbar sind und welche Register indirekt (über die Addiererkette) parallel ladbar sind. Die modulare Addition R N [b+a] kann nun einfach durch die parallele Auswahl des O- peranden a über die Multiplexer-Reihe At 1 durch Einspeisung eines Bits mit dem Wert 1 in FFa über den Multiplexer At ? sowie durch Auswahl eines Bits mit dem Wert 1 ü- ber den Multiplexer At 2 in SE gestartet werden. Damit wird nur ein Teil des Zwischenergebnisses b+a von R N [b+a] in Reg b der ersten PS geschrieben. Mit weiteren P-1 halben Taktperioden werden die Bits mit dem Wert 1 an den Ausgängen von At; und
At 2 mit Hilfe von TVE durch alle D-Flipflops Za m und Zi m geschoben und somit b+a in Reg b vollständig erhalten. Dabei zählt der Zähler Zä nur bis 1 (nicht wie bei der Berechnung des ergänzten Produktkettenbruchs bis 1 TC). Bei der Berechnung von b+a ist das Register Reg w rückgesetzt (sein Inhalt wird auf 0 gesetzt) und wird nicht getaktet. Stattdessen wird das Register Reg b mit einem Taktanschluss T b versorgt um das Ergebnis b+a in den einzelnen Pipeline-Stufen parallel übernehmen zu können. Die dadurch in Reg b entstandene Summe b+a ist eventuell größer als der Modulus, also muss N in diesem Fall höchstens einmal (weil a < N und b < N angenommen wurde) abgezogen werden. Dazu muss das Zweierkomplement N zc des Modulus auf den Inhalt (b+a) von Reg b addiert werden. Das Zweierkomplement von ungeraden
Zahlen, wie der Modulus N eine ist, kann man durch bitweise Invertierung der einzelnen Bits und Setzen des LSB auf 1 erhalten. Das Zweierkomplement wird schon bereitgestellt und man kann es einfach über die Multiplexer M = { M m
; (m = 1 ,... , %)} auswählen. Durch Einspeisung eines Bits mit dem Wert 1 in FFa über den Multiplexer Mi sowie durcn Auswani eines Bits mit dem Weil 1
Die Entscheidung über das Abziehen des Modulus ist nicht ganz trivial, es müsste dazu überprüft werden, ob der Inhalt (b+a) in Reg b größer als N ist. Eine Lösung dieses Problems ohne einen aufwändigen Wort-Komparator einzuführen, liefert die Trial-And- E/ror-Methode. Bei ihr wird der Modulus auf jeden Fall einmal nach der oben beschriebenen Methode abgezogen. War das Zwischenergebnis b+a kleiner als der Modulus, entstand dabei ein überlauf im TC+i-ten Bit von Reg b (Register Reg b ist um zwei Bitstellen erweitert, siehe RbE in Fig. 26). Dieser überlauf kann einfach detektiert werden. Wenn er aufgetreten ist wird der Modulus N wieder (über eine Auswahl durch die Multiplexer M) aufaddiert.
Die modulare Subtraktion R N [b-a] erfolgt ganz ähnlich, nämlich durch Addition des Zweierkomplements a zc von a auf b. Dieses Zweierkomplement ist jedoch etwas schwieriger zu berechnen, da a im Allgemeinen nicht als ungerade vorausgesetzt werden kann. Aus diesem Grund muss die Addition des Zweierkomplements in eine Addition des (einfach zu erhaltenden) bitweisen Komplements a c und der Konstante 1 zerlegt werden. Die Multiplexer M bieten diese Möglichkeit (siehe Fig. 27).
Auch hier kann wieder der Fall auftreten, dass a > b galt, durch die Subtraktion also ein negatives Zwischenergebnis (zu erkennen am überlauf im TC+i-ten Bit von Reg b) aufgetreten ist. In diesem Fall muss der Modulus noch einmal auf den Inhalt von Reg b addiert werden.
Die Korrektursubtraktion gemäß (32) bei der Auswertung der Kettenbruchtransforma- tion erfolgt ebenfalls durch die Trial-And-Error-Methode wie bei der modularen Addition. Nach der Auswertung des ergänzten Produktkettenbruchs wird der Inhalt des Arbeitsregisters Reg w (wo das Ergebnis des ergänzten Produktkettenbruchs gespeichert ist) in das Operandenregister Reg b kopiert. Das wird wie eine Addition ausgeführt, nur werden die Ausgänge der beiden Multiplexer Mi und M 2 auf den Wert 0
gesetzt. Danach wird bei Bedarf mit der Trial-and-Error Methode der Modulus N, wie oben beschrieben, abgezogen.
Im polynomialen Fall ist der einzige Unterschied zu der oben beschriebenen Schaltung die Funktion der Addierer {A m }. Sie führen dann keine Addition mit übertrag aus, sondern ein einfaches XOR ihrer Operanden. Ein solcher einstellbarer Addierer ist schon in Figur 13 gezeigt. Es ist festzuhalten, dass im polynomialen Fall die modulare Addition nicht die bestmögliche Laufzeit hat. Es muss die gesamte Pipeline passiert werden - auch wenn dies aufgrund der fehlenden überträge keinen Mehrwert bringt. Aus diesem Grund benötigt eine modulare Addition auch im polynomialen Fall P/2 Taktperioden.
Die Invertierung bzw. Division wird von der hier beschriebenen Schaltung nicht berücksichtigt, da sie (wie oben beschrieben) mit Hilfe des kleinen Satzes von Fermat durch mehrfache Multiplikation durchgeführt werden kann. Dasselbe gilt für modulare Potenzierung mit einer natürlichen Zahl die z.B. durch die Square-and-Multiply- Methode durchgeführt werden kann.
Für die vorstehend vorgestellten parallelen Schaltungen für die Berechnung des ergänzten Produktkettenbruchs sind die Erweiterungen auf andere modulare Grundoperationen prinzipiell identisch mit der hier betrachteten binären seriell-parallelen Schaltung.
Alle Vorgänge bei der Auswertung des ergänzten Produktkettenbruchs sowie bei mo- dularer Addition, Subtraktion, Potenzierung mit einer natürlichen Zahl und Division können durch einen relativ einfachen endlichen Steuerungsautomaten in der Steuerungseinheit SE (Fig. 23) vorgenommen werden. Eine alternative Möglichkeit ist die Verwendung eines externen Prozessors, welcher diese Aufgabe übernimmt. Damit ermöglicht die binäre seriell-parallele Schaltung mit der Pipeline-Struktur eine sehr effiziente Durchführung der vollständigen modularen Arithmetik sowohl für ganze Zahlen als auch für Polynome über Z 2 [X] N( * ) und erfüllt somit die Forderung nach einer kompletten Schaltung.
Neben parallelen und seriell-parallelen Ausführungen die oben beschrieben wurden, lässt sich die Kettenbruchtransformation auch seriell implementieren. Diese Implementierung benötigt nur eine Pipeline Stufe (PS) deren Länge der Breite des Daten- Busses angepasst ist. Die PS ist durch eine Ergänzungsfunktions-Einheit EF, einen Zwischenspeicher ZS und eine Verlängerung der arithmetischen Einheit (VAE) ergänzt, wie in Figur 28 für den binären Fall dargestellt. Alle Operanden und Zwischenergebnisse werden in einem RAM-Speicher, der durch einen Mikrokontroller μC ge-
steuert ist, zwischengespeichert. Die Pipeline Stufe hat kein Arbeitsregister, da die Zwischenergebnisse direkt über die Datenbus Schnittstelle in den RAM geleitet werden. Wegen der Verschiebung um ein Bit (Teilen durch 2), benötigt die Berechnung eines ergänzten Zählers Z n ' des ergänzten Produktkettenbruchs in PS zwei passende, im RAM gespeicherte. Zwischenergebnisse die schon bei der Berechnung des Zählers Z n- i' gespeichert worden sind. Diese werden in die Register reg w' und reg w aus dem RAM geholt. Am Anfang der Berechnung von Z n ' holt man gleich zwei passende Zwischenergebnisse in reg w' und reg w. In weiteren Verlauf der Berechnung von Z n ' holt man aus dem RAM nur noch ein Zwischenergebnis in reg w', da das andere vorher aus reg w' in reg w einfach übernommen werden kann. Die überträge die am Ende der Pipeline Stufe in ZS gespeichert sind, werden über eine Rückkopplung vom Addierer A 0 für die nächste Berechnung übernommen. Am Ende der Berechnung von Z n ' wird noch über die Multiplexer Mux die VAE Einheit eingeschaltet um das MSB von Z n ' zu berechnen. Auch Blöcke der Operanden a holt man aus dem RAM in reg a, wo dann die einzelnen Bits a n in der Berechnung von Z n ' seriell eingeführt werden. Die vorgestellte binäre serielle Schaltung für die Berechnung des ergänzten Produktkettenbruchs e N (a»b/2 sr ) oder β N(X )(a(x)»b(x)/x ir ) mit ungeradem Modulus (N 0 =I) ist besonders für platzsparende Schaltungen wie Sensoren oder RFIDs geeignet. Damit wurde gezeigt, dass die Kettenbruchtransformation auch implementierungsflexibel ist. Sie kann als eigenständige Schaltung, als Schaltung, die durch Mikrocontrol- ler gesteuert ist, oder sogar als reines Software-Modul für einen Mikrocontroller eingesetzt werden.
Literatur
[I] Whitfield Diffie, Martin E. Hellman: „New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), pp. 644-654, November 1976.
[2] Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: „A Method for Obtaining Digital Signaturcs ar.d Public Key Cryptoεyεtems", CACM 21(2), pn. 120-126, Feb. 1978.
[3] Taher EIGamal: „A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory 31(4), pp. 469- 472, 1985.
[4] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: „Handbook of Applied Cryptography", CRC Press series on discrete mathematics and its appli- cations, CRC Press, ISBN: 0-8493-8523-7, 1997.
[5] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen and Frederik Vercauteren: „Handbook of Elliptic and Hyperelliptic Curve Cryptography", Chapter 26, pp. 617-645, Chapman & Hall/ CRC, 2006.
[6] Donald Knuth: „The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Addison-Wesley, Reading, Massachusetts, Sections 4.3.2. and 4.3.3., pp. 268-303, 1981.
[7] Niels Ferguson, Bruce Schneier: „Practical Cryptography", Wiley, Indianapolis, Indiana, Chapter 16, pp. 279-294, ISBN: 0-471-22357-3, 2003.
[8] IEEE P1363: „Standard Specifications For Public Key Cryptography", Draft P1363/D13, November 1999.
[9] Michael Rosing: „Implementing Elliptic Curve Cryptography", Manning Publi- cations Co., Greenwich, CT, Chapter 5, pp. 103-127, ISBN: 1-884777-69-4, 1999.
[10] Darrel Hankerson, Alfred J. Menezes and Scott A. Vanstone: „Guide to Elliptic Curve Cryptography", Springer-Verlag, Berlin, Germany / Heidelberg, Germa- ny / London, UK, Chapter 5, pp. 205-256, ISBN: 0-387-95273-X, 2004.
[I I] Douglas R., Stinson: „Cryptography: Theory and Practice", CRC Press, Inc., Sections 5.1 and 5.2, pp. 162-191 , ISBN: 0-8493-8521-0, 1986.
[12] Willi Geiselmann: „Algebraische Algorithmenentwicklung am Beispiel der A- rithmetik in endlichen Körpern", Shaker Verlag, Aachen, pp. 1-22, 1994.
[13] T. Beth, D. Gollman: „Algorithm Engineering for Public Key Algorithms", IEEE J. Selected Areas in Communications, 7(4):458_465, May 1989.
[14] Paul Barrett: „Implementing the Rivest Shamir and Adleman Public Key Enc- ryption Algorithm on a Standard Digital Signal Processor", in A. M. Odlyzko (E- ClIt-), Advances in Cryptology — CRYPTO '86, Vol. 263, Lecture Notes in Computer Science, Springer-Verlag, pp. 311-323, 1987.
[15] Andrew D. Booth: „A signed binary multiplication technique", Quarterly Journal of Mechanics and Applied Mathematics, Vol. 4, pp. 236-240, 1951.
[16] Ernest F. Brickell: „A Fast Modular Multiplication Algorithm With Application To Two Key Cryptography", In David Chaum, Ronald L. Rivest und Alan T. Sherman (Edit.), Advances in Cryptology: Proceedings of Crypto 82. Plenum Press, New York and London, pp. 51-60, 1983.
[17] Peter L. Montgomery: „Modular Multiplication Without Trial Division", Mathematics of Computation 44(170), pp. 519-521 , April 1985.
[18] Holger Sedlak: „The RSA Cryptography Processor", in David Chaum und Wyn L. Price (Edit.), Advances in Cryptology— EUROCRYPT 87, Vol. 304, Lectu- re Notes in Computer Science. Springer- Verlag, pp. 95-105, 1988.
[19] Dan Zuras: „More On Squaring and Multiplying Large Integers", IEEE Transactions on Computers, Vol. 43, No. 8, pp. 899-908, August 1994.
[20] Blakley, G. R.: „A Computer Algorithm for Calculating the Product A*B modu- Io M", IEEE on Computers, Vol. C-32, No. 5, pp. 497-500, May 1983.
[21] Morita Hikaru: „A Fast Modular-multiplication Algorithm based on a Higher Radix", in G. Brassard (Edit.): Advances in Cryptology-CRYPTO 1 89, LNCS 435, pp. 387-399, 1990, Springer Verlag Berlin Heidelberg 1990.
[22] J. Großschädl: „A Bit-Serial Unified Multiplier Architecture for Finite Fields GF(p) and GF(2 m )", LNCS 2162, Lecture Notes in Computer Science. Springer- Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 202 ff., 2001.
[23] J. Wolkerstorfer: „Dual-Field Arithmetic Unit for GF(p) and GF{2 m )", LNCS 2523, Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 500 ff, 2002.
[24] Laszlo Hars: „Long Modular Multiplication for Cryptographic Applications", LNCS 3156, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 45 ff, 2004.
[25] S.E. Eldridge, CD. Walter: „Hardware implementation of Montgomery's modular multiplication algorithm," IEEE Transactions on Computers, vol. 42, no. 6, pp. 693-699, 1993.
[26] Erkay Savas, Alexandre F. Tenca, Cetin Kaya Koc: „A Scalable and Unified Multiplier Architecture for Finite Fields GF(p) and GF(2 m )", in CHES: International Workshop on Cryptographic Hardware and Embedded Systems, CHES, LNCS- 1965, Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 277 ff., 2000.
[27] Wieland Fischer, Jean-Pierre Seifert: „High-Speed Modular Multiplication", in CHES: International Workshop on Cryptographic Hardware and Embedded Systems, CHES, LNCS-2964, Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 264 ff., 2004.
[28] Kai Schramm, Kerstin Lemke, Christof Paar: „Embedded Cryptography: Side Channel Attacks", in Kerstin Lemke, Christof Paar Marko Wolf (Eds.): „Embedded Security in Cars", Springer-Verlag, pp. 187-206, 2006.
[29] Kerstin Lemke: „Embedded Security: Physical Protection against Tampering Attacks", in Kerstin Lemke, Christof Paar, Marko Wolf (Eds.): „Embedded Security in Cars", Springer-Verlag, pp. 207-220, 2006.
[30] K. Gandolfi, C. Mourtel, F. Olivier: „Electromagnetic Analysis: Concrete Re- sults", LNCS 2162, Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 251 ff, 2001.
[31] S. Chari, J. R. Rao, P. Rohatgi: „Template Attacks", LNCS 2523, Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 13 ff, 2002.
[32] C. Clavier, J. -S. Coron, N. Dabbous: „Differential Power Analysis in the Pre- sence of Hardware Countermeasures", LNCS 1965, Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 252 ff, 2000.
[33] J. -S. Coron: „Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems", LNCS 1717, Lecture Notes in Computer Science. Springer- Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 292 ff, 1999.
[34] T.S. Messerges, E.A. Dabbish, R. H. Sloan: „Power Analysis Attacks of Mo- dular Exponentiation in Smartcards", LNCS 1717, Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany / Heidelberg, Germany / London, UK, p. 144 ff, 1999.