PatentDe  


Dokumentenidentifikation DE102006013989A1 27.09.2007
Titel Verfahren zur Reduktion eines Polynoms in einem binären finiten Feld
Anmelder IHP GmbH - Innovations for High Performance Microelectronics/Institut für innovative Mikroelektronik, 15236 Frankfurt, DE
Erfinder Langendörfer, Peter, Dr., 15230 Frankfurt, DE;
Peter, Steffen, 15232 Frankfurt, DE
Vertreter Eisenführ, Speiser & Partner, 10178 Berlin
DE-Anmeldedatum 22.03.2006
DE-Aktenzeichen 102006013989
Offenlegungstag 27.09.2007
Veröffentlichungstag im Patentblatt 27.09.2007
IPC-Hauptklasse G06F 17/10(2006.01)A, F, I, 20060322, B, H, DE
IPC-Nebenklasse G06F 17/50(2006.01)A, L, I, 20060322, B, H, DE   
Zusammenfassung Ein schnelles und Chipfläche sparendes Verfahren zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n-1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C"0(x) entspricht, wobei m entweder kleiner oder gleich n ist, beinhaltet ein Partitionieren des ersten Datenworts in ein binäres erstes Sub-Datenwort C0 und ein binäres zweites Sub-Datenwort C1, eine wiederholte Rechtsverschiebung von C1 zur Bildung von Summandentermin, bis jedem nicht verschwindenden Term eines Reduktionstrinomials oder -pentanomials, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist, ein Addieren der gebildeten Summandenterme zum ersten Sub-Datenwort zur Bildung eines Summendatenwortes, und eine erneute Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, bis das ermittelte Summendatenwort eine Länge von maximal m hat und somit das gesuchte zweite Datenwort bildet.

Beschreibung[de]

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Reduktion eines einem Polynom C(x) entsprechenden binären ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld, dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist.

Asymmetrische Verschlüsselungsverfahren wie RSA und die elliptische Kurvenkryptographie (Eliptic Curve Cryptography, ECC) werden verwendet, um einen sicheren Austausch von Schlüsseln für kryptographische Verfahren zu gewährleisten und um digitale Signaturen zu berechnen.

Die elliptische Kurvenkryptographie erfordert eine deutlich kürzere Schlüssellänge als RSA bei gleicher Sicherheitsstufe. Darüber hinaus kann man für die elliptische Kurvenkryptographie binäre endliche (finite) Galois-Felder GF(2m) nutzen, welche auf Grund ihrer algebraischen Eigenschaften sehr gut für Hardwareimplementierungen geeignet sind. Hierbei gibt m die Länge der Elemente eines jeweiligen Galois-Feldes an.

