PatentDe  


Dokumentenidentifikation DE10201443A1 07.08.2003
Titel Carry-Save-Multiplizierer
Anmelder Infineon Technologies AG, 81669 München, DE
Erfinder Klug, Franz, 81737 München, DE;
Kniffler, Oliver, 81737 München, DE;
Gammel, Berndt, 81737 München, DE
Vertreter Schoppe, Zimmermann, Stöckeler & Zinkler, 82049 Pullach
DE-Anmeldedatum 16.01.2002
DE-Aktenzeichen 10201443
Offenlegungstag 07.08.2003
Veröffentlichungstag im Patentblatt 07.08.2003
IPC-Hauptklasse G06F 7/52
Zusammenfassung Ein Carry-Save-Multiplizierer für verschlüsselte Daten umfaßt ein erstes Operandenregister (10), ein zweites Operandenregister (12), ein Multiplikationszwischenergebnisregister (14) sowie eine Mehrzahl von Ein-Bit-Volladdierern (160, 161, 162, ...) von einer Ordnung (0) bis zu einer Ordnung (n - 1), wobei jeder Ein-Bit-Volladdierer aus einem verschlüsselten Bit der Ordnung (i) des zweiten Operanden, aus einem verschlüsselten Übertragbit der Ordnung (i) aus dem Multiplikationszwischenergebnisregister (14) aus dem verschlüsselten Summenbit der nächsthöheren Ordnung (i + 1) aus dem Multiplikationszwischenergebnisregister (14) ein veschlüsseltes Übertragbit für die Ordnung (i) und ein verschlüsseltes Summenbit für die Ordnung (i) berechnet und im Multiplikationszwischenergebnisregister (14) ablegt. Damit eine gleiche Schlüsselbasis für jede Ordnung beibehalten ist, ist eine Umverschlüsselungseinrichtung (20i) vorgesehen, die einen Umverschlüsselungs-Schlüssel aus einer Kombination der Verschlüsselungsparameter (ki) und (ki+1) der betroffenen Stellen berechnet und dem entsprechenden Ein-Bit-Volladdierer (16i) zuführt. Der Carry-Save-Multiplizierer für veschlüsselte Daten speichert sämtliche Bits in den Registern in verschlüsselter Form und umfaßt vorzugsweise einen Ein-Bit-Volladdierer, der direkt aus verschlüsselten Eingangsdaten verschlüsselte Ausgangsdaten berechnet. Der Carry-Save-Multiplizierer erzeugt somit an keiner Stelle Klartextdaten und ist vor ...

Beschreibung[de]

Die vorliegende Erfindung bezieht sich auf Rechenwerke und insbesondere auf einen sicheren Carry-Save-Multiplizierer.

Multiplikationsalgorithmen, wie z. B. der Radix-2- Multiplikationsalgorithmus oder der Booth-Recoding- Multiplikationsalgorithmus sind in der Technik bekannt und in "Computer Architecture a Quantitative Approach", Second Edition, Hennessy und Patterson, Morgan Kaufmann Publishers, Inc., 1996, Anhang A beschrieben. Diese Multiplikationsalgorithmen erfordern zum Bilden des Produkts aus einem ersten Operanden a und einem zweiten Operanden b das Hinzuaddieren des zweiten Operanden b zu einem Multiplikationszwischenergebnis, das in einem Multiplikationszwischenergebnisregister P gespeichert, wobei dann, nach der Multiplikation bzw. Subtraktion der Inhalt des Multiplikationszwischenergebnisregisters P und der Inhalt des ersten Operandenregisters A zum Speichern des Operanden a gemeinsam um ein Bit nach rechts verschoben werden. Dann wird zum aktuellen Zwischenergebnisregister wieder der zweite Operand addiert, falls das betrachtete Bit des ersten Operanden a gleich 1 ist, woraufhin wieder eine Rechtsverschiebung folgt etc. Am Ende dieser iterativen Abarbeitung sämtlicher Bits des ersten Operanden steht im Multiplikationszwischenergebnisregister und im ersten Operandenregister das Multiplikationsergebnis.

Zur Beschleunigung von Multiplikationsverfahren existieren verschiedene Algorithmen, die ebenfalls in dem oben beschriebenen Lehrbuch im Anhang A beschrieben sind. Ein schnellerer Multiplizierer ist der sogenannten Carry-Save-Multiplizierer. Ein solcher Carry-Save-Multiplizierer bzw. der wesentliche Teil desselben ist in Fig. 6 dargelegt. Ein Carry-Save- Multiplizierer ist eine Sammlung von n unabhängigen Ein-Bit- Volladdierern VA0, VA1, VA2, . . .. In Fig. 6 ist ferner ein erstes Operandenregister 60 (A), ein zweites Operandenregister 62 (B) sowie ein Multiplikationszwischenergebnisregister 64 (P) gezeigt. In dem zweiten Operandenregister B ist der zweite Operand b gespeichert, während zu Anfang des Multiplikationsalgorithmus im ersten Operandenregister A der erste Operand gespeichert ist. Die beiden Operanden a und b sollen multipliziert werden, um das Multiplikationsergebnis zu erhalten.

