PatentDe  


Dokumentenidentifikation DE69931606T2 08.03.2007
EP-Veröffentlichungsnummer 0001052611
Titel DATENWANDLER UND AUFZEICHNUNGSMEDIUM ZUR AUFNAHME EINES PROGRAMMS ZUR DATENUMWANDLUNG
Anmelder Nippon Telegraph and Telephone Corp., Tokio/Tokyo, JP
Erfinder KANDA, Nippon Telegraph and Teleph.Corp., Masayuki, Tokyo 163-1419, JP;
TAKASHIMA, Nippon Telegr. and Telep.Corp., Youichi, Tokyo 163-1419, JP;
AOKI, Nippon Telegraph and Teleph.Corp., Kazumaro, Tokyo 163-1419, JP;
UEDA, Nippon Telegraph and Telephone Corp., Hiroki, Tokyo 163-1419, JP;
OHTA, Nippon Telegraph and Telephone Corp., Kazuo, Tokyo 163-1419, JP;
MATSUMOTO, Tsutomu, Kanagawa 227-0048, JP
Vertreter Hoffmann, E., Dipl.-Ing., Pat.-Anw., 82166 Gräfelfing
DE-Aktenzeichen 69931606
Vertragsstaaten DE, FR, GB, IT
Sprache des Dokument EN
EP-Anmeldetag 27.01.1999
EP-Aktenzeichen 999018849
WO-Anmeldetag 27.01.1999
PCT-Aktenzeichen PCT/JP99/00337
WO-Veröffentlichungsnummer 1999038143
WO-Veröffentlichungsdatum 29.07.1999
EP-Offenlegungsdatum 15.11.2000
EP date of grant 31.05.2006
Veröffentlichungstag im Patentblatt 08.03.2007
IPC-Hauptklasse G09C 1/00(2006.01)A, F, I, 20051017, B, H, EP
IPC-Nebenklasse H04L 9/06(2006.01)A, L, I, 20051017, B, H, EP   

Beschreibung[de]
TECHNISCHES FACHGEBIET

Die vorliegende Erfindung betrifft eine Transformationsvorrichtung, die in einer Verschlüsselungsvorrichtung zum Verstecken von Daten bei der Datenkommunikation oder -speicherung verwendet wird, und insbesondere eine Datentransformationsvorrichtung, die zur Verwendung in einer Verschlüsselungsvorrichtung mit Verschlüsselungsalgorithmus mit geheimem Schlüssel geeignet ist, die Datenblöcke unter Verwendung eines geheimen Schlüssels verschlüsselt oder entschlüsselt, und ein Speichermedium, auf dem ein Programm gespeichert ist, das von der Transformationsvorrichtung auszuführen ist.

STAND DER TECHNIK

Im Hinblick auf die Erstellung eines schnellen und sicheren Verschlüsselungsalgorithmus mit geheimem Schlüssel wird eine Blockchiffre verwendet, gemäß derer die zu verschlüsselnden Daten in Blöcke mit angemessener Länge aufgeteilt und blockweise verschlüsselt werden. Im Allgemeinen umfasst die Blockchiffre ein Datendiffusionsteil, das die zu verschlüsselnden Eingabedaten randomisiert, und ein Schlüssel-Planungsteil, das mit einem geheimen gemeinsamen Schlüssel (nachfolgend als Hauptschlüssel bezeichnet) versorgt wird, der in die Verschlüsselungsvorrichtung eingegeben wird, und eine Folge von Unterschlüsseln zur Verwendung durch das Datendiffusionsteil erzeugt. Ein typischer Verschlüsselungsalgorithmus mit geheimem Schlüssel, der in der Datentransformationsvorrichtung zum Verstecken von Daten verwendet wird, ist DES (Data Encryption Standard), der der FIPS-anerkannte Verschlüsselungsalgorithmus war.

1 veranschaulicht die funktionale Konfiguration von DES. DES verwendet einen 64-Bit Geheimschlüssel (8 Bits werden für die Parität verwendet) und verschlüsselt oder entschlüsselt Daten in Blöcken von 64 Bits. In 1 wird das Verschlüsselungsverfahren in einem Datendiffusionsteil 10 durchgeführt, das mit einer anfänglichen Permutation von 64 Bits eines Klartextes M in einem Anfangs-Permutationsteil 11 beginnt, gefolgt von einer Teilung der permutierten Daten in zwei Stück 32-Bit-Block-Daten L0 and R0. Die Blockdaten R0 werden in ein Funktions-Betriebsteil (auch als Rundenfunktion bezeichnet) 12 eingegeben, das ein Datentransformationsteil ist, das als ein i-tes Runden-Verarbeitungsteil 14i (i = 0, 1, ..., 15) in 2 gezeigt ist, in welchem sie unter Verwendung eines 48-Bit-Unterschlüssels k0 zu f(R0, k0) transformiert werden. Die auf diese Weise transformierten Daten f(R0, k0) und die Blockdaten L0 werden in einer XOR-Schaltung 13 Exklusiv-Oder-verknüpft, und deren Ausgabe und die Blockdaten R0 werden vertauscht, um die nächsten Blockdaten L1, R1 zu erhalten. Diese sind: wobei ein Exklusiv-Oder darstellt. Ein 0-tes Runden-Verarbeitungsteil 140 weist das Funktions-Betriebsteil 12 und die XOR-Schaltung 13 auf und tauscht die zwei Stück Blockdaten aus, um die zwei Stück ausgegebene Blockdaten L1 und R1 bereitzustellen; ähnliche Runden-Verarbeitungsteile 141 bis 1415 sind in einer Kaskade bereitgestellt. Die Verarbeitung durch das i-te Runden-Verarbeitungsteil 14i wird im Weiteren als i-te Verarbeitung bezeichnet, wobei i = 0, 1, ..., 15. Damit führt jedes Runden-Verarbeitungsteil 14i (wobei 0 ≤ i ≤ 15) die folgende Verarbeitung durch Ri+1 = Li ⨁ f(Ri, ki) Li+1 = Ri

Und schließlich die Verkettung von zwei Stück Daten R16 und L16 in 64-bit-Daten, die in einem End-Permutationsteil 15 permutiert werden, um einen 64-Bit-Chiffretext bereitzustellen. Übrigens entspricht die Bearbeitung durch das Schluss-Permutationsteil 15 einer umgekehrten Transformation der Bearbeitung durch das Anfangs-Permutationsteil 11.

Das Entschlüsselungsverfahren kann durchgeführt werden, indem das gleiche Verfahren wie bei dem Verschlüsselungsverfahren durchgeführt wird, mit der Ausnahme, dass die Unterschlüssel k0, k1, ..., k14, k15 in die Funktion f (in das Funktions-Betriebsteil 12) in der Reihenfolge k15, k14, ..., k1, k0 eingegeben werden, welche umgekehrt ist zu derjenigen des Verschlüsselungsverfahrens. In einem derartigen Fall werden die Ausgaben L16 und R16 des letzten Runden-Verarbeitungsteils 14 15, wie dargestellt, weiter vertauscht; und in dem Entschlüsselungsverfahren wird der Chiffretext in das Anfangs-Permutationsteil 11 zur Ausführung des Verfahrens von 1 eingegeben, durch das der Klartext an der Ausgabe des End-Permutationsteils 15 intakt bereitgestellt wird. In einem Schlüssel-Planungsteil 20 führt ein Expansionsschlüssel-Erzeugungsteil 21 Folgendes aus: es teilt einen Hauptschlüssel von 64 Bits, ausgenommen 8 Bits, die für die Parität verwendet werden, in zwei Stück rechte und linke Schlüsseldaten von 28 Bit auf; führt dann eine 16-Runden-Vertauschung der zwei Stück linke und rechte 28-Bit-Schlüsseldaten durch; und führt eine reduzierte Permutation der permutierten rechten und linken Daten (insgesamt 56 Bits) durch, die aus den entsprechenden Runden erhalten wurden, um 16 Unterschlüssel k0, k1, ..., k14, k15 mit 48 Bits zu erzeugen, die zu den entsprechenden Runden-Verarbeitungsteilen des Datendiffusionsteils 10 geliefert werden.

Die Verarbeitung in dem Funktions-Betriebsteil 12 wird wie in 2 dargestellt durchgeführt. Vorab werden die 32-Bit Blockdaten Ri in einem erweiterten Permutationsteil 17 zu 48-Bit Daten E(Ri) transformiert. Diese Ausgabedaten und der Unterschlüssel ki werden in einer XOR-Schaltung 18 Exklusiv-Oder-verknüpft, deren Ausgabe zu 48-Bit Daten E(Ri)⨁ki transformiert wird, welche dann in acht Stück 6-Bit Unterblockdaten aufgeteilt werden. Die acht Stück 6-Bit-Unterblockdaten werden in verschiedene S-Boxen S0 bis S7 eingegeben, um hiervon eine jeweilige 4-Bit-Ausgabe zu erhalten. Übrigens handelt es sich bei der S-Box Sj (wobei j = 0, 1, ..., 7) um eine nichtlineare Transformationstafel, die die 6 Bit Eingabedaten in die 4 Bit Ausgabedaten umwandelt, und sie ist ein wesentliches Teil, das die Sicherheit von DES liefert. Die acht Stück Ausgabedaten aus den S-Boxen S0 bis S7 werden wiederum zu 32-Bit-Daten verkettet, die in ein Permutationsteil 19 eingegeben werden, um die Ausgabe f(Ri, ki) des in 2 gezeigten Funktions-Operationsteils bereitzustellen. Diese Ausgabe wird mit Li Exklusiv-Oder-verknüpft, um Ri+1 zu erhalten.

