DE69716331T2

DE69716331T2 - Schaltung für Modulo-Multiplikations- und Exponentiationsarithmetik

Info

Publication number: DE69716331T2
Application number: DE69716331T
Authority: DE
Inventors: Hidenori Ebihara; Kiyoto Kawasaki
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1996-04-05
Filing date: 1997-04-02
Publication date: 2003-06-18
Anticipated expiration: 2017-04-03
Also published as: EP0801345A1; CN1172390A; CN1148643C; JPH09274560A; JP3525209B2; US5982900A; EP0801345B1; DE69716331D1

Description

HINTERGRUND DER ERFINDUNG

Die vorliegende Erfindung betrifft die Verschlüsselungs- und Entschlüsselungstechnik von Informationen, die auf dem Gebiet der Informationskommunikationsnetzwerke, Verkehrssysteme, Bankeinrichtungen, medizinischen Dienstleistungen, Verteilerindustrien und der gleichen verwendet werden, und insbesondere ein System, für eine Modulo- Exponentierungsarithmetik und ein arithmetisches Verfahren zum Durchführen der Modulo- Exponentierungsarithmetik zum Verwirklichen der Verschlüsselung und Entschlüsselung der Informationen.
Mit der Entwicklung der Informationskommunikationstechnik wird das Sicherstellen der Sicherheit eines Informationsnetzwerkes (zum Verhindern des Stehlens und der Zerstörung von Daten) als wichtig angesehen. Zu diesem Zweck wird die Verschlüsselungs- und Entschlüsselungstechnik von Informationen nicht nur auf dem Gebiet der Informationskommunikation eingesetzt, sondern auch auf Gebieten wie Verkehrssystemen, Bankeinrichtungen, medizinische Dienstleistungen, Verteilungsindustrien und dergleichen. Entsprechend ist eine Verschlüsselungs- und Entschlüsselungstechnik von dieser Art erforderlich, um einen hohen Sicherheitsgrad durch ein einfaches Prinzip realisieren zu können.
Um das Verständnis dieser Technik dieser Art zu erleichtern, wird jetzt die Verschlüsselung und Entschlüsselung von Informationen kurz beschrieben.
In der Kryptographie ist der "asymmetrische Kryptographiealgorithmus" qualitativ ausgezeichnet. Beim asymmetrischen Kryptographiealgorithmus sind der Verschlüsselungsschlüssel und Entschlüsselungsschlüssel von einander verschieden, und ein Schlüssel kann leicht aus dem anderen Schlüssel berechnet werden.
Die Vertreter des asymmetrischen Kryptographiealgorithmus beinhalten die RSA- Kryptographie, die Elgamal-Kryptographie, die Rabin-Kryptographie und die Williams- Kryptographie, die die Modulo-Exponentierungsarithmetik verwenden. Bei der Anwendung des Kryptographiealgorithmus gibt es das "digitale Signatur"-System, und es besteht gegenwärtig eine Tendenz seiner Standardisierung. Die Vertreter der digitalen Signatursysteme die zu standardisieren sind umfassen das RSA-Signaturverfahren, das Elgamal-Signaturverfahren, das Schnorr-Signaturverfahren und das DAS-Verfahren (digitaler Signaturalgorithmus), von denen alle die Modulo-Exponentierungsarithmetik einer langen Bitlänge verwenden. Entsprechend ist es unvermeidlich, eine arithmetische Einheit zu entwickeln, die die Modulo-Exponentierungsarithmetik mit einer verdammten Bitlänge in kurzer Zeit abschließen kann, um das digitale Signatursystem zu realisieren.
Die RSA-Kryptographie, Elgamal-Kryptographie, die Rabin-Kryptographie und die Williams-Kryptographie verwenden im Grunde die Modulo-Exponentierungsarithmetik-Form, die durch die folgenden Gleichungen (1) dargestellt wird. Die Gleichung (1) bedeutet, dass ein Rest von XY geteilt durch N berechnet wird. Weiter repräsentiert das X in (1) einen zu verschlüsselnden (entschlüsselnden) Klartext, und Y und N repräsentieren Schlüssel für die Verschlüsselung (Entschlüsselung).
XYmodN (1)
Die Modulo-Exponentierungsarithmetik kann verwendet werden, um die Verschlüsselung und die Entschlüsselung von Informationen auf einfache Weise durchzuführen und es erschweren, die Schlüssel durch Verlängerung der Bit-Länge der Operanden X, Y und N zu kryptoanalysieren.
Wenn jedoch die Bit-Länge des Operanden lang gemacht wird, braucht es eine lange Zeit, um die Modulo-Exponentierungsarithmetik durchzuführen. Der Punkt ist, wie die Modulo- Exponentierungsarithmetik mit einer langen Bit-Länge des Operanden in kurzer Zeit abgeschlossen wird.
Die tatsächliche Verschlüsselung und Entschlüsselung unter Verwendung der Modulo- Exponentierungsarithmetik und ihre Verwendung werden jetzt anhand des Beispiels einer RSA-Kryptographie beschrieben.

(1) ZUSAMMENFASSUNG DER VERSCHLÜSSELUNG UND ENTSCHLÜSSELUNG DER RSA KRYPTOGRAPIE

Für die Verschlüsselung wird die folgenden Gleichung verwendet:
C = Memodn (2)
Für die Entschlüsselung wird die folgende Gleichung verwendet:
M = Cdmodn (3)
wobei M eine zu verschlüsselnden Klartext darstellt und C einen verschlüsselten Klartext, d. h. einen chiffrierten Text, darstellt. In Gleichung (2) repräsentieren e und n Verschlüsselungsschlüssel und in Gleichung (3) repräsentieren d und n Entschlüsselungsschlüssel. Diese Schlüssel wurden zuvor mit den folgenden Bedingungen versehen:
n = p · q (4)
1 == e · dmod{LCM(p - 1, q - 1)} (5)
wobei "==" bedeutet, dass die linke Seite und die rechte Seite der Gleichung ähnlich sind, und LCM bedeutet das kleinste gemeinsame Vielfache. Weiter sind p und q Primzahlen. Zusätzlich sind die Schlüssel e und n öffentliche Schlüssel und d, n und q sind geheime Schlüssel.
Die obigen Gleichungen (4) und (5) definieren beide Bedingungen der numerischen Werte der Modulo-Exponentierungsarithmetik im Verschlüsselungsalgorithmus. Die Gleichung (4) definiert, das n ein Produkt großer Primzahlen p und q ist, die zueinander teilerfremd sind. Die Primzahl p und q sind beides ungrade Zahlen und entsprechend muss das Produkt n natürlich eine ungrade Zahl sein. Weiter zeigt Gleichung (5), das der Rest eines Produktes c · d von c und d geteilt durch das kleinste gemeinsame Vielfache der Werte, die man durch Subtrahieren von 1 von den in Gleichung (4) gezeigten p und q erhält, 1 ist.
Auf der Grundlage der Gleichungen (4) und (5) wird der Klartext M mittels Gleichung (2) verschlüsselt, und der verschlüsselte Klartext M (chiffrierter Text C) wird mittels Gleichung (3) entschlüsselt.

(2) BEISPIEL FÜR DIE VERSCHLÜSSELUNG UND ENTSCHLÜSSELUNG

Mit Bezug auf Fig. 2 wird als Beispiel eine Beschreibung für ein Verarbeitungsverfahren angegeben, das durch eine Übertragungsperson A und eine Empfangsperson B in dem Fall durchgeführt wird, in welchem "die Übertragungsperson A den Klartext M in den chiffrierten Text C verschlüsselt, um ihn zu übertragen, und die Empfangsperson B den chiffrierten Text C in den Klartext M entschlüsselt" (mit der digitalen Signatur).

DER PROZESS; DER DURCH DIE ÜBERTRAGUNGSPERSON A DURCHGEFÜHRT WIRD:

Der Klartext MA, der durch die Übertragungsperson A bereitgestellt wurde, wird mittels des eigenen geheimen Schlüssels dA der Übertragungsperson verschlüsselt, um einen Signaturtext CA (Signatur) herzustellen.
CA == MAdAmodnA (6)
Der öffentliche Schlüssel eß der Person B wird verwendet, um einen verschlüsselten Signaturtext cA (Verschlüsselung) herzustellen.
cA == CAeBmodnB (7)
Das cA wird an die Person B übertragen.

DER PROZESS, DER DURCH DIE EMPFANGSPERSON B AUSGEFÜHRT WIRD:

Der verschlüsselte Signaturtext cA, der durch die Person B empfangen wurde, wird mittels des eigenen geheimen Schlüssels dB der Empfangsperson entschlüsselt (Entschlüsselung).
CAdBmodnB == (CAeBmodnB)aBmodnB (8)
Wenn CAeB = X, kann die Gleichung (8) umgeformt werden in:
(CAeBmodnB)dBmodnB = (XmodnB)dBmodnB (9)
Wenn in Gleichung (9) X modnB = Y, d. h., wenn ein Rest von X geteilt durch nB Y ist und der Quotient daraus k ist, kann die Gleichung ausgedrückt werden durch:
X = k · nB + Y
Y = X - k · nB (10)
Wenn die Gleichung (10) für den entsprechenden Teil auf der rechten Seite von Gleichung (9) eingesetzt wird, lässt sich die Gleichung (9) ausdrücken durch:
(XmodnB)dBmodnB = YdBmodnB = (X - k · nB)dBmodnB (11)
Wenn (X - k · nB)dB der Gleichung (11) unter Verwendung von Konstanten ai (i = 1, 2, ...) expandiert wird, kann (X - k · nB)dB ausgedrückt werden durch:
(X - k · nB)dB = (XdB - a1 · XdB-1 · nB + a2 · XdB-2 · nB² - ... - ai · nBdB) (12)
Wenn die Gleichung (12) für den entsprechenden Teil der Gleichung (11) eingesetzt wird, gilt:
(XmodnB)dBmodnB = YdBmodnB = (X - k · nB)dBmodnB = (XdB - a1 · XdB-1 · nB + a2 · XdB-2 · nB² - ... - ai · nBdB)modnB = XdBmodnB - a1 · Xab-1 · nBmodnB + a2 · Xab-2 · nB²modnB - ... - ai · nBdBmodnB
Der zweite und die nachfolgenden Terme dieser Gleichung können alle durch nB geteilt werden, und können daher gestrichen werden. Folglich lässt sich diese Gleichung ausdrücken durch:
= XdBmodnB (13)
CAeB = X wird oben angenommen, und folglich erhält man die Gleichung, wenn X an CAeB zurückgegeben wird, wie folgt:
= (CAeB)dBmodnB (14)
Wenn der obige Prozess zusammengefasst wird, liest sich die obige Gleichung wie folgt:
CAdBmodnB == (CAeBmodnB)dBmodnB = (CAeB)aBmodnB
Da eB und dB die Gleichung (5) erfüllen, lassen sich eB und dB durch die folgenden Gleichung unter Verwendung einer bestimmten ganzen Zahl h ausdrücken.
eB · dB = h(pB - 1) + 1
Wenn das kleine Theorem von Fermat, dass nämlich die Gleichung: Xp-1modp = 1 für die Primzahl p und jede ganze Zahl X gilt, die zu p teilerfremd ist, verwendet wird, lässt sich die obige Gleichung ausdrücken durch:
CAeB·dBmodpB = CAh(p-1)+1modpB = CA · CAh(p-1)modpB = CAmodpB (15)
Da die obige Gleichung sogar dann erfüllt ist, wenn CA ein Vielfaches von pB ist, kann CAeB·dB - CA für alle CA durch pB geteilt werden. Ähnlich kann CAeB·dB - CA durch qB geteilt werden. Da pB und qB unterschiedliche Primzahlen sind, kann CAeB·dB - CA durch nB = pB · qB geteilt werden. Folglich gilt die folgende Gleichung.
cAdBmodnB == CAeB·dBmodnB == CAmodnB (= CA)
Der öffentliche Schlüssel eA der Übertragungsperson wird verwendet, um den Klartext MA (Authentizität der Signatur) herzustellen.
CAeAmodnA == (MAdA)eAmodnA == (MAeA)dAmodnA
Wenn die Berechnung in derselben Weise durchgeführt wird wie der obige Entschlüsselungsprozess wird die folgende Gleichung abgeleitet
= MA
Wie oben beschrieben, werden die Werte von e, d und n unter der Bedingung der Gleichungen (4) und (5) und der Modulo-Exponentierungsarithmetik bestimmt, und die Modulo- Exponentierungsarithmetikform, die durch Gleichung (1) dargestellt wird, wird grundsätzlich verwendet, so dass der Klartext verschlüsselt werden kann und der verschlüsselte Klartext entschlüsselt werden kann.
Wenn zum Beispiel n = 15, e = 3, p = 5, q = 3 und d = 11 (n = p · q = 5 · 3 = 15, e · dmod(p - 1) · (q - 1) = 3 · 11mod4 · 2 = 33mod8 = 1) und der Klartext M = 13, dann werden Verschlüsselung und Entschlüsselung wie folgt durchgeführt:
C = Memodn = 13³mod15 = 2197mod15 = 7
M = Cdmodn = 7¹¹mod15 = 1977326743mod15 = 13
Es wird bestätigt, das der Klartext M = 13 entschlüsselt wird.

(3) MODULO-EXPONENTIERUNGSARITHMETIK-VERFAHREN

Das Modulo-Exponentierungsarithmetik Verfahren, das bei der Verschlüsselung und Entschlüsselung verwendet wird, wird jetzt beschrieben.
Die Modulo-Exponentierungsarithmetik von A = MemodN wird durch Verwendung des Iterationsquadrat- und Multiplikationsverfahrens durchgeführt, welches im folgenden Ablauf 1 gezeigt ist, wobei die binäre Expansion der ganzen Zahl e = ek-1 ... e¹e&sup0; ist. ABLAUF 1
Das Iterationsquadrat- und Multiplikationsverfahren wird durch das Flussdiagramm von Fig. 3 ausgedrückt.
Als erstes wird ein Anfangswert 1 in ein Register A geladen. Der im Register A gespeicherte Wert wird mit sich selbst multipliziert, um A · A zu berechnen, und das Produkt A · A wird durch N geteilt, um einen Rest zu ermitteln. Der Rest wird in einem Register a gespeichert. Anschließend wird der im Register a gespeichert Wert in das Register A geladen. Wenn nun der Exponent e gleich 1 ist, wird der im Register A gespeicherte Wert mit dem Klartext M multipliziert, und das Produkt hieraus wird durch N geteilt, um einen Rest zu ermitteln, der im Register a gespeichert wird. Anschließend werden die Inhalte des Registers a wiederum in das Register A gespeichert. Wenn der Exponent gleich 0 ist, wird die obige Berechnung nicht durchgeführt, und der im Register A gespeicherte Wert bleibt wie er ist, ohne irgendeine Operation. Die obige Berechnung wird wiederholt vom höchstwertigen Bit zum niederwertigsten Bit von e durchgeführt, so dass der letztlich in das Register A gespeicherte Wert eine Lösung der zu berechnenden Modulo-Exponentierungsarithmetik ist.
Wie oben beschrieben, ist die Grundlage der Arithmetik die Multiplikation und Division (modulare Arithmetik), wie es durch die Gleichungen (16) und (17) gezeigt ist. Die Multiplikation führt A · A oder A · M für den Wert A aus, der 1 als Anfangswert aufweist, und die Division führt modN für den Wert aus, der durch jede Multiplikation erhalten wird. Ein paar von arithmetischen Operationen der Multiplikation und der Division (A · AmodN oder A · MmodN) werden entsprechend der Bitwerte von "e" wiederholt. Das heißt, die Multiplikation und die Division werden entsprechend den Inhalten der Bits vom höchstwertigen Bit zum niederstwertigen Bit von "e" durchgeführt.
Vorangehend wurde die Modulo-Exponentierungsarithmetik beschrieben, die eine Lösung durch Wiederholen der grundlegenden Restarithmetik oder modularen Arithmetik ermitteln kann, während die Anzahl der Wiederholungen höchstens einige Hundert oder Tausend beträgt, und die Wiederholungsoperation sogar entsprechend durch den Softwareprozess behandelt werden kann. Die modulare Arithmetik selbst erfordert jedoch einen groß bemessenen arithmetischen Schaltkreis und eine komplizierte Verarbeitungsprozedur, um die Division auszuführen, und demnach ist es wünschenswert, die modulare Arithmetik zu verbessern.
US 5499299 zeigt eine Vorrichtung nach dem Stand der Technik.

