Wenn P = NP, gibt es Kryptosysteme, die n ^ 2 Zeit benötigen, um zu brechen?

Wenn P gleich NP ist, ist es dann weiterhin möglich, ein Kryptosystem zu entwerfen, bei dem der optimale Kryptoanalysealgorithmus beispielsweise das Quadrat der von den legitimen Verschlüsselungs- und Entschlüsselungsalgorithmen beanspruchten Zeit benötigt? Gibt es solche Algorithmen schon?

Ja - tatsächlich hat der allererste Algorithmus mit öffentlichem Schlüssel, der außerhalb eines Geheimdienstes erfunden wurde, so funktioniert! Die erste Veröffentlichung, in der Kryptografie mit öffentlichen Schlüsseln vorgeschlagen wurde, war "Sichere Kommunikation über unsichere Kanäle" von Ralph Merkle , in der er die Verwendung von "Rätseln" vorschlug . Dies ist ein Schlüsselvereinbarungsprotokoll.

1. Alice sendet verschlüsselte Nachrichten (sogenannte Rätsel), die jeweils eine eindeutige Kennung I i und einen Sitzungsschlüssel K i enthalten , wobei die Schlüssel für jede Nachricht aus einem Satz von n Schlüsseln ausgewählt werden. Dies benötigt O ( n ) Zeit ( O ( 1 ) pro Nachricht).$n$$I_i$$K_i$$n$$O(n)$$O(1)$
2. Bob entschlüsselt eine der Botschaften , mit brutaler Gewalt und sendet mit verschlüsselten K i . Dies dauert O ( n ) Mal ( O ( 1 ) pro Schlüssel, mal n mögliche Schlüssel).$I_i$$K_i$$O(n)$$O(1)$$n$
3. Alice versucht alle Schlüssel, um die Nachricht zu entschlüsseln. Dies dauert wiederum Mal.$O(n)$

Jede Partei benötigt nur -Berechnung, aber ein Lauscher, der K i finden möchte, muss durchschnittlich die Hälfte der Rätsel ausprobieren, um den richtigen Schlüssel zu berechnen (der Lauscher weiß nicht, welche Nachricht Bob zum Entschlüsseln ausgewählt hat), also der Lauscher erfordert Θ ( n 2 ) Berechnung im Durchschnitt.$O(n)$$K_i$$\Theta(n^2)$

Nachdem Merkle seine Rätsel erfunden hatte, veröffentlichten Diffie und Hellman ein Schlüsselvereinbarungsprotokoll, das auf dem diskreten Logarithmusproblem basierte . Dieses Protokoll wird noch heute verwendet.

Das Problem mit Merkle-Rätseln oder allem, bei dem der Arbeitsaufwand für den Angreifer nur mit dem Platz der legitimen Partei zunimmt, besteht darin, dass große Schlüsselgrößen und Berechnungsmengen erforderlich sind, um eine angemessene Sicherheitsmarge zu erzielen.

In jedem Fall ist es nicht klar, dass der bloße Nachweis von P = NP bestehende kryptographische Algorithmen ungültig macht. Wenn die Polynomzunahme hoch genug ist, ist dies in der Praxis möglicherweise nicht so wichtig. Siehe Wie muss die Sicherheit geändert werden, wenn P = NP? , Können wir sagen, dass es bei P = NPP = NP keine sichere CPA-Verschlüsselung mit öffentlichem Schlüssel gibt? , P = NP und aktuelle kryptografische Systeme ,…

https://en.m.wikipedia.org/wiki/One-time_pad

Ein One Time Pad ist unabhängig von der Komplexität sicher, solange Ihre Zahlen wirklich zufällig sind.

Selbst wenn Sie jeden Schlüssel schnell ausprobieren können, ist dies nutzlos, da hierdurch jede mögliche Nachricht angezeigt wird und Sie nicht wissen können, welcher der gewünschte war.

Für das, was Sie beschreiben, würde die Analyse, wenn sie nur das Quadrat der Verschlüsselungszeit benötigt, nach modernen Maßstäben als unsicher eingestuft. Die Verschlüsselung muss in Sekunden oder noch weniger erfolgen, sodass bei einem quadratischen Anstieg die Nachrichten innerhalb weniger Stunden dekodiert werden können.