Als nächstes erfolgt eine Beschreibung von Verschlüsselungsanalysetechniken. Eine Vielzahl von Verschlüsselungsanalysetechniken wurden für DES und andere übliche Verschlüsselungsalgorithmen mit geheimem Schlüssel vorgeschlagen; sehr wirksame Verschlüsselungsanalysetechniken darunter sind die Differentialverschlüsselungsanalyse, die von E. Biham und A. Shamir, („Differential Cryptanalysis of DES-like Cryptosystems", Journal of Cryptology, Vol. 4, No. 1, pp.3–72) vorgeschlagen wurde, und lineare Verschlüsselungsanalyse, die von Matsui, ("Linear Cryptanalysis Method for DES cipher", Advances in Cryptology-EUROCRYPT' 93 (Lecture Notes in Computer Science 765), pp. 386–397.) vorgeschlagen wurde.

Unter der Annahme, dass die Differenz zwischen zwei Stück Daten X und X* definiert ist als &Dgr;X = X ⨁ X*, zielt die Differential-Verschlüsselungsanalyse darauf ab, den Unterschlüssel k15 in dem letzten Rundenverarbeitungsteil 1415 zu erhalten, indem zwei Sätze von Klartext-Chiffretext-Paaren, die ein Angreifer besitzt, auf die folgenden Gleichungen angewendet werden. Bei dem Verschlüsselungsverfahren von 1 stellen (Li, Ri) und (L*i, R*i) Eingabedaten in das Rundenverarbeitungsteil 14i für erste bzw. zweite Klartexte dar. Mit der oben definierten Differenz gelten die folgenden Gleichungen. &Dgr;Li = Li ⨁ L*i &Dgr;Ri = Ri ⨁ R*i

Da in 1 L15 = R14, L*15 = R*14, L16 = R15 und L*16 = R*15, gelten die folgenden Gleichungen R16 = L15 ⨁ f(R15, k15) R*16 = L*15 ⨁ f(R*15, k15), und das Exklusiv-Oder beider Seiten dieser Gleichungen wird wie folgt erhalten: &Dgr;R16 = &Dgr;L15 ⨁ f(L16, k15) ⨁ f(L16⨁&Dgr;L16, k15).

Die Exklusiv-Oder-Verknüpfung ihrer beiden Seiten mit &Dgr;R14 = &Dgr;L15 ergibt die folgende Gleichung: f(L16, k15) ⨁ f(L16&Dgr;L16, k15) = &Dgr;R16 ⨁ &Dgr;R14.

Diesmal handelt es sich, da L16, &Dgr;L16 und &Dgr;R16 von dem Chiffretext zu erhalten sind, um bekannte Informationen. Wenn daher der Angreifer &Dgr;R14 korrekt erhalten kann, dann ist in der obigen Gleichung nur k15 eine unbekannte Konstante; der Angreifer kann ein korrektes k15 unweigerlich durch eine eingehende Suche nach k15 unter Verwendung der bekannten Sätze von Klartext-Chiffretext-Paaren herausfinden. Wird demnach einmal der Unterschlüssel k15 gefunden, so können sogar die verbleibenden acht Bits (d.h. 56–48) auf einfache Weise durch eine weitere eingehende Suche erhalten werden.

Andererseits ist es im Allgemeinen schwierig, &Dgr;R14 zu erhalten, da dieser Wert ein Differenz-Zwischenwert ist. Dann soll angenommen werden, dass jede Rundenverarbeitung mit den folgenden Gleichungen mit einer Wahrscheinlichkeit pi in der 0-ten bis vorletzten Runde (d.h. der 14-ten) angenähert wird: &Dgr;Ri+1 = &Dgr;Li ⨁ &Dgr;{f(&Dgr;Ri)} &Dgr;Li+1 = &Dgr;Ri+1.

Es geht darum, dass, wenn ein bestimmtes &Dgr;Ri in das i-te Runden-Verarbeitungsteil eingegeben wird, &Dgr;{f(&Dgr;Ri)} mit einer der Wahrscheinlichkeit pi vorhergesagt werden kann, ungeachtet des Wertes des Unterschlüssels ki. Der Grund, weshalb derartige Näherungen vorgenommen werden können, ist, dass die S-Boxen, die nichtlineare Transformationentafeln sind, eine extrem ungleiche Verteilung von Ausgabedifferenzen für die gleichen Eingabedifferenzen liefern. Beispielsweise wird in der S-Box S0 eine Eingabedifferenz "110100(2)" zu einer Ausgabedifferenz "0010(2)" mit einer Wahrscheinlichkeit von R transformiert. Dann wird die Näherung für jede Runde erhalten, indem angenommen wird, dass jede der S-Boxen in der Lage ist, die Verbindung zwischen der Eingabedifferenz und der Ausgabedifferenz mit einer Wahrscheinlichkeit von Psi vorherzusagen, und diese miteinander kombiniert werden. Des Weiteren ermöglicht die Verkettung derartiger Näherungen in den entsprechenden Runden, &Dgr;R14 aus &Dgr;L0 und &Dgr;R0 (&Dgr;L0 und &Dgr;R0 sind Daten, die von dem Klartext ableitbar und daher bekannt sind) mit einer Wahrscheinlichkeit von P = &Pgr;i=0 13pi zu erhalten. Übrigens, je größer die Wahrscheinlichkeit P ist, desto einfacher ist die Verschlüsselungsanalyse. Nachdem der Unterschlüssel k15 auf diese Weise erhalten wurde, wird eine ähnliche Berechnung des Unterschlüssels k14 durchgeführt, indem dieser als 15-Runden DES betrachtet wird, dies ist eine Runde weniger als oben; derartige Operationen werden wiederholt, um die Unterschlüssel einen nach dem anderen bis k0 zu erhalten.

Es hängt von der Wahrscheinlichkeit P ab, ob diese Verschlüsselungsanalyse erfolgreich ist: je höher die Wahrscheinlichkeit P ist, desto wahrscheinlicher ist der Erfolg. Biham et al. sagen, dass DES mit dieser Verschlüsselungsanalyse geknackt werden kann, falls 247 Sätze gewählter Klartext-Chiffretext-Paare verfügbar sind.

Die lineare Verschlüsselungsanalyse zielt darauf ab, Unterschlüssel zu erhalten, indem folgende lineare Näherungsgleichung aufgestellt wird und das Maximum-Likelihood-Verfahren mit Sätzen bekannter Klartext-Chiffretext-Paare angewendet wird, die ein Angreifer besitzt. (L0, R0) &Ggr; (L0, R0) ⨁ (L16, R16) &Ggr; (L16, R16) = (k0, k1, ..., k15) &Ggr; (k0, k1, ..., k15), wobei &Ggr;(X) den Vektor repräsentiert, der eine bestimmte Bit-Position von X auswählt, und dieser wird als Maskenwert bezeichnet.

Die Aufgabe des linearen Näherungsausdrucks ist, den Verschlüsselungsalgorithmus durch den linearen Ausdruck ungefähr zu ersetzen und diesen aufzuteilen in einen Teil, der den Satz von Klartext-Chiffretext-Paaren betrifft, und in einen Teil, der die Unterschlüssel betrifft. Demnach nehmen bei den Sätzen von Klartext-Chiffretext-Paaren alle Exklusiv-Oder-Verknüpfungen zwischen den Werten an bestimmten Bitpositionen des Klartextes und denjenigen des Chiffriertextes einen festen Wert an, was angibt, dass dieser der Exklusiv-Oder-Verknüpfung der Werte an bestimmten Positionen der Unterschlüssel gleicht. Dies bedeutet, dass der Angreifer Informationen (k0, k1, ..., k15) &Ggr; (k0, k1, ..., k15) (ein Bit) aus Information (L0, R0) &Ggr; (L0, R0) ⨁ (L16, R16) &Ggr; (L16, R16) erhält.

Zu diesem Zeitpunkt sind (L0, R0) und (L16, R16) der Klartext bzw. der Chiffretext, und somit sind diese bekannt. Kann demnach der Angreifer &Ggr; (L0, R0), &Ggr; (L16, R16) und &Ggr; (k0, k1, ..., k15) korrekt erhalten, dann kann er (k0, k1, ..., k15) &Ggr; (k0, k1, ..., k15) (ein Bit) erhalten.

Bei DES führen nur die S-Boxen eine nichtlineare Transformation durch: können daher nur für die S-Boxen lineare Darstellungen gemacht werden, dann kann der lineare Näherungsausdruck auf einfache Weise konstruiert werden. Dann nehme man an, dass jede S-Box mit einer Wahrscheinlichkeit psi linear dargestellt werden kann. Der Punkt hierbei ist, dass, wenn der Eingabe-Maskenwert für die S-Box gegeben ist, sein Ausgabe-Maskenwert mit der Wahrscheinlichkeit psi vorhergesagt werden kann. Der Grund hierfür ist, dass die S-Boxen, die eine nichtlineare Transformationstafel bilden, eine extrem ungleiche Verteilung der Ausgabe-Maskenwerte entsprechend der Eingabe-Maskenwerte liefern. Zum Beispiel wird, wenn der Eingabe-Maskenwert in der S-Box S4 "010000(2)" ist, ein Ausgabe-Maskenwert "1111(2)" mit einer Wahrscheinlichkeit von 3/16 vorhergesagt. Durch Kombinieren der Maskenwerte in diesen S-Boxen kann eine lineare Darstellung jeder Runde mit den Eingabe- und Ausgabe-Maskenwerten mit einer Wahrscheinlichkeit pi gemacht werden, und durch Verketten der linearen Darstellungen der entsprechenden Runden werden &Ggr; (L0, R0), &Ggr; (L16, R16) und &Ggr; (k0, k1, ..., k15) mit der folgenden Wahrscheinlichkeit erhalten: P = 1/2 + 215&Pgr;i=015 |pi – 1/2|.

Je größer die Wahrscheinlichkeit P ist, desto leichter ist die Verschlüsselungsanalyse.

Matsui war nach eigenen Angaben bei der Analyse von DES mit dieser Verschlüsselungsanalyse unter Verwendung von 243 Sätzen bekannter Klartext-Chiffretext-Paare erfolgreich.

Um Chiffrierungen vor den obigen Verschlüsselungsanalysetechniken zu schützen, muss die Wahrscheinlichkeit P nur auf einen ausreichend kleinen Wert reduziert werden. Eine große Vielzahl von Vorschlägen wurden zur Verminderung der Wahrscheinlichkeit P gemacht, und der einfachste Weg, um eine erhöhte Sicherheit bei den herkömmlichen Verschlüsselungs- bzw. Chiffriersystemen bereitzustellen, ist, die Anzahl der Runden zu erhöhen. Zum Beispiel ist Dreifach-DES mit drei DES, die verkettet werden, ein Algorithmus der die Anzahl von Runden von 16 auf 48 wesentlich erhöht; und dies liefert eine weit geringere Wahrscheinlichkeit P als DES.

Durch eine Erhöhung der Anzahl von Runden im Hinblick darauf, die oben beschriebenen Verschlüsselungsanalysetechniken zu vermeiden, wird jedoch die Verschlüsselungsgeschwindigkeit unvermeidbar beeinträchtigt. Wenn zum Beispiel die Anzahl an Runden verdreifacht wird, wird die Verschlüsselungsgeschwindigkeit auf 1/3 reduziert. Da die Verschlüsselungsgeschwindigkeit des vorliegenden DES bei einem Pentium-PC ungefähr 10 Mbps beträgt, verringert sich die Verschlüsselungsgeschwindigkeit von Dreifach-DES auf ungefähr 3,5 Mbps. Andererseits werden Netzwerke und Computer Jahr für Jahr schneller, und daher besteht ein Wunsch nach Datentransformationsvorrichtungen, die mit diesen Geschwindigkeitssteigerungen Schritt halten. Mit gewöhnlichen Datentransformationsvorrichtungen ist es daher extrem schwierig, gleichzeitig die Anforderungen an die Sicherheit und an eine Steigerung der Geschwindigkeit zu erfüllen.

Darüber hinaus wird gemäß der Differential-Verschlüsselungsanalyse und der Linear-Verschlüsselungsanalyse der Unterschlüssel in der letzten Runde wie oben beschrieben erhalten. Da DES eine Schwachstelle besitzt, nämlich dass der Hauptschlüssel von dem Unterschlüssel auf einfache Weise in der letzten Runde abgeleitet werden kann, wird in dem US-Patent Nr. 4,850,019 vorgeschlagen: ein Verfahren, das eine erhöhte Sicherheit durch eine Erhöhung der Komplexität der Korrespondenz zwischen den Unterschlüsseln und dem Hauptschlüssel in dem Schlüssel-Planungsteil 20 liefert. Seine Grundkonfiguration ist in 3 dargestellt. In dem oben genannten US-Patent werden die Unterschlüssel durch Datendiffusionsteile (fk) aus dem Hauptschlüssel erzeugt; es wird daher erwartet, dass der Hauptschlüssel nicht auf einfache Weise aus den Unterschlüsseln hergeleitet werden kann.

Als nächstes erfolgt unter Bezugnahme auf 3 eine Beschreibung der allgemeinen Grundzüge eines in dem oben genannten US-Patent offenbarten Schlüssel-Planungsteils 20. Ein erweitertes Schlüsselerzeügungsteil 21 weist N/2 (beispielsweise N = 16) Runden von Schlüssel-Verarbeitungsteilen 210 bis 21N/2-1 auf, die jeweils Schlüssel-Diffusionsteile 220 bis 22N/ 2-1 besitzen. Jedes Schlüssel-Verarbeitungsteil 21j (wobei j = 0, 1, ..., N/2-1) führt eine Diffusionsverarbeitung von zwei Stück rechte und linke 32-Bit-Schlüsseldaten durch und vertauscht diese, um zwei Stück rechte und linke Schlüsseldaten zur Eingabe in das Schlüssel-Verarbeitungsteil 21j+1 der nächsten Runde bereitzustellen. Die Schlüssel-Verarbeitungsteile 21j, mit Ausnahme der ersten Runde, haben jeweils ein Exklusiv-Oder-Teil 23j, das das Exklusiv-Oder der linken Eingabe-Schlüsseldaten zum Schlüssel-Verarbeitungsteil 21j-1 der vorhergehenden Runde und der linken Ausgabe-Schlüsseldaten aus diesem berechnet und die berechneten Daten an das Schlüssel-Diffusionsteil 22j liefert. Die linken Eingabe-Schlüsseldaten des Schlüssel-Verarbeitungsteils 21j werden durch die Ausgabe des Exklusiv-Oder-Teils 23j in dem Schlüssel-Diffusionsteil 22j zerstreut, von dem aus die zerstreuten Daten als rechte Schlüsseldaten zur Eingabe in die nächste Runde ausgegeben werden, und die rechten Eingabe-Schlüsseldaten des Schlüssel-Verarbeitungsteils 21j werden als linke Schlüsseldaten zur Eingabe in die nächste Runde ausgegeben. Die Ausgabe jedes Schlüssel-Diffusionsteils 22j wird durch Bit-Aufteilung in zwei Unterschlüssel Q2j und Q2j+1 (d.h. ki und ki+1) aufgeteilt, die an das entsprechende (i = 2j)-te Runden-Verarbeitungsteil und (i + 1 = 2j + 1)-te Runden-Verarbeitungsteil in 1 geliefert werden.

Der 64-Bit-Hauptschlüssel wird in zwei Stück rechte und linke 32-Bit-Schlüsseldaten aufgeteilt, dann werden in dem Schlüssel-Verarbeitungsteil 210 der ersten Runde die linken Schlüsseldaten in dem Schlüssel-Diffusionsteil 220 durch die rechten Schlüsseldaten zerstreut, um zerstreute linke Schlüsseldaten zu erhalten, und diese zerstreuten linken Schlüsseldaten und die rechten Schlüsseldaten werden untereinander ausgetauscht und als nächstes als rechte und linke Schlüsseldaten zu dem Schlüssel-Verarbeitungsteil 211 geliefert. Die Ausgaben aus den Schlüssel-Diffusionsteilen 220 bis 22N /2-1 der Schlüssel-Verarbeitungsteile 210 bis 21N/2-1 werden als Unterschlüssel k0 bis kN-1 auf die entsprechenden Runden-Verarbeitungsteile 140 bis 14N-1 des in 1 gezeigten Daten-Diffusionsteils 10 angewendet.

In dem erweiterten Schlüsselerzeugungsteil 21 der 3 ist jedoch jedes Schlüssel-Diffusionsteil 22j eine Funktion zur Erzeugung eines Paars von Schlüsseldaten (Unterschlüsseln Q2j, Q2j+1) aus zwei Stück Eingabedaten. Falls eines der beiden Stücke Eingabedaten und die Ausgabedaten bekannt sind, so kann das andere Stück Eingabedaten herausgefunden werden, wenn angenommen wird, dass drei Paare von Unterschlüsseln (Q2j-2 und Q2j-1), (Q2j und Q2j+1), (Q2j+1 und Q2j+3) bekannt sind. Da die Ausgaben (Unterschlüssel Q2j+2 und Q2j+3) aus dem (j + 1)-ten Schlüsseldiffusionsteil 22j+1 und das eine Stück Eingabedaten (Unterschlüssel Q2j-1 und Q2j-1) zu diesem bekannt sind, kann das andere Stück Eingabedaten (d.h. die Ausgabedaten von dem Exklusiv-Oder-Teil 23j+1) erhalten werden; und es ist möglich, aus den auf diese Weise erhaltenen Daten und den Unterschlüsseln Q2j und Q2j+1 die die einen Eingabedaten zu dem Exklusiv-Oder-Teil 23j+1 darstellen, die Eingabedaten zu dem vorangehenden (j-ten) Schlüssel-Diffusionsteil 22j abzuleiten, die die anderen Eingabedaten zu dem Exklusiv-Oder-Teil 23j+1 darstellen, demnach die Unterschlüssel Q2j-4 und Q2j-3, die die Ausgabe aus dem ((j-2)-ten) Schlüssel-Verarbeitungsteil 22j-2 der drittvorangehenden Runde darstellen. Durch Wiederholen derartiger Operationen in einer sequentiellen Anordnung ist es möglich, alle Unterschlüssel durch eine Datenanalyse ausschließlich in dem Schlüssel-Planungsteil 20 zu bestimmen, ohne eine Datenanalyse in dem Daten-Diffusionsteil 10 mit einzubeziehen. Es wurde oben gerade beschrieben, dass, wenn die Unterschlüssel von drei aufeinander folgenden Runden bekannt sind, alle betroffenen Unterschlüssel erhalten werden können, wenn jedoch Unterschlüssel zweier aufeinanderfolgender Runden [bekannt sind], so wird die Verschlüsselungsanalyse auch durch Schätzen der Unterschlüssel der verbleibenden einen Runde durch eine erschöpfende Suche Erfolg haben.

Ist die letzte Stufe der Rundenverarbeitung in 1 durch i = N repräsentiert, so sind die Unterschlüssel kN und kN-1 auf einfache Weise durch Differential- oder Linear-Verschlüsselungsanalyse zu erhalten. Durch Analysieren der Schlüsseldaten in dem erweiterten Schlüsselplanungsteil 21 wie oben beschrieben unter Verwendung der erhaltenen Unterschlüssel besteht die Möglichkeit, alle betreffenden Unterschlüssel zu erhalten.

US 4,850,019 offenbart eine Einrichtung zur Randomisierung von Daten, die für Randomisierungsteile in einer Randomisierungseinrichtung verwendet wird. Eingabedaten werden in vier Blöcke aufgeteilt, wovon jeder wenigstens einer funktionalen Operation und zumindest einer Transformation unterzogen wird; bei diesen funktionalen Operationen und Transformationen handelt es sich jedoch um Modulo-Operationen, Exklusiv-Oder-Operationen und Bitzirkulationsoperationen, d.h. lineare Operationen.

Das Dokument Matsui M: "New Structure of Block Ciphers with Provable Security against Differential and Linear Cryptanalysis", Lecture Notes in Computer Science, Springer Verlag, New York, NY, US, vol. 1039, 1996, Seiten 205–218, XP002914985 ISSN: 0302-9743 offenbart eine Randomisierungseinrichtung, die eine Vielzahl von in Kaskade angeordneten Runden aufweist, wovon jede eine Unterfunktion umfasst, die aus drei in Kaskade angeordneten Runden aufgebaut ist, wovon jede der Reihe nach eine Unterfunktion umfasst, die aus weiteren drei in Kaskaden angeordneten Runden aufgebaut ist, wovon jede eine S-Box umfasst, die eine nichtlineare Transformation ausführt. Damit hat jede Runde der Randomisierungseinrichtung eine dreifach verschachtelte Struktur, wobei deren tiefste Runden drei S-Boxen besitzen. Diese Anordnung erreicht eine höhere Sicherheit im Vergleich zu der nicht verschachtelten Struktur, benötigt jedoch insgesamt neun S-Boxen für jede Runde der in 8 des Dokuments gezeigten Randomisierungseinrichtung.

Eine Aufgabe der vorliegenden Erfindung ist, eine Datentransformationsvorrichtung bereitzustellen, bei welcher die Rundenfunktion f (das Funktionsoperationsteil) konfiguriert ist, um gleichzeitig die Anforderungen an die Sicherheit und eine Steigerung der Geschwindigkeit zu erfüllen, um damit die Sicherheit und einen schnellen Verschlüsselsvorgang zu gewährleisten, ohne dass die Anzahl an Runden wesentlich erhöht wird, und ein Speichermedium, auf dem ein Programm zur Implementierung der Datentransformation gespeichert ist.

OFFENBARUNG DER ERFINDUNG

Diese Aufgabe wird mit einer Datentransformationsvorrichtung nach Anspruch 1 und einem Speichermedium nach Anspruch 21 gelöst. Bevorzugte Ausführungsformen der Erfindung sind Gegenstand der abhängigen Ansprüche.

Gemäß der vorliegenden Erfindung ist gewährleistet, dass, wenn die Differentialwahrscheinlichkeit/Linearwahrscheinlichkeit in dem ersten und dem zweiten nichtlinearen Transformationsteil p ist (< 1), die Differentialwahrscheinlichkeit/Linearwahrscheinlichkeit der Annäherung jeder Runde pi ≤ p2 ist (wenn die in die Funktion f (das nichtlineare Funktionsteil) eingegebene Differenz im Falle der Differentialverschlüsselungsanalyse nicht 0 ist und wenn der aus der Funktion ausgegebene Maskenwert im Falle der Linearverschlüsselungsanalyse nicht 0 ist). Und wenn die Funktion f objektiv ist und die Anzahl von Runden der Verschlüsselungsvorrichtung auf 3r festgesetzt ist, dann wird die Wahrscheinlichkeit der Verschlüsselung P ≤ pi 2r ≤ p4r. Darüber hinaus ist, falls das zweite schlüsselabhängige lineare Transformationsteil, insbesondere im Falle von n = 4, einen Aufbau besitzt, der die Kombination von drei von vier Stück Unterdaten mit einem von vier Stück Schlüsseldaten Exklusiv-Oder-verarbeitet, die Wahrscheinlichkeit der Annäherung jeder Runde pi ≤ p4, und die Wahrscheinlichkeit der Verschlüsselung ist P ≤ pi 2r ≤ p8r. Falls das zweite schlüsselabhängige lineare Transformationsteil im Falle n = 8 einen Aufbau besitzt, der die Kombination von sechs oder fünf von acht Stück Unterdaten mit einem von acht Stück Schlüsseldaten Exklusiv-Oder-verarbeitet, dann ist die Wahrscheinlichkeit der Annäherung jeder Runde pi ≤ p5, und die Wahrscheinlichkeit der Verschlüsselung ist P ≤ pi 2r ≤ p10r.

Darüber hinaus sind das erste und das zweite nichtlineare Transformationsteil derart angeordnet, dass deren Verarbeitungen vollständig parallel zueinander ausgeführt werden können – dies trägt zu einer Erhöhung der Geschwindigkeit bei.

Es ist daher möglich, eine schnelle und Quellen-nichtlineare Funktion gegenüber einer Differential- und Linearverschlüsselungsanalyse zu konstruieren und die Implementierung einer Datentransformationsvorrichtung zu ermöglichen, die sowohl der Sicherheit als auch einer Erhöhung der Geschwindigkeit Rechnung trägt.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

1 ist ein Diagramm, das die funktionale Konfiguration einer herkömmlichen DES-Verschlüsselungsvorrichtung zeigt.

2 ist ein Diagramm, das eine konkrete funktionale Konfiguration eines Funktions-Operationsteils 12 von 1 zeigt.

3 ist ein Diagramm, das ein Beispiel für ein erweitertes Schlüsselerzeugungsteil 21 von 2 zeigt.

4 ist ein Diagramm, das die funktionale Konfiguration der ersten Ausführungsform der vorliegenden Erfindung zeigt.

5 ist ein Diagramm, das im Detail ein Beispiel für die funktionale Konfiguration eines nichtlinearen Funktionsteils 304 der ersten Ausführungsform zeigt.

6 ist ein Diagramm, das die Grundkonfiguration eines nichtlinearen Funktionsteils zur Bestimmung eines optimalen linearen Transformationsteils von 5 zeigt.

7 ist ein Diagramm, das ein konkretes Beispiel für das zweite schlüsselabhängige lineare Transformationsteil 344 von 5 zeigt.

8A ist ein Diagramm, das eine äquivalente funktionale Konfiguration eines nichtlinearen Transformationsteils 3430' der zweiten Ausführungsform zeigt.

8B ist ein Diagramm, das eine äquivalente funktionale Konfiguration eines nichtlinearen Transformationsteils 3431' der zweiten Ausführungsform zeigt.

8C ist ein Diagramm, das eine äquivalente funktionale Konfiguration eines nichtlinearen Transformationsteils 3432' der zweiten Ausführungsform zeigt.

8D ist ein Diagramm, das eine äquivalente funktionale Konfiguration eines nichtlinearen Transformationsteils 3433' der zweiten Ausführungsform zeigt.

9 ist ein Diagramm, das die funktionale Konfiguration eines zweiten schlüsselabhängigen linearen Transformationsteils 344 der zweiten Ausführungsform zeigt.

10 ist ein Diagramm, das die funktionale Konfiguration eines nichtlinearen Funktionsteils 3430 (3450) der dritten Ausführungsform zeigt.

11 ist ein Flussdiagramm, das den Vorgang der Implementierung einer Datentransformation durch einen Computer zeigt.

12 ist ein Flussdiagramm, das den Vorgang von Schritt S3 von 11 im Detail zeigt.

13 ist ein Diagramm, das die funktionale Konfiguration der vierten Ausführungsform der vorliegenden Erfindung zeigt.

14 ist ein Diagramm, das die funktionale Konfiguration eines nichtlinearen Funktionsteils 304 in 13 zeigt.

15A ist ein Diagramm, das ein lineares Transformationsteil 334A mit einer begrenzten Struktur zeigt, die dazu gedacht ist, die mit der Suche verbundene rechnerische Komplexität zu reduzieren.

15B ist ein Diagramm, das ein Beispiel der Konfiguration einer Transformationsbox von 15A zeigt.

16 ist ein Diagramm, das ein Beispiel für die Konfiguration eines linearen Transformationsteils 344A, das von dem Suchalgorithmus bestimmt ist, zeigt.

17 ist ein Diagramm, das ein Beispiel für die funktionale Konfiguration eines zweiten schlüsselabhängigen linearen Transformationsteils 344a in 14 der vierten Ausführungsform zeigt.

18 ist ein Diagramm, das ein anderes Beispiel für die funktionale Konfiguration eines zweiten schlüsselabhängigen linearen Transformationsteils 344 von 14 der vierten Ausführungsform zeigt.

19 ist ein Diagramm, das ein weiteres Beispiel für die funktionale Konfiguration eines zweiten schlüsselabhängigen linearen Transformationsteils 344 von 14 der vierten Ausführungsform zeigt.

20A ist ein Diagramm, das die funktionale Konfiguration eines nichtlinearen Transformationsteils 3430' der fünften Ausführungsform veranschaulicht.

20B ist ein Diagramm, das die funktionale Konfiguration eines nichtlinearen Transformationsteils 3431' veranschaulicht.

20C ist ein Diagramm, das die funktionale Konfiguration eines nichtlinearen Transformationsteils 3437' veranschaulicht.

21 ist ein Diagramm, das die funktionale Konfiguration eines zweiten schlüsselabhängigen linearen Transformationsteils 344 der fünften Ausführungsform zeigt.

22 ist ein Diagramm, das eine Konfiguration zur Ausführung eines Datenverarbeitungsprogramms zeigt, das auf einem Speichermedium gespeichert ist.

23A ist ein Blockdiagramm, das die funktionale Grundkonfiguration eines Schlüssel-Erzeugungsteils zeigt.

23B ist ein Blockdiagramm, das die funktionale Grundkonfiguration eines weiteren Schlüssel-Erzeugungsteils zeigt.

24 ist ein Blockdiagramm, das ein Beispiel für die funktionale Konfiguration eines Zwischenschlüssel-Erzeugungsteils 220 von 23A oder 23B zeigt.

25 ist ein Blockdiagramm, das die funktionale Konfiguration eines G-Funktionsteils von 24 zeigt, wenn die vorliegende Erfindung auf ein Schlüssel-Planungsteil von 3 angewendet wird.

26 ist ein Blockdiagramm, das die funktionale Konfiguration eines Unterschlüssel-Erzeugungsteil 240 von 23A zeigt, wenn dieses auf ein Schlüssel-Planungsteil von 3 angewendet wird.

27 ist ein Blockdiagramm, das ein Beispiel für die funktionale Konfiguration eines Unterschlüssel-Erzeugungsteils 250 von 23B zeigt, wenn dieses auf ein Schlüssel-Planungsteil von 3 angewendet wird (In diesem Beispiel enthält das Schlüssel-Erzeugungsteil ein H-Funktionsteil, das mit einer Bit-Extraktionsfunktion ausgestattet ist).

28 ist ein Blockdiagramm, das die funktionale Konfiguration des G-Funktionsteils 22 zeigt, das zur Anwendung auf eine Feistel-Chiffre gedacht ist, die 228 Bits als einen Block verwendet.

BESTE AUSFÜHRUNGSFORM ZUR AUSFÜHRUNG DER VORLIEGENDEN ERFINDUNG Erste Ausführungsform

Eine Ausführungsform der vorliegenden Erfindung wird nachfolgend unter Bezugnahme auf die beiliegenden Zeichnungen beschrieben.

4 veranschaulicht die funktionale Konfiguration eines Verschlüsselungsverfahrens bei der Datentransformationsvorrichtung gemäß einer Ausführungsform der vorliegenden Erfindung. Die Datentransformationsvorrichtung weist ein Datendiffusionsteil 10 und ein Schlüssel-Planungsteil 20 auf. Auch bei der Datentransformationsvorrichtung gemäß der vorliegenden Erfindung umfasst das Datendiffusionsteil 10 N Runden von in Kaskade verbundenen Runden-Verarbeitungsteilen 380 bis 38N-1, die der Reihe nach eine Rundenverarbeitung von linken und rechten Stücken von Daten ausführen, nachdem die Eingabedaten in linke und rechte Stücke L0, R0 aufgeteilt wurden; jedes Runden-Verarbeitungsteil 38i (wobei i = 0, 1, ..., N-1) ist aufgebaut aus einem nichtlinearen Funktionsteil 304, das dem Funktions-Operationsteil 12 von 1 entspricht, einem linearen Operationsteil 305, das der XOR-Schaltung von 1 entspricht, und einem Tauschteil 306.

Eingabedaten M, die einem Klartext entsprechen, werden in die Verschlüsselungseinrichtung über ein Eingabeteil 301 eingegeben. Das Schlüssel-Planungsteil 20 weist ein Schlüssel-Eingabeteil 320, ein erweitertes Schlüsselerzeugungsteil 321 und ein Schlüssel-Speicherteil 322 auf. Basierend auf Eingabedaten (einem Hauptschlüssel K) von dem Schlüssel-Eingabeteil 321 erzeugt das erweiterte Schlüsselerzeugungsteil 321 viele Stück Schlüsseldaten (Unterschlüssel) {fk; k00, k01; k10, k11, k12; ...; k(N-1)0, k(N-1)1, k(N-1)2; ek}, die in dem Schlüssel-Speicherteil 322 gespeichert werden. Die Eingabedaten M werden in einem schlüsselabhängigen Anfangs-Transformationsteil 302 mit den in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten fk transformiert, danach in einem Anfangs-Teilungsteil 303 in zwei Stück linke und rechte Blockdaten L0 und R0 geteilt. Beispielsweise werden 64-Bit-Daten in zwei Stück 32-Bit-Blockdaten L0 und R0 geteilt. Das schlüsselabhängige Anfangs-Transformationsteil 302 führt eine lineare Transformation aus, wie Exklusive-Oder-Operationen der Schlüsseldaten fk und der Eingabedaten M oder eine Bit-Rotation der Eingabedaten M durch die Schlüsseldaten fk, oder eine nichtlineare Transformation durch eine Kombination von Multiplikationen.

Die rechten Blockdaten R0 werden an das nichtlineare Funktionsteil 304, das charakteristisch ist für die vorliegende Erfindung, zusammen mit den Schlüsseldaten k00, k01 und k02, die in dem Schlüssel-Speicherteil 322 gespeichert sind, geliefert, und in dem nichtlinearen Funktionsteil 304 werden die rechten Blockdaten nichtlinear zu Daten Y0 transformiert. Die Daten Y0 und die linken Blockdaten L0 werden zu Daten L0* durch eine lineare Operation in dem Linear-Operationsteil 305 transformiert. Die Daten L0* und die Daten R0 werden in dem Tauschteil 306 getauscht, um L1←R0, R1←L0* bereitzustellen; und diese Datenstücke L1 und R1 werden in das nächste, erste Runden-Verarbeitungsteil 381 eingegeben.

Danach wird in i-ten Runden-Verarbeitungsteilen 38i (wobei i = 0, 1, ..., N-1) die gleiche oben genannte Verarbeitung für zwei Stück Eingabe-Blockdaten Li und Ri wiederholt. Demnach werden die rechten Blockdaten Ri in das nichtlineare Funktionsteil 304 zusammen mit den Schlüsseldaten ki0, ki1 und ki2 eingegeben und in dem nichtlinearen Funktionsteil 304 nichtlinear zu Daten Yi transformiert. Die Daten Yi und die Daten Li werden durch eine lineare Operation in dem Linear-Operationsteil 305 zu Daten Li* transformiert. Die Daten Li* und die Daten Ri werden in ihrer Datenposition in dem Tauschteil 306 getauscht, demnach Li+1←Ri, Ri+1←Li*. Das Linear-Operationsteil 305 führt beispielsweise eine exklusive Oder-Operation aus.

Repräsentiert N die Wiederhohlzahl (die Anzahl von Runden), die geeignet ist, um für die Verschlüsselung die Sicherheit einer Datentransformationsvorrichtung bereitzustellen, so werden Stück linke und rechte Daten LN und RN als das Ergebnis einer derartigen wiederholten Verarbeitung durch die Runden-Verarbeitungsteile 380 to 38N-1 erhalten. Diese Datenstücke LN und RN werden zu einem einzelnen Stück Blockdaten in einem End-Kombinationsteil 307 kombiniert; beispielsweise werden die zwei Stück 32-Bit-Daten LN und RN zu 64-Bit-Daten kombiniert. Dann werden die auf diese Weise kombinierten Daten in einem linearen End-Transformationsteil 308 unter Verwendung der in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten ek transformiert, und Ausgabedaten C werden als ein Chiffretext von einem Ausgabeteil 309 bereitgestellt.

Bei einer Entschlüsselung kann der Klartext M durch Umkehrung des Verschlüsselungsverfahrens aus dem Chiffretext C hergeleitet werden. Insbesondere wenn das schlüsselabhängige End-Transformationsteil 308 eines ist, das eine zu dem schlüsselabhängigen Anfangs-Transformationsteil 302 umgekehrte Transformation ausführt, dann kann die Entschlüsselung durchgeführt werden, indem Chiffretextdaten anstatt der Eingabedaten von 4 und dann Schlüsseldaten in einer zu der von 4 umgekehrten Reihenfolge, demnach ek, k(N-1)0, k(N-1)1, k(N-1)2, ..., k10, k11, k12, k00, k01, k02, fk, eingegeben werden.

Als nächstes erfolgt eine detaillierte Beschreibung der internen Konfiguration des nichtlinearen Funktionsteils 304. 5 ist ein Diagramm, das die interne funktionale Konfiguration des nichtlinearen Funktionsteils 304 zeigt.

Die in das i-te Runden-Verarbeitungsteil 38i eingegebenen Blockdaten Ri stellen zusammen mit den im dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten ki0, ki1, ki2 Eingabedaten zu dem nichtlinearen Funktionsteil 304 dar. Die Blockdaten Ri werden beispielsweise einer Exklusiv-Oder-Operation mit den Schlüsseldaten ki0 in einem ersten schlüsselabhängigen linearen Transformationsteil 341 unterzogen, durch die es linear zu Daten Ri* = Ri⨁ki0 transformiert wird. Danach werden die auf diese Weise transformierten Daten Ri* in einem Teilungsteil 342 in vier Stück beispielsweise 8-Bit-Daten in0, in1, in2 und in3 aufgeteilt. Die vier Datenstücke in0, in1, in2 und in3 werden zu vier Datenstücken mid00, mid01, mid02 und mid03 in nichtlinearen Transformationsteilen 3430, 3431, 3432 bzw. 3433 nichtlinear transformiert, von denen aus sie in ein zweites schlüsselabhängiges lineares Transformationsteil 344 eingegeben werden.

Das zweite schlüsselabhängige lineare Transformationsteil 344 führt eine lineare Transformation 344 (Exklusiv-Oder-Operation) unter den Stücken von Eingabedaten mid00, mid01, mid02 und mid03 von vier Pfaden durch, um neue Daten von vier Pfaden bereitzustellen, und führt des weiteren eine lineare Transformation (Exklusiv-Oder-Operation) unter diesen Datenstücken der vier Pfade mit vier Stück Schlüsseldaten ki1 durch, um Ausgabedaten mid10, mid11, mid12 and mid13 von vier Pfaden bereitzustellen. Die vier Stück Daten werden in nichtlineare Transformationsteile 3450, 3451, 3452 und 3453 eingegeben, in denen sie jeweils zu Daten out0, out1, out2 bzw. out3 transformiert werden. Diese vier Stück Daten werden in einem Kombinationsteil 346 zu Daten Yi* kombiniert; darüber hinaus werden die Daten Yi* in einem dritten schlüsselabhängigen linearen Transformationsteil 347 einer linearen Operation mit Schlüsseldaten ki2 unterworfen, um Ausgabedaten Yi zu erzeugen.

Das oben genannte zweite schlüsselabhängige lineare Transformationsteil 344 ist konfiguriert, um eine Exklusiv-Oder-Operation von Daten zwischen den Daten-Verarbeitungspfaden 300, 301, 302 and 303, die jeweils entsprechend zu den Datenstücken mid00, mid01, mid02 bzw. mid03 bereitgestellt sind, unter Verwendung eines der vorliegenden Erfindung entsprechenden Algorithmus durchzuführen, wodurch eine erhöhte Sicherheit bereitgestellt wird, ohne die Anzahl von Runden der in 4 gezeigten Datentransformationsvorrichtung zu erhöhen. Die Sicherheit der Datentransformationsvorrichtung von 4 gegenüber einer Differentialverschlüsselungsanalyse und einer Linearverschlüsselungsanalyse hängt von der Konfiguration des nichtlinearen Funktionsteils 304 von 5 in jeder Runde ab; insbesondere wenn das nichtlineare Funktionsteil 304 von 5 eine derartige, in 6 gezeigte Grundkonfiguration aufweist, hängt die Sicherheit von einem ersten nichtlinearen Transformationsteil 343 ab, das aus n nichtlinearen Transformationsteilen (S-Boxen) mit m-Bit-Eingabedaten aufgebaut ist, einem linearen Transformationsteil 344A zur linearen Transformation der n Ausgaben und einem zweiten nichtlinearen Transformationsteil 345, das aus n nichtlinearen Transformationsteilen (S-Boxen) zur nichtlinearen Transformation der n m-Bit-Ausgaben aufgebaut ist. Es ist insbesondere von Bedeutung, wie ein optimales Transformationsteil 344A konstruiert ist, das gegenüber Differential und Linear-Verschlüsselungsanalyse sicher ist. Gemäß der vorliegenden Erfindung ist das lineare Transformationsteil 344A durch eine n × n Matrix P über {0, 1} repräsentiert, und das optimale lineare Transformationsteil 344A wird konstruiert, indem Elemente der Matrix P derart bestimmt werden, dass die maximalen differentiellen und linearen charakteristischen Wahrscheinlichkeiten p, q minimiert werden. In diesem Fall wird ein lineares Transformationsteil, das den Unterschlüssel ki1 verwendet, der in dem zweiten schlüsselabhängigen Transformationsteil 344 enthalten ist, als ein schlüsselabhängiges Transformationsteil 344B zu dem linearen Transformationsteil 344A, das durch die in 7 gezeigte Matrix P bestimmt ist, hinzugefügt.

Übrigens ist mit dem Begriff "optimal" gemeint, dass die höchste Widerstandskraft gegenüber einer Differential- und Linear-Verschlüsselungsanalyse in dem linearen Transformationsteil 344A der obigen Konfiguration bereitgestellt werden soll, dies bedeutet jedoch nicht notwendigerweise das Optimum bezüglich anderer Kriterien, beispielsweise einer Lawineneigenschaft (avalanche). Empirisch gesprochen, können jedoch andere Angriffe als Differential- und Linearverschlüsselungsanalysen auf einfache Weise durch ledigliche Erhöhung der Anzahl an Runden verhindert werden, wohingegen es nicht sicher ist, ob nur ein gewisser Anstieg in der Anzahl an Runden dazu taugt, Differential- und Linear-Verschlüsselungsanalyse zu verhindern, bevor nicht eine sorgfältige Untersuchung der verwendeten Rundenfunktion durchgeführt wurde. Im Hinblick darauf misst die vorliegende Erfindung die größte Bedeutung der Widerstandstandkraft der Rundenfunktion gegenüber einer Differential- oder Linear-Verschlüsselungsanalyse bei und konstruiert entsprechend das optimale lineare Transformationsteil 344A.

Gemäß der vorliegenden Erfindung ist das lineare Transformationsteil 344A in 6 als eine n × n-Matrix P über {0, 1} dargestellt, worauf oben Bezug genommen wurde. Dies bedeutet, dass die Matrix P eine lineare Transformation in Einheiten von m Bits durchführt, und dass das lineare Transformationsteil 344A durch lediglich Exklusiv-Oder-Operationen gebildet werden kann. Damit kann diese Transformation durch folgende Gleichung ausgedrückt werden:

Insbesondere wenn m = 8 ist, dann wird die lineare Transformation in Byte-Einheiten durchgeführt und kann effizient auf anderen Plattformen implementiert werden, bei denen die Wortbreite 8 Bit oder mehr beträgt.

Als konkretes Beispiel im Falle von n = 4 wird eine 4 × 4-Matrix PE beschrieben, die durch folgende Gleichung ausgedrückt ist:

Die Rundenfunktion, die die Matrix PE verwendet, besitzt die folgenden Merkmale. Es wird jedoch angenommen, dass die S-Box bijektiv ist. z'0, z'1, z'2 bzw. z'3, die durch die obige Matrix definiert sind, repräsentieren jeweils die folgenden Operationen. z'0 = 0·z0⨁1·z1⨁1·z2⨁1·z3 = z1⨁z2⨁z3(3-1) z'1 = 1·z0⨁0·z1⨁1·z2⨁1·z3 = z0⨁z2⨁z3(3-2) z'2 = 1·z0⨁1·z1⨁1·z2⨁0·z3 = z0⨁z1⨁z2(3-3) z'3 = 1·z0⨁1·z1⨁1·z2⨁1·z3 = z0⨁z1⨁z2⨁z3(3-4)

Die Widerstandskraft der Rundenfunktion gegenüber einer Differential- und Linear-Verschlüsselungsanalyse kann durch die kleinste Anzahl nd, n1 von aktiven S-Boxes bestimmt werden, und diese Werte sind diejenigen, die zum Zeitpunkt der Bestimmung der Matrix P (siehe Anhang) bestimmt werden. Bei der Differential-Verschlüsselungsanalyse wird eine S-Box, deren Eingabe-Differenzwert &Dgr;x nicht gleich Null ist, als eine aktive S-Box bezeichnet, und bei der linearen Verschlüsselungsanalyse wird eine S-Box, deren Ausgabe-Maskenwert &Ggr;y nicht gleich Null ist, als eine aktive Box bezeichnet.

Wenn eine bestimmte Matrix P gegeben ist, gibt es im Allgemeinen eine Vielzahl von Konstruktionen für das lineare Transformationsteil 344A, die dieser entsprechen. Dies ist deshalb der Fall, weil die Matrix P nur die Beziehung zwischen Eingabe- und Ausgabedaten des linearen Transformationsteils 344A repräsentiert und nicht dessen konkreten Aufbau definiert. Darum können diese linearen Transformationsteile, die in der Matrix P übereinstimmen, die die Beziehung zwischen deren Eingabe- und Ausgabedaten repräsentiert, betrachtet werden, als hätten sie unabhängig von deren individuellen Aufbau die gleiche Charakteristik. Demnach wird in der folgenden Beschreibung zuerst die Matrix P bestimmt, die die größte Unangreifbarkeit gegenüber Differential- und Linear-Verschlüsselungsanalyse und einen guten Lawineneffekt bietet, gefolgt von der Bestimmung des Aufbaus des linearen Transformationsteils 344A. Dieses Verfahren ist bei der Suche nach einem linearen Transformationsteil 344A mit einer optimalen Charakteristik wirksamer als ein Verfahren, bei dem individuelle Konstruktionen von linearen Transformationsteilen geprüft werden, um zu sehen, ob diese die optimale Charakteristik besitzen.

Die Elemente der n × n-Matrix P werden durch den folgenden Suchalgorithmus bestimmt, der die Differentialcharakteristik mit einbezieht.

Schritt 1: Lege eine Sicherheitsschwelle T fest (wobei T eine ganze Zahl mit 2 ≤ T ≤ n ist).

Schritt 2: Bereite ein Satz C von Spaltenvektoren vor, deren Hamming-Gewichte gleich sind mit oder größer als T-1. Noch genauer, bereite n oder mehr n-dimensionale Spaltenvektoren vor, die T-1 oder mehr Elemente "1" haben.

Schritt 3: Wähle einen Untersatz Pc von n Spaltenvektoren aus dem Satz C aus. Wiederhole die folgenden Schritte bis alle Untersätze überprüft wurden.

Schritt 3-1: Berechne nd für den Untersatz Pc von n Spaltenvektoren. Dies ist als nd(Pc) repräsentiert.

Schritt 3-2: Falls nd(Pc) ≥ T, dann akzeptiere eine Matrix Pc, die aus den n Spaltenvektoren besteht, als eine Kandidatenmatrix.

Schritt 4: Gebe Matrizen P und einen Wert nd(P) aus, der den maximalen Wert von nd unter allen Kandidatenmatrizen erzielt.

Falls die Kandidatenmatrix von dem obigen Suchalgorithmus angenommen wird, dann ist garantiert, dass der Wert nd gleich ist mit oder größer als T. Die Matrix P, die nd maximiert, kann effizient gefunden werden, indem nach jeder Ausführung des obigen Suchalgorithmus T in der Reihenfolge T = n, n-1, ..., 3, 2 um 1 inkrementiert wird.

Bei dem obigen Suchalgorithmus, kann, falls es möglich ist, eine relativ zufriedenstellende Unangreifbarkeit gegenüber Differential- oder Linear-Verschlüsselungsanalyse zu erhalten, eine Matrix mit nd(Pc) ≥ T, die durch Ausführen der Schritte bis 3-2 erhalten wurde, als die gewünschte Matrix P verwendet werden. Alternativ kann die Matrix Pc, die aus n Vektoren aufgebaut ist, deren Hamming-Gewichte gleich sind mit oder größer als T-1, die nach Schritt 1 in Schritt 2 ausgewählt wurden, als Matrix P verwendet werden.

Die Eingabe-Maskenwerte des linearen Transformationsteils 344A können durch Exklusiv-Oder-Operationen seiner Ausgabe-Maskenwerte dargestellt werden, und daher durch eine bestimmte Matrix ausgedrückt werden, wie es mit Differentialcharakteristik der Fall ist. Als Ergebnis unserer Überprüfung der Verbindung zwischen der Matrix für Differentialcharakteristik und der Matrix für linearen Ausdruck in einigen linearen Transformationsteilen mit verschiedenem Aufbau, wurde folgender Lehrsatz (Theorem) gebildet.

Theorem 1: Nimm an, dass eine n × n Matrix P über {0, 1} für das lineare Transformationsteil 344A gegeben ist. Zu diesem Zeitpunkt ist die Beziehung zwischen Eingabe- und Ausgabe-Differenzwerten &Dgr;z und &Dgr;z' des linearen Transformationsteils 344A (ein Differenzweg) durch die Matrix P, und die Beziehung zwischen Eingabe- und Ausgabemaskenwerten &Ggr;z und &Ggr;z' (ein Maskenwertweg) durch eine transponierte Matrix TP gegeben. Dann ist &Dgr;z' = P&Dgr;z(4) &Ggr;z = TP&Ggr;z'.(5)

Das Folgende ist ein Algorithmus zur Bestimmung des Aufbaus des linearen Transformationsteils 344A, wenn die Matrix P gegeben ist. Hier müssen die folgenden Bedingungen erfüllt werden.

  • (1) Minimierung der Anzahl von Exklusiv-Oder-Operationen (XOR), oder
  • (2) Wiederholtes Auftreten des ähnlichen Unteraufbaus.

Schritt 1: Wähle aus der Matrix P zwei Spalten aus und XOR-verknüpfe die eine Spalte (Spalte a) mit der anderen Spalte (Spalte b) (im Folgenden als primitive Operation bezeichnet).

Schritt 2: Transformiere die Matrix P in eine Einheits-Matrix I durch Wiederholen der primitiven Operation, zähle die Anzahl, wie oft die primitive Operation ausgeführt wurde, und finde ein Matrix-Transformationsverfahren, das die minimale Anzahl von primitiven Operationen ergibt.

Schritt 3: Um das lineare Transformationsteil 344A zu konstruieren, werden die Zeilen A und B, die den in Schritt 2 gewählten Spalten a und b entsprechen, in einer zum Transformationsverfahren umgekehrten Reihenfolge XOR-verknüpft.

In 7 ist ein konkretes Beispiel für das zweite schlüsselabhängige lineare Transformationsteil 344 dargestellt, das das wie oben bestimmte lineare Transformationsteil 344A besitzt. In das lineare Transformationsteil 344A werden die vier Datenteile mid00, mid01, mid02 und mid03 jeweils in die Verarbeitungspfade 300 bis 303, eingegeben. In dem Verarbeitungspfad 300 werden mid00 und mid01 durch eine XOR-Schaltung 310 XOR-verknüpft; in dem Verarbeitungspfad 302 werden mid02 und die Ausgabe von der XOR-Schaltung 310 durch eine XOR-Schaltung 312 XOR-verknüpft; und die Ausgabe von der XOR-Schaltung 312 wird mit mid01 durch eine XOR-Schaltung 311 XOR-verknüpft.

In dem Verarbeitungspfad 303 werden die Ausgabe von der XOR-Schaltung 310 und die Daten mid03 durch eine XOR-Schaltung 313 XOR-verknüpft; in dem Verarbeitungspfad 301 werden die Ausgaben von den XOR-Schaltungen 311 und 313 durch eine XOR-Schaltung 321 XOR-verknüpft; und in dem Verarbeitungspfad 300 werden die Ausgaben von der XOR-Schaltung 321 und 310 durch eine XOR-Schaltung 320 XOR-verknüpft.

Die Ausgaben von den XOR-Schaltungen 320, 321, 312 und 313 und Unterschlüsseldaten ki10, ki11, ki12 und ki13 werden jeweils durch die XOR-Schaltungen 350 bis 353 des schlüsselabhängigen Transformationsteils 344B, von dem mid10, mid11, mid12 bzw. mid13 geliefert werden, XOR-verknüpft. Mit anderen Worten, die Datenstücke mid00, mid01, mid02 und mid03 werden miteinander assoziiert und dann einer linearen Transformation unterworfen, die jeweils von den 8-Bit-Unterschlüsseldaten ki10, ki11, ki12 bzw. ki13 abhängig ist. Kurz gesagt werden logische Operationen durchgeführt, die durch den folgenden logischen Ausdruck gegeben sind. mid10 = mid00⨁mid02⨁mid03⨁ki10(7-1) mid11 = mid01⨁mid02⨁mid03⨁ki11(7-2) mid12 = mid00⨁mid01⨁mid02⨁ki12(7-3) mid13 = mid00⨁mid01⨁mid03⨁ki13(7-4)

Übrigens ist der Unterschlüssel ki1 aus vier Datenteilen ki10, ki11, ki12 und ki13 aufgebaut.

Wie in 5 dargestellt, werden diese Datenstücke mid10, mid11, mid12 und mid13 dann in den nichtlinearen Transformationsteilen 3450, 3451, 3452 und 3453 jeweils nichtlinear zu den Daten out0, out1, out2 bzw. out3 transformiert, die in dem Kombinationsteil 346 zu dem einzelnen Datenstück Yi kombiniert werden. Schließlich werden die Daten Yi* beispielsweise durch eine ki2-Bit-Linksrotation in dem dritten schlüsselabhängigen linearen Transformationsteil 347 unter Verwendung der Schlüsseldaten ki2 zu Daten Yi linear transformiert, wodurch die Ausgabedaten Yi aus dem nichtlinearen Funktionsteil 305 erzeugt werden. Die nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 funktionieren genauso wie S-Boxen für DES-Verschlüsselung und werden beispielsweise durch ROM konstruiert, das die Eingabedaten als eine Adresse empfängt, um hieraus die entsprechenden Daten auszulesen.

Da die vier nichtlinearen Transformationsteile 3430 bis 3433 parallel zueinander angeordnet sind und deren Transformationsverfahren nicht miteinander assoziiert sind, können sie parallel zueinander ausgeführt werden. Das gleiche gilt für die nichtlinearen Transformationsteile 3450 bis 3453. Somit kann jedes lineare Transformationsteil in einem Schritt für jede Gruppe (insgesamt zwei Schritte in dem nichtlinearen Funktionsteil 304) durchgeführt werden. Wenn p die differentielle/lineare Wahrscheinlichkeit der nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 repräsentiert, liefert das nichtlineare Funktionsteil 304 eine differentielle/lineare Wahrscheinlichkeit von insgesamt p4, wenn das zweite schlüsselabhängige Transformationsteil 344 einen in 7 gezeigten Aufbau besitzt. Wenn demnach die Anzahl an Runden der gesamten Datentransformationsvorrichtung 3r ist, wird eine angenäherte Darstellung mit einer Wahrscheinlichkeit von P ≤ p8r erhalten; beispielsweise wenn r = 4 ist (12 Runden), gilt P ≤ p32. Im Falle von DES-Verschlüsselung entspricht dies 48 oder mehr Runden, was genügend Sicherheit gegenüber Differential- und Linear-Verschlüsselungsanalyse gewährleistet.

Übrigens werden die Teile von Schlüsseldaten fk, k00, k01, k02, k10, k12, ..., k(1-N)1, k(N-1)2, ek in dem Schlüssel-Speicherteil 322 von 4 gespeichert, nachdem sie in dem erweiterten Schlüsselerzeugungsteil 321 aus dem Hauptschlüssel transformiert wurden, der über das Schlüssel-Eingabeteil 320 des Schlüssel-Planungsteils 20 eingegeben wurde. Die Erzeugung von Schlüsseldaten in dem erweiterten Schlüsselerzeugungsteil 321 kann die gleiche sein wie in dem erweiterten Schlüsselerzeugungsteil 21 für DES-Verschlüsselung in 1 oder wie in dem erweiterten Schlüsselerzeugungsteil 21 von Miyaguchi et al., das in 3 dargestellt ist.

Das schlüsselabhängige Anfangs-Transformationsteil 302 und das schlüsselabhängige End-Transformationsteil 308, die in 4 gezeigt sind, und die schlüsselabhängigen linearen Transformationsteile 341, 344 und 347 in jedem nichtlinearen in 5 gezeigten Funktionsteil 304 sind lineare Transformationsteile, die von Schlüsseln abhängig sind; daher ist die Vorrichtung dieser Ausführungsform eine Verschlüsselungsvorrichtung, die ausreichend sicher ist gegenüber Differential- sowie Linear-Verschlüsselungsanalyse, und die der Sicherheit erstrangige Bedeutung zumisst.

Die vorliegende Erfindung ist nicht speziell auf dieses Beispiel begrenzt; wenn beispielsweise eine Erhöhung der Geschwindigkeit verlangt wird, ist es vernünftig, auf eines der schlüsselabhängigen Anfangs-Transformationsteile 302, der schlüsselabhängigen End-Transformationsteile 308 und der schlüsselabhängigen linearen Transformationsteile 341, 344 und 347 zu verzichten oder diese zu schlüsselunabhängigen Transformationsteilen zu modifizieren. In diesem Fall kann die Verschlüsselungsgeschwindigkeit erhöht werden, ohne die Sicherheit gegenüber Differential- und Linear-Verschlüsselungsanalyse signifikant zu vermindern.

Zweite Ausführungsform

Es erfolgt eine Beschreibung einer weiteren Ausführungsform des nichtlinearen Funktionsteils 304 von 5 bei einer Datentransformationsvorrichtung mit der gleichen Konstruktion wie derjenigen der ersten in 4 gezeigten Ausführungsform. Bei dieser Ausführungsform werden die nichtlinearen Transformationsteile 3430, 3431, 3432 und 3433 von 5 durch nichtlineare Transformationsteile 3430' bis 3433' ersetzt, die beispielsweise 8-Bit-Eingaben in0 bis in3 nichtlinear auf 32 Bit erweiterte Daten MID00, MID01, MID02 und MID03 transformieren, wie jeweils äquivalent in 8A bis 8D dargestellt; darüber hinaus hat das schlüsselabhängige nichtlineare Transformationsteil 344 einen in 9 dargestellten Aufbau.

Wie im Falle von 5 werden die Daten Ri zusammen mit den Schlüsseldaten ki0, ki1 und ki2 in das nichtlineare Funktionsteil 304 eingegeben. Die Daten Ri werden linear zu Daten Ri* = Ri⨁ki0 transformiert, beispielsweise indem sie in dem ersten schlüsselabhängigen linearen Transformationsteil 341 mit den Schlüsseldaten ki0 XOR-verknüpft werden. Als nächstes werden die Daten Ri* in dem Teilungsteil 342 in vier Stück Daten in0, in1, in2 und in3 aufgeteilt. Die vier Stück Daten in0, in1, in2 und in3 werden jeweils in den in 8A bis 8D gezeigten nichtlinearen Transformationsteilen 3430', 3431', 3432' und 3433' nichtlinear zu Daten MID00, MID01, MID02 und MID03 transformiert. Bei der ersten Ausführungsform gibt das nichtlineare Transformationsteil 3430 die m-Bit-Daten mid00 für die m-Bit-Eingabe in0 aus, wohingegen bei dieser Ausführungsform das nichtlineare Transformationsteil 3430' eine S-Box besitzt, das die gleichen m-Bit-Daten mid00 als m hochwertige Bits, wie es das nichtlineare Transformationsteil 3430 bei der ersten Ausführungsform von 5 macht, und feste Daten "00 ... 0(2)" als m niedrigwertige Bits ausgibt; des Weiteren ist das nichtlineare Transformationsteil eingerichtet, um die hochwertigen m-Bit-Daten mid00 durch Duplizieren an drei Pfade auszugeben und die m-Bit-Daten "00 ... 0(2)" auszugeben. Damit ist das nichtlineare Transformationsteil 3430' ein Mittel zum Transformieren der m-Bit-Daten in0 in 4m-Bit-Daten. MID00 = [mid00, 00 ... 0(2), mid00, mid00](8-1)

In ähnlicher Weise sind die nichtlinearen Transformationsteile 3431', 3432' und 3433' Mittel zum Transformieren der Eingabedaten in1, in2 and in3 in MID01 = [00 ... 0(2), mid01, mid01, mid01](8-2) MID02 = [mid02, mid02, mid02, 00 ... 0(2)](8-3) MID03 = [mid03, mid03, 00 ... 0(2), mid03](8-4)

Die durch die Gleichung (8-1) ausgedrückten Daten MID00 können bestimmt werden, indem als MID00 die gesamten Daten voreingestellt werden, die in den vier Ausgabepfaden des linearen Transformationsteils 344A geliefert werden, wenn jedes der Datenstücke mid01, mid02 und mid03 mit Ausnahme von mid00 zu "00 ... 0(2)" festgesetzt wird. In ähnlicher Weise können die Daten MID01, MID02 und MID03, die durch die Gleichungen (8-2), (8-3) und (8-4) ausgedrückt sind, ebenso einfach bestimmt werden. Diese nichtlinearen Transformationsteile 3430' bis 3433' können im Speicher als Transformationstafeln konstruiert sein, aus denen die Daten MID00, MID01, MID02 und MID03 unter Verwendung der Daten in0, in1, in2 und in3 als Adressen auszulesen sind.

Dann werden diese Datenstücke MID00 bis MID03 in das zweite schlüsselabhängige lineare Transformationsteil 344 mit den Schlüsseldaten ki1 eingegeben, wie in 9 dargestellt. MID00 und MID01 werden mit einer XOR-Schaltung 41 XOR-verknüpft; MID02 und MID03 werden mit einer XOR-Schaltung 42 XOR-verknüpft; die Ausgaben der XOR-Schaltungen 41 und 42 werden mit einer XOR-Schaltung 43 XOR-verknüpft; und die Ausgabe aus der XOR-Schaltung 43 und die Schlüsseldaten ki1 werden mit einer XOR-Schaltung 44 XOR-verknüpft. Die Ausgabe MID1 aus der XOR-Schaltung 44 wird in m-Bit-Ausgaben mid10, mid11, mid12 und mid13 aufgeteilt. Schließlich transformiert das zweite schlüsselabhängige lineare Transformationsteil 344 die Eingabedaten linear mit folgender Operation MID1 = MID00⨁MID01⨁MID02⨁MID03⨁ki1.(9)

Die Komponenten der Ausgabe MID1 = [mid10, mid11, mid12, mid13] dieser linearen Transformationsoperation sind jeweils durch die folgenden Gleichungen ausgedrückt: mid10 = mid00⨁mid02⨁mid03⨁ki10(10-1) mid11 = mid01⨁mid02⨁mid03⨁ki11(10-2) mid12 = mid00⨁mid01⨁mid02⨁ki12(10-3) mid13 = mid00⨁mid01⨁mid03⨁ki13(10-4)

Diese linearen Transformationsoperationen sind äquivalent mit denjenigen von 7, die durch die Gleichungen (7-1) bis (7-4) angegeben sind. Auf diese Weise werden die gleichen Datenstücke d10, mid11, mid12 und mid13 wie bei der ersten Ausführungsform erzeugt. Übrigens ist ki1 aus Stück Daten ki10, ki11, ki12 und ki13 aufgebaut.

Dann werden die vier Datenstücke mid10, mid11, mid12 und mid13, wie in 5, in den nichtlinearen Transformationsteilen 3450, 3451, 3452 und 3453 jeweils nichtlinear zu Daten out0, out1, out2 und out3 transformiert, und in dem Kombinationsteil 346 werden die vier Datenstücke out0, out1, out2 und out3 zu einem einzelnen Datenstück Yi* kombiniert. Schließlich werden die Daten Yi* linear zu Daten Yi transformiert durch beispielsweise eine ki2-Bit Linksrotation-in dem dritten schlüsselabhängigen linearen Transformationsteil 347 unter Verwendung der Schlüsseldaten ki2, wodurch die Ausgabedaten Yi des nichtlinearen Funktionsteils 304 erzeugt werden.

Bei der zweiten in den 8A bis 8D und 9 dargestellten Ausführungsform ist es ebenso wie im Falle der ersten Ausführungsform möglich, die nichtlinearen Transformationsteile 3430 bis 3433 der 8A bis 8D nur durch S-Boxen zu bilden, die jeweils 8Bit-Daten mid00 bis mid03 ausgeben, und die in 8A bis 8D gezeigten Verdrahtungen und ein Register bereitzustellen, das 8-Bit-Daten "00 ... 0" in dem schlüsselabhängigen Transformationsteil 344 ausgibt, um darin die Daten MID00 bis MID03 zu erzeugen.

Bei dieser Ausführungsform implementiert das zweite schlüsselabhängige lineare Transformationsteil 344 eine zu der in 7 gezeigten äquivalente lineare Transformation durch das Verwenden von vier XOR-Schaltungen, wie in 9 dargestellt (in 7 zehn XORs), und ermöglicht daher eine schnellere Transformation als bei der ersten Ausführungsform.

Darüber hinaus sind wie im Falle der ersten Ausführungsform die vier nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 parallel zueinander angeordnet, und ihre nichtlinearen Transformationsverfahren sind nicht miteinander assoziiert und können daher parallel zueinander ausgeführt werden. Ferner, wenn p die differentielle/lineare Wahrscheinlichkeit der nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 repräsentiert, wird die differentielle/lineare Wahrscheinlichkeit der nichtlinearen Funktion 304 insgesamt p4.

Dritte Ausführungsform

Es folgt die Beschreibung einer weiteren Ausführungsform des nichtlinearen Transformationsteils 304 mit einer weiteren funktionalen Konfiguration in der Datentransformationsvorrichtung, die wie im Fall der ersten Ausführungsform die in 4 gezeigte funktionale Konfiguration besitzt.

Wie in 5 dargestellt, wird beispielsweise ein 32-Bit-Datenwert Ri zusammen mit den Schlüsseldaten ki0, ki1 und ki2, die in dem Schlüssel-Speicherteil 322 gespeichert sind, in das nichtlineare Funktionsteil 304 eingegeben. Der Datenwert Ri wird durch beispielsweise XOR-Verknüpfung mit den Schlüsseldaten ki0 in dem ersten schlüsselabhängigen linearen Transformationsteil 341 linear zu Daten Ri* = Ri⨁ki0 transformiert. Dann wird der Datenwert Ri* in dem Teilungsteil 342 in vier Stück beispielsweise 8 Bit breite Daten in0, in1, in2 und in3 aufgeteilt.

In dem nichtlinearen Transformationsteil 3430 werden, wie in 10 dargestellt, beispielsweise die Daten in0 des Weiteren n zwei Unterblöcke in00 und in01 zu beispielsweise 4 Bit aufgeteilt; der Unterblock in00 wird in einem nichtlinearen Unter-Transformationsteil 51 zu Daten mid000 transformiert, und zur gleichen Zeit wird er mit den Daten in01 durch eine XOR-Schaltung 52 XOR-verknüpft, deren Ausgabe in00⨁in01 in einem nichtlinearen Unter-Transformationsteil 53 zu Daten mid001 transformiert wird. Danach werden diese Ausgaben mid000 und mid001 durch eine XOR-Schaltung 54 XOR-verknüpft, und deren Ausgabe und der Datenwert mid001 werden zu dem Datenwert mid00 kombiniert. Demnach teilt das nichtlineare Transformationsteil 3430 die Eingabe in0 in zwei Unterblöcke auf, führt dann eine lineare Transformation und eine nichtlineare Transformation der beiden Unterblöcke durch und kombiniert die zwei resultierenden Ausgabe-Unterblöcke zu der Ausgabe des nichtlinearen Transformationsteils. In ähnlicher Weise werden die anderen verbleibenden Datenstücke in1, in2 und in3 zu Daten mid01, mid02 und mid03 in den nichtlinearen Transformationsteilen 3431, 3432 und 3433 transformiert, wovon jedes die in 10 gezeigte funktionale Konfiguration besitzt, die zwei nichtlineare Transformationsteile und zwei XOR-Schaltungen aufweist.

Diese transformierten Datenstücke mid00, mid01, mid02 und mid03 werden in das zweite in 7 gezeigte schlüsselabhängige lineare Transformationsteil eingegeben, welches die Schlüsseldaten ki1 verwendet. Das Transformationsteil 344 führt die vorstehend genannten Operationen der Gleichungen (7-1) bis (7-4) durch.

Dann wird der Datenwert mid10 in das nichtlineare Transformationsteil 3450 mit derselben in 10 gezeigten funktionalen Konfiguration eingegeben, in welchem er weiter in zwei Unterblöcke mid100 und mid101 aufgeteilt wird. Der Unterblock mid100 wird in dem nichtlinearen Unter-Transformationsteil 51 zu Daten out00 transformiert. Die Unterblöcke mid100 und mid101 werden durch die XOR-Schaltung 52 XOR-verknüpft, und deren Ausgabe mid100⨁mid101 wird in dem nichtlinearen Transformationsteil 53 zu Daten out01 transformiert. Dann werden die zwei Datenstücke out00 und out01 durch die XOR-Schaltung 54 XOR-verknüpft, und deren Ausgabe out00⨁out01 und die Daten out01 werden zu out0 kombiniert. In ähnlicher Weise werden die anderen verbleibenden Datenstücke mid11, mid12 und mid13 zu den Daten out1, out2 und out3 in den nichtlinearen Transformationsteilen 3451, 3452 und 3453 transformiert, wovon jedes die in 10 gezeigte Konfiguration besitzt, die zwei nichtlineare Unter-Trainsformationsteile 51, 53 und zwei XOR-Schaltungen 52, 54 aufweist.

Die vier auf diese Weise nichtlinear transformierten Datenstücke out0, out1, out2 und out3 werden in dem Kombinationsteil 346 zu einem einzelnen Stück Daten Yi* kombiniert. Schließlich wird der Datenwert Yi* linear zu einem Datenwert Yi transformiert, beispielsweise durch eine ki2-Bit-Linksrotation in dem dritten schlüsselabhängigen linearen Transformationsteil 347 unter Verwendung der Schlüsseldaten ki2, wodurch die Ausgabedaten Yi des nichtlinearen Funktionsteils 304 erzeugt werden.

Wie vorstehend beschrieben werden gemäß dieser Ausführungsform in jedem nichtlinearen Transformationsteil 3430 bis 3433 und 3450 bis 3453 die Eingabedaten in zwei Stück Daten aufgeteilt, die in den zwei nichtlinearen Unter-Transformationsteilen (51 und 53 in 10) nichtlinear transformiert werden. Somit ist es möglich, in die nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 Daten mit einer Bitlänge einzugeben, die zweimal größer ist als diejenige von Daten, mit denen die 16 nichtlinearen Untertransformationsteile 51 und 53 umgehen können. Wenn man beispielsweise annimmt, dass die nichtlinearen Untertransformationsteile 8-Bit-Boxen sind, sind alle Eingabedaten zu den nichtlinearen Transformationsteilen 3430 bis 3433 und 3450 bis 3453 16 Bit lang, und die Eingabedaten zu dem nichtlinearen Funktionsteil 304 sind 64 Bit lang. Daher kann in der Datentransformationsvorrichtung von 4 die Blocklänge 128 Bit betragen.

Die nichtlinearen Unter-Transformationsteile 51 und 53 sind parallel zueinander in Gruppen von je acht angeordnet, und ihre nichtlinearen Transformationsverfahren sind nicht miteinander assoziiert und können daher parallel zueinander ausgeführt werden. Wenn darüber hinaus p die differentiellen/linearen Wahrscheinlichkeiten der nichtlinearen Unter-Transformationsteile 51 und 53 repräsentiert, liefert das nichtlineare Funktionsteil 304 insgesamt eine differentielle/lineare Wahrscheinlichkeit p4.

In Obigem müssen das erste schlüsselabhängige Transformationsteil 341, das zweite schlüsselabhängige Transformationsteil 344 und das dritte schlüsselabhängige Transformationsteil 347 nicht immer schlüsselabhängig sein, d.h. die lineare Transformation kann auch in Unterdaten ausgeführt werden.

In Obigem wurde die Datenverarbeitung als eine beschrieben, die unter Verwendung einer Hardware-Struktur ausgeführt wird, diese kann jedoch auch mit einer Software implementiert werden, die einem Programm folgt. Beispielsweise ist 11 ein Flussdiagramm, das den prinzipiellen Teil des Verfahrens zur Datenverarbeitung zeigt. 11 zeigt das Verfahren, das dem gesamten Verfahren von 4 entspricht.

Schritt S1: Initialisiere eine Variable i, die die Wiederholungszahl der Verarbeitung repräsentiert, auf 0.

Schritt S2: Führe eine Anfangstransformation eines eingegebenen Klartextes aus und teile diesen in linke und rechte Blockdaten Li und Ri.

Schritt S3: Verarbeite die rechten Blockdaten Ri mit einer nichtlinearen Funktion unter Verwendung des Unterschlüssel ki, um Blockdaten Yi zu erzeugen.

Schritt S4: Führe eine lineare Verarbeitung der linken Blockdaten Li mit den Blockdaten Yi durch, um die Blockdaten Li* zu erzeugen.

Schritt S5: Tausche die rechten Blockdaten Ri in neue linke Blockdaten Li und die Blockdaten Li* in neue rechte Blockdaten Ri.

Schritt S6: Erhöhe die Variable i um eins.

Schritt S7: Überprüfe um zu sehen, ob i N erreicht hat, und falls nicht, kehre zu Schritt S3 zurück und wiederhole die Schritte S3 bis S7.

Schritt S8: Falls in Schritt S7 entschieden wird, dass die Variable i N erreicht hat, kombiniere die linken und die rechten Daten Li und Ri und gib das Ergebnis der abschließenden Transformation als Ausgabedaten C aus.

Details des Verfahrens von Schritt S3 in 11 entsprechen dem von dem nichtlinearen Funktionsteil 304 von 5 durchgeführten Verfahren, und das Verfahren ist in 12 dargestellt.

Schritt S31: Führe eine erste schlüsselabhängige lineare Transformation der rechten Daten Ri zu den Daten Ri* durch.

Schritt S32: Teile die Daten Ri* in n m-Bit-Daten in0, in1, ..., inn-1 (wobei beispielsweise m = 8 und n = 4).

Schritt S33: Lies die Daten mid00, mid01, ..., mid0(n-1) aus den n ersten S-Boxen unter Verwendung der Daten in0, in1, ..., inn-1 als Adressen aus.

Schritt S34: Führe eine schlüsselabhänige lineare Transformation der Daten mid00 bis mid0(n-1) durch den Unterschlüssel ki1 aus, um Daten mid00 to mid1(n-1) zu erzeugen.

Schritt S35: Lies die Daten out0 to outn-1 aus den n zweiten S-Boxen unter Verwendung der Daten mid10 bis mid1(n-1) als Adressen aus.

Schritt S36: Kombiniere die Daten out0 bis outn-1 zu Daten Y*i.

Schritt S37: Führe eine dritte schlüsselabhängige lineare Transformation der Daten Y*i aus, um Daten Yi zu erzeugen, und gib diese aus.

Die Operationen in Schritt S34 können die Operationen der Gleichungen (7-1) bis (7-4) oder der Gleichung (9) unter Verwendung der Definitionen der Gleichungen (8-1) bis (8-4) sein. Obwohl 11 das Verfahren zeigt, bei dem die Schritte S3 bis S7 mit der Anzahl von einbezogenen Runden wiederholt werden, können die individuellen Verfahren durch die in 4 gezeigten Runden-Verarbeitungsteile 380 bis 38N-1 auch intakt programmiert werden, um das Daten-Diffusionsteil gemäß der vorliegenden Erfindung zu implementieren.

Vierte Ausführungsform

Die in 4 gezeigte erste Ausführungsform ist eine Ausführungsform, bei welcher das grundlegende lineare Transformationsteil 344A von 6, das das zweite schlüsselabhängige lineare Transformationsteil 344 des nichtlinearen Funktionsteils 304 (5) darstellt, durch eine 4 × 4 Matrix (demnach vier Eingaben – vier Ausgaben) repräsentiert ist. Die vierte Ausführungsform wird nachstehend in Verbindung mit dem Fall beschrieben, bei welchem das lineare Transformationsteil 344A durch eine 8 × 8 Matrix repräsentiert ist.

13 veranschaulicht die funktionale Konfiguration des Verschlüsselungsverfahrens in der Datentransformationsvorrichtung gemäß der vierten Ausführungsform der vorliegenden Erfindung. Diese Konfiguration selbst ist identisch mit derjenigen der ersten Ausführungsform, unterscheidet sich jedoch von der letzteren bezüglich der Datenlänge und der Teilungszahl n von in dem nichtlinearen Funktionsteil 304 zu teilenden Daten.

Die Eingabedaten M werden in dem schlüsselabhängigen Anfangs-Transformationsteil 302 unter Verwendung der in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten fk transformiert und in dem Teilungsteil 303 in linke und rechte Blockdaten L0 und R0 aufgeteilt. Beispielsweise werden 128-Bit Daten in zwei Stück 64-Bit-Blockdaten L0 und R0 aufgeteilt. Das schlüsselabhängige Anfangs-Transformationsteil 302 führt eine lineare Transformation wie eine Exklusiv-Oder-Operation der Schlüsseldaten fk und der Eingabedaten M, eine Bit-Rotation der Eingabedaten M durch die Schlüsseldaten fk oder eine nichtlineare Transformation durch eine Kombination von Multiplikationen durch.

Der rechte Blockdatenwert R0 wird dem nichtlinearen Funktionsteil 304 zusammen mit den in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten k00, k01 und k02 zugeführt und in dem nichtlinearen Funktionsteil 304 nichtlinear zu einem Datenwert Y0 transformiert. Die Daten Y0 und L0 werden in dem linearen Operationsteil 305 durch eine lineare Operation zu einem Datenwert L0* transformiert. Die Daten L0* und R0 werden in dem Tauschteil 306 einem Datenpositionstausch unterzogen, um L1←R0 und R1←L0* bereitzustellen, und die Datenstücke L1 und R1 werden in das nächste erste Runden-Verarbeitungsteil 381 eingegeben.

Danach wird in i-ten Runden-Verarbeitungsteilen 38i (wobei i = 0, 1, ..., N-1) die gleiche oben genannte Verarbeitung für zwei Stück eingegebene Blockdaten Li und Ri wiederholt. Demnach werden die rechten Blockdaten Ri zusammen mit den Schlüsseldaten ki0, ki1 und ki2 in das nichtlineare Funktionsteil 304 eingegeben und in dem nichtlinearen Funktionsteil 304 nichtlinear zu Blockdaten Yi transformiert. Die Blockdaten Yi und die Blockdaten Li werden durch eine lineare Operation in dem linearen Operationsteil 305 zu Daten Li* transformiert. Die Daten Li* und die Daten Ri werden bezüglich ihrer Datenposition in dem Tauschteil 306 ausgetauscht, demnach Li+1←Ri, Ri+1←Li*. Das lineare Operationsteil 305 führt beispielsweise eine Exklusiv-Oder-Operation durch.

Wenn N die Anzahl an Runden repräsentiert, die geeignet ist, um einer Datentransformationsvorrichtung Sicherheit zu geben, werden zwei Stück linke und rechte Daten LN und RN als das Ergebnis einer derartigen wiederholten Verarbeitung erhalten. Diese Datenstücke LN und RN werden in dem End-Kombinationsteil 307 zu einem einzelnen Blockdatenwert kombiniert; beispielsweise werden die zwei Stück 64-Bit-Daten LN und RN zu 128-Bit-Daten kombiniert. Dann werden die auf diese Weise kombinierten Daten in einem linearen End-Transformationsteil 308 unter Verwendung der in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten ek transformiert, und Ausgabedaten C werden von dem Ausgabeteil 309 als Chiffretext geliefert.

Bei der Entschlüsselung kann der Klartext M von dem Chiffretext C hergeleitet werden, indem das Verschlüsselungsverfahren umgekehrt wird. Insbesondere wenn das schlüsselabhängige End-Transformationsteil 308 eines ist, das eine zu dem schlüsselabhängigen Anfangs-Transformationsteil 302 umgekehrte Transformation durchführt, kann die Entschlüsselung erfolgen, indem der Chiffretext anstatt der Eingabedaten von 13 eingegeben wird und dann die Schlüsseldaten in einer zur 13 umgekehrten Reihenfolge eingegeben werden, d.h. ek, k(N-1)0, k(N-1)1, k(N-1)2, ..., k10, k11, k12, k00, k01, k02, fk.

Als nächstes erfolgt eine detaillierte Beschreibung der internen Konfiguration des nichtlinearen Funktionsteil 304. 14 ist ein Diagramm, das die interne funktionale Konfiguration des nichtlinearen Funktionsteils 304 zeigt.

Der rechte Blockdatenwert Ri wird zusammen mit den in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten ki0, ki1 und ki2 in das nichtlineare Funktionsteil 304 eingegeben. In dem ersten schlüsselabhängigen linearen Transformationsteil 341 wird der rechte Blockdatenwert Ri zu einem Datenwert Ri* = Ri⨁ki0 beispielsweise durch eine XOder-Operation mit den Schlüsseldaten ki0 transformiert. Die auf diese Weise transformierten Daten Ri* werden in dem Teilungsteil 342 in n = 8 Stück Daten in0, in1, in2, ..., in7 aufgeteilt. Die acht Stück Daten in0 bis in7 werden in den nichtlinearen Transformationsteilen 3430 to 3437 nichtlinear zu Daten mid00 bis mid07 transformiert und danach in das zweite schlüsselabhängige lineare Transformationsteil 344 unter Verwendung der Schlüsseldaten ki1 eingegeben.

Das zweite schlüsselabhängige lineare Transformationsteil 344 führt unter den Datenstücken mid00, mid01, mid02, ..., mid07, die von acht Pfaden eingegeben wurden, eine lineare Transformation (XOR-Operation) durch, um neue Daten der acht Pfade bereitzustellen, und führt des weiteren eine lineare Transformation (XOR-Operation) unter diesen Datenteilen der acht Pfade mit acht Stück Schlüsseldaten ki1 durch, um Ausgabedaten mid10, mid11, mid12, ..., mid17 der acht Pfade bereitzustellen. Die acht Stück Daten werden in nichtlineare Transformationsteile 3450, 3451, 3452, ..., 3457 eingegeben, in welchen sie jeweils zu Daten out0, out1, out2, ..., out7 transformiert werden. Diese acht Stück Daten werden in dem Kombinationsteil 346 zu Daten Yi* kombiniert: darüber hinaus, werden die Daten Yi* in dem dritten schlüsselabhängigen linearen Transformationsteil 347 einer linearen Transformation mit Schlüsseldaten ki2 unterworfen, um Ausgabedaten Yi zu erzeugen.

Das zweite schlüsselabhängige lineare Transformationsteil 344 umfasst das lineare Transformationsteil 344A, das wie vorstehend unter Bezugnahme auf 6 beschrieben durch eine n × n Matrix ausgedrückt ist; bei dieser Ausführungsform ist n = 8. In diesem Fall wird angenommen, dass das lineare Transformationsteil bijektiv ist. Demnach ist Rang(P) = 8. Es erfolgt eine Beschreibung der Bestimmung einer 8 × 8 Matrix P, die, wie bei der Ausführungsform 1 beschrieben, einen Maximalwert von nd erreicht. In diesem Fall wird die Sicherheitsschwelle T einzeln in der Reihenfolge T = 8, 7. ...reduziert, und der folgende Algorithmus wird für jeden Wert durchgeführt.

Schritt 1: Lege die Sicherheitsschwelle T fest (wobei T eine ganze Zahl mit 2 ≤ T ≤ n ist).

Schritt 2: Bereite einen Satz von Spaltenvektoren C vor, deren Hamming-Gewichte größer oder gleich T-1 sind.

Schritt 3: Wähle einen Untersatz Pc von acht Spaltenvektoren aus dem Satz C aus. Falls Rang(Pc) ≠ 8, dann wird der Untersatz Pc nicht als Kandidat akzeptiert.

Schritt 3-1: Berechne nd für Pc wie folgt.

Für irgendwelche zwei Spalten (Spalten a, b):

Für irgendwelche drei Spalten (Spalten a, b, c):

Für irgendwelche vier Spalten (Spalten a, b, c d): nd = min{ndi|0 ≤ i ≤ 9}

Intuitiv repräsentieren die Gleichungen nd0 bis nd9 die minimale Anzahl von aktiven S-Boxen in dem zweiten nichtlinearen Transformationsteil 345 (zweiter Term auf der rechten Seite) und die gesamte Anzahl von aktiven S-Boxen (linke Seite) zu jenem Zeitpunkt, wenn die Anzahl von aktiven S-Boxen in dem ersten nichtlinearen Transformationsteil 343 (erster Term auf der rechten Seite) bestimmt wird. Wenn es beispielsweise in dem ersten nichtlinearen Transformationsteil 343 zwei aktive S-Boxen gibt, können deren Differenzwerte jeweils durch &Dgr;za und &Dgr;zb repräsentiert sein. Dann gilt [&Dgr;z'i] = [tia&Dgr;za⨁tib&Dgr;zb] (0 ≤ i < 8)(11)

Insbesondere wenn &Dgr;za = &Dgr;zb, [&Dgr;z'i] = [(tia⨁tib)&Dgr;zn] (0 ≤ i < 8)(12)

Demnach ist in diesem Fall die minimale Anzahl von aktiven S-Boxen durch nd0 gegeben.

Als ein Ergebnis unserer Suche nach der Matrix P mit dem obigen Suchalgorithmus, wurde festgestellt, dass es keine Matrix mit nd ≥ 6 = T gibt, aber 10080 Kandidatenmatrizen mit nd = 5 = T. Demnach beträgt die Unangreifbarkeit der Rundenfunktion, die eine derartige Matrix P verwendet, gegenüber Differential-Verschlüsselungsanalyse p ≤ ps 5. Und die Unangreifbarkeit gegenüber Linearverschlüsselungsanalyse beträgt ebenfalls q ≤ ps 5.

Der Aufbau des linearen Transformationsteils wird unter den oben genannten 10080 Kandidatenmatrizen P bestimmt. Die Bestimmung des Aufbaus durch eine erschöpfende Suche umfasst eine rechnerische Komplexität von ungefähr (8 × 7)16 ≈ 293, wenn 16 XORs verwendet werden – dies kann nicht ausgeführt werden. Dann ist der Aufbau auf einen Aufbau begrenzt, bei dem das lineare Transformationsteil 344A vier Boxen B1 bis B4 mit 8 Eingaben und 4 Ausgaben, wie in 15A dargestellt, umfasst. Die Boxen sind jeweils von vier XOR-Schaltungen, wie in 15B dargestellt, gebildet, und derart gestaltet, dass jede Eingabeleitung eine der XOR-Schaltungen durchläuft. Demnach weist das lineare Transformationsteil 344A insgesamt 16 XOR-Schaltungen auf. In diesem Fall beträgt die rechnerische Komplexität ungefähr (4 × 3 × 2 × 1)4 ≈ 218, was für eine erschöpfende Suche ausreichend klein ist.

Obwohl in 15A vier Transformationsboxen abwechselnd in die Leitungen der rechten und linken Pfade eingefügt sind, können diese Linien festgelegt werden als vier Linien beliebig ausgewählte Leitungen und die restlichen vier Leitungen. Jede Transformationsbox wird mit Eingaben von den vier Leitungen, in welche sie eingefügt ist, und Eingaben von den verbleibenden vier Leitungen versorgt und gibt die Ergebnisse der Transformation an die ersterwähnten vier Leitungen aus.

Als Ergebnis des Absuchens der 10080 mit dem obigen Suchalgorithmus erhaltenen Matrizen nach Matrizen, die die Einheitsmatrix I mit 16 primitiven Operationen (XOR-Operationen) darstellen und den Aufbau von 15 erfüllen, wurde festgestellt, dass es 57 Aufbaumöglichkeiten gibt. Die Matrix P einer dieser Aufbaumöglichkeiten ist unten gezeigt.

In 16 ist ein Beispiel für den Aufbau des linearen Transformationsteils 344A, das diese Matrix verwendet, zusammen mit den nichtlinearen Transformationsteilen 343 und 345 gezeigt. Wie dargestellt, sind vier Transformationsboxen B1 bis B4 abwechselnd in Leitungen von vier linken und rechten Pfaden von acht S-Boxen eingefügt, die das erste lineare Transformationsteil 343 bilden, und daher sind zwei XOR-Schaltungen in jede Leitung eingefügt.

Wie im Falle der 4 × 4 Matrix bei der ersten Ausführungsform kann, wie unten erwähnt, bestimmt werden, ob die Matrix für den Maskenwertpfad in dem linearen Transformationsteil 344A von 16 eine transponierte Matrix der Matrix P ist und ob n1 = 5 gilt. Indem ein Maskenwertpfad in dem linearen Transformationsteil 334A von 16 unter Verwendung von durch das im Anhang befindliche Theorem 2 definierten Verkettungsregeln konstruiert wird, kann die Matrix TP für den Maskenwertpfad wie folgt berechnet werden:

Dies zeigt, dass die Matrix TP eine transponierte Matrix der Matrix P ist. Des Weiteren kann bestätigt werden, dass die minimale Anzahl von aktiven S-Boxen n1 = 5 ist.

17 veranschaulicht konkrete Beispiele des zweiten schlüsselabhängigen linearen Transformationsteils 344, welches das lineare Transformationsteil 344A mit dem oben festgelegten Aufbau und ein Schlüssel-Transformationsteil 344B aufweist.

Das Schlüssel-Transformationsteil 344B berechnet die XORs der Schlüsseldaten ki10 ki11, ki12, ..., ki17 und der Ausgaben aus dem linearen Transformationsteil durch XOR-Schaltungen 630, 631, 632, ..., 637 und erhält Ausgabedaten mid10, mid11, mid12, ..., mid17. Mit einem derartigen in 17 gezeigten funktionalen Aufbau werden die folgenden Operationen durchgeführt. mid10 = mid01⨁mid02⨁mid03⨁mid04⨁mid05⨁mid06⨁ki10(15-1) mid11 = mid00⨁mid02⨁mid03⨁mid05⨁mid06⨁mid07⨁ki11(15-2) mid12 = mid00⨁mid01⨁mid03⨁mid04⨁mid06⨁mid07⨁ki12(15-3) mid13 = mid00⨁mid01⨁mid02⨁mid04⨁mid05⨁mid07⨁ki13(15-4) mid14 = mid00⨁mid01⨁mid03⨁mid04⨁mid05⨁ki14(15-5) mid15 = mid00⨁mid01⨁mid02⨁mid05⨁mid06⨁ki15(15-6) mid16 = mid01⨁mid02⨁mid03⨁mid06⨁mid07⨁ki16(15-7) mid17 = mid00⨁mid02⨁mid03⨁mid04⨁mid07⨁ki17(15-8)

Die obigen Operationen erzeugen die Daten mid10, mid11, mid12, ..., mid17. Übrigens ist der Unterschlüssel ki1 aus acht Stück Daten ki10, ki11, ki12, ..., ki17 aufgebaut. In 17 werden die Datenstücke mid00 bis mid07 jeweils in die Pfade 600 bis 607 eingegeben.

Die XOR-Schaltungen 614, 615, 616, 617 auf den Pfaden 604, 605, 606, 607 berechnen die XORs der Datenwerte mid04 und mid00, mid05 und mid01, mid06 und mid02 bzw. mid07 und mid03.

Die XOR-Schaltungen 610, 611, 612, 613 auf den Pfaden 600, 601, 602, 603 berechnen jeweils die XORs des Datenwerts mid00 und der Ausgabe aus der XOR-Schaltung 616, des Datenwerts mid01 und der Ausgabe aus der XOR-Schaltung 617, des Datenwerts mid02 und der Ausgabe aus der XOR-Schaltung 614, des Datenwerts mid03 und der Ausgabe aus der XOR-Schaltung 615.

Die XOR-Schaltungen 624, 625, 626, 627 auf den Pfaden 604, 605, 606, 607 berechnen jeweils die XORs der Ausgaben aus den XORr-Schaltungen 613 und 614, der Ausgaben aus den XOR-Schaltungen 610 und 615, der Ausgaben aus den XOR-Schaltungen 611 und 616, der Ausgaben aus den XOR-Schaltungen 612 und 617.

Die XOR-Schaltungen 620, 621, 622, 623 auf den Pfaden 600, 601, 602, 603 berechnen jeweils die XORs der Ausgaben aus den XOR-Schaltungen 610 und 624, der Ausgaben der XOR-Schaltungen 611 und 625, der Ausgaben der XOR-Schaltungen 612 und 626, der Ausgaben der XOR-Schaltungen 613 und 627.

Darüber hinaus, XOR-verknüpfen die XOR-Schaltungen 630 bis 637 auf den Pfaden 600 bis 607 jeweils die Ausgaben der XOR-Schaltungen 620 bis 627 und der Schlüsseldaten ki10 bis ki17, wodurch die Ausgaben mid10 bis mid17 der Pfade 600 bis 607 bereitgestellt werden. Demnach sind die Ausgaben mid10 bis mid17 die XORs von sechs Stück Daten, die aus den Eingabedaten mid00 to mid07 ausgewählt sind, und den Schlüsseldaten, und die Ausgaben mid14 bis mid17 sind die XORs von fünf Stück Daten, die aus den Eingabedaten mid00 bis mid07 ausgewählt sind, und den Schlüsseldaten.

Kehren wir zurück zu 14: die Datenstücke mid10, mid11, mid12, ..., mid17 werden in den nichtlinearen Transformationsteilen 3450, 3451, 3452, ..., 3457 nichtlinear zu des Datenstücken out0, out1, out2, ..., out7 transformiert und in den Kombinationsteilen 346 werden die acht Stück Daten out0, out1, out2, ..., out7 zu einem Einzel-Datenstück Yi* kombiniert. Schließlich wird der Datenwert Yi* linear zu einem Datenwert Yi transformiert, beispielweise durch eine ki2-Bit Linksrotation in dem dritten schlüsselabhängigen linearen Transformationsteil 347 unter Verwendung der Schlüsseldaten ki2, wodurch der Ausgabedatenwert Yi des nichtlinearen Funktionsteils 304 erzeugt wird.

Die nichtlinearen Transformationsteile 3430 bis 3437 und 3450 bis 3457 funktionieren genauso wie S-Boxen für DES-Verschlüsselung, und sie werden jeweils beispielsweise durch ein ROM gebildet, das die Eingabedaten als eine Adresse empfängt, aus der die entsprechenden Daten herauszulesen sind.

Die acht nichtlinearen Transformationsteile 3430 bis 3437 sind parallel zueinander angeordnet, ihre Transformationsverfahren sind nicht miteinander assoziiert und können daher parallel zueinander ausgeführt werden. Das gleiche gilt für die nichtlinearen Transformationsteile 3450 bis 3457. Somit können die linearen Transformationsoperationen für jede Gruppe in einem Schritt (insgesamt zwei Schritte) durchgeführt werden. Wenn p die differentielle/lineare Wahrscheinlichkeit der nichtlinearen Transformationsteile 3430 bis 3437 und 3450 bis 3457 repräsentiert, liefert das nichtlineare Funktionsteil 304 insgesamt eine differentielle/lineare Wahrscheinlichkeit p5, wenn das zweite schlüsselabhängige lineare Transformationsteil 344 einen derartigen, in 17 gezeigten Aufbau besitzt. Wenn die Anzahl von Runden der gesamten Datentransformationsvorrichtung 3r ist, wird demnach eine angenäherte Darstellung mit einer Wahrscheinlichkeit von P ≤ p10r erhalten, beispielsweise wenn r = 4 (12 Runden), P ≤ p40. Im Falle von DES-Verschlüsselung entspricht dies 60 oder mehr Runden, wodurch es möglich ist, eine Datentransformationsvorrichtung bereitzustellen, die gegenüber Differential-Verschlüsselungsanalyse und Linear-Verschlüsselungsanalyse ausreichend sicher ist. Übrigens ist das zweite schlüsselabhängige Transformationsteil 344 nicht speziell auf das in 17 gezeigte lineare Transformationsteil beschränkt, sondern kann auch, wie beispielsweise wie in 18 gezeigt, modifiziert sein. In diesem Fall werden die folgenden Operationen durchgeführt. mid10 = mid01⨁mid02⨁mid04⨁mid05⨁mid06⨁mid07⨁ki10(16-1) mid11 = mid01⨁mid02⨁mid03⨁mid04⨁mid06⨁ki11(16-2) mid12 = mid00⨁mid01⨁mid03⨁mid04⨁mid05⨁mid06⨁ki12(16-3) mid13 = mid00⨁mid03⨁mid04⨁mid06⨁mid07⨁ki13(16-4) mid14 = mid00⨁mid02⨁mid03⨁mid05⨁mid06⨁mid07⨁ki14(16-5) mid15 = mid00⨁mid01⨁mid02⨁mid05⨁mid06⨁ki15(16-6) mid16 = mid00⨁mid01⨁mid02⨁mid03⨁mid04⨁mid07⨁ki16(16-7) mid17 = mid00⨁mid02⨁mid04⨁mid05⨁mid07⨁ki17(16-8)

Alternativ kann der Schaltungsaufbau von 19 verwendet werden, wobei dann die folgenden Operationen ausgeführt werden. mid10 = mid00⨁mid01⨁mid04⨁mid05⨁mid06⨁ki10(17-1) mid11 = mid01⨁mid03⨁mid04⨁mid05⨁mid07⨁ki11(17-2) mid12 = mid00⨁mid02⨁mid04⨁mid06⨁mid07⨁ki12(17-3) mid13 = mid02⨁mid03⨁mid05⨁mid06⨁mid07⨁ki13(17-4) mid14 = mid00⨁mid01⨁mid03⨁mid05⨁mid06⨁mid07⨁ki14(17-5) mid15 = mid01⨁mid02⨁mid03⨁mid04⨁mid06⨁mid07⨁ki15(17-6) mid16 = mid00⨁mid01⨁mid02⨁mid04⨁mid05⨁mid07⨁ki16(17-7) mid17 = mid00⨁mid02⨁mid03⨁mid04⨁mid05⨁mid06⨁ki17(17-8)

Wie aus den Operationen von 17 bis 19 deutlich wird, führt das zweite schlüsselabhängige Transformationsteil 344 eine schlüsselabhängige lineare Transformation durch, welche insgesamt acht Stück Ausgabedaten mid10, mid11, mid12, ..., mid17 einbringt, d.h. vier Stück Ausgabedaten, die von sechs Stück Daten abgeleitet sind, die aus den acht Stück Eingabedaten mid00, mid01, mid02, ..., mid07 ausgewählt sind und vier Stück Ausgabedaten, die von fünf Stück Daten abgeleitet sind, die aus den acht Stück Eingabedaten ausgewählt sind. In derartigen Fällen liefert das nichtlineare Funktionsteil 304 insgesamt, wie vorstehend mit Bezug auf 17 beschrieben, eine differentielle/lineare Wahrscheinlichkeit p5.

Die Schlüsseldaten {fk, k00, k01, k02, k10, k11, k12, ..., k(N-1)0, k(n-1)1, k(N-1)2, ek} sind Daten, die bereitgestellt werden, indem der Hauptschlüssel über das Schlüssel-Eingabeteil 320 in das Expansionsschlüssel-Erzeugungsteil 321 eingegeben wird, welches diesen in Schlüsseldaten transformiert und in dem Schlüssel-Speicherteil 322 speichert.

Das erweiterte Schlüsselerzeugungsteil 321 kann in seinem Aufbau identisch ausgeführt werden mit dem in 1 gezeigten erweiterten Schlüsselerzeugungsteil für DES-Verschlüsselung oder einem in dem U. S. Patent Nr. 4,850,019 offenbarten Expansionsschlüssel-Erzeugungsteil.

Da das schlüsselabhängige Anfangs-Transformationsteil 302, das schlüsselabhängige End-Transformationsteil 308 und die schlüsselabhängigen linearen Transformationsteile 341, 344 und 347 schlüsselabhängige lineare Transformationsmittel sind, ist die Datentransformationsvorrichtung auch ausreichend sicher gegenüber anderen Verschlüsselungsanalysetechniken als Differential- und Linear-Verschlüsselungsanalyse.

Die vierte Ausführungsform ist nicht speziell auf die obigen Konstruktionen beschränkt; falls eine Erhöhung der Geschwindigkeit gewünscht ist, kann auf jedes der Teile, auf das schlüsselabhängige Anfangs-Transformationsteil 302, auf das schlüsselabhängige End-Transformationsteil 308 und auf die schlüsselabhängigen linearen Transformationsteile 341, 344 und 347 verzichtet werden, oder diese können zu schlüsselunabhängigen Transformationsmitteln modifiziert werden. In diesem Fall kann die Verschlüsselungsgeschwindigkeit erhöht werden, ohne die Sicherheit gegenüber Differential- oder Linear-Verschlüsselungsanalyse signifikant zu verringern.

Fünfte Ausführungsform

Es erfolgt eine Beschreibung einer modifizierten Form der funktionalen Konfiguration des nichtlinearen Funktionsteils 304 bei der gleichen Datentransformationsvorrichtung wie der in 13 gezeigten fünften Ausführungsform. Der grundsätzliche Aufbau ist der gleiche wie bei der vierten Ausführungsform von 13 mit der Ausnahme, dass die nichtlinearen Transformationsteile 3430 bis 3437 in dem nichtlinearen Funktionsteil 304 von 14 wie die nichtlinearen Transformationsteile 3430', 3431', 3432' und 3433' bei der zweiten in 8A bis 8D dargestellten Ausführungsform modifiziert sind, sodass diese erweiterte Daten ausgeben. Das zweite schlüsselabhängige lineare Transformationsteil 344 ist von demselben Aufbau wie das in 9 gezeigte.

Wie in 13 dargestellt, werden die rechten Blockdaten Ri zusammen mit den in dem Schlüssel-Speicherteil 322 gespeicherten Schlüsseldaten ki0, ki1, ki2 in das nichtlineare Funktionsteil 304 eingegeben. In dem ersten schlüsselabhängigen linearen Transformationsteil 341 werden die Daten Ri beispielsweise mit den Schlüsseldaten ki0 XOR-verknüpft und dadurch wie im Falle von 14 linear zu Daten Ri* = Ri⨁ki0 transformiert. Dann werden die Daten Ri* in dem Teilungsteil 342 in acht Stück Daten in0, in1, in2, ..., in7 aufgeteilt. Die acht Stück Daten in0, in1, in2, ..., in7 werden in den nichtlinearen Transformationsteilen 3430', 3431', 3432', ..., 3437' jeweils nichtlinear zu Daten MID00, MID01, MID02, ..., MID07 transformiert. Das nichtlineare Transformationsteil 3430' ist gestaltet, um die m-Bit-Daten in0 zu den folgenden 8 × m-Bit-Daten zu transformieren. MID00 = [00...0(2), mid00, mid00, mid00, mid00, mid00, 00...0(2), mid00](18-1)

Demnach hat das nichtlineare Transformationsteil 3430' beispielsweise, wie in 20A gezeigt, eine S-Box, die die Daten mid00 in m hochwertigen Bits ausgibt, wie es das nichtlineare Transformationsteil 3430 der vierten Ausführungsform von 14 macht, und "00...0(2)" als m niedrigwertige Bits ausgibt; darüber hinaus zweigt es die Ausgabedaten mid00 zu sechs Pfaden und "00...0(2)" zu zwei anderen Pfaden ab.

Das nichtlineare Transformationsteil 3431' besitzt, wie in 20B dargestellt, eine S-Box 3431, die die Daten mid01 in m hochwertige Bits und "00...0(2)" als m niedrigwertige Bits ausgibt; darüber hinaus zweigt es die Ausgabedaten mid01 zu sechs Pfaden und m-Bit-Daten "00...0" zu zwei anderen Pfaden ab. Die anderen nichtlinearen Transformationsteile 3432' bis 3437' sind auch ähnlich aufgebaut; in 20C ist der Aufbau des nichtlinearen Transformationsteils 3437' gezeigt, die Beschreibung wird jedoch nicht wiederholt. Diese nichtlinearen Transformationsteile 3431' bis 3437' transformieren Daten in1 bis in7 jeweils zu den folgenden Daten MID01 bis MID07. MID01 = [mid01, 00...0(2), mid01, mid01, mid01, mid01, mid01, 00...0(2)](18-2) MID02 = [mid02, mid02, 00...0(2), mid02, 00...0(2), mid02, mid02, mid02](18-3) MID03 = [mid03, mid03, mid03, 00...0(2), mid03, 00...0(2), mid03, mid03](18-4) MID04 = [mid04, 00...0(2), mid04, mid04, mid04, 00...0(2), 00...0(2), mid04](18-5) MID05 = [mid05, mid05, 00...0(2), mid05, mid05, mid05, 00...0(2), 00...0(2)](18-6) MID06 = [mid06, mid06, mid06, 00...0(2), 00...0(2), mid06, mid06, 00...0(2)](18-7) MID07 = [00...0(2), mid07, mid07, mid07, 00...0(2), 00...0(2), mid07, mid07](18-8)

Diese Datenstücke MID00 bis MID07 können in derselben bereits vorstehend in Bezug auf die Gleichungen (8-1) bis (8-4) bei der zweiten Ausführungsform beschriebenen Weise vorbestimmt werden. Demnach sind die Daten MID00 ein Datensatz, der an den Ausgaben der acht Pfade des linearen Transformationsteils 344A von 17 erhalten wird, wenn Datenstücke mid00 und mid02 bis mid07 mit Ausnahme von mid01 alle zu "00...0(2)." festgesetzt sind. Das gleiche gilt für die Daten MID02 bis MID07. Diese nichtlinearen Transformationsteile 3430' bis 3437' können von einem Speicher gebildet werden, aus dem die Datenstücke MID00 bis MID07 direkt unter Verwendung der Daten in0 bis in7 als Adressen ausgelesen werden.

Dann werden die Datenstücke MID00 bis MID07 in das zweite schlüsselabhängige lineare Transformationsteil 344 unter Verwendung der Schlüsseldaten ki1, wie in 21 gezeigt, eingegeben. Das zweite schlüsselabhängige lineare Transformationsteil 344 ist aufgebaut aus XOR-Schaltungen 411 bis 414, wovon jede zwei Stück Eingabedaten XOR-verknüpft, XOR-Schaltungen 421 und 422, wovon jede die Ausgaben aus zwei von diesen XOR-verknüpft, einer XOR-Schaltung 43, die deren Ausgaben XOR-verknüpft, und einer XOR-Schaltung 44, die deren Ausgabe und die Schlüsseldaten ki1 XOR-verknüpft. Mit diesem Aufbau wird die folgende Operation durchgeführt. MID1 = MID00⨁MID01⨁MID02⨁MID03⨁MID04⨁MID05⨁MID06⨁MID07⨁kil(19)

Diese Ausgabe MID1 wird in acht Blöcke aufgeteilt, die als Daten mid10, mid11, mid12, ..., mid17 ausgegeben werden. Schließlich wird die lineare Transformation des zweiten schlüsselabhängigen linearen Transformationsteils 344, ausgedrückt in Einheiten von m-Bit-Unterblöcken, die folgende; mid10 = mid01⨁mid02⨁mid03⨁mid04⨁mid05⨁mid06⨁ki10(20-1) mid11 = mid00⨁mid02⨁mid03⨁mid05⨁mid06⨁mid07⨁ki11(20-2) mid12 = mid00⨁mid01⨁mid03⨁mid04⨁mid06⨁mid07⨁ki12(20-3) mid13 = mid00⨁mid01⨁mid02⨁mid04⨁mid05⨁mid07⨁ki13(20-4) mid14 = mid00⨁mid01⨁mid03⨁mid04⨁mid05⨁ki14(20-5) mid15 = mid00⨁mid01⨁mid02⨁mid05⨁mid06⨁ki15(20-6) mid16 = mid01⨁mid02⨁mid03⨁mid06⨁mid07⨁ki16(20-7) mid17 = mid00⨁mid02⨁mid03⨁mid04⨁mid07⨁ki17(20-8)

Die obigen Gleichungen drücken eine lineare Transformation aus, die äquivalent ist zu derjenigen der Gleichungen (15-1) bis (15-8), die vorstehend mit Bezug auf die 17 beschrieben wurde. Als Ergebnis werden die gleichen Datenstücke mid10, mid11, mid12, ..., mid17 erzeugt. Übrigens sind die Unterschlüsseldaten kil aus acht Stück Daten ki10, ki11, ki12, ..., ki17 aufgebaut.

Als nächstes werden die acht Stück Daten mid10, mid11, mid12, ..., mid17 in den nichtlinearen Transformationsteilen 3450, 3451, 3452, ..., 3457 von 14 nichtlinear zu acht Stück Daten out0, out1, out2, ..., out7 transformiert, und die acht Stück Daten out0, out1, out2, ..., out7 werden in dem Kombinationsteil 346 zu einem Einzel-Datenwert Yi* kombiniert. Schließlich werden die Daten Yi* zu Daten Yi durch beispielsweise eine ki2-Bit-Linksrotation in dem dritten schlüsselabhängigen linearen Transformationsteil 347 unter Verwendung der Schlüsseldaten ki2 linear transformiert.

Wie in 21 dargestellt, verwendet das zweite schlüsselabhängige lineare Transformationsteil 344 acht XOR-Schaltungen, implementiert jedoch die zu 17 (die 24 XOR-Schaltungen verwendet) äquivalente lineare Transformation, und daher erlaubt diese eine schnellere Transformation als bei der vierten Ausführungsform.

Des Weiteren sind wie im Falle der vierten Ausführungsform die acht nichtlinearen Transformationsteile 3430 bis 3433 und 3450 bis 3453 parallel zueinander angeordnet, deren nichtlineare Transformationsverfahren sind nicht miteinander assoziiert und können daher parallel zueinander ausgeführt werden. Des Weiteren wird, wenn p die differentielle/lineare Wahrscheinlichkeit p der nichtlinearen Transformationsteile 3430' bis 3437' repräsentiert, die Differential/Linearwahrscheinlichkeit der nichtlinearen Funktion 304 insgesamt p5.

In Obigem kann das zweite (schlüsselabhängige) lineare Transformationsteil 344 die Transformation durch XOR-Operation der eingegebenen Unterdaten unabhängig von dem Schlüssel ki1 durchführen. Demnach kann auf die XOR-Schaltungen 630 bis 637 von 17 und die diesen entsprechenden Schaltungen in 18, 19 und 21 verzichtet werden.

Darüber hinaus müssen in Obigem das erste schlüsselabhängige lineare Transformationsteil 341, das zweite schlüsselabhängige Transformationsteil 344 und das dritte schlüsselabhängige Transformationsteil 347 nicht immer schlüsselabhängig sein, demnach kann die lineare Transformation auch an Unterdaten ausgeführt werden, ohne Schlüsseldaten in diese einzugeben.

Die Datentransformationsverarbeitung bei der oben beschriebenen vierten und fünften Ausführungsform kann auch implementiert werden, indem ein Programm mit deren Verfahren durch einen Computer durchgeführt wird. Das Verfahren ist das gleiche wie in 11 und 12 gezeigt; daher wird keine Beschreibung wiederholt.

22 veranschaulicht ein Beispiel der Systemkonfiguration, bei welcher ein Programm für die in Verbindung mit der ersten bis fünften Ausführungsform beschriebene Datentransformationsverarbeitung auf einem Speichermedium vorab gespeichert ist und von diesem zur Ausführung der Datentransformation gemäß der vorliegenden Erfindung herausgelesen wird. Eine zentrale Verarbeitungseinheit (Central Processing Unit, CPU) 110, ein Festwertspeicher (Read-Only Memory, ROM) 120, ein Speicher mit wahlfreiem Zugritt (Random Access Memory, RAM) 130, eine Speichervorrichtung (beispielsweise eine Festplatte (hard disc) HD) 140, eine I/O Schnittstelle 150 und einen Bus, der diese miteinander verbindet, bilden einen gewöhnlichen Computer 100. Das Programm zur Implementierung des Datentransformationsverfahrens gemäß der vorliegenden Erfindung ist auf einem Speichermedium wie der Festplatte HD vorab gespeichert. In dem ROM 120 sind entsprechende S-Boxen in tabellarischer Form gespeichert. Bei der Ausführung der Datentransformation wird das Programm von der Festplatte HD 140 aus in den RAM 130 eingelesen und nach Eingabe des Klartextes M über die Schnittstelle 150 wird das Programm unter der Kontrolle der CPU 110 durchgeführt, und die resultierenden Ausgabedaten C werden über die Schnittstelle 150 ausgegeben.

Das Programm für das Datentransformationsverfahren kann eines sein, das in einer beliebigen externen Speichervorrichtung 180 vorab gespeichert ist. In einem derartigen Fall kann das Programm genutzt werden, nachdem dieses einmal über einen Treiber 170 von der externen Speichervorrichtung 180 zu der Festplatte 140 oder dem RAM 130 transferiert wurde.

Wenn, obwohl dies nicht dargestellt ist, die Ausgabedaten C über eine Kommunikationsleitung oder das Internet versendet werden, ist nur eine Person, die einen gemeinsamen geheimen Schlüssel besitzt, berechtigt, die Ausgabedaten C zu entschlüsseln. Da die gemäß der vorliegenden Erfindung transformierten Daten C gegenüber einer Differential-Verschlüsselungsanalyse und einer Linear-Verschlüsselungsanalyse höchst widerstandsfähig sind, ist es möglich, eine Übertragung von Informationen mit erhöhter Sicherheit zu erreichen.

Übrigens, wenn das Schlüssel-Planungsteil 20 bei jeder Ausführungsform denselben in 3 gezeigten Aufbau besitzt, werden die in dem Daten-Diffusionsteil 10 als ki und ki+1 benutzten Unterschlüssel zu den Ausgaben Q2j und Q2j+1 (wobei i = 2j) aus dem Schlüssel-Verarbeitungsteil 21j in dem Schlüssel-Planungsteil 20. Andererseits, da es die Unterschlüssel kN und kN-1 sind, die durch Differential-Verschlüsselungsanalyse oder Linear-Verschlüsselungsanalyse leicht analysiert werden können, erlaubt eine Kombination von Daten-Diffusionsteilen mit diesen Stücken von Information eine Vereinfachung beim Auffinden anderer Unterschlüssel.

Die unten beschriebene Ausführungsform ist dazu gedacht, dieses Problem zu lösen, indem ein komplexerer Schlüssel-Planungs-Algorithmus in dem Schlüssel-Planungsteil 20 zur Erzeugung von Unterschlüsseln in der Datentransformationsvorrichtung von 4 verwendet wird, die typisch ist für die oben beschriebenen Ausführungsformen. Mit Blick darauf, zu verhindern, dass ein Erfolg bei der Analyse der Unterschlüssel kN und kN-1 zu einem Verlust vieler Informationen über die Ausgaben aus anderen Datendiffusionsteilen führt, verwendet die folgende Ausführungsform ein G-Funktionsteil, das die gleiche Funktion ausführt wie das in 3 gezeigte Schlüssel-Diffusionsteil 22 (die Funktion fk in 3); des Weiteren wird ein H-Funktionsteil bereitgestellt, das eine Datenextraktionsfunktion besitzt, mit welcher zur Erzeugung von Unterschlüsseln notwendige Informationen aus einer notwendigen Anzahl von L Komponenten so gleichförmig wie möglich extrahiert werden, die aus L Komponenten ausgewählt sind, die einmal in einem Speicherteil gespeichert wurden, nachdem diese aus dem G-Funktionsteil gemäß einem ersten Aspekt der Schlüsselerzeugung ausgegeben wurden. Gemäß einem zweiten Aspekt werden Teilinformationen, die als Unterschlüssel verwendet werden, in dem H-Funktionsteil aus den von dem G-Funktionsteil ausgegebenen L-Komponenten extrahiert und in einem Speicherteil gespeichert, und notwendige Informationen werden aus einer notwendigen Anzahl von L-Komponenten extrahiert, um damit Unterschlüssel zu erzeugen.

Da im Falle von DES die Unterschlüssel nur durch Tauschen von Bit-Positionen des Hauptschlüssels erzeugt werden, ist das Schlüsselplanungsverfahren schnell. Es gibt jedoch ein Problem; falls nämlich einige Unterschlüssel bekannt sind, kann der entsprechende Hauptschlüssel sofort erhalten werden.

Um eine erhöhte Komplexität in der Beziehung zwischen dem Hauptschlüssel und den Unterschlüsseln ohne eine wesentliche Erhöhung der rechnerischen Komplexität der Schlüsselplanung und ohne eine Erhöhung der Programmgröße des Schlüssel-Planungsteils bereitzustellen, ist die G-Funktion als die Datendiffusionsfunktion unter Verwendung der in dem Datendiffusionsteil zu verwendenden F-Funktion oder einer Subroutine konstruiert, die die F-Funktion bildet (wobei diese Funktionen nachfolgend mit f bezeichnet sind), und eine Vielzahl von Zwischenwerten L wird durch wiederholte Anwendung der G-Funktion erzeugt.

Die G-Funktion ist daran angepasst, mit zwei Eingabekomponenten (Y, v) zu arbeiten und drei Ausgabekomponenten (L, Y, v) zu erzeugen. Die Bits der Komponente Y sind größer als oder gleich den Bits des Hauptschlüssels K.

Um dem Datendiffusionsteil Unterschlüssel zuzuführen, wird die G-Funktion eine notwendige Anzahl (M) von Malen aufgerufen, um M Komponenten L (wobei 0 ≤ j ≤ M-1) zu erzeugen. Werden die Ausgaben der G-Funktion, die ein j-tes Mal aufgerufen wurde, durch (Lj, Yj, vj) repräsentiert, dann wird ein Teil dieses Werts als Eingabe (Yj+1 = Yj, vJ+1 = vj) für die ein (j + 1)-tes Mal aufgerufene G-Funktion verwendet. Hier wird angenommen, dass Y0 ein Wert ist, der K enthält, und dass v0 ein vorbestimmter Wert ist (beispielsweise 0).

Für den gegebenen Hauptschlüssel K, wird der Unterschlüssel ki (mit i = 0, 1, 2, ..., N-1) folgendermaßen bestimmt: (Li, (Y1, v1)) = G(Y0, v0)(21) (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (j = 1, 2, ..., M-1)(22) ki = H(i, L1, L2, ..., LM) (i = 0, 1, 2, ..., N-1)(23) wobei die H-Funktion ein Mittel ist, um nach Bedarf von jeder Komponente Li Informationen über die durch das Suffix i festgelegte Bit-Position entsprechend dem Suffix i des Unterschlüssels und den M Komponenten L zu extrahieren, die von der G-Funktion ausgegeben werden.

Sechste Ausführungsform

In 23A ist der Grundaufbau des Schlüsselplanungsteils dieser Ausführungsform zur Anwendung auf ein in 4a gezeigtes Schlüsselplanungsteil 20 gezeigt. Der Hauptschlüssel K wird in ein Zwischenschlüssel-Erzeugungsteil 220 eingegeben; das Zwischenschlüssel-Erzeugungsteil 220 besitzt eine Mehrzahl (M Runden) von G-Funktionsteilen, die in Kaskade arbeiten, und erzeugt Zwischenschlüssel L1 bis LM, die in einem Speicherteil 230 gespeichert werden. Die in dem Speicherteil 230 gespeicherten Zwischenschlüssel L1 bis LM werden einem Unterschlüssel-Erzeugungsteil 240 zugeführt, in welchem Unterschlüssel ki basierend auf einem H-Funktionsteil erzeugt werden. Die Struktur und die Arbeitsweise jedes Teils wird nachstehend genau beschrieben.

Dieses Beispiel ist dazu gedacht, die Sicherheit des in 3 gezeigten Schlüsselplanungsteils durch Verwendung eines in dem vorgenannten US-Patent von Miyaguchi et al. offenbarten Datenrandomisierungsteils zu erhöhen. Diese Ausführungsform wird so beschrieben als würde sie auf das Schlüsselplanungsteil (3) in dem US-Patent von Miyagushi et al. angewendet werden, wenn N = 16.

In 3 werden 16 Q-Komponenten durch 8 (= N/2) Runden von Datendiffusionsteilen erhalten. Hier repräsentiert Qj die entsprechende Q-Komponente. Jede Qj-Komponente ist 16-Bit. Das Unterschlüssel-Erzeugungsteil 240 konstruiert den Unterschlüssel k0 aus dem Wert eines ersten Bits der entsprechenden Qj-Komponente, den Unterschlüssel k1 aus dem Wert eines zweiten Bits der entsprechenden Qj-Komponente und allgemein den Unterschlüssel ki-1 aus dem Wert eines i-ten Bits der Qj-Komponente. Wenn Qj[i] das i-te Bit der Qj-Komponente repräsentiert, dann ist demnach der Unterschlüssel ki durch folgende Gleichung ausgedrückt. Ki-1 = (Q1[i], Q2[i], ..., Qj[i], ..., Q16[i])(24) wobei 1 ≤ i, j ≤ 16.

Dieses Verarbeitungsverfahren wird unten im Rahmen der oben genannten G-Funktion und H-Funktion behandelt. Hier repräsentiert Yj den Wert von 64 Bits, Yj L den Wert von 32 hochwertigen Bits von Yj und Yj R den Wert von 32 niedrigwertigen Bits von Yj.

Wenn die Ausgabe der G-Funktion für die Eingabe (Yj, vj) repräsentiert ist durch (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ 7),(25) dann ist die Ausgabe (Lj+1, (Yj+1, vj+1)) durch die folgenden Gleichungen gegeben. Yj+1L = YjR(26) Yj+1R = Lj+1 = fk(YjL, YjR⨁vj)(27) vj+1 = YjL(28)

Der Unterschlüssel ki ist als eine Funktion von i und L1 bis L8 durch die folgende Gleichung gegeben. Ki-1 = H(i, L1, L2, ..., L8)(29)

Wenn jedes Li durch (tj (1), tj (2), ..., tj (32)) repräsentiert ist, dann konstruierte die H-Funktion den Unterschlüssel ki folgendermaßen: Ki = (t1(i), t1(16+i), t2(16+i), ..., t8(i), t8(16+i) (1 ≤ i ≤ 16)(30)

Da dieses Verfahren maximal 16 Unterschlüssel liefert, kann der in dem US-Patent von Miyaguchi et al. beschriebene Verschlüsselungsalgorithmus für die Struktur mit maximal 8 Runden von F-Funktionen verwendet werden.

Nachstehend wird unter Bezugnahme auf 24 das in 23A gezeigte Zwischenschlüssel-Erzeugungsteil 220 beschrieben. G-Funktionsteile 22-1 bis 22-8 sind in Kaskade bereitgestellt. Der Hauptschlüssel K wird als Y0 in das erste Runden-G-Funktionsteil 22-1 zusammen mit einer Konstante v0 eingegeben, und Yj-1 und vj-1 werden in das G-Funktionsteil 22-j jeder j-ten Runde eingegebenen; jedes G-Funktionsteil randomisiert Yj-1 und gibt Lj, Yj und vj aus. Lj ist ein Zwischenschlüssel, und Yj und vj werden in das nächste G-Funktionsteil 22-(j + 1) eingegeben. Nachdem Y0 = K und v0 = 0 festgesetzt sind, wird das G-Funktionsteil 22 acht Mal aufgerufen. Der Aufbau des G-Funktionsteils ist in 25 dargestellt, für welchen das folgende Verfahren von j = 0 bis j = 7 wiederholt wird.

Schritt 1: Nach der Eingabe von Yj und vj in das G-Funktionsteil 22-(j + 1), teile Yj mit einem Teilungsteil 221 von 25 in zwei Blöcke (Yj L, Yj R) auf.

Schritt 2: Gib Yj L als vj+1 aus. Gib Yj L in ein Datendiffusionsteil (fk) 222 ein.

Schritt 3: Gib Yj R in ein Datentauschteil 224 ein. Gib Yj R und vj in eine XOder-Schaltung 223 ein, um Yj R⨁vj zu berechnen und gib das Rechenergebnis in das Datendiffusionsteil (fk) 222 ein.

Schritt 4: Nach Empfang von Yj L und Yj R⨁vj als Eingaben in dieses gibt das Datendiffusionsteil (fk) 222 das Berechnungsergebnis als Lj+1 aus und zur gleichen Zeit in das Tauschteil 224 ein.

Schritt 5: Nach Empfang von Yj R und des Berechnungsergebnisses Lj+1 des Datendiffusionsteils (fk) 222 macht das Tauschteil 224 Yj R zu Yj+1 L und Lj+1 zu Yj+1 R, verkettet diese zu Yj+1 = (Yj+1 L, Yj+1 R) und gibt dieses aus.

Die acht aus dem G-Funktionsteil 22-1 bis 22-8 ausgegebenen Li-Komponenten werden einmal in dem Speicherteil 230 (23A) gespeichert.

Als nächstes erfolgt unter Bezugnahme auf 26 eine Beschreibung des Aufbaus des H-Funktionsteils, das als das Unterschlüssel-Erzeugungsteil 240 dient. Das H-Funktionsteil 240 führt die folgenden Schritte nach Auslesen der acht L-Komponenten L1 bis L8 aus dem Speicherteil 230 aus.

Schritt 1: Lies jede Komponente Li aus dem Speicherteil 230 aus und gib diese in einen Bit-Teiler 241 ein, um diese folgendermaßen bitweise aufzuteilen: (tj(1), tj(2), ..., tj(32)) = Lj (j = 1, 2, ..., 8)(31)

Schritt 2: Gib (t1 (i), t1 (16+i), t2 (i), t2 (16+i), ..., t8 (i), t8 (16+i)) in einen Bit-Kombinierer 242 ein, um den Unterschlüssel folgendermaßen zu erhalten: ki = (t1(i), t1(16+i), t2(i), t2(16+i), ..., t8(i), t8(16+i)) (i = 1, 2, .., 16)(32)

Siebte Ausführungsform

Unter Bezugnahme auf die 23B, 24, 25 und 27A erfolgt eine Beschreibung einer weiteren Ausführungsform, die den gleichen Unterschlüssel wie die sechste Ausführungsform ausgibt.

Wie in 23B gezeigt, werden eine Vielzahl von Zwischenschlüsseln Lj in dem Zwischenschlüssel-Erzeugungsteil 220 erzeugt. Das Zwischenschlüssel-Erzeugungsteil 220 ist in seinem Aufbau identisch mit dem in 23A gezeigten; d.h. es weist eine Vielzahl von in 24 gezeigten G-Funktionsteilen 22 auf. Nach jedem Erzeugen des Zwischenschlüssels Lj in dem G-Funktionsteil 22 wird der Zwischenschlüssel Lj in das Unterschlüssel-Erzeugungsteil 250 eingegeben, von dem aus Bit-Positions-Information, die durch das Suffix i des Unterschlüssels ki und seine Bit-Position q bestimmt ist, als Information kiq ausgegeben und in dem Speicherteil 260 gespeichert wird.

Demnach wiederholen das Zwischenschlüssel-Erzeugungsteil 220 und das Unterschlüssel-Erzeugungsteil 250 die folgenden Schritte 1 bis 7 für jeden Wert von j = 0 bis j = 7.

Schritt 1: Nach Eingabe von Yj und vj in das G-Funktionsteil 22-(j + 1), teile mit dem Teilungsteil 221 Yj in zwei Blöcke (Yj L, Yj R) auf.

Schritt 2: Gib Yj L als vj+1 aus. Und gib Yj L in das Datendiffusionsteil (fk) 222 ein.

Schritt 3: Gib Yj R in das Tauschteil 224 ein. Und gib Yj R und vj in die XOR-Schaltung 223 ein, um Yj R⨁vj zu berechnen und gib dieses in das Datendiffusionsteil (fk) 222 ein.

Schritt 4: Nach Empfang von Yj L und Yj R⨁vj gibt das Datendiffusionsteil (fk) 222 sein Rechenergebnis als Lj+1 in das Unterschlüssel-Erzeugungsteil 250 (23B) und gleichzeitig in das Tauschteil 224 ein.

Schritt 5: Nach Empfang von Yj R und dem Berechnungsergebnis Lj+1 aus dem Datendiffusionsteil (fk) 222 macht das Tauschteil 224 Yj R zu Yj+1 L und Lj+1 zu Yj+1 R, verkettet diese dann zu Yj+1 = (Yj+1 L, Yj+1 R) und gibt dieses aus.

Schritt 6: Wie in 27 dargestellt, gibt das Unterschlüssel-Erzeugungsteil 250 Lj in einen Bit-Teiler 251 ein, um dieses folgendermaßen bitweise zu teilen: (tj(1), tj(2), ..., tj(32)) = Lj (j = 1, 2, ..., 8),(33) und gibt diese dann in einen Informationsverteiler 252 ein.

Schritt 7: Die in den Informationsverteiler 252 eingegebene Bitkette (tj (1), tj (2), ..., tj ( 32 )) ist Information über die Bit-Position von Lj, die durch die Bit-Position des Unterschlüssels ki für ein Suffix i bestimmt ist, das als Information über die Bit-Position q des Unterschlüssels ki verwendet wird, und ist für jedes Lj in einem von 16 Speicherbereichen des Speicherteils 260 gespeichert, der für jeden Unterschlüssel aufgeteilt ist. ki = (t1(i), t1(16+i), t2(i), t2(16+i), ..., t8(i), t8(16+i))(34)

Schritt 8: Wenn 16-Bit-Informationen für jeden ki festgesetzt sind, d.h. wenn der Unterschlüssel ki erzeugt ist, gib seinen Wert (i = 1, 2, ..., 16) aus.

Achte Ausführungsform

Im Hinblick auf eine Reduzierung der Vorrichtungsgröße oder der Anzahl von Programmschritten verwendet diese Ausführungsform bei der Schlüsselplanung eine zur Verschlüsselung genutzte F-Funktion.

Diese Ausführungsform wird auch im Rahmen der G- und H-Funktion beschrieben.

Die Ausgabe der G-Funktion für die Eingabe (Yj, vj) sei repräsentiert durch (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ 7), und die Ausgabe sei folgendermaßen festgesetzt:

Die folgenden Definitionen sind gegeben. Y(i)j+i = f(Y(i)j) (i = 1, 2, 3, 4)(36) L(0)j+1 = vj(37) L(i)j+1 = f(L(i-1)j+1)⨁ Y(i)j+1 (i = 1, 2, 3, 4)(38) vj+1 = L(4)j+1(39)

Des Weiteren sind in ki = H(i, L1, L2, ..., L8)(40) die folgenden Definitionen gegeben. qi+4j = L(i+1)j+1 (i = 0, 1, 2, 3)(41) (t(0)i, t(1)i, ..., t(7)i = qi (i = 0, 1, ..., 31)(42)

Nimm an, dass [i/2] in Gleichung (43) ⌊i/2⌋ repräsentiert.

Dieser Vorgang wird nachstehend unter Bezugnahme auf die 28 und 26 beschrieben.

Vorbereitung

Schritt 1: Setze als v0 einen Wert fest, der aus 0123456789abcdef101112....(hex) mit derselben Anzahl von Bits wie die Bit-Länge der Funktion f extrahiert ist.

Schritt 2: Setze den Hauptschlüssel K auf Y0.

Erzeugung des Zwischenschlüssels: Der folgende Vorgang wird für j = 0, 1, 2, ..., 7 wiederholt.

Schritt 1: Teile die Eingabe Yj gleichmäßig in vier Stücke (Yj (1), Yj (2), Yj (3), Yj (4)).

Schritt 2: Berechne für i = 1, 2, 3, 4 Yj+1 (i) = f(Yj (i)) mit dem Datendiffusionsteil 611 bis 614.

Schritt 3: Setze Lj+1 = vj.

Schritt 4: Berechne für I = 1, 2, 3, 4 f(Lj+1 (i–1)) mit dem Datendiffusionsteil 621 bis 624, und gib das Berechnungsergebnis in eine XOR-Schaltung 63i ein, um dieses mit Yj+1 (i) XOR zu verknüpfen, um Lj+1 (i) = f(Lj+1 (i–1))⨁Yj+1 (i) zu erhalten.

Schritt 5: Setze Yj+1 = (Yj+1 (1), Yj+1 (2), Yj+1 (3) Yj+1 (4)).

Schritt 6: Setze Lj+1 = Lj+1 (1), Lj+1 (2), Lj+1 (3), Lj+1 (4)).

Schritt 7: Setze vj+1 = Lj+1 (4).

Erzeugung des Unterschlüssels: Wie im Falle der sechsten Ausführungsform wird die Gleichung (43) implementiert, um k1, k2, ..., kN (mit N ≤ 16) zu erhalten.

Diese Ausführungsform ist nicht speziell auf die obige begrenzt, sie kann auch in folgender Weise ausgeführt werden:

  • (1) Wenn Y0 größer ist als K, dann wird K als ein Teil von Y0 verwendet und der verbleibende Teil wird mit einer Konstante ausgefüllt.
  • (2) Eine beliebige Konstante wird als v0 verwendet.
  • (3) Die Bit-Länge der entsprechenden Zeichen werden beliebig in den Bereichen festgesetzt, in welchen sie zueinander harmonisiert sind.
  • (4) Andere als für die Verschlüsselung genutzte Funktionen werden als f verwendet.
  • (5) Ein Teil von Li wird nicht verwendet, um N zu berechnen, d.h. dies geschieht, wenn die Anzahl von Unterschlüsseln ki klein ist und die Bits von Lj groß sind.
  • (6) H wird in der gleichen Weise berechnet wie bei der sechsten Ausführungsform.
  • (7) G wird in der gleichen Weise berechnet wie bei der sechsten Ausführungsform.
  • (8) Wie im Falle der siebten Ausführungsform wird nach jeder Erzeugung eines Zwischenschlüssels, jedoch nicht nach Erzeugung aller Zwischenschlüssel, das Rechenergebnis in dem Speicherteil 260 in der entsprechenden Bit-Position von ki gespeichert.

Das Zwischenschlüssel-Erzeugungsteil 220, die Unterschlüssel-Erzeugungsteile 240 und 250 können ausgestaltet sein, um unter der Programmkontrolle durch den in 22 dargestellten Computer betrieben zu werden.

WIRKUNG DER ERFINDUNG

Wie oben im Detail beschrieben ist gemäß der vorliegenden Erfindung die in einer Verschlüsselungsvorrichtung zum Verbergen von Daten zu verwendende Datentransformationsvorrichtung derart ausgestaltet, dass diese die Anforderungen an die Sicherheit und eine Erhöhung der Geschwindigkeit zugleich erfüllt, wodurch Sicherheit und ein schneller Verschlüsselungsvorgang gewährleistet werden, ohne die Anzahl von Runden erheblich zu erhöhen. Daher ist die vorliegende Erfindung zur Verwendung in einer Verschlüsselungsvorrichtung des Verschlüsselungssystems mit gemeinsamem Schlüssel geeignet, das Daten unter Verwendung eines geheimen Schlüssels in Blöcken verschlüsselt oder entschlüsselt.

Darüber hinaus, auch wenn k6, k7, k8, k9, k10 und k11 bei der sechsten und siebten Ausführungsform bekannt sind, sind gemäß der Schlüssel-Planung der vorliegenden Erfindung nur 12 Bits (beispielsweise 6te, 7te, 8te, 9te, 10te, 11te, 22te, 23te, 24te 25te, 26te and 27te Bits) der entsprechenden Li-Komponenten bekannt. Somit sind die bei DES und in dem US-Patent von Miyaguchi et al aufgekommenen Probleme hinsichtlich der Sicherheit des Schlüssel-Planungsteils gelöst worden.

ANHANG Schreibweisen

  • #{a|cond}: Anzahl von Sätzen, die die Bedingung cond. erfüllen
  • &Dgr;x, &Ggr;x: Differenzwert von x, Maskenwert von x
  • a·b: Parität des bitweisen logischen Produkts von a und b
  • Lineares Transformationsteil: P = [tij], tij∊{0, 1}, 0 ≤ i, j ≤ n-1
  • Eingabe in lineares Transformationsteil: z = T[z0, ..., zn-1], zi∊GF(2m), 0 ≤ i ≤ n-1
  • Ausgabe aus linearem Transformationsteil; z' = T[z'0, ..., z'n-1] = Pz, z'i∊GF(2m), 0 ≤ i ≤ n-1

Definitionen

[Definition 1] Für irgendein gegebenes &Dgr;x, &Dgr;y, &Ggr;x, &Ggr;y sind die differentielle und die lineare Wahrscheinlichkeit DPs(&Dgr;x→&Dgr;y) und LPs(&Ggr;y→&Ggr;x) einer S-Box folgendermaßen definiert: DPs(&Dgr;x→&Dgr;y) = #{x∊GF(2m)|s(x) + s(x + &Dgr;x) = &Dgr;y}/2m LPs = (&Ggr;y→&Ggr;x) = (2 × #{x∊GF(2m)|x·&Ggr;x = s(x)·&Ggr;y}/2m-1)2

[Definition 2] Die maximale differentielle und lineare Wahrscheinlichkeit ps und qs einer S-Box sind folgendermaßen definiert:

[Definition 3] Bei der Differential-Verschlüsselungsanalyse wird eine S-Box, deren Differenzwert &Dgr;x nicht gleich Null ist, als aktive S-Box bezeichnet, und bei der Linear-Verschlüsselungsanalyse wird eine S-Box, deren Ausgabe-Maskenwert &Ggr;y nicht gleich Null ist, als aktive S-Box bezeichnet.

[Definition 4] Für irgendein gegebenes &Dgr;x, &Dgr;y, &Ggr;x, &Ggr;y sind die charakterische differentielle und lineare Wahrscheinlichkeit p(&Dgr;x→&Dgr;y) und q(&Ggr;y→&Ggr;x) einer Rundenfunktion mit 2-Runden-SPN-Struktur folgendermaßen definiert: wobei &Dgr;x = (&Dgr;x0, ..., &Dgr;xn-1) und ebenso für &Dgr;y, &Ggr;x und &Ggr;y. p(&Dgr;z→&Dgr;z'i) bezeichnet eine Transformation durch das lineare Transformationsteil von &Dgr;z zu &Dgr;z'i für jedes i. Demnach, für i, ∃&Dgr;z'is,t,p(&Dgr;z→&Dgr;z'i) = 1. Ebenso für p(&Ggr;z'→&Ggr;zi).

[Definition 5] Die maximale charakterische differentielle und lineare Wahrscheinlichkeit p und q einer Rundenfunktion mit 2-Runden-SPN-Struktur sind folgendermaßen definiert:

[Definition 6] Wenn alle S-Boxen bijektiv sind: dann ist die minimale Anzahl nd und nl von aktiven S-Boxen in einer Rundenfunktion mit 2-Runden-SPN-Struktur für die differentielle Verschlüsselungsanalyse und die lineare Verschlüsselungsanalyse jeweils folgendermaßen definiert: wobei Hw(z) = #{0 ≤ i < n|zi ≠ 0

Des Weiteren bezeichnen &Dgr;z und &Ggr;z die Eingabedifferenz und die Eingabe-Maskenwerte des linearen Transformationsteils, und &Dgr;z' und &Ggr;z' die Ausgabedifferenz und die Ausgabe-Maskenwerte des linearen Transformationsteils.

[Theorem 1]

Die maximale charakteristische differentielle und lineare Wahrscheinlichkeit p und q in einer Rundenfunktion mit 2-Runden-SPN-Struktur gelten für die folgenden Beziehungen:

[Beweisskizze]

Betrachte den Fall von differentieller Verschlüsselungsanalyse. Aus den Definitionen 2 und 3 ist die differentielle Wahrscheinlichkeit in der aktiven S-Box durch ps begrenzt. Wenn ndz die Anzahl an aktiven S-Boxen für &Dgr;x und &Dgr;y repräsentiert, ist folglich die charakteristische differentielle Wahrscheinlichkeit einer Rundenfunktion durch ps ndz durch Definition 4 nach unten begrenzt. Wenn andererseits nd die minimale Anzahl von aktiven S-Boxen repräsentiert, dann gilt nd ≤ ndz' und ps ≤ 1 für alle &Dgr;x und &Dgr;y, so dass

Daher ist die maximale charakteristische differentielle Wahrscheinlichkeit p dieser Rundenfunktion Das gleiche gilt für den Fall von linearer Verschlüsselungsanalyse und

[Theorem 2] Verkettungsregeln

Wenn X⫞(Y, Z) bezeichnet, dass die Daten X in Daten Y und Daten Z verzweigt werden. D.h. X = Y = Z. Dann gelten die folgenden Beziehungen. X = Y⨁Z ⇒ &Dgr;X = &Dgr;Y⨁&Dgr;Z, &Ggr;X = &Ggr;Y = &Ggr;Z (XOR-Operation) X⫞(Y, Z) ⇒ &Dgr;X = &Dgr;Y = &Dgr;Z, &Ggr;X = &Ggr;Y⨁&Ggr;Z (Verzweigungsvorgang)

[Widerstandsfähigkeit gegenüber differentieller Verschlüsselungsanalyse und linearer Verschlüsselungsanalyse]

Wie mit der Gleichung von Theorem 1 angegeben kann die Widerstandsfähigkeit der Rundenfunktion gegenüber differentieller und linearer Verschlüsselungsanalyse aus der minimalen Anzahl nd und nlvon aktiven S-Boxen bestimmt werden. Zum Beispiel, da die durch eine Matrix PE lineare repräsentierte Transformation bijektiv ist, gilt Hw(&Dgr;z') ≥ 1, wenn Hw(&Dgr;z) ≥ 2 ist, und Hw(&Dgr;z') ≥ 3, wenn Hw(&Dgr;z) ≥ 1 ist; somit kann die Anzahl an aktiven S-Boxen niemals 2 werden und nd ≥ 3. Übrigens, wenn beispielsweise &Dgr;z0 = &Dgr;z2 ≠ 0 und &Dgr;z1 = &Dgr;z3 = 0 ist, gilt &Dgr;z'0 = &Dgr;z2 ≠ 0 und &Dgr;z'1 = &Dgr;'z2 = &Dgr;z'3 = 0 (Hw(&Dgr;z') = 1), und die Anzahl von aktiven S-Boxen ist Hw(&Dgr;z) + Hw(&Dgr;z') = 3. Demnach ist nd = 3, und gemäß Theorem 1 ist die Widerstandsfähigkeit dieser Rundenfunktion p ≤ ps 3. Das gleiche gilt für nl, und demnach kann bewiesen werden, dass q ≤ qs 3.


Anspruch[de]
Datentransformationsvorrichtung, die ein Schlüssel-Speichermittel (322) zur Speicherung mehrerer Stück Schlüsseldaten und eine Mehrzahl von in Kaskade miteinander verbundenen Runden-Verarbeitungsteilen (38) hat, wovon jedes aus einem nichtlinearen Funktionsteil (304) aufgebaut ist, das mit den mehreren Stück Schlüsseldaten versorgt wird, um eine schlüsselabhängige nichtlineare Transformation durchzuführen, wodurch Eingabedaten in Abhängigkeit von Schlüsseldaten zu verschiedenen Daten transformiert werden, wobei das nichtlineare Funktionsteil (304) jedes Runden-Verarbeitungsteils (38) aufweist:

erste schlüsselabhängige lineare Transformationsmittel (341) zum linearen Transformieren von Eingabedaten in das Runden-Verarbeitungsteil (38) basierend auf ersten Schlüsseldaten, die in dem Schlüssel-Speichermittel (322) gespeichert sind;

ein Teilungsmittel (342) zum Teilen der Ausgabedaten aus dem ersten schlüsselabhängigen Transformationsmittel (341) in n Stück Unterdaten, wobei n eine ganze Zahl größer oder gleich 4 ist;

ein erstes nichtlineares Transformationsmittel (343) zum nichtlinearen Transformieren jedes der n Teile von Unterdaten;

ein zweites schlüsselabhängiges lineares Transformationsmittel (344) zum linearen Transformieren der aus jedem der ersten nichtlinearen Transformationsmittel (343) ausgegebenen Unterdaten basierend auf zweiten Schlüsseldaten, die in dem Schlüssel-Speichermittel gespeichert sind;

zweite nichtlineare Transformationsmittel (345) zum nichtlinearen Transformieren von n Stück ausgegebenen Unterdaten aus dem zweiten schlüsselabhängigen linearen Transformationsmittel (344); und

ein Kombinationsmittel (346) zum Kombinieren von n Stück ausgegebenen Unterdaten aus den zweiten nichtlinearen Transformationsmitteln (345), um die Ausgabe aus dem nichtlinearen Funktionsteil (304) bereitzustellen;

wobei das zweite schlüsselabhängige lineare Transformationsmittel (344) eine lineare Transformationsschicht umfasst, wobei die Eingabe in dieses unter Verwendung von durch eine n × n-Matrix definierten XOR-Operationen linear transformiert wird.
Datentransformationsvorrichtung nach Anspruch 1, die des Weiteren aufweist:

ein Anfangs-Teilungsmittel (303) zum Teilen der Eingabedaten in zwei Stück Daten;

ein nichtlineares Funktionsmittel, das mit einem der beiden Datenstücke beliefert wird;

ein lineares Operationsmittel zum Veranlassen der Ausgabedaten aus dem nichtlinearen Funktionsmittel, auf das andere Datenstück einzuwirken; und

ein End-Kombinationsmittel (307) zum Kombinieren von zwei Stück Daten zu einem einzelnen Stück Ausgabedaten.
Datentransformationsvorrichtung nach Anspruch 2, die des Weiteren ein Anfangs-Transformationsmittel (302) zum Transformieren der Eingabedaten und zum Liefern der transformierten Eingabedaten an das Anfangs-Teilungsmittel (303) aufweist. Datentransformationsvorrichtung nach Anspruch 2 oder 3, die des Weiteren ein End-Transformationsmittel (308) zum Transformieren der Ausgabedaten aus dem End-Kombinationsmittel (307) aufweist, um Ausgabedaten aus der Datentransformationsvorrichtung bereitzustellen. Datentransformationsvorrichtung nach Anspruch 3 oder 4, bei der wenigstens eines der Anfangs-Transformationsmittel (302) und End-Transformationsmittel (308) ein schlüsselabhängiges Transformationsmittel ist, das eine Transformation basierend auf in dem Schlüssel-Speichermittel (322) gespeicherten Schlüsseldaten durchführt. Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 5, bei der das nichtlineare Funktionsteil (304) ausgestattet ist mit einem dritten schlüsselabhängigen linearen Transformationsmittel (347) zum linearen Transformieren der Ausgabedaten aus dem Kombinationsmittel (346) basierend auf dritten, in dem Schlüssel-Speichermittel (322) gespeicherten Schlüsseldaten, um die Ausgabe aus dem nichtlinearen Funktionsteil (304) bereitzustellen. Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 6, bei der das erste schlüsselabhängige lineare Transformationsmittel (341), das zweite schlüsselabhängige lineare Transformationsmittel (344) und/oder das dritte schlüsselabhängige lineare Transformationsmittel (347) ein lineares Transformationsmittel ist, das eine feste lineare Transformation durchführt. Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 7, bei der das erste nichtlineare Transformationsmittel (343) und das zweite nichtlineare Transformationsmittel (345) jeweils ausgestattet sind mit: einem Mittel zum Teilen der in dieses eingegebenen Unterdaten in zwei Unterblöcke; einem Mittel zum Ausführen linearer Transformation und nichtlinearer Transformation jedes der beiden geteilten Unterblöcke in Kaskade; und einem Mittel zum Kombinieren der transformierten Unterblöcke aus den kaskadierten Transformationsmitteln, um transformierte Ausgabe-Unterdaten bereitzustellen, die den Eingabe-Unterdaten entsprechen. Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 8, bei der die n × n-Matrix gebildet ist aus n Spaltenvektoren, deren Hamming-Gewichte für eine vorbestimmte Sicherheits-Schwelle T größer oder gleich T-1 sind. Datentransformationsvorrichtung nach Anspruch 9, bei der die Matrix aus einer Vielzahl von Matrizen-Kandidaten ausgewählt ist, die einen Maximalwert von nd liefern, wobei nd die minimale Anzahl von aktiven S-Boxen ist. Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 10, bei der die n × n-Matrix eine 4 × 4-Matrix ist. Datentransformationsvorrichtung nach Anspruch 11, bei der das zweite schlüsselabhängige lineare Transformationsmittel (344) aufweist:

ein Mittel (344A), das in dieses vier Daten A1, A2, A3 und A4 aus dem ersten nichtlinearen Transformationsmittel (343) eingibt, B1 = A1⨁A3⨁A4 B2 = A2⨁A3⨁A4 B3 = A1⨁A2⨁A3 B4 = A1⨁A2⨁A4 berechnet, um Daten B1, B2, B3 and B4 zu produzieren; und

ein Mittel (344B), das ebenfalls mit Schlüsseldaten k2 = [k21, k22, k23, k24] aus dem Schlüssel-Speichermittel (322) beliefert wird und XOR-Operationen durch die Schlüsseldaten k21, k22, k23 und k24 mit den Daten B1, B2, B3 bzw. B4 durchführt, um vier Stück Unterdaten zu produzieren, die an das zweite nichtlineare Transformationsmittel (345) zu liefern sind.
Datentransformationsvorrichtung nach Anspruch 11, bei der:

das erste nichtlineare Transformationsmittel (343) für vier Stück m-Bit Unterdaten in1, in2, in3 und in4 aus dem Teilungsmittel (342) aufweist: Mittel zum Transformieren von in1 zu 4m-Bit-Daten MI1 = [A1, 00...0(2), A1, A1]; Mittel zum Transformieren von in2 zu 4m-Bit-Daten MI2 = [00...0(2), A2, A2, A2]; Mittel zum Transformieren von in3 zu 4m-Bit-Daten MI3 = [A3, A3, A3, 00...0(2)]; und Mittel zum Transformieren von in4 zu 4m-Bit Daten M14 = [A4, A4, 00...(2), A4]; und

das zweite schlüsselabhängige lineare Transformationsmittel (344) ein Mittel (41, 42, 43), das mit den Daten MI1, MI2, MI3 und MI4 aus dem ersten nichtlinearen Transformationsmittel (343) beliefert wird, um B = MI1⨁MI2⨁MI3⨁MI4 zu berechnen; und

ein Mittel (44) aufweist, das ebenfalls mit 4m-Bit-Schlüsseldaten k2 aus dem Schlüssel-Speichermittel (322) beliefert wird und eine XOR-Operation durch die Schlüsseldaten k2 mit B durchführt, um vier Stück Unterdaten zu produzieren, die an das zweite nichtlineare Transformationsmittel (345) geliefert werden.
Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 10, bei der die n × n-Matrix eine 8 × 8-Matrix ist. Datentransformationsvorrichtung nach Anspruch 14, bei der das zweite schlüsselabhängige lineare Transformationsmittel (344) aufweist: ein Mittel (344A), das seine acht Stück Ausgabedaten B1 bis B8 bereitstellt durch Erhalten von vier Stück der Ausgabe-Unterdaten B1, B2, B3 und B4 durch XOR-Operationen unter Verwendung von sechs von acht Stück Unterdaten A1, A2, ..., A8 aus dem ersten nichtlinearen Transformationsmittel (343) und durch Erhalten von vier Stück der Ausgabe-Unterdaten B5, B6, B7 und B8 durch XOR-Operation unter Verwendung von fünf der acht Stück Unterdaten aus dem ersten nichtlinearen Transformationsmittel (343); und ein Mittel (344B), das mit Schlüsseldaten k2 = [k21, k22, k23, k24, k25, k26, k27, k28] beliefert wird, die in dem Schlüssel-Speichermittel (322) gespeichert sind, und XOR-Verarbeitungen durch die Schlüsseldaten k21, k22, k23, k24, k25, k26, k27 und k28 mit den Unterdaten [B1, B2, B3, B4, B5, B6, B7, B8] durchführt, um 8 Stück Unterdaten zu produzieren, die an das zweite nichtlineare Transformationsmittel (345) geliefert werden. Datentransformationsvorrichtung nach Anspruch 14, bei der:

das erste nichtlineare Transformationsmittel (343) ein Mittel ist zum Transformieren von acht Stück m-Bit-Unterdaten in1 bis in8 aus dem Teilungsmittel (342) zu acht Stück 8m-Bit-Unterdaten MI1 = [00...0(2), A1, A1, A1, A1, A1, 00...0(2), A1], MI2 = [A2, 00...0(2), A2, A2, A2, A2, A2, 00...0(2)] MI3 = [A3, A3, 00...0(2), A3, 00...0(2), A3, A3, A3], MI4 = [A4, A4, A4, 00...0(2), A4, 00...0(2), A4, A4], MI5 = [A5, 00...0(2), A5, A5, A5, 00...0(2), 00...0(2), A5], MI6 = [A6, A6, 00...0(2), A6, A6, A6, 00...0(2), 00...0(2)] MI7 = [A7, A7, A7, 00...0(2), 00...0(2), A7, A7, 00...0(2)], und MI8 = [00...0(2), A8, A8, A8, 00...0(2), 00...0(2), A8, A8]; und das zweite schlüsselabhängige lineare Transformationsmittel (344) ein Mittel (411414, 421, 422, 43) umfasst, das mit den Daten MI1 bis MI8 aus dem ersten nichtlinearen Transformationsmittel (343) beliefert wird, um B = MI1⨁MI2⨁MI3⨁MI4⨁MI5⨁MI6⨁MI7⨁MI8 zu berechnen; und

ein Mittel (44), das ebenfalls mit den in dem Schlüssel-Speichermittel (322) gespeicherten 8m-Bit-Schlüsseldaten k2 beliefert wird und eine XOR-Operation durch die Schlüsseldaten k2 mit B durchführt, um acht Stück Unterdaten zu produzieren, die an das zweite nichtlineare Transformationsmittel (345) zu liefern sind.
Ein Speichermedium, auf welchem ein Datentransformationsprogramm gespeichert ist, mit welchem Rundenverarbeitung, die ein nichtlineares Funktionsverfahren zur Ausführung schlüsselabhängiger nichtlinearer Transformationen basierend auf mehreren Stücken von in dem Schlüssel-Speichermittel (322) gespeicherten Schlüsseldaten umfasst, mehrmals in Kaskade ausgeführt wird, um damit Eingabedaten zu verschiedenen Daten in Abhängigkeit von Schlüsseldaten zu transformieren, wobei das nichtlineare Funktionsverfahren der Rundenverarbeitung aufweist:

einen ersten schlüsselabhängigen linearen Transformationsschritt des linearen Transformierens von Eingabedaten zu einem Runden-Verarbeitungsteil (38) basierend auf in dem Schlüssel-Speichermittel (322) gespeicherten ersten Schlüsseldaten;

einen Teilungsschritt des Teilens von Ausgabedaten des ersten schlüsselabhängigen linearen Transformationsschritts in n Stück Unterdaten, wobei n eine ganze Zahl größer oder gleich 4 ist;

einen ersten nichtlinearen Transformationsschritt des nichtlinearen Transformierens jedes der n Stück Unterdaten;

einen zweiten schlüsselabhängigen linearen Transformationsschritt des Durchführens einer linearen Transformation unter Verwendung von zweiten Schlüsseldaten und von von dem nichtlinearen Transformationsschritt ausgegebenen Unterdaten;

einen zweiten nichtlinearen Transformationsschritt des Durchführens einer zweiten nichtlinearen Transformation jedes der n Stück von von dem zweiten schlüsselabhängigen linearen Transformationsschritt ausgegebenen Unterdaten; und

einen Kombinationsschritt des Kombinierens von n Stück von von dem zweiten nichtlinearen Transformationsschritt ausgegebenen Unterdaten zu einem einzelnen Datenstück Daten zum Ausgeben als das Ergebnis des nichtlinearen Funktionsverfahrens;

wobei der zweite schlüsselabhängige lineare Transformationsschritt einen linearen XOR-Transformationsschritt des Ausführens einer durch eine n × n-Matrix definierten XOR-Verarbeitung seiner Eingabe umfasst.
Speichermedium nach Anspruch 17, bei dem das Datentransformationsprogramm aufweist:

einen Anfangs-Teilungsschritt des Teilens der Eingabedaten in zwei Stück Daten;

einen Schritt des Durchführens des nichtlinearen Funktionsverfahrens unter Verwendung eines der beiden Stücke Daten als seine Eingabe;

einen linearen Operationsschritt des Veranlassens der Ausgabedaten aus dem nichtlinearen Funktionsverarbeitungsschritt, auf das andere Stück Daten einzuwirken; und

einen End-Kombinationsschritt des Kombinierens der beiden Stücke Daten zu einem einzelnen Stück Ausgabedaten.
Speichermedium nach Anspruch 18, bei dem das Datentransformationsprogramm einen Anfangs-Transformationsschritt des Transformierens der Eingabedaten und des Lieferns der transformierten Eingabedaten an den Anfangs-Teilungsschritt umfasst. Speichermedium nach Anspruch 18 oder 19, bei dem das Datentransformationsprogramm einen End-Transformationsschritt des Transformierens der aus dem End-Kombinationsschritt ausgegebenen Daten umfasst, um Ausgabedaten bereitzustellen. Speichermedium nach Anspruch 19 oder 20, bei dem von Anfangs-Transformationsschritt und End-Transformationsschritt des Datentransformationsprogramms wenigstens einer ein schlüsselabhängiger Transformationsschritt des Durchführens von Transformation basierend auf Schlüsseldaten ist. Speichermedium nach einem der Ansprüche 17 bis 21, bei dem der nichtlineare Funktionsverarbeitungsschritt einen dritten schlüsselabhängigen linearen Transformationsschritt des linearen Transformierens der aus dem Kombinationsschritt ausgegebenen Daten basierend auf dritten in dem Schlüssel-Speichermittel (322) gespeicherten Schlüsseldaten umfasst, um die Ausgabe aus dem nichtlinearen Funktionsverarbeitungsschritt bereitzustellen. Speichermedium nach einem der Ansprüche 17 bis 22, bei dem der erste schlüsselabhängige lineare Transformationsschritt, der zweite schlüsselabhängige lineare Transformationsschritt und/oder der dritte schlüsselabhängige lineare Transformationsschritt ein linearer Transformationsschritt des Durchführens einer festen linearen Transformation ist. Speichermedium nach einem der Ansprüche 17 bis 23, bei dem der erste nichtlineare Transformationsschritt und der zweite nichtlineare Transformationsschritt jeweils umfassen: einen Teilungsschritt des Teilens der in diese eingegebenen Daten in zwei Unterblöcke, einen Schritt des Durchführens linearer Transformation eines jeden der beiden geteilten Unterblöcke, einen Schritt des Durchführens linearer Transformation und nichtlinearer Transformation in Kaskade eines jeden der beiden geteilten Unterblöcke und einen Schritt des Kombinierens der durch den Kaskaden-Transformationsschritt transformierten Unterblöcke zu den Eingabedaten entsprechenden nichtlinear transformierten Ausgabedaten. Speichermedium nach einem der Ansprüche 17 bis 24, bei dem die n × n-Matrix gebildet ist aus n Spaltenvektoren, deren Hamming-Gewichte für eine vorbestimmte Sicherheitsschwelle T größer oder gleich T-1 sind. Speichermedium nach Anspruch 25, bei dem die Matrix diejenige aus einer Vielzahl von Matrix-Kandidaten ausgewählte ist, die einen Maximalwert von nd liefert, wobei nd die minimale Anzahl von aktiven S-Boxen ist. Speichermedium nach einem der Ansprüche 17 bis 26, bei dem die n × n-Matrix eine 4 × 4-Matrix ist. Speichermedium nach Anspruch 27, bei dem der zweite schlüsselabhängige Transformationsschritt umfasst: einen Schritt des Eingebens von vier Daten A1, A2, A3 und A4 in diesen durch den ersten nichtlinearen Transformationsschritt, des Berechnens von B1 = A1⨁A3⨁A4 B2 = A2⨁A3⨁A4 B3 = A1⨁A2⨁A3 B4 = A1⨁A2⨁A4, um Daten B1, B2, B3 und B4 zu produzieren; und

einen Schritt des Eingebens von Schlüsseldaten k2 = [k21, k22, k23, k24] aus dem Schlüssel-Speichermittel (322) und des Durchführens von XOR-Operationen durch die Schlüsseldaten k21, k22, k23 und k24 mit den Daten B1, B2, B3 bzw. B4, um vier Stück Unterdaten zu produzieren, die dem zweiten nichtlinearen Transformationsschritt zu liefern sind.
Speichermedium nach Anspruch 27, bei dem:

der erste nichtlineare Transformationsschritt aufweist: für vier Stück m-Bit Unterdaten in1, in2, in3 und in4 aus dem Teilungsschritt einen Schritt des Transformierens von in1 in 4m-Bit-Daten MI1 = [A1, 00...0(2), A1, A1], einen Schritt des Transformierens von in2 in 4m-Bit-Daten MI2 = [00...0(2), A2, A2, A2]; einen Schritt des Transformierens von in3 in 4m-Bit-Daten MI3 = [A3, A3, A3, 00...0(2)]; und einen Schritt des Transformierens von in4 im 4m-Bit-Daten MI4 = [A4, A4, 00...(2), A4]; und

der zweite schlüsselabhängige lineare Transformationsschritt aufweist: einen Schritt des Eingebens der Daten MI1, MI2, MI3 und MI4 durch den ersten nichtlinearen Transformationsschritt, des Berechnens von B = MI1⨁MI2⨁MI3⨁MI4; und

einen Schritt des Eingebens von 4m-Bit-Schlüsseldaten k2 aus dem Schlüssel-Speicherteil (322) und des Durchführens einer XOR-Operation durch die Schlüsseldaten k2 mit B, um vier Stück Unterdaten zu produzieren, die an das zweite nichtlineare Transformationsmittel (345) zu liefern sind.
Speichermedium nach einem der Ansprüche 17 bis 26, bei dem die n × n-Matrix eine 8 × 8-Matrix ist. Speichermedium nach Anspruch 30, bei dem der zweite schlüsselabhängige Transformationsschritt aufweist: einen Schritt des Erhaltens von vier Stücken der ausgegebenen Unterdaten B1, B2, B3 und B4 durch XOR-Operationen unter Verwendung von sechs von acht Stück Unterdaten A1, A2, ..., A8 des ersten nichtlinearen Transformationsschritts und des Erhaltens von vier Stück ausgegebenen Unterdaten B5, B6, B7 und B8 durch XOR-Operation unter Verwendung von fünf von acht Stück Unterdaten des ersten nichtlinearen Transformationsschritts; und

einen Schritt des Eingebens von in dem Schlüssel-Speichermittel (322) gespeicherten Schlüsseldaten k2 = [k21, k22, k23, k24, k25, k26, k27, k28] und des Durchführens von XOR-Operationen durch die Schlüsseldaten k21, k22, k23, k24, k25, k26, k27 und k28 mit den Unterdaten [B1, B2, B3, B4, B5, B6, B7, B8], um acht Stück Unterdaten zu produzieren, die durch den zweiten nichtlinearen Transformationsschritt verarbeitet werden.
Speichermedium nach Anspruch 30, bei dem:

der erste nichtlineare Schritt ein Schritt des Transformierens von acht Stück m-Bit-Unterdaten in1 bis in8 durch den Teilungsschritt in acht Stück 8m-Bit-Daten ist MI1 = [00...0(2), A1, A1, A1, A1, A1, 00...0(2), A1], MI2 = [A2, 00...0(2), A2, A2, A2, A2, A2, 00...0(2)] MI3 = [A3, A3, 00...0(2), A3, 00...0(2), A3, A3, A3], MI4 = [A4, A4, A4, 00...0(2), A4, 00...0(2), A4, A4 ], MI5 = [A5, 00...0(2), A5, A5, A5, 00...0(2), 00...0(2), A5], MI6 = [A6, A6, 00...0(2), A6, A6, A6, 00...0(2), 00...0(2)] MI7 = [A7, A7, A7, 00...0(2), 00...0(2), A7, A7, 00...0(2)], und MI8 = [00...0(2), A8, A8, A8, 00...0(2), 00...0(2), A8, A8]; und der zweite schlüsselabhängige lineare Transformationsschritt aufweist: einen Schritt des Eingebens der Daten MI1 bis MI8 durch den ersten nichtlinearen Transformationsschritt, des Berechnens von B = MI1⨁MI2⨁MI3⨁MI4⨁MI5⨁MI6⨁MI7⨁M18; und einen Schritt des Eingebens von in dem Schlüssel-Speicherteil (322) gespeicherten 8m-Bit-Schlüsseldaten k1 und des Durchführens einer XOR-Operation durch die Schlüsseldaten k2 mit B, um acht Stück Unterdaten zu produzieren, die von dem zweiten nichtlinearen Transformationsschritt zu verarbeiten sind.
Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 16, welche des Weiteren aufweist:

ein G-Funktionsmittel (220), aufgebaut aus M Runden-Mitteln (22), die mit einem Hauptschlüssel K beliefert werden und Zwischenwerte Lj+1 (j = 0, 1, ..., M-1) erzeugen;

Zwischenwert-Speichermittel (230) zum temporären Speichern jedes der Zwischenwerte Lj aus dem G-Funktionsmittel (220); und

ein H-Funktionsmittel (240), das mit einer Teilinformations-Extraktionsfunktion des Erzeugens von N Unterschlüsseln aus einer Mehrzahl von Lj und zum Speichern derselben als die mehreren Stück Schlüsseldaten in dem Schlüssel-Speichermittel (322) ausgestattet ist;

wobei:

das G-Funktionsmittel (220) den Hauptschlüssel zumindest als einen Teil von Y0 nimmt, Yj und vj in die Ausgabe (Lj, Yj, vj) der j-ten Runde in seine (j + 1)-te Runde eingibt (wobei j = 0, 1, ..., M-1), die Eingaben zerstreut und Lj+1, Yj+1 und vj+1 ausgibt; und

das H-Funktionsmittel (240) i (mit i = 1, 2,..., N) und die im Zwischenwert-Speichermittel (230) gespeicherten L1, L2, ..., LM eingibt, Informationen über Bit-Positionen von Unterschlüsseln ki, die durch das i von den L1, ..., LM, bestimmt sind, extrahiert und diese Unterschlüssel ausgibt, wobei die Unterschlüssel in dem Schlüssel-Speichermittel (322) gespeichert sind.
Datentransformationsvorrichtung nach einem der Ansprüche 1 bis 16, welche des Weiteren aufweist:

ein G-Funktionsmittel (220), das aus M Runden-Mitteln (22) aufgebaut ist, die mit einem Hauptschlüssel K beliefert werden und Zwischenwerte Lj+1 (j = 0, 1, ..., M-1) erzeugen;

ein H-Funktionsmittel (240), das mit einer Teilinformations-Extraktionsfunktion zum Erzeugen von Unterschlüsseln aus einer Vielzahl von Lj, die durch das G-Funktionsmittel (220) erzeugt sind, ausgestattet ist; und

Zwischenwert-Speichermitteln (230) zum Speichern von Ausgaben aus dem H-Funktionsmittel (240) als den Unterschlüsseln ki entsprechende Werte;

wobei:

das G-Funktionsmittel (220) den Hauptschlüssel als zumindest einen Teil von Y0 nimmt, Yj und vj in die Ausgabe (Lj, Yj, vj) der j-ten Runde in seine (j + 1)-te Runde eingibt, die Eingaben zerstreut und Lj+1, Yj+1 und vj+1 ausgibt; und

das H-Funktionsmittel (240) i, q und Lj (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ q ≤ die Anzahl von Bits ki) eingibt und Bit-Positionsinformation von Lj, die durch i und q definiert ist, extrahiert, um Informationen über die Bitposition q der Unterschlüssel ki bereitzustellen, wobei die Unterschlüssel als die Mehrzahl von Schlüsseldaten in dem Schlüssel-Speichermittel (322) gespeichert sind.
Datentransformationsvorrichtung nach Anspruch 33 oder 34, bei der das G-Funktionsmittel (220) aufweist:

ein Datenteilungsmittel (221) zum Teilen der Eingabe Yj in zwei Blöcke (Yj L, Yj R) und zum Ausgeben von Yj L als vj+1;

ein XOR-Mittel (223) zur Berechnung von Yj R⨁vj aus dem Yj R und dem vj;

ein Datendiffusionsmittel (220), das mit dem Yj L und der Ausgabe aus dem XOR-Mittel beliefert wird, um diese zu zerstreuen und um das Ergebnis als Lj+1 auszugeben; und

Datentauschmittel (224) zum Verwandeln von Yj R in Yj+1 L und von Lj+1 in Yj+1 R und zum Verketten von Yj+1 L und Yj+1 R zu einer Ausgabe Yj+1 =(Yj+1 L, Yj+1 R).
Datentransformationsvorrichtung nach Anspruch 33, bei der das H-Funktionsmittel (240) aufweist:

ein Bit-Teilungsmittel (241) zum bitweisen Teilen jedes aus dem Zwischenwert-Speichermittel (230) ausgelesenen Lj in (tj(1), tj(2), ..., tj(2N)) = Lj (j = 1, 2, ..., M); und ein Bit-Kombinationsmittel (242) zum Kombinieren der resultierenden (t1 (i), t1 (N+i), t2 (i), t2 (N+i), ..., tM (i), tM (N+i)) und zum Ausgeben von Unterschlüsseln ki = (t1(i), t1(N+i), t2(i), t2(N+i), ..., tM(i), tM(N+i)) (i = 1, 2, ..., N).
Datentransformationsvorrichtung nach Anspruch 34, bei der das H-Funktionsmittel (240) aufweist:

ein Bit-Teilungsmittel (241) zum bitweisen Teilen jedes Lj in (tj(1), tj(2),..., tj(2N)) = Lj (j = 1, 2, ..., M); und ein Bit-Kombinationsmittel (242) zum Kombinieren der Bits (tj (1), tj (2), ..., tj (2N)), sodass Information über die Bitposition für i, die durch die Bitposition q von ki bestimmt ist, zur Bitposition von ki wird, und zum Ausgeben der Unterschlüssel ki = (t1(i), t1(N+i), t2(i), t2(N+i), ..., tM(i), tM(N+1)) (i = 1, 2, ..., N).
Datentransformationsvorrichtung nach Anspruch 33 oder 34, bei der das G-Funktionsmittel (220) ein Mittel ist, um die folgenden Operationen durchzuführen: für das Ausgabeergebnis wobei: Y(i)j+1 = f(Y(i)j) (i = 1, 2, 3, 4) L(0)j+1 = &ngr;j L(i)j+1 = f (L(i-1)j+1)⨁Y(i)j+1 (i = 1, 2, 3, 4) vj+1 = L(4)j+1; und das H-Funktionsmittel (240) Mittel zum Durchführen der folgenden Operation ist: für ki = H(i, L1, L2, ..., LM) q4i+j = L(i+1)j+1 (i = 0, 1, 2, 3) (t(0)i, t(1)i, ..., t(7)i) = qi (i = 0, 1, ..., 31)






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