DE3650335T2

DE3650335T2 - Rechenverfahren und -gerät für endlichfeldmultiplikation.

Info

Publication number: DE3650335T2
Application number: DE3650335T
Authority: DE
Inventors: Ronald C Mullin; Ivan M Onyszchuk; Scott A Vanstone
Original assignee: Cryptech Systems Inc
Current assignee: Certicom Corp
Priority date: 1986-12-16
Filing date: 1986-12-16
Publication date: 1996-03-21
Anticipated expiration: 2006-12-17
Also published as: AU6939487A; AU625552B2; EP0337985A1; GB2176325B; CA1242030A; EP0337985A4; US4745568A; GB8613182D0; GB2176325A; EP0337985B1; WO1988004805A1; DE3650335D1

Description

Hintergrund der Erfindung

Die vorliegende Erfindung betrifft ein Verfahren und eine Vorrichtung zum multiplizieren zweier Elemente in dem endlichen Feld GF(2m).
Wie in der europäischen Anmeldung 0080528, aus der die folgende Diskussion entnommen wurde, vollständig erklärt ist, ist das endliche Feld GF(2m) ein Zahlensystem, das 2m Elemente enthält. Seine Attraktivität in praktischen Anwendungen resultiert aus dem Vermögen, jedes Element durch einen Vektor aus m Bits (binary digits) darzustellen. Die praktische Anwendung von fehlerkorrigierenden Codes verwendet in erheblichem Maße eine Berechnung im GF(2m). Sowohl die Codier- als auch die Dekodiervorrichtungen für die wichtigen Reed-Solomon-Codes müssen Berechnungen im GF(2m) ausführen. Die Dekodiervorrichtung für die binären Bose-Chaudhuri-Hocquenghem-Codes muß ebenfalls eine Berechnung im GF(2m) ausführen. Der Leser wird auf "Error-Correcting Codes" von W.W. Peterson und E.J. Weldon, Jr. , 2. Ausgabe, M.I.T. Press, 1972 hinsichtlich Details dieser und anderer Anwendungen der GF(2m)-Berechnung für Fehlerkorrektur verwiesen.
Es gibt kryptographische Systeme mit Verschlüsselungs- und Entschlüsselungsalgorithmen, die Potenzierungsoperationen an großen Zahlen benötigen. Mehrere Kryptosysteme mit öffentlichem Schlüssel wurden vorgeschlagen, die die Anwendung der Potenzierung von Elementen im GF(2m) benötigen oder daran angepaßt werden können. Da der Prozeß des Potenzierens aus Quadrierungs- und Multiplikationsoperationen besteht, ist es wesentlich, daß diese Operationen so schnell und effizient wie möglich ausgeführt werden. Der Leser wird auf "Cryptography and Data Security" von D.E. Denning, Addison-Wesley, 1983, hinsichtlich der Beschreibung der GF(2m)-Arithmetik- und Potenzierungsalgorithmen und Beispielen von Kryptosystemen mit öffentlichem Schlüssel, die diese Algorithmen anwenden, verwiesen.
Neueste Fortschritte in der Technik der Geheimhaltungs-Codierung benötigen auch die Verwendung der Berechnung im GF(2m). Der Leser wird auf das Schreiben "Implementing Public Key Scheine", von S. Barkovits, J. Kowalchuk und B.Schanning, IEEE Communications Magazine, Ausgabe 17, Seiten 2-3, Mai 1979, verwiesen.
Das endliche Feld GF(2) ist das Zahlensystem, in dem die einzigen Elemente die binären Zahlen 0 und 1 sind, und in dem die Regeln der Addition und Multiplikation wie folgt sind:
0 + 0 = 1 + 1 = 0
0 + 1 = 1 + 0 = 1
0 x 0 = 1 x 0 = 0 x 1 = 0 (1)
1 x 1 = 1
Diese Regeln werden weithin Modulo 2-Arithmetik genannt. Also werden alle Additionen, die in logischen Ausdrücken oder durch Addierer spezifiziert sind, in dieser Anmeldung Modulo 2 ausgeführt. Zusätzlich wird die Multiplikation durch logische UND-Glieder durchgeführt, um mit der oben unter (1) aufgestellten Regel übereinzustimmen. Das endliche Feld GF(2m), in dem in eine ganze Zahl größer als 1 ist, ist das Zahlensystem, in dem es 2m Elemente gibt, und in dem die Regeln der Addition und Multiplikation mit arithinetischem Modulo, eines nicht reduzierbaren Polynoms des Grades in mit Koeffizienten im GF(2) übereinstimmen. Selbst im abstrakten Sinn gibt es für jedes in nur ein Feld GF(2m), wobei die Komplexitität der logischen Schaltungsanordnung, die benötigt wird, um Operationen im GF(2m) durchzuführen, stark von der bestimmten Weise abhängen, in der die Feldelemente dargestellt sind.
Der herkömmliche Weg zum Entwurf einer logischen Schaltungsanordnung, um Operationen im GF(2m) durchzuführen, ist in derartigen Schriften, wie z.B. T. Bartes und D. Schneider, "Computation with Finite Fields", Information and Control, Ausgabe 6, Seiten 79-98, 1963, beschrieben. Auf diesem herkömmlichen Weg wählt man zuerst ein Polynom P(X) des Grades in aus, das über GF(2) nicht reduzierbar ist, d. h., P(X) hat binäre Koeffizienten, kann aber nicht in ein Produkt von Polynomen mit binären Koeffizienten zerlegt werden, deren jeweiliger Grad kleiner als in ist. Ein Element A im GF(2m) wird dann als eine Wurzel von P(X) definiert, d. h., um P(A) = 0 zu erfüllen. Die Tatsache, daß P(X) nicht reduzierbar ist, garantiert, daß die in Elemente A&sup0; = 1, A, A², ...Am-1 des GF(2m) über GF(2) linear unabhängig sind, d. h., daß b&sub0; + b&sub1;A + b&sub2;A² +... + bm-1Am-1 nur verschwindet, wenn die Bits b&sub0;, b&sub1;, b&sub2;... bm-1 alle Null sind. Es ist der herkömmliche Weg, den Einheitsvektoren der Länge in mit binären Komponenten dann die Elemente 1, A, A², ..., Am-1 zuzuweisen.
Als spezielles Beispiel des herkömmlichen Weges sei das endliche Feld GF(2³) mit der Wahl
P(X)=X³+X+1 (2)
für das nicht reduzierbare Polynom des Grades 3 betrachtet. Der nächste Schritt ist es, A als ein Element des GF(2³) festzulegen, so daß
A³+A+1 =0 (3)
ist. Die folgende Zuweisung von Einheitsvektoren wird dann gemacht:
A&sup0; = 1 = [0, 0, 1]
A = [0, 1, 0]
A² = [1, 0, 0] (4)
Ein willkürliches Element B des GF(2³) wird nun durch den binären Vektor [b&sub2;, b&sub1;, b&sub0;] dargestellt, was bedeutet, daß
B = [b&sub2;, b&sub1;, b&sub0;] = b&sub2;A² + b&sub1;A + b&sub0; (5)
ist. C = [c&sub2;, c&sub1;, c&sub0; ] sei ein zweites Element des GF(2³). Es folgt aus den Gleichungen (4) und (5), daß
B + C = [b&sub2;+c&sub2;,b&sub1;+c&sub1;,b&sub0;+c&sub0;] (6)
ist.
So wird beim herkömmlichen Weg die Addition im GF(2m) leicht durch eine logische Schaltungsanordnung ausgeführt, die nur die Modulo 2-Summe der zwei Vektoren bildet, die die Elemente darstellen, um Komponente-für- Komponente summiert zu werden. Eine Multiplikation jedoch ist um einiges komplexer zu implementieren. Beim Weiterverfolgen des Beispiels sieht man aus der Gleichung (3), daß
A³ = A + 1
A&sup4; = A² + A (7)
sind, wobei von der Tatsache Gebrauch gemacht wurde, daß -1 = +1 im GF(2) ist. Aus den Gleichungen (4), (5) und (7) folgt, daß
B x C = [d&sub2;, d&sub1;, d&sub0;] (8)
ist, wobei
d&sub0; = b&sub0;c&sub0; + b&sub1;c&sub2; + b&sub2;c&sub1;
d&sub1; = b&sub0;c&sub1; + b&sub1;c&sub0; + b&sub1;c&sub2; + b&sub2;c&sub1; + b&sub2;c&sub2; (9)
d&sub2; = b&sub0;c&sub2; + b&sub2;c&sub0; + b&sub1;c&sub1; + b&sub2;c&sub2;
sind.
Eine komplexe logische Schaltungsanordnung wird benötigt, um die Gleichungen (9) zu implementieren. Setzt man C = B in Gleichung (8), folgt aus der Gleichung (9), daß
B² = [e&sub2;,e&sub1;,e&sub0;] (10)
ist, wobei
e&sub0; = b&sub0;
e&sub1;=b&sub2; (11)
e&sub2; = b&sub1; + b&sub2;
sind, und wobei von der Tatsache Gebrauch gemacht wurde, daß b&sub2; = b und b + b = 0 im GF(2) ist. Während die Quadrierungsregel der Gleichungen (11) wesentlich einfacher zu implementieren ist als die Multiplikationsregel der Gleichungen (9), hat sie immer noch den Nachteil, daß einige Additionen (in dem Beispiel nur eine) ausgeführt werden müssen, und daß sich die Form der Quadrierungsregel zwischen den Komponenten des Quadrats ändert.
Zusammengefaßt kann man sagen, daß der herkömmliche Weg eine logische Schaltungsanordnung zu entwerfen, um Operationen im GF(2m) durchzuführen, zu einer einfachen Schaltungsanordnung für Addition führt, zu einer etwas komplexeren Schaltungsanordnung zum Quadrieren und zu einer sehr komplexen Schaltungsanordnung für eine Multiplikation.
In der oben erwähnten europäischen Anmeldung 0080528 wurde ein Fortschritt in den folgenden speziellen Merkmalen des endlichen Felds GF(2m) erzielt. Es existiert immer eine sogenannte Normalenbasis für dieses endliche Feld, d. h., man kann immer ein Feldelement A finden, so daß A, A², A&sup4;, ... , A2m-1 die Basis für das GF(2m) in dem Sinn ist, daß jedes Feldelement B einheitlich als
B = bm-1A2m-1 ... + b&sub2;A&sup4; + b&sub1;A² + b&sub0;A = [bm-1,..., b&sub2;, b&sub1;, b&sub0;] (12)
geschrieben werden kann, wobei b&sub0;, b&sub1;, b&sub2;, ..., bm-1 Bits sind. Darüber hinaus ist eine Quadrierung im GF(2m) eine lineare Operation in dem Sinn, daß für jedes Paar von Elementen B und C im GF(2m)
(B + C)² = B² + C² (13)
ist. Darüber hinaus ist es für jedes Element B des GF(2m) der Fall, daß
B2m = B (14)
ist.
Die Erfinder in der oben genannten Anmeldung strebten danach, den Multiplikationsprozeß durch anfängliches Auswählen eines Polynoms P(X) des Grades in zu vereinfachen, das über GF(2) nicht reduzierbar ist, und das linear unabhängige Wurzeln aufweist. Diese letzte Bedingung an P(X) stellt sicher, daß beim Definieren von A als ein Element des GF(2m), so daß P(A) = 0 ist, dann A, A², A&sup4;, ..., A2m-1 eine Normalenbasis für das GF(2m) bilden.
Hinsichtlich einer Diskussion von Normalenbasen in endlichen Feldern wird der Leser auf "Finite Fields" von Lidl und Neidereiter verwiesen. Falls dann B = [bm-1, ..., b&sub2;, b&sub1;, b&sub0;] und C = [cm-1, ..., c&sub2;, c&sub1;, c&sub0; ] irgendwelche zwei Elemente des GF(2m) in der Normalenbasisdarstellung sind, dann hat das Produkt
D = B x C = [dm-1, ..., d&sub2;, d&sub1;, d&sub0;] (15)
die Eigenschaft, daß dieselbe logische Schaltungsanordnung, die dm-1 erzeugt, wenn sie auf die Komponenten oder Bits der Vektoren angewendet wird, die B und C darstellen, sequentiell die übrigen Komponenten dm-2, ..., d&sub2;, d&sub1;, d&sub0; des Produkts bildet, wenn sie auf die Komponenten der aufeinanderfolgenden Rotationen der Vektoren angewendet wird, die B und C darstellen.
Dies kann man sich bewußt machen, indem die Bits d&sub2;, d&sub1;, d&sub0; z. B. in der oben genannten Gleichung (9) betrachtet werden, wobei
d&sub2; = b&sub1;c&sub1; + b&sub0;c&sub1; + b&sub1;c&sub0; + b&sub0;c&sub2; + b&sub2;c&sub0;
d&sub1; = b&sub0;c&sub0; + b&sub2;c&sub0; + b&sub0;c&sub2; + b&sub2;c&sub1; + b&sub1;c&sub2;
d&sub0; = b&sub2;c&sub2; + b&sub1;c&sub2; + b&sub2;c&sub1; + b&sub1;c&sub0; + b&sub0;c&sub1;
sind. Ähnliche der Bits bj oder cj werden gruppiert, um gruppierte Terme zu erhalten, so daß diese in der Form
d&sub2; = b&sub0; (c&sub1; + c&sub2;) + c&sub0; (b&sub1; + b&sub2;) + b&sub1;c&sub1;
d&sub1; = b&sub2; (c&sub0; + c&sub1;) + c&sub2; (b&sub0; + b&sub1;) + b&sub0;c&sub0;
d&sub0; = b&sub1; (c&sub2; + c&sub0; ) + c&sub1; (b&sub2; + b&sub0;) + b&sub2;c&sub2;
umgeschrieben werden können, wobei ein Ausdruck, wie z. B. b&sub0;(c&sub1; + c&sub2;) anschließend als ein gruppierter Term bezeichnet wird. So könnte die logische Gleichung für d&sub1; aus der für d&sub2; hergeleitet werden, indem der Suffix aller Bits bj, cj um 1 (Modulo-3) reduziert wird. Eine praktische Implementierung wurde durch Eingeben der Vektoren in entsprechende Schieberegister erreicht, die Verbindungen herstellen und eine digitale logische Schaltungsanordnung implementieren, um alle Terme der Komponente d&sub2; gleichzeitig zu erzeugen.
Dann werden die Schieberegistermhalte um eine Bit-Position rotiert, um d&sub1; und gleichzeitig d&sub0; zu erhalten. So könnten durch Rotieren der Vektoren B und C in den zwei Schieberegistern die Bits des Produktvektors D durch eine logische Schaltung erzeugt werden.
Während jedoch der oben genannte Vorschlag effizienter als der herkömmliche Weg ist, weist er den Nachteil auf, daß alle gruppierten Terme, die ein Bit des Vektors bilden, gleichzeitig an einer Stelle addiert werden müssen. Das macht die Implementierung der Logik kompliziert und für große Werte von in (z. B. größer als 250) unpraktisch. Die oben genannte europäische Anmeldung schlägt auch das gleichzeitige oder parallele Erzeugen aller in Bits des Produktvektors durch in identische Multiplizierer-Logikschaltungen vor. Dies jedoch verschlimmert nur die Schwierigkeit logischer Implementierung wegen der Zunahme externer Schieberegisterverbindungen und der Größe der benötigten Schaltungsanordnung.
Die Anmelder haben erkannt, daß eine Multiplikation durch Speichern von Bitvektoren B und C in jeweiligen Schieberegistern und Herstellen von Verbindungen zu jeweiligen Akkumulatorzellen implementiert werden können, so daß ein gruppierter Term jeder der Ausdrücke dj in den jeweiligen der in Akkumulatorzellen erzeugt wird. Durch Rotieren der Bitvektoren B und C in den Schieberegistern und durch Rotieren der Inhalte der Akkumulatorzellen, wird jeder gruppierte Term eines jeweiligen Bits dj in aufeinanderfolgenden Zellen akkumuliert. So werden alle Bits des Produktvektors gleichzeitig in den Akkumulatorzellen nach einer kompletten Rotation der Bitvektoren B und C erzeugt
Ausführungsformen der Erfindung, die in den unabhängigen Ansprüchen 1,10 und 12 und in den abhängigen Ansprüchen 2-9, 11, und 13-18 beansprucht sind, werden nun nur als Beispiel unter Bezugnahme auf die beigefügten Zeichnungen beschrieben, in denen:
Figur 1 ein Blockdiagramm eines Multiplizierers ist, um eine Multiplikation von zwei Elementen in dem Feld GF(2&sup5;) zu implementieren;
Figur 2 ein logisches Blockschaltbild der Komponente ist, die in dem Multiplizierer der Figur 1 verwendet wird;
Figur 3 ein Blockschaltbild einer alternativen Form eines Multiplizierers ist, um eine Multiplikation von zwei Elementen in dem Feld GF(2&sup5;) zu implementieren;
Figur 4 ein Blockdiagramm einer weiteren Ausführungsforin eines Multiplizierers ist, um eine Multiplikation in dem Feld GF(2&sup5;) zu implementieren; und
Figur 5 ein Blockdiagramm des Multiplizierers der Figur 4 ist, wobei die Verbindungen für eine optimale Implementierung eines GF(2&sup5;)-Multiplizierers modifiziert sind.
Das Operationsprinzip kann am besten unter Bezugnahme auf die Figuren 1 und 2 verstanden werden, die die logische Implementierung zum Multiplizieren zweier Elemente in dem endlichen Feld GF(2&sup5;) darstellen. Ehe auf die Figuren detailliert Bezug genommen wird, ist es nützlich, die Form des Produkts D zweier Elemente B und C zu betrachten.
B ist von der Form B = (b&sub0;, b&sub1;, b&sub2;, b&sub3;, b&sub4;) in Normalenbasisdarstellung und C ist von der Form C = (c&sub0;, c&sub1;, c&sub2;, c&sub3;, c&sub4;) in Normalenbasisdarstellung.
Das Produkt D ist von der Form D = (d&sub0;, d&sub1;, d&sub2;, d&sub3;, d&sub4;) in Normalenbasisdarstellung. Jeder der Bitvektoren dj besteht aus gruppierten Termen der Bits, die B und G darstellen,und für den Fall, in dem m = 5 ist, folgt
dj = bj+&sub4; (cj+4+cj+3+cj+1+cj) + bj+3
(cj+4+cj+2+cj+1+cj) + bj+2(cj+3+cj)
+ bj+1 (cj+4+cj+3)
+ bj (cj+4+cj+3+cj+2).
Allgemein werden alle Indizes addiert, indem sie Modulo 5-Arithmetik verwenden. So haben die Bits folgende Form:
d&sub0;=b&sub4;(c&sub4;+c&sub3;+c&sub1;+c&sub0;)+b&sub3;(c&sub4;+c&sub2;+c&sub1;+c&sub0;)+ b&sub2;(c&sub3;+c&sub0;)+b&sub1;(c&sub4;+c3)+b&sub0;(c&sub4;+c&sub3;+c&sub2;)
d&sub1;=b&sub0;(c&sub0;+c&sub4;+c&sub2;+c&sub1;)+b&sub4;(c&sub0;+c&sub3;+c&sub2;+c&sub1;)+ b&sub3;(c&sub4;+c&sub1;)+b&sub2;(c&sub0;+c&sub4;)+b&sub1;(c&sub0;+c&sub4;+c&sub3;)
d&sub2;=b&sub1;(c&sub1;+c&sub0;+c&sub3;+c&sub2;)+b&sub0;(c&sub1;+c&sub4;+c&sub3;+c&sub2;)+ b&sub4;(c&sub0;+c&sub2;)+b&sub3;(c&sub1;+c&sub0;)+b&sub2;(c&sub1;+c&sub0;+c&sub4;)
d&sub3;=b&sub2;(c&sub2;+c&sub1;+c&sub4;+c&sub3;)+b&sub1;(c&sub2;+c&sub0;+c&sub4;+c&sub3;)+ b&sub0;(c&sub1;+c&sub3;)+b&sub4;(c&sub2;+c&sub1;)+b&sub3;(c&sub2;+c&sub1;+c&sub0;)
undd&sub4;=b&sub3;(c&sub3;+c&sub2;+c&sub0;+c&sub4;)+b&sub2;(c&sub3;+c&sub1;+c&sub0;+c&sub4;)+ b&sub1;(c&sub2;+c&sub4;)+b&sub0;(c&sub3;+c&sub2;)+b&sub4;(c&sub3;+c&sub2;+c&sub1;)
Anhand des Vorstehenden wird bewußt, daß durch Herstellen von logischen Verbindungen, um den ersten gruppierten Term b&sub4; (c&sub4;+c&sub3;+c&sub1;+c&sub0;) von d&sub0; zu erzeugen, der erste gruppierte Term der Bits d&sub4;, d&sub3;, d&sub2; und d&sub1; auch durch diese selben Verbindungen erzeugt wird, falls die Bitvektoren von B und C aufeinander folgend um eine Stelle nach rechts rotiert werden. Die Anmelder haben erkannt, daß, falls Verbindungen auch hergestellt werden, um den zweiten gruppierten Term von d&sub0; nach dem Erzeugen des ersten gruppierten Terms und nachdem die Bitvektoren rotiert worden sind, die Verbindungen in der Tat den zweiten gruppierten Term von d&sub1; vor dem Rotieren der Bitvektoren B und C erzeugen. So ist es möglich, durch Herstellen von Verbindungen, um aufeinanderfolgende gruppierte Terme der Bits d&sub0; in aufeinanderfolgenden Taktzyklen zu erzeugen, jedes der Bits des Produktvektors parallel zu akkumulieren. Dies vereinfacht eine Implementierung der Logik.
Unter Bezugnahme auf Figur 1 umfaßt ein Multiplizierer 10 deshalb ein Paar von Schieberegistern 12, 14, wobei jedes in Zellen 16 aufweist. Die Schieberegister 12 und 14 werden mit Bitvektoren B bzw. C geladen, so daß jede Zelle 16 eines der Bits bj oder cj aufweist.
Die Schieberegister 12, 14 sind, derart wie nachfolgend beschrieben, mit den jeweiligen Akkumulatorzellen 18 eines Term-Akkumulatorregisters 20 verbunden. Das Register 20 hat in Zellen 18, von denen jede wie in Figur 2 gezeigt konfiguriert ist. Unter Bezugnahme auf Figur 2 nimmt jede Zelle 18 ein Paar von Eingangssignalen 22, 24, die von den Schieberegistern 12 bzw. 14 kommen, und ein Eingangssignal 26 von der angrenzenden Zelle 18 des Registers 20 auf. Die Eingangssignale 22, 24 sind mit Eingängen eines UND- Glieds 28 verbunden. Der Ausgang des Glieds 28 ist dem Eingang 26 am MOD 2-ADDIERER 30 zugefügt, dessen Ausgang mit einem Signalspeicher 32 verbunden ist. Das Ausgangssignal des Signalspeichers 32 bildet das Eingangssignal 26 der nächsten Zelle 18 und empfängt ein Taktsignal 34, um das Ausgangssignal des ADDIERERs 30 zu speichern.
Die Art der Eingangssignale 22, 24 wird durch die Verbindungen bestimmt, die zwischen den Zellen 16 der Schieberegister 12, 14 und der Zelle 18 implementiert sind. Die Verbindungen sind so angeordnet, daß ein gruppierter Term der Bits dj am Ausgang des UND-Glieds 28 erzeugt wird. So werden für die oben gezeigten Bits d&sub0; bis d&sub4; die Bits b&sub0; bis b&sub4; und c&sub0; bis c&sub4; in den Schieberegistern 12 bzw. 14 gespeichert, wie in Figur 1 gezeigt. Ein erster gruppierter Term von d&sub0; wird in der Zelle 18 akkumuliert, die mit d&sub0; in Figur 1 bezeichnet ist, d. h., das Ausgangssignal des UND-Glieds 28 bezeichnet den gruppierten Term b&sub0; (c&sub4;+c&sub3;+c&sub2;). Um dies zu implementieren ist eine Verbindung von der Zelle 16 des Schieberegisters 12 hergestellt, das das Bit b&sub0; enthält, um das Eingangssignal 22 zu bilden. Die Verbindungen von den Zellen 16 des Schieberegisters 14, das die Bits c&sub4;, c&sub3; und c&sub2; enthält, werden für den ADDIERER 36 erzeugt dessen Ausgangssignal, das c&sub4;+c&sub3;+c&sub2; darstellt, das Eingangssignal 24 zum UND-Glied 28 bildet. Das Ausgangssignal des UND-Glieds 28 wird so b&sub0;(c&sub4;+c&sub3;+c&sub2;).
Es werden Verbindungen zwischen den Schieberegistern 12, 14 und der Zelle 18 hergestellt, die mit d&sub1; bezeichnet ist, um den vorletzten gruppierten Term von d&sub1;, d. h. den Term b&sub2; (c&sub0;+c&sub4;) zu erzeugen. So sind die Zellen 16 des Schieberegisters 14, die die Bits c&sub0; und c&sub4; enthalten, mit dem Addierer 38 verbunden, dessen Ausgangssignal das Eingangssignal 24 der Zelle 18 bildet, die mit d&sub1; bezeichnet ist, und die Zelle 16 des Schieberegisters 12, das das Bit b&sub2; enthält, ist mit dem Eingang 22 der Zelle 18 verbunden, die mit d&sub1; bezeichnet ist, so daß das Ausgangssignal des UND-Glieds 28 gleich b&sub2; (c&sub0;+ c&sub4;) ist.
Ebenso sind die Schieberegister 12, 14 mit der Zelle 18 verbunden, die mit d&sub2; bezeichnet ist, um den dritten Term des Bits d&sub2; zu erzeugen, d. h. b&sub4;(c&sub0;+c&sub2;); mit der Zelle 18, die mit d&sub3; bezeichnet ist, um den zweiten Term des Bits d&sub3; zu schaffen, d. h. b&sub1;(c&sub2;+C&sub0;+c&sub4;+c&sub3;); und mit der Zelle 18, die mit d&sub4; bezeichnet ist, um den ersten Term des Bits d4 zu erzeugen, d. h. b&sub3;(c&sub3;+c&sub2;+c&sub0;+c&sub4;).
Deshalb ist allgemein die j-te Zelle 18 des Akkumulatorregisters 20 mit den Schieberegistern 12, 14 verbunden, um die den j-ten gruppierten Term eines Bits dj zu erzeugen, wobei die Indizes der Bits bj und cj, die um j - 1 vergrößert werden, Modulo m-Arithmetik verwenden. Diese Änderung der Indizes des gruppierten Terms wird "Offsetting" genannt und stellt sicher, daß jede der in Akkumulatorzellen einen gruppierten Term jedes der Bits dj während jedem der m aufeinanderfolgenden Taktzyklen erzeugt.
Mit den hergestellten Verbindungen können die Bits d&sub0; bis d&sub5; wie folgt erzeugt werden.
Als erstes werden die Bits b&sub0; bis b&sub5; in das Schieberegister 12 geladen und die Bits c&sub0; bis c&sub5; werden in das Schieberegister 14 geladen. Diese können parallel oder in Serie geladen werden, wie es für die besonderen verwendeten Schieberegister am besten geeignet ist. Die Inhalte der Signalspeicher 32 der Zellen 18 des Akkumulatorregisters 20 werden durch Laden von Nullen in jeden gelöscht. Bei der Einleitung der Multiplikation werden die gruppierten Terme entsprechend der vorstehenden Verbindungen an dem Ausgang jedes UND-Glieds 28 erzeugt. Da jedes der Eingangssignale 26 Null ist, stimmen die Ausgangssignale des MOD 2-ADDIERERs 30 in jedem Fall mit dem Ausgangssignal des UND-Glieds 28 überein.
An der ersten ansteigenden Flanke des Taktsignals wird das Ausgangssignal jedes ADDIERERS 30 in den entsprechenden Signalspeicher 32 eingegeben, um als das Eingangssignal der angrenzenden Zelle 18 zu erscheinen So enthält der Signalspeicher 32 der Zelle 18, die mit d&sub0; bezeichnet ist, den Term b&sub0;(c&sub4;+c&sub3;+c&sub2;), der Signalspeicher 32 der Zelle 18, die mit d&sub1; bezeichnet ist, enthält den Term b&sub2;(c&sub0;+c&sub4;) etc. Die erste ansteigende Flanke des Taktsignals verursacht die gleichzeitige Rotation der Inhalte der Register 12 bzw. 14 um eine Position nach rechts, so daß die Bits bi und 91 zu einer angrenzenden Zelle übertragen werden. So werden die Eingangssignale der Zelle 18, die mit d&sub0; bezeichnet ist, nun b&sub4; vom Schieberegister 12 und (c&sub1;+c&sub2; +c&sub3;) vom Addierer 36. Das Ausgangssignal des UND-Glieds 28 der Zelle 18, die mit d&sub0; bezeichnet ist, wird so b&sub4;(c&sub1;+c&sub2;+c&sub3;). Das Eingangssignal 26 der Zelle 18 (d&sub0;) wird zu den Inhalten des Signalspeichers 32 der Zelle 18 (d&sub4;), d. h. b&sub3;(c&sub3;+c&sub2;+c&sub0;+c&sub4;), und so wird das Ausgangssignal des MOD 2- ADDIERER 30 der Zelle 18 (d&sub0;) gleich b&sub4;(c&sub1;+c&sub2;+c&sub3;) + b&sub3;(c&sub3;+c&sub2;+c&sub0;+c&sub4;).
Man sieht, daß dies mit zwei gruppierten Termen des oben dargestellten Bits d&sub4; übereinstimmt. Eine genaue Betrachtung des Ausgangssignals jedes ADDIERERS 30 zeigt, daß die Summe zweier gruppierter Terme jedes Bits dj als das Ausgangssignal der jeweiligen Signalspeicher 32 erscheint.
Bei der nächsten ansteigenden Flanke des Taktsignals werden die Ausgangssignale jedes ADDIERERS 30 in entsprechende Signalspeicher 32 und die Bits bj und cj werden in den Schieberegistern 12 bzw. 14 rotiert. So werden die Inhalte des Signalspeichers der Zelle 18 (d&sub0;), nämlich b&sub4;(c&sub1;+c&sub2; +c&sub3;)+b&sub3;(c&sub3;+c&sub2;+c&sub0;+c&sub4;) als Eingangssignal 28 der Zelle 18 (d&sub1;) vorhanden sein und das Ausgangssignal des UND-Glieds 28 der Zelle 18 (d&sub1;) wird b&sub0; (c&sub2; + c&sub3;), d. h. ein dritter gruppierter Term des Bits d&sub4;. Es wird bewußt, daß nach fünf Taktzyklen die Summe aller gruppierter Terme des Bits d&sub4; in dem Signalspeicher der Zelle 18, die mit d&sub3; bezeichnet ist, gespeichert wird und ebenso die Summe aller gruppierten Terme der Bits d&sub3; bis d&sub0; in entsprechenden Zellen 18 gespeichert werden. So ist der Bitvektor, der die Normalenbasisdarstellung des Produkts D bildet, durch Lesen der Inhalte des Akkumulatorregisters 20 verfügbar.
Es wird auch bemerkt, daß die Verbindungen von den Zellen 16 der Schieberegister 12 und 14 unter den Zellen 18 des Akkumulatorregisters 20 verteilt sind, um die Zahl der Eingänge jedes Addierers zu reduzieren.
Während der vorstehend beschriebene Multiplizierer eine wesentliche Verbesserung gegenüber dem darstellt, der in der europäischen Patentanmeldung 0080528 beschrieben ist, kann die Zahl der Verbindungen weiter reduziert werden, obwohl die Zahl der Taktzyklen, die benötigt werden, um die Bits d&sub1; zu erzeugen, größer wird. Ein Multiplizierer für das Feld GF(2&sup5;) ist in Figur 3 gezeigt und ist ähnlich dem in Figur 1 gezeigten. Dementsprechend werden die Bezugsziffern, die in der Beschreibung der Figur 1 und 2 verwendet werden, verwendet, um ähnliche Komponenten mit einem hinzugefügten Präfix 100 zu kennzeichnen, d. h. die Bezugsziffer 12 wird 112. Die in Figur 3 gezeigte Anordnung unterscheidet sich auf zweierlei Weise, nämlich durch die Bereitstellung zum Austauschen der Inhalte der Schieberegister 112 und 114 wie durch die gestrichelten Linien 150, 152 bezeichnet, und durch die Art der Verbindungen zwischen den Zellen 116 und 118. Es wird auch bemerkt daß die Schieberegister 112, 114 durch ein separates Taktsignal, das mit Takt 1 bezeichnet ist, zum Akkumulatorregister 120 gesteuert werden, dessen Taktsignal mit Takt 2 bezeichnet ist.
Die Art der Verbindungen wird von einer weiteren Manipulation der Terme gebildet, die die Bits dj darstellen. So kann dies unter Betrachtung des vorstehenden Bits d&sub4; folgendermaßen geschrieben werden:
b&sub3;c&sub3;+b&sub3;c&sub2;+b&sub3;c&sub0;+b&sub3;c&sub4;+b&sub2;c&sub3;+b&sub2;c&sub1;+b&sub2;c&sub0; +b&sub2;c&sub4;+b&sub1;c&sub2;+b&sub1;c&sub4;+b&sub0;c&sub3;+b&sub4;c&sub3;+b&sub4;c&sub2;+b&sub4;c&sub1;
und folgendermaßen umgeschrieben werden:
b&sub3;c&sub3;+[b&sub3;c&sub2;+b&sub2;c&sub3;]+[b&sub3;c0+b&sub0;c&sub3;] +[b&sub3;c&sub4;+b&sub4;c&sub3;]+[b&sub2;c&sub1;+b&sub1;c&sub2;]+[b&sub2;c&sub4;+b&sub4;c&sub2;) +[b&sub1;c&sub4;+b&sub4;c&sub1;]
Es wird beobachtet, daß die Terme innerhalb der Klammern [] eine Symmetrie besitzen&sub1; so daß falls ein Produktterm die Form bjck besitzt, der andere Produktterm durch Vertauschen der Suffizes, d. h. bkci, erhalten wird. Es wurde erkannt, daß durch Implementieren der Logik, um einen Produktterm jedes Paars zu erzeugen, der andere Produktterm durch eine einfache Vertauschung der Inhalte der Schieberegister erhalten werden kann, und durch eine wiederholte Schaltungsoperation kann jedes der Produktterme jedes Paars erhalten werden. Darüberhinaus trifft das Offsetting-Prinzip immer noch zu, so daß die Terme jedes Bits parallel erzeugt werden. Der Ausdruck für das Bit d&sub4; ist
Die Produktterme in Spalte Y werden dann ausgewählt und ähnliche Terme werden, wie vorstehend unter Bezugnahme auf Figur 1 diskutiert, gruppiert. So kann die Spalte Y als b&sub3;(c&sub2;+c&sub0;+c&sub4;) + b&sub2;(c&sub1;+c&sub0;+c&sub4;) + b&sub1;c&sub4; ausgedrückt werden. Durch Implementieren der Logik, um diese Terme in aufeinanderfolgenden Zellen 118 des Akkumulatorregisters 120 zu erzeugen, werden die Terme der Spalte Z auch nach Vertauschen der Schieberegister 112, 114 durch einen zweiten Durchgang durch die Akkumulatorzellen erzeugt. Der ungerade Term der Spalte X kann während einer der zwei Durchgänge durch die Zellen 118 hindurch erzeugt werden, wobei seine Bildung während des anderen Durchgangs gesperrt ist.
Es wird bemerkt, daß die gruppierten Terme der Spalte Y drei Eingangssignale für zwei der ADDIERER benötigen, während nur drei der Akkumulatorzellen 118 verwendet werden. Um die Verbindungen zwischen den Zellen 118 gleichmäßig zu verteilen, wird der Ausdruck modifiziert, um eines von jedem Paar der Produktterme auszuwählen, aber eine unterschiedliche Gruppierung zu erhalten. So werden in dem vorstehenden Beispiel die dritten und sechsten Produktterme eher aus der Spalte Z ausgewählt, als aus Y, so daß der Ausdruck b&sub3;(c&sub2;+c&sub0;) + b&sub4;(c&sub3;+c&sub2;) + b&sub2;(c&sub1;+c&sub0;) + b&sub1;c&sub4; implementiert wird. Dies erhöht die Zahl der verwendeten Zellen 118 und reduziert die Zahl der Verbindungen zu einigen der ADDIERER.
Unter Bezugnahme auf Figur 3 wird deshalb der endliche Term b&sub1;c&sub4; in der Zelle 118 implementiert, die mit d&sub0; bezeichnet ist (nachfolgend als 118 [d&sub0;] bezeichnet), und zwar durch Verbinden der Zelle 116 des Schieberegisters 112, welches das Bit b&sub1; enthält, und der Zelle 116 des Schieberegisters 114, das das Bit c&sub4; enthält mit dem UND-Glied 128. Die Verbindungen zur zweiten der Zellen 118 wird von einem zweiten Term hergestellt, wobei die Suffizes der Bits um 1, Modulo 5, erhöht sind, d. h. b&sub3;(c&sub2;+c&sub1;), und im allgemeinen akkumuliert die j-te Zelle 118 drei j-te Terme des Ausdrucks mit den Suffizes, die um j-1 (Modulo in) erhöht sind.
Verbindungen werden auch hergestellt, um den ungeraden Term b&sub3;c&sub3; der Spalte X in der Zelle 118, die mit d&sub4; bezeichnet ist, zu implementieren. Die Verbindungen zu d&sub4; werden modifiziert, um ein UND-Glied 154 zu umfassen, um die Akkumulation der Addierterme, z. B. b&sub3;c&sub3;, zu sperren. Das UND-Glied 154 ist zwischen der Zelle 116, die mit c&sub3; bezeichnet ist, und dem ADDIERER 160 angeordnet, und empfängt als ein Eingangssignal das Ausgangssignal der Zelle 116 und als sein anderes Eingangssignal ein Sperrsignal 156, das von dem Taktsignal abgeleitet ist. Wenn das Sperrsignal 156 den logischen Pegel 0 aufweist, wird das Ausgangssignal des UND-Glieds 154 Null, so daß Null durch den ADDIERER 130 zu den Inhalten des Signalspeichers 136 der vorherigen Zelle 118 [d&sub3;] addiert wird.
Mit den hergestellten Verbindungen werden die Bits b&sub0; bis b&sub4; und c&sub0; bis c&sub4; in jeweiligen Zellen 116 der Schieberegister 112, 114 geladen. Die Inhalte jeder Zelle 118 werden gelöscht, so daß jeder Signalspeicher 132 Null enthält, und das Sperrsignal 156 wird auf dem logischen Pegel 0 gehalten, um das UND- Glied 156 zu zwingen, auch Null zu sein.
Die Inhalte der Schieberegister 112, 114 und die Zellen 118 werden dann um eine Bit-Position nach rechts durch aufeinanderfolgende Taktzyklen rotiert, so daß nach in Taktzyklen eines von jedem Teil der gepaarten Produktterme in jeweiligen Zellen 118 akkumuliert wird. Die Erzeugung des Terms ist in der nachfolgenden Tabelle 1 gezeigt.
So wird erkannt, daß die Terme in d&sub4; mit dem umgeschriebenen Ausdruck für ein jedes der Paare von Produkttermen übereinstimmen.
Nach fünf Taktzyklen haben die Register 112, 114 eine komplette Rotation durchgemacht, so daß die Bits bi und ci in den Zellen 116 gespeichert werden, in die sie anfänglich gespeichert wurden.
Nun werden die Inhalte der Schieberegister 112 und 114 über Verbindungen 150, 152 ausgetauscht. Dies kann durch Verschieben der Inhalte beider Register 112, 114 für fünf Taktzyklen als ein serieller, zirkularer Austausch geschaffen werden, oder könnte alternativ durch parallele Verbindungen zwischen den Zellen 116 erhalten werden. Ein serieller Austausch ist in Figur 4 gezeigt, und ist für große Werte von m am leichtesten zu implementieren. Während des Austausches durchläuft der Takt 1 fünf Zyklen während der Takt 2 niedrig gehalten wird, um zu verhindern, daß ungewollte Terme im Register 120 akkumuliert werden. Wenn Bits dj Akkumulatorzellen passieren, sind beide Taktsignale identisch.
Nach dem Austausch der Bits wird das Sperrsignal 156 auf den logischen Pegel 1 gesetzt, so daß das UND-Glied 154 das Eingangssignal von der Zelle 116 zum Eingang des ADDIERERs 160 bewegt. Die Schaltungsoperation setzt sich wie durch die nachfolgende Tabelle veranschaulicht für die nächsten fünf Taktzyklen fort. Wieder wird erkannt, daß die Terme jedes der Bits dj in jeder der Zellen 118 parallel akkumuliert sind, so daß nach 2m Taktzyklen der Berechnung die Bits von D in den Zellen 118 des Akkumulatorregisters 120 verfügbar sind. Wegen der Notwendigkeit, die Inhalte der Schieberegister 112, 114 auszutauschen, werden zusätzliche Taktzyklen benötigt, um die Berechnung zu beenden. Jedoch ist die Zahl der Verbindungen zwischen den Schieberegistern und dem Akkumulatorregister in dem Multiplizierer der Figur 3 kleiner als jene, die in dem Multiplizierer der Figur 1 gezeigt ist, um dies wieder auszugleichen.
Die in Figur 3 gezeigte Implementierung wurde verwendet, um die Allgemeingültigkeit des vorstehend beschriebenen Prinzips zu erläutern. Jedoch können in praktischen Implementierungen, insbesondere für große Werte von m, die Verbindungen durch Auswählen der gruppierten Terme in aufsteigender Reihenfolge der Koeffizienten bj oder cj weiterhin verbessert werden. Auf diese Weise werden maximal zwei Verbindungen zwischen jeder Zelle eines der Schieberegister und des Akkumulatorregisters erhalten.
Um die Zeit zu reduzieren, die verstreicht, um die Bits dj zu berechnen, kann der Multiplizierer der Figur 3 weiterhin wie in Figur 4 gezeigt modifiziert werden. Wieder werden ähnliche Komponenten wie jene, auf die in der Beschreibung der Figuren 1 und 2 verwiesen wurde, durch ähnliche Bezugsziffern bezeichnet, wobei ein Präfix 200 zu Zwecken der Klarheit hinzugefügt wurde. Die Figur 4 zeigt einen Multiplizierer zum Erzeugen von Bits dj in dem Feld GF(2&sup4;). Es wird bemerkt daß die Schieberegister 212 und 214 in drei Einheiten, 212a, b oder c bzw. 214a, b oder c segmentiert wurden, wobei jede zwei Zellen 116 umfaßt. Ebenso ist das Akkumulatorregister 220 in drei Einheiten 220a, b oder c segmentiert, wobei jede zwei Zellen aufweist. Es wird bemerkt daß jede der Schieberegistereinheiten 212a, b und c mit einer entsprechenden Schieberegistereinheit 214a, b und c durch Pfade 250a, b, c bzw. 525a, b, c verbunden ist. Die Pfade 250, 252 werden verwendet, um die Inhalte der Register 212, 214 zwischen Einheiten a, b und c eher zu tauschen, als durch den gesamten Schieberegister. Auf diese Weise wird die Zahl der Taktzyklen, die notwendig ist, um die Inhalte des Schieberegisters zu übertragen, von m auf die Zahl der Zellen 216 in jeder Einheit reduziert.
Das Bit d&sub5; des Produkts D im GF(2&sup6;) ist folgendermaßen gegeben:
So können durch Implementieren des Ausdrucks b&sub0;(c&sub3;+c&sub5;) + b&sub1;c&sub2; + b&sub2;(c&sub0; +c&sub5;) + b&sub3;c&sub1; + b&sub4;c&sub2; + b&sub5;(c&sub4;+c&sub5;) die Bits dj der Normalenbasisdarstellung des Produkts D erzeugt werden. Es wird geglaubt, daß von der vorstehenden Diskussion klar wird, daß die anfänglichen Verbindungen, die herzustellen sind, wie folgt sind: Zelle 118 Physikalische Verbindung
In diesem Fall wird der ungerade Term anfangs in Zelle 218 [d&sub5;] erzeugt und das Eingangssignal zum der Zelle 218 [d&sub5;] zugeordneten Addierer 236, das anfangs von der Zelle 216 stammt, die das Bit c&sub4; enthält, wird nach dem ersten Durchgang durch das Akkumulatorregister 220 unter Verwendung eines UND- Glieds auf die Weise gesperrt, die dem in Figur 3 Gezeigten ähnlich ist.
Die Operation des Multiplizierers der Figur 4 ist ähnlich dem unter Bezugnahme auf Figur 3 vorstehend Beschriebenen. Jedoch tritt der Austausch der Inhalte der Register 212, 214 über die Leitung 250, 252 auf, um die Zahl der Taktzyklen, die nötig sind, um den Austausch zu beenden, von 6 auf 2 zu reduzieren.
Es wird geglaubt, daß die vorstehenden Beispiele klar und deutlich die Operation des GF(2m) des Multiplizierers erklären. Relativ kleine Werte von in wurden der Einfacheit halber ausgewählt, aber es wird deutlich, daß die vorstehenden Prinzipien für große Werte von in, die normalerweise bei Verschlüsselung angewendet werden, zutreffen.
Jedoch kann für größere Werte von m, die gewöhnlich bei Verschlüsselung verwendet werden, die Zahl der Produktterme in dem Ausdruck für das mit Bit di quadratisch mit dem Wert von in zunehmen. Dies macht die Implementierung eines Multiplizierers wegen der großen Zahl von benötigten Verbindungen unpraktisch. Für jene Werte von in, die in Tabelle 3 aufgelistet sind, existiert eine optimale Normalenbasis in dem Sinn, daß sie einen Ausdruck dj hervorbringt, der 2m-1 Produktterme aufweist, die kleinstmögliche Zahl. Jede der ganzen Zahlen in hat eine Typenbezeichnung zur Verwendung in dem nachfolgend diskutierten Computerprogramm. Die Bits bjcj des Bits d&sub0; des Produktvektors D für die optimale Normalenbasis eines Werts von in, die in Tabelle 3 aufgelistet sind, können erhalten werden, wobei das Computerprogramm, das in Anhang 1 aufgelistet ist, ausgeführt wird. Beim Ausführen des Programms für m = 6 werden die folgenden Ergebnisse erhalten:
was die Gleichung für d&sub0; wie folgt ergibt:
d&sub0;=b&sub5;c&sub5;+b&sub0;c&sub1;+b&sub1;c&sub0;+b&sub4;c&sub1;+b&sub1;c&sub4; +b&sub5;c&sub3;+b&sub3;c&sub5;+b&sub4;c&sub2;+b&sub2;c&sub4;+b&sub3;c&sub2;+b&sub2;c&sub3;
Figur 5 zeigt die Implementierung dieses Ausdrucks für den segmentierten GF(2&sup6;)-Multiplizierer, der in Figur 4 gezeigt ist, mit geeigneten Modifikationen an den Verbindungen, um das Vorstehende zu implementieren. Die Änderung von d&sub0;, um diese Verbindungen zu erhalten, wird anhand des Vorstehenden und der Betrachtung von Figur 5 klar.
Ein optimaler Multiplizierer-Entwurf existiert für jeden Wert von m, der in Tabelle 3 aufgelistet ist, so daß jede Akkumulatorzelle 218 ein einzelnes Eingangssignal von derselben Schieberegisterzelle 216 aufweist. So werden in Modulo-2 ADDIERER ausgeschlossen, im Vergleich zu den Multiplizierern der Figuren 1, 3 und 4, die die Schaltungsanordnung weiter vereinfachen.
Zusätzlich glauben die Anmelder, daß die maximale Zahl von Verbindungen zum Ausgang jeder Schieberegisterzelle 216 drei ist.
Die vorstehende Beschreibung hat B lockschaltbild-Darstellungen der Register 12, 14, 20 und der Addierer und Logikfunktionen verwendet. Jedoch wird geglaubt, daß die Auswahl und Operation der Komponenten, um die vorstehend diskutierten Funktionen auszuführen, für einen Fachmann für Digitallogik-Entwurf klar sind und daß eine weitere Spezifizierung der Komponenten nicht notwendig ist.
Deutlich verschiedene Offsett-Muster können gewählt werden, während das Prinzip der parallelen Erzeugung von Termen jedes der Bits von dj verwendet wird. Tabelle 1 Taktzyklus Tabelle 2 Taktzyklus Tabelle 2 Fortsetzung Taktzyklus Tabelle 3

