Warum wird XOR in der Kryptographie verwendet?

75

Warum wird in kryptografischen Algorithmen nur XOR verwendet und andere Logikgatter wie OR, AND und NOR werden nicht verwendet?

Bhaskar
quelle
6
Warum glauben Sie, dass dies der Fall ist?
Skaffman
1
Versuchen Sie zu fragen, warum kryptografische Algorithmen nur XOR verwenden? Ich habe XOR woanders benutzt ...
Austin Salonen
3
Austin, er sagt nicht, dass XOR nicht anderswo verwendet wird, aber XOR ist das einzige, das als Verschlüsselungsmethode verwendet wird
1
Keccak (jetzt SHA-2) verwendet XOR, NOT, AND und ROT.
CodesInChaos
1
@Xz_awan Es ist kein Verschlüsselungsalgorithmus . Es ist eine kryptografische Hash-Funktion und somit ein kryptografischer Algorithmus. Die SHA-2-Komprimierungsfunktion basiert auf einer Blockverschlüsselung. | Aber ich habe im obigen Kommentar einen Fehler gemacht, ich wollte "Keccak (jetzt SHA-3) ..." sagen. Im Gegensatz zu Keccak verwendet SHA-2 zusätzlich zu den oben genannten Vorgängen ADD.
CodesInChaos

Antworten:

70

Es ist nicht genau richtig zu sagen, dass die logische Operation XOR die einzige ist, die in der gesamten Kryptographie verwendet wird, es ist jedoch die einzige Zwei-Wege-Verschlüsselung, bei der sie ausschließlich verwendet wird.

Hier wird das erklärt:

Stellen Sie sich vor, Sie haben eine Folge von Binärziffern 10101 und XOR die Zeichenfolge 10111damit, die Sie erhalten00010

Jetzt ist Ihre ursprüngliche Zeichenfolge codiert und die zweite Zeichenfolge wird zu Ihrem Schlüssel. Wenn Sie Ihren Schlüssel mit Ihrer codierten Zeichenfolge XOR-verknüpfen, erhalten Sie Ihre ursprüngliche Zeichenfolge zurück.

Mit XOR können Sie eine Zeichenfolge einfach verschlüsseln und entschlüsseln, mit den anderen Logikoperationen nicht.

Wenn Sie eine längere Zeichenfolge haben, können Sie Ihren Schlüssel wiederholen, bis er lang genug ist. Wenn beispielsweise Ihre Zeichenfolge vorhanden 1010010011ist, schreiben Sie Ihren Schlüssel einfach zweimal und er wird zu 1011110111XOR mit der neuen Zeichenfolge

Hier ist ein Wikipedia-Link zur XOR-Chiffre.


Ziezi
quelle
"Wenn Sie eine längere Saite haben, können Sie Ihren Schlüssel wiederholen, bis er lang genug ist" - Könnten Sie das bitte näher erläutern? Ich denke, das einfache Wiederholen des Schlüssels zum Verschlüsseln eines größeren Textes ist eine wirklich schlechte Idee, da Muster entstehen.
Tiago
@Tiago: Natürlich ist es eine schreckliche Idee, den Schlüssel zu wiederholen, wenn dies im eigentlichen Sinne sicher sein soll. Die klassische Methode zur sicheren Kommunikation mit XOR ist ein "One Time Pad". Sie und die Person, mit der Sie kommunizieren, haben identische Kopien eines beliebig langen Notizbuchs mit zufälligen Bits. Sie XOR so viele Bits wie nötig, um eine Nachricht zu senden, und brennen diesen Teil des Pads unmittelbar danach, um ihn nie wieder zu verwenden. Dies ist logistisch meistens nicht machbar, daher sind in der Praxis klügere Methoden erforderlich. XOR-Chiffren können Bausteine ​​für bessere Techniken sein.
Joshua P. Swanson
45

Ich kann 2 Gründe sehen:

1) (Hauptgrund) XOR gibt keine Informationen über den ursprünglichen Klartext weiter.

2) (Nice-to-have-Grund) XOR ist eine involvierende Funktion , dh wenn Sie XOR zweimal anwenden, erhalten Sie den ursprünglichen Klartext zurück (dh XOR(k, XOR(k, x)) = xwo xist Ihr Klartext und kist Ihr Schlüssel). Das innere XOR ist die Verschlüsselung und das äußere XOR ist die Entschlüsselung, dh genau dieselbe XOR-Funktion kann sowohl für die Verschlüsselung als auch für die Entschlüsselung verwendet werden.

