Frage:
Warum können Sie nicht mit dem öffentlichen Schlüssel rückwärts arbeiten, um eine Nachricht zu entschlüsseln?
Max
2015-04-22 18:51:02 UTC
view on stackexchange narkive permalink

Wie der Titel schon sagt, bin ich gespannt, warum Sie mit einer Nachricht, einem öffentlichen Schlüssel und einer verschlüsselten Nachricht nicht rückwärts arbeiten können, um herauszufinden, wie die Nachricht entschlüsselt werden kann!

Ich verstehe nicht Wie kann eine Nachricht mit einem Schlüssel verschlüsselt werden und wie können Sie dann nicht rückwärts arbeiten, um die Verschlüsselung rückgängig zu machen?

Ein schönes Video zur RSA-Verschlüsselung: https://www.youtube.com/watch?v=M7kEpw1tn50 Es hat mir geholfen zu verstehen, warum es so verdammt schwer zu knacken ist :)
Ich mag dieses Video, das das Mischen von Farben verwendet: https://www.youtube.com/watch?&v=3QnD2c4Xovk#!
Der springende Punkt bei der asymmetrischen Schlüsselverschlüsselung ist, dass der Schlüssel, den Sie zum Verschlüsseln verwenden, * nicht * zum Entschlüsseln verwendet werden kann - Sie benötigen sein Gegenstück.
@BadSkillz - Danke ... jetzt werde ich den Rest meines Tages verlieren, wenn ich mir ihre anderen Videos ansehe. : P.
Warum können Sie nicht einfach mit einem MD5-Hash rückwärts arbeiten, um die ursprüngliche Eingabe zu finden? (oder zumindest * eine * Eingabe, die Ihnen den gleichen Hash gibt)
Eigentlich kannst du! Das Problem ist vorwärts und rückwärts zu gehen, ist nicht etwas, was Sie mit der gleichen Effizienz tun können. Wir verlassen uns darauf, dass wir rückwärts arbeiten, um Zeit dafür zu haben.
@BadSkillz Ziemlich gutes Video, aber es hat ein paar Mängel. Dies deutet darauf hin, dass RSA im EZB-Modus verwendet wird. Dies ist aus mehreren Gründen eine schlechte Idee. Darüber hinaus ist die Verwendung eines geraden Moduls leicht irreführend.
Hier sind einige weitere Antworten, die für manche Menschen möglicherweise nützlicher sind. Ich denke, die ursprüngliche Absicht der Frage war: "Wenn X-Schritte mit Y-Eingaben bekannt sind, warum können sie dann nicht umgekehrt ausgeführt werden, wenn man diese bereits kennt, um die ursprüngliche Antwort zu erhalten?" bezog sich auf die tatsächliche spezifische Mechanik der Bedienung der Algorithmen und nicht so sehr auf die selbstverständlichere Verschleierung / Entropie des Menschen unter Verwendung des mathematischen Teils. Der Link: https://crypto.stackexchange.com/questions/18658/why-cant-you-decrypt-an-encrypted-message-with-just-the-public-key
Es ist für einen Hacker tatsächlich möglich, die Nachricht nur mit dem öffentlichen Schlüssel zu entschlüsseln.Aber das ist heute für jeden Computer extrem schwierig.Da das Zurücksetzen dieser verschlüsselten Nachricht mit diesem öffentlichen Schlüssel eine sehr schwierige mathematische Operation ist, insbesondere wenn dieser Schlüssel eine 2048-Bit-Zahl hat.Die Stärke der mathematischen Operation hängt von der Härte der Primfaktorisierung einer großen Zahl ab. Hier ist ein großartiges Video, das dieses https://www.youtube.com/watch?v=wXB-V_Keiu8 erklärt
Sieben antworten:
Lucas
2015-04-22 20:32:30 UTC
view on stackexchange narkive permalink

In der Informatik gibt es Einwegfunktionen (nicht mathematisch bewiesen, aber Sie werden reich und berühmt sein, wenn Sie etwas anderes beweisen). Diese Funktionen sind leicht in eine Richtung zu lösen, aber schwer umzukehren, z. Es ist einfach für Sie, 569 * 757 * 911 = 392397763 in ein oder zwei Minuten auf einem Blatt Papier zu berechnen. Wenn ich Ihnen andererseits 392397763 geben und Sie bitten würde, die Hauptfaktoren zu finden, würden Sie es sehr schwer haben. Wenn diese Zahlen wirklich groß sind, kann selbst der schnellste Computer der Welt die Faktorisierung nicht in angemessener Zeit rückgängig machen.