Die wichtigste Operation bei der Anwendung der elliptischen Kurvenkryptographie ist die Multiplikation großer Polynome. Nach einer Polynom-Multiplikation in einem finiten Feld sind die möglichen resultierenden Produkte bekanntlich länger als das größte Element des zu Grunde liegenden endlichen Feldes. Deshalb muss nach einer Polynom-Multiplikation eine so genannte Reduktion ausgeführt werden. In dieser Reduktion wird das lange Polynom des resultierenden Produktes auf einen („äquivalenten") Wert in den Grenzen des Feldes umgerechnet. Diese Operation ist nach jeder Polynom-Multiplikation notwendig.

Da die Multiplikation in der elliptischen Kurvenkryptographie eine Hauptoperation darstellt, ist entsprechend nicht nur die Multiplikationsoperation allein kritisch für die Leistungsfähigkeit (Performance) im Sinne von Schnelligkeit einer ECC-Implementierung, sondern auch die Reduktionsoperation.

Die Reduktion entspricht der Division mit Rest (Modulo-Operation) in ,normalen' endlichen Feldern. Diese soll anhand eines einfachen Beispiels erläutert werden. Das finite Feld GF(7) besteht aus den Elementen {0, 1, 2, 3, 4, 5, 6}. Eine Multiplikation von 5·4 ergibt 20, was größer als das größte mögliche Element in dem Feld ist. In dem Fall wird 20 durch 7 dividiert und der Rest dieser Division, nämlich 6, ist dann auch das Ergebnis der Multiplikation von 5·4 innerhalb des finiten Feldes (GF(7)).

Binäre finite Felder (GF(2m)) enthalten keine Zahlen, sondern Polynome. Ein Element dieser Felder ist A(x) = am–1·xm–1 + am_2·xm–2+ ... + a1·x + a0. Die Koeffizienten ai sind dabei entweder 0 oder 1. Eine wichtige Eigenschaft der Felder ist, dass bei der Addition und Subtraktion von Koeffizienten die XOR-Operation angewendet wird. Entsprechend ist 1 + 1 ≡ 1 – 1 ≡ 1 XOR 1 = 0.

Die maximale Länge eines Elementes des Feldes GF(2m) ist m. Die Multiplikation zweier Elemente (A(x)·B(x)) ergibt ein doppelt so langes Polynom C(x) = A(x)·B(x) = Cm_2·x2m–2 + ... + C0. Das Ergebnis hat also eine Länge von 2m – 1.

Man kann nun C(x) zerlegen in C(x) = C1(x)·xm + C0(x). C0(x) hat dabei die Länge, die der maximalen Länge der Polynome des Feldes entspricht. C1(x) ist der über die maximale Feldlänge überstehende Teil, der mittels des Reduktionsprozesses in C0 integriert werden muss.

Diese Reduktion kann man mittels einer kompletten Polynomdivision lösen, was sehr lange dauert. Ein solches Verfahren entspricht genau der oben am Beispiel in GF(7) erläuterten Modulo-Divison.

Es sind alternative, schnellere Möglichkeiten bekannt, diese Reduktion auszuführen. Ein oft genutzter Ansatz ist die multiplikative Reduktion. Multipliziert man C1(x) mit einem Reduktionspolynom R(x) und subtrahiert das entstehende Produkt von C(x), ist das Ergebnis kleiner als das Ausgangspolynom, aber in dem zu Grunde liegendem Feld äquivalent. Es gilt: C(x) ≡ C(x) – C1(x)·R(x). Wiederholt man diese Operation, kommt man auf immer weitere kleinere, aber im zu Grunde liegenden Feld äquivalente Werte. Wenn C1(x) die Länge Null erreicht hat, ist die Reduktion abgeschlossen.

Sind die Länge des Feldes und das Reduktionspolynom R(x) bekannt, kann man sehr effizient eine direkte Verdrahtung der Reduktionslogik realisieren. Dies ist zum Beispiel bekannt aus der Veröffentlichung Saqib, N. A., Rodriguez-Henriquez, F., and Diaz-Perez, A., „A parallel architecture for fast computation of elliptic curve scalar multiplication over GF(2m)", 18th International Parallel & Distributed Processing Symposium (IPDPS), Santa Fe, New Mexico, 26–30 Apr 2004.

Der Nachteil des aus dieser Veröffentlichung bekannten Systems ist jedoch gerade, dass es die Kenntnis der Länge des Feldes und des Reduktionspolynoms R(x) voraussetzt. Es wird daher angestrebt, einen ähnlich effizienten Weg zu finden, der diese Operationen für zur Laufzeit variable Felder mit variablen Reduktionspolynomen in Hardware möglich macht.

Eine aus dem Dokument Eberle, H., Gura, N., and Chang-Shantz, S., "A cryptograhpic processor for arbitrary elliptic curves over GF(2m)", IEEE 14th International Conference on Application-specific Systems, Architectures and Processors (ASAP), June 24–26, 2003, Seiten 444–454 schon bekannte Möglichkeit ist es, einen kompletten Multiplizierer für den Reduktionsschritt C(x) – C1(x)·R(x) zu nutzen. Eine zusätzliche komplette Multiplikation an dieser Stelle ist für die Schnelligkeitder ECC-Implementierung jedoch sehr negativ.

Aus der US2003/0208515 A1 (dort 32) ist es bekannt, bei der multiplikativen Reduktion zentriert ausgerichteter Polynome einen Berechnungsschritt C'(x) = C1(x)·(M – xm) + xn–m + C0(x) durchzuführen, bis der überstehende Teil des resultierenden Polynoms verschwindet. Hierbei kennzeichnet M ein geeignetes irreduzibles Polynom. Das Verfahren beinhaltet, das Reduktionspolynom ohne den Term xm um n – m Positionen nach links verschoben abzuspeichern und die Randpositionen links und rechts mit dem Wert Null aufzufüllen. Für eine 233-Bit-Implementierung (m = 233) mit M = x233 + x74 + 1 auf einer 256-Bit-Hardware (n = 256), ist (M – xm)·xn–m = (x74 + 1)·x256–233 = x97 + x23. Dieses für den gesamten Reduktionsprozess wiederverwendbare Polynom wird mit dem überstehenden Teil C1(x) multipliziert und zu C0(x) addiert (XOR), bis C1(x) Null ist. Es sind daher wiederholte komplette Polynommultiplikationen notwendig. Abschließend wird das so berechnete äquivalente, reduzierte Polynom durch eine Multiplikation mit xm nach links verschoben.

Eine in der US2003/0208515 A1 beschriebene Variante (33) sieht vor, statt des ursprünglichen Polynoms ein teilweise reduziertes Polynom für die Berechnung von Punktmultiplikationsoperationen zu verwenden, um erst danach abschließend die Reduktion entsprechend dem eben beschriebenen Verfahren vorzunehmen. Auf diese Weise können mit einer Implementierung Operationen in Feldern GF(2m) mit unterschiedlichen Werten m vorgenommen werden.

Nachteil der in diesem Dokument beschriebenen Verfahren ist jedoch, dass wiederholte vollständige Polynom-Multiplikationen zur Reduktion durchgeführt werden müssen. Für die Reduktion wird eine Vielzahl von Taktzyklen benötigt.

Das der vorliegenden Erfindung zugrunde liegende technische Problem ist es daher, ein Verfahren und eine Vorrichtung zur Reduktion eines Polynomproduktes anzugeben, das eine in besonders wenigen Taktzyklen durchführbare Reduktion in Feldern unterschiedlicher Länge und mit unterschiedlichen Reduktionspolynomen ermöglicht.

Die Erfindung spiegelt sich in drei Aspekten wieder, wovon zwei Aspekte Verfahren betreffen und ein dritter Aspekt eine Vorrichtung.

Gemäß einem ersten Aspekt der Erfindung wird ein Verfahren zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m bereitgestellt. Das zweite Datenwort entspricht in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x), wobei m entweder kleiner oder gleich n ist. Das Verfahren weist die folgenden Schritten auf:

  • – Bereitstellen eines Reduktionspolynoms R(x), das ein Trinomial oder ein Pentanomial bildet;
  • – Partitionieren des ersten Datenworts in ein binäres erstes Sub-Datenwort C0 und ein binäres zweites Sub-Datenwort C1, deren entsprechende Polynome C0(x) und C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllen, und Abgreifen des zweiten Sub-Datenwortes zur Bildung eines ersten Summandenterms;
  • – Rechtsverschieben des zweiten Sub-Datenworts zur Bildung eines zweiten Summandenterms, und Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme, bis jedem nicht verschwindenden Term des Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist, indem die Schrittweite einer jeweiligen Rechtsverschiebung gleich der Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynoms ist;
  • – Addieren der gebildeten Summandenterme zum ersten Sub-Datenwort zur Bildung eines Summendatenwortes;
  • – wenn das so ermittelte Summendatenwort eine Länge größer als m hat, Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, bis das so ermittelte Summendatenwort eine Länge von maximal m hat und somit das zweite Datenwort bildet.

Das erfindungsgemäße Verfahren zur Reduktion eines ersten Datenwortes ermöglicht in einer Hardwareimplementierung eine besonders schnelle Durchführung in wenigen Taktzyklen. In einem bevorzugten Ausführungsbeispiel, das weiter unten beschrieben wird, gelingt die Reduktion sogar in nur einem Taktzyklus.

Das erfindungsgemäße Verfahren beinhaltet verschiedene Maßnahmen, die zu dieser Beschleunigung der Reduktionsoperation gegenüber bekannten Verfahren führen.

Zunächst wird erfindungsgemäß ein Reduktionspolynom R(x) bereitgestellt, das ein Trinomial oder ein Pentanomial bildet. Trinomiale sind Polynome mit drei besetzten Termen. Pentanomiale sind Polynome mit fünf besetzten Termen. Mit dieser Maßnahme macht sich das erfindungsgemäße Verfahren die Eigenschaften derjenigen binären finiten Felder zunutze, die in der elliptischen Kurvenkryptographie in der Praxis zum Einsatz kommen, weil sie von Standardisierungsgremien wie beispielsweise dem amerikanischen National Institut of Standards and Technology (NIST) empfohlen werden.

Da zusätzlich die zweithöchste besetzte Stelle der empfohlenen Reduktionspolynomen in aller Regel kleiner als m/2 ist, kann eine komplette Reduktion nach zwei aufeinanderfolgenden Multiplikationen vollendet werden.

Weiterhin werden bei dem erfindungsgemäßen Verfahren Multiplikationsschritte durch flexible Verschiebeoperationen realisiert. Dies führt zu einer wesentlichen Vereinfachung der erforderlichen Multiplikationsschritte und gleichzeitig zu einer flexiblen Hardwareimplementierung, die es erlaubt, Produkte von Datenworten mit unterschiedlicher (in einem jeweiligen Produkt jedoch gleicher) Länge zu reduzieren.

Mathematisch kann das erfindungsgemäße Reduktionsverfahren wie folgt beschrieben werden. Ausgehend von einem Polynom der Form C(x) = C1(x)·xm + C0(x)(1)

Wird in einer ersten Iteration der Reduktionsoperation die folgende Differenz berechnet: C'(x) = C(x) – C1(x)·R(x)(2)

Nachfolgend wird erläutert, wie diese Differenz erfindungsgemäß besonders einfach berechnet wird. Gleichung (2) lässt sich auch darstellen als C'(x) = C1(x)·xm + C0(x) – (C1(x)·xm + C1(x)xm/xS3 + C1(x)·xm/xS2 + C1(x)·xm/xS1 + C1(x)·xm/xS0)(3)

