In typischen CPUs stellt die Schiebeoperation eine wichtige Funktion dar. Dadurch können beispielsweise Multiplikations- oder Divisionsalgorithmen implementiert werden. Bekannte CPUs arbeiten mit Klartextdaten, die um n Positionen nach links oder rechts geschoben oder rotiert werden können. Hierfür stehen unterschiedliche Schiebewerke, wie z. B. Barrel- Shifter oder logarithmische Shifter, zur Verfügung. Im allge- meinen handelt es sich um einen Permutator, der ein beliebi- ges Bit von Position i auf Position j bringt.

Nachteilig an solchen Schiebevorrichtungen für bekannte CPUs ist, daß sie nur mit Klartextdaten korrekt arbeiten. Hier- durch werden Angriffsmöglichkeiten relevant, die entweder auf Nadelangriffen (Probing) oder auf einer einfachen Leistung- analyse (SPA ; SPA = Simple Power Analysis) oder einer Diffe- renz-Leistungsanalyse (DPA ; DPA = Differential Power Analy- sis) basieren. Um in Prozessoren die Sicherheit gegenüber solchen Angriffen zu verbessern, wurde bereits eine Busver- schlüsselung eingeführt. Dies bedeutet, daß Daten, die auf Bussen übertragen werden, verschlüsselt sind und, bevor sie in die CPU eingespeist werden, entschlüsselt werden, damit die CPU korrekte Rechenoperationen im Klartextraum ausführen kann. Das Ergebnis einer Operation wird dann wieder ver- schlüsselt und in verschlüsseltem Zustand über einen Bus ent- weder zu einem Cache oder einem externen Speicher (extern be- züglich der CPU) übertragen.

Damit wird es einem Angreifer unmöglich gemacht, Daten, die auf einem internen Bus transportiert werden, abzuhören, da er, wenn er abhören möchte, lediglich die verschlüsselten Da- ten erhält. Greift der Angreifer jedoch den Eingang oder den Ausgang des Rechenwerks an, oder Zwischenzustände im Rechen- werk, so kann er Klartextdaten abhören, da das Rechenwerk im Klartextraum arbeitet. Obgleich die dort abzuhörenden Struk- turen wesentlich kleiner und weniger regelmäßig sind als Bus- strukturen, stellt dies doch einen Angriffspunkt dar.

Die Aufgabe der vorliegenden Erfindung besteht darin, ein si- chereres Konzept zum Verschieben von Daten zu schaffen.

Diese Aufgabe wird durch eine Schiebevorrichtung gemäß Pa- tentanspruch 1 oder durch ein Verfahren gemäß Patentanspruch 7 gelöst.

Der vorliegenden Erfindung liegt die Erkenntnis zugrunde, daß die Schiebeoperation im Geheimtextraum, d. h. mit verschlüs- selten Daten, durchgeführt werden muß, um die Angriffspunkte zu vermeiden, bei denen Daten im Klartextraum vorliegen.

Nachdem unterschiedliche Stellen des Datenworts unterschied- lich verschlüsselt sind, muß zusätzlich zu einer Schiebeope- ration einer ersten Stelle eines Datenworts an eine zweite Stelle eines Datenworts eine Umverschlüsselung stattfinden, und zwar dahingehend, daß die Stelle des Datenworts, die mit einem Verschlüsselungsparameter für die erste Stelle ver- schlüsselt in die Schiebevorrichtung eingespeist wird, mit dem Verschlüsselungsparameter für die zweite Stelle ver- schlüsselt die Schiebevorrichtung verläßt. Zu diesem Zweck ist eine Umverschlüsselungsvorrichtung der ersten Stelle von einer Verschlüsselung unter Verwendung des ersten Verschlüs- selungsparameters in einer Verschlüsselung unter Verwendung des Verschlüsselungsparameters vorgesehen. Die Reihenfolge der Schiebeoperation und Umverschlüsselungsoperation ist prinzipiell beliebig. So ist es möglich, die erste Stelle zu- nächst umzuverschlüsseln und dann zu verschieben. Alternativ

kann jedoch auch die erste Stelle zunächst verschoben werden und dann umverschlüsselt werden.