ZUSAMMENFASSUNG DER ERFINDUNG

Daher ist es ein Ziel der Erfindung, die Vorrichtung zum leichteren und effizienteren Durchführen zur Verfügung zu stellen, insbesondere eine nach den Ansprüchen 1 und 8.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Flussdiagramm der vorliegenden Erfindung;
Fig. 2 ist ein Diagramm zu Erläuterung eines definierten Beispiels zur Verarbeitung von Chiffriertext;
Fig. 3 ist ein Flussdiagramm, das eine Modulo-Exponentierungsarithmetik zeigt;
Fig. 4 ist ein Blockschaltbild, das schematisch eine erfindungsgemäße Hardware zeigt;
Fig. 5 ist ein Blockschaltbild, das schematisch eine erste erfindungsgemäße Ausführungsform zeigt;
Fig. 6 ist ein Diagramm, zum Erläutern einer Einheit zur Multiplikation und Addition;
Fig. 7 zeigt ein Hardwarebild zur Erläuterung der Arbeitsweise der ersten erfindungsgemäßen Ausführungsform;
Fig. 8 ist eine Blockschaltbild, das schematisch eine zweite Ausführungsform zeigt;
Fig. 9 ist eine Blockschaltbild, das schematisch eine dritte Ausführungsform zeigt;
Fig. 10 ist eine Blockschaltbild, das schematisch eine vierte Ausführungsform zeigt;
Fig. 11 zeigt ein Hardwarebild zur Erläuterung der Arbeitsweise der vierten erfindungsgemäßen Ausführungsform;
Fig. 12 zeigt ein arithmetisches Beispiel zur Erläuterung der Arbeitsweise der vierten erfindungsgemäßen Ausführungsform;
Fig. 13 ist eine Blockschaltbild, das schematisch eine fünfte Ausführungsform zeigt;
Fig. 14 zeigt ein Hardwarebild zur Erläuterung der Arbeitsweise der fünften erfindungsgemäßen Ausführungsform;
Fig. 15 zeigt ein Hardwarebild zur Erläuterung der Arbeitsweise der fünften erfindungsgemäßen Ausführungsform;
Fig. 16 zeigt ein arithmetisches Beispiel zur Erläuterung der Arbeitsweise der fünfte erfindungsgemäßen Ausführungsform;
Fig. 17 ist eine Blockschaltbild, das schematisch eine sechste Ausführungsform zeigt;
Fig. 18 ist eine Blockschaltbild, das schematisch eine siebte Ausführungsform zeigt;
Fig. 19 ist eine Blockschaltbild, das schematisch eine achte Ausführungsform zeigt;
Fig. 20 ist eine Blockschaltbild, das schematisch eine neunte Ausführungsform zeigt;
Fig. 21 ist ein Flussdiagramm, das die Berechnung von N' zeigt; und
Fig. 22 ist ein Beispiel für das Berechnen von N' und R'.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