Gleichung (3) ist äquivalent mit C'(x) = C0(x) – (C1(x)·xm/xS3 + C1(x)·xm/xS2 + C1(x)·xm/xS1 + C1(x)·xm/xS0(4)

Hierbei entsprechen die Divisionen durch die Terme xS3, xS2, xS1, xS0 Rechtsverschiebeoperationen um eine Schrittweite, die der Ordnung der nicht verschwindenden Terme xS3, xS2, xS1, und xS0 des Reduktionspolynoms entspricht.

In zahlreichen Fällen ist nach dieser erstmaligen Anwendung des Reduktionspolynoms noch keine vollständige Reduktion erzielt. Es erfolgt daher ein nächster Iterationsschritt der auf einer Darstellung des Zwischenergebnisses C'(x) in der Form: C'(x) = C1'(x)·xm + C0'(x)(5) basiert. Die maximale Länge des Zwischenergebnisses C1'(x) ist m – s3 – 1. Die erneute Anwendung des Reduktionspolynoms erfolgt gemäß der Gleichung C''(x) = C'(x) – C1'(x)·R(x) = C1''(x)·xm + C0''(x)(6)

Dabei ist, falls m < 2·s3, die Ordnung des Terms C1''(x) Null. Die Reduktion benötigt daher in diesem Fall nur zwei Iterationen.

Der im erfindungsgemäßen Verfahren enthaltene Schritt des Partitionierens des ersten Datenworts beinhaltet nicht notwendiger Weise eine physikalische Aufspaltung des ersten Datenworts in zwei getrennte Sub-Datenworte oder gar ihre getrennte Abspeicherung in Speichern oder Registern. Wesentlich für das Partitionieren ist allein, dass im weiteren Verlauf des Verfahrens die Sub-Datenworte getrennt verwendet werden. Hierzu kann in einer vorteilhaften Hardware-Implementierung jedoch schon das getrennte Verdrahten der Bitpositionen der Sub-Datenworte in einem Register, welches das vollständige erste Datenwort enthält, mit jeweils nachgeschalteten Operator-Implementierungen genügen.

Unter der Länge eines gebildeten Summandendatenwortes ist die höchstwertige Position zu verstehen, deren Wert ungleich Null ist. Wenn also ein Summanden-Datenwort eine Länge von größer als m hat, bedeutet, dass auf Positionen > m Werte ungleich Null vorhanden sind.

Der im erfindungsgemäßen Verfahren enthaltene Schritt des Rechtsverschiebens des zweiten Sub-Datenworts zur Bildung eines zweiten Summandenterms, und die Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme, ist so zu verstehen, dass der zweite Summandenterm im Ergebnis gegenüber dem zweiten Sub-Datenwort (C1) in seiner ursprünglichen Position im ersten Datenwort (C0 + C1) nach rechts verschoben verwendet wird. Dies kann nicht nur durch eine tatsächliche Rechtsverschiebung, sondern beispielsweise auch auf dem Wege erreicht werden, dass das zweite Sub-Datenwort zunächst rechtsbündig abgegriffen und dann um eine jeweils entsprechend anzupassende Schrittweite nach links verschoben wird. Offensichtlich ist das Ergebnis jedoch dasselbe.

Gemäß einem zweiten Aspekt der vorliegenden Erfindung wird ein Verfahren zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m bereitgestellt, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist, mit den Schritten:

  • – Bereitstellen eines Reduktionspolynoms R(x), das ein Trinomial oder ein Pentanomial bildet;
  • – Partitionieren des ersten Datenworts in ein binäres erstes Sub-Datenwort C0 und ein binäres zweites Sub-Datenwort C1, deren entsprechende Polynome C0(x) und C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllen, und Abgreifen des zweiten Sub-Datenwortes zur Bildung eines ersten Summandenterms;
  • – Rechtsverschieben des zweiten Sub-Datenworts zur Bildung eines zweiten Summandenterms, und Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme, bis jedem nicht verschwindenden Term des Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist, indem die Schrittweite einer jeweiligen Rechtsverschiebung gleich der Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynoms ist;
  • – Addieren der gebildeten Summandenterme, mit Ausnahme des ersten Summandenterms, zum ersten Datenwort (, nachfolgend auch als erster Addierschritt bezeichnet);
  • – wenn das so ermittelte Summendatenwort eine Länge größer als m hat, Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, bis das so ermittelte Summendatenwort eine Länge von maximal m hat;
  • – Addieren des ersten Summandenterms und, im genannten Falle einer Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, jedes weiteren zwischenzeitlich ermittelten zweiten Sub-Datenworts zum zuletzt ermittelten Summendatenwort zur Bildung des zweiten Datenworts (, nachfolgend auch als zweiter Addierschritt bezeichnet).

Das Verfahren des zweiten Aspekts der Erfindung unterscheidet sich von dem des ersten Aspekts der Erfindung darin, dass die jeweiligen ersten Summandenterme, d. h. die jeweiligen zweiten Sub-Datenworte, erst abschließend, nach Durchführung aller erforderlichen Iterationen zur Reduktion zum zuletzt ermittelten Summendatenwort addiert werden, um das vollständig reduzierte zweite Datenwort zu bilden.

Der zusätzliche Vorteil des Verfahrens des zweiten Aspekts der Erfindung liegt darin, dass auf diese Weise noch kompaktere Hardware-Implementierungen möglich werden. Denn in einer erfindungsgemäßen Reduktionsvorrichtung muss eine darin vorgesehene Schiebeeinheit zur Durchführung dieses Verfahrens nur noch maximal drei Rechtsschiebe-Operationen durchführen. Dies spart Chipfläche.

Die Verfahrensführung dieses Aspekts der Erfindung beruht auf der Einsicht, dass alle irreduziblen Polynome die Struktur: R(x) = xm + ... + 1(7) haben. Die Terme xm und 1 sind daher Teil jedes Reduktionspolynoms R(x). Da die niedrigste Ordnung des Reduktionspolynoms immer Null (x0 = 1) ist, und s0 der Differenz von m und Null entspricht, ist s0 immer äquivalent zu m. Daher wird für diesen Term tatsächlich keine Rechtsverschiebung benötigt und kann die erforderliche Addition im Anschluss an die Iterationen erfolgen.

Weitere Vorteile dieses Verfahrens ergeben sich aus der nachfolgenden Beschreibung von Ausführungsbeispielen, die sich jedoch ebenso auf das Verfahren gemäß dem ersten Aspekt der Erfindung beziehen. Die Ausführungsbeispiele sind miteinander kombinierbar, soweit nicht ausdrücklich beschrieben ist, dass es sich um zueinander alternative Ausführungsbeispiele handelt.