Claims

1. Verfahren zum Bestimmen des Produkts D zweier Elemente B und C eines endlichen Galois-Felds GF(2m), wobei in eine ganze Zahl größer als 1 ist, und das Feld Elemente A2i (0≤i≤m) hat, die eine Normalenbasis bilden, wobei das Verfahren die folgenden Schritte aufweist:

a) Darstellen des Elements B als einen Vektor von Bits bi, wobei bi der Koeffizient von A2i in der Normalenbasisdarstellung von B ist;

b) Darstellen des Elements C als einen Vektor von Bits ci, wobei ci der Koeffizient von A2i in der Normalenbasisdarstellung von C ist;

c) Darstellen des Produkts D der Elemente B und C als einen Vektor von Bits di, wobei di der Koeffizient von A2i in der Normalenbasisdarstellung von D ist, wobei jedes der Bits di in der Form einer Summe von Produkten der Bits bi und ck (0≤j,k≤m) ausgedrückt ist;

d) Speichern der Bits bi in in aufeinanderfolgenden Zellen eines ersten Umlauf-Schieberegisters (12);

e) Speichern der Bits ci in in aufeinanderfolgenden Zellen eines zweiten Umlauf-Schieberegisters (14);

f) Auswählen mindestens einiger Produkte der Bits bj und ck(0≤j,kE m), die ein Bit di ausdrücken, und Gruppieren gleicher Bits bj oder ck, um gruppierte Terme der Form