Um den ersten Punkt zu veranschaulichen, betrachten Sie die Wahrheitstabellen von AND, OR und XOR:

Und

0 UND 0 = 0

0 UND 1 = 0

1 UND 0 = 0

1 UND 1 = 1 (Leck!)

Oder

0 ODER 0 = 0 (Leck!)

0 ODER 1 = 1

1 ODER 0 = 1

1 ODER 1 = 1

XOR

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

Alles in der ersten Spalte ist unsere Eingabe (dh der Klartext) . Die zweite Spalte ist unser Schlüssel und die letzte Spalte ist das Ergebnis Ihrer Eingabe "gemischt" (verschlüsselt) mit dem Schlüssel unter Verwendung der spezifischen Operation (dh des Chiffretextes) .

Stellen Sie sich nun vor, ein Angreifer hat Zugriff auf ein verschlüsseltes Byte, z. B. 10010111 , und möchte das ursprüngliche Klartextbyte abrufen .

Angenommen, der AND-Operator wurde verwendet, um dieses verschlüsselte Byte aus dem ursprünglichen Klartextbyte zu generieren. Wenn AND verwendet wurde, wissen wir mit Sicherheit, dass jedes Mal, wenn wir das Bit '1' im verschlüsselten Byte sehen, die Eingabe (dh die erste Spalte, der Klartext) gemäß der Wahrheitstabelle von auch '1' sein muss UND. Wenn das verschlüsselte Bit stattdessen eine '0' ist, wissen wir nicht, ob die Eingabe (dh der Klartext) eine '0' oder eine '1' ist. Daher können wir schließen, dass der ursprüngliche Klartext wie folgt lautet: 1 _ _ 1 _ 111. Es wurden also 5 Bits des ursprünglichen Klartextes durchgesickert (dh es konnte ohne den Schlüssel zugegriffen werden).

Wenn wir dieselbe Idee auf OR anwenden, sehen wir, dass jedes Mal, wenn wir eine '0' im verschlüsselten Byte finden, wir wissen, dass die Eingabe (dh der Klartext) auch eine '0' sein muss. Wenn wir eine '1' finden, wissen wir nicht, ob die Eingabe eine '0' oder eine '1' ist. Daher können wir schließen, dass der eingegebene Klartext: _ 00 _ 0 _ _ _ ist. Diesmal konnten wir 3 Bits des ursprünglichen Nur-Text-Bytes verlieren, ohne etwas über den Schlüssel zu wissen.

Schließlich können wir mit XOR kein Stück des ursprünglichen Klartextbytes erhalten. Jedes Mal, wenn wir im verschlüsselten Byte eine '1' sehen, könnte diese '1' aus einer '0' oder einer '1' generiert worden sein. Gleiches gilt für eine '0' (sie kann sowohl von '0' als auch von '1' stammen). Daher wird kein einziges Bit aus dem ursprünglichen Klartextbyte verloren.

Tiago
quelle
34

Der Hauptgrund ist, dass, wenn eine Zufallsvariable mit unbekannter Verteilung R1 mit einer Zufallsvariablen R2 mit gleichmäßiger Verteilung XOR-verknüpft ist, das Ergebnis eine Zufallsvariable mit gleichmäßiger Verteilung ist. Sie können also eine voreingenommene Eingabe einfach randomisieren, was mit anderen binären Operatoren nicht möglich ist.

Anurag Uniyal
quelle
1
Dieser Punkt ist wirklich wichtig, da er für jede Verteilung von Bits in der Nachricht gilt. Die Bits im Chiffretext sind immer gleichmäßig verteilt, wodurch sichergestellt wird, dass statistische Kryptoanalysetechniken wie die Frequenzanalyse nicht zum Aufbrechen der Chiffre verwendet werden können.
Mistertim
1
Sie müssen R1 und R2 unabhängig sein, damit das Ergebnis einheitlich ist (einfaches Gegenbeispiel: R1 = R2).
Rlandster
@rlandster richtig, aber ich habe nie erwähnt, dass sie abhängig sind? sie sind zufällig + R1 könnte voreingenommen sein, aber R2 ist theoretisch rein zufällig
Anurag Uniyal
2
Dies ist die beste Antwort hier. R1 muss überhaupt nicht zufällig sein und R1 könnte gleich R2 sein. Solange R2 zufällig ist, ist das Ergebnis nicht von zufällig zu unterscheiden. Deshalb ist XOR der Liebling.
Jim Flood
26

Die Ausgabe von XOR hängt immer von beiden Eingängen ab. Dies ist bei den anderen von Ihnen genannten Vorgängen nicht der Fall.