Gemäß einem bevorzugten Ausführungsbeispiel der erfindungsgemäßen Verfahren, bei dem das erste Datenwort eine Länge von weniger als 2n – 1 hat, erfolgt vor der Rechtsschiebeoperation ein zusätzlicher erster Justierschritt. Der erste Justierschritt beinhaltet ein Linksverschieben des ersten Datenworts um eine Auffüllschrittweite und ein beiderseitiges Anfügen einer der Auffüllschrittweite entsprechenden Anzahl Nullen an das erste Datenwort. Die Linksverschiebung und das Anfügen der Nullen erfolgt derart, dass die Länge des so modifizierten ersten Datenworts 2n – 1 beträgt und dass im modifizierten ersten Datenwort diejenigen Terme des dem ersten Datenwort entsprechenden Polynoms C(x), die eine Ordnung größer als m haben, an denselben Bitpositionen angeordnet sind wie wenn das erste Datenwort schon anfänglich die Länge 2n – 1 gehabt hätte.

Auf diese Weise ist es möglich, auch kleinere Datenworte in ein und derselben Hardware-Implementierung zu reduzieren. Damit wird die Flexibilität einer Hardware-Implementierung erhöht.

Vorzugsweise wird bei dieser Verfahrensführung ein zweiter Justierschritt durchgeführt, der beim Verfahren gemäß dem ersten Aspekt der Erfindung insbesondere nach dem Addieren der gebildeten Summandenterme zum ersten Sub-Datenwort zur Bildung des Summanden-Datenwortes im letzten Iterationsschritt durchgeführt wird. Beim Verfahren gemäß dem zweiten Aspekt der Erfindung wird der zweite Justierschritt insbesondere vordem zweiten Addierschritt durchgeführt.

Bei einer besonders bevorzugten Ausführungsform der erfindungsgemäßen Verfahren wird das irreduzible Polynom allein durch die Potenzen der nicht verschwindenden Terme des Reduktionspolynoms, die nicht der Term xm sind, repräsentiert. Das bedeutet, dass das Reduktionspolynom nicht in der vollen Länge eines Datenwortes gespeichert wird, sondern nur in der Form (s1, s2, s3). Die Verfahrensführung wird dadurch weiter vereinfacht und beschleunigt. Der zusätzliche Parameter der bekannten maximalen Länge m von Datenworten des binären finiten Feldes, der zu einer eindeutigen Kenntnis des irreduziblen Polynoms benötigt wird, kann, muss jedoch nicht zusammen mit den Parametern (s1, s2, s3) abgespeichert werden, da er auch anderweitig vorhanden ist.

Ein dritter Aspekt der Erfindung betrifft eine Vorrichtung zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist, mit:

  • – einem Speicher, der eine Repräsentation mindestens eines Reduktionspolynoms R(x) enthält, das ein Trinomial oder ein Pentanomial bildet;
  • – einer Selektionseinheit, die ausgebildet ist, ein binäres Sub-Datenwort aus dem ersten Datenwort zu abzugreifen, dessen entsprechendes Polynom C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllt und das einen ersten Summandenterm bildet;
  • – einer Schiebeeinheit, die mit der Selektionseinheit verbunden und ausgebildet ist, das Sub-Datenwort zur Bildung eines zweiten oder weiterer Summandenterme um eine jeweils vorbestimmte Schrittweite nach rechts zu verschieben und die gebildeten Summandenterme auszugeben;
  • – einer Addiereinheit, die mit der Schiebeeinheit verbunden und ausgebildet ist, einen jeweiligen Summandenterm sowie die von der Schiebeeinheit ausgegebenen Summanden zum ersten Datenwort zu addieren; und
  • – einer Steuereinheit, die ausgebildet ist,

    – die Schrittweite einer jeweiligen, von der Schiebeeinheit auszuführenden Rechtsverschiebung zur Bildung eines Summandenterms als Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynoms zu bestimmen,

    – die Schiebeeinheit zur wiederholten Durchführung des Rechtsverschiebungsschritts für eine Bildung weiterer Summandenterme mit jeweils neu bestimmter Schrittweite zu instruieren, bis jedem nicht verschwindenden Term eines jeweils vorgegebenen Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist,

    – die Berechnungseinheit, die Schiebeeinheit und die Addiereinheit erforderlichenfalls erneut zu aktivieren, bis ein ermitteltes Summendatenwort eine Länge von maximal m hat und somit das zweite Datenwort bildet.

Die erfindungsgemäße Reduktionsvorrichtung ermöglicht eine schnelle Reduktion von Datenwörtern. Sie bietet die Voraussetzung für eine hohe Flexibilität, die in bevorzugten Ausführungsbeispielen die Reduktion von Datenwörtern unterschiedlicher Länge ermöglicht.

Gegenüber bekannten Vorrichtungen gelingt dies mit einer besonders einfachen Struktur, die ohne jegliche dezidierte Multiplikationseinheit auskommt. Durch entsprechende Steuerung der flexiblen Schiebeeinheit, die ein selektiertes Sub-Datenwort um eine jeweils vorbestimmte Schrittweite nach rechts verschiebt, kann in Zusammenwirkung mit einer Addiereinheit eine multiplikative Reduktion durch nur wenige einfache Schiebe- und Addieroperationen ausgeführt werden. Die Tatsache, dass die Steuereinheit ausgebildet ist, die Berechnungseinheit, die Schiebeeinheit und die Addiereinheit erforderlichenfalls erneut zu aktivieren, bis ein ermitteltes Summendatenwort eine Länge von maximal m hat und somit das zweite Datenwort bildet, ist nicht notwendigerweise mit einem Prüfschritt verbunden, in dem die Länge eines teilreduzierten Datenwortes ermittelt wird. In einer bevorzugten Implementierung findet vielmehr keine Kontrolle auf die Länge statt. Dabei macht man sich zunutze, dass ein geeignet ausgewähltes Reduktionspolynom gewährleistet, dass die Reduktion nach 2 Iterationen komplett ist.

Nachfolgend werden Ausführungsbeispiele der erfindungsgemäßen Vorrichtung beschrieben. Die Ausführungsbeispiele können miteinander kombiniert werden, soweit sie nicht ausdrücklich als alternative Ausführungsbeispiele beschrieben sind.

Bei einem bevorzugten Ausführungsbeispiel der Reduzierungsvorrichtung ist die Steuereinheit ausgebildet, die Addiereinheit im Falle einer Wiederholung der Verfahrensschritte ab dem Schritt des Ermittelns eines binären Sub-Datenworts, zu instruieren, die jeweils gebildeten Summandenterme mit Ausnahme des ersten Summandenterms zum jeweiligen ersten Datenwort zu addieren, und nach einer Feststellung, dass ein ermitteltes Summendatenwort eine Länge hat, die nicht größer als m ist, zur Bildung des zweiten Datenworts jeden zwischenzeitlich ermittelten ersten Summandenterm zum ermittelten Summendatenwort zu addieren.

Dieses Ausführungsbeispiel realisiert das Verfahren des zweiten Aspekts der Erfindung.