Im Multiplikationszwischenergebnisregister P, das in Fig. 6 mit dem Bezugszeichen 64 bezeichnet ist, existieren für jede Stelle 0, 1, 2, 3, . . ., zwei Speicherplätze, nämlich ein erster Speicherplatz zum Speichern des Summenbits si des Volladdierers VAi, und ein zweiter Speicherplatz zum Speichern des Übertragbits ci des Volladdierers VAi für diese Stelle. Das besondere Merkmal des Carry-Save-Multiplizierers besteht darin, daß das Summenbit si+1 der nächsthöheren Stelle i + 1 in dem Volladdierer VAi als zweiter Eingangsoperand verwendet wird, während der Übertrag, der von dem Volladdierer VAi im vorherigen Schritt berechnet worden ist, wieder im aktuellen Schritt als Übertrag-Eingangssignal in den Ein-Bit- Volladdierer VAi eingespeist wird. Die Übertragbits der einzelnen Volladdierer c0 bis cn-1 werden somit in dem Multiplikationszwischenergebnisregister P gespeichert, weshalb dieser Multiplizierer als Carry-Save-Multiplizierer bezeichnet wird.

Ein Carry-Save-Addierer ist somit eine Sammlung von n unabhängigen Volladdierern. Jeder Volladdierer VAi ist ein Ein- Bit-Volladdierer, wobei jeder Kasten in Fig. 6 ein Bit eines Registers darstellt. Jede Additionsoperation resultiert in einem Bitpaar, das in dem Summen- und dem Carry-Teil von P gespeichert wird. Da jeder Addiervorgang unabhängig ist, sind in einem Addiervorgang nur zwei logische Ebenen betroffen, was den in Fig. 6 gezeigten Multiplizierer sehr schnell macht.

Um den Multiplizierer in Fig. 6 zu betreiben, werden zunächst die Summen- und die Übertragbits von dem Multiplikationszwischenergebnisregister P mit Nullen geladen, um eine Initialisierung zu erreichen. Dann wird die erste ALU-Operation des verwendeten Multiplikationsalgorithmus durchgeführt. Wenn ein Booth-Recoding verwendet wird, kann die erste ALU-Operation eine Subtraktion statt einer Addition sein.

Dann wird das niederstwertige Summenbit von P, wie es in Fig. 6 durch einen Pfeil 66 angedeutet ist, in das erste Operandenregister, und zwar an das höchstwertige Bit desselben, geschoben. Gleichzeitig wird das erste Operandenregister A um ein Bit nach rechts geschoben. Es sei darauf hingewiesen, daß außer dem niederstwertigen Summenbit des Multiplikationszwischenergebnisregisters P, also so, keinerlei Verschiebungen in dem Register durchgeführt werden müssen. Die Summen-Bits si schieben sich gewissermaßen automatisch herunter, da das Summenbit der Stelle i + 1 in den Operandeneingang des Volladdierers für die Stelle i eingespeist wird. Dagegen bleiben die Übertragbits ci stehen. Daher wird in Fig. 6 dieselbe Bezeichnung ci für das Übertrag-Eingangssignal und das Übertrag-Ausgangssignal verwendet, da der Volladdierer VAi auf dieselbe Carry-Speicherstelle im Multiplikationszwischenergebnisregister zugreift. Jeder Additionsschritt wird beim Carry-Save-Multiplizierer deutlich beschleunigt, da jede Addiererzelle unabhängig von den anderen Addiererzellen arbeitet und keine Übertrag-Ausbreitung auftreten muß, auf die gegebenenfalls gewartet werden müßte.

Der Carry-Save-Multiplizierer benötigt mehr Hardware, da das Multiplikationszwischenergebnisregister P im Vergleich zu einem üblichen Multiplizierer doppelt so groß sein muß. Ferner muß nach dem letzten Schritt das hochwertige Wort des Ergebnisses in einen üblichen Addierer eingespeist werden, um die Summen- und die Übertrag-Teile zu kombinieren. Dann steht in dem Multiplikationszwischenergebnisregister P und dem ersten Operandenregister A wieder das Ergebnis der Multiplikation.

Nachteilig an dem in Fig. 6 gezeigten Multiplizierer ist die Tatsache, daß er lediglich mit Klartextdaten arbeitet und daher physikalisch angreifbar ist. Die möglichen Angriffsszenarien reichen dabei von verschiedenen physikalischen Angriffsszenarien, wie z. B. Nadelangriffen, bis hin zu sogenannten indirekten Angriffen, wie z. B. SPA (SPA = Simple Power Analysis) oder DPA (DPA = Differential Power Analysis = differentielle Leistungsanalyse).

Bei dem in Fig. 6 gezeigten Multiplizierer sind drei Register, nämlich A, B und P involviert, die, wenn mit sicherheitsrelevanten Daten gerechnet wird, alle sensible Daten halten, die möglicherweise angegriffen werden können.

Um sicherere Rechenwerke zu schaffen, kann eine Dual-Rail- Precharge-Technik verwendet werden, um unabhängig von der Art der Daten das gleiche Strom-, Leistungs- oder Zeitprofil zu erhalten. Dieses Verfahren eliminiert zwar das Rechenwerk als Angriffspunkt, liefert jedoch keinen Schutz der Register vor Ausspähungen. Nachteilig ist ferner der höhere Chipflächenverbrauch, da sämtliche Rechenwerke typischerweise zweimal ausgeführt werden müssen.

