-
Die vorliegende Erfindung betrifft ein Gerät zum Ausführen einer Division
eines Dividenden A durch einen Divisor D, gebildet von "n" Wörtern, die für eine Basis
"b" stehen, um einen Quotienten Q und einen Rest R zu erhalten.
-
Die Erfindung betrifft auch eine mit solch einem Gerät versehene Chipkarte
oder Mikroschaltungskarte.
-
Ein solches Gerät findet großen Einsatz in Bereichen, wo Divisionen großer
Zahlen erforderlich sind. Allerdings gibt es einen bevorzugten Anwendungsbereich für die
Erfindung: Den Bereich der Mikroschaltungskarten unter Verwendung des RSA-
Kodierverfahrens. Dieses Verfahren, beschrieben in dem US-A 4405829 von Rivest,
Shamir und Adleman in 1978, ist ein System mit einem öffentlichen Schlüssel "e". Es
gründet auf dem Problem der Faktorisierung einer großen Zahl "N", die das Produkt von
zwei anfänglichen Zahlen "p" und "q" ist.
-
Die Basisoperation dieser Kodierung wird folgendermaßen definiert.
-
Der zu kodierenden Nachricht wird die Form einer in Blöcke M fester
Länge getrennten Kette von Zahlen gegeben, kleiner als N. Jeder Block ergibt ein
Kryptogramm C mit Hilfe eines Exponenten "e", der öffentlich bekannt sein kann und eine
Zahl ist, die bei der Durchführung der folgenden Operation weder "p - 1" noch "q - 1"
dividiert:
-
C = Me (mod N)
-
wobei (mod N) anzeigt, daß die Operation nach einem Modul N durchgeführt wird.
-
Zum Wiederherstellen der Nachricht muß der Empfänger einen geheimen
Exponenten "d" kennen und die Operation durchführen:
-
M = Cd (mod N), d. h.:
-
M = Mde (mod N)
-
Eine gängig, für die N bildende Zahl binärer Elemente verwendete Größe ist
512, was etwa 155 Dezimalzahlen entspricht, dann nimmt man für "p" und "q" eine Länge
der Größenordnung von 256 binären Elementen. Geräte, die dieses Kodierverfahren
umsetzen, verwenden die Theorie des chinesischen Rests, die es ermöglicht, eine über 512
binäre Elemente reichende Exponentialgröße in zwei Exponentialgrößen zu 256 Elementen
in bezug auf jeden dieser Faktoren umzuwandeln. Die Faktoren "p", "q" werden ihrerseits
mit "N" ersetzt, und die Potenzierungsoperationen nach den Moduln "p" und "q"
vorgenommen.
-
In der europäischen, unter der Nr. EPA 0 443 679 veröffentlichten
Patentanmeldung beschreibt man die Art, wie diese Potenzierungen durchgeführt werden.
Diese Lehren wurden in der von Philips hergestellten Mikrosteuerung 83C852 umgesetzt.
Die Potenzierungen werden mit Moduln durchgeführt, die normalisierte Zahlen sind. Diese
Normalisierung besteht im Reservieren von drei Bytes, die in der Folge der Berechnungen
verwendet werden. Diese Anmeldung schlägt jedoch Maßnahmen vor, wenn die Zahlen
nicht normalisiert sind. Dies beinhaltet praktisch, daß zwei Sorten Berechnungsarten
vorzukehren sind, eine erste für die normalisierten Zahlen und eine zweite für die nicht
normalisierten Zahlen. Einerseits ist dieses andere Verfahren weitaus weniger an die
Struktur der besagten Mikrosteuerung angepaßt und führt zu einer Rechenzeit, die lang sein
kann, und andererseits belasten die zwei vorhandenen Verfahren den Speicher des
Programms.
-
Hier findet die Erfindung eine wichtigen Einsatz, indem sie die
Normalisierung aller vorgeschlagenen Zahlen N ermöglicht. Diese werden mit einem
Normalisierungskoeffizienten Multipliziert, woraufhin am Ende des Potenzierungsvorgangs
eine Division durch diesen selben Koeffizienten vorgenommen wird.
-
Die vorliegende Erfindung schlägt ein Gerät der in der Einleitung von
Anspruch 1 aufgeführten Art vor, die besonders gut für die Mikrosteuerung des
vorgenannten Typs geeignet ist und es folglich ermöglicht, beliebig große Zahlen als Modul
zu verwenden und gleichzeitig eine zufriedenstellende Verarbeitungsgeschwindigkeit zu
liefern.
-
Das der Beschreibung im Anspruch entsprechende Gerät ist daher
bemerkenswert, da es eine Bestimmungsvorrichtung für Q enthält, um folgende Operation
durchzuführen:
-
A + Q'dbk = Q" · bn + k + S · bk + R', wobei dbk = bn + k - D mit k ≥ 1
-
damit der Wert S, der als Separator dient, für einen Wert Q' Null wird, damit Q" den Wert
von Q, und R' den Wert von R annimmt.
-
Die folgende, von den beigefügten Zeichnungen begleitete, als nicht
begrenzendes Beispiel gegebene Beschreibung wird leicht verständlich machen, wie die
Erfindung umgesetzt werden kann.
-
Fig. 1 zeigt die Struktur eines Geräts, in dem die Erfindung umgesetzt wird.
-
Fig. 2 zeigt sehr schematisch die Funktionsweise der Erfindung.
-
Fig. 3 ist ein Organigramm der Funktionsweise des Geräts nach einer vorgezogenen
Durchführungsform der Erfindung.
-
Das Gerät von Fig. 1 besteht aus einem Mikroprozessor 1, einem aktiven
Speicher 2, versehen mit einem Eingang für AD-Adressenkode und einem Zugang für den
Eingang und den Ausgang der DT-Daten, einem Festspeicher 3 mit insbesondere den
Funktionsinstruktionen zur Umsetzung der Erfindung und zugleich einem EEPROM-
Speicher zum Enthalten verschiedener Daten 5, insbesondere im Rahmen des
beschriebenen Beispiels eines Normalisierungswerts des Divisors λ und des Werts dbk. In
dieser Figur sind diese verschiedenen Elemente über eine im Multiplexmodus arbeitende
BUS-Leitung verbunden, d. h., sie befördert zu bestimmten Zeitpunkten Daten und zu
anderen Adressenkodes. Das Gerät von Fig. 1 enthält zudem eine Recheneinheit 8 zur
Vornahme von Multiplikationen mit oder ohne Kumulation. Diese Einheit 8 enthält einen
Satz von vier Eingängen a0, a1, a2 und a3 zum Erhalt eines in den Registern 10, 11, 12 und
13 enthaltenen Operanden zu vier Bytes, einen an die Register 14 und 15 für einen
Multiplikanden mit mehreren Bits verbundenen Eingang xi, einen mit den Registern 17 und
18 für mehrere zu addierende Bytes verbundenen Eingang Ai und einen Ausgang RO zum
Liefern des Ergebnisses. Es kommen verschiedene Operanden aus dem aktiven Speicher 2.
Je nach dem Eingang, dem diese Operanden zugeführt werden, greift man auf die
Indexregister 21, 22 und 23 zurück. Die Register 21 und 23 sind mit den
Dekrementalorganen 25 und 26 verbunden. Das Register 21 ist in bezug auf den Operanden
dem Eingang Ai zuzuführen, das Register 22 auf die Operanden den Eingängen a1, a2, a3
und a4 zuzuführen und das Register 23 auf den Operanden dem Eingang xi zuzuführen. Ein
anderes Indexregister 24 mit seinem verbundenen Dekrementalorgan 28 bezieht sich auf die
Position im Speicher 2, um das am Ausgang RO gelieferte Ergebnis einzuordnen. Die in
RPL-Pipelineregistern angeordneten Register 40, 41, 42 und 43 sind vorgesehen, um die
am Ausgang RO verfügbaren Bytes ebenfalls zu erhalten. Auf ähnliche Art wie bei
Speicher 2 sind die mit den Dekrementalorganen 55 und 56 verbundenen Indexregister 51
und 52 an den Speicher 5 angeschlossen. Auch wird ein zusätzliches Register 58 zum
Adressieren verwendet.
-
Die Recheneinheit 8 wird über verschiedene Zwischenregister 60, 62, 64, 66
und 68 gesteuert. Die Register 71, 73, 75, 77 werden direkt von der Recheneinheit 8
verwaltet. Das Register 60 ist ein Register, in dem die Steuerungen für die Einheit 8 und die
Zustandsinformationen bezüglich der von dieser Einheit vorgenommenen Operationen
gespeichert werden. Das Register 62 wird für die Steuerung der Einheit 8 verwendet. Das
Register 64 dient zum Zählen der Anzahl Bytes des vom Ausgang RO gelieferten
Ergebnisses. Das Register 66 steuert den Beginn des Schreibens in den Speicher 2 der am
Ausgang RO verfügbaren Informationen und bietet die Möglichkeit, und das Schreiben in
den Speicher einer gewissen Anzahl Bytes zu sperren, während das Register 68 vorgesehen
ist, um die Grenzwerte der den Eingängen Ai und xi zugeführten Operanden festzulegen,
d. h. deren Anzahl Bytes. Weitere Details können in der Anleitung der aufgeführten
Mikrosteuerung 83C852 gefunden werden.
-
Es wird vorgeschlagen, mit diesem Gerät eine Division eines von einer
großen Anzahl "m" gebildeten Dividenden A durch einen Divisor D mit vorzugsweise n ≤
m vorzunehmen. Das gewünschte Ergebnis ist der Quotient Y und der Rest R.
-
Gemäß der Erfindung wurde eine Bestimmungsvorrichtung von Q zur
Durchführung folgender Operation vorgesehen:
-
A + Q'dbk = Q" · bn + k + S · bk + R' (1)
-
wobei dbk = bn + k - D mit k ≥ 1, so daß der Wert S, der als Separator dient, für einen Wert Q'
Null wird, damit Q" den Wert von Q, und R' den Wert von R annimmt. Nach einem Aspekt
der Erfindung wurden bestimmte Speicherplätze vorgesehen, die ausreichen, um den
Dividenden A zu enthalten und in denen die verschiedenen mit der Relation (1)
einhergehenden Operationen durchgeführt werden, ohne zu sehr zusätzlichen Platz zu
benötigen. Diese Operationen werden in Mulitpräzision durchgeführt, d. h. mit dem
aufeinanderfolgenden Operieren auf Wörtergruppen des von "m" Wörtern gebildeten
Dividenden oder, im Rahmen des beschriebenen Beispiels, von "m" Bytes mit den
Vielfachen bJ der Menge dbk. Man beginnt mit den größten Stellenwerten, was der
Multiplikation von dbk mit bJ gleichkommt, mit J = m - n, ihn also zu den größten
Stellenwerten zu versetzen. Das Ergebnis der Operation (1) wird ein Wert Q", der die
höchsten Stellenwerte des Quotienten darstellt. Diese letztere Menge wird zum Wert qs,
wenn der Wert eines über "k" Bytes reichenden Separators S Null wird (siehe Zeile "a" der
Fig. 2). In der Praxis wird der Separator aus einem einzigen Byte gebildet. Dann wird
dasselbe Verfahren wiederholt, indem der Wert von dbk als ein Wert u · n erklärt wird,
abhängig von der Kapazität des Multiplikationsorgans als Teil des Rechenorgans 8. Dieser
Wert kann den Wert x + y annehmen, wenn die Multiplikation über "x" und "y" Bytes
enthaltende Operanden vorgenommen wird. Es treten nacheinander verschiedene
Komponenten des Quotienten qγ, qβ und qα auf, was respektive auf den Zeilen "b", "c" und
"d" der Fig. 1 dargestellt ist.
-
Die Erfindung beruht auf folgenden Betrachtungen.
-
Kommen wir zuerst auf die Teilungsformel zurück:
-
A = Q · D + R; 0 ≤ R < D
-
wobei A der über "m" Wörter einer Basis "b" kodierte Dividend ist,
-
wobei D der über "n" Wörter der Basis "b" kodierte Divisor ist,
-
sprich k Ganzzahl ≥ 1:
-
Das Komplement zu D in ZBn + k ist mit dbk bezeichnet.
-
Somit hat man:
-
A + Q · dbk = Qbn + k + r
-
Wenn man das globale Format des Akkumulators betrachtet, in dem sich das Ergebnis
A + Q · dbk befindet, kommt ein Separator (S) zum Vorschein:
-
Wenn ein (Default-)Bewertungsfehler des exakten Quotienten q gemacht
wird:
-
= Q - δ: bewerteter Quotient
-
dann: A + · dbk = Q · bn + k - δ · dbk + R
-
Der Separator ist nicht Null. Um δ zu bestimmen genügt es, den Separator
mit aufeinanderfolgenden Additionen von dbk mit dem Akkumulator zu annullieren. Dieses
Verfahren kann allerdings anhand der folgenden Beobachtung verbessert werden:
-
- wenn v&sub0; der im Separator vorhandenen Wert ist,
-
dann: A + · dbk = α&sub0;bn + k + v&sub0;bn + r&sub0;
-
unter der Beobachtung, daß: dbk = (bk - 1)bn +
-
wobei das Komplement zu D in einem Format mit n Wörtern darstellt; dann hat man
durch Addition von v&sub0; · dbk:
-
A + ( + v&sub0;)dbk = (α&sub0; + v&sub0;)bn + k + v&sub0; + r0
-
Vorausgesetzt, daß: v&sub0; + r&sub0; = v&sub1;bn + r&sub1;
-
stellt man fest, daß:
-
(a) v&sub1; < v&sub0;: der Wert im Separator wird geringer,
-
(b) die Bewertung des Quotienten wird präziser.
-
Nach einer vorgezogenen Durchführungsform der Erfindung wurde zudem
ein Zeichentest vorgesehen. Er besteht im Hinzufügen des Werts dbk auf der Ebene des
Separators, damit keine Vermehrung des Übertrags stattfinden kann, oder anders gesagt,
daß man sich versichert, daß die Komponente des Quotienten nicht zu sehr unterbewertet
wurde.
-
Das Organigramm der Fig. 3 ist nach einer jede Aktion in einem Rechteck
darstellenden Norm aufgebaut. Die fünfeckigen Felder stellen einen Test dar, wenn der Test
positiv ist, geht man zum darunterliegenden Rechteck, ansonsten zum rechts daneben
liegenden Feld über. Die verschiedenen Felder zeigen die nachstehend erklärten Aktionen.
-
Es wird vorausgesetzt, daß der aus M Bytes gebildete Dividend an einem
Platz des Speichers 2 liegt, in der folgenden Erläuterung mit Accu 6M,1> bezeichnet. Diese
Kennzeichnung bedeutet, daß die in den geschweiften Klammern stehenden, von einem
Beistrich getrennten Bytes zu betrachten sind. Hier sind folglich alle Bytes ab M als die
größten Stellenwerte bis zum Byte 1 geringen Stellenwerts zu betrachten. Die M Bytes
Accu 6M,1> werden von den Indexregistern 21 und 24 indexiert. Auch wird vorausgesetzt,
daß der Divisor, oder besser der Wert dbk, im EEPROM-Speicher vorhanden ist; dieser
Wert wird aus 4 + K Bytes gebildet (wobei K die Anzahl Bytes im Separator); er wird vom
Register 52 angezeigt. Schließlich wird vorausgesetzt, daß der Normalisierungskoeffizient
λ des Divisors D ebenfalls im EEPROM-Speicher vorhanden ist, wobei dieser jedoch von
51 angezeigt wird. Der Koeffizient λ wird definiert durch:
-
λ = MAX 6 · 0ù; x · D # bn + k> , wobei ù sämtliche positiven Ganzzahlen bezeichnet
-
K1: Bezeichnet die Aktion, die darin besteht, einen Wert I, der die Anzahl Schritte im
Algorithmus darstellt, an einen als Zähler dienenden Platz des Speichers 2 zu
bringen. Zum Bestimmen dieser Zahl I wird der Divisor in Gruppen zu vier Bytes
aufgeteilt, was der Länge der Multiplikanden entspricht, die der
Multiplikationsoperation entsprechen, die die Recheneinheit 8 durchführen kann.
-
K2: Ist die Aktion, die die auf der Seite des höchsten Stellenwerts verbleibenden Bytes
der Vierergruppe auf Null stellt. Die Register 23, 21 und 24 zeigen zu dem Oktett
Accu 64I-7> .
-
K3: Man testet, ob alle Schritte durchgeführt wurden.
-
K10: Bezeichnet die aktuellen Divisionsoperationen.
-
K11: Zuerst werden die vier Bytes des Normalisierungskoeffizienten γ in die vier RPL-
Register gebracht; diese Bytes gehen durch die Einheit 10 mittels einer Anweisung,
die eine Multiplikation mit einem Kumulationsoperanden steuert, der λ ist und den
Multiplikanden mit Hilfe des Registers 68 auf einen Wert Null festlegt.
-
K13: Acht der Bytes (der größten Stellenwerte des Dividenden, beginnend beim ersten
Schritt), die in A 6I,4I-7> enthalten sind, werden multipliziert. Das im Prinzip aus
12 Bytes gebildete, hier mit UC 612,1> bezeichnete Resultat geht durch das RPL-
Register.
-
K15: Von diesen 12 Bytes werden nur 4 beibehalten, d. h. UC 611,8> . Das Byte
höchsten Stellenwerts UC 612> wird, um eine korrekte Ausrichtung zu erhalten,
entfernt. UC 611,8> wird dann in das RPL-Register übertragen. Es ist zu
bemer
ken, daß die in den Feldern K11 und K13 gezeigten Operationen außerhalb der
Recheneinheit keinen vorgekehrten Zwischenspeicher benötigen. Diese Bytes UC
611,8> bilden einen Wert des angenäherten Quotienten .
-
K17: Der im RPL-Register verfügbare angenäherte Quotient wird jetzt durch die
Addition von · dbk zur Verminderung des Akkumulators verwendet. Es ist zu bemerken,
daß der angenäherte Quotient im RAM-Speicher nach den K Separationsbytes
auftritt.
-
K19: Aus Accu wird der Separator entnommen, um ihn den Eingängen RPL zuzuführen.
Man beachte die vor dem Separator übertragenen 0,0,0.
-
K21: Der Wert dieses Separators wird mit Null verglichen. Solange dieser Separator
nicht Null ist, werden die Operationen des Felds K23 ausgeführt, das selbst
wiederum die Felder K25 und K27 beinhaltet.
-
K25: Der Separator wird mit dbk multipliziert und Accu hinzugefügt.
-
K27: Der Separator wird erneut entnommen und RPL zugeführt.
Dies wird fortgesetzt, solange der Separator nicht Null ist.
-
K29: Es wird der Zeichentest gestartet, indem dbk dem Inhalt von Accu zugefügt wird,
und das Ergebnis wird in die fiktiven Arbeitsbereiche UC 66,1> gebracht, denn
tatsächlich wird nur der Bereich UC66> für das nächste Feld berücksichtigt.
-
K31: Das höchste, den Übertragwert enthaltende Byte wird am Ende vom Test in das
RPL-Register zurückgebracht.
-
K33: Hier führt man den Test durch, solange dieser Inhalt ungleich 0 ist, führt man die in
Feld K35 gezeigte Operation durch.
-
K35: Der Wert von dbk wird mit den Inhalten von Accu addiert.
-
K37: Der Wert von I wird dekrementiert, um gegebenenfalls die Operation von Feld K10
nochmals durchzuführen.
-
Es folgt ein Beispiel einer im Dezimalsystem durchgeführten Division. Der
Dividend ist 99145360 und der Divisor 80. Die Multiplikation wird vorausgesetzter Weise
über 2 · 2 Stellen vorgenommen, weshalb man ausdrücklich zuläßt, daß die Kapazität des
RPL-Registers ebenfalls zweistellig, und der Separator nur einstellig ist. Der
Normalisierungskoeffizient des Divisors ist derart, daß λ · D = 960, d. h. λ = 12 und dbk = 920.
ANHANG 1 BEISPIEL MIT BASIS 10 (DEZIMAL)
ANHANG 1 (Fortsetzung)
ANHANG 1 (Fortsetzung)