Vorzugsweise wird die Umverschlüsselung derart durchgeführt, daß während der Umverschlüsselung keine Klartextdaten vorlie- gen. Dies wird dadurch erreicht, daß eine Entschlüsselung der ersten Stelle in den Klartextraum unter Verwendung des ersten Verschlüsselungsparameters und eine Verschlüsselung der im Klartextraum vorliegenden ersten Stelle unter Verwendung ei- nes Verschlüsselungsparameters für die zweite Stelle in eine Operation zusammengefaßt werden, bei der als Zwischenergeb- nisse keine Klartextdaten auftreten.

Vorzugsweise wird als Verschlüsselungsalgorithmus eine bit- weise XOR-Verknüpfung oder XNOR-Verknüpfung mit einem Ver- schlüsselungsparameter eingesetzt, wobei die Verschlüsse- lungsparameter für die einzelnen Stellen des Datenworts von- einander unabhängig sind. Eine Umkehrung der XOR-Operation bzw. der XNOR-Operation entspricht wieder der XOR-bzw. XNOR- Operation. Eine Umverschlüsselung von einer Verschlüsselung mit einem ersten Verschlüsselungsparameter in eine Verschlüs- selung mit einem zweiten Verschlüsselungsparameter kann bei Anwendung der XOR-Funktion schaltungstechnisch einfach und mit geringem Platzbedarf dadurch erreicht werden, daß ein Um- verschlüsselungs-Schlüssel berechnet wird, der einer XOR- Verknüpfung bzw. XNOR-Verknüpfung des ersten Verschlüsse- lungsparameters und des zweiten Verschlüsselungsparameters entspricht. Die Umverschlüsselung wird dann dadurch erreicht, daß die mit dem ersten Verschlüsselungsparameter verschlüs- selte erste Stelle des Datenworts mit dem Umverschlüsse- lungsschlüssel XOR-bzw. XNOR-verknüpft wird, um eine Stelle des Datenworts zu erhalten, die mit dem zweiten Verschlüsse- lungsparameter für die zweite Stelle verschlüsselt ist. Bei der XOR-bzw. XNOR-Verknüpfung mit dem Umverschlüsselungs- Schlüssel treten keine Klartextdaten auf, so daß ein Angrei- fer keine Chance hat, an irgendeiner Stelle der Schiebevor- richtung Klartextdaten zu hören.

Zum Verschlüsseln können sämtliche umkehrbaren Algorithmen eingesetzt werden. Aus Geschwindigkeitsgründen wird jedoch die XOR-bzw. XNOR-Verschlüsselung bevorzugt.

Erfindungsgemäß werden nunmehr ausschließlich verschlüsselte Daten verschoben. Dadurch werden die Angriffsmöglichkeiten erheblich eingeschränkt.

Bevorzugte Ausführungsbeispiele der vorliegenden Erfindung werden nachfolgend Bezug nehmend auf die beiliegenden Zeich- nungen detailliert erläutert. Es zeigen : Fig. 1 ein Blockschaltbild einer erfindungsgemäßen Schie- bevorrichtung ; Fig. 2 eine erfindungsgemäße Schiebevorrichtung gemäß ei- nem bevorzugten Ausführungsbeispiel der vorliegen- den Erfindung, bei dem die Umverschlüsselung vor der Verschiebung durchgeführt wird ; und Fig. 3 ein Blockschaltbild eines bevorzugten Ausführungs- beispiels der vorliegenden Erfindung, bei dem die Umverschlüsselung nach der Verschiebung durchge- führt wird.

Fig. 1 zeigt eine erfindungsgemäße Schiebevorrichtung, die eine Mehrzahl von Eingängen für verschlüsselte Stellen do', du',... eines Datenworts aufweisen, das aus einer oder meh- reren verschlüsselten Stellen do'... gebildet ist. Jeder Eingang hat eine bestimmte Wertigkeit, wobei hier beispiels- weise im binären Zahlensystem die Wertigkeiten 2°, 21,... in Fig. 1 angegeben sind. Ferner ist jede Stelle des Datenworts d unter Verwendung eines dieser Stelle zugeordneten Ver- schlüsselungsparameters ko, kl, k2,..., verschlüsselt. Dies bedeutet, daß die Stelle des Datenworts do'mit dem Ver- schlüsselungsparameter ko verschlüsselt ist, während die