zu schaffen;

g) Zuordnen jedes gruppierten Terms zu einer anderen der in Akkumulatorzellen (18) eines Akkumulator-Umlauf-Schieberegisters (20);

h) Herstellen vorbestiinmter Verbindungen zwischen den Zellen der ersten und zweiten Umlauf-Schieberegister (12, 14) und einer ersten Akkumulatorzelle (18), um einen ersten gruppierten Term in der Akkumulatorzelle zu schaffen;

i) Herstellen vorbestiminter Verbindungen zwischen den Zellen der ersten und zweiten Umlauf-Schieberegister (12, 14) und einer zweiten Akkumulatorzelle (18), die an die erste Akkumulatorzelle angrenzt, um einen Ausdruck zu schaffen, der äquivalent zu einem anderen gruppierten Term ist, wobei die Suffixe der Bits des zweiten gruppierten Terms um 1 (Modulo m) erhöht ist;

j) Wiederholen des Schritts i für aufeinanderfolgende gruppierte Terme, wobei die Erhöhung in dem Suffix jedes Bits di der gruppierten Terme für jede Wiederholung mit 1 (Modulo m) akkumuliert wird, wobei in jeder Akkumulatorzelle ein gruppierter Term des jeweiligen der in Bits di geschafffen wird;

k) Erzeugen eines jeweiligen gruppierten Terms in mindestens (m-1) Akkumulatorzellen;

