Wie kann Verschlüsselung Zufälligkeit beinhalten?

8

Wenn ein Verschlüsselungsalgorithmus eine Zeichenfolge in eine andere Zeichenfolge konvertieren soll, die dann wieder in das Original entschlüsselt werden kann, wie könnte dieser Prozess eine Zufälligkeit beinhalten?

Sicherlich muss es deterministisch sein, sonst wie könnte die Entschlüsselungsfunktion wissen, welche Faktoren bei der Erstellung der verschlüsselten Zeichenfolge beteiligt waren?

CJ7
quelle
3
Bitte stellen Sie auf mehreren Stack Exchange-Sites keine identischen Fragen, wie diese auf Crypto.SE .
Paŭlo Ebermann

Antworten:

5

Es kann mehr als einen Chiffretext geben, der demselben Klartext zugeordnet ist. In mathematischen Begriffen muss der Verschlüsselungsalgorithmus injektiv sein, damit Sie den Klartext für den Chiffretext wiederherstellen können. Dies hindert den Chiffretext jedoch nicht daran, mehr Informationen als den Klartext zu codieren.

Betrachten Sie als konkretes Beispiel Modi der Blockverschlüsselungsoperation wie CBC , CTR oder OFB . Alle diese Modi beinhalten zusätzlich zum Klartext, dem Blockverschlüsselungsalgorithmus und seinem Schlüssel eine IV (Initialisierungsvektor). (Für die Klickrate wird die IV als Nonce bezeichnet, spielt jedoch eine ähnliche Rolle.) Die Verschlüsselungsfunktion ist für eine bestimmte IV deterministisch. Die IV kann andererseits zufällig ausgewählt werden (für die Klickrate muss sie zufällig ausgewählt werden). Sofern das Protokoll keine deterministische Methode zur Auswahl der IV angibt (z. B. eine vereinbarte Konstante), wird die IV zusammen mit dem Chiffretext gesendet. Tatsächlich besteht die Ausgabe der Verschlüsselungssoftware häufig aus der IV, gefolgt vom streng sensiblen Chiffretext. Die IV selbst wird im Klartext gesendet; Es enthält (darf) keine vertraulichen Informationen.

Betrachten Sie als weiteres Beispiel den PKCS1.5-Modus („Auffüllschema“) von RSA (definiert in PKCS # 1 Version 1.5 - siehe S.22–25 von PKCS # 1 v2.1 ). Dieser Modus vereinfacht ein Bit und besteht darin, eine zufällige Zeichenfolge mit der Nachricht zu verketten und dann die Exponentiationsoperation anzuwenden. Der Chiffretext ist wobei die Verkettung ist, die Nachricht ist und eine Füllzeichenfolge ist, deren Bits größtenteils zufällig sind. Um die Nachricht aus dem Chiffretext wiederherzustellen , wenden Sie die Rohentschlüsselungsoperation und teilen Sie in Auffüllung (die verworfen wird) und Nachricht auf.(PM)emodnMPCCdmodnC

Gilles 'SO - hör auf böse zu sein'
quelle
4

Nicht nur können Verschlüsselungsverfahren haben Zufälligkeit, aber in einigen Fällen (zB Public-Key - Verschlüsselung), sie müssen randomisiert werden. Dies ist kein Problem, da ein korrektes Verschlüsselungsschema erforderlich ist, dh für jede Nachricht und jeden Schlüssel , der über die Zufälligkeit .mk

Pr[ DEC( ENC(k,m,R) )=m]=1
R

Der Grund , dass die öffentliche Schlüsselschemata zufällig sein muss ergibt sich aus der Art , wie wir Sicherheit definieren: Wir haben nicht den Geheimtext wünschen Leck jegliche Informationen über die verschlüsselte Nachricht. Das klassische Beispiel ist das folgende. Angenommen, ist der öffentliche bzw. der geheime Schlüssel, und der Gegner fängt eine verschlüsselte Nachricht die an eine Einheit im Feld gesendet wird. Der Gegner weiß, dass die Nachricht entweder "ATTACK" oder "RETREAT" ist, weiß aber nicht, welche. Eine Sache, die der Gegner tun kann, ist, beide Nachrichten mit dem öffentlichen zu verschlüsseln . Lassen Sie und . If(pk,sk)cpkcA=ENCpk("ATTACK ")cR=ENCpk("RETREAT")ENCist deterministisch, kann der Gegner die Nachricht mit Sicherheit herausfinden, indem er mit und .ccAcR

Die Art und Weise, wie dieser Begriff formal definiert wird, wird als semantische Sicherheit bezeichnet :

Ein Verschlüsselungsschema ist semantisch sicher, wenn ein Gegner das folgende Spiel nicht mit einer Wahrscheinlichkeit von deutlich mehr als :A1/2

  1. Ein Herausforderer generiert Schlüssel und sendet den öffentlichen Schlüssel an den Gegner.C(pk,sk)pk
  2. A wählt zwei Nachrichten gleicher Länge und und gibt beide an .m0m1C
  3. C wählt gleichmäßig ein Bit und sendet .b{0,1}ENC(mb)
  4. A muss angeben, welche Nachricht verschlüsselt wurde: oder , er muss das Bit ausgeben .m0m1b

(Ich lasse den Sicherheitsparameter weg, der für die Definition von "vernachlässigbar" oder "erkennbar" entscheidend ist. Wir müssen davon ausgehen, dass die Generierung der Schlüssel von abhängt und dass der Vorteil oben liegt ist in vernachlässigbar , dh kleiner als ) κκA1/2κκω(1)

Ran G.
quelle
Wir können am Ende der Eingabe eine zufällige Zeichenfolge hinzufügen, bevor wir die Verschlüsselung durchführen, um das Problem zu vermeiden, und immer , dh die Bedingung kann stärker sein als die oben angegebene . DEC(ENC(k,m,R))=m
Kaveh
3

Sie haben nicht angegeben, um welche Art von Verschlüsselung es sich handelt, aber lassen Sie mich darauf hinweisen, was für die Sicherheit der kartografischen Protokolle wirklich erforderlich ist (zusätzlich zu den Angaben in anderen Antworten).

Was wir wirklich brauchen, ist Folgendes: Die Schlüssel sollten zufällig generiert werden (dies kann in Zusammenarbeit wie bei der Kryptografie mit öffentlichen Schlüsseln wie RSA oder von einer Entität wie bei der Kryptografie mit privaten Schlüsseln erfolgen). Die Zufälligkeit des Schlüssels stellt sicher, dass ein Gegner die Schlüssel nicht vorhersagen kann (und sie verwendet, um das Protokoll zu brechen). Solange die Schlüssel für den Gegner zufällig aussehen, ist das Protokoll sicher. Oft werden die Schlüssel durch einen zufälligen Algorithmus generiert und dann an die Parteien weitergegeben, während die Verschlüsselungs- und Entschlüsselungsalgorithmen nicht zufällig, sondern deterministisch sind.

Denken Sie auch daran, dass eine Randomisierung nicht bedeutet, dass der Prozess nicht invertierbar ist. Ein einfaches Beispiel ist das folgende: Wenn , wird zufällig generiert , ausgegeben . Zum Invertieren können wir den ersten Teil des Paares ausgeben.xrx,r

Kaveh
quelle
Ihr Beispiel ist wichtig: Ohne zufällige Polsterung ist Vanille-RSA unsicher. Mit zufälliger Polsterung kann nachgewiesen werden, dass RSA im zufälligen Orakelmodell
Sasho Nikolov
1

Sowohl der Verschlüsselungs- als auch der Entschlüsselungsalgorithmus können randomisiert werden, solange Sie einen Satz beweisen können, dass die Verschlüsselung gefolgt von der Entschlüsselung die meiste Zeit die ursprüngliche Nachricht liefert .

Warum sollte jemand ein solches Verschlüsselungsschema wollen? Denn: 1) Situationen gibt es , wo wir nicht richtig sein wollen die ganze Zeit , aber nur 99999999 mal jeder von 100 Millionen und 2) ermöglicht so kleine Fehler verbessert oft etwas anderes (wie Effizienz) durch einen unverhältnismäßig hohen Anteil.