Ein weiteres bevorzugtes Ausführungsbeispiel enthält eine erste und eine zweite Justiereinheit. Die erste Justiereinheit ist ausgebildet, ein eingehendes erstes Datenwort mit einer Länge von weniger als 2n – 1 vor der Rechtsschiebeoperation um eine Auffüllschrittweite nach links zu verschieben und beiderseits des ersten Datenwortes eine der Auffüllschrittweite entsprechende Anzahl Nullen an das erste Datenwort anzufügen, derart, dass die Länge des so modifizierten ersten Datenworts 2n – 1 beträgt und dass im modifizierten ersten Datenwort diejenigen Terme des dem ersten Datenwort entsprechenden Polynoms C(x), die eine Ordnung größer als m haben, an denselben Bitpositionen angeordnet sind wie wenn das erste Datenwort schon anfänglich die Länge 2n – 1 gehabt hätte.

Die zweite Justiereinheit ist ausgebildet, das ermittelte Summendatenwort der Länge von maximal m um die Auffüllschrittweite nach rechts zu verschieben und die anfänglich angefügten Nullen zu entfernen.

Zur Beschleunigung der Reduktion enthält die Schiebeeinheit vorzugsweise eine Anzahl parallel geschalteter Rechtsschieber, denen das Sub-Datenwort zugeführt ist.

Alternativ enthält die Schiebeeinheit genau einen Rechtsschieber, und die Steuereinheit ist ausgebildet, die Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme durch zusätzliches Rechtsschieben des zuletzt vom Rechtsschieber ausgegebenen Summandenterms um eine jeweilige Differenzschrittweite durchzuführen, wobei die jeweilige Differenzschrittweite die Differenz zwischen den Rechtsverschiebungen aufeinander folgender Summandenterme jeweils gegenüber dem ersten Summandenterm ist.

Nachfolgend werden die Erfindung und verschiedene Ausführungsbeispiele anhand der beiliegenden Figuren näher erläutert. Es zeigen

1 ein Diagramm zur Erläuterung einer einfachen Polynomreduktion;

2a) und 2b) zwei alternative Ausführungsformen des erfindungsgemäßen Verfahrens;

3 ein weiteres alternatives Ausführungsbeispiel des erfindungsgemäßen Verfahrens;

4 ein Blockdiagramm eines Ausführungsbeispiels eines flexiblen Reduzierers;

5 ein Blockdiagramm zur Erläuterung einer alternativen Struktur einer Reduziereinheit für den flexiblen Reduzierer der 4.

1 zeigt ein Diagramm zur Erläuterung einer einfachen Polynomreduktion. Das Grundproblem der Polynomreduktion in finiten binären Feldern beruht darauf, dass eine Polynommultiplikation ein erstes Datenwort erzeugt, das eine größere Länge hat als die maximale Länge m des Feldes. Anstelle von der Feldlänge spricht man auch vom Feldgrad. Um das Polynomprodukt in das binäre finite Feld einzupassen, muss es reduziert werden. Der Reduktionsprozess entspricht der Bestimmung eines zum anfänglichen Datenwort äquivalenten Datenwort im binären finiten Feld GF(2m). Die Operation entspricht der bekannten Modulo-Operation in Primfeldern.

Ein naheliegender Reduktionsansatz besteht demnach darin, dass anfängliche erste Datenwort durch das irreduzieble Polynom zu dividieren. Der Rest dieser Division ist das reduzierte Datenwort, das hier auch als zweites Datenwort bezeichnet wird.

Eine alternative Methode zur Reduktion bildet die multiplikative Reduktion. Bei diesem Verfahren wird der überhängende Teil des Datenwortes, der hier auch als zweites Sub-Datenwort bezeichnet wird, mit dem Reduktionspolynom multipliziert und vom anfänglichen ersten Datenwort subtrahiert. Die Subtraktion entspricht bekanntlich wie die Addition einer XOR-Verknüpfung.

Im in 1 dargestellten Beispiel beträgt die maximale Feldlänge des verwendeten binären finiten Feldes m = 3. Nach einem ersten Iterationsschritt entsteht ein Summanden-Datenwort C'(x), das sich wiederum als C1'(x)·xm + C0'(x) darstellen lässt. Das den überhängenden Teil bildende zweite Sub-Datenwort C1' konnte also gegenüber dem anfänglichen ersten Datenwort verkleinert werden. Eine weitere Reduktion ist jedoch noch erforderlich, die durch Multiplikation des zweiten Sub-Datenworts C1'(x) mit dem Reduktionspolynom R bewerkstelligt wird. Wie im linken Teil des Diagramms der 1 ersichtlich ist, ist nach diesen zwei Reduktionsschritten das anfängliche erste Datenwort 110111 durch zweifache Multiplikation des jeweils überhängenden zweiten Sub-Datenwortes mit dem irreduziblen Polynom 1011 auf das äquivalente Datenwort 110 im Feld GF(23) reduziert worden.

Es wird betont, dass das Beispiel der 1 nur zur Veranschaulichung des Prinzips dient. Das verwendete Zahlenbeispiel ist zur Erläuterung gewählt und insofern für den Anwendungsfall uncharakteristisch als die Länge des ersten Datenwortes hier 6 ist. Das entspricht 2·m, während nach einer Multiplikation ist die Länge des zu reduzierenden Datenworts nicht länger als 2·m – 1 ist.

Die 2a) und 2b) zeigen zwei alternative Ausführungsformen des erfindungsgemäßen Verfahrens. Die in den 2a) und 2b) dargestellte Lösung basiert auf den Eigenschaften der finiten binären Felder, die beispielsweise von der NIST für die elliptische Kurvenkryptographie empfohlen sind. Da alle zusätzlich empfohlenen Reduktionspolynome entweder Trinomiale oder Pentanomiale sind, kann man eine Multiplikation durch 3 oder 5 aufsummierte Schiebeoperationen ersetzen. Da zusätzlich die zweithöchste besetzte Stelle in den Reduktionspolynomen in der Regel kleiner als m/2 ist, ist die komplette Reduktion nach zwei aufeinanderfolgenden Multiplikationen vollendet. Der entsprechende Reduktionsprozess wird anhand zweier Fälle in den 2a) und 2b) verdeutlicht.

2a) zeigt das erfindungsgemäße Verfahren für den Fall, dass die Länge des in Hardware zulässigen Feldes genau der Länge des Feldes entspricht (m = n), auf dem eine vorangegangene Polynommultiplikation durchgeführt wurde. Ein erstes, nicht reduziertes Datenwort 300 der Länge 2n – 1 ist in zwei Sub-Datenworte 302 und 304 partitionierbar. Ein erstes Sub-Datenwort C0 reicht von niedrigsten Bitposition bis zur Länge m des binären finiten Felds GF(2m). Ein zweites Sub-Datenwort C1 304 entspricht dem überhängenden Teil des ersten Datenworts 300 und hat die Länge 2n – m – 1.

Die erwähnte Partitionierung des ersten Datenworts 300 in die zwei Sub-Datenwörter 302 und 304 benötigt keinen tatsächlichen Zerlegungsschritt. Es genügt, die Bits der entsprechenden Sub-Datenwörter für die nachfolgenden Rechnungsschritte von ihren jeweiligen Positionen separat abzugreifen.