Die Aufgabe der vorliegenden Erfindung besteht darin, eine sichere und effiziente Ausführung für einen Carry-Save- Multiplizierer zu schaffen.

Diese Aufgabe wird durch einen Carry-Save-Multiplizierer gemäß Patentanspruch 1 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß Sicherheit bei der Datenspeicherung in den Register A, B und P und bei der Datenübertragung zwischen den Registern und den voneinander unabhängigen Ein-Bit-Volladdierern dadurch erreicht werden kann, daß in den Registern verschlüsselte Daten abgespeichert werden, und daß diese Daten in verschlüsseltem Zustand zu den jeweiligen Volladdierern übertragen werden. Auf sämtlichen Übertragungswegen und in sämtlichen Registern finden sich daher lediglich noch verschlüsselte Daten, die nicht mehr ohne weiteres angegriffen werden können.

Erfindungsgemäß wird ferner eine bitweise Verschlüsselung der Operanden eingesetzt, wobei für jedes Operandenbit ein Verschlüsselungsparameter verwendet wird, der von Verschlüsselungsparametern für andere Operandenbits unabhängig ist. Nachdem ein Volladdierer für eine Stelle i als Eingangssignal das Summenbit der nächsthöheren Stelle i + 1 erhält, wird erfindungsgemäß ferner eine Umverschlüsselungseinheit vorgesehen, um das Summenbit der Stelle i + 1, das mit dem Verschlüsselungsparameter für die Stelle i + 1 verschlüsselt ist, zum Gebrauch durch den Addierer für die Stelle i umzuverschlüsseln.

Prinzipiell könnte an den Eingängen des Volladdierers für die Stelle i eine Entschlüsselungseinrichtung vorhanden sein, um die Eingangsoperanden zu entschlüsseln. Dann kann die Ein- Bit-Addieroperation im Klartext durchgeführt werden, und das Klartextergebnis in Form des Summenbits und des Übertragbits können verschlüsselt werden und zu dem Multiplikationszwischenergebnisregister P übertragen werden.

Aus Sicherheitsgründen wird es jedoch bevorzugt, die Ein-Bit- Volladdiereroperation direkt unter Verwendung verschlüsselter Daten durchzuführen, um ein verschlüsseltes Summenbit und ein verschlüsseltes Übertragbit zu erzeugen, ohne daß eine Entschlüsselung am Eingang des Addierers bzw. eine Verschlüsselung am Ausgang des Addierers auftritt. Der Addieralgorithmus ist ferner vorzugsweise so ausgestaltet, daß auch keine Klartext-Zwischenergebnisse erzeugt werden, so daß an keiner Stelle des gesamten Multiplizierers Klartextdaten auftreten.

Dieser Carry-Save-Multiplizierer arbeitet vollständig im Geheimtextraum mit verschlüsselten Daten unter Verwendung von voneinander unabhängigen Verschlüsselungsparametern für die einzelnen Stellen, so daß ein hohes Sicherheitsniveau erreicht ist. Ein Angreifer müßte die Schlüssel für die einzelnen Stellen ausspähen, um mit direkten oder indirekten Angriffen Daten lesen zu können. Um dies zu erschweren, wird es ferner bevorzugt, einen häufigen Schlüsselwechsel vorzunehmen, wobei die einzelnen Verschlüsselungsparameter unter Verwendung verschiedener Zufallszahlengeneratoren erzeugt werden können.

Das solchermaßen aufgebaute Rechenwerk zum Multiplizieren zweier Operanden auf der Basis des Carry-Save- Multiplikationsalgorithmus liefert zu keinem Zeitpunkt ein Zwischenergebnis in Klartextform. Dadurch werden alle Arten von statistischen Angriffsszenarien, wie z. B. DPA oder SPA wesentlich erschwert. Das erfindungsgemäße Rechenwerk ist ferner technologieunabhängiger anwendbar als eine Fullcustom- Lösung mit Dual-Rail-Precharge-Technik und somit leichter und schneller bei einem Technologiewechsel anpaßbar.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeichnungen detailliert erläutert. Es zeigen:

Fig. 1 ein Blockschaltbild eines Carry-Save- Multiplizierers gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung;

Fig. 2 eine Prinzipdarstellung eines kryptographischen Ein-Bit-Volladdierers;

Fig. 3 eine bevorzugte Ausführungsform für eine Schaltung zum Berechnen des Summenbits, wobei die Umverschlüsselungsfunktion und die Addiererfunktion kombiniert sind;

Fig. 4 eine bevorzugte Ausführungsform für eine Schaltung zum Berechnen eines verschlüsselten Übertragbits, wobei die Umverschlüsselung und die Addiererfunktion kombiniert sind;

Fig. 5a eine Schaltung gemäß einem weiteren Ausführungsbeispiel der vorliegenden Erfindung zum Berechnen des Übertragbits unter Verwendung des Schlüssels für die aktuelle Volladdiererstelle;