Stelle des Datenworts d3 beispielsweise nicht mit dem Ver- schlüsselungsparameter ko, sondern mit dem Verschlüsselungs- parameter k3 verschlüsselt ist. An dieser Stelle sei ange- merkt, daß verschlüsselte Größen mit einem Apostroph gekenn- zeichnet sind.

Die erfindungsgemäße Vorrichtung umfaßt ferner eine Einrich- tung 10 zum Verschieben einer ersten Stelle des Datenworts an eine zweite Stelle des Datenworts, eine Einrichtung 12 zum Umverschlüsseln der ersten Stelle von einer Verschlüsselung unter Verwendung des Verschlüsselungsparameters für die erste Stelle in eine Verschlüsselung unter Verwendung des Ver- schlüsselungsparameters, der der zweiten Stelle zugeordnet ist. Die erfindungsgemäße Schiebevorrichtung umfaßt ferner eine Steuereinrichtung 14, die eine Ablaufsteuerung der Ein- richtung zum Verschieben 10 und der Einrichtung zum Um- verschlüsseln 12 durchführt, daß entweder die erste Stelle zunächst an die zweite Stelle geschoben wird, und daß dann eine Umverschlüsselung vorgenommen wird, oder daß zunächst die verschlüsselte erste Stelle des Datenworts umverschlüs- selt wird, und daß dann der umverschlüsselte Wert an die zweite Stelle geschoben wird. Der Steuerung 14 ist über einen Steuereingang 16 ein Schiebebetrag zuführbar, der angibt, um wieviel Stellen ein Wort verschoben werden soll bzw. eine Stelle eines Worts verschoben werden soll. Die Einrichtung 12 zum Umverschlüsseln umfaßt ferner einen Schlüsseleingang 18, über den dieselbe die Schlüssel für die unterschiedlichen Stellen, also die Verschlüsselungsparameter, die den einzel- nen Stellen bzw. Eingängen zugeordnet sind, erhalten kann.

Die erfindungsgemäße Schiebevorrichtung umfaßt ferner eine Mehrzahl von Ausgängen, denen eine bestimmte Wertigkeit 2°, 21, 22... zugeordnet ist, und denen, ebenso wie den Eingän- gen, die Verschlüsselungsparameter ko, k1,... zugeordnet sind.

Im nachfolgenden wird anhand eines Beispiels die Verschiebung eines-Datenworts anhand von Fig. 1 dargelegt. Es wird davon ausgegangen, daß das verschlüsselte Datenwort d'drei Stellen hat, nämlich do', t d1 und d2. Der am Eingang 16 eingegebene Schiebebetrag beträgt +2, d. h. die drei Stellen des ver- schlüsselten Datenworts am Eingang der in Fig. 1 gezeigten Vorrichtung sollen jeweils um zwei Stellen nach rechts, d. h. zu höherwertigen Stellen, verschoben werden. Hierzu benötigt die Einrichtung 12 zum Umverschlüsseln die Schlüssel für die betroffenen Stellen, nämlich ko, kl und k2, da dies die Stel- len des Eingangs-Datenworts sind, die von der Schiebeoperati- on betroffen sind, und zusätzlich die Schlüssel k3 und k4, da dies die Stellen sind, die aufgrund der Verschiebung um zwei Bit nach rechts neu belegt werden.

Für das dargestellte Beispiel sei angenommen, daß die Daten mit den jeweiligen Verschlüsselungsparametern bitweise XOR- verschlüsselt sind, d. h. dj/= di XOR ki. Prinzipiell ist je- doch jedes beliebige andere umkehrbare Verschlüsselungsver- fahren anwendbar.

Der Umverschlüsselungs-Schlüssel zum Umverschlüsseln der ers- ten Stellen do von der Wertigkeit 2° zur Wertigkeit 22 ist gleich einer XOR-Verknüpfung von ko mit k2. Der Umverschlüs- selungs-Schlüssel für die eingangsseitige Stelle mit der Wer- tigkeit 21 lautet analog dazu kl XOR k3. Schließlich lautet der Umverschlüsselungs-Schlüssel um das Eingangsdatenbit d2' zu verschieben : d24 = ka XOR k4. Prinzipiell ist es unerheb- lich, ob die Daten zunächst umverschlüsselt werden und dann verschoben werden, oder ob die Daten zunächst verschoben wer- den und dann umverschlüsselt werden. Auf jeden Fall wird si- chergestellt, daß immer verschlüsselte Daten verschoben wer- den. Dies ist insbesondere bei größeren Schiebern von beson- derer Bedeutung, da hier Leitungslängen von einem Eingang zu einem Ausgang durchaus beträchtliche Werte annehmen können und somit relativ leicht abhörbar sind. Die erfindungsgemäße Schiebevorrichtung stellt jedoch sicher, daß immer nur ver-