l) Akkumulieren Modulo 2 jedes erzeugten gruppierten Terms mit den vorher erzeugten gruppierten Termen, die in einer angrenzenden Akkumulatorzelle (18) akkumuliert werden, wobei gruppierte Terme desselben Bits in derselben Zelle summiert werden;

m) Übertragen der Inhalte jeder Zelle der ersten und zweiten Umlauf- Schieberegister (12, 14) zu ihrer nächsten Zelle; und

n) Wiederholen der Schritte k, l und m (m-1)-mal, wobei nach (m-1) Wiederholungen jede Akkumulatorzelle (18) die Modulo 2-Summe der ausgewählten gruppierten Terme eines anderen Bits di umfaßt.

2. Verfahren nach Anspruch 1, wobei alle Produkte zum Gruppieren in gruppierte Terme ausgewählt werden.

3. Verfahren nach Anspruch 1, wobei der Schritt f weiterhin die Schritte des paarweisen Anordnens der Produkte umfaßt, so daß ein Term jedes Paars die Form bick und das andere Paar die Form bkcj hat, und des Auswählens eines jeden Paars zusammen mit irgendwelchen Produkttermen, die nicht paarweise angeordnet werden können, um die gruppierte Terme zu bilden.

4. Verfahren nach Anspruch 3, wobei die anderen Produktterme jedes Paars durch miteinander Vertauschen der Bits der ersten und zweiten Umlauf- Schieberegister (112, 114) durch Durchführen des Schritts n und Wiederholen der Schritte k bis n erzeugt werden.

