In der Geheimschrift ist geradliniger cryptanalysis eine allgemeine Form von cryptanalysis, der auf der Entdeckung affine Annäherungen an die Handlung einer Ziffer gestützt ist. Angriffe sind für Block-Ziffern und Strom-Ziffern entwickelt worden. Geradliniger cryptanalysis ist einer der zwei am weitesten verwendeten Angriffe auf Block-Ziffern; der andere, unterschiedlicher cryptanalysis seiend.

Die Entdeckung wird Mitsuru Matsui zugeschrieben, der zuerst die Technik auf die FEAL Ziffer (Matsui und Yamagishi, 1992) angewandt hat. Nachher hat Matsui einen Angriff auf Data Encryption Standard (DES) veröffentlicht, schließlich hat das Führen zum ersten experimentellen cryptanalysis der Ziffer in der offenen Gemeinschaft berichtet (Matsui, 1993; 1994). Der Angriff auf DES ist nicht allgemein praktisch, 2 bekannte plaintexts verlangend.

Eine Vielfalt von Verbesserungen zum Angriff, ist einschließlich des Verwendens vielfacher geradliniger Annäherungen oder Verbindens nichtlinearer Ausdrücke angedeutet worden, zu einem verallgemeinerten Verteilen cryptanalysis führend. Beweise der Sicherheit gegen geradlinigen cryptanalysis werden gewöhnlich neuer Ziffer-Designs erwartet.

Übersicht

Es gibt zwei Teile zu geradlinigem cryptanalysis. Das erste soll geradlinige Gleichungen bauen, die sich plaintext, ciphertext und Schlüsselbit beziehen, die eine hohe Neigung haben; d. h. wessen Wahrscheinlichkeiten, (über den Raum aller möglichen Werte ihrer Variablen) zu halten, so nah sind wie möglich an 0 oder 1. Das zweite soll diese geradlinigen Gleichungen in Verbindung mit bekannten plaintext-ciphertext Paaren verwenden, um Schlüsselbit abzuleiten.

Das Konstruieren geradliniger Gleichungen

Zu den Zwecken von geradlinigem cryptanalysis drückt eine geradlinige Gleichung die Gleichheit von zwei Ausdrücken aus, die aus zweiwertigen Variablen bestehen, die mit dem exklusiven - oder (XOR) Operation verbunden sind. Zum Beispiel setzt die folgende Gleichung, von einer hypothetischen Ziffer, die XOR Summe der ersten und dritten plaintext Bit fest (als in einem Block-Ziffer-Block), und der erste ciphertext hat gebissen ist dem zweiten Bit des Schlüssels gleich:

P_1 \oplus P_3 \oplus C_1 = K_2.

</Mathematik>

In einer idealen Ziffer würden jede geradlinige Gleichung, die sich plaintext, ciphertext bezieht, und Schlüsselbit mit der Wahrscheinlichkeit 1/2 halten. Da sich die in geradlinigem cryptanalysis befassten Gleichungen in der Wahrscheinlichkeit ändern werden, werden sie mehr genau geradlinige Annäherungen genannt.

Das Verfahren, um Annäherungen zu bauen, ist für jede Ziffer verschieden. Im grundlegendsten Typ der Block-Ziffer, eines Netzes der Ersatz-Versetzung, wird Analyse in erster Linie auf den S-Kästen, dem einzigen nichtlinearen Teil der Ziffer konzentriert (d. h. die Operation eines S-Kastens kann in einer geradlinigen Gleichung nicht verschlüsselt werden). Für kleine genug S-Kästen ist es möglich, jede mögliche geradlinige Gleichung aufzuzählen, die den Eingang des S-Kastens und Produktionsbit verbindet, ihre Neigungen zu berechnen und die besten zu wählen. Geradlinige Annäherungen für S-Kästen müssen dann mit den anderen Handlungen der Ziffer, wie Versetzung und das Schlüsselmischen verbunden werden, um geradlinige Annäherungen für die komplette Ziffer zu erreichen. Das sich anhäufende Lemma ist ein nützliches Werkzeug für diesen Kombinationsschritt. Es gibt auch Techniken, um geradlinige Annäherungen (Matsui 1994) wiederholend zu verbessern.

Das Abstammen von Schlüsselbit

Eine geradlinige Annäherung der Form erhalten:

P_ {i_1} \oplus P_ {i_2} \oplus \cdots \oplus C_ {j_1} \oplus C_ {j_2} \oplus \cdots = K_ {k_1} \oplus K_ {k_2} \oplus \cdots

</Mathematik>

wir können dann einen aufrichtigen Algorithmus (der Algorithmus von Matsui 2) mit bekannten plaintext-ciphertext Paaren anwenden, um auf die Werte der an der Annäherung beteiligten Schlüsselbit zu schätzen.

Für jeden Satz von Werten der Schlüsselbit auf der rechten Seite (gekennzeichnet als ein teilweiser Schlüssel), zählen Sie, wie oft die Annäherung über alle bekannten plaintext-ciphertext Paare für wahr hält; nennen Sie diesen Punkt der Klagebegründung T. Der teilweise Schlüssel, dessen T den größten absoluten Unterschied zur Hälfte der Zahl von plaintext-ciphertext Paaren hat, wird als der wahrscheinlichste Satz von Werten für jene Schlüsselbit benannt. Das ist, weil es angenommen wird, dass der richtige teilweise Schlüssel die Annäherung veranlassen wird, mit einer hohen Neigung zu halten. Der Umfang der Neigung ist hier im Vergleich mit dem Umfang der Wahrscheinlichkeit selbst bedeutend.

Dieses Verfahren kann mit anderen geradlinigen Annäherungen wiederholt werden, das Erreichen schätzt auf Werte von Schlüsselbit, bis die Zahl von unbekannten Schlüsselbit niedrig genug ist, dass sie mit der rohen Gewalt angegriffen werden können.

Siehe auch

• Anhäufen des Lemmas
• Differenzial cryptanalysis

Außenverbindungen

• Ein Tutorenkurs auf dem geradlinigen (und Differenzial) cryptanalysis Block-Ziffern
• "Die Besserung der Zeitkompliziertheit des Geradlinigen Cryptanalysis von Matsui" verbessert die Kompliziertheit dank des Schnellen Fouriers, Gestaltet Um