Problem mit dem Pseudozufallszahlengenerator One-Time-Pad

7

Ich habe im Unterricht angefangen, Kryptographie zu lernen, und wir sind auf One-Time-Pads gestoßen, bei denen der Schlüssel (einheitlich vereinbart) so lang ist wie die Nachricht selbst. Dann wandeln Sie die Nachricht in Bits um, führen und erhalten den Chiffretext. Dies verschlüsselt die Nachricht und um die Nachricht zu entschlüsseln, würden Sie mit den Verschlüsselungs- und Schlüsselbits ausführen.XORXOR

Um ein effizienteres One-Time-Pad zu erstellen, verwenden Sie einen Pseudozufallszahlengenerator, bei dem der ursprüngliche Schlüssel Bit lang ist (und nicht so lang sein muss wie die Nachricht). Dann würden Sie den Schlüssel in den Generator stecken und eine Pseudozufallszahl erhalten. Aber würden Sender und Empfänger nicht unterschiedliche Schlüssel erhalten, da es pseudozufällig ist? Wie kann der Empfänger dann die Nachricht entschlüsseln, wenn er nicht denselben Schlüssel hat?n

Ski-Maske
quelle
Wenn Ihr Kernproblem PRNG ist, kann der Schlüssel als Startwert verwendet werden (nicht wirklich gut für OTP). Wenn beide Parteien denselben Startwert (für denselben Generator) verwenden, sind die generierten Sequenzen gleich.
Evil
Beide Parteien verwenden denselben Schlüssel. Mithilfe eines PRNG erweitern sie es auf eine viel längere, zufällig aussehende gemeinsame Zeichenfolge, die als einmaliges Pad dient.
Yuval Filmus
Wissen Sie, wie PRNGs funktionieren?
user253751
11
Nur als Hinweis für zukünftige Fragen gibt es eine ganze Stack-Austausch-Site, die auf Kryptographie spezialisiert ist .
Paŭlo Ebermann

Antworten:

17

Sie scheinen falsch verstanden zu haben, was der Schlüssel ist.

Im Kontext der symmetrischen Verschlüsselung ist der Schlüssel ein gemeinsames Geheimnis: etwas, das sowohl dem Absender als auch dem Empfänger bekannt ist. Bei OTP ist der Schlüssel das gesamte Pad. Wenn zwei Personen eine Nachricht mit OTP verschlüsseln möchten, müssen sie zuvor sicherstellen, dass sie über ein ausreichend langes Pad verfügen, um dies zu tun.

Für Ihr vorgeschlagenes "effizientes" OTP ist der Schlüssel das PRNG-Seed: Beide Parteien müssen im Voraus sicherstellen, dass sie es wissen. Dann initialisieren beide das PRNG mit demselben Startwert und es wird garantiert, dass für jeden von ihnen dieselbe Sequenz von "Zufallszahlen" erzeugt wird.

Beachten Sie jedoch, dass dies eine massive, massive Schwächung von OTP ist. Ein tatsächliches OTP bietet perfekte Sicherheit, solange das Pad geheim gehalten wird. Wenn Sie die 17-stellige Nachricht abfangen

nsmklmfmwnfmngner

Sie haben keine Ahnung, ob es ist

maketrumpthepotus

mit einem Pad codiert oder

ensureclintonwins

mit einem anderen Pad codiert. Oder

kittensarethebest

oder buchstäblich alles andere. Die Verwendung eines Pseudozufalls-Pads bedeutet jedoch, dass nur bestimmte Pads möglich sind (möglicherweise gibt es überhaupt keinen Schlüssel, der die Kätzchen-Nachricht in "nsmklmfmwnfmngner" verschlüsselt, sodass Sie dies ausschließen können). Jeder, der den PRNG-Algorithmus kennt, kann Schlüssel erraten, um zu versuchen, Nachrichten zu entschlüsseln. Jeder, der Pad-Material erfasst, kann versuchen, das PRNG zurückzuentwickeln. Jeder, der verschlüsselte Nachrichten erfasst, kann dies auch versuchen.

Sie sollten es wirklich nicht OTP nennen, es sei denn, das Schlüsselmaterial ist so lang wie die Nachricht. Ihr Vorschlag für die Verwendung eines PRNG ist nur eine generische Stream-Chiffre.