Fig. 5b eine Wahrheitstabelle für die in Fig. 5a gezeigte Schaltung; und

Fig. 6 ein Blockschaltbild eines bekannten Carry-Save- Multiplizierers für Klartextdaten.

Fig. 1 zeigt einen Carry-Save-Multiplizierer gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung. Der erfindungsgemäße Carry-Save-Multiplizierer, der in Fig. 1 gezeigt ist, umfaßt ein erstes Operandenregister 10, das mit A bezeichnet ist, und das Registerplätze für Bits a0, a1, a2, . . . ai, . . . an-1 aufweist. Bei dem in Fig. 1 gezeigten Beispiel beträgt n gleich 6. Erfindungsgemäß speichert das erste Operandenregister 10 verschlüsselte Operandenbits, wie es durch den Apostroph bei jedem Bit hervorgehoben ist. Der Multiplizierer umfaßt ferner ein zweites Operandenregister 12, das in Fig. 1 mit B bezeichnet ist. Dieses Register speichert die Operandenbits b0', b1', b2', . . ., bi', . . . bn-1' des zweiten Operanden b der Multiplikation. Wie im Register A sind auch im Register B verschlüsselte Operandenbits abgelegt. Dasselbe trifft für ein Multiplikationszwischenergebnisregister 14 zu, das mit P bezeichnet ist. Das Multiplikationszwischenergebnisregister 14 umfaßt Speicherplätze zum Speichern verschlüsselter Summenbits s0', s1', s2', . . ., si', . . ., sn-1'. Ferner umfaßt das Register 14 Registerplätze zum Speichern verschlüsselter Übertragbits c0', c1', c2', . . ., ci', . . ., cn-1'. Für jede Stelle der Operanden a', b' ist ein Ein-Bit- Volladdierer 160, 161, 162, 163, . . ., 16i, ..., 16n-1 vorgesehen.

Der erfindungsgemäße Carry-Save-Multiplizierer umfaßt ferner ein Schlüsselregister 18 zum Speichern der für die einzelnen Stellen verwendeten Verschlüsselungsparameter k0, k1, k2, . . ., ki, . . ., kn-1. Vorzugsweise wird jede Stelle i mit einem eigenen Verschlüsselungsparameter ki verschlüsselt. Als Verschlüsselungsalgorithmus, durch den ein Operandenbit ai bzw. bi mit dem Verschlüsselungsparameter ki für diese Stelle verknüpft wird, ist prinzipiell jede umkehrbare Funktion verwendbar. Aus Gründen der schaltungstechnischen Einfachheit beim Aufbau des Rechenwerks für verschlüsselte Daten wird es bevorzugt, als Verschlüsselungsalgorithmus eine XOR- oder XNOR-Verknüpfung zu verwenden. Die Umkehrung der XOR- Verknüpfung ist ebenfalls eine XOR-Verknüpfung des verschlüsselten Bits mit dem Verschlüsselungsparameter für dieses Bit. Ein Bit wird daher vorzugsweise folgendermaßen verschlüsselt:



xi' = xi XOR ki.

In Fig. 1 ist ferner eine Umverschlüsselungseinrichtung 21 dargestellt, um das aus dem Multiplikationszwischenergebnisregister 14 herauszuschiebende niederstwertige Summenbit s'0 umzuverschlüsseln, damit dieses Bit mit dem korrekten Verschlüsselungsparameter verschlüsselt ist, der für die höchstwertige Stelle des ersten Operandenregisters 10 zutreffend ist. Beim vorliegenden Beispiel hat das erste Operandenregister sieben Stellen, wobei der für die höchstwertige Stelle des Operandenregisters zuständige Verschlüsselungsparameter k6 ist. Das niederstwertige Summenbit des Multiplikationszwischenergebnisregisters 14, das in Fig. 1 mit s'0 bezeichnet ist, muß daher unter Verwendung der Umverschlüsselungseinheit 21 während seiner Verschiebung auf dem Register 14 heraus in das Register 10 umverschlüsselt werden. Der Umverschlüsselungs-Schlüssel ergibt sich aus der XOR- Verknüpfung des Verschlüsselungsparameters k0 für die niederstwertige Stelle und des Verschlüsselungsparameters k6 für die sechste Stelle, welche die Zielstelle der Verschiebung ist.

Die Bitverschiebung von verschlüsselten Bits kann entweder dadurch erreicht werden, daß das Ursprungsbit zunächst umverschlüsselt wird und dann an die Zielstelle geschoben wird, oder daß das Ursprungsbit zunächst an die Zielstelle geschoben wird und dann umverschlüsselt wird. Dieselbe Vorgehensweise ist ferner anzuwenden, wenn im Register A, das verschlüsselte Bits beinhaltet, eine Bitverschiebung durchgeführt wird. Soll in einem nächsten Schritt das höchstwertige Bit des ersten Operandenregisters a'6 auf die Stelle a'5, geschoben werden, so muß ebenfalls eine Umverschlüsselung des Bits a'6 unter Verwendung eines Verschlüsselungsparameters durchgeführt werden, der wieder gleich der XOR-Verknüpfung der Schlüssel k5 und k6 ist.