5. Verfahren nach Anspruch 4, wobei das Erzeugen der Produktterme,

die nicht paarweise angeordnet werden können, während einer Wiederholung der Schritte k bis n verzögert wird.

6. Verfahren nach Anspruch 4, wobei jeder der ersten und zweiten Umlauf-Schieberegister (112, 114) in komplementäre Segmente (212i, 214i) segmentiert wird und Verbindungen zwischen den Umlauf-Schieberegistern hergestellt werden, so daß die Inhalte eines Segments eines Umlauf- Schieberegisters mit den Inhalten des entsprechenden Segments des anderen Umlauf-Schieberegisters vertauscht werden, wobei die Inhalte der ersten und zweiten Umlauf-Schieberegister in weniger als in Taktzyklen miteinander vertauscht werden.

7. Verfahren nach Anspruch 6, wobei die Segmente jedes Umlauf- Schieberegisters dieselbe Größe haben.

8. Verfahren nach Anspruch 1, wobei das Herstellen der Verbindungen den Schritt des Addierens suminierter Terme jedes gruppierte Terms umfaßt und das anschließende Multiplizieren dessen Ergebnisses mit dem Multiplikator bj oder ck.

9. Verfahren nach Anspruch 1, das den Schritt des Speicherns der akkumulierten gruppierte Terme in einem Signalspeicher (32) umfaßt.