Das zweite Sub-Datenwort 304 wird anschließend in verschiedenen Kopien um unterschiedliche Schrittweiten nach rechts verschoben. Dies ist in 2a) durch die fünf Kopien 306 bis 314 des zweiten Sub-Datenwortes 304 schematisch symbolisiert. Jede Kopie ist um eine für sie aufgrund des verwendeten Reduktionspolynoms vorbestimmte Schrittweite nach rechts verschoben. Die Anzahl der tatsächlich verschobenen Summandenterme 308 bis 314 entspricht der Anzahl der nicht verschwindenden Terme vorbekannten Reduktionspolynoms R(x), die nicht den Term xm bilden. Die Kopie 306 muss dagegen nicht verschoben werden. Die Schrittweite einer jeweiligen Rechtsverschiebung ist gleich der Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynoms.

Die Ordnung eines als Beispiel angenommen Terms x74 eines Reduktionspolynoms R(x) ist 74. Im Feld GF(2233) wird für diesen Term ein Summandenterm aus dem zweiten Sub-Datenwort 304 erzeugt, der um 159 Positionen nach rechts verschoben ist. Die in 2 angezeigten Parameter s0 bis s3 repräsentieren die jeweilige Schrittweite einer jeweiligen Rechtsverschiebung.

Durch anschließendes Addieren der gebildeten Summandenterme 306 bis 314 zum ersten Sub-Datenwort 302 (C0) entsteht ein Zwischenergebnis C'(x) = C'0(x) + C'1(x), das als Block 320 dargestellt ist und zwei entsprechende Sub-Datenworte 322 und 324 enthält. Ein schraffiert gekennzeichneter Bereich 324.1 enthält aufgrund der bis hier durchgeführten Verfahrensschritte lediglich Nullen.

Da jedoch das so gebildete Summendatenwort 320 noch nicht vollständig reduziert ist, werden die Schritte des Abgreifens des zweiten Sub-Datenwortes 324 und die Rechtsverschiebung des zweiten Sub-Datenwortes 324 entsprechend den Parametern s0 bis s3 des irreduziblen Polynoms R, wie oben erläutert, erneut durchgeführt. Entsprechende rechtsverschobene Kopien 326 bis 334 des zweiten Sub-Datenwortes 324 sind in 2a) dargestellt.

Es versteht sich, dass anstelle der parallelen Verschiebung von Kopien auch serielle Verschiebeschritte an ein und demselben Sub-Datenwort vorgenommen werden können. Schneller ist jedoch die parallele Erzeugung der rechtsverschobenen Kopien mit verschiedenen, parallel geschalteten Rechtsschiebern.

Da der Term mit der zweihöchsten gesetzten Ordnung im Reduktionspolynom weniger als die Hälfte des maximalen Grades m beträgt, sind lediglich zwei aufeinanderfolgende Iterationsschritte für eine vollständige Reduktion erforderlich.

Das nach erneut durchgeführter Addition der Summandenterme 326 bis 334 zum ersten Sub-Datenwort 322 entstehende Summendatenwort 336 hat daher lediglich die maximale Länge m. Es bildet das gesuchte reduzierte, zweite Datenwort.

2b) zeigt ein dem Verfahren der 2a) entsprechendes Verfahren für den Fall, dass die maximale Feldlänge der eingehenden Datenworte kleiner ist als die zulässige Datenwortbreite n des erfindungsgemäßen Reduzierers.

Zusätzlich zu den in 1 dargestellten Verfahrensschritten, wird anfänglich ein erster Justierschritt durchgeführt, mit dem erreicht wird, dass die Länge des so modifizierten ersten Datenwortes gleich der hardwaremäßig unterstützten Länge 2n – 1 beträgt und dass im so modifizierten ersten Datenwort 350 diejenigen Terme des dem ersten Datenwort entsprechenden Polynom C(x), die eine Ordnung größer als m haben, an denselben Bitpositionen angeordnet sind, wie wenn das erste Datenwort 350 schon anfänglich die Länge 2n – 1 gehabt hätte. Im Ergebnis entspricht die so durchgeführte Linksverschiebung im ersten Justierschritt eine Verschiebung um (n – m), wobei n die größte hardwaremäßig unterstützte Länge eines Datenwortes bedeutet. Am Eingang des Reduzierers ist die unterstützte Wortbreite dementsprechend 2n – 1.

Die Schrittweite dieser Linksverschiebung im ersten Justierschritt wird auf Auffüllschrittweite bezeichnet, weil die auf diese Weise entstehenden Bitpositionen in den Feldern 352.1 und 354.1 am Rande der Sub-Datenwörter 352 und 354 mit Nullen aufgefüllt werden.

Mit diesem so modifizierten ersten Datenwort 350 wird anschließend das Reduzierverfahren wie in 2a) beschrieben. Dabei werden in einem ersten Iterationsschritt Summandenterme 356 bis 364 gebildet und zum ersten Sub-Datenwort 352 addiert. Das auf diese Weise erhaltene Summen-Datenwort 370 enthält in seinem überhängenden zweiten Sub-Datenwort 374 einen Block 374.1, der vollständig aus Nullen besteht. Die verbleibenden nicht verschwindenden Bitpositionen des überhängenden zweiten Sub-Datenwortes 374 werden in einem zweiten Iterationsschritt durch Bildung von Summandentermen 376 bis 384 und Addition zum ersten Sub-Datenwort 372 beseitigt, wodurch ein Summen-Datenwort 386 entsteht. Dieses wird in einem abschließenden zweiten Justierschritt um die gleiche Anzahl Bitpositionen, also um die Auffüllschrittweite nach rechts verschoben, um den rechtsseitigen Block 386.1, der anfänglich durch Anfügung von Nullen entstanden war, zu beseitigen. Der verbleibende Block 386.2 entspricht dem gesuchten zweiten Datenwort, das zum ersten Datenwort äquivalent ist.

3 zeigt einen alternativen Verfahrensfluss für den Fall m < n, der auch der Verfahrensführung der 2b) zugrunde lag. Die Darstellung in 3 ist in vier Hauptverfahrensblöcke S400, S410, S420 und S430 unterteilt.

Der Verfahrensblock S400 umfasst einen ersten Justierschritt S402, bei dem ein eingehendes Datenwort 450, dessen Länge 2m – 1 kleiner als die hardwaremäßig unterstützte Länge 2n – 1 ist, um eine Auffüllschrittweite sf nach links verschoben wird. Das so modifizierte Datenwort 450' enthält ein erstes Sub-Datenwort 452 und ein zweites Sub-Datenwort 454. Diese sind in 4 wie gehabt auch mit C0 und C1 gekennzeichnet. Diese Bezeichnung umfasst auch die links- und rechtsseitig vorhandenen Blöcke 452.1 und 454.1, die mit Nullen gefüllt sind.

Das zweite Datenwort 454 wird anschließend in drei parallel durchgeführten Rechtsschiebeschritten um die Schrittweiten S1, S2 und S3 nach rechts verschoben erfolgt in entsprechenden Schritten S412, S414 und S416. Anschließend werden die so gebildeten Summandenterme in einem Addierschritt S418 zum ersten Sub-Datenwort 452 addiert.