David Richerby
quelle
4
Ich denke , es ist erwähnenswert , dass OTP ist wirksam und praktikabel in dem Szenario , in dem Sie einen sicheren Kanal mit hohen Bandbreite der Kommunikation (zB persönlicher Kontakt), aber es ist nur vorübergehend-und magst später sicher mit niedriger Bandbreite Kommunikation senden. Beispiel: Geben Sie Ihrem Spion vor seinem Einsatz Ihren einmaligen Block. dann kann er damit sicher kurze Nachrichten senden, solange das Pad reicht.
Wildcard
@Wildcard sollte man es trotzdem mit einem MAC kombinieren, um sicherzustellen, dass die Nachricht während der Übertragung nicht geändert wird.
Paŭlo Ebermann
8
"Sie sollten es wirklich nicht OTP nennen, es sei denn, das Schlüsselmaterial ist so lang wie die Nachricht." und nie wiederverwendet . Daher einmalig . Die andere Sache (mit dem PRNG) ist übrigens. Ich habe gerade eine Stream-Chiffre genannt.
Jonas Schäfer
@ JonasWielicki "Die andere Sache (mit dem PRNG) ist übrigens nur eine Stream-Chiffre genannt." Ähm, das habe ich im Satz nach dem, den du zitiert hast, gesagt!
David Richerby
@ DavidRicherby Ha. Wie habe ich das vermisst?
Jonas Schäfer
11

Um ein effizienteres One-Time-Pad zu erstellen, verwenden Sie einen Pseudozufallszahlengenerator

Nein, nein und noch einmal nein. Ich mache mir Sorgen, dass Ihnen dies beigebracht wird. Das absolut grundlegende Konzept eines einmaligen Pads und der Begriff der mathematisch nachweisbaren perfekten Geheimhaltung ist, dass das Pad-Material wirklich zufällig ist. Und es darf niemals wiederverwendet werden , auch nicht einmal. Es kann von keinem Algorithmus generiert werden. Die Zufallszahlen müssen aus einem physikalischen Prozess wie Würfeln, elektrischem Rauschen oder Photoneninterferenz in einem geteilten Laserstrahl stammen. Wenn Sie sie mit einem Algorithmus / Code erstellen, ist dies nur eine Stream-Verschlüsselung wie RC4 oder ein AES-Konstrukt.

Durchsuchen Sie die Fragen mit dem einmaligen Pad auf crypto.se. Das wird dir alles erzählen. Noch wichtiger ist, dass Sie viele Versuche lesen werden , das One-Time-Pad zu verbessern oder effizienter zu gestalten . Alle von ihnen sind Schlangenöl, egal wie verlockend sie erscheinen mögen.

Paul Uszak
quelle
1
Reg. "Kann nicht durch irgendeine Form von Algorithmus erzeugt werden" - technisch gesehen wird der eigentliche Schlüssel , selbst wenn Sie einen physikalischen Prozess als Entropiequelle verwenden, im Allgemeinen immer noch von einem Algorithmus erzeugt: einem, der aus den Rohmessungen eine gleichmäßige Verteilung macht , sonst ist es auch nicht perfekt sicher. Dieser Algorithmus muss nur mit mehr zufälligen Bits beginnen, als der Schlüssel haben wird.
links um den
@leftaroundabout Natürlich hast du recht. Ich wollte das ohnehin trübe Wasser nicht mit Diskussionen über Zufälligkeitsextraktoren trüben.
Paul Uszak
7

Ein Pseudozufallsgenerator ist ein deterministischer Algorithmus, der bei einem kurzen zufälligen Startwert eine Pseudozufallszeichenfolge zurückgibt, die bestimmte Gegner täuscht (dh solche Gegner können die Ausgabe des Generators nicht von einer wirklich zufälligen Zeichenfolge unterscheiden). Beachten Sie, dass das Erlauben des Generators, Münzen zu werfen, das Ganze uninteressant macht, da Sie einfach eine wirklich zufällige Ausgabe zurückgeben könnten.

In diesem Fall kann der Schlüssel der Keim sein sund der Empfänger kann berechnen G(s) um die Nachricht zu entschlüsseln (seit G ist deterministisch, liefert diese Berechnung für beide Parteien das gleiche Ergebnis).

Ariel
quelle
1
Beachten Sie, dass viele "Zufallszahlengeneratoren" in Computern eine Mischung aus realer Zufälligkeit und Pseudozufälligkeit verwenden und daher weder für dieses "Kurzschlüssel" -Pseudo-Einmal-Pad noch für die Erstellung eines bewährten sicheren echten Einmal-Pads funktionieren.
Paŭlo Ebermann