In der Modulo-Exponentierungsarithmetik ist die Prozedur der Durchführung der grundlegenden modularen Arithmetik sehr kompliziert, und folglich wird der arithmetische Schaltkreis wie oben beschrieben groß. Daher hat Montgomery ein Schema vorgeschlagen, um eine Lösung einer modularen Arithmetik zu ermitteln, und zwar durch "Multiplikation" und einem einfachen Bit-Ketten-Prozess, ohne die modulare Arithmetik in der oben beschriebenen allgemeinen Weise durchzuführen. Die vorliegenden Erfindung setzt im Grunde Montgomerys vorgeschlagenes Schema ein, um die arithmetische Operation auszuführen, und entsprechend wird Montgomerys vorgeschlagenes Schema jetzt kurz beschrieben, während Maßnahmen zur Verkürzung der Operationszeit in jeder arithmetischen Operation für die vorliegende Erfindung charakteristisch sind.
In der modularen Arithmetik wird R als ein Exponent von 2 definiert, der etwas größer ist, als modN, und ein inverser Wert von R wird in der "Multiplikation von modN" [das bedeutet, das ein Rest von (einem Wert · einem Wert)/(Wert N) berechnet wird] als R' definiert wird (R · R'modN = 1 wird bewirkt). Weiter wird N' zur Erfüllung der Relation R · R' - N · N' = 1 und 0 < N' < R definiert (N' ist ein inverser Wert zu N in "Montgomerys Arithmetischen Schema"). Zu diesem Zeitpunkt wird zum Beispiel, wenn die modulare Arithmetik in der Form M (X) = XmodN durchgeführt wird, die Form durch die folgende Form ersetzt:
M'(X) = X · R'modN (18)
Wenn somit ein Berechnungsverfahren für eine im folgenden Ablauf 2 gezeigte Funktion REDC(X) durchgeführt wird, kann man die Lösung der modularen Arithmetik ohne Abhängigkeit von einem allgemeinen Verfahren wie oben beschrieben erhalten (es werden lediglich Multiplikation und Division durchgeführt). Der Ablauf 2 ist jedoch ein Ablauf zur Berechnung einer Lösung der modularen Arithmetik und ist kein Ablauf zur Berechnung einer Lösung der Modulo-Exponentierungsarithmetik. Die Lösung von Gleichung (18), die durch die obige Funktion erhalten wird, ist t oder t - N. Ablauf 2
Die obige Funktion enthält die Multiplikation unter Verwendung der arithmetischen Elemente N und N' und die Division unter der Verwendung des arithmetischen Elements R. Da R = 2n definiert wird, weist die Division unter Verwendung von R einen Quotienten auf, der ein Wert ist, welcher 2n übersteigt, und zwar aus einem Dividend und einem Rest, welcher ein Wert ist, der kleiner als 2n ist. Folglich untersucht die modulare Arithmetik der Gleichung (19) nur einen Wert der im Grunde kleiner als 2n ist, und die Division der Gleichung (20) untersucht im Grunde lediglich einen Wert der gleich oder größer als 2n ist. Das heißt, die Lösung der modularen Arithmetik kann nur durch Multiplikation und Addition ohne wesentliche Ausführung der Division (modulare Arithmetik) erhalten werden.
Die Relation von m, R und N wird nun unter Verwendung der Gleichungen (19) und (20) jeweils beschrieben.
In Gleichung (19) gilt:
m · N = ((XmodR) · N'modR) · N == X · N · N'modR == X · (R · R' - 1)modR == X · R · R'modR - XmodR == -XmodR
X + m · N == X + (-XmodR) == 0modR
Diese Gleichung bedeutet, dass ein Rest gleich 0 ist, wenn X + m · N durch R geteilt wird, das heißt, X + m · N kann durch R ohne Rest geteilt werden.
Da X + m · N eine Summe von "X" und "Multiplikation von N", gilt, (X + m · N)modN == XmodN + m · NmodN == XmodN
Folglich ergibt sich aus Gleichung (20)
t · RmodN == XmodN
wenn beide Seiten mit R' multipliziert werden, gilt
t · R · R'modN == tmodN == X · R'modN
wenn X der obigen Gleichung X · R'modN ein Multiplikatorwert nach der Berechnung von modN oder modR (Beschreibung später) ist, gilt
X < N · N < R · N < R · R
da m ein ausgeführtes Ergebnis von modR ist, gilt m < R. Folglich gilt:
m · N < R · N
Da X < R · N, gilt
X + m · N < R · N + R · N = 2R · N
folglich gelten die folgenden Gleichungen
t = (X + m · N)/R < 2N
t < 2N
wenn t größer als N ist, wird N von beiden Seiten der obigen Gleichung subtrahiert, so dass man die folgende Gleichung erhält.
t - N < N
Es ergibt sich aus dieser Gleichung, das t - N ein Wert ist, der modN unterzogen wurde.
Weiter werden nachfolgend die Berechnung von t = (X + m · N)/R der Gleichung (20) und der Abschluss der Berechnung von t beschrieben.
X + m · N ist notwendigerweise ein Vielfaches von R und folglich sind zum Beispiel wenn R = 2&sup5;&sup7;&sup6; ist, die Werte mit weniger als 576 Bits von X + m · N alle 0. Daher wird die Berechnung von t der Gleichung (20) auf die folgenden zwei Arten klassifiziert.
(i) wenn X kein Vielfaches von R ist;
Bitketten von X + m · N und R werden als Bild wie folgt ausgedrückt:
Bei der Berechnung der Gleichung (20) wird X + m · N ein Vielfaches von R, da man für t notwendigerweise einen ganzzahligen Wert erhält. Folglich ist X + m · N so wie das obige Bitkettenbild. Der unterstrichene Abschnitt ist eine Lösung von t. Der Grund ist, das, da X + m · N ein Vielfaches von R ist, ein Additionsergebnis von X und m · N, das kleiner als R ist, notwendigerweise 0 sein sollte, und die Werte, die durch ein ? angedeutet sind, ursprünglich nicht alle 0 sind, so dass jeder Übertrag zu einer Ziffer, die R übersteigt, im Verlauf der Addition erzeugt werden sollte. Folglich werden die Werte X und m · N, die kleiner als R sind, vernachlässigt, und die folgende Berechnung wird zur Ermittlung der Lösung durchgeführt.
t = (Wert von X größer R) + (Wert von m · N größer R) + 1
(ii) wenn X ein Vielfaches von R ist;
werden Bitketten von X und R als ein Bild wie folgt ausgedrückt:
R = 1000...0000
X = ?????000...0000
Zu diesem Zeitpunkt ist XmodR der Gleichung (19) 0 und folglich ist m = 0. Wenn m = 0, ist die Berechnung der Gleichung (20) t = X/R. Da ein ganzzahliger Wert notwendigerweise für t ermittelt wird, kann man die Lösung durch die folgende Gleichung erhalten.
t = (Wert von X größer R)
Es kann entschieden werden, ob X ein Vielfaches von R ist, und zwar basierend auf der Frage, ob ein Wert von X kleiner als R 0 ist oder nicht. Dies bedeutet, das die Berechnung für die gesamte Bitlänge von X bei der Berechnung von t nicht erforderlich ist, so dass der Berechnungsumfang und die Berechnungszeit reduziert werden können.
Bezüglich des Abschlusses der Berechnung von t ist das Berechnungsergebnis der Funktion REDX(X) ein Wert im Bereich von 0 < t < 2N, und wenn N < t, muss die Berechnung von t - N nochmals wie im Ablauf 2 gezeigt ausgeführt werden. Bezüglich des Berechnungsergebnisses t der Funktion REDC(X), die im Verlauf der Modulo-Exponentierungsarithmetik durchgeführt wird, wird jedoch die nachfolgende Berechnung so durchgeführt, wie sie ist, wenn das Ergebnis im Bereich von t < R liegt, sogar wenn die Relation N < t gilt. Der Grund dafür ist, das der N-Wert, der in diesem Prozess zurückgelassen wird, durch die später durchgeführte modulare Arithmetik entfernt wird.
Wenn man annimmt, dass das Berechnungsergebnis im Wege der Modulo- Exponentierungsarithmetik MmodN = S beträgt, wird die folgende Beziehung verwirklicht M = k1 · N + S = (k1 - 1) · N + N + S
Wenn man demnach berücksichtigt, das N + S in der modularen Arithmetik zu diese Zeit zurückgelassen wird, wird zum Beispiel der folgende Prozess A²modN (siehe Fig. 3) der Modulo-Exponentierungsarithmetik in der nächsten modularen Arithmetik durchgeführt, um dadurch die modulare Arithmetik nochmals auszuführen.
M1 = A · A = (N + S) · (N + S) = N² + 2 · N · S + S²
Daher gilt:
M1modN = (N² + 2 · N · S + S²)modN == S²modN
Die obige Gleichung bedeutet, dass der N-Wert entfernt wird, der in der vorherigen modularen Arithmetik zurückgelassen wurde. Sogar wenn M1 in der Modulo- Exponentierungsarithmetik von A · MmodN berechnet wird, wird ein ähnliches Ergebnis erhalten. Dasselbe ergibt sich beim Montgomery-Verfahren.
Zur Vereinfachung wird die Beschreibung unter Verwendung eines tatsächlichen numerischen Werts mit einer kurzen Bitlänge beispielhaft angegeben.
Wenn man annimmt, dass N = 13(1101), R = (10000) und t = 15(1111), was bei der letzten Berechnung der Funktion REDC(X) ermittelt wurde, weisen diese Werte folgende Beziehung auf N =< t < R < 2N. Bit 4 von t ist zu diese Zeit "0" während eine reine Lösung der modularen Arithmetik als Wert von t selbst jetzt noch nicht ermittelt wird. Da jedoch t nicht die Bitlänge von M übersteigt, eignet es sich als Ersatzwert für A · A · R'modN oder A · M · R'modN in der nächsten Modulo-Exponentierungsarithmetik. Das bedeutet, da die Ergebniswerte der Multiplikation A · A und A · M, die als nächstes durchgeführt werden, eine vorgeschriebene Bitlänge nicht übersteigen (im obigen Beispiel für den numerischen Wert: 4 Bits · 2 = 8 Bits), die Berechnung der "Multiplikation R'modN" mit der vorgeschriebenen Bitlänge fortlaufend durchgeführt werden kann.
t kann ausgedrückt werden durch: t = 15 = 13 + 2 = N + 2. Das bedeutet, dass der Wert von t, der durch die letzte Funktion REDC(X) ermittelt wurde, bei der Berechnung von modN "der Wert mit dem N ist, das zurückgelassen wurde". Wenn der Wert von t unverändert für A eingesetzt wird, wird A · A · R'modN wie folgt berechnet:
A · A · R'modN = (N + 2) · (N + 2) · R'modN = (N² + 4N + 4) · R'modN == N² · R'modN + 4N · R'modN + 4 · R'modN == 4 · R'modN
Dies weist dasselbe Ergebnis auf wie in dem Fall, bei dem A · A · R'modN mit einer reinen Lösung t = 2 der rnodN Arithmetik statt des Wertes von t berechnet wird, den man durch die letzte Funktion REDC(X) ermittelt hat und der nicht t = N + 2 ist.

(TATSÄCHLICHES BEISPIEL)

Die Berechnung von M'(X) = X · R'modN für X = 44123, R = 2&sup8; und N = 199:
Aus der Beziehung von R · R'modN = 1 und R · R' - N · N' = 1, erhält man: R' = 7 und N' = 9.
Folglich sollte man M'(X) = 44123 · 7mod199 = 13 = 0Dh erhalten.
Die Funktion REDC(X) wird verwendet, um die obige Lösung zu erhalten.
Aus X = 44123 = AC5Bh, R = 100h, N = 199 = C7h und N' = 9h, ergibt sich:
(Funktion REDC(X)
m = (XmodR) · N'modR = 5Bh · 9h modR = 333h modR = 33h
t = (X + m · N)/R = (AC5Bh + 33h · C7h)/R = D400h/R = D4h
Eine reine Lösung ist t - N = D4h - C7h = 0Dh, während t · t · R'modN unverändert ausgeführt wird (als nächstes Gleichung 1).
1. t = D4h : t · t = D4h · D4h = AF90h
m = (XmodR) · N'modR = 90h · 9h modR = 510h modR = 10h
t = (X + m · N)/R = (AF90h + 10h · C7h)/R = BC00h/R = BCh
2. t = 0Dh : t · t = 0Dh 0 · Dh = 00A90h
m = (XmodR) · N'modR = A9h · 9h modR = 5F1h modR = F1h
t = (X + m · N)/R = (00AF9h + F1h · C7h)/R = BC00h/R = BCh
Die Berechnungsergebnisse der obigen Gleichung (1) und (2) weisen dieselben Werte auf, wie durch die Unterstreichung angedeutet ist.
Das obige ist wichtig für die Reduzierung der Operationszeit. Das heißt, wenn das höchstwertige Bit von N Bit(n - 1) ist, wird t - N für Bit (n) = 1 für das ermittelte t ausgeführt, und die nachfolgende Arithmetik kann für Bit (n) = 0 ausgeführt werden.
Allgemein gilt für die Modulo-Exponentierungsarithmetik mit einem Operanden von einer Länge von 576 Bits: R = 2&sup5;&sup7;&sup6;. Wenn zu diesem Zeitpunkt das Berechnungsergebnis der Gleichung (20) 576 Bits übersteigt (wenn ein Überlauf über 576 Bit auftritt) gilt: t > = R. Weiter wird die Berechnung von t - N in diesem Fall durch die folgende Gleichung durchgeführt.
t - N = (Wert der unteren 576 Bits von t) + (invertierter Wert von N) + 1
Da der Wert N im Kryptographiealgorithmus ungrade ist, erhält man die Summe des invertierten Werts von N und 1 durch Berechnen des Inversen von N und ändern von dessen niederwertigsten Bit auf 1.
Die Funktion REDC zur Durchführung der in Ablauf 2 gezeigten Montgomery-Arithmetik ermittelt lediglich die Lösung der Montgomery-Arithmetik. Das heißt, wie in Gleichung (18) gezeigt, wird zur Erleichterung der Berechnung ein eigentümlicher numerischer Wert R' verwendet. Um die Lösung der Gleichung unter Verwendung der Multiplikation der modN-Form, die R' nicht erhält, zu ermitteln, ist es nötig, die Lösung der in Ablauf 2 gezeigten Montgomery-Arithmetik durch irgendeine Operation auf einen numerischen Wert zurück zusetzen, der R' nicht erhält.
In der vorliegenden Erfindung wird die folgende Eigenschaft eingesetzt, um den Wert R' zu löschen, der für die Montgomery-Arithmetik eigentümlich ist.
In M' (X) = X · R' modN,
gilt wenn X (X · R) ist:
M'(X · R) = (X · R) R'modN = XmodN
und wenn X (s · RmodN) ist, gilt
M'(X · RmodN) = (X · RmodN) R'modN = XmodN
In anderen Worten wird durch Anwenden der Montgomery-Arithmetik auf die Form ? · R oder ? · R modN das für die Montgomery-Arithmetik eigentümliche R' entfernt, so dass es in die Form ? modN geändert wird.
Wenn daher diese Eigenschaft auf die Modulo-Exponentierungsarithmetik unter Verwendung des Iterationsquadrat- und Multiplikationsverfahrens angewendet wird, welches in Ablauf 1 gezeigt ist, erhält man die Lösung der Modulo-Exponentierungsarithmetik, wie es im Ablauf 3 gezeigt ist. Genau gesagt lassen sich durch das Ausführen des Ablaufs 2 in jeder modN-Arithmetik der Gleichungen (24), (25) und (26), die in Ablauf 3 gezeigt sind, die Lösungen in den Gleichungen (24), (25) und (26) leicht ermitteln, so dass die Lösung der Modulo-Exponentierungsarithmetik unter Verwendung des Ablaufs 3 leicht erhalten wird.
Große Unterschiede zwischen dem Ablauf 1 und dem Ablauf 3 liegen darin, dass in Gleichung (23) der im Register A gespeicherte Anfangswert nicht 1 ist, und dass R modN (1 · RmodN) in Anbetracht einer späteren Montgomery-Arithmetik gespeichert wird, wobei Gleichung (25) anstatt des Wertes M von Gleichung (17) den Wert M · R modN verwendet, wobei die Gleichung (26) neu ausgeführt wird. Durch Speichern von RmodN im Register A vorab wird R' in den Gleichungen (24), (25) und (26) entfernt. Das Interationsquadrat und - Multiplikationsverfahren des Ablaufs 3 wird durch das in Fig. 1 gezeigte Flussdiagramm ausgedrückt.
Vor der Ausführung der Arithmetik müssen die vorab in Fig. 1 erforderlichen RmodN, M · RmodN und N' ermittelt werden.
Für RmodN
Bei der Modulo-Exponentierungsarithmetik, die in einem RSA-Kryptographen oder dergleichen verwendet wird, sind das höchstwertige Bit n-1 und das geringstwertige Bit b&sup0; von "N" 0. Folglich wird R zu diesem Zeitpunkt als 2n ausgewählt. Demnach gilt RmodN = R - N. R - N kann einfach durch Ermitteln der Inversen von N und ändern ihres geringstwertigen Bits auf 1 berechnet werden.
Für N' aus der Beziehung R · R'modN = 1, R · R' - N · N' = 1, 0 < R' und N' < R lässt sich die folgende Beziehung ableiten.
R' < N', N' - R < R - N
Für M · RmodN
Durch vorausgehendes Ermitteln von R²modN, kann M · RmodN durch die folgende Berechnung unter Verwendung der Montgomery-Arithmetik ermittelt werden.
M · (R²modN) · R'modN == M · R² · R'modN == M · RmodN
Wenn z. B. R = 2&sup5;¹² angenommen wird,
gilt 2&sup5;¹³modN = 2 · 2&sup5;¹²modN == 2 · (RmodN)modN = A
Wenn der folgende Ablauf 4 ausgeführt wird, in dem das obige A als Anfangswert verwendet wird, kann die Lösung von R²modN ermittelt werden. Ablauf 4
Der Berechnungsprozess im Ablauf 4 ist wie folgt:
i = 1: A = 2&sup5;¹³modN M(A,A) = 2&sup5;¹³ · 2&sup5;¹³ · 2&supmin;&sup5;¹²modN == 2&sup5;¹&sup4;modN
i = 2: A = 2&sup5;¹&sup4;modN M(A,A) = 2&sup5;¹&sup4; · 2&sup5;¹&sup4; · 2&supmin;&sup5;¹²modN == 2&sup5;¹&sup6;modN
i = 3: A = 2&sup5;¹&sup6;modN M(A,A) = 2&sup5;¹&sup6; · 2&sup5;¹&sup6; · 2&supmin;&sup5;¹²modN == 2&sup5;²&sup0;modN
i = 4: A = 2&sup5;²&sup0;modN M(A,A) = 2&sup5;²&sup0; · 2&sup5;²&sup0; · 2&supmin;&sup5;¹²modN == 2&sup5;²&sup8;modN
i = 5: A = 2&sup5;²&sup8;modN M(A,A) = 2&sup5;²&sup8; · 2&sup5;²&sup8; · 2&supmin;&sup5;¹²modN == 2&sup5;&sup4;&sup4;modN
i = 6: A = 2&sup5;&sup4;&sup4;modN M(A,A) = 2&sup5;&sup4;&sup4; · 2&sup5;&sup4;&sup4; · 2&supmin;&sup5;¹²modN == 2&sup5;&sup7;&sup6;modN
i = 7: A = 2&sup5;&sup7;&sup6;modN M(A,A) = 2&sup5;&sup7;&sup6; · 2&sup5;&sup7;&sup6; · 2&supmin;&sup5;¹²modN == 2&sup6;&sup4;&sup0;modN
i = 8: A = 2&sup6;&sup4;&sup0;modN M(A,A) = 2&sup6;&sup4;&sup0; · 2&sup6;&sup4;&sup0; · 2&supmin;&sup5;¹²modN == 2&sup7;&sup6;&sup9;modN
i = 9: A = 2&sup7;&sup6;&sup8;modN M(A,A) = 2&sup7;&sup6;&sup8; · 2&sup7;&sup6;&sup8; · 2&supmin;&sup5;¹²modN == 2¹&sup0;²&sup4;modN
Das Endergebnis (i = 9) ist die Lösung des zu ermittelnden R²modN.
Nach dem das in dieser Berechnung ermittelte R²modN mit M multipliziert wird, wird Ablauf 2 unter Verwendung des multiplizierten Ergebnisses als X in Ablauf 2 ausgeführt, um dadurch M · RmodN zu ermitteln.
Wie oben beschrieben, enthält die Berechnung im Ablauf 2 die Multiplikation unter Verwendung von N und N' und die Division unter Verwendung von R. Folglich kann die Lösung nur durch Multiplikation und Addition ohne wesentliche Ausführung der Division (modulare Arithmetik) ermittelt werden.
Wie oben beschrieben, können die Werte RmodN, M · RmodN und N', die im Flussdiagramm von Fig. 1 zuvor benötigt wurden, bereitgestellt werden.
Das Flussdiagramm der Fig. 1 wird jetzt ausgeführt.
Zuerst wird das zuvor ermittelte RmodN in einem Register A als Anfangswert gespeichert. (Das Register A kann z. B. ein Speicher sein. Dies gilt nachfolgend.) Das zuvor ermittelte M · RmodN wird in einem Register B gespeichert. Der Grund, warum M · RmodN im Register B gespeichert wird, ist, dass M · RmodN in Gleichung (25) gesichert wird, die im späteren Prozess verwendet wird.
Anschließend wird Gleichung (24) ausgeführt. Das heißt, das die Montgomery-Arithmetik A² · R'modN ausgeführt wird. Die Gleichung (24) erhält man wie oben beschrieben durch Ausführen des Ablaufs 2. Einen Wert, den man durch Quadrieren des in Register A gespeicherten Werts erhält, wird als X in Gleichung (19) berechnet, um m zu erhalten. Wie oben beschrieben, wird diese Berechnung durch die modulare Arithmetik unter Verwendung der Multiplikation und R durchgeführt. Da R = 2n definiert ist, kann die modulare Arithmetik unter Verwendung von R nur einen Wert des Dividenden untersuchen, der kleiner als oder gleich 2n ist. Anschließend wird das erhaltene m verwendet, um die Gleichung (20) auszuführen. Einen Wert, den man durch Quadrieren des in Register A gespeicherten Werts erhält, wird als X in Gleichung (20) berechnet, um t zu erhalten. Wie oben beschrieben, wird diese Berechnung durch die Multiplikation und Addition und Division unter Verwendung von R durchgeführt. Da R = 2n definiert ist, kann die Division unter Verwendung von R nur einen Wert des Dividenden untersuchen, der größer als oder gleich 2n ist. Dieses Berechnungsergebnis wird im Register A gespeichert.
Anschließend wird der Wert, der im Register a gespeichert ist in Register A gespeichert. Es erfolgt eine Bewertung der Bits des Exponenten e. Wenn das Bit 1 ist, wird Gleichung (25) ausgeführt. Das heißt, die Montgomery-Arithmetik A · B · R'modN wird ausgeführt. Die Gleichung (25) erhält man durch Ausführen des Ablaufs 2, wie oben beschrieben. Ein Produkt des in Register A gespeicherten Wertes und des in Register B gespeicherten Wertes wird als X in Gleichung (19) berechnet, um m zu ermitteln. Das ermittelte m wird verwendet, um Gleichung (20) auszuführen. Ein Produkt des in Register A gespeicherten Wertes und des in Register B gespeicherten Wertes wird als X in Gleichung (20) berechnet, um t zu ermitteln. Das Berechnungsergebnis wird in das Register a gespeichert. Das Berechnungsergebnis, das in Register a gespeichert ist wird in Register A gespeichert.
Wenn das Bit des Exponenten e 0 ist, wird die Berechnung der Gleichung (25) nicht durchgeführt, und der Prozess fährt mit dem nächsten Schritt fort.
Es erfolgt eine Beurteilung, ob die obige arithmetische Operation (Ausführung der Gleichungen (24) und (25)) für alle Bits des Exponenten e durchgeführt wird oder nicht. Wenn sie nicht durchgeführt wird, wird der Prozess zu dem Schritt zurückgesetzt, in welchem die Gleichung (24) durchgeführt wird, während, wenn sie durchgeführt wird, Gleichung (26) dann ausgeführt wird. Die Gleichung (26) erhält man durch Ausführen des oben beschriebenen Ablaufs 2. Die Berechnung erfolgt unter Verwendung des Werts, der in Register A als X in Gleichung (19) gespeichert ist, um m zu erhalten. Dann wird das erhaltene m verwendet, um Gleichung (20) auszuführen. Es erfolgt eine Berechnung unter Verwendung des Wertes, der im Register A als X in Gleichung (20) gespeichert ist, um t zu erhalten.
So wird die Abfolge der oben beschriebenen Operation abgeschlossen. Die Lösung der Modulo-Exponentierungsarithmetik, die oben beschrieben ist, wird wie folgt zusammengefasst.
1. Modulo-Exponentierungsarithmetik (MemodN)
2. Ein Iterationsquadrat- und Multiplikationsverfahren wird verwendet (Iteration von A · AmodN und A · ModN)
3. Die Berechnung von A · AmodN und A · MmodN wird durch das Montgomery- Verfahren ersetzt, da die Division kompliziert ist (Montgomery-Verfahren: M'(X) = X · R'modN)
4. M'(X) = X · R'modN kann unter Verwendung der Funktion REDC(X) realisiert werden. (Die Funktion REDC, die die Arithmetik von modN in die Form von modR umwandeln kann, um die Komplexität der Division zu vermeiden).
Eine Hardware zur tatsächlichen Realisierung der Erfindung wird jetzt mit Bezug auf die beiliegenden Zeichnungen verwendet.
Fig. 4 ist ein Blockschaltbild, das schematisch die eigentliche Hardware zeigt.
In Fig. 4 bezeichnen die Ziffern 401, 403, 405, 407, 409, 411, 413 und 415 Speicher oder Register. Die in den entsprechenden Kästen beschriebenen Werte werden in den Registern 401, 403, 405 407, 409, 411 und 413 gespeichert. Das Register 405 entspricht dem Register A das in Fig. 1 beschrieben wurde, und das Register 415 entspricht dem Register a. Ein Selektor 417 dient dazu, jede Ausgabe des Registers 407 oder des Registers 405 an eine arithmetische Einheit 419 entsprechend einer Anzeigeform eines Ein-Bit-nach-links- Verschieberegisters 409 übertagen, in welchen der Exponent e gespeichert wird. Der Selektor 417 entspricht einem Abschnitt zum Ausführen der "Verschiebung und des Übertrags von e" in Fig. 1. Das heißt, wenn der Exponentenabschnitt e 1 ist, wird M · RmodN an die arithmetische Einheit übertragen, und wenn der Exponentenabschnitt e 0 ist, wird dies nicht übertragen. Im Anfangsabschnitt des in Fig. 1 gezeigten Flussdiagramms wird, wenn A² ermittelt wird, eine Ausgabe der Registers 405 an die arithmetische Einheit übertragen.
Die arithmetische Einheit 419 enthält eine Multiplikationseinheit und eine Divisionseinheit. Die arithmetische Einheit 419 führt die Multiplikation und die Funktion REDC(X) aus.
Die Hardware zur Realisierung der vorliegenden Erfindung wird jetzt im Detail mit Bezug auf die Zeichnung beschrieben.

Erste Ausführungsform

Struktur

Das Berechnungsverfahren der Modulo-Exponentierungsarithmetik MemodN führt zwei Arten von arithmetischen Operationen A² · R'modN...(24) und A · B · R'modN...(25) (B entspricht einem Abschnitt, in welches "M · RmodN" der Gleichung (25) angeordnet ist) in dem arithmetischen Montgomery-Verfahren durch, welches oben beschrieben wurde, und zwar geschieht dies wiederholt auf der Grundlage einer vorgeschriebenen Prozedur entsprechend der Inhalte von den Bitwerten des Exponenten "e", und führt schließlich die folgende Gleichung (26) durch, wie sie in Fig. 1 und dem Ablauf 3 beschrieben wurde.
A · 1 · R'modN (26)
Entsprechend kann durch Vorsehen einer arithmetischen Einheit (nachfolgend als Coprozessor bezeichnet) zur Durchführung der drei Arten von modularen Arithmetiken der Coprozessor verwendet werden (die wiederholte Prozedur der Arithmetik kann durch ein Steuerverfahren einer Software oder Hardware realisiert werden), um die Lösung der Modulo- Exponentierungsarithmetik zu ermitteln.
Die vorliegende Erfindung betrifft den Coprozessor mit drei Arten von modularen Arithmetiken oder drei arithmetischen Modi.
Fig. 5 ist ein Diagramm, welches schematisch einen modularen arithmetischen Coprozessor nach einer ersten Ausführungsform der vorliegenden Erfindung zeigt.
In Fig. 5 stellen die dicken Pfeillinien, die die Blöcke verbinden, Busse zum Übertragen von Daten dar. Der modulare arithmetische Coprozessor der vorliegenden Erfindung umfasst eine Zeitgeber/Steuerschaltung T/C zur Zuführung von Operationstaktungen des gesamten Coprozessors und von Steuersignalen, die einer Art der Arithmetischen Operationen der drei Arten entspricht, an verschiedene Schaltungen in der arithmetischen Einheit und umfasst eine Mehrzahl von arithmetischen Wertespeichern Smem, N'mem, Nmem, Mmem, A'mem, Wlmem und Whmem zum Speichern arithmetischer Werte im Montgomery- Verfahren. Weiter umfasst der modulare arithmetische Coprozessor der vorliegenden Erfindung einen Hochgeschwindigkeits-Multiplizierer/Addierer Mul/Add zur Durchführung der Multiplikation und Addition, einen Hochgeschwindigkeitsaddierer Add zum Durchführen der Addition, ein Multiplikationsspeicherregister Xi-reg zum Speichern eines Multipliziererwerts, ein Multiplikandenspeicherregister Yi-reg zum Speichern eines Multiplikanden, ein Augendenspeicherregister Ai-reg zum Speichern eines Augenden und ein Register RH zum Speichern einer obersten Ziffer eines Wertes, der durch den Hochgeschwindigkeitsaddierer Add erzeugt wurde.
Der Hochgeschwindigkeitsaddierer Add, das Multipliziererspeicherregister Xi-reg das Multiplikandenspeicherregister Yi-reg und das Augendenspeicherregister Ai-reg haben die Funktion des temporären Speicherns eines Wertes, der aus den arithmetischen Wertespeicher ausgelesen wurde und der einer Eingabebitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entspricht.
Der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add ist ein Multiplizierer/Addierer der mit einer spezifischen Bitlänge, der mit einem Ausgabewert des Registers Xi-reg und einem Ausgabewert des Registers Yi-reg als Eingabewert bei der Multiplikationsoperation gespeist wird und der mit einem Ausgabewert des Registers Ai-reg als Eingabewert in der Additionsoperation gespeist wird. Eine Ausgabe des Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add wird in den Hochgeschwindigkeitsaddierer Add der nächsten Stufe als Additionseingabewert eingegeben.
Der Hochgeschwindigkeitsaddierer Add ist ein Addierer mit einer spezifischen Bitlänge, der die Addition des Ausgabewertes des Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add und des Ausgabewertes des Registers RH durchführt. Die obere Ziffer der Ausgabe des Hochgeschwindigkeitsaddierers Add wird dem Register RH oder den arithmetischen Wertespeichern zugeführt, und seine untere Ziffer wird den arithmetischen Wertespeichern zugeführt.

Operation

Die Operation des in Fig. 5 gezeigten Schaltkreises wird nun beschrieben.
Realisierungsverfahren für A2 · R'modN...(24)
Ein Wert A wird in beiden arithmetischen Wertespeichern A'mem und Wlmem gespeichert, ein Wert N' im Montgomery-Verfahren wird in dem arithmetischen Wertespeicher N'mem gespeichert und ein Wert N wird in den arithmetischen Wertespeicher N'mem gespeichert. Da die Werte N und N' Schlüssel für die Verschlüsselung/Entschlüsselung sind, werden die Werte durch den Bediener des Kryptongraphsystems für die die Daten übertragende/empfangende Person bestimmt. Ein Wert für R wird aus dem Wert von N bestimmt. Der Wert für A wird durch Ausführen von R modN wie oben beschrieben bestimmt.
Ein Modus 1-Signal wird an die Zeitgeber/Steuerschaltung T/C zugeführt, um dadurch Gleichung (24) für A² · R'modN auszuführen, wie es unten beschrieben ist.
Die Berechnung für A · A wird zuerst durchgeführt.
Ein Wert, der der eingegebenen Bitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entspricht, wird aus dem arithmetischen Wertespeicher A'mem in das Register Xi-reg geholt. Gleichzeitig wird ein Wert, der der eingegebenen Bitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entspricht, wird aus dem arithmetischen Wertespeicher Yi-reg in das Register Whnem geholt.
Wie in Fig. 6 gezeigt, werden, wenn die Bitlänge (z. B. 116 Bits) des Operationswerts die Multiplikationseingabeverarbeitungsbitlänge (z. B. 4 Bit) des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add übersteigt, eine Einheit der Multiplikation und Addition die Anzahle von Malen (4 · 4 = 16 Mal) so oft mit ihrer Operation wiederholt, wie es der Bitlänge des Operationswerts entspricht.
Die obige Operation ist im Detail durch das in Fig. 7 gezeigte Hardwarebild ausgedrückt.
Diese arithmetische Operation bedeutet, das Werte, die man durch Multiplizieren von Werten erhält, die man in Adressen A'3, A'2, A' 1 und A'0 des arithmetischen Wertespeichers A'mem gespeichert sind, mit Werten, die in Adressen W13, W12, W11 und W10 gespeichert sind, in Adressen Wh3, Wh2, Wh1, Wh0, W13, W12, W11 und W10 der arithmetischen Wertespeicher Whmem und Wlmem gespeichert.

Einheit der Multiplikation und Addition 1

Der Wert (Multiplikand), der in der Adresse W10 des arithmetischen Speichers Wlmem gespeichert ist, wird in das Register Yi-reg aufgenommen und der Wert (Multiplizierer), der in der Adresse A'0 des arithmetischen Wertespeichers A'mem gespeichert ist, wird in das Register Xi-reg aufgenommen. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und führt das Produkt daraus dem Hochgeschwindigkeitsaddierer Add zu. In diese Multiplikations- und Additionseinheit 1 wird der Addend, der dem Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add aus dem Register Ai-reg zugeführt wurde, als 0 angenommen, da die Zifferanordnungsoperation nicht erforderlich ist. (Der Wert des Registers Ai-reg wird auf 0 gesetzt oder der Wert, der im Register Ai-reg gespeichert ist, wird so angepasst, das er nicht im Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add zugeführt.) Weiter wird ein Signal mit hohem Pegel einem Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so dass die Inhalte des Registers RH nicht addiert werden. Bei der Multiplikation des Wertes des arithmetischen Wertespeichers A'mem und des Wertes des arithmetischen Wertespeichers Wlmem wird, da die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 1 die geringstwertige Ziffer des abschließenden Operationsergebnisses ist, die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 1 in der geringstwertigen Adresse Wl0 des arithmetischen Wertespeichers Wlmem als Operationsendergebnis dieser Multiplikation gespeichert (in Fig. 7 wird das Operationsendergebnis in der unterstrichenen Adresse gespeichert). Die obere Ziffer des Operationsergebnis der Multiplikations- und Additionseinheit 1 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 2

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'1 des arithmetischen Wertespeichers A'mem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und gibt das Produkt hieraus an den Hochgeschwindigkeitsaddierer Add weiter. Bei dieser Multiplikations- und Additionseinheit 2 wird der Addend, der dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add vom Register Ai-reg zugeführt wurde, als 0 angenommen (der Wert des Registers Ai-reg wird auf 0 gesetzt oder der im Register Ai-reg gespeicherte Wert wird so angepasst, das er dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add nicht zugeführt wird). Ein Signal mit geringem Pegel wird durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 1) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 2 wird in der geringwertigsten Adresse Wh0 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 2 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 3

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'2 des arithmetischen Wertespeichers A'mem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und gibt das Produkt hieraus an den Hochgeschwindigkeitsaddierer Add weiter. Bei dieser Multiplikations- und Additionseinheit 3 wird der Addend, der dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add vom Register Ai-reg zugeführt wurde, als 0 angenommen (der Wert des Registers Ai-reg wird auf 0 gesetzt oder der im Register Ai-reg gespeicherte Wert wird so angepasst, das er dem Hochgeschwindigkeitsmultiplizierer/Addierer Mut/Add nicht zugeführt wird). Ein Signal mit geringem Pegel wird durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 1) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 3 wird in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 3 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 4

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'3 des arithmetischen Wertespeichers A'mem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und gibt das Produkt hieraus an den Hochgeschwindigkeitsaddierer Add weiter. Bei dieser Multiplikations- und Additionseinheit 4 wird der Addend, der dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add vom Register Ai-reg zugeführt wurde, als 0 angenommen (der Wert des Registers Ai-reg wird auf 0 gesetzt oder der im Register Ai-reg gespeicherte Wert wird so angepasst, das er dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add nicht zugeführt wird). Ein Signal mit geringem Pegel wird durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 1) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 4 wird in der Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 4 wird in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 5

Das Register Yi-reg nimmt den Wert (Multiplikand) auf, der in der Adresse Wl1 des arithmetischen Wertespeichers Wlmem gespeichert ist, das Register Xi-reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'0 des arithmetischen Wertespeichers A'mem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend) auf, der in der Adresse Wh0 des arithmethischen Wertespeichers Whmem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert den Addenden zu diesem Multiplikationsergebnis, um das addierte Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. Bei dieser Multiplikations- und Additionseinheit 5 wird ein Signal mit hohem Pegel dem Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das die Inhalte (obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 4) des Registers RH nicht addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 5 wird in der Adresse Wl1 des arithmetischen Wertespeichers Wlmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 5 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 6

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'1 des arithmetischen Wertespeichers A'mem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert den Addenden zu diesem Multiplikationsergebnis, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 6 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 5) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 6 wird in der Adresse Wh0 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 6 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 7