rekursiv
quelle
6

Ich denke, weil XOR reversibel ist. Wenn Sie Hash erstellen möchten, sollten Sie XOR vermeiden.

Denis Masyukov
quelle
Es gibt keinen Grund, warum Hashes reversible Operationen vermeiden sollten. Typischerweise ist der Hauptteil einer Hash-Funktion reversibel, und erst am Ende wird eine irreversible Operation angewendet. Oft besteht diese irreversible Operation vollständig aus XORs.
CodesInChaos
6

XOR ist das einzige Gate, das direkt verwendet wird, da der andere Eingang unabhängig vom Eingang immer einen Einfluss auf den Ausgang hat.

Es ist jedoch nicht das einzige Gate, das in kryptografischen Algorithmen verwendet wird. Das mag für die Kryptographie der alten Schule zutreffen, die Tonnen von Bit-Shuffles und XORs und rotierenden Puffern umfasst, aber für Krypto auf der Basis von Primzahlen benötigen Sie alle Arten von Mathematik, die nicht über XOR implementiert werden.

jprete
quelle
4

XOR wirkt wie ein Kippschalter, mit dem Sie bestimmte Bits ein- und ausschalten können. Wenn Sie eine Zahl (ein Bitmuster) "verschlüsseln" möchten, XOR Sie sie mit einer Zahl. Wenn Sie diese verschlüsselte Nummer nehmen und sie erneut mit derselben Nummer XOR-verknüpfen, erhalten Sie Ihre ursprüngliche Nummer zurück .

210 XOR 145 gives you  67  <-- Your "scrambled" result
 67 XOR 145 gives you 210  <-- ...and back to your original number

Wenn Sie eine Zahl (oder einen Text oder ein beliebiges Bitmuster) mit XOR "verschlüsseln", haben Sie die Grundlage für einen Großteil der Kryptographie.

Robert Cartaino
quelle
3

XOR verwendet weniger Transistoren ( 4 NAND-Gatter ) als kompliziertere Operationen (z. B. ADD, MUL), was die Implementierung in Hardware erleichtert, wenn die Anzahl der Gatter wichtig ist. Darüber hinaus ist ein XOR eine eigene Umkehrung, die sich gut zum Anwenden von Schlüsselmaterial eignet (der gleiche Code kann zum Ver- und Entschlüsseln verwendet werden). Die sehr einfache AddRoundKey- Operation von AES ist ein Beispiel dafür.

Jeff Moser
quelle
2

Bei symmetrischer Krypto sind die einzigen realen Auswahloperationen, die Bits mit der Verschlüsselung mischen und die Länge nicht erhöhen, Operationen, die mit Übertrag, Hinzufügen ohne Übertrag (XOR) und Vergleichen (XNOR) hinzugefügt werden. Jede andere Operation verliert entweder Bits, erweitert sich oder ist auf CPUs nicht verfügbar.

Joshua
quelle
3
Auf gängigen CPUs stehen mehr invertierbare Anweisungen zur Verfügung: Rotation ist eine, Ganzzahlmultiplikation mit einer ungeraden Ganzzahl ist eine andere. Alle werden in einigen modernen Blockchiffren verwendet.
Accipitridae
Ich habe die Rotation weggelassen, weil sie für Krypto alleine nicht wirklich geeignet ist. Ich hätte nie gedacht, dass eine ungerade Ganzzahlmultiplikation invertierbar ist.
Joshua
2

Die XOR-Eigenschaft (a xor b) xor b = a ist praktisch für Stream-Chiffren: Um verschlüsselte Daten zu verschlüsseln, wird eine pseudozufällige Folge von n Bits unter Verwendung des Kryptoschlüssels und des Kryptoalgorithmus erzeugt.

Absender:
Daten: 0100 1010 (0x4A)
Pseudozufallssequenz: 1011 1001 (0xB9)
                        ------------------ ------------------.
verschlüsselte Daten 1111 0011 (0xF3)
                        ------------------ ------------------.

Empfänger:
verschlüsselte Daten 1111 0011 (0xF3)
Pseudozufallsfolge: 1011 1001 (0xB9) (Empfänger hat Schlüssel und berechnet dieselbe Folge)
                        ------------------ ------------------.
                         0100 1010 (0x4A) Daten nach Entschlüsselung
                        ------------------ ------------------.
Babu Srinivasan
quelle
2

Betrachten wir die drei gängigen bitweisen logischen Operatoren