Vinayak Pathak
quelle
3
Es gibt zwar probabilistische Verschlüsselung, sie sind jedoch eher exotisch. Viele alltägliche Verschlüsselungsalgorithmen beinhalten Zufälligkeit, ohne probabilistisch zu sein.
Gilles 'SO - hör auf böse zu sein'
@ Gilles: Eine wichtige Unterscheidung zu treffen.
Raphael
0

Um nur ein Beispiel zu nennen: Bei der RSA-Verschlüsselung müssen Sie zwei Primzahlen und und eine Ganzzahl generieren , mit der Ihre öffentlichen und privaten Schlüssel erstellt werden.pqe

Wenn Sie einen dieser Werte deterministisch generieren, kann seine Generierung reproduziert werden, wodurch möglicherweise Ihre Verschlüsselung beeinträchtigt wird. Wenn diese Zahlen zufällig generiert werden, ist dies kein Problem.

Aktualisieren

Als genaueres Beispiel für die Antwort von Ran G. können Sie sich die Kryptographie mit elliptischen Kurven ansehen , bei der der Algorithmus einen zufälligen Parameter (normalerweise als , oder ) zum Ver- und Entschlüsseln von Nachrichten benötigt. Wenn derselbe "zufällige" Parameter mehrmals verwendet wird, kann der Schlüssel aus zwei verschlüsselten Nachrichten berechnet werden. Dies war das Problem / die Prämisse des PlayStation 3-Hacks vom letzten Jahr .dkr

Pedro
quelle
1
Dies ist Zufälligkeit bei der Schlüsselgenerierung, was meiner Meinung nach die Frage ist: Jede Schlüsselgenerierung muss Zufälligkeit beinhalten, andernfalls ist der Schlüssel vorhersehbar (oder abgeleitet und nicht generiert).
Gilles 'SO - hör auf böse zu sein'
Ich denke nicht, dass dies der Ort für die Randomisierung ist, an den das OP denkt. Schlüssel sind gegeben und statisch für die (en | de) Kryption. Wie Sie Ihren Schlüssel auswählen, ist davon unabhängig.
Raphael
@ Gilles: Ich würde es nicht als so eindeutig betrachten. Die Werte , und werden normalerweise in verschlüsselter Form mit einem vom Benutzer gewählten Passwort gespeichert. Genau genommen sind sie der Schlüssel, aber aus Anwendersicht sind sie nur zufällige Werte, die durch Eingabe von Kauderwelsch auf der Tastatur generiert werden, und haben nichts mit dem sorgfältig ausgewählten Passwort zu tun. pqe
Pedro
@Pedro Ich verstehe nicht, wie sich Ihr letzter Kommentar auf die Frage bezieht. Selbst aus der Perspektive von Schlüsseldateien (die ich in der Frage nicht sehe) wird der Schlüssel offensichtlich nicht zufällig generiert, sondern aus der Schlüsseldatei und dem Passwort abgeleitet.
Gilles 'SO - hör auf böse zu sein'