Das Register Yi-reg hält den schon gespeicherten Wert (Muftiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'2 des arithmetischen Wertespeichers A'mem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert den Addenden zu diesem Multiplikationsergebnis, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 7 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 6) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 7 wird in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 7 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 8

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse A'3 des arithmetischen Wertespeichers A'mem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert den Addenden zu diesem Multiplikationsergebnis, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 8 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 7) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 8 wird in der Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 8 wird in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert.
Die Einheiten der Multiplikation und Addition 9 bis 16 werden wie in Fig. 7 gezeigt, entsprechend der Einheit der Multiplikation und Addition durchgeführt, die oben beschrieben wurde. Somit wird A · A, d. h. der Wert, den man durch multiplizieren des Werts, der in dem arithmetischen Wertespeicher A'mem gespeichert ist, mit dem Wert, der in dem arithmetischem Wertespeicher Wlmem gespeichert ist, erhält, in Form von Whmem - Wlmem ("-" ist kein Zeichen, welches die Subtraktion darstellt) gespeichert wird.
Im Falle des berechneten Ergebnisses 6752 h aus 64h · F5h bei der Berechnung von 8 Bits · 8 Bits wird zum Beispiel seine obere Ziffer 65h im arithmetischen Wertespeicher Whmem gespeichert, und die untere Ziffer 72h wird im arithmetischen Wertespeicher Wlmem gespeichert.
Anschließend wird die Funktion REDC verwendet, um die modulare Arithmetik unter Verwendung des Montgomery-Verfahrens durchzuführen. Wenn beim Montgomery-Verfahren die Modulo-Exponentierungsarithmetik mit einer Operandenlänge von n Bits n durchgeführt wird, ist R = 2n wie oben beschrieben. Es gibt Werte R' und N' mit einer Bitlänge von n in dieser Relation. Da der Wert von A · A in Form von Whmem - Wlmem gespeichert wird, ist die Berechnung von m wie folgt.
m = (XmodR) · N'modR = (Wlmem) · (N'mem)modR
Da (XmodR) ein Rest von X geteilt durch R ist, wird der Wert der kleiner ist als R untersucht, so dass die obige Gleichung wie folgt aussieht.
m = (Wlmem) · (N'mem)modR
Die obige Gleichung gibt einen Rest von (Wlmem) · (N'mem) geteilt durch R an, und folglich ist der untere n-Bit-Wert des Ergebnisses, welches man durch Ausführen von (Wlmem) · (N'mem) erhält, m.
Insbesondere wird der Wert, der in dem arithmetischen Wertespeicher Mmem gespeichert wird, wenn die Berechnung von (Wlmem) · (N'mem) entsprechend der Berechnung von A · A durchgeführt wird und das Ergebnis hieraus sowohl in den arithmetischen Wertespeicher A'mem als auch in den arithmetischen Wertespeicher Mmem in Form von A'mem-Mmem gespeichert wird, zu m.
Weiter erfolgt die Berechnung von t wie folgt.
t = (X + m · N)/R = [(Whmem - Wlmem) + (Mmem) · (Nmem)]/R
Um eine Lösung für die obige Gleichung zu erhalten, wird die Berechnung von (Mmem) · (Nmem) entsprechend A · A durchgeführt, und das Ergebnis hieraus wird sowohl in den arithmetischen Wertespeicher A' mem als auch Mmem in Form von A'mem- Mmem gespeichert. Nachfolgend wird die folgende Berechnung durchgeführt.
Mmem'1 + Wlmem (27) (Addition der unteren Ziffer)
A'mem' 1 + Whmem + Überlauf von (27) (28) (Addition der oberen Ziffer)
Die Gleichung (28) ist zu diesem Zeitpunkt das zu ermittelnde t.
Da der Wert, der kleiner oder gleich R ist, notwendigerweise 0 ist und das berechnete Ergebnis von Gleichung (27) 0 ist, ist es nicht nötig, es im Speicher zu speichern. Bei der Berechnung von Gleichung (27) wird während der Fall berücksichtigt wird, bei dem ein Überlauf einer Ziffer auftritt, 1 dem Anschluss (+1) des in Fig. 5 gezeigten Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add zu diesem Zeitpunkt bei der Berechnung der Gleichung (28) zugeführt. Es ist klar, das die Berechnungen leicht mittels des erfindungsgemäßen Coprozessors durchgeführt werden können.
Der Wert, den man durch Gleichung (28) erhält, wird in beiden arithmetischen Wertespeichern A'mem und Mmem gespeichert. Weiter wird eine 1 in einen Übertragsmarker CF geschrieben, wenn ein Zifferüberlauf auftritt.
Wenn der Übertragsmarker 1 ist, ist klar, dass es eine Beziehung t > n gibt und es folglich nötig ist, t - N zu berechnen. Dies wird durch Ausführen der folgenden Berechnung ermittelt.
[(Invertiertes Nmem + 1)'1] + Wlmem (29)
Das invertierte Nmem bedeutet die Inverse des Wertes, der in Nmem gespeichert ist.
Da der Wert von N, der in den arithmetischen Wertespeicher von Nmem gespeichert ist, im Kryptographiealgorithmus ungrade ist, wird der Wert (das invertierte Nmem + 1) in Gleichung 29 durch berechnen eine Kompliments 1 für Nmem und ändern des geringstwertigen Bits auf 1 erzielt. Diese Operation wird durch Übertragen von 1 an einen Anschluss Inv des Registers Xi-Reg, das in Fig. 5 gezeigt ist, realisiert (das Kompliment 1 für den Wert, der im Register Xi-Reg gespeichert ist, wird berechnet).

REALISIERUNGSVERFAHREN VON A · B · R'modN...(25)

Der Wert A wird im arithmetischen Wertespeicher Wlmem, der Wert B wird im arithmetischen Wertespeicher Wsmem, der Wert N' im Montgomery-Verfahren wird im arithmetischen Wertespeicher N'mem und der Wert N wird im arithmetischen Wertespeicher Nmem gespeichert.
Ein Modus 2 Signal wird dem Zeitgeber/Steuerschaltkreis T/C zugeführt, um dadurch die Gleichung (25) A · B · R'modN wie unten beschrieben auszuführen.
Die Berechnung von A · B wird zuerst durchgeführt.
Ein Wert, der der Eingabebitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entspricht, wird in das Register Xi-Reg aus dem arithmetischen Wertespeicher Smem aufgenommen. Auf ähnliche Weise wird ein Wert, der der Eingabebitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entspricht, in das Register Yi-Reg aus dem arithmetischen Wertespeicher Wlmem aufgenommen.
Die Berechnung von A · B ist dieselbe wie die von A · A, die oben beschrieben wurde, mit der Ausnahme, dass der Wert, der dem Register Xi-Reg zugeführt wurde, aus dem arithmetischem Wertespeicher Smem genommen wurde.
Anschließend wird die Funktion REDC verwendet, um die modulare Arithmetik unter Verwendung des Montgomery-Verfahrens durchzuführen.
Das Berechnungsverfahren ist dasselbe wie im Falle von A · A und das Berechnungsergebnis wird in beiden arithmetischen Wertespeichern A'mem und Wlmem gespeichert.
Wenn die Modulo-Exponentierungsarithmetik durchgeführt wird, werden die Gleichungen (24) und (25) wiederholt berechnet. Durch Verwenden des Realisierungsverfahrens der Berechnung, welches oben beschrieben wurde, werden die Berechnungsergebnisse der Gleichungen (24) und (25) in beiden arithmetischen Wertespeichern A'mem und Wlmem gespeichert. Da die Initialisierung der arithmetischen Werte am Beginn der Berechnung jeder Gleichung nicht erforderlich ist, kann demnach die wiederholte Berechnung gleichmäßig durchgeführt werden.

REALISIERUNGSVERFAHREN FÜR A · R'modN...(26)

Der Wert A wird im arithmetischen Wertespeicher Whnem gespeichert, der Wert N' im Montgomery-Verfahren wird im arithmetischen Wertespeicher N'mem gespeichert und der Wert N wird im arithmetischen Wertespeicher Nmem gespeichert.
Ein Modus-3-Signal wird dem Zeitgeber/Steuerschaltkreis T/C zugeführt, um dadurch die Gleichung (26) mit A · R'modN wie unten beschrieben auszuführen. In der Gleichung ist es jetzt möglich, die Multiplikation A · ? auszuführen. Folglich wird nur die modulare Arithmetik durchgeführt, die das Montgomery-Verfahren verwendet.
Das Berechnungsverfahren von m in der modularen Arithmetik ist im wesentlichen dasselbe wie in dem Fall von A · A. Der Wert des arithmetischen Wertespeichers Wlmem ist, wenn das Berechnungsergebnis in beiden arithmetischen Wertespeichern A'mem und Wlmem in Form von A'mem-Wlmem gespeichert wird, der Wert m.
Die weitere Berechnung von t ist wie folgt.
t = (X + m · N)/R = [Wert größer R des Ergebnisses von (Wlmem) · (Nmem)] + 1 (30)
Bei der Berechnung der Gleichung (26) ist das oben genannte X A, und es gibt keinen Wert über R (es wird als 0 betrachtet). Folglich ist es nicht nötig, die Addition des Wertes (Whmem) oberhalb von R durchzuführen, wie es im Realisierungsverfahren der Gleichung (24) beschrieben wurde. Das (X + m · N) notwendigerweise ein Vielfaches von R ist, ist es nicht nötig, den Wert X, der durch den zweiten Term von Gleichung (30) angedeutet wird, zu addieren, und die Lösung erhält man stattdessen durch "[Wert über R des Ergebnisses von (Wlmem) · (Nmem)] + 1". Das heißt, dass der Wert A in dieser Berechnung nicht 0 ist, wenn die modulare Arithmetik im Kryptographiealgorithmus verwendet wird.
Folglich wird in Gleichung (30) die Berechnung von (Wlmem) · (Nmem) zuerst durchgeführt, und das Berechnungsergebnis hieraus kann in den arithmetischen Wertespeichern A'mem und Wlmem in der Form A'mem-Wlmem gespeichert werden. Der Wert im Speicher A'mem, der als Ergebnis hieraus erhalten wurde, ist die zu ermittelnde Lösung. (Alle Operationen der Modulo-Exponentierungsarithmetik werden durch die Ausführung dieser arithmetischen Operation beendet, und folglich kann das Speichern im arithmetischen Wertespeicher Whnem ausgelassen werden). Mit dem Takt des Speicherns des abschließenden Berechnungsergebnisses zu dieser Zeit in der geringstwertigen Ziffer des arithmetischen Wertespeichers A'mem wird eine 1 an den Anschluss +1 zugeführt, der in Fig. 5 gezeigt ist, um die Addition von 1 in Gleichung (30) auszuführen.
Wie oben beschrieben, wird nach der ersten Ausführungsform der Multiplizierer/Addierer (ein Multiplizierer und ein Addierer können separat vorgesehen werden) mit einer vorgeschriebenen Bitlänge als ein Kernstück der arithmetischen Einheit zur Verfügung gestellt, und die Steuersignale aus dem Schaltkreis zur Erzeugung des Zeitgeber/Steuersignals werden einer Schaltung zugeführt, die an seinem Rand angeordnet ist, um dadurch die modulare Arithmetik mit einer langen Bitlänge realisieren zu können, wobei das Montgomery- Verfahren oder die Modulo-Exponentierungsarithmetik verwendet wird. Nach diesem System kann die Schaltungsabmessung klein gemacht werden und eignet sich für ein LSI, da das Kernstück der arithmetischen Einheit durch die arithmetische Einheit mit einer beschränkten (vorgeschriebenen) Bitlänge konfiguriert werden kann.

ZWEITE AUSFÜHRUNGSFORM

Struktur

Fig. 8 ist ein Blockschaltbild, welches schematisch einen modularen arithmetischen Coprozessor gemäß einer zweiten erfindungsgemäßen Ausführungsform zeigt.
Die zweite Ausführungsform enthält zusätzlich zur Konfiguration der ersten Ausführungsform (Fig. 5) einen Schaltkreis zum Detektieren, dass ein arithmetischer Wert 0 ist, und zum Steuern der Abfolge der nächsten arithmetischen Operation.
Genauer gesagt wird dieser Steuerschaltkreis durch NullC in Fig. 8 dargestellt. Der Steuerschaltkreis NullC ist ein Schaltkreis zum Detektieren, dass ein arithmetischer Wert 0 ist, um die Abfolge für die nächste arithmetische Operation zu steuern, und enthält einen Eingabeanschluss, welchem das Ausgabesignal des Hochgeschwindigkeitsaddierers Add zugeführt wird, sowie einen Ausgabeanschluss. Der Steuerschaltkreis erzeugt aus dem Ausgabeanschluss ein Signal, um das Zeitgeber/Steuersignal, das durch den Zeitgeber/Steuerschaltkreis T/C erzeugt wurde, um das Signal zum Betreiben der verschiedenen Schaltkreise im Coprozessor einer vorbestimmten Steuerung zu unterziehen.

Betrieb

Bei der Berechnung der Funktion REDC, die im Realisierungsverfahren für die Gleichungen (24) und (25) der ersten Ausführungsform beschrieben wurde, kann der Wert X, den man als Ergebnis der vorangegangenen Multiplikation erhält, in die folgenden zwei Fälle klassifiziert werden.
a. wenn er ein Vielfaches von R ist
ist der Wert (Wlmem), den man in der vorausgegangenen Berechnung erhält, 0.
b. wenn er kein Vielfaches von R ist,
ist der Wert (Wlmem), den man in der vorausgegangenen Berechnung erhält, nicht 0.
In der Ausführungsform detektiert der Steuerschaltkreis NullC, ob der Wert der kleiner als R ist für den X-Wert (Wert von A · A oder A · B) 0 ist oder nicht und führt die Folge der nachfolgenden arithmetischen Operation entsprechend dem detektierten Ergebnis wie folgt durch.
Im Fall von a. ist klar, das m = 0, da X modR = 0. Folglich ist es zu diesem Zeitpunkt nicht nötig, die Berechnung von m durchzuführen.
Die Berechnung von t ist wie folgt.
t = (X + m · N)/R = X/R = Whmem (31)
Dies deutet an, dass die obere Ziffer des berechneten Ergebnisses von A · A und A · B ein unveränderter Wert t ist. Folglich wird in dem Prozess in diesem Fall durch Hardware der im arithmetischen Wertespeicher Whmem gespeicherte Wert in beiden arithmetischen Wertespeichern A'mem und Whmem unverändert gespeichert, und es erfolgt eine Vorbereitung für die nächste wiederholte arithmetische Operation. D. h. wenn der Wert, der kleiner als R ist, für den Wert X (der Wert der durch die voherige Berechnung erhalten wurde) 0 ist, ist es nicht nötig, t zu berechnen. Das bedeutet, dass es nicht nötig ist, bei der Berechnung von t die gesamte Bitlänge von X zu berechnen.
Im Fall von b. wird die Berechnung zum Ermitteln von m in derselben Weise wie bei der ersten Ausführungsform durchgeführt, und das berechnete Ergebnis wird in beiden arithmetischen Wertespeichern A'mem und Wlmem in Form von A'mem-Wlmem gespeichert. Der im arithmetischen Wertespeicher Wlmem gespeicherte Wert wird so eingestellt, dass er den Wert m hat. Die Berechnung von t wird fortgesetzt durchgeführt.
Die Berechnung von t ist wie folgt.
t = (X + m · N)/R = Whmem + [Wert größer R des Ergebnisses von (Whnem) · (Nmem)] + 1
Die Lösung der Gleichnung (32) erhält man durch Ausführen der Berechnung (Wlmem) · (Nmem), um das berechnete Ergebnis in beiden arithmetischen Wertespeichern A'mem und Wlmem in Form von A'mem - Wlmem zu speichern, wobei anschließend die Berechnung der folgenden Gleichung durchgeführt wird.
(A'mem) · 1 + (Whmem) + 1 (33)
Der Grund ist, dass es, da der Wert X + m · M notwendigerweise ein Vielfaches von R ist, nicht nötig ist, mit Absicht den Wert zu berechnen, der kleiner als R ist. In Gleichung (33) wird zum Berechnungstakt der geringstwertigen Ziffer eine 1 dem Anschluss +1 zugeführt, der in Fig. 5 gezeigt ist, um die Addition von 1 in Gleichung (33) auszuführen.
Das berechnete Ergebnis, das in Gleichung (33) erhalten wurde, wird in beiden arithmetischen Wertespeichern A'mem und Wlmem gespeichert, und wenn ein Überlauf einer Ziffer auftritt, wird eine 1 in den Übertrags-Marker CF geschrieben. Der nachfolgende Prozess ist derselbe wie der der ersten Ausführungsform.
Wie oben beschrieben, kann nach der zweiten Ausführungsform die Addition der Steuerschaltung (die mit einer Schaltkreisabmessung konfiguriert werden kann, die der Bitlänge des Multiplizierers/Addierers entspricht und bei der es sich um eine klein bemessene Schaltung handelt) zum Detektieren, dass der arithmetische Wert 0 ist und zum Steuern der Abfolge der nachfolgenden arithmetischen Operationen die Löschung des arithmetischen Wertespeichers Mmem des den in der ersten Ausführung beschriebenen Coprozessors und die Löschung des Umfangs einer arithmetischen Operation erzielen. Entsprechend kann die Löschung von Hardware und eine Verringerung der Operationszeit erzielt werden.

Dritte Ausführungsform

Struktur

Fig. 9 ist ein Blockschaltbild, welches schematisch einen modularen arithmetischen Coprozessor nach einer dritten erfindungsgemäßen Ausführungsform zeigt.
Die dritte Ausführungsform erhält zusätzlich zur Konfiguration der ersten Ausführungsform (Fig. 5) oder der zweiten Ausführungsform (Fig. 8) eine Steuerschaltung zur Auswahl der Bitlänge zum Auswählen der Bitlänge des Operanden, um das Takt/Steuersignal zu verändern.
Insbesondere wird die Steuerschaltung zur Auswahl der Bitlänge durch LenCont von Fig. 9 dargestellt. Die Steuerschaltung zur Auswahl der Bitlänge LenCont wird betrieben, um das Operationstaktsignal, welches durch den Takt/Steuerschaltkreis T/C erzeugt wurde, und das Steuersignal zu steuern, welches den verschiedenen Schaltungen im Coprozessor entsprechend einem Eingangssignal Sel-len zugeführt wurde.

Operation

Im Betrieb des Coprozessors werden der Wert R, der Wert R', der durch den Wert R bestimmt wurde, die Bitlänge des N'Werts und die wiederholte Prozedur (Anzahl der Wiederholungen) der Multiplikation und Addition der vorgeschriebenen Bitlänge entsprechend der Änderung der Bitlänge des Operanden verändert.
Wenn zum Beispiel der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add eine Bitlänge von 16 Bit aufweist und die Multiplikation A · A mit einer Operandenbitlänge von 512 Bit durchführt, ist die Zahl der Wiederholungen der Multiplikation und Addition durch den Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add wie folgt.
(512/16) · (512/16) = 1024 mal
Andererseits beträgt diese Anzahl für die Operandenbitlänge von 768 Bits wie folgt.
(768/16) · (768/16) = 2304 mal
Die Abfolgen diese Berechnung sind unterschiedlich. Da weiterhin wie oben beschrieben der Wert R in einzigartigerweise entsprechend der Operandenbitlänge bestimmt wird, werden die Bitlängen der Werte R' und N' entsprechend verändert.
Die Steuerschaltung zur Auswahl der Bitlänge LenCont steuert den Faktor für die obigen Änderungen, das heißt die Schaltung steuert, um das Operationstaktsignal und das Steuersignal zu erzeugen, welches durch den Takt/Steuerschaltkreis T/C entsprechend der ausgewählten Bitlänge generiert wurde.
Im Allgemeinen kann die Steuerschaltung zur Auswahl der Bitlänge LenCont durch eine relativ klein bemessene Schaltungskonfiguration, wie z. B. PLA-oder Logik-Schaltkreise realisiert werden.
Wie oben beschrieben, wird bei dem Coprozessor der dritten Ausführungsform die Steuerschaltung zur Auswahl der Bitlänge LenCont hinzugefügt, um dadurch in der Lage zu sein, die modulare Arithmetik oder die Modulo-Exponentierungsarithmetik mit verschiedenen Operandenbitlängen auszuführen.

Vierte Ausführungsform

Struktur

Die Grundlage der arithmetischen Operation des in den obigen Ausführungsformen beschriebenen Coprozessors ist die Multiplikation und Addition mit der vorgeschriebenen Bitlänge. Das Verfahren des Wiederholens der zugrundeliegenden Multiplikation und Addition zur Realisierung der modularen Arithmetik oder der Modulo- Exponentierungsarithmetik ist wie das, welches in den obigen Ausführungsformen beschrieben wurde.
Da bei den obigen Ausführungsformen jedoch der Coprozessor nur den Modus der modularen Arithmetik durchführt, ist seine Anwendung auf die modulare Arithmetik beschränkt, obwohl die Grundlage der arithmetischen Operation die Multiplikation und die Addition ist.
Folglich wird der Multiplikations- und Additionsmodus mit einer langen Bitlänge hinzugefügt, welcher die Grundlage für verschiedene arithmetische Operationen bildet, um die Generalität des Coprozessors zu verbessern.
Fig. 10 ist ein Blockschaltbild, das schematisch den modularen arithmetischen Coprozessor nach der vierten erfindungsgemäßen Ausführungsform zeigt.
Bei der vierten Ausführungsform wird der Multiplikations- und Additionsmodus den oben beschriebenen Ausführungsformen hinzugefügt. Um diesen Modus auszuführen, wird ein Modussignal 4 dem Takt/Steuerschaltkreis T/C zugeführt.

Operation

Ein Ausführungsbeispiel der unten gezeigten Multiplikation und Addition wird nun beschrieben.
A · B + C (34)
Als aller erstes werden in Gleichung (34) die Werte A, B und C in den arithmetischen Wertespeichern Wlmem, Smem und Whmem gespeichert. Das Modussignal 4 wird dem Takt/Steuerschaltkreis T/C zugeführt, um die Art der arithmetischen Operation auf den Modus der Ausführung von Multiplikation und Addition einzustellen.
Die obige Operation wird im Detail durch das in Fig. 11 gezeigte Hardwarebild ausgedrückt.
Diese arithmetische Operation bedeutet, dass Werte, die man durch Addieren von in Adressen gespeicherten Werten Wh3, Wh2, Wh1 und Wh0 zu Werten erhält, die man durch Multiplizieren von in den Adressen S3, S2, S1 und S0 des arithmetischen Wertespeichers Smem gespeicherten Werten mit Werten erhält; die in den Adressen Wl3, Wl2, Wl1 und Wl0 des arithmetischen Wertespeichers Wlmem gespeichert sind, in Adressen Wh3, Wh2, Wh1, Wh0, Wl3, Wl2, Wl1 und Wl0 der arithmetischen Wertespeicher Whmem und Wlmem gespeichert werden.

Einheit der Multiplikation und Addition 1

Der Wert (Multiplikand), der in der Adresse Wl0 des arithmetischen Speichers Wlmem gespeichert ist, wird zuerst in das Register Yi-reg aufgenommen, und der Wert (Multiplizierer), der in der Adresse S'0 des arithmetischen Wertespeichers Smem gespeichert ist, wird in das Register Xi-reg aufgenommen und der Wert (Addend), der in der Adresse Wh0 des arithmetischen Wertspeichers Whmem gespeichert ist, wird dem Register Ai-reg zugeführt. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zum Addenden, um das addierte Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. In diese Multiplikations- und Additionseinheit 1 wird ein Signal mit hohem Pegel einem Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so dass die Inhalte des Registers RH nicht addiert werden.
Da die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 1 die geringstwertige Ziffer des abschließenden Operationsergebnisses dieser Multiplikation und Addition ist, wird die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 1 in der geringstwertigen Adresse Wl0 des arithmetischen Wertespeichers Wlmem als Operationsendergebnis dieser Multiplikation gespeichert (in Fig. 11 wird das Operationsendergebnis in der unterstrichenen Adresse gespeichert). Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 1 wird im Register RH für die nächste Einheit der Multiplikation und Addition gespeichert.

Einheit der Multiplikation und Addition 2

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse S1 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-Reg nimmt den Wert (Addend) auf, der in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zum Addenden, um das addierte Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. Bei dieser Multiplikations- und Additionseinheit 2 wird eine Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 1) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 2 wird in der geringwertigsten Adresse Wh0 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 2 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 3

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse S2 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend) auf, der in Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zum Addenden, um das addierte Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. Bei dieser Multiplikations- und Additionseinheit 3 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 2) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 3 wird in der geringstwertigen Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 3 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 4

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse 53 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend) auf, der in Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert ist. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zum Addenden, um das Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. Bei dieser Multiplikations- und Additionseinheit 4 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 3) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 4 wird in der geringstwertigen Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 4 wird in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 5