schlüsselte Daten (entweder gemäß dem eingangsseitigen Ver- schlüsselungsparameter oder gemäß dem ausgangsseitigen Ver- schlüsselungsparameter) verschoben werden. Obgleich es bevor- zugt wird, eine Umverschlüsselung derart durchzuführen, daß während der Umverschlüsselung keine Klartextdaten berechnet werden (in diesem Fall besteht kein Angriffspunkt auf Klar- textdaten mehr), wird jedoch auch in dem Fall eine Sicher- heitssteigerung erreicht, bei dem die Umverschlüsselung der- art vor sich geht, daß zunächst eine Entschlüsselung unter Verwendung des ersten Verschlüsselungsparameters durchgeführt wird, und daß dann eine Verschlüsselung unter Verwendung ei- nes zweiten Verschlüsselungsparameters durchgeführt wird, wo- bei zwischen Entschlüsselung und Verschlüsselung Klartextda- ten vorliegen. Auch in diesem Fall werden lediglich ver- schlüsselte Daten verschoben, und die Klartextdaten liegen lediglich innerhalb der Umverschlüsselungseinheit vor. Das Ausspähen dieser Daten beispielsweise mittels eines Nadelan- griffs ist ungleich schwieriger als das Ausspähen von unver- schlüsselt verschobenen Daten.

Es sei darauf hingewiesen, daß Fig. 1 lediglich beispielhaft eine Verschiebung aller Bits um eine Position darstellt. Der erfindungsgemäße Schieber kann als allgemeiner Permutator wirken, bei dem beliebige Bits an beliebige Stellen gebracht werden, wobei immer die entsprechende Umverschlüsselung be- rücksichtigt wird, damit die korrekte Schlüsselbasis vor- liegt. Bei einem Permutator kann auch der Fall auftreten, daß ein Bit nicht verschoben wird. In diesem Fall muß auch nichts umverschlüsselt werden.

Fig. 2 zeigt eine bevorzugte Ausführungsform für eine erfin- dungsgemäße Schiebevorrichtung mit bitweiser XOR- Verschlüsselung und Umverschlüsselung vor der Verschiebung.

Insbesondere ist in Fig. 2 ein Bit-Slice gezeigt, nämlich für das verschlüsselte Bit des Eingangsdatenwortes di'. Die Um- verschlüsselungseinrichtung umfaßt eine Anzahl von XOR-

Gattern 20,21, 22 und 23. Die Einrichtung zum Verschieben umfaßt eine Anzahl von Schiebeeinrichtungen, die eine Ver- schiebung um links (SHL ; SHL = shift left) oder eine Ver- schiebung nach rechts (SHR ; SHR = shift right) ermöglichen.

Das in Fig. 2 gezeigte Prinzip eines verschlüsselten Barrel- Shifters benötigt für jedes Bit zusätzlich (n-1) Dreifach- XOR-Gatter. Für eine 32-Bit-CPU wären das 32 x (n-1) Drei- fach-XOR-Gatter an Zusatzaufwand, wobei die Zahl n angibt, um wieviel Stellen eine Verschiebung nach links bzw. rechts ma- ximal möglich ist.

Anstelle einer Umverschlüsselung vor der Schiebeoperation, wie es in Fig. 2 dargestellt ist, kann auch eine Umverschlüs- selung nach der Schiebeoperation erreicht werden. Dies ist in Fig. 3 anhand eines Bit-Slices für eine verschlüsselte Stelle di des Datenworts dargestellt. Zunächst wird der verschlüs- selte Wert di'um n Bit geshiftet und dann mittels des ent- sprechenden Umverschlüsselungs-Schlüssels umverschlüsselt.