Zu beachten ist, dass im Verfahren der 2 die Summandenterme zu C addiert (300) wurden. In der Verfahrensführung der 2 werden sie nur noch zu C0 addiert (452). Dadurch entfällt (unter Rückgriff auf die verwendeten Bezugszeichen) im vorliegenden Ausführungsbeispiel die Operation (304) + (306), die stets in Null resultiert. In der vorliegenden Verfahrensführung werden daher insgesamt nur vier Terme zum ersten Sub-Datenwort hinzu addiert.

Nach der so erfolgten Teilreduktion wird das am Ausgang des Addierschritts 418 bereitstehende Summendatenwort 470 im nächsten Iterationsschritt S420 einer entsprechenden Schrittfolge S422 bis S428 unterzogen, wie im Zusammenhang mit 2b) ausführlich wurde.

Das am Ausgang des Addierschritt S428 bereitstehende Summen-Datenwort 486 wird in einem anschließenden zweiten Justierschritt S432 um die Auffüllschrittweite sf nach rechts verschoben, wodurch ein entsprechend modifiziertes Summen-Datenwort 488 gebildet wird. Zu diesem werden anschließend in einem weiteren Addierschritt S434 die zweiten Sub-Datenwörter 454 und 474 addiert, wodurch am Ausgang des Addierschritts 434 das gesuchte reduzierte zweite Datenwort 490 vorliegt.

Der Vorteil dieser Verfahrensführung liegt darin, dass in jedem Iterationsschritt ein Rechtsschiebeschritt eingespart wird. Dies bedeutet, dass in einer entsprechenden Hardwareimplementierung ein Rechtsschieber weniger benötigt wird, was einerseits zu einer zusätzlichen Verfahrensbeschleunigung und andererseits zu einer Flächenersparnis führt.

4 zeigt ein Blockdiagramm eines Reduzierers, der zur Implementierung der Verfahrensführung entsprechend den 2a) und 2b) ausgebildet ist. Der Reduzierer 500 ist einem Multiplizierer M nachgeschaltet, an dessen Ausgang Datenworte mit der Länge 2m – 1 anliegen. Ein solches Datenwort, dass das Produkt einer im Multiplizierer M durchgeführten Multiplikation bildet, wird einer ersten Justiereinheit 502 zugeführt, die eine Linksverschiebung entsprechend dem Schritt S402 aus 3 ausführt. Hierbei wird die erste Justiereinheit 502 von einer Steuereinheit 504 angesteuert, die den Parameter m, also die Feldgrößer der Datenworte vorgibt. Anhand dieses Parameters ermittelt die erste Justiereinheit eine Auffüllschrittweite, wie zuvor beschrieben. Die Justiereinheit füllt nach einer mit der Auffüllschrittweite durchgeführten Linksverschiebung des eingangs anliegenden ersten Datenwortes am linken und rechten Rand mit Nullen auf, so dass am Ausgang der ersten Justiereinheit 502 ein Datenwort der vom Reduzierer 500 unterstützten Wortlänge 2n – 1 vorliegt. In dem so modifizierten ersten Datenwort liegen diejenigen Terme des dem ursprünglichen ersten Datenwort entsprechendem Polynoms C(x), die eine Ordnung größer als m haben an denselben Bitpositionen, wie wenn schon das ursprüngliche Datenwort die Länge 2n – 1 gehabt hätte.

Der ersten Justiereinheit 502 ist eine Reduziereinheit 506 nachgeschaltet, deren Betrieb ebenfalls von der Steuereinheit 504 kontrolliert wird. Diese liefert der Reduziereinheit insbesondere die für die anhand der 2a) und 2b) und 3 ausführlich beschriebenen Rechtsverschiebungen erforderlichen Parameter SO bis S3. Die nähere Struktur der Reduziereinheit wird anhand der nachfolgenden 6 und 7 in alternativen Ausführungsbeispielen beschrieben.

Der Reduziereinheit 506 ist eine zweite Justiereinheit 508 nachgeschaltet. Diese sorgt für eine Rücktransformation des am Ausgang des Reduzierers anliegenden Summen-Datenwortes durch eine Rechtsverschiebung und Entfernung der eingangs in der ersten Justiereinheit eingefügten Nullen. Am Ausgang der zweiten Justiereinheit 508 liegt dann das gesuchte reduzierte zweite Datenwort an.

5 zeigt eine alternative Implementierung der Reduziereinheit, bei der mit lediglich einem Rechtsschieber 702 gearbeitet wird, der seriell unterschiedlich weit verschobene Kopien des zweiten Sub-Datenwortes erzeugt, die zum jeweiligen ersten Sub-Datenwort hinzu addiert werden.

Die Reduziereinheit 706 der 5 benötigt dementsprechend viele Zyklen für einen Reduzierschritt, wobei vorausgesetzt wird, dass die Rechtsverschiebungen in der Ordnung S3 ≤ S2 ≤ S1 ≤ S0 durchgeführt werden, so dass sukzessive nach rechts geschoben wird.


Anspruch[de]
Verfahren zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist, mit den Schritten:

– Bereitstellen eines Reduktionspolynoms R(x), das ein Trinomial oder ein Pentanomial bildet;

– Partitionieren des ersten Datenworts in ein binäres erstes Sub-Datenwort C0 und ein binäres zweites Sub-Datenwort C1, deren entsprechende Polynome C0(x) und C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllen, und Abgreifen des zweiten Sub-Datenwortes zur Bildung eines ersten Summandenterms;

– Rechtsverschieben des zweiten Sub-Datenworts zur Bildung eines zweiten Summandenterms, und Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme, bis jedem nicht verschwindenden Term des Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist, indem die Schrittweite einer jeweiligen Rechtsverschiebung gleich der Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynomsist;

– Addieren der gebildeten Summandenterme zum ersten Sub-Datenwort zur Bildung eines Summendatenwortes;

– wenn das so ermittelte Summendatenwort eine Länge größer als m hat, Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, bis das so ermittelte Summendatenwort eine Länge von maximal m hat und somit das zweite Datenwort bildet.
Verfahren zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist, mit den Schritten:

– Bereitstellen eines Reduktionspolynoms R(x), das ein Trinomial oder ein Pentanomial bildet;

– Partitionieren des ersten Datenworts in ein binäres erstes Sub-Datenwort C0 und ein binäres zweites Sub-Datenwort C1, deren entsprechende Polynome C0(x) und C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllen, und Abgreifen des zweiten Sub-Datenwortes zur Bildung eines ersten Summandenterms;

– Rechtsverschieben des zweiten Sub-Datenworts zur Bildung eines zweiten Summandenterms, und Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme, bis jedem nicht verschwindenden Term des Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist, indem die Schrittweite einer jeweiligen Rechtsverschiebung gleich der Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynomsist;

– Addieren der gebildeten Summandenterme, mit Ausnahme des ersten Summandenterms, zum ersten Datenwort;