Der Wert (Multiplikand), der in der Adresse Wl1 des arithmetischen Wertespeichers Whnem gespeichert ist, wird dem Register Yi-reg zugeführt, der Wert (Multiplizierer), der in der Adresse 50 des arithmetischen Wertespeichers Smem gespeichert ist, wird dem Register Xi-reg zugeführt, und der Wert (Addend), der in der Adresse Wh0 des arithmetischen Wertespeichers Whmem gespeichert ist, wird dem Register Ai-reg zugeführt. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das Multiplikationsergebnis zum Addenden, um das addierte Ergebnis dem Hochgeschwindigkeitsaddierer Add zuzuführen. Bei dieser Multiplikations- und Additionseinheit 5 wird ein Signal mit hohem Pegel dem Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das die Inhalte (obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 4) des Registers RH nicht addiert werden. Die geringstwertige Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 5 wird in der Adresse Wl1 des arithmetischen Wertespeichers Wlmem gespeichert. Die höchstwertige Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 5 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 6

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse S1 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zu dem Addenden, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 6 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 5) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 6 wird in der Adresse Wh0 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 6 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 7

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse 52 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das multiplizierte Ergebnis zu dem Addenden, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 7 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 6) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/ Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 7 wird in der Adresse Wh1 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 7 wird im Register RH gespeichert, um die Ziffer in der nächsten Einheit der Multiplikation und Addition anzuordnen.