Der erfindungsgemäße Multiplizierer umfaßt ferner für jede Stelle eine Umverschlüsselungseinrichtung 200, 201, 202, . . ., 20i, . . ., 20n-1. Die Umverschlüsselungseinrichtung fungiert bei dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung, bei dem eine XOR-Verknüpfung als Verschlüsselungseinrichtung verwendet wird, folgendermaßen. Die beiden Schlüssel ki und ki+1, die bei der Umverschlüsselungsoperation betroffen sind, werden XOR-verknüpft, um einen Umverschlüsselungs-Schlüssel ti zu berechnen, der mit dem unter Verwendung des Verschlüsselungsparameters ki+1 verschlüsselten Bits XOR- verknüpft werden muß, um dieselbe Bitordnung zu erhalten, wobei das Bit nun jedoch mit dem Verschlüsselungsparameter ki verschlüsselt ist.

Im nachfolgenden wird auf Fig. 2 Bezug genommen, das allgemein einen Ein-Bit-Volladdierer zeigt, der als Ausgangssignale ein verschlüsseltes Summenbit s'i und ein verschlüsseltes Übertragbit c'i liefert, und der als Eingangssignal ein verschlüsseltes Bit des zweiten Operanden b'i, das Übertragbit c'i aus dem Multiplikationszwischenergebnisregister 14 (Fig. 1) sowie das verschlüsselte Summenbit s'i+1 erhält, das im vorherigen Iterationsschritt von dem Volladdierer 16i+1 der um eine Ordnung höheren Stufe erzeugt worden ist. Damit eine gleiche Schlüsselbasis innerhalb des Volladdierers 16i existiert, muß das verschlüsselte Summenbit s'i+1 der nächsthöheren Stufe auf den Verschlüsselungsparameter ki der aktuellen Stufe umverschlüsselt werden. Daher erhält der Ein-Bit- Volladdierer 16i auch einen Umverschlüsselungs-Schlüssel ti, der, wie es ausgeführt worden ist, aus der XOR-Verknüpfung der beiden beteiligten Verschlüsselungsparameter ki und ki+1 berechnet wird.

Der Ein-Bit-Volladdierer, der in Fig. 2 gezeigt ist, kann verschiedene Formen annehmen, so lange er aus den in Fig. 2 gezeigten Eingangssignalen die in Fig. 2 gezeigten Ausgangssignale erzeugt. Prinzipiell könnte der Ein-Bit-Volladdierer 16i, der lediglich verschlüsselte Eingangsdaten empfängt, intern einen Ein-Bit-Volladdierer üblichen Aufbaus für Klartextdaten umfassen. Dann müßten sämtliche Eingangsdaten innerhalb des Ein-Bit-Volladdierers 16i unter Verwendung des Verschlüsselungsparameters ki entschlüsselt werden, um das Übertragbit ci im Klartext und das Summenbit si im Klartext zu berechnen. Bevor das Übertragbit und das Summenbit dann zum Register 14 übertragen werden, würde eine Verschlüsselungseinheit vorgesehen sein, die unter Verwendung des Verschlüsselungsparameters ki diese Klartext-Ergebnisbits verschlüsselt, um das verschlüsselte Summenbit s'i und das verschlüsselte Übertragbit c'i zu erhalten, die in verschlüsselter Form zum Multiplikationszwischenergebnisregister 14 übertragen werden, um dort in verschlüsselter Form abgespeichert zu werden.

Bei einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung findet innerhalb des Ein-Bit-Volladdierers 161 jedoch keine Entschlüsselung bzw. Verschlüsselung statt, sondern der Ein-Bit-Volladdierer arbeitet direkt auf der Basis verschlüsselter Eingangsdaten, um verschlüsselte Ausgangsdaten zu liefern, ohne daß Klartext-Zwischenergebnisse berechnet werden. Eine Schaltung zum Berechnen eines verschlüsselten Summenbits si' direkt aus den verschlüsselten Eingangssignal s'i+1, b'i, c'i und ti ist in Fig. 3 gezeigt. Ein verschlüsseltes Summenbit s'i wird durch XOR-Verknüpfung der Eingangssignale erreicht. Es ist zu sehen, daß bei der in Fig. 3 gezeigten Schaltung zur Berechnung eines verschlüsselten Summenbits keinerlei Entschlüsselungen bzw. Zwischenergebnisse im Klartextraum erzeugt werden. Daher kann ein Angreifer auch an keiner Stelle Klartextergebnisse ausspähen.

Fig. 4 zeigt eine beispielhafte Schaltung zum Berechnen eines verschlüsselten Übertragbits ci'out unter Verwendung der verschlüsselten Eingangssignale s'i+1, b'i, c'i. Ferner benötigt die in Fig. 4 gezeigte Schaltung ebenso wie die in Fig. 3 gezeigte Schaltung den Umverschlüsselungs-Schlüssel ti, der berechnet wird, wie es Bezug nehmend auf Fig. 2 dargestellt worden ist. Die in Fig. 4 gezeigte Schaltung implementiert die unterhalb der Schaltung in Fig. 4 gezeigte logische Gleichung und umfaßt hierzu als Umverschlüsselungseinrichtung ein XOR-Gatter 20i, drei UND-Gatter 42a, 42b und 42c sowie schließlich ein OR-Gatter 44, die, wie es in Fig. 4 gezeigt ist, miteinander verdrahtet sind. Am Ausgang des OR-Gatters 44 ergibt sich das verschlüsselte Übertragbit c'iout. Es sei darauf hingewiesen, daß bei der in Fig. 4 gezeigten Schaltung zum Berechnen des verschlüsselten Übertragbits c'iout der Schlüssel ki für die Stelle i nicht explizit benötigt wird, sondern lediglich implizit innerhalb des Umverschlüsselungsschlüssels ti.