10. Verfahren zum Bestimmen des Produkts D zweier Elementen B und C eines endlichen Galois-Felds GF(2m), wobei in eine ganze Zahl größer als 1 ist, und das Feld Elemente A2i(0≤i< m) hat, die eine Normalenbasis bilden, wobei das Verfahren folgende Schritte aufweist:

c) Darstellen des Produkts D der Elemente B und C als einen Vektor von Bits di, wobei di der Koeffizient von A2i in der Normalenbasisdarstellung von D ist, wobei jedes der Bits di in der Form einer Summe von Produkten der Bits bj und ck (0≤j,k≤m) ausgedrückt ist;

d) Speichern der Bits bj in in aufeinanderfolgenden Zellen eines ersten Umlauf-Schieberegisters (112);

e) Speichern der Bits ci in in aufeinanderfolgenden Zellen eines zweiten Umlauf-Schieberegisters (114);

f) Auswählen mindestens einiger Produkte eines Bits dj und Gruppieren ähnlicher Bits bj oder ck, um gruppierte Terme der Form

zu schaffen;

g) Herstellen von Verbindungen von entsprechenden Zellen der Schieberegister zu jeder Zelle eines Akkumulator-Umlauf-Schieberegisters (120), um in jeder Akkumulatorzelle einen gruppierten Term eines Bits zu erzeugen, das den Vektor D darstellt, wobei die Verbindungen so hergestellt werden, daß ein erster gruppierter Term eines Bits in einer ersten Zelle (118) des Akkumulator-Schieberegisters (120) akkumuliert wird, und, beim wiederholten Übertragen der Inhalte der ersten Akkumulatorzeile über jede Akkumulatorzelle (118), die durch aufeinanderfolgende Rotationen der Umlauf- Schieberegistermhalte begleitet werden, aufeinanderfolgende gruppierte Terme des einen Bits erzeugt und in aufeinanderfolgenden Akkumulatorzellen akkumuliert werden;