Die Notation d (i+2n, _ (n) bedeutet, daß das Datenbit an der Stelle i+2n um n Positionen nach rechts verschoben wurde.

Dieses Zwischenergebnis benötigt noch die Umverschlüsselung- soperation mit dem Umverschlüsselungs-Schlüssel tij, der sich aus einer XOR-Verknüpfung der beiden betroffenen Verschlüsse- lungsparameter für die beiden betroffenen Stellen, also die Ursprungsstelle und die Zielstelle, ergibt. Gleichungsmäßig bedeutet dies für das Ergebnisbit : rj = (di « n) XOR tij Bei dieser Lösung wird für jedes Bit des Resultats ri zusätz- lich ein dreifaches XOR-Gatter 30 sowie ein n-in-1- Multiplexer 32 benötigt. Ferner werden, wie es auch bei Fig.

2 der Fall war, entsprechende Verschiebungseinrichtungen 24, 25,26 und 27 benötigt, die den entsprechenden Elementen in Fig. 2 entsprechen.

Es sei darauf hingewiesen, daß sich beliebige Shiftalgo- rithmen auf der Basis der vorstehenden Details implementieren lassen, beispielsweise logarithmische Schieber, etc. Eine Spezialoperation der Verschiebung ist die Rotation eines Worts. Wenn ein Datenwort um eine Stelle nach rechts rotiert werden soll, bedeutet dies, daß das niederstwertige Bit (lsb) des Datenworts vor der Rotation zum höchstwertigen Bit (msb) des Datenworts nach der Rotation wird. Die erste Stelle ist dann das niederstwertige Bit des Datenworts, und die zweite Stelle ist das höchstwertige Bit des Datenworts. Der Um- verschlüsselungs-Schlüssel berechnet sich dann auf der Ver- knüpfung des Verschlüsselungsparameters für das höchstwertige Bit und des Verschlüsselungsparameters für das niederstwerti- ge Bit.

Der erfindungsgemäße Schieber kann auch in Kombination mit einer kompletten ALU verwendet werden, die mit verschlüssel- ten Daten rechnet, um komplexere Operationen, wie z. B. das Extrahieren von k Bit aus einem Register und Einfügen in ein anderes Register an anderer Bitposition durchzuführen. Allge- mein ausgedrückt fungiert der erfindungsgemäße Schieber als Permutator, der beliebige Bitpositionen vertauschen kann.

Insbesondere kann bei einem allgemeinen Permutator der Fall auftreten, dass bestimmte Bitpositionen verschoben werden, und damit umverschlüsselt werden müssen, während wieder ande- re Bitpositionen nicht verschoben werden, und damit auch nicht umverschlüsselt werden müssen.

Es existieren unterschiedliche Möglichkeiten, wie die Bits behandelt werden sollen, die durch die Verschiebung frei wer- den, wie z. B. das Bit mit der Wertigkeit 2° und 21 von Fig.

1. Sollen-im Klartextraum-hier Nullen eingefügt werden, so wären die Nullen im Geheimtextraum mit den Schlüsseln ko für die niederstwertige Stelle und kl für die höherwertigere Stelle zu verschlüsseln. Sollen dagegen beispielsweise aus Vorzeichengründen, Einsen eingefügt werden, so wären diese Einsen ebenfalls mit den Schlüsseln für die entsprechenden

Stellen zu verschlüsseln. Wird ferner der Schiebebetrag selbst verschlüsselt, beispielsweise unter Verwendung eines eigenen Verschlüsselungsparameters bzw. eines Verschlüsse- lungsparameters für die Eingänge, so wäre es einem Angreifer nicht einmal mehr möglich, festzustellen, ob bzw. um wieviel verschoben worden ist. Nachdem hinzugefügte Nullen oder Ein- sen auf nicht benötigten bzw. frei gewordenen Bitleitungen ebenfalls verschlüsselt sind, ist aus dem Ausgangsbitmuster nicht unbedingt zu ersehen, was innerhalb des verschlüsselten Shifters stattgefunden hat.

Bezugszeichenliste 10 Einrichtung zum Verschieben 12 Einrichtung zum Umverschlüsseln 14 Steuerung 16 Schiebebetrageingang 18 Schlüsseleingang 20 erstes XOR-Gatter 21 zweites XOR-Gatter 22 drittes XOR-Gatter 23 viertes XOR-Gatter 24 erster Schieber 25 zweiter Schieber 26 dritter Schieber 27 vierter Schieber 30 Ausgangs-XOR-Gatter 32 Multiplexer