In der Kryptografie mit öffentlichen Schlüsseln werden diese Einwegfunktionen auf clevere Weise verwendet, um es jemandem zu ermöglichen, den öffentlichen Schlüssel zum Verschlüsseln von etwas zu verwenden, was es jedoch sehr schwierig macht, die resultierende Nachricht zu entschlüsseln. Sie sollten den Wiki-Artikel RSA-Kryptosystem lesen.

Mutige Ansprüche. Ist die Existenz von Einwegfunktionen mathematisch bewiesen (vor einigen Jahren noch nicht)? Gibt es einen Beweis dafür, dass die in Kryptosystemen mit öffentlichem Schlüssel verwendeten Funktionen wirklich einseitig sind?
@jknappen Der Nachweis ihrer Existenz oder ihres Fehlens würde die Lösung von P = NP bedeuten. Wir müssen uns jedoch nicht darauf verlassen, dass sie sich mathematisch als einseitig für die Computersicherheit erwiesen haben: Bisher ist es niemandem gelungen, einen schnellen Weg zu finden, um große Primzahlen zu faktorisieren.
@AronFoster: Wir wissen nicht, ob jemand hat.
@jknappen:Fair genug (ich habe einen Hinweis in Klammern hinzugefügt). Es hat sich als äußerst schwierig erwiesen, die Existenz von Einwegfunktionen mathematisch zu beweisen, aber Kryptosysteme funktionieren unter der Annahme, dass sie existieren, und ich denke, die überwiegende Mehrheit der Mathematiker und Informatiker geht auch davon aus, dass sie existieren.
@GuntramBlohm Und wir wissen nicht, ob jeder Intel-Chip eine Hintertür hat, durch die die NSA alles lesen kann, was Sie schreiben. Es gibt unendlich viele Risiken und es gibt einen Punkt, an dem etwas so unwahrscheinlich ist, dass es sich nicht lohnt, Ihre Aufmerksamkeit darauf zu richten.
Diese Bemerkungen liegen wirklich außerhalb des Rahmens der Frage, die offensichtlich eine Anfängerfrage ist. Wenn Sie als Anwalt darauf hinweisen, dass wir die Existenz von Einwegfunktionen technisch nicht bewiesen haben, wenn sie in der Praxis ständig als solche verwendet werden, wird dies den Fragesteller nur verwirren und keinen wirklichen Wert liefern. Das ist also nicht "fair genug" und imo hättest du es nicht bearbeiten sollen.
@AndreasBonini, Dies wäre ein Beispiel für [Lügen von Kindern] (https://en.wikipedia.org/wiki/Lie-to-children)
@GuntramBlohm Die Möglichkeit, das Produkt großer Primzahlen schnell zu faktorisieren, ist für einige Regierungen kein streng gehütetes Geheimnis. Es wäre eine große mathematische Leistung, wie sie vielleicht einmal in einer Generation vorkommt.
@AronFoster Wir nicht? Ich dachte, jeder wüsste es.
Sie benötigen nicht nur eine Einwegfunktion (wie eine Hash-Funktion), sondern normalerweise eine Einwegfunktion für die Falltür. (Außerdem brauchen Sie sie nicht nur, um zu existieren, sondern tatsächlich, dass die Funktion, die Sie verwenden, eine ist.)
@AndreasBonini Stack Exchange-Sites sind nicht nur für die Person gedacht, die die Frage stellt. Sie sind auch für andere, die mit der gleichen Frage kommen. Es ist nicht nötig, Details absichtlich wegzulassen: Erklären Sie es einfach in einfachen Worten (wie Lucas es getan hat).
@AronFoster: Das Faktorisieren großer Primzahlen ist einfach. Das Faktorisieren von Nicht-Primzahlen ohne kleine Primteiler ist schwierig.
@mason: es kommt darauf an, wie pedantisch die Details sind. Dies ist analog zu der Erwähnung der möglichen Störung durch kosmische Strahlung, wenn jemand fragt, wie eine Multiplikation in C ++ durchgeführt werden soll
@AronFoster Ich glaube nicht, dass das Factoring-Problem P = NP entspricht (oder zumindest nicht nachgewiesen wurde).
@AndreasBonini Nein, das ist überhaupt nicht ähnlich. Lucas erklärte klar und deutlich, wie Verschlüsselung funktioniert, und es ist äußerst wichtig, die Einschränkungen dieses Prozesses zu verstehen. Es braucht kein Genie, um zu verstehen, was Lucas geschrieben hat, was es zu einer guten Antwort macht. Ermutigen Sie die Leute nicht, wichtige Details zu Stack Exchange wegzulassen, da die Antworten für * alle * gelten und nicht nur für die erste Person, die sie fragt. Das ist ein Kernprinzip von SE-Standorten.
@tomasz "Faktor groß [Semiprimes] (http://mathworld.wolfram.com/Semiprime.html)" war wahrscheinlich gemeint.
abligh
2015-04-23 17:21:57 UTC
view on stackexchange narkive permalink

Ihre Frage ist ungefähr so ​​(mit Entschuldigung an Tom Stoppard): "Warum kann ich die Marmelade in meinen Milchreis einrühren, aber nicht wieder ausrühren?"

Einige mathematische Operationen sind sowohl rückwärts als auch vorwärts so einfach durchzuführen. Zum Beispiel können Sie einer Zahl genauso einfach 100 hinzufügen wie 100 subtrahieren. Einige sind jedoch schwieriger umzukehren. Zum Beispiel, wenn ich x nehme und g (x) = a (x ^ 5) + b (x ^ 4) + c (x ^ 3) + d (x ^ 2) finde ) + ex + f muss ich nur einfache Multiplikationen und Additionen machen. Es ist jedoch schwierig (auf algebraische Weise), von g (x) zu x zurückzukehren, da es keine allgemeine algebraische Lösung für eine quintische Gleichung a gibt >. Es ist nicht sofort klar, warum dies der Fall sein sollte (im Gegensatz zu einer quadratischen Gleichung), aber es ist so. Wenn ich Ihnen als geeigneteres Beispiel sagen würde, dass 34129 und 105319 beide Primzahlen sind (was sie sind), könnten Sie schnell herausfinden, dass ihr Produkt 3594432151 ist. Wenn ich Sie jedoch bitten würde, die beiden Primfaktoren von 3594432151 zu finden Dies ist wahrscheinlich schwieriger.