Eine weitere Implementation einer Schaltung zum Berechnen des Übertrags unter Verwendung lediglich verschlüsselter Daten ak und des Verschlüsselungsparameters k ist in Fig. 5a gezeigt. Bei dieser Schaltung wird der Schlüssel k für die aktuelle Stelle benötigt, es wird jedoch kein Zwischenergebnis in Klartextform der Parameter a, b oder c berechnet.

Im nachfolgenden wird auf Fig. 5a Bezug genommen, um als Beispiel für einen Addierer eine verschlüsselte Drei-Operanden- Operation zwischen den Operanden a, b und c zu zeigen. Bestimmungsgleichung hierfür ist die nachfolgende Gleichung:





Die Operation von drei Operanden bzw. von drei Bits von Operanden, wenn ein Bit-Slice eines Addierers betrachtet wird, führt zu einem Übertrag c, wobei in der vorletzten Spalte und der drittletzten Spalte der in Fig. 5b gezeigten Wahrheitstabelle die Überträge bei der ADD-Operation zwischen dem unverschlüsselten Operanden a, b und c als cp aufgeführt ist, wobei p für "plain" = unverschlüsselt steht, und wobei in der vorletzten Zeile der Übertrag der ADD-Operation der erfindungsgemäßen ALU ck gezeigt ist. Der Übertrag ck(n+1) ergibt sich durch folgende Gleichung:





Eine Implementierung dieser Gleichung ist in Fig. 5a dargestellt. Die ALU von Fig. 5a für ein Rechenwerk umfaßt wiederum eine Vielzahl von arithmetischen Unteroperationen, nämlich AND-Operationen 171 bis 173 und OR-Operationen 179 und 180. Ausgangsseitig ergibt sich dann der Übertrag (ckn)n+1 für die ADD-Verknüpfung der drei Eingangs-Operanden, welcher wieder gemäß der in Fig. 5b gezeigten Wahrheitstabelle mit dem Übertrag übereinstimmt, wenn die drei Operanden in unverschlüsselter Form addiert werden und dann verschlüsselt werden. Insbesondere bedeutet (ckn)n+1 den Übertrag (Carry-In) für die nächsthöhere ((n + 1)-te) Position (Bit-Slice), verschlüsselt mit dem Schlüssel kn, also mit dem Schlüssel der aktuellen Position n, also nicht verschlüsselt mit dem Schlüssel kn+1für die nächsthöhere Position. Dies bedeutet, daß je nach Ausführung eines Bit-Slices eine Umverschlüsselung von (ckn)n+1 vom Schlüssel kn in den Schlüssel kn+1 stattfinden wird.

Die beiden letzgenannten Gleichungen geben eine Implementation für einen Addierer mit verschlüsselten Operanden vor, der ein verschlüsseltes Summenbit s' (s' = skn) und ein verschlüsseltes Übertragbit c' (c' = (ckn)n+1) ausgibt, wobei derselbe eingangsseitig neben den beiden verschlüsselten Operanden ein verschlüsseltes Übertrageingangsbit erhält. Ein solcher Addierer wird im Stand der Technik auch als Ein-Bit- Volladdierer bezeichnet und kann als Addiereinrichtung 160, 161, . . . (Fig. 1) verwendet werden.

Für Fachleute ist es offensichtlich, daß beliebige alternative Verschlüsselungsalgorithmen statt der XOR-Verknüpfung als Verschlüsselungsalgorithmus verwendet werden können. Im wesentlichen gleichwertig zur XOR-Verknüpfung als Verschlüsselungsalgorithmus ist die XNOR-Verknüpfung als Verschlüsselungsalgorithmus, wobei der Schaltungsaufwand zur Implementation des Ein-Bit-Volladdierers 16i für verschlüsselte Daten der gleiche ist. Für kompliziertere Verschlüsselungsalgorithmen wird sich ein anderer Aufbau für den Ein-Bit-Volladdierer 16i (Fig. 2) ergeben, um aus verschlüsselten Eingangsdaten verschlüsselte Ausgangsdaten zu berechnen. Ferner sei darauf hingewiesen, daß die in Fig. 3 und Fig. 4 gezeigten logischen Gleichungen je nach Technologie auf eine Vielzahl verschiedener Arten und Weisen implementiert werden können, die sich aus Umformungen unter Verwendung von Rechenvorschriften für logische Gleichungen aus den in den Fig. 3 und 4 gezeigten Gleichungen ergeben. So können diese Gleichungen, wie es bekannt ist, für bestimmte Technologien und hauptsächliche Verwendung von NOR- bzw. NAND-Gattern ausgedrückt werden, woraus sich eine Schaltungsimplementation ergibt, die eine andere Anzahl und Art von Gattern hat, die jedoch dieselbe Funktion erfüllen, nämlich aus verschlüsselten Eingangsdaten ein verschlüsseltes Summenbit und ein verschlüsseltes Übertragbit zu berechnen.