h) Erzeugen aufeinanderfolgender gruppierter Terme des einen Bits durch Rotieren der Vektoren, die B und C in den ersten und zweiten Umlauf- Schieberegistern (112, 114) darstellen;

i) Akkumulieren Modulo 2 des anderen gruppierte Terms mit den vorher erzeugten gruppierten Termen, die in einer angrenzenden Akkumulatorzelle (118) erzeugt werden, um gruppierte Terme des einen Bits zu erzeugen;

j) Wiederholen des Akkumulationsschritts (in-1)-mal, wobei gruppierte Terme jedes Bits gleichzeitig in aufeinanderfolgenden Akkumulatorzellen akkumuliert werden, um jeden der in Bits des Vektors zu erzeugen, der gleichzeitig das Produkt D darstellt

wobei Schritt f weiterhin folgende Schritte aufweist:

paarweises Anordnen der Produkte, so daß ein Term jedes Paars die Form bjck und das andere Paar die Form bkcj hat; und

Auswählen eines jeden Paars zusammen mit irgendwelchen Paaren, die nicht paarweise angeordnet werden können, um die gruppierte Terme zu bilden; und wobei die anderen Produktterme jedes Paars durch miteinander Vertauschen der Bits der ersten und zweiten Umlauf-Schieberegister (112, 114) durch Durchführen des Schritts j und Wiederholen der Schritte h bis j erzeugt werden; und