Für die Kryptografie mit öffentlichen Schlüsseln sind zwei Schlüssel erforderlich. Im Allgemeinen liefert der private Schlüssel den Parametern einen schwer umkehrbaren Algorithmus in eine Richtung (z. B. Klartext in Chiffretext), und der öffentliche Schlüssel liefert Parameter für einen schwer umkehrbaren Algorithmus in die andere Richtung.

Der Grund, warum Sie nicht rückwärts arbeiten können, liegt einfach darin, dass der Algorithmus so konzipiert ist, dass dies schwierig ist.

Beste Antwort im Vergleich zu den anderen.
Thomas Pornin
2015-04-22 19:12:50 UTC
view on stackexchange narkive permalink

Jonglieren ist einfach: Sie werfen die Bälle einfach zum richtigen Zeitpunkt, damit Sie beim Fallen freie Hand haben. Bei einem oder zwei Bällen ist dies trivial. Mit drei ist es einfach genug. Mit mehr Bällen wird es (überraschenderweise) schwieriger. Noch wesentlich schwieriger.

Im Allgemeinen ist das "Umkehren" der Verschlüsselung mit einem n -Bit-Schlüssel wie das Jonglieren mit 2 n sup> Bälle. Mit einem 2048-Bit-Schlüssel ist dies wie 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 Bälle. Oder so.

(Da Algorithmen mit öffentlichen Schlüsseln viele mathematische Strukturen verwenden, haben intelligente Köpfe die Mathematik genutzt, um diese Anzahl von Bällen auf 162259276829213363391578010288128 zu reduzieren, was erheblich niedriger ist, aber immer noch weit über dem Aggregat liegt Leistung aller vorhandenen Computer auf der Erde.)