– wenn das so ermittelte Summendatenwort eine Länge größer als m hat, Anwendung der Verfahrensschritte ab dem Schritt des Parfitionierens auf das gebildete Summandendatenwort, bis das so ermittelte Summendatenwort eine Länge von maximal m hat;

– Addieren des ersten Summandenterms und, im genannten Falle einer Anwendung der Verfahrensschritte ab dem Schritt des Partitionierens auf das gebildete Summandendatenwort, jedes weiteren zwischenzeitlich ermittelten zweiten Sub-Datenworts zum zuletzt ermittelten Summendatenwort zur Bildung des zweiten Datenworts.
Verfahren nach Anspruch 1 oder 2, bei dem das erste Datenwort eine Länge von weniger als 2n – 1 hat, mit einem vor der Rechtsschiebeoperation durchgeführten zusätzlichen ersten Justierschritt, der ein Linksverschieben des ersten Datenworts um eine Auffüllschrittweite und ein beiderseitiges Anfügen einer der Auffüllschrittweite entsprechenden Anzahl Nullen an das erste Datenwort beinhaltet, derart, dass die Länge des so modifizierten ersten Datenworts 2n – 1 beträgt und dass im modifizierten ersten Datenwort diejenigen Terme des dem ersten Datenwort entsprechenden Polynoms C(x), die eine Ordnung größer als m haben, an denselben Bitpositionen angeordnet sind wie wenn das erste Datenwort schon anfänglich die Länge 2n – 1 gehabt hätte. Verfahren nach Anspruch 3, mit einem zweiten Justierschritt, der ein Entfernen der anfänglich angefügten Nullen aus dem ermittelten Summendatenwort und ein Rechtsverschieben des Summendatenworts um die Auffüllschrittweite beinhaltet. Verfahren nach einem der Ansprüche 1 bis 4, bei dem das irreduzible Polynom allein durch die Potenzen der nicht verschwindenden Terme des Reduktionspolynoms, die nicht der Term xm sind, repräsentiert wird. Verfahren nach Anspruch 5, bei dem das irreduzible Polynom zusätzlich durch die bekannte maximale Länge m von Datenworten des binären finiten Feldes repräsentiert wird. Vorrichtung zur Reduktion eines einem Polynom C(x) entsprechenden ersten Datenworts mit einer Länge von maximal 2n – 1 auf ein zweites Datenwort mit einer Länge von maximal m, das in einem binären finiten Feld GF(2m), dessen Elemente eine maximale Länge m haben, einem zu C(x) äquivalenten Polynom C''0(x) entspricht, wobei m entweder kleiner oder gleich n ist, mit:

– einem Speicher, der eine Repräsentation mindestens eines Reduktionspolynoms R(x) enthält, das ein Trinomial oder ein Pentanomial bildet;

– einer Selektionseinheit, die ausgebildet ist, ein binäres Sub-Datenwort aus dem ersten Datenwort zu abzugreifen, dessen entsprechendes Polynom C1(x) die Gleichung C(x) = C1(x)·xm + C0(x) erfüllt und das einen ersten Summandenterm bildet;

– einer Schiebeeinheit, die mit der Selektionseinheit verbunden und ausgebildet ist, das Sub-Datenwort zur Bildung eines zweiten oder weiterer Summandenterme um eine jeweils vorbestimmte Schrittweite nach rechts zu verschieben und die gebildeten Summandenterme auszugeben;

– einem Addiereinheit, die mit der Schiebeeinheit verbunden und ausgebildet ist, einen jeweiligen Summandenterm sowie die von der Schiebeeinheit ausgegebenen Summanden zum ersten Datenwort zu addieren; und

– einer Steuereinheit, die ausgebildet ist,

die Schrittweite einer jeweiligen, von der Schiebeeinheit auszuführenden Rechtsverschiebung zur Bildung eines Summandenterms als Differenz von m und der Ordnung eines jeweiligen nicht verschwindenden Terms des Reduktionspolynoms zu bestimmen,

die Schiebeeinheit zur wiederholten Durchführung des Rechtsverschiebungsschritts für eine Bildung weiterer Summandenterme mit jeweils neu bestimmter Schrittweite zu instruieren, bis jedem nicht verschwindenden Term eines jeweils vorgegebenen Reduktionspolynoms, der nicht der Term xm ist, je ein Summandenterm zugeordnet ist,

und die Berechnungseinheit, die Schiebeeinheit und die Addiereinheit erforderlichenfalls erneut zu aktivieren, bis ein ermitteltes Summendatenwort eine Länge von maximal m hat und somit das zweite Datenwort bildet.
Vorrichtung nach Anspruch 7, bei der die Steuereinheit ausgebildet ist, die Addiereinheit im Falle einer Wiederholung der Verfahrensschritte ab dem Schritt des Ermittelns eines binären Sub-Datenworts, zu instruieren, die jeweils gebildeten Summandenterme mit Ausnahme des ersten Summandenterms zum jeweiligen ersten Datenwort zu addieren, und nach einer Feststellung, dass ein ermitteltes Summendatenwort eine Länge hat, die nicht größer als m ist, zur Bildung des zweiten Datenworts jeden zwischenzeitlich ermittelten ersten Summandenterm zum ermittelten Summendatenwort zu addieren. Vorrichtung nach Anspruch 7 oder 8, mit einer ersten und einer zweiten Justiereinheit,

wobei die erste Justiereinheit ausgebildet ist, ein eingehendes erstes Datenwort mit einer Länge von weniger als 2n – 1 vor der Rechtsschiebeoperation um eine Auffüllschrittweite nach links zu verschieben und beiderseits des ersten Datenwortes eine der Auffüllschrittweite entsprechende Anzahl Nullen an das erste Datenwort anzufügen, derart, dass die Länge des so modifizierten ersten Datenworts 2n – 1 beträgt und dass im modifizierten ersten Datenwort diejenigen Terme des dem ersten Datenwort entsprechenden Polynoms C(x), die eine Ordnung größer als m haben, an denselben Bitpositionen angeordnet sind wie wenn das erste Datenwort schon anfänglich die Länge 2n – 1 gehabt hätte, und

wobei die zweite Justiereinheit ausgebildet ist, das ermittelte Summendatenwort der Länge von maximal m um die Auffüllschrittweite nach rechts zu verschieben und die anfänglich angefügten Nullen zu entfernen.
Vorrichtung nach einem der Ansprüche 7 bis 9, bei der die Schiebeeinheit eine Anzahl parallel geschalteter Rechtsschieber enthält, denen das Sub-Datenwort zugeführt ist. Vorrichtung nach einem der Ansprüche 7 bis 9, bei der die Schiebeeinheit genau einen Rechtsschieber enthält, und bei der die Steuereinheit ausgebildet ist, die Wiederholung des Rechtsverschiebungsschrittes zur Bildung weiterer Summandenterme durch zusätzliches Rechtsschieben des zuletzt vom Rechtsschieber ausgegebenen Summandenterms um eine jeweilige Differenzschrittweite durchzuführen, wobei die jeweilige Differenzschrittweite die Differenz zwischen den Rechtsverschiebungen aufeinander folgender Summandenterme jeweils gegenüber dem ersten Summandenterm ist.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com