In Fig. 1 ist ferner eine Umverschlüsselungseinrichtung 21 dargestellt, um das aus dem Multiplikationszwischenergebnisregister 14 herauszuschiebende niederstwertige Summenbit s'0 umzuverschlüsseln, damit dieses Bit mit dem korrekten Verschlüsselungsparameter verschlüsselt ist, der für die höchstwertige Stelle des ersten Operandenregisters 10 zutreffend ist. Beim vorliegenden Beispiel hat das erste Operandenregister sieben Stellen, wobei der für die höchstwertige Stelle des Operandenregisters zuständige Verschlüsselungsparameter k6 ist. Das niederstwertige Summenbit des Multiplikationszwischenergebnisregisters 14, das in Fig. 1 mit s'0 bezeichnet ist, muß daher unter Verwendung der Umverschlüsselungseinheit 21 während seiner Verschiebung auf dem Register 14 heraus in das Register 10 umverschlüsselt werden. Der Umverschlüsselungs-Schlüssel ergibt sich aus der XOR- Verknüpfung des Verschlüsselungsparameters k0 für die niederstwertige Stelle und des Verschlüsselungsparameters k6 für die sechste Stelle, welche die Zielstelle der Verschiebung ist. Die Bitverschiebung von verschlüsselten Bits kann entweder dadurch erreicht werden, daß das Ursprungsbit zunächst umverschlüsselt wird und dann an die Zielstelle geschoben wird, oder daß das Ursprungsbit zunächst an die Zielstelle geschoben wird und dann umverschlüsselt wird. Dieselbe Vorgehensweise ist ferner anzuwenden, wenn im Register A, das verschlüsselte Bits beinhaltet, eine Bitverschiebung durchgeführt wird. Soll in einem nächsten Schritt das höchstwertige Bit des ersten Operandenregisters a'6 auf die Stelle a'5 geschoben werden, so muß ebenfalls eine Umverschlüsselung des Bits a'6 unter Verwendung eines Verschlüsselungsparameters durchgeführt werden, der wieder gleich der XOR-Verknüpfung der Schlüssel k5 und k6 ist. Bezugszeichenliste 10 erstes Operandenregister

12 zweites Operandenregister

14 Multiplikationszwischenergebnisregister

160, 161, . . . Ein-Bit-Volladdierer

18 Schlüsselregister

200, 201, . . . Umverschlüsselungseinrichtung

21 Umverschlüsselungseinrichtung

40a, 40b NOT-Gatter

42a, 42b, 42c AND-Gatter

60 erstes Operandenregister

62 zweites Operandenregister

64 Multiplikationszwischenergebnisregister

66 Rechtsverschiebung

171-173 AND-Gatter

179-180 OR-Gatter