Nehmen wir an, wir können eine Zahl auswählen (nennen wir sie Maske) und sie mit einem unbekannten Wert kombinieren

  • Bei AND geht es darum, einige Bits auf Null zu setzen (diejenigen, die in der Maske auf Null gesetzt sind).
  • Bei OR geht es darum, einige Bits zu eins zu zwingen (diejenigen, die in der Maske auf eins gesetzt sind).

XOR ist subtiler. Sie können den Wert eines Teils des Ergebnisses nicht genau kennen, unabhängig von der gewählten Maske. Wenn Sie Ihre Maske jedoch zweimal anwenden, erhalten Sie Ihren ursprünglichen Wert zurück.

Mit anderen Worten, der Zweck von UND und ODER besteht darin, einige Informationen zu entfernen, und das ist definitiv nicht das, was Sie in kryptografischen Algorithmen (symmetrische oder asymmetrische Verschlüsselung oder digitale Signatur) wollen. Wenn Sie Informationen verlieren, können Sie diese nicht zurückerhalten (entschlüsseln), oder die Signatur würde einige winzige Änderungen in der Nachricht tolerieren und damit ihren Zweck zunichte machen.

Alles, was gesagt wurde, gilt für kryptografische Algorithmen, nicht für deren Implementierungen. Die meisten Implementierungen von kryptografischen Algorithmen verwenden auch viele UNDs, normalerweise um einzelne Bytes aus 32 oder 64 internen Registern zu extrahieren.

Normalerweise erhalten Sie solchen Code (dies ist ein fast zufälliger Auszug aus aes_core.c).

rk[ 6] = rk[ 0] ^
 (Te2[(temp >> 16) & 0xff] & 0xff000000) ^
 (Te3[(temp >>  8) & 0xff] & 0x00ff0000) ^
 (Te0[(temp      ) & 0xff] & 0x0000ff00) ^
 (Te1[(temp >> 24)       ] & 0x000000ff) ^
 rcon[i];
rk[ 7] = rk[ 1] ^ rk[ 6];
rk[ 8] = rk[ 2] ^ rk[ 7];
rk[ 9] = rk[ 3] ^ rk[ 8];

8 XORs und 7 ANDs, wenn ich richtig zähle

kriss
quelle
1

Ich denke, es ist einfach so, weil eine gegebene zufällige Menge von Binärzahlen eine große Anzahl von 'ODER'-Operationen zu allen' Einsen tendieren würde, ebenso würde eine große Anzahl von 'UND'-Operationen zu allen Nullen tendieren. Wobei eine große Anzahl von 'XORs eine zufällige Auswahl von Einsen und Nullen erzeugt.

Dies bedeutet nicht, dass AND und OR nicht nützlich sind - nur, dass XOR nützlicher ist.

Die Prävalenz von OR / AND und XOR in der Kryptographie hat zwei Gründe:

Eine davon sind blitzschnelle Anweisungen.

Zweitens sind sie mit herkömmlichen mathematischen Formeln schwer zu modellieren

James Anderson
quelle
1

XOR ist eine mathematische Berechnung in der Kryptographie. Es ist eine logische Operation. Es gibt andere logische Operationen: AND, OR, NOT, Modulo-Funktion usw. XOR ist die wichtigste und am häufigsten verwendete.

Geben Sie hier die Bildbeschreibung ein

Wenn es das gleiche ist, ist es 0.

Wenn es anders ist, ist es 1.

Beispiel:

Nachricht: Hallo

Binäre Version von Hello: 01001000 01100101 01101100 01101100 01101111

Schlüsselstrom: 110001101010001101011010110011010010010111

Chiffretext mit XOR: 10001110 11000110 00110110 10100001 01001010

Anwendungen: Das One-Time-Pad / die Vern-am-Verschlüsselung verwendet die Exklusiv- oder Funktion, bei der der Empfänger denselben Schlüsselstrom hat und den Chiffretext über einen verdeckten Transportkanal empfängt. Der Empfänger Xor dann den Chiffretext mit dem Schlüsselstrom, um den Klartext von Hallo zu enthüllen. In One Time Pad sollte der Key-Stream mindestens so lang sein wie die Nachricht.

Fakt: Das One Time Pad ist die einzige wirklich unzerbrechliche Verschlüsselung.

Exklusiv oder in der Feistel-Struktur verwendet, die in der Blockverschlüsselung DES algo verwendet wird.

Hinweis: Bei einer XOR-Operation besteht eine 50% ige Chance, 0 oder 1 auszugeben.

Geben Sie hier die Bildbeschreibung ein

Rajesh Prajapati
quelle