Warum hängt die meiste Kryptographie im Gegensatz zu anderen Problemen von großen Primzahlpaaren ab?

9

Die meisten aktuellen Kryptografiemethoden hängen von der Schwierigkeit ab, Zahlen zu faktorisieren, die das Produkt zweier großer Primzahlen sind. Soweit ich weiß, ist dies nur schwierig, solange die Methode zur Erzeugung der großen Primzahlen nicht als Abkürzung zum Faktorisieren der resultierenden zusammengesetzten Zahl verwendet werden kann (und das Faktorisieren großer Zahlen selbst schwierig ist).

Es sieht so aus, als ob Mathematiker von Zeit zu Zeit bessere Verknüpfungen finden und die Verschlüsselungssysteme daher regelmäßig aktualisiert werden müssen. (Es besteht auch die Möglichkeit, dass Quantencomputer die Faktorisierung letztendlich zu einem viel einfacheren Problem machen, aber das wird niemanden überraschen, wenn die Technologie mit der Theorie Schritt hält.)

Einige andere Probleme haben sich als schwierig erwiesen. Zwei Beispiele, die mir in den Sinn kommen, sind Variationen des Rucksackproblems und des Problems der reisenden Verkäufer.

Ich weiß, dass Merkle-Hellman gebrochen wurde, dass Nasako-Murakami sicher bleibt und dass Rucksackprobleme möglicherweise gegen Quantencomputer resistent sind. (Danke, Wikipedia.) Ich habe nichts darüber gefunden, das Problem des Handlungsreisenden für die Kryptographie zu verwenden.

Warum scheinen Paare großer Primzahlen die Kryptographie zu beherrschen?

  • Liegt es einfach daran, dass es derzeit einfach ist, Paare großer Primzahlen zu generieren, die leicht zu multiplizieren, aber schwer zu faktorisieren sind?
  • Liegt es daran, dass es nachweislich schwierig ist, Paare großer Primzahlen in einem vorhersehbaren Ausmaß zu faktorisieren, das gut genug ist?
  • Sind Paare großer Primzahlen auf andere Weise als auf Schwierigkeiten nützlich, beispielsweise als Eigenschaft, sowohl für die Verschlüsselung als auch für die kryptografische Signatur zu arbeiten?
  • Ist das Problem, Problemmengen für jeden der anderen Problemtypen zu generieren, die für den kryptografischen Zweck selbst schwierig genug sind, zu schwierig, um praktisch zu sein?
  • Sind die Eigenschaften anderer Problemtypen nicht ausreichend untersucht, um vertrauenswürdig zu sein?
  • Andere.
Steve
quelle
8
Erstens bin ich mir ziemlich sicher, dass die Kryptographie mit elliptischen Kurven in der Praxis verwendet wird, obwohl ich mich nicht erinnern kann, in welcher Situation. Sie haben jedoch Recht, dass RSA viel häufiger als andere Kryptosysteme verwendet wird. Ich denke, der Grund liegt hauptsächlich darin, dass die RSA-Verschlüsselung seit Jahren eine Art Standard ist, mit einer Menge (natürlich fehlerhaft!) Software, die sie implementiert, und mit Leuten, die daran gewöhnt sind. Andere Verschlüsselungssysteme (zum Beispiel basierend auf elliptischen Kurven oder Gittern) sind manchmal verwendbar, aber es braucht Leute, um sie zu erwerben, und das braucht Zeit! Änderung der Gewohnheiten ...
Bruno
3
@Bruno Bitcoin verwendet beispielsweise elliptische Kurven, um Transaktionen zu signieren.
Martin Berger

Antworten:

9

Boaz Barak hat dies in einem Blogbeitrag angesprochen

Meine Erkenntnis aus seinem Beitrag (grob gesagt) ist, dass wir nur wissen, wie man kryptografische Grundelemente unter Verwendung von Rechenproblemen mit einer gewissen Struktur entwirft, die wir ausnutzen. Ohne Struktur wissen wir nicht, was wir tun sollen. Bei zu viel Struktur wird das Problem effizient berechenbar (daher für kryptografische Zwecke unbrauchbar). Es scheint, dass die Menge an Struktur genau richtig sein muss.

Tyson Williams
quelle
Als ich diesen Artikel las, dachte ich an einen anderen möglichen Grund, warum das Faktorisieren von Paaren großer Primzahlen die Methode der Wahl für die Kryptographie mit öffentlichen Schlüsseln bleibt: Es ist wirklich schwierig, einen Ersatz zu finden. Die Anzahl der Mathematiker, die eine bestimmte Alternative verstehen, ist gering, was (1) die Anzahl der Personen begrenzt, die Alternativen vorschlagen können, und (2) die Anzahl der Personen, die Vorschläge glaubwürdig analysieren können, um festzustellen, ob sie praktikabel sind. Primzahlen funktionieren möglicherweise nicht für immer, aber sie funktionieren vorerst, sodass sie durch Trägheit weiterhin verwendet werden.
Steve
6

Alles, was ich sagen werde, ist bekannt (alle Links sind zu Wikipedia), aber hier ist es:

  1. Der in RSA verwendete Ansatz unter Verwendung von Primzahlenpaaren kann auch in einem allgemeineren Rahmen von zyklischen Gruppen angewendet werden, insbesondere im Diffie-Helmann- Protokoll, das verallgemeinert zu einer beliebigen Gruppe, insbesondere zu elliptischen Kurven, die weniger anfällig für Angriffe auf Ganzzahlen sind. Es wurden andere Gruppenstrukturen in Betracht gezogen, die möglicherweise nicht kommutativ sind, aber keine sind weit verbreitet. AFAIK.(Z./.pqZ.)×

  2. Es gibt andere Ansätze für die Kryptographie, insbesondere die gitterbasierte Kryptographie , die sich auf bestimmte schwierige Probleme bei Gittern stützen (z. B. das Finden von Punkten mit kleiner Norm auf dem Gitter), um die Kryptographie mit öffentlichem Schlüssel zu implementieren. Interessanterweise sind einige dieser Systeme nachweislich hart , dh können nur dann gebrochen werden, wenn das entsprechende harte Problem in der Gittertheorie gelöst werden kann. Dies steht im Gegensatz zu beispielsweise RSA, die nicht die gleiche Garantie bietet . Beachten Sie, dass der gitterbasierte Ansatz vermutlich nicht NP-hart ist (aber vorerst schwieriger zu sein scheint als das Integer-Factoring).

  3. Das Teilen von Schlüsseln ist ein besonderes Anliegen, nämlich das geheime Aufdecken , das sehr interessante Eigenschaften der Komplexitätstheorie aufweist. Ich kenne die Details nicht, aber die Theorie der Zero-Knowledge-Protokolle ermöglicht es Alice, Bob ihr Wissen über ein Geheimnis zu offenbaren, das schwer zu berechnen ist (Graph Hamiltonian), ohne das Geheimnis selbst zu enthüllen (in diesem Fall den Pfad).

Schließlich möchten Sie vielleicht auf der Seite zur Post-Quanten-Kryptographie nach alternativen Ansätzen für Kryptosysteme mit öffentlichem Schlüssel suchen, die auf schwierigen Problemen beruhen.

Cody
quelle