Anspruch[de]
  1. 1. Carry-Save-Multiplizierer mit folgenden Merkmalen:

    einem ersten Operandenregister (10) mit einer Mehrzahl von Stellen;

    einem zweiten Operandenregister (12) mit einer Mehrzahl von Stellen von einer Ordnung 0 bis zu einer Ordnung n - 1;

    einem Multiplikationszwischenergebnisregister (14) zum Speichern einer Mehrzahl von Summenbits von einer Ordnung 0 bis zu einer Ordnung n - 1 und einer Mehrzahl von Übertragbits von einer Ordnung 0 bis zu einer Ordnung n - 1;

    einer Mehrzahl von Ein-Bit-Volladdierern von einer Ordnung 0 bis zu einer Ordnung n - 1, wobei ein Ein-Bit-Volladdierer 16i der Mehrzahl von Volladdierern für eine Ordnung i folgende Merkmale aufweist:

    einen ersten Eingang für eine Stelle b'i des zweiten Operandenregisters (12) mit der Ordnung i;

    einen zweiten Eingang für ein Übertragbit c'i der Ordnung i;

    einen dritten Eingang für ein Summenbit s'i+1 der Ordnung i + 1;

    einen ersten Ausgang für ein Summenbit s'i der Ordnung i, und

    einen zweiten Ausgang für ein Übertragbit c'i der Ordnung i,

    wobei das erste Operandenregister (10), das zweite Operandenregister (12) und das Multiplikationszwischenergebnisregister (14) angeordnet sind, um verschlüsselte Zahlen zu speichern, die bitweise unter Verwendung eines Verschlüsselungsparameters ki für ein Bit der Ordnung i verschlüsselt sind, und

    wobei für die Ordnung i eine Umverschlüsselungseinheit (20i) vorgesehen ist, um ein verschlüsseltes Summenbit s'i+1 der Ordnung i + 1, das mit einem Verschlüsselungsparameter ki+1 für die Ordnung i + 1 verschlüsselt ist, so umzuverschlüsseln, daß es mit einem Verschlüsselungsparameter ki für die Ordnung i verschlüsselt ist.
  2. 2. Carry-Save-Multiplizierer nach Anspruch 1, bei dem ferner eine Umverschlüsselungseinheit (21) vorgesehen ist, um unter Verwendung eines Verschlüsselungsparameters k0 für eine Ordnung 0 und eines Verschlüsselungsparameters kn+1 für ein höchstwertiges Bit des ersten Operandenregisters (10) ein zu verschiebendes Summenbit des Ein-Bit-Volladdierers (160) für die Ordnung 0 umzuverschlüsseln.
  3. 3. Carry-Save-Multiplizierer nach Patentanspruch 2, bei dem bei einem Schiebevorgang des verschlüsselten niederstwertigen Bits des Multiplikationszwischenergebnisregisters (14) auf ein höchstwertiges Bit des ersten Operandenregisters (10) entweder zunächst eine Umverschlüsselung und dann eine Bitverschiebung vorgenommen wird, oder zunächst eine Bitverschiebung und dann eine Umverschlüsselung vorgenommen wird.
  4. 4. Carry-Save-Multiplizierer nach einem der vorhergehenden Ansprüche, bei dem die Mehrzahl von Ein-Bit-Volladdierern Ein-Bit- Volladdierer für verschlüsselte Daten sind, die unter Verwendung verschlüsselter Eingangsdaten und eines Verschlüsselungsschlüssels verschlüsselte Ausgangdaten liefern, ohne daß ein Zwischenergebnis in Klartextform generiert wird, wobei die Umverschlüsselungseinheit (20i) einen ersten Teil außerhalb eines jeweiligen Ein-Bit-Volladdierers aufweist, die zur Erzeugung eines Umverschlüsselungsschlüssels vorgesehen ist, und wobei die Umverschlüsselungseinheit ferner einen zweiten Teil aufweist, der in den Ein-Bit-Volladdierer integriert ist und dafür vorgesehen ist, die Umverschlüsselung durchzuführen.
  5. 5. Carry-Save-Multiplizierer nach einem der vorhergehenden Ansprüche, bei dem die Verschlüsselung der Zahlen auf einer bitweisen XOR-Verknüpfung einer unverschlüsselten Zahl mit Verschlüsselungsparametern ki für die Stellen der Zahl basiert.
  6. 6. Carry-Save-Multiplizierer nach Patentanspruch 5, bei dem die Umverschlüsselungseinheit (20i) vorgesehen ist, um eine Umverschlüsselung durchzuführen, indem ein verschlüsseltes Bit mit der Ordnung i + 1 mit einem Umverschlüsselungsschlüssel ti XOR-verknüpft wird, wobei der Umverschlüsselungs-Schlüssel ti mittels einer XOR-Verknüpfung des Verschlüsselungsparameters ki für die Ordnung i und des Verschlüsselungsparameters ki+1 für die Ordnung i + 1 berechenbar ist.
  7. 7. Carry-Save-Multiplizierer nach Patentanspruch 6, bei dem die Umverschlüsselungseinheit (20i) für die Ordnung i und der Ein-Bit-Volladdierer (16i) für die Ordnung i kombiniert sind, und eine Einrichtung zum Berechnen eines verschlüsselten Summenbits s'i aufweisen, durch die die folgende Gleichung ausführbar ist:

    si = s'i+1 ⊕ b'i ⊕ c'i ⊕ ti,

    wobei s'i ein verschlüsseltes Summenbit der Ordnung i ist;

    wobei s'i+1 ein verschlüsseltes Summenbit der Ordnung i + 1 ist;

    wobei b'i ein verschlüsseltes Operandenbit des zweiten Operanden der Ordnung i ist; wobei c'i ein verschlüsseltes Übertragbit der Ordnung i ist, und wobei ti ein Umverschlüsselungs-Schlüssel für die Ordnung i ist, der durch XOR- Verknüpfung eines Verschlüsselungsparameters ki für die Ordnung i und eines Verschlüsselungsparameters ki+1 für die Ordnung i + 1 berechenbar ist.
  8. 8. Carry-Save-Multiplizierer nach Anspruch 5, 6 oder 7,

    bei dem die Umverschlüsselungseinrichtung (20i) für die Ordnung i und der Ein-Bit-Volladdierer (16i) für die Ordnung i kombiniert sind und eine Einrichtung zum Berechnen eines verschlüsselten Übertragbits (c'iout) aufweisen, durch die folgende Gleichung ausführbar ist:



    C'iout = [s'i+1 ⊕ ti]bi' + ci'.[s'i+1 ⊕ ti] + ci'.bi'



    wobei s'i ein verschlüsseltes Summenbit der Ordnung i ist, wobei s'i+1 ein verschlüsseltes Summenbit der Ordnung i + 1 ist, wobei b'i ein verschlüsseltes Operandenbit des zweiten Operanden der Ordnung i ist, wobei c'iout ein verschlüsseltes Übertragbit der Ordnung i ist, und wobei ti ein Umverschlüsselungs-Schlüssel für die Ordnung i ist, der durch XOR- Verknüpfung eines Verschlüsselungsparameters ki für die Ordnung i und eines Verschlüsselungsparameters ki+1 für die Ordnung i + 1 berechenbar 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

Patent Zeichnungen (PDF)

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