Verzögern des Erzeugens der Produktterme, die während eines Wiederholens der Schritte h bis j nicht paarweise angeordnet werden können.

11. Verfahren nach Anspruch 10, wobei alle Produkte für das Gruppieren in gruppierte Terme ausgewählt werden.

12. Vorrichtung zum Bestimmen des Produkts zweier Elementen B und C des endlichen Galois-Felds GF(2m), wobei in eine ganze Zahl größer als 1 ist, und das Feld Elemente A2i (0≤i> m) hat, die eine Normalenbasis bilden, wobei die Vorrichtung folgendes aufweist:

a) ein erstes Umlauf-Schieberegister (12) mit in aufeinanderfolgenden Zellen, wobei jede davon ein Bit bi eines Vektors empfängt, der das Element B darstellt, wobei bi der Koeffizient von A2i in der Nomalenbasisdarstellung von B ist;

b) ein zweites Umlauf-Schieberegister (14) mit in aufeinanderfolgenden Zellen, wobei jede davon ein Bit ci eines Vektors empfängt, der das Element C darstellt, wobei ci der Koeffizient von A2i in der Nomalenbasisdarstellung von C ist;

c) einen Akkumulator-Umlauf-Schieberegister (20) mit in aufeinanderfolgenden Akkumulatorzellen (18), um aufeinanderfolgende gruppierte Terme jedes Bits di eines Vektors zu akkumulieren, der das Produkt D der Elemente B und C darstellt, wobei di der Koeffizient von A2i in der Normalenbasisdarstellung von D ist, und wobei die gruppierte Terme folgende Form haben:

d) eine Logikeinrichtung (36), die Verbindungen von jeweiligen Zellen der Umlauf-Schieberegister (12, 14) zu jeder Akkumulatorzelle (18) herstellt, um in jeder Akkumulatorzelle einen gruppierten Term eines Bits di eines Vektors zu erzeugen, der das Produkt D dastellt, wobei die Verbindungen so hergestellt werden, daß ein erster gruppierter Term einer der Bits in einer ersten Akkumulatorzelle akkumuliert wird und, beim wiederholten Übertragen der Inhalte der ersten Akkumulatorzelle über jede der Akkumulatorzellen (18), die von aufeinanderfolgenden Rotationen der Umlauf-Schieberegisterinhalte begleitet werden, aufeinanderfolgende gruppierte Terme des einen Bits in aufeinanderfolgenden Zellen erzeugt werden;

e) wobei die Akkumulatorzelle eine Akkumulatoreinrichtung (30) hat, um im GF(2) das Ausgangssignal der Logikeinrichtung (36) und die vorher erzeugten gruppierte Terme in einer angrenzenden Akkumulatorzelle zu summieren, und dadurch eine weitere Akkumulierung der gruppierte Terme zu schaffen;

f) eine Einrichtung (32), um die weitere Akkumulierung der gruppierten Terme zu speichern; und

g) eine Einrichtung, um die Inhalte der Umlauf-Schieberegister (12, 14, 20) über aufeinanderfolgende Zellen zu rotieren, wobei nach in Operationen der Summierungseinrichtung jede Speichereinrichtung Bits di des Vektors umfaßt der das Produkt D darstellt.

13. Vorrichtung nach Anspruch 12, wobei die Logikeinrichtung (36) Verbindungen herstellt, um gruppierte Terme zu erzeugen, die durch das Auswählen eines Paars von Produkttermen, die die Form bjck; bkcj haben, zusammen mit irgendwelchen Produkttermen gebildet werden, die nicht paarweise angeordnet werden können.

14. Vorrichtung nach Anspruch 13, die eine Einrichtung (150, 152) umfaßt um die Inhalte der ersten und zweiten Umlauf-Schieberegister (112, 114) nach in aufeinanderfolgenden Rotationen miteinander zu vertauschen.

15. Vorrichtung nach Anspruch 14, die eine Einrichtung (154) umfaßt, um selektiv die Logikeinrichtung (160) zu verzögern, die einer der Akkumulatorzellen (118) zugeordnet ist.

16. Vorrichtung nach Anspruch 15, wobei die ersten und zweiten Umlauf-Schieberegister (212, 214) segmentiert sind, und die Austauscheinrichtung (250, 252) so wirkt, die Inhalte entsprechender Segmente der ersten und zweiten Umlauf-Register (212, 214) in weniger als in Taktzyklen miteinander zu vertauschen.

17. Vorrichtung nach Anspruch 12, wobei die Logikeinrichtung (36) eine Addiereinrichtung umfaßt um die Inhalte der entsprechenden Zellen eines der Umlauf-Schieberegister zu addieren (Modulo 2), und eine Multipliziereinrichtung (28), um im GF(2) das Ausgangssignal der Addiereinrichtung mit den Inhalten einer der Zellen des anderen Umlauf-Schieberegisters zu multiplizieren.

18. Vorrichtung nach Anspruch 17, wobei die Speichervorrichtung (32) ein Speicherelement umfaßt das einen Eingang besitzt, der mit der Suinmierungseinrichtung (30) verbunden ist, und einen Ausgang, der mit einer angrenzenden Akkumulatorzelle (18) verbunden ist.