Einheit der Multiplikation und Addition 8

Das Register Yi-reg hält den schon gespeicherten Wert (Multiplikand) und das Register Xi- reg nimmt den Wert (Multiplizierer) auf, der in der Adresse 53 des arithmetischen Wertespeichers Smem gespeichert ist, und das Register Ai-reg nimmt den Wert (Addend), der in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert ist, auf. Anschließend multipliziert der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add den Multiplizierer mit dem Multiplikanden und addiert das Multiplikationsergebnis zu dem Addenden, um das addierte Ergebnis an den Hochgeschwindigkeitsaddierer Add weiterzugeben. Bei dieser Multiplikations- und Additionseinheit 8 wird ein Signal mit geringem Pegel durch den Durchgangsanschluss des Hochgeschwindigkeitsaddierers Add zugeführt, so das Inhalte (die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 7) des Registers RH zur Ausgabe des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add addiert werden. Die untere Ziffer des Operationsergebnisses in der Multiplikations- und Additionseinheit 8 wird in der Adresse Wh2 des arithmetischen Wertespeichers Whmem gespeichert. Die obere Ziffer des Operationsergebnisses der Multiplikations- und Additionseinheit 8 wird in der Adresse Wh3 des arithmetischen Wertespeichers Whmem gespeichert.
Die Einheiten der Multiplikation und Addition 9 bis 16 werden, wie in Fig. 11 gezeigt, entsprechend der Einheit der Multiplikation und Addition durchgeführt. Somit wird das abschließende Operationsergebnis in Form von Whmem-Wlmem ("-" ist kein Zeichen, welches die Subtraktion darstellt) gespeichert.
Fig. 12 zeigt die Einheit der Multiplikation und Addition in dem Fall, in welchem 8591 · 4673 + 2069 = 40147812 durch die obige Hardware ausgeführt wird. Die Operation von Fig. 12 ist dieselbe wie in Fig. 11 und folglich wird ihre Beschreibung fortgelassen.
Da wie oben beschrieben nach der vierten Ausführungsform der Multiplikations- und Additionsmodus mit einer langen Bitlänge, die die Grundlage für verschiedene arithmetische Operationen bildet realisiert werden kann, kann die Generalität des Coprozessors stark verbessert werden.

Berechnung von N'

Zusätzlich wird für die Multiplikation und Addition die Berechnung von N' nachfolgend beschrieben. Wie oben beschrieben ist jeder der Werte wie folgt:
1. R · R' - N · N' = 1(R · RmodN = 1)
2. R wird als ein Exponent von 2, der ein wenig größer als modN ist, definiert
3. N ist ungrade
4. 0 < N' < R
Dann gilt
R · R' = XXX XXX000 000
N · N' = YYY YYY111 111 (35)
(die Zahl "0", "1" ist klein n)
XXX XXX = YYY YYY + 1 = R' (36)
Um N' auf der Grundlage von N zu ermitteln, ist es nötig, die obige Gleichung (35) so anzugeben, dass alle niederen Bits von N · N' gleich "1" sind.
Fig. 21 ist ein Flussdiagramm, welches die Berechnung von N' zeigt. In Fig. 21 bezeichnet das Bezugszeichen n die Bitlänge von N, i einen Bitpositionszeiger, A das Arbeitsregister, B das N'-Ergebnisregister, ein 2iN Speicherregister, Ai die durch i bezeichnete Bitposition von A und Bi die durch i bezeichnete Bitposition von B, wobei die Bitlänge der Arbeitsregisters A und des 2iN a 2n beträgt, und die Bitlänge von B n beträgt.
Zuerst werden Daten, die die Bitlänge von N darstellen, auf n gesetzt, und der Wert von N wird in Arbeitsregister A eingestellt, während der Bitpositionszeiger i und das N- Ergebnisregister B geleert sind. Als nächstes wird das 2iN Speicherregister auf 2iN gesetzt (Anfangswert ist 2&sup0;N). Weiter wird der Wert der Bitposition Ai dahingehend geprüft, ob er gleich 1 ist oder nicht. Falls ja, dann entwickelt der Bitpositionszeiger i seine Inkrementierung. Wenn nein, dann wird die Bitposition Bi auf 1 gesetzt, und ein neuer Wert des vorherigen Wertes des Arbeitsregister A + den Wert (der Anfangswert ist 2&sup0;N) des 2iN- Speicherregisters wird im Arbeitsregister A eingestellt; und außerdem folgt dieselbe Inkrementierung des Bitpositionszeigers i. Weiter wird der Bitpositionszeiger i dahingehend überprüft, ob er gleich der Bitlänge von N + 1 ist oder nicht. Wenn ja, (wenn er davon verschieden ist), dann fährt die ähnliche Prozedur fort, die sich wiederholen wird, bis sie die Bitlänge von N + 1 erreicht. Wenn nein (wenn es dem gleich ist), ist die Berechnung von N' vorbei. Auf diese Weise stellt der abschließende Wert des N'-Ergebnisregisters B N' zur Verfügung.
Nachfolgend wird ein Beispiel der Berechnung von N' und R' beschrieben. Fig. 22 zeigt ein Beispiel der Berechnung von N' und R', von denen jedes vergleichsweise eine Zahl mit kurzer Ziffernfolge beinhaltet.
Zuerst wird für ein gegebenes N (= 11010111), die Bitverschiebung von N nach links wiederholt, bis das LSB (geringstwertiges Bit) des verschobenen N ein erstes "0"- Bit (2³) antrifft, welches in 2&sup0; · N liegt, d. h., die linksseitige Bitverschiebung wird dreimal durchgeführt. Dies liefert 2³ · N. Als nächstes werden 2&sup0; · N und 2³ · N addiert, was eine erste Summe 11110001111 bereitstellt, wie es in der Figur gezeigt ist. Ähnlich zur Ermittlung von 2³ · N wird für diese Summe die linksseitige Bitverschiebung von N wiederholt, bis das LSB des verschobenen N ein erstes "0"-Bit (24) antrifft, das in der Summe liegt, die linksseitige Bitverschiebung wird nämlich viermal ausgeführt, und ergibt dadurch 2&sup4; · N. Nachfolgend werden die Summe und 2&sup4; · N addiert, wodurch eine zweite Summe (= 1010011111111) erzeugt wird. Schließlich liefert das Addieren von 2&sup4; · N, 2&sup4; · N, und 2&sup4; · N, wobei es sich um eine Gesamtsumme von 2i handelt, N' (= 25). Die Zifferzahl von R (= 100000000) ist 9. Da die Ziffern (= 10100), die an Zifferpositionen gleich oder größer als die neunte Zifferposition liegen, R' - 1 liefern ergibt sich daraus R' (21).

Fünfte Ausführungsform

Struktur

Da der in den obigen Ausführungsformen beschriebene Coprozessor erforderlich ist, um auf den Speicher für jede Einheit der Multiplikation und Addition zuzugreifen, die durch die Eingabebitlänge des Hochgeschwindigkeitsmultiplizierer/Addierers Mul/Add und des Hochgeschwindigkeitsaddierers Add bestimmt wird, gibt es Raum für eine Verbesserung bei der Reduzierung der Operationszeit. Der Grund ist, dass die Operationsgeschwindigkeit der gesamten Schaltung einschließlich der Speicher durch die Speicherzugriffszeit beschränkt ist.
Bei dieser Ausführung wird die Anzahl der Zugriffe auf die Speicher hinsichtlich der Zahl der arithmetischen Operationen in der Einheit der Multiplikation und Addition reduziert, um die letzliche Operationszeit zu verkürzen.
Fig. 13 ist ein Blockschaltbild, welches schematisch den modularen arithmetischen Coprozessor nach der fünften erfindungsgemäßen Ausführungsform zeigt.
In der fünften Ausführungsform wird das Multiplikandenspeicherregister Yi-reg auf eine Mehrzahl von Multiplikanden Speicherregistern erhöht, und es ist im Vergleich zu den obigen Ausführungsformen eine Schaltung zum Auswählen der Ausgaben der Mehrzahl von Multiplikanden Speicherregistern vorgesehen. Weiter sind die Register zum Speichern des oberen Ziffernausgabewertes oder des unteren Ziffernausgabewertes des Hochgeschwindigkeitsaddierers Add entsprechend der Anzahl der Multiplikandenspeicherregister vorgesehen, und es sind Auswahlschaltungen zum ordnungsgemäßen Auswählen von Ausgabewerten der Register vorgesehen.
Insbesondere sind die Register Yi-Reg [0], Yi-Reg [1], Yi-Reg [2] und Yi-Reg [3] Multiplikandenspeicherregister mit einer Bitlänge, die der Eingabebitlänge des Hochgeschwindigkeitsmultiplizierers/Addierers Mul/Add entsprechen, und entsprechende Ausgänge dieser Multiplikanden Speicherregister sind mit den Multiplikanden Auswahlschaltkreis Yi-sel verbunden. Der Multiplikandenauswahlschaltkreis Yi-sel ist eine Auswahlschaltung, die einen der Werte in den Registern Yi-reg [0], Yi-Reg [1], Yi-Reg [2] und Yi-Reg [3] auswählt, um den ausgewählten Wert im nachfolgenden Zustand dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add zuzuführen.
Ein Register RA ist ein Register zum vorübergehenden Speichern der oberen Ziffer R-hoch der Ausgabe des Hochgeschwindigkeitsaddierers Add, und die Ausgabe des Registers RA ist mit den Auswahlschaltungen SelA SelB und EnSel verbunden. Die untere Ziffer Rniedrig der Ausgabe des Hochgeschwindigkeitsaddierers Add ist mit der Auswahlschaltung SelB und einem Aktivierungspuffer En verbunden.
Die Ausgabe des Registers Ai-reg ist mit der Auswahlschaltung SelA verbunden. Die Auswahlschaltung SelA wählt irgendwelche Inhalte der Register Ai-reg und des Registers RA aus, und ist mit dem Hochgeschwindigkeitsaddierer Add verbunden, um das ausgewählte Signal dem Hochgeschwindigkeitsaddierer zuzufügen.
Das Register RB ist ein Register zur vorübergehenden Speicherung der Ausgabe der Auswahlschaltung SelB, und die Ausgabe des Registers RB ist mit dem Register RC und EnSel verbunden.
Das Register RC ist ein Register zur vorübergehenden Speicherung der Ausgabe des Registers RB, und die Ausgabe des Registers RC ist mit dem Register RD und der Auswahlschaltung EnSel verbunden.
Das Register RD ist ein Register zur vorübergehenden Speicherung der Ausgabe des Registers RC, und die Ausgabe des Registers RD ist mit der Auswahlschaltung EnSel und dem Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add verbunden.
Der Auswahlschaltkreis EnSel ist eine Auswahlschaltung zum Auswählen eines der Inhalte der Register RA, RB, RC und RD und zum Zuführen des ausgewählten Ergebnisses an die arithmetischen Wertespeicher.
Andere Schaltungen haben dieselbe Funktion wie die der obigen Ausführungsformen und demgemäss wird ihre Beschreibung ausgelassen.

