[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/23\/fallturfunktion-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/23\/fallturfunktion-wikipedia\/","headline":"Fallt\u00fcrfunktion – Wikipedia","name":"Fallt\u00fcrfunktion – Wikipedia","description":"before-content-x4 Dieser Artikel befasst sich mit der mathematischen Kryptographiefunktion. Informationen zur Umgehung der Sicherheit finden Sie unter Backdoor (Computing). Die","datePublished":"2020-11-23","dateModified":"2020-11-23","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki15\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki15\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/8\/8f\/Trapdoor_permutation.svg\/300px-Trapdoor_permutation.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/8\/8f\/Trapdoor_permutation.svg\/300px-Trapdoor_permutation.svg.png","height":"212","width":"300"},"url":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/23\/fallturfunktion-wikipedia\/","wordCount":2977,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Dieser Artikel befasst sich mit der mathematischen Kryptographiefunktion.  Informationen zur Umgehung der Sicherheit finden Sie unter Backdoor (Computing).  Die Idee der Fallt\u00fcrfunktion.  Eine Fallt\u00fcrfunktion f mit seiner Fallt\u00fcr 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\u00fcr t gegeben ist.[1]EIN Fallt\u00fcrfunktion ist eine Funktion, die leicht in eine Richtung zu berechnen ist, jedoch ohne spezielle Informationen, die als “Fallt\u00fcr” bezeichnet wird, nur schwer in die entgegengesetzte Richtung zu berechnen ist (ihre Umkehrung zu finden).  Fallt\u00fcrfunktionen sind in der Kryptographie weit verbreitet.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4In mathematischen Begriffen, wenn f Ist eine Fallt\u00fcrfunktion, dann gibt es einige geheime Informationen t, so dass gegeben f((x) und tist es einfach zu berechnen x.  Betrachten Sie ein Vorh\u00e4ngeschloss und seinen Schl\u00fcssel.  Es ist trivial, das Vorh\u00e4ngeschloss ohne Verwendung des Schl\u00fcssels von offen auf geschlossen zu \u00e4ndern, indem der Sch\u00e4kel in den Verriegelungsmechanismus gedr\u00fcckt wird.  Zum einfachen \u00d6ffnen des Vorh\u00e4ngeschlosses muss jedoch der Schl\u00fcssel verwendet werden.  Hier ist der Schl\u00fcssel die Fallt\u00fcr und das Vorh\u00e4ngeschloss die Fallt\u00fcrfunktion.Ein Beispiel f\u00fcr eine einfache mathematische Fallt\u00fcr ist “6895601 ist das Produkt zweier Primzahlen. Was sind diese Zahlen?”  Eine typische L\u00f6sung w\u00e4re, 6895601 durch mehrere Primzahlen zu teilen, bis die Antwort gefunden ist.  Wenn man jedoch erf\u00e4hrt, dass 1931 eine der Zahlen ist, kann man die Antwort finden, indem man “6895601 \u00f7 1931” in einen beliebigen Taschenrechner eingibt.  Dieses Beispiel ist keine robuste Fallt\u00fcrfunktion – moderne Computer k\u00f6nnen alle m\u00f6glichen Antworten innerhalb einer Sekunde erraten -, aber dieses Beispielproblem k\u00f6nnte durch die Verwendung des Produkts zweier viel gr\u00f6\u00dferer Primzahlen verbessert werden.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Trapdoor-Funktionen wurden Mitte der 1970er Jahre durch die Ver\u00f6ffentlichung asymmetrischer (oder Public-Key-) Verschl\u00fcsselungstechniken von Diffie, Hellman und Merkle in der Kryptographie bekannt.  In der Tat haben Diffie & Hellman (1976) den Begriff gepr\u00e4gt.  Es wurden mehrere Funktionsklassen vorgeschlagen, und es wurde schnell klar, dass Fallt\u00fcrfunktionen schwerer zu finden sind als urspr\u00fcnglich angenommen.  Ein fr\u00fcher Vorschlag war beispielsweise, Schemata zu verwenden, die auf dem Teilmengen-Summenproblem basieren.  Dies stellte sich – ziemlich schnell – als ungeeignet heraus.Stand 2004[update]Die bekanntesten Kandidaten f\u00fcr Fallt\u00fcrfunktionen (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\u00e4rte des diskreten Logarithmusproblems beziehen (entweder modulo a prime oder in einer Gruppe, die \u00fcber eine elliptische Kurve definiert ist) sind nicht Es ist bekannt, dass es sich um Fallt\u00fcrfunktionen handelt, da keine “Fallt\u00fcr” -Informationen \u00fcber die Gruppe bekannt sind, die die effiziente Berechnung diskreter Logarithmen erm\u00f6glichen.Eine Fallt\u00fcr in der Kryptographie hat die oben erw\u00e4hnte Bedeutung und ist nicht mit einer Hintert\u00fcr zu verwechseln (diese werden h\u00e4ufig synonym verwendet, was falsch ist).  Eine Hintert\u00fcr ist ein absichtlicher Mechanismus, der einem kryptografischen Algorithmus (z. B. einem Algorithmus zur Erzeugung von Schl\u00fcsselpaaren, einem Algorithmus f\u00fcr die digitale Signatur usw.) oder einem Betriebssystem hinzugef\u00fcgt wird, der es einer oder mehreren nicht autorisierten Parteien erm\u00f6glicht, die Sicherheit von zu umgehen oder zu untergraben das System in gewisser Weise.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsDefinition[edit]Beispiele[edit]RSA-Annahme[edit]Rabins quadratische R\u00fcckstandsannahme[edit]Siehe auch[edit]Verweise[edit]Definition[edit]EIN Fallt\u00fcrfunktion ist eine Sammlung von Einwegfunktionen { fk :: D.k  \u2192 R.k  } (()k \u2208 K.), in dem alle von K., D.k, R.k  sind Teilmengen von Bin\u00e4rzeichenfolgen {0, 1}* *, die folgenden Bedingungen erf\u00fcllen:Es gibt eine probabilistische Polynomzeit (PPT) Probenahme Algorithmus Gen st Gen (1n) = (k, tk) mit k \u2208 K. \u2229 {0, 1}n  und tk  \u2208 {0, 1}* * erf\u00fcllt | tk  | p ((n), in welchem p ist ein Polynom.  Jeder tk  hei\u00dft das Fallt\u00fcr korrespondierend zu k.  Jede Fallt\u00fcr kann effizient abgetastet werden.Gegebene Eingabe kEs gibt auch einen PPT-Algorithmus, der ausgibt x \u2208 D.k.  Das hei\u00dft, jeder D.k  kann effizient abgetastet werden.F\u00fcr jeden k \u2208 K.gibt es einen PPT-Algorithmus, der korrekt berechnet fk.F\u00fcr jeden k \u2208 K.gibt es einen PPT-Algorithmus EIN st f\u00fcr jeden x \u2208 D.k, Lassen y = EIN (( k, fk((x), tk  ) und dann haben wir fk((y) = fk((x).  Das hei\u00dft, bei Fallt\u00fcr ist es leicht umzukehren.F\u00fcr jeden k \u2208 K.ohne Fallt\u00fcr tkf\u00fcr 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\u00e4ssigbar.[2][3][4]Wenn jede Funktion in der obigen Sammlung eine Einwegpermutation ist, wird die Sammlung auch als a bezeichnet Fallt\u00fcrpermutation.[5]Beispiele[edit]In den folgenden beiden Beispielen nehmen wir immer an, dass es schwierig ist, eine gro\u00dfe zusammengesetzte Zahl zu faktorisieren (siehe Integer-Faktorisierung).RSA-Annahme[edit]In diesem Beispiel mit der Umkehrung von e Modulo \u03c6 (n), die Totientenfunktion des Eulers von nist die Fallt\u00fcr:f((x)=xemodn{ displaystyle f (x) = x ^ {e}  mod n}Wenn die Faktorisierung bekannt ist, ist \u03c6 (n) kann berechnet werden, also dann die Umkehrung d  von e  berechnet werden kann d  = e\u22121 mod \u03c6 (n) und dann gegeben y = f((x) wir k\u00f6nnen finden x = yd  mod n = xed  mod n = x mod n.  Seine H\u00e4rte ergibt sich aus der RSA-Annahme.[6]Rabins quadratische R\u00fcckstandsannahme[edit]Lassen n eine gro\u00dfe zusammengesetzte Zahl sein, so dass n = pq, wo p und q sind gro\u00dfe Primzahlen wie die p \u2261 3 mod 4, q \u2261 3 mod 4 und gegen\u00fcber dem Gegner vertraulich behandelt.  Das Problem ist zu berechnen z gegeben ein so dass ein \u2261 z2 mod n.  Die Fallt\u00fcr ist die Faktorisierung von n.  Mit der Fallt\u00fcr werden die L\u00f6sungen von z kann angegeben werden als cx + dy, cx – – dy, – cx + dy, – cx – – dy, wo ein \u2261 x2 mod p, ein \u2261 y2 mod q, c \u2261 1 mod p, c \u2261 0 mod q, d \u2261 0 mod p, d \u2261 1 mod q.  Weitere Einzelheiten finden Sie im chinesischen Restsatz.  Beachten Sie die angegebenen Primzahlen p und q, wir k\u00f6nnen finden x \u2261 ein((p+1) \/ 4 mod p und y \u2261 ein((q+1) \/ 4 mod q.  Hier die Bedingungen p \u2261 3 mod 4 und q \u2261 3 mod 4 garantieren, dass die L\u00f6sungen x und y kann gut definiert werden.[7]Siehe auch[edit]^ Ostrovsky, S. 6-9^ Pass’s Notes, def.  56.1^ Goldwassers Vorlesungsunterlagen, def.  2.16^ Ostrovsky, S. 6-10, def.  11^ Pass’s Notizen, def 56.1;  Dodis ‘Def 7, Vorlesung 1.^ Goldwassers Vorlesungsunterlagen, 2.3.2;  Lindells Notizen, S. 17, Bsp.  1.^ Goldwassers Vorlesungsunterlagen, 2.3.4Verweise[edit]Diffie, W.;  Hellman, M. (1976), “Neue Wege in der Kryptographie” (PDF), IEEE-Transaktionen zur Informationstheorie, 22 (6): 644\u2013654, CiteSeerX 10.1.1.37.9720, doi:10.1109 \/ TIT.1976.1055638Pass, Rafael, Ein Kurs in Kryptographie (PDF)abgerufen 27. November 2015Goldwasser, Shafi, Vorlesungsunterlagen zur Kryptographie (PDF)abgerufen 25. November 2015Ostrovsky, Rafail, Grundlagen der Kryptographie (PDF)abgerufen 27. November 2015Dodis, Jewgenij, Einf\u00fchrung in die Kryptographie Lecture Notes (Herbst 2008)abgerufen 17. Dezember 2015Lindell, Yehuda, Grundlagen der Kryptographie (PDF)abgerufen 17. Dezember 2015     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/23\/fallturfunktion-wikipedia\/#breadcrumbitem","name":"Fallt\u00fcrfunktion – Wikipedia"}}]}]