Falltürfunktion – Wikipedia

Posted on by
before-content-x4

Dieser Artikel befasst sich mit der mathematischen Kryptographiefunktion. Informationen zur Umgehung der Sicherheit finden Sie unter Backdoor (Computing).

Die Idee der Falltürfunktion. Eine Falltürfunktion f mit seiner Falltür t kann durch einen Algorithmus erzeugt werden Gen.. f kann effizient berechnet werden, dh in probabilistischer Polynomzeit. Die Berechnung der Inversen von f ist in der Regel schwer, es sei denn, die Falltür t gegeben ist.[1]

EIN Falltürfunktion ist eine Funktion, die leicht in eine Richtung zu berechnen ist, jedoch ohne spezielle Informationen, die als “Falltür” bezeichnet wird, nur schwer in die entgegengesetzte Richtung zu berechnen ist (ihre Umkehrung zu finden). Falltürfunktionen sind in der Kryptographie weit verbreitet.

after-content-x4

In mathematischen Begriffen, wenn f Ist eine Falltürfunktion, dann gibt es einige geheime Informationen t, so dass gegeben f((x) und tist es einfach zu berechnen x. Betrachten Sie ein Vorhängeschloss und seinen Schlüssel. Es ist trivial, das Vorhängeschloss ohne Verwendung des Schlüssels von offen auf geschlossen zu ändern, indem der Schäkel in den Verriegelungsmechanismus gedrückt wird. Zum einfachen Öffnen des Vorhängeschlosses muss jedoch der Schlüssel verwendet werden. Hier ist der Schlüssel die Falltür und das Vorhängeschloss die Falltürfunktion.

Ein Beispiel für eine einfache mathematische Falltür ist “6895601 ist das Produkt zweier Primzahlen. Was sind diese Zahlen?” Eine typische Lösung wäre, 6895601 durch mehrere Primzahlen zu teilen, bis die Antwort gefunden ist. Wenn man jedoch erfährt, dass 1931 eine der Zahlen ist, kann man die Antwort finden, indem man “6895601 ÷ 1931” in einen beliebigen Taschenrechner eingibt. Dieses Beispiel ist keine robuste Falltürfunktion – moderne Computer können alle möglichen Antworten innerhalb einer Sekunde erraten -, aber dieses Beispielproblem könnte durch die Verwendung des Produkts zweier viel größerer Primzahlen verbessert werden.

Trapdoor-Funktionen wurden Mitte der 1970er Jahre durch die Veröffentlichung asymmetrischer (oder Public-Key-) Verschlüsselungstechniken von Diffie, Hellman und Merkle in der Kryptographie bekannt. In der Tat haben Diffie & Hellman (1976) den Begriff geprägt. Es wurden mehrere Funktionsklassen vorgeschlagen, und es wurde schnell klar, dass Falltürfunktionen schwerer zu finden sind als ursprünglich angenommen. Ein früher Vorschlag war beispielsweise, Schemata zu verwenden, die auf dem Teilmengen-Summenproblem basieren. Dies stellte sich – ziemlich schnell – als ungeeignet heraus.

Stand 2004Die bekanntesten Kandidaten für Falltürfunktionen (Familien) sind die Funktionsfamilien RSA und Rabin. Beide sind als Exponentiation modulo einer zusammengesetzten Zahl geschrieben, und beide beziehen sich auf das Problem der Primfaktorisierung.

Funktionen, die sich auf die Härte des diskreten Logarithmusproblems beziehen (entweder modulo a prime oder in einer Gruppe, die über eine elliptische Kurve definiert ist) sind nicht Es ist bekannt, dass es sich um Falltürfunktionen handelt, da keine “Falltür” -Informationen über die Gruppe bekannt sind, die die effiziente Berechnung diskreter Logarithmen ermöglichen.

Eine Falltür in der Kryptographie hat die oben erwähnte Bedeutung und ist nicht mit einer Hintertür zu verwechseln (diese werden häufig synonym verwendet, was falsch ist). Eine Hintertür ist ein absichtlicher Mechanismus, der einem kryptografischen Algorithmus (z. B. einem Algorithmus zur Erzeugung von Schlüsselpaaren, einem Algorithmus für die digitale Signatur usw.) oder einem Betriebssystem hinzugefügt wird, der es einer oder mehreren nicht autorisierten Parteien ermöglicht, die Sicherheit von zu umgehen oder zu untergraben das System in gewisser Weise.

after-content-x4

Definition[edit]

EIN Falltürfunktion ist eine Sammlung von Einwegfunktionen { fk :: D.k → R.k } (()k ∈ K.), in dem alle von K., D.k, R.k sind Teilmengen von Binärzeichenfolgen {0, 1}* *, die folgenden Bedingungen erfüllen:

  • Es gibt eine probabilistische Polynomzeit (PPT) Probenahme Algorithmus Gen st Gen (1n) = (k, tk) mit k ∈ K. ∩ {0, 1}n und tk ∈ {0, 1}* * erfüllt | tk | p ((n), in welchem p ist ein Polynom. Jeder tk heißt das Falltür korrespondierend zu k. Jede Falltür kann effizient abgetastet werden.
  • Gegebene Eingabe kEs gibt auch einen PPT-Algorithmus, der ausgibt x ∈ D.k. Das heißt, jeder D.k kann effizient abgetastet werden.
  • Für jeden k ∈ K.gibt es einen PPT-Algorithmus, der korrekt berechnet fk.
  • Für jeden k ∈ K.gibt es einen PPT-Algorithmus EIN st für jeden x ∈ D.k, Lassen y = EIN (( k, fk((x), tk ) und dann haben wir fk((y) = fk((x). Das heißt, bei Falltür ist es leicht umzukehren.
  • Für jeden k ∈ K.ohne Falltür tkfür jeden PPT-Algorithmus die Wahrscheinlichkeit einer korrekten Invertierung fk (dh gegeben fk((x), finde ein Vorbild x ‘ so dass fk((x ‘ ) = fk((x)) Ist vernachlässigbar.[2][3][4]

Wenn jede Funktion in der obigen Sammlung eine Einwegpermutation ist, wird die Sammlung auch als a bezeichnet Falltürpermutation.[5]

Beispiele[edit]

In den folgenden beiden Beispielen nehmen wir immer an, dass es schwierig ist, eine große zusammengesetzte Zahl zu faktorisieren (siehe Integer-Faktorisierung).

RSA-Annahme[edit]

In diesem Beispiel mit der Umkehrung von e Modulo φ (n), die Totientenfunktion des Eulers von nist die Falltür:

Wenn die Faktorisierung bekannt ist, ist φ (n) kann berechnet werden, also dann die Umkehrung d von e berechnet werden kann d = e−1 mod φ (n) und dann gegeben y = f((x) wir können finden x = yd mod n = xed mod n = x mod n. Seine Härte ergibt sich aus der RSA-Annahme.[6]

Rabins quadratische Rückstandsannahme[edit]

Lassen n eine große zusammengesetzte Zahl sein, so dass n = pq, wo p und q sind große Primzahlen wie die p ≡ 3 mod 4, q ≡ 3 mod 4 und gegenüber dem Gegner vertraulich behandelt. Das Problem ist zu berechnen z gegeben ein so dass ein ≡ z2 mod n. Die Falltür ist die Faktorisierung von n. Mit der Falltür werden die Lösungen von z kann angegeben werden als cx + dy, cx – – dy, – cx + dy, – cx – – dy, wo ein ≡ x2 mod p, ein ≡ y2 mod q, c ≡ 1 mod p, c ≡ 0 mod q, d ≡ 0 mod p, d ≡ 1 mod q. Weitere Einzelheiten finden Sie im chinesischen Restsatz. Beachten Sie die angegebenen Primzahlen p und q, wir können finden x ≡ ein((p+1) / 4 mod p und y ≡ ein((q+1) / 4 mod q. Hier die Bedingungen p ≡ 3 mod 4 und q ≡ 3 mod 4 garantieren, dass die Lösungen x und y kann gut definiert werden.[7]

Siehe auch[edit]

  1. ^ Ostrovsky, S. 6-9
  2. ^ Pass’s Notes, def. 56.1
  3. ^ Goldwassers Vorlesungsunterlagen, def. 2.16
  4. ^ Ostrovsky, S. 6-10, def. 11
  5. ^ Pass’s Notizen, def 56.1; Dodis ‘Def 7, Vorlesung 1.
  6. ^ Goldwassers Vorlesungsunterlagen, 2.3.2; Lindells Notizen, S. 17, Bsp. 1.
  7. ^ Goldwassers Vorlesungsunterlagen, 2.3.4

Verweise[edit]


after-content-x4