Gegenoperation zur Modulorechnung?
Hallo,
Mich würde mal interessieren, was es für Gegenoperationen zum Modulooperator gibt. Ich hege zur Zeit Interesse für Verschlüsselungen und experimentiere eben ein wenig herum.
Um einen verschlüsselten Text zu entschlüsseln, muss der Algorithmus ja rückrechenbar sein.
Der einzige Weg, der mir einfallen würde, um über den Rest an den ursprünglichen Wert zu kommen, wäre der Chinesische Restsatz. Doch leider funktioniert der nur, wenn 3 Reste vorhanden sind und x mod p = n, für p€P (Primzahlen), gilt.
Gibt es da noch andere Möglichkeiten? Für mein jetziges Experiment habe ich folgende Formel:
(2^c + i) mod 26 + 65
Liebe Grüße,
RouteUS66
3 Antworten
Das f(x) = g^x mod n (ohne die beiden anderen Summanden) ist eine so genannte diskrete Exponentialfunktion.
Wenn n eine Primzahl ist, dann gibt es (mindestens) eine Zahl g, sodass für x = 1, 2, ..., (n - 1) jede Zahl y = 1, 2, ..., (n - 1) angenommen wird, d. h. f(x) ist eine bijektive Abbildung der Menge {1, 2, ..., (n - 1)} in sich selbst, also eine Permutation. Die Zahl g heißt dann Erzeuger der Menge Z_{n}^{*}.
Die Umkehroperation dazu heißt diskreter Logarithmus. Und nun kommt die Krux an der Sache. Den diskreten Logarithmus zu berechnen ist schwer im Sinne der Komplexitätstheorie, d. h. um Dein Verfahren sicher zu machen, musst Du n sehr groß wählen. Dann kannst Du die Operation aber nicht mehr invertieren.
Die Tatsache, dass die Operation einfach zu berechnen, aber schwierig zu invertieren ist, kann man allerdings verwenden, um daraus eine so genannte Falltürfunktion zu bauen und diese kann man dann für kryptographische Zwecke verwenden. Das funktioniert aber nicht so direkt. Es gibt einige asymmetrische Kryptosysteme, die auf der diskreten Exponentialfunktion (bzw. dem diskreten Logarithmusproblem) beruhen. Die wichtigsten Vertreter sind der Diffie-Hellman-Schlüsseltausch, sowie das darauf aufbauende Elgamal-Kryptosystem.
Ersterer ist noch einigermaßen verständlich, kann allerdings nicht direkt zur Verschlüsselung eingesetzt werden, sondern dient dazu, auf sichere Art und Weise einen gemeinsamen geheimen Schlüssel über einen "unsicheren" (öffentlichen) Kanal zu vereinbaren. Das heißt, selbst wenn jemand auf dem Kanal mithört, kann dieser aus den ausgetauschten Nachrichten nicht (effizient) den ausgehandelten Schlüssel berechnen.
Letzteres ist tatsächlich ein Kryptosystem, allerdings ein asymmetrisches, d. h. Du benötigst zum Ver- und Entschlüsseln unterschiedliche Schlüssel. Und es ist leider auch nicht mehr wirklich einfach zu verstehen.
Wenn die Gruppe so gewählt ist, dass das diskrete Logarithmusproblem in ihr nicht schwer im Sinne der Komplexitätstheorie ist, etwa weil der Modulus p klein ist, dann lässt sich die Funktion umgekehren.
Es ist dann aber keine sichere Verschlüsselung. Was soll hier überhaupt der (geheime) Schlüssel sein? Das i? Das ist ja völlig unabhängig von der Exponentiation. Schwer zu invertieren ist einzig und allein die Exponentiation und zwar sowohl für den "legitimen" Nutzer, als auch für den Angreifer. So kann man keine Sicherheit schaffen.
Für ein sicheres Kryptosystem benötigst Du entweder eine Operation, die "unter normalen Umständen" schwer zu invertieren ist und unter Kenntnis einer Zusatzinformation leicht (Falltüroperation) oder eben ein symmetrisches Verfahren und einen geheimen Schlüssel.
Ein einfaches symmetrisches Verfahren, das zudem perfekte Geheimhaltung (perfect secrecy) bietet, ist das so genannte One-Time-Pad. Hierbei wird die Nachricht mit dem geheimen Schlüssel per XOR verknüpft, was einer Addition im endlichen Körper F2 entspricht. Damit das Verfahren sicher ist, muss der Schlüsselstrom zufällig gleichverteilt gewählt werden und genau so lang sein, wie die Nachricht. Das Chiffrat enthält dann keinerlei Information mehr über den Klartext, weshalb selbst ein Angreifer mit unendlichen Ressourcen keinerlei Information mehr aus dem Chiffrat gewinnen könnte.
Andere symmetrische Verfahren, so genannte Stromchiffren, funktionieren ähnlich wie das One-Time-Pad, erzeugen den langen Schlüsselstrom, der dann nur noch pseudozufällig ist, aus einem kürzeren geheimen Schlüssel. Dann gibt es auch noch Blockchiffren, die anders konstruiert werden. Wie man so etwas umsetzt, ist allerdings nicht einfach zu erklären. Generell sollte man selbstentwickelte Kryptoverfahren nur zum Experimentieren verwenden, denn sie sind eigentlich immer angreifbar. ;-)
Voraussetzung für die Existenz einer Umkehrfunktion ist eine injektive Abbildung. Da Modulo aber nicht injektiv ist, gibt es keine Umkehrfunktion.
Das geht nicht. Angenommen du hast x mod 10 = 5 dann kann x alles sein: 5, 15, 25, ..., 1525,.. etc etc.
Die Modulo-Operation ist nicht umkehrbar
Erstmal vielen lieben Dank für die detaillierte Antwort!
Das hieße dann (wenn ich es richtig verstehe), dass die Entschlüsselung des Algorithmus generell möglich wäre, wenn man den Klartext mithilfe des diskreten Logarithmus berechnet?