Hahaha! Können Sie der Vollständigkeit halber erwähnen, wofür "Bälle" eine Metapher sind?
Es ist eine Metapher für die erste Reihe einer umfassenden Untersuchung eines Graphen, der das Verschlüsselungssystem darstellt, das als endlicher Automat ausgedrückt wird.
@ThomasPornin: Tolle Antwort! Können Sie ein Zitat für den Wert "162259276829213363391578010288128" angeben? Das sieht so aus, als wäre es 2 ^ 107, und ich habe Folgendes gefunden: https://www.imperialviolet.org/2011/04/09/multiprime.html, aber ich habe mich gefragt, ob Sie eine maßgeblichere Quelle oder eine Erklärung haben, die Sie bevorzugen .
Es gibt verschiedene Stellen, die versuchen, Schätzungen darüber vorzunehmen, wie RSA-Schlüsselgrößen mit symmetrischen Schlüsseln verglichen werden. Letztendlich gibt es keine einzige Antwort, da wir verschiedene Arten von Algorithmen vergleichen (für das Knacken symmetrischer Schlüssel zählt RAM nicht; während es für die Faktorisierung ganzer Zahlen viel zählt). Die Äquivalenz für RSA liegt somit zwischen etwa 100 und 112 Bit, je nachdem, wen Sie fragen und was Sie als "Einheits" -Operation betrachten. "107" abgeleitet aus der Rohanwendung der Komplexität des [General Number Field Sieve] (http://en.wikipedia.org/wiki/General_number_field_sieve).
Wenn Sie "maßgebliche" Quellen wünschen, schauen Sie sich [diese Site] an (http://www.keylength.com/en/). Insbesondere die Anwendung der ECRYPT II-Gleichungen (aus ihrem letzten verfügbaren Jahresbericht, der anscheinend aus dem Jahr 2012 stammt ...) führt dazu, dass RSA-2048 einem symmetrischen 103-Bit-Algorithmus "äquivalent" ist.
Diese Antwort verfehlt den Punkt, da sie den Eindruck erwecken kann, dass die Verschlüsselung mit einem solchen Schlüssel eine ebenso schwierige Aufgabe ist.
Während diese Antwort für jeden unterhaltsam ist, der die Grundlagen der Kryptographie tatsächlich versteht, ist sie kaum informativ und ich denke nicht, dass sie tatsächlich die gestellte Frage anspricht.
Rob
2015-04-23 07:31:56 UTC
view on stackexchange narkive permalink

Max, das beste Werkzeug, das jemals zum Nachdenken über Kryptographie entwickelt wurde, ist der Zauberwürfel. Wenn Sie von einer Welt ausgehen, in der das Lösen ein ungelöstes Problem darstellt, gibt es direkte Analoga für DiffieHellmanKeyExchange, RSA-Signatur, RSA-Verschlüsselung usw. Sie können Streiche spielen, indem Sie Züge aufschreiben, sie auf Würfeln ausführen und sie austauschen. und die gruppentheoretischen Gleichungen sind für die Krypto- und die Rubiks-Würfel gleich.

Aber das Wichtigste, was Sie beachten sollten, ist, was Sie stören muss: Sie haben Recht. Es ist "möglich", alle diese Operationen umzukehren. Technisch gesehen haben wir f (x) und f_inverse (x), wobei f (x) in Polynomzeit läuft (dh Sie können große Zahlen schnell verschlüsseln), während f_inverse (x, s) in Exponentialzeit läuft (dh: sogar mittel Zahlen sind nicht realisierbar) - es sei denn, Sie haben das richtige Geheimnis, um f_inverse anzuschließen. Solche Funktionspaare nennt man Falltüren. Die häufigsten Falltüren sind Probleme der Zahlentheorie wie Primfaktorisierung und diskrete Logarithmen.

Wenn man sich einen Zauberwürfel als Analogie für die Verschlüsselung vorstellt, hat man die Frage des OP. Wenn ich eine Reihe von Schritten (den Schlüssel) mit einem Würfel in einem bestimmten Zustand (Klartext) ausführe, um einen Würfel in einem anderen Zustand (Cyphertext) zu erhalten, kann ich dieselben Schritte rückwärts ausführen, um zum ursprünglichen Zustand zurückzukehren ((Schlüssel)). Klartext). Dass dies nicht für die asymmetrische Verschlüsselung gilt, ist die Frage, die gestellt wird.
In der Rubiks-Cube-Notation sind die Reverse-Operation und die Commutator-Operation identisch. Um eine Operation zu invertieren, wenden Sie nicht nur die inversen Funktionen an, sondern wenden Sie sie in umgekehrter Reihenfolge an. dh: (L * F * U) .inv == (U.inv * F.inv * L.inv). Der Unterschied zur asymmetrischen Verschlüsselung besteht darin, dass die .inv-Operation so ineffizient ist, dass Sie sie nicht ohne die Hilfe eines geheimen Schlüssels ausführen können.
Diese Idee erstreckt sich auf Hashes. Ein Hash ist eine Funktion, für die die .inv-Operation ineffizient ist, und es gibt keinen geheimen Schlüssel, der sie effizienter macht. Bei der symmetrischen Schlüsselverschlüsselung ist der INV-Schlüssel effizient. dh: Msg * SymmetricKey = CipherText. CipherText * SymmetricKey == Msg. Weil X * X.inv == 1.
Der Punkt ist, dass er tatsächlich richtig ist. Es ist nicht "unmöglich", die Verschlüsselung rückgängig zu machen. Es ist ineffizient. Nicht nur das, für die von uns verwendeten Falltürschemata ist nicht einmal bewiesen, dass es ineffizient ist. Wir hoffen, dass niemand bald die Primfaktorisierung herausfindet.
BeepBeep
2015-04-22 19:16:03 UTC
view on stackexchange narkive permalink

Sie müssen sich über Public-Key-Kryptografie informieren. Die kurze Antwort lautet: Es basiert auf einem Algorithmus, mit dem ein Schlüssel verschlüsselt und der andere Schlüssel entschlüsselt werden kann, weshalb Sie nicht rückwärts arbeiten können.

Dies ist eine vereinfachte Erklärung des Geschehens. Wenn Sie das Problem auf den Punkt bringen möchten, können Sie sich Quellen wie die folgenden ansehen. Seien Sie jedoch gewarnt, dass es schnell von der Klippe in die Mathematik übergeht Das kann für Sie einfach sein oder auch nicht: http://nrich.maths.org/2200

Und es gibt eine einfachere Grundierung auf http://doctrina.org/How-RSA-Works-With-Examples.html
woliveirajr
2015-04-23 17:43:47 UTC
view on stackexchange narkive permalink

Bei dieser Verschlüsselung mit öffentlichem Schlüssel (oder einer asymmetrischen Aufschrift) gehen Sie wie folgt vor, um etwas zu verschlüsseln:

Nehmen Sie Ihre Nachricht zur Übertragung (als Zahl): Nehmen wir an, es ist 5.

Berechne 3 ^ 5 (3 zum "Geheimnis" erhoben) = 243

Berechne den Modul davon, geteilt durch eine andere Zahl: sagen wir 143. Also 243/143 = 100.

Los geht's. Ihr verschlüsseltes Geheimnis ist 100.

Um das Geheimnis ohne den privaten Schlüssel zu finden, müssen Sie nur eine Zahl finden, die, wenn sie durch 143 geteilt wird, 100 ergibt, und dann den kubischen Radix davon finden.

Woher kommt der 143? Was ist hier der öffentliche Schlüssel und was ist der private? Diese Antwort lässt zu wünschen übrig, ist aber behebbar.
@ChrisCudmore danke, ich werde es bearbeiten, um es zu verbessern, wie Sie kommentiert haben
Es sieht so aus, als wäre '5' die Nachricht.
Pete
2015-04-25 21:48:18 UTC
view on stackexchange narkive permalink

Im Allgemeinen können Sie nicht rückwärts arbeiten - auf offensichtliche Weise -, weil Sie nicht über genügend Informationen verfügen.

RSA hängt von der Schwierigkeit ab, große Zahlen zu berücksichtigen. Sie erzeugen Ihren RSA-Modul n, indem Sie zwei große Primzahlen p und q multiplizieren. Das Multiplizieren von p mit q ist einfach. Sie können den Vorgang auch umkehren, indem Sie q = n / p (oder p = n / q ) berechnen. Was Sie nicht einfach tun können, ist, sowohl p als auch q wegzuwerfen und sie dann aus n zu berechnen. Dies ist ein anderes Problem und keine Umkehrung eines bereits verwendeten Prozesses.

In ähnlicher Weise umfasst die RSA-Verschlüsselung einer Nachricht m unter Verwendung des Verschlüsselungsschlüssels e die Berechnung von (m ^ e) mod n . Sie könnten m ^ e theoretisch mithilfe von Protokollen invertieren, aber ohne die Modulo-Operation wäre diese Zahl zu groß, um damit zu arbeiten. In jedem Fall verwirft die Modulo-Operation einen Teil der Nummer, sodass Sie wiederum nicht über alle Informationen verfügen, die Sie benötigen würden, um auf triviale Weise rückwärts zu arbeiten.



ⓘ
Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...