Operation

Das Berechnungsverfahren der folgenden Gleichung:
(A3A2A1A0) · B0 + C0
welche die Grundlage der Arithmetik ist, wird jetzt mit Bezug auf Fig. 14 unter Verwendung des folgenden Hardwarebildes beschrieben.
(Wl3, Wl2, Wl1, Wl0) · SO = (RA, RB, RC, RD, Wl0)
Die unterstrichene Adresse bedeutet, dass das letzliche arithmetische Ergebnis darin gespeichert wird.

Initialisierung

Zuerst wird wie in Fig. 14 gezeigt, die Initialisierung durchgeführt.

Schritt 1

Eine arithmetische Operation wird an einem Wert des Registers Xi-reg, einem Wert des Registers Yi-reg [0], das durch die Auswahlschaltung Yi-Sel ausgewählt wurde, einen Wert des Registers RD und einen Wert des Registers Ai-reg ausgeführt, welches durch die Auswahlschaltung SeIA ausgewählt wurde. Unmittelbar vor dem Ende dieser arithmetischen Operation wird die obere Ziffer R-hoch des arithmetischen Ergebnisses im Register RA gespeichert, und seine untere Ziffer R-niedrig wird in dem arithmetischen Wertespeicher Wlmem gespeichert. Zur selben Zeit werden die Werte der Register RC und RB in den Registern RD bzw RC gespeichert und der Wert des Registers RA wird im Register RB gespeichert, welches durch die Auswahlschaltung SelB ausgewählt wurde.

Schritt 2

Die arithmetische Operation wird an dem Wert des Registers Xi-reg, dem Wert des Registers Yi-reg [1], das durch die Auswahlschaltung Yi-Sel ausgewählt wurde, dem Wert des Registers RD und dem Wert des Registers RA ausgeführt, welches durch die Auswahlschaltung SelA ausgewählt wurde. Unmittelbar vor dem Ende dieser arithmetischen Operation wird die obere Ziffer R-hoch des arithmetischen Ergebnisses im Register RA gespeichert, und seine untere Ziffer R-niedrig wird im Register RB gespeichert, welches durch die Auswahlschaltung SelB ausgewählt wurde. Zur selben Zeit werden die Werte der Register RC und RB in den Registern RD bzw. RC gespeichert.

Schritt 3

Die arithmetische Operation wird an dem Wert des Registers Xi-reg, dem Wert des Registers Yi-reg [2], das durch die Auswahlschaltung Yi-Sel ausgewählt wurde, dem Wert des Registers RD und dem Wert des Registers RA ausgeführt, welches durch die Auswahlschaltung SelA ausgewählt wurde. Unmittelbar vor dem Ende dieser arithmetischen Operation wird die obere Ziffer R-hoch des arithmetischen Ergebnisses im Register RA gespeichert, und seine untere Ziffer R-niedrig wird im Register RB gespeichert, welches durch die Auswahlschaltung SelB ausgewählt wurde. Zur selben Zeit werden die Werte der Register RC und RB in den Registern RD bzw. RC gespeichert.

Schritt 4

Die arithmetische Operation wird an dem Wert des Registers Xi-reg, dem Wert des Registers Yi-reg [3], das durch die Auswahlschaltung Yi-Sel ausgewählt wurde, dem Wert des Registers RD und dem Wert des Registers RA ausgeführt, welches durch die Auswahlschaltung SelA ausgewählt wurde. Unmittelbar vor dem Ende dieser arithmetischen Operation wird die obere Ziffer R-hoch des arithmetischen Ergebnisses im Register RA gespeichert, und seine untere Ziffer R-niedrig wird im Register RB gespeichert, welches durch die Auswahlschaltung SelB ausgewählt wurde. Zur selben Zeit werden die Werte der Register RC und RB in den Registern RD bzw. RC gespeichert.
Im obigen Prozess von Schritt 1 bis Schritt 4 erfolgt der Zugriff auf den arithmetischen Wertespeicher in Schritt 1 gerade einmal. Demnach kann während der verbleibenden Periode von Schritt 2 zu Schritt 4 eine Änderung der Adressen der arithmetischen Wertespeicher und ein Vorabladen erfolgen, um Zeit für den Speicherzugriff zu erhalten. Die in der Periode von Schritt 2 bis Schritt 4 durchgeführten Operationen sind im wesentlichen identisch und folglich ist die arithmetische Operation nicht kompliziert.
Als weiteres Beispiel für die arithmetische Operation ist das Berechnungsverfahren für die folgenden Gleichung:
(A3, A2, A1, A0) · (B3, B2, B1, B0) + (C3, C2, C1, C0)
in den Fig. 15 und 16 unter Verwendung des folgenden Hardwarebildes gezeigt.
(Wl3, Wl2, Wl1, Wl0) · S3, S2, S1, S0) + (Wh3, Wh2, Wh1, Wh0) = (RA, RB, RC, RD, Wl3, Wl2, Wl1, Wl0)
Weiter zeigt Fig. 16 als Beispiel für eine tatsächliche Berechung den arithmetischen Prozess von Zeitpunkt 1 bis Zeitpunkt 4 mit 8591 · 4673 + 2069 = 40147812.
Die unterstrichenen Werte sind die Endergebnisse der arithmetischen Operation.
Man kann aus Fig. 16 entnehmen, dass die oberen Ziffern des Endergebnisses Werte sind, die in den Registern RA, RB, RC und RD gespeichert sind, die man in Schritt 4 zum Zeitpunkt 4 erhält, und dass die unteren Ziffern Werte sind, die in dem arithmetischen Wertespeicher Wlmem gespeichert sind, die man in Schritt 1 erhalten hat.
Wie oben beschrieben, ist es nach der fünften Ausführungsform nicht nötig, die Größe der arithmetischen Verarbeitungseinheit, wie z. B. den Multiplizierer/Addierer oder dergleichen, zu ändern, und es kann der modulare arithmetische Coprozessor realisiert werden, der durch eine klein bemessene Schaltung als Ganzes gebildet wird und eine kurze Operationszeit aufweist.

Sechste Ausführungsform

Struktur

Fig. 17 ist ein Blockschaltbild, welches die sechste erfindungsgemäße Ausführungsform zeigt. Die Ausführungsform enthält eine Schnittstellenschaltung für den arithmetischen Wertespeicher und eine arithmetische Steuerschaltung, die zwischen dem oben beschriebenen Coprozessor und der externen Einheit vorgesehen sind.

Schnittstellenschaltkreis für arithmetische Wertespeicher MemIF

Der Schaltkreis MemIF dient zum Übertragen und empfangen von Daten zwischen der MCU und den arithmetischen Wertespeichern im Coprozessor.
Die arithmetischen Wertespeicher speichern arithmetische Daten von außerhalb des Coprozessors von der arithmetischen Operation und senden die arithmetischen Ergebnisse vom Coprozessor nach außen, wenn die arithmetische Operation abgeschlossen ist. Gleichzeitig greifen die arithmetischen Wertespeicher wiederholt und dynamisch auf die arithmetische Einheit ohne Beziehung vom Coprozessor nach außen zu. D. h. die arithmetischen Wertespeicher weisen zwei Arten von Kommunikationsprotokollen auf. Der Schnittstellenschaltkreis für arithmetische Wertespeicher ist so gebildet, dass er das Protokoll verwirklicht.
Ein Adresssignal adrs und ein Speichersteuersignal Memcon, die durch die MCU erzeugt werden, werden in die Schnittstelle für arithmetische Wertespeicher MemIF eingegeben, und ein Adresssignal Comemad und ein Speichersteuersignal Comcon werden für jeden arithmetischen Wertespeicher im Coprozessor in der Schnittstelle für arithmetische Wertespeicher MemIF bereitgestellt, um dem Coprozessor zugeführt zu werden. MDbus ist ein Datenbus der MCU, und CoDbus ist ein Datenbus für eine externe Schnittstelle des Coprozessors.
Wenn die arithmetischen Wertespeicher innerhalb der MCU in einem einzigen Speicherbereich angeordnet werden, werden eine Sorte des adrs Signals und des Memcon Signals, die in die Schnittstelle für arithmetische Wertespeicher MemIF eingegeben wurden, und der MDbus bereitgestellt, während wenn die arithmetischen Wertespeicher in einer Mehrzahl von Speicherbereichen angeordnet werden, mehrere Arten von Eingaben erforderlich sind. Allgemein werden MDbus und CoDbus oftmals direkt verbunden, während z. B. wenn die Datenlänge der arithmetischen Wertespeicher, die innerhalb des Coprozessors verarbeitet wird, und die Datenlänge der MCU unterschiedlich sind, die Datenumwandlung durch die Schnittstelle für arithmetische Wertespeicher MemIF erfolgt.
Da die arithmetischen Wertespeicher zur Ausführung der Arithmetik dynamisch betrieben werden, während der Coprozessor die Arithmetik ausführt, wird sie weiter so gesteuert, dass ein Zugriff von der MCU verhindert wird. Auf diese Weise wird das erste Kommunikationsprotokoll zwischen den arithmetischen Wertespeichern im Coprozessor und der externen Einheit realisiert.
Bei Ausführung der Arithmetik wird ein Speichersteuersignal, welches durch den Zeitgeber/Steuerschaltkreis T/C im Coprozessor erzeugt wird, in die Schnittstelle für arithmetische Wertespeicher MemIF eingegeben. Wenn die Schnittstelle für arithmetische Wertespeicher MemIF das Signal empfängt, führt die Schnittstelle MemIF dem Coprozessor das Comemad-Signal und das Comcon-Signal zu, die verarbeitet wurden, um zu bewirken, dass die arithmetischen Wertespeicher Daten zwischen der arithmetischen Einheit und den arithmetischen Wertespeichern senden und empfangen. Auf diese Weise wird das zweite Kommunikationsprotokoll zwischen der arithmetischen Einheit und den arithmetischen Wertespeichern während der Ausführung der Arithmetik innerhalb des Coprozessors realisiert.

Arithmetischer Steuerschaltkreis CopCon

Der arithmetische Steuerschaltkreis CopCon dient dazu, ein Coprozessorsteuersignal Excon zu empfangen, das durch die MCU erzeugt wurde, und ein arithmetisches Steuersignal Sevex (arithmetisches Modussignal, Bitlängenauswahlsignal, und dergleichen in den obigen Ausführungsformen) dem Coprozessor zur Verfügung zu stellen. Die arithmetische Operation im Coprozessor wird durch Zuführen des arithmetischen Modussignals und des Takts COPCLK für den Coprozessor gestartet.
Um den Abschluss der arithmetischen Operation auf Seiten der MCU zu bestätigen, wird weiter ein Taktsignal Coend zum Abschluss der Arithmetik, welches durch den Zeitgeber/Steuerschaltkreis T/C im Coprozessor erzeugt wird, durch CopCon empfangen, und ein Überwachungssignal für den Abschluss der Arithmetik Endmoni, das durch einen Sperrschaltkreis oder dergleichen verarbeitet wurde, wird der MCU zugeführt.
Allgemein kann der arithmetische Steuerschaltkreis CopCon so gebildet werden, dass er als Peripherschaltung der MCU in einem lokalen Speicherbereich verteilt wird und direkt durch eine Anweisung der MCU zugreift, und er kann durch einen relativ einfachen Schaltkreis realisiert werden.
In Fig. 17 repräsentiert ein MCUCLK- Signal einen Takt für die MCU und ein COPCLK- Signal repräsentiert einen Takt für den Coprozessor.
Da wie oben beschrieben nach der sechsten Ausführungsform die Schnittstelle zwischen der externen Einheit (z. B. MCU) und dem Coprozessor durch eine relativ klein bemessenes Schaltung realisiert werden kann, kann der modulare arithmetische Coprozessor mit der externen Schnittstelle oder die MCU, die den modularen arithmetischen Coprozessor enthält, gebildet und durch ein LSI realisiert werden.

Siebte Ausführungsform

Die Maßnahme zur Bestätigung des Abschlusses der Arithmetik von außerhalb des Coprozessors besteht nur in der Untersuchung des Überwachungssignals für den Abschluss der Arithmetik Endmoni. In diesem Verfahren wird jedoch, da eine Menge an modularer arithmetischer Operationen mit langer Bitlänge erhöht wird, die durch den Coprozessor verarbeitet werden, die Zeit zum ständigen Überwachen von Endmoni seitens der MCU im Fall, in dem die externe Einheit z. B. die MCU ist, relativ lang, und demgemäss wird die Operationsleistung der MCU reduziert.
Um dieses Problem zu lösen, enthält diese Ausführungsform einen exklusiven Steuerschaltkreis für die Abschlusszeit der Arithmetik.
Fig. 18 ist ein Blockschaltbild, das schematisch die siebte erfindungsgemäße Ausführungsform zeigt.
In Fig. 18 repräsentiert IntCon einen Unterbrechungssteuerschaltkreis für den Abschluss der Arithmetik, in welchem die Vorbereitung der Unterbrechung durch ein Unterbrechungseinstellsignal Intset erfolgt, das zuvor durch die MCU erzeugt wurde. Wenn das Taktsignal zum Abschluss der Arithmetik Coend durch den Coprozessor eingegeben wird, werden ein Unterbrechungsverarbeitungsanfragesignal, ein Bestätigungssignal und ein Vektorsteuerungssignal, die für die Unterbrechung nötig sind, als Intsig zwischen der MCU und dem IntCon für jede Art des durch das CopCon eingestellten arithmetischen Modus gesendet und empfangen, und schließlich wird die Unterbrechungsvorbereitung abgebrochen, um den Unterbrechungsprozess zu beenden.
Ein einzelner Unterbrechungsfaktor für den Abschluss der Arithmetik kann fest eingestellt werden, während, da der Coprozessor eine Mehrzahl von arithmetischen Modi aufweist, das Verfahren zur Entwicklung der Modulo-Exponentierungsarithmetik durch die externe Einheit leicht gemacht wird, und zwar durch ausführen einer Unterbrechung für jeden arithmetischen Modus, und folglich ist es wünschenswert, mehrere Unterbrechungsfaktoren einzustellen.
Intcon kann so gebildet werden, dass es in einem lokalen Speicherbereich als Peripherschaltung der MCU verteilt wird, ähnlich zum arithmetischen Steuerschaltkreis CopCon, und direkt durch eine Anweisung der MCU zugreift, und kann durch eine relativ einfache Schaltung realisiert werden.
Wie oben beschrieben, kann nach der siebten Ausführungsform der modulare arithmetische Coprozessor mit der externen Schnittstelle oder die MCU, die den modularen arithmetischen Coprozessor mit der Unterbrechungsfunktion zum Abschluss der Arithmetik enthält, durch einen relativ klein bemessenen Schaltkreis gebildet und durch ein LSI realisiert werden.

Achte Ausführungsform

Da die modulare arithmetische Operation im Coprozessor vom Beginn bis zum Ende der arithmetischen Operation dynamisch durchgeführt wird, ist es angenehm, dass die Operation der externen Einheit während der Ausführung der Arithmetik in einen vorübergehenden Haltezustand (nachfolgend als Schlaf bezeichnet) versetzt werden kann, um einen Verbrauchsstrom während der Ausführung der Arithmetik im ganzen System zu unterdrücken, welches mit der externen Einheit verbunden ist.
Die Ausführungsform enthält eine exklusive Schlafsteuerschaltung für die externe Einheit und einen Steuerschaltkreis, der zur Realisierung der Schlafoperation vorgesehen ist.
Fig. 19 zeigt schematisch die achte Ausführungsform und enthält den Schlafsteuerschaltkreis für die externe Einheit und den Taktsteuerschaltkreis die zur siebten Ausführungsform hinzugefügt wurden.
In Fig. 19 repräsentiert Slpcon einen MCU Schlafsteuerschaltkreis, der ein Schlafeinstellsignal Slpset von der MCU empfängt und ein Schlafsignal Slp erzeugt, um das Schlafsignal der Taktsteuerschaltung CLKCon zuzuführen.
Die Taktsteuerschaltung CLKCon stellt üblicherweise den Takt MCUCLK der MCU im Ansprechen auf das System Takt Signal CLK zur Verfügung, das von außen eingegeben wurde, während, sobald das Slp Signal empfangen wird, die Taktsteuerschaltung CLKCon dazu dient, die Zuführung des Takts MCUCLK an die MCU zu stoppen.
Nach Abschluss der arithmetischen Operation wird das Taktsignal zum Abschluss der arithmetischen Operationen Coend dem SlpCon zugeführt, um die Zuführung des SLP Signals zum CLKCon zu stoppen, so dass die Zuführung von MCUCLK zur MCU vom CLKCon wieder aufgenommen wird.
Allgemein wird die Schlaffunktion oftmals durch Eingeben eines Signals in einen bestimmten Anschluss der externen Einheit aufgehoben. Folglich kann in diesem Fall die Schlafsteuerschaltung SlpCon so gebildet werden, dass sie diese Funktion aufweist.
Die SlpCon kann so gebildet sein, dass sie in einem lokalen Speicherbereich als periphere Schaltung der MCU ähnlich wie die arithmetische Steuerschaltung CopCon verteilt ist und das sie direkt durch eine Anweisung der MCU zugreift, und sie kann durch eine relativ einfache Schaltung realisiert werden.
Nach der oben beschriebenen achten Ausführungsform kann der modulare arithmetische Coprozessor mit der äußeren Schnittstelle oder die MCU, die den modularen arithmetischen Coprozessor mit der Schlaffunktion der externen Einheit enthält, durch einen relativ klein bemessenen Schaltkreis gebildet und durch ein LSI realisiert werden.

Neunte Ausführungsform

Der Coprozessor kann verwendet werden, wenn die Hochgeschwindigkeitscharakteristik der Verarbeitungszeit des Kryptographiealgorithmus zur Durchführung einer komplizierten modularen Arithmetik in großem Maßstab in Frage gestellt wird. Demnach ist es erforderlich, das die Operationszeit kurz ist, sogar für jede Frequenz eines dem System zugeführten Eingabetaktes.
Ein frequenzvervielfachter Takt/Steuerschaltkreis ist enthalten, um die Operationsgeschwindigkeit zu verbessern. Fig. 20 ist ein Blockschaltbild, das schematisch die Neunte Ausführungsform zeigt, bei der die Taktsteuerschaltung der achten Ausführungsform modifiziert ist, so dass sie die frequenzvervielfachte Taktsteuerschaltung bildet.
Die frequenzvervielfachte Taktsteuerschaltung kann separat der sechsten oder siebten Ausführungsform hinzugefügt werden.
In Fig. 20 repräsentiert CLKCon2 die Taktsteuerschaltung, die die frequenzvervielfachte Taktsteuerschaltung enthält, der ein Signal Ckwset von der MCU als Frequenzvervielfachungseinstellsignal zugeführt wird, um die Frequenzvervielfachungsfünktion zu betreiben.
Die Frequenzvervielfachungsfunktion wird im Ansprechen auf den von außen zugeführten Takt CLK betrieben, und ihr Schaltkreis ist so gebildet, dass der vorbereitete frequenzvervielfachte Takt als Takt MCUCLK für die MCU, der Takt COPCLK für den Coprozessor oder für beide erzeugt wird. Somit kann der Benutzer in Anbetracht eines Kompromisses für den Stromverbrauch verschiedene Auswahlen im System treffen.
Die Frequenzvervielfachungsfunktion kann durch Eingeben des Signals Ckwset als Löschungssignal in derselben Weise gelöscht werden, wie ihre Einstellung.
Die frequenzvervielfachte Taktsteuerschaltung kann so gebildet werden, dass sie in einem lokalen Speicherbereich als Peripherschaltung der MCU ähnlich zur arithmetischen Steuerung CopCon verteilt ist und direkt durch eine Anweisung der MCU zugreift und sie kann durch einen relativ einfachen Schaltkreis realisiert werden.
Nach der oben beschriebenen neunten Ausführungsform kann der modulare arithmetische Coprozessor mit der äußeren Schnittstelle oder die MCU, die den modularen arithmetischen Coprozessor mit der Frequenzvervielfachungsfunktion des Systems enthält, durch einen relativ klein bemessenen Schaltkreis gebildet und durch ein LSI realisiert werden, um die Operationsverarbeitungsgeschwindigkeit des gesamten Systems zu verbessern.
Der in den ersten bis fünften Ausführungsformen gezeigte Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add kann durch den separat vorgesehen Multiplizierer und Addierer gebildet werden.
Der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add und der Hochgeschwindigkeitsaddierer Add die in den ersten bis fünften Ausführungsformen gezeigt sind, können integral ausgebildet sein.
Der Hochgeschwindigkeitsmultiplizierer/Addierer Mul/Add und der Hochgeschwindigkeitsaddierer Add die in den ersten bis fünften Ausfiuirungsformen gezeigt sind, können durch kommerziell erhältliche ICs ausgebildet sein.
Der in den sechsten bis neunten Ausführungsformen gezeigt Coprozessor ist auf der Grundlage des in den ersten bis fünften Ausführungsformen gezeigten Coprozessors gebildet, kann aber durch einen anderen Coprozessor gebildet werden, der dieselbe Funktion aufweist, wie der in der ersten bis fünften Ausführungsform gezeigte Coprozessor.
Der in den ersten bis fünften Ausführungsformen gezeigte Multiplikationsalgorithmus mit langer Bitlänge wurde allgemein beschrieben, während ein anderer Algorithmus (z. B. BOOTH oder dergleichen) der durch die in der Beschreibung verwendete Hardwarestruktur verwendet werden kann, kann durch den Zeitgeber/Steuerschaltkreis gebildet werden.
Bei der Beschreibung der ersten bis fünften Ausführungsform wird der "0"- Detektionsschaltkreis NullC verwendet, um die arithmetischen Wertespeicher als primäres Ziel zu reduzieren, während der NullC verwendet werden kann, um die Abfolge so zu steuern, dass z. B. bei den Inhalten des Multiplizierers oder des Multiplikanden der Einheit der Multiplikation die arithmetische Operation ausgelassen wird, und der Wert während der arithmetischen Operation auf Ziffer 0 gesetzt wird, um zur nächsten Operation vorzurücken, um dadurch die Operationszeit zu reduzieren.
Bei der fünften Ausführungsform wird die Anzahl der Multiplikandenspeicherregister erhöht, während die Bitlänge des Multiplikandenspeicherregisters verlängert wird, um seine Größe zu erhöhen.
Wie oben beschrieben kann nach einem erfindungsgemäßen Vertreter das zuvor vorbereitete Modussignal zugeführt werden, wenn die Lösung der Modulo-Exponentierungsarithmetik ermittelt wird, um dadurch verschiedene arithmetische Operationen auszuführen.

Claims

1. Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik, die angepasst ist, um eine allgemeine Gleichung einer modularen Exponentierungsarithmetik F(M, E) = MEmodN auszuführen, um einen Rest einer ganzen Zahl M hoch einer ganzzahligen E-ten Potenz, dividiert durch eine ganze Zahl N, zu berechnen, und zwar durch Ausführen einer ersten Gleichung einer modularen Multiplikationsarithmetik f(A, B) = A BmodN, um einen Rest eines Produktes einer ganzen Zahl A und einer ganzen Zahl B, geteilt durch eine ganze Zahl N zu berechnen, indem

eine zweite Gleichung einer Ersatzarithmetik f (A, B) = A · B · R'modN entsprechend der ersten Gleichung f(A, B) = A · BmodN im iterativen Quadrat verwendet wird, wobei R' einen Wert bezeichnet, der der Gleichung R · R'modN = 1 bezüglich R genügt, welches ein Exponent ist, der um 2 größer als der Absolutwert von N ist und der teilerfremd (coprime) zum Absolutwert von N ist, und indem

ein Multiplikationsverfahren zum Berechnen der modularen Exponentierungsarithmetik verwendet wird, wobei die Vorrichtung folgendes umfasst:

erste Ausführungsmittel zum Ausführen einer ersten Ersatzarithmetik f&sub1;', = f'(f&sub2;', f&sub2;'), wobei anfangs f&sub1;' = f'(RmodN, RmodN) gilt;

zweite Ausführungsmittel zum Ausführen einer zweiten Ersatzarithmetik f&sub2;' = f'(f&sub1;', M · RmodN); und

dritte Ausführungsmittel zum Ausführen einer dritten Ersatzarithmetik f&sub3;' = f'(f&sub2;'; 1) nach der Wiederholung der ersten und zweiten Ersatzarithmetik f&sub1;' und f&sub2;' durch die ersten und zweiten Ausführungsmittel, um die modulare Exponentierungsarithmetik MEmodN zu berechnen.

2. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 1, weiter umfassend;

erste Vorberechnungsmittel zum Berechnen von RmodN vor dem Berechnen der ersten Ersatzarithmetik f&sub1;' = f'(RmodN, RmodN) der ersten Mittel;

erste Speichermittel zum Speichern des berechneten RmodN;

zweite Vorberechnungsmittel zum Berechnen von M · RmodN vor dem Berechnen der zweiten Ersatzarithmetik f&sub2;' = f'(f&sub1;', M · RmodN); und

zweite Speichermittel zum Speichern des berechneten M · RmodN.

3. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 1, bei der die ersten, zweiten und dritten Ausführungsmittel jeweils Mittel zum Ausführen einer entsprechenden ersten, zweiten und dritten Ersatzarithmetik enthalten, wobei die Funktion REDC verwendet wird, die durch die folgenden Schritte bezeichnet ist, wobei m und t Variablen bezeichnen:

a) m = (A · BmodR) · N'modR

b) t = (A · B + mxN)/R

c) wenn t < N gebe t zurück (t: Ergebnis)

d) sonst gebe t - N zurück (t - N: Ergebnis).

4. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 3, weiter umfassend:

N'-Berechnungsmittel zum Berechnen von N' durch Multiplikation und Addition auf der Grundlage von N, und

Mittel zum Speichern von N'.

5. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 3, weiter umfassend:

Mittel zum Detektieren, ob das Produkt der ganzen Zahl A und B gleich einem Vielfachen der ganzen Zahl R ist oder nicht;

Mittel zum Auslassen des Schritts (a) m = (A · BmodR) · N'modR und zum Setzen der Variable m auf "0" in der Funktion REDC, während der Schritt (b) t = (A · B + m · N)/R ausgelassen und die Variable t auf "A B/R" in der Funktion REDC gesetzt wird, sobald detektiert wird, dass das Produkt von A und B gleich einem Vielfachen von R ist; und

Mittel zum Setzen der Variable m, wobei die ersten Stellen niedriger liegen als das höchstwertige Bit der ganzen Zahl R von den zweiten Sfiellen, wobei die zweiten Stellen ein Produkt der dritten Stellen und N' sind, wobei die dritten Stellen niedriger liegen als das höchstwertige Bit der ganzen Zahl R von einem Produkt der ganzen Zahl A und der ganzen Zahl B, während die Variable t als die Summe der folgenden drei Stellen festgesetzt wird: (1) die vierten Stellen, die höher liegen als das höchstwertige Bit der ganzen Zahl von dem Produkt der ganzen Zahl A und der ganzen Zahl B, (2) die fünften Stellen, die höher liegen als das höchstwertige Bit der ganzen Zahl R von einem Produkt der Variable m und der ganzen Zahl N, und (3) 1, sobald detektiert wird, dass das Produkt der ganzen Zahl A und der ganzen Zahl B sich von irgendeinem Vielfachen der ganzen Zahl R unterscheidet.

6. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 1, weiter umfassend:

Mittel zum Eingeben einer Zifferlänge der zu berechnenden modularen Exponentierung; und

Mittel zum Setzen von Ausführungsbedingungen für die Ersatzarithmetik f'(A, B), die der Länge der eingegebenen Ziffer entspricht.

7. Die Vorrichtung zur Durchführung einer modularen Exponentierungsarithmetik nach Anspruch 1, weiter umfassend:

mehrere Register zur Verwendung für die Ausführung der ersten Arithmetik f&sub1;', der zweiten Arithmetik f&sub2;' und der dritten Arithmetik f&sub3;'.

8. Eine Verschlüsselungsvorrichtung, die einen Kryptographen C so präpariert, dass ein bloßer Text M mit Verschlüsselungsschlüsseln E und N verschlüsselt wird, und zwar durch Implementierung einer modularen Exponentierungsarithmetik C = MEmodN, wobei C, M, E und N positive ganze Zahlen sind, bei der eine Gleichung einer Ersatzarithmetik f'(A, B) = A · B · R'modN, einer Gleichung f(A, B) = A · BmodN im iterativen Quadrat entspricht, und

ein Multiplikationsverfahren zum Ausführen der modularen Exponentierungsarithmetik eingesetzt werden, wobei die Verschlüsselungsvorrichtung folgendes umfasst:

erste Ausführungsmittel zum Ausführen einer ersten Ersatzarithmetik f&sub1;' = f'(f&sub2;', f&sub2;'), wobei anfangs f&sub1;' = f'(RmodN, RmodN) gilt;

dritte Ausführungsmittel zum Ausführen einer dritten Ersatzarithmetik f&sub3;' = f'(f&sub2;'; 1) nach der Wiederholung der ersten und zweiten Ersatzarithmetik f&sub1;' und f&sub2;' durch die ersten und zweiten Ausführungsmittel, um Kryptographen C zu berechnen.

9. Die Verschlüsselungsvorrichtung nach Anspruch 8, bei der die ersten, zweiten und dritten Ausführungsmittel jeweils Mittel zum Ausführen einer entsprechenden ersten, zweiten und dritten Ersatzarithmetik enthalten, wobei die Funktion REDC verwendet wird, die durch die folgenden Schritte bezeichnet ist, wobei m und t Variablen bezeichnen:

a) m = (A · BmodR) · N'modR

b) t = (A · B + m · N)/R

c) wenn t < N gebe t zurück (t: Ergebnis)

d) sonst gebe t - N zurück (t - N: Ergebnis).