Peter-K-Webseiten


Hauptseite

Sitemap


Letzte Änderung / Last update: 2023-Feb-28

Verschlüsselung 10crypt

Um sensible Informationen auch bei der Übertragung übers Internet vor fremden Augen zu schützen, verschlüsselt man sie. Verfahren dazu gibt es seit der Antike, heutzutage in Form von Software und ihren Algorithmen. Wissenschaftlich spricht man von [WP Kryptologie], neudeutsch von Encryption und Decryption.

Am Anfang wurden vor allem Verfahren verwendet, bei denen die Buchstaben des Alphabets gegenseitig vertauscht wurden, siehe [WP Substitution (Kryptographie)]. Hierfür – wie auch heute immer noch – müssen sowohl Absender als auch Empfänger sowohl das Verfahren kennen als auch die aktuelle Ersetzungssystematik, beispielsweise jeden Buchstaben um drei Plätze im Alphabet zu versetzen.

Solche einfachen Verfahren sind natürlich leicht durchschaubar und damit zu knacken. Mit heutigen leistungsfähigen Computern kann man jede Menge verzwickter Verschlüsselungstricks nachvollziehen und auflösen. Und auch bei komplizierteren Verschlüsselungen können sie dank ihrer Rechenkraft schon mal stumpf alle möglichen Werte des jeweiligen Schlüssels durchprobieren, dessen muss man sich bewusst bleiben. Das alles noch vor jeglichem Einsatz von KI.

Das Ziel soll es sein, eine Nachricht, also allgemein eine Datei, so zu verschlüsseln, dass auch aktuelle Computerleistung nicht in der Lage ist, diese Verschlüsselung in praktisch realisierbarer Zeit zu knacken. Zweitens soll es dem Anwendenden möglichst leicht gemacht werden; denn wenn sie oder er durch die Eingabe ewig langer Passwörter abgeschreckt wird und dann entweder gar nicht verschlüsselt oder nur mit untauglich kurzem Passwort, ist sowieso alle Mühe umsonst.

Das Dilemma ist offensichtlich: Ausreichende Sicherheit bekommt man nur mit sehr langen Passwörtern, was den Aufwand beim Benutzer extrem hochtreibt. Als eine Abhilfe dient ein [WP Asymmetrisches Kryptosystem], wo der Anwender zu einem großen Teil entlastet wird. Eine beliebte Software hierzu ist [WP Pretty Good Privacy], abgekürzt PGP.

Da werden auch Algorithmen verwendet, die auf Produkten von großen Primzahlen beruhen. Ist das Produkt zweier solcher Zahlen öffentlich, so kann man mit normalem Rechenaufwand praktisch nicht die beiden Faktoren ermitteln. Für die Zukunft ist dieser Ansatz aber in Gefahr, da die aufkommenden [WP Quantencomputer] versprechen, diese Aufgabe direkt lösen zu können.

Im Endeffekt soll das Verschlüsselungsverfahren so geschickt sein, dass man den Algorithmus vollkommen offenlegen kann, und die Verschlüsselung trotzdem nur mit vollständiger Kenntnis des Passworts, der Schlüsselsequenz, aufgelöst werden kann. Am besten funktioniert so etwas mit einem [WP One-Time-Pad], also mit einem Schlüssel, der nur einmal verwendet wird und idealerweise länger ist als die zu verschlüsselnde Nachricht. Das ist aber nichts für die tägliche Praxis. Man versucht dem aber näher zu kommen, indem man einen Schlüssel von handhabbarer Länge verwendet und ihn durch einen Algorithmus sozusagen aufbläst, um ihn wie einen viel längeren wirken zu lassen.

Ein Ansatz in dieser Richtung wurde von vielen Spionen verwendet, und zwar das Codebuch. Ein Buch, das jeder Agent und natürlich ihre Zentrale besaß. Dann konnte man Schlüssel definieren, indem man beispielsweise auf Seite x und dort auf den Buchstaben in Zeile y und an Position z verwies. Oder auf ganze Wörter oder Sätze an solchen Stellen. Dumm nur, wenn dem Feind so ein Codebuch in die Hände fiel, dann lag auf einen Schlag alles offen. - Ich brüte schon lange Zeit darüber, wie man das heutzutage realisieren könnte: Man bräuchte eine große Datei, mindestens mehrere Megabytes, die jeder auf seinem Rechner hat (also Teil des OS), die sich aber vor allem nicht dauernd bei regelmäßigen Updates ändert. Gute Kandidaten wären evtl. auch Bilder, die in größerer Anzahl zum Verschlüsselungsprogramm dazugehören könnten. Mehrere Bilder, damit man nicht immer dasselbe nehmen muss. Ich suche da noch nach Inspirationen.

So, und um dies alles nicht nur als graue Theorie zu durchdenken, will ich auch selbst aktiv werden. Ja, es gibt schon massenweise fertige Programme dazu, aber bei selbst Gebasteltem weiß ich halt am besten, was da alles unter der Haube vor sich geht und wo die Fallen sind, in die man tappen kann, und was drum herum alles wichtig wird, das einem zunächst gar nicht aufgefallen war. Am Ende kann man sich dann zurücklehnen und mit umso mehr Hintergrunderfahrung auch fremde Programme beurteilen, wieviel sie wirklich taugen. Meine Idee wird irgendwann zu einem ziemlich umfangreichen Programm werden, das ich aber im Kopf schon sehr nett in kleine, hoffentlich gut umsetzbare Segmente aufgeteilt habe. Als ersten Anlauf will ich hier als Quick-and-Dirty-Projekt einen kleinen Teil jenes kommenden Großprojekts realisieren. Wenn es gut läuft, sollte aber auch dieser Teil schon gut (halt nicht optimal) brauchbar sein. Worauf ich erst zuletzt achte, ist die Performance; im Vergleich mit bestehender Standard-Software wird das hier bestimmt sterbenslangsam werden.


XOR

Mein Ansatz versucht, dieses Ziel des virtuell riesig langen Schlüssels per [WP XOR-Verknüpfung] umzusetzen. XOR steht für exklusives Oder, einfach gesprochen entweder-oder: Ein Bit wird wahr, wenn von den beiden Eingangsbits entweder das eine oder das andere wahr ist, sie also verschieden sind. Daher wird es auch als "ungleich"-Verknüpfung bezeichnet. XOR angewandt heißt, dass man die Nachricht/Datei byteweise mit den Bytes eines Schlüssels verknüpft und so umcodiert. Der Charme der XOR-Verknüpfung besteht darin, dass sie invertierbar ist: Wenn man sie ein zweites Mal auf das umcodierte Byte anwendet, ergibt sich wieder genau das ursprüngliche Byte. Man braucht also für Ver- und Entschlüsselung nur ein einziges Programm!

Ok, wenn man es ganz primitiv macht, wird die komplette Nachricht mit ein und demselben Byte XOR-verknüpft. Das zu knacken, ist aber zu einfach. In der nächsten Stufe nimmt man eine ganze Schlüsselsequenz, die aus praktischen Gründen nicht arg lang sein darf. Wenn alle ihre Bytes mit den ersten Bytes der Nachricht verknüpft sind, fängt man einfach wieder von vorne im Schlüssel an. Aber auch das ist kaum schwieriger zu knacken.

Mein Ansatz ist danach, dass ich eben nicht den eingegebenen Schlüssel direkt verwende. Stattdessen habe ich einen sehr langen Schlüssel fest ins Programm eingebaut und verwende dann Teile dieses Schlüssels, die dann mit der Nachricht XOR-verknüpft werden. Welche Teile wann verwendet werden, das wiederum steuere ich indirekt über eine zweite Schlüsselsequenz, die ich ganz konventionell eingebe, die dann aber nicht so lang zu sein braucht.

Und dann setze ich noch eine Steigerung obendrauf: Jedes Byte der Nachricht wird nicht nur mit einem einzelnen Byte der Schlüsselsequenz verknüpft, sondern mit mehreren, von verschiedenen Stellen der Sequenz stammend. Diese Stellen wandern mit bestimmten Schrittweiten durch die Grundsequenz, und zwar in Schritten, die in Primzahlen bemessen sind. Warum Primzahlen? Wenn ich zwei solche Sequenzen durch die Grundsequenz laufen lasse, sollen sie nicht parallel laufen oder sich zu oft treffen. Genau das erreiche ich durch Schrittweiten aus (verschiedenen) Primzahlen.

In meinem konkreten Programm 10crypt verwende ich zehn verschiedene Primzahlen. Die Nachricht wird dann byteweise mit jeweils zehn Bytes aus der Grundsequenz XOR-verknüpft und dann in dieser Form in die verschlüsselte Datei gespeichert. Zum Entschlüsseln muss ich nur genau das Gleiche mit der gleichen Schlüsselsequenz auf die verschlüsselte Datei anwenden und bekomme als Resultat wieder die Originaldatei.


Programm 10crypt.bas

Das Programm ist in [WP FreeBASIC] geschrieben und dadurch wohl besonders gut lesbar auch für Leute aus anderen Programmiersprachenlagern.

  • Es sind ein paar Programmteile aus einem Vorgängerprogramm erhalten, die jetzt keine Funktion mehr haben; man könnte mal aufräumen.
  • Variablen sind durch angehängte Zeichen typisiert: $ für Strings, % für 16-Bit-Integers, & für 32-Bit-LongInts, # für Long-Reals.
  • Die Grundsequenz erstreckt sich im Programmtext über mehrere Zeilen und ist in der Stringvariablen co$ gespeichert. Sie entstand durch willkürliches Herumhämmern auf der Tastatur, absichtlich ohne jedes System.
  • Die Primzahlen werden aus der DATA-Zeile in den Array pri%() eingelesen, die zugehörigen Untersequenzen in den zugehörigen Arrays p%() verwaltet. Die verwendeten Primzahlen sind willkürlich ausgewählt, es sind nicht einfach aufeinander folgende. Sie dürfen bei dieser Programmierung lediglich nicht größer als 99 werden.
  • Die eigene Schlüsselsequenz wird als lange Code-Sequenz vom Anwender eingegeben, in die Variable cc$. Die Sequenz darf nur aus Ziffern und auch nicht nur aus Nullen bestehen. Im Idealfall soll sie 20 Zeichen lang sein, 2 Ziffern jeweils als Anfangs-Offset für jede Primzahl. Gibt man weniger als 20 Stellen ein, wird der Rest automatisch generiert, indem die Quersumme der eingegebenen Ziffern angehängt wird. Das wird ggf. wiederholt, bis die 20 erreicht ist. Beispiel für eine erinnerbare 20-Ziffern-Folge: drei 8-stellige Geburtsdaten von Familienmitgliedern, ggf. teilweise rückwärts einzugeben.
    Der Punkt ist in jedem Fall, dass man der verschlüsselten Datei am Ende nicht ansehen kann, mit einer wie langen Schlüsselsequenz sie erzeugt wurde!
  • Zur eigentlichen Verschlüsselung wird die Eingangsdatei byteweise als Variable c gelesen. In einer Laufanweisung über die Primzahlen wird die Verknüpfungsvariable c2 bestimmt. Bei ihr wird zusätzlich darauf geachtet, dass bei jedem zweiten Mal auch das oberste Bit (MSB, das in der Grundsequenz arg selten vorkommt) gesetzt wird, sofern es das nicht schon ist.
  • Die Bytes der Originaldatei werden übrigens einfach an ihrem Ort belassen, es werden auch keine hinzugefügt. Bei modernen Verfahren werden die Bits jedes Bytes dagegen gerne miteinander verwürfelt, so dass sie über einen Block von beispielsweise 64 Bytes verstreut werden. Das ist eines der Elemente, die hier weggelassen sind.
Durch die Anzahl von zehn Primzahlen und deren Werte ergibt sich eine virtuelle Schlüssellänge von vielen Billionen. Das sollte für praktische Anwendungen ausreichen. - Ausführlicher: Die Multiplikation der verwendeten zehn Primzahlen ergibt:
7*13*19*23*29*37*43*53*57*67 = 371.378.309.338.491 = ca. 3,7*1014
Binär bzw. hex: 1.51C4.4034.957B = ca. 1,3*248, also knapp 50 Bit

Die erwähnte Sonderbehandlung des MSB habe ich aus Neugier mal überprüft. Dazu habe ich mit einem eigenen, kleinen Programm in der verschüsselten Datei separat die Bits 0 bis 7 jedes Bytes zusammengezählt. Und tatsächlich waren sie ziemlich gleichmäßig verteilt, mit erwartbaren Schwankungen. Das scheint also zu funktionieren.

Wer an dem Programm etwas ändern möchte, kann zum einen die Grundsequenz ändern (auch in ihrer Länge) und andererseits die Auswahl und Anzahl der Primzahlen. Die Funktion sollte dadurch kaum gestört werden können, und die Ergebnisse der Verschlüsselung werden total anders aussehen.

Wer diese Verschlüsselung knacken will und einen richtigen Supercomputer zur Hand hat anstelle eines simplen PCs, muss eigentlich mit Brute Force alle Möglichkeiten durchprobieren. Die Schlüssellänge entspricht hier etwa 50 Bit, das sind hunderte Billionen Möglichkeiten, die es für die Eingabe der Code-Zahl gibt. Auch für einen Supercomputer wird das schon schwierig. Und er steht noch vor einem zweiten Problem: Woran erkennt man, dass die Entschlüsselung erfolgreich ist? Bei Klartext ist das ein kleineres Problem, es sei denn, man hätte es mit ganz exotischen Sprachen zu tun. Was aber, wenn man es sowieso schon mit Binärdateien zu tun hat, Zip-Archiven, Programm-Executables, komprimierten Bilddateien? Die sehen auch im Normalzustand aus wie Binärgemüse, wie soll man sie dann als entschlüsselt erkennen?

Wenn ich das also zu knacken versuchen müsste, würde ich beispielsweise darauf warten, dass ich weiß, dass es um eine Bilddatei geht. JPG-, GIF- oder BMP-Dateien fangen mit definierten Kennbuchstaben an. Ich würde dann zunächst nur das allererste Byte hernehmen und das mit allen hundert Billionen möglichen Werten der Code-Zahl durchprobieren. Das sollte noch gerade machbar sein. Es sollten viele Werte der Code-Zahl herauskommen, mit denen das klappt. Die würde ich mir alle merken. In weiteren Durchläufen würde ich diese wenigeren Werte nehmen und das zweite und dritte Byte behandeln. Auf diese Weise könnte man das Problem deutlich einschränken, so dass es vielleicht bearbeitbar wird. Aber wie gesagt, bisher nur rein theoretisch und nur bei Bildern.

Eine Ergänzung könnte dem Programm guttun: Die Namen und Pfade von Eingangs- und Ausgangsdatei sind fest eingebaut als 1.txt und 2.txt. Wenn mir jemand beibringen könnte, wie man den OpenFile-Dialog von Windows von FreeBasic aus aufruft, dem wäre ich dankbar.

Wo ich selbst leider keinerlei Kompetenz habe, ist, ob so ein Ansatz geeignet sein könnte, auch einem Quantencomputer zu widerstehen. Wer mich da aufklären könnte, sollte mir eine Mail schreiben, da wäre ich ebenfalls dankbar.


Testfälle

Auf dieser Website findet man folgende Dateien bereit zum Download per Browser-Befehl "Ziel speichern unter ...":

Ausblick

Wie oben schon angemerkt, ist dies hier nur ein Teil eines größeren Projekts, das mir vorschwebt. Das sollte dann noch um einiges aufwendiger zu knacken werden. Aber wie es in den Erwägungen oben zum Knacken solcher Verschlüsselungen schon anklingt, kann man heute mit Supercomputern oder den kommenden Quantencomputern gewaltig viel erreichen. Ich ahne schon, dass ich nicht darum herum kommen werde, vom Anwender ewig lange Schlüsselsequenzen eingeben zu lassen. Auch da gibt es Tricks, wie man das erleichtern kann, aber die sind am Ende natürlich auch durchschaubar und knackbar. Bis man damit Staatsgeheimnisse sicher verschlüsseln kann, ist wohl noch ein ziemlicher Weg. Ich denke also noch darüber nach.






↑ Seitenanfang/Top of page  /   DSGVO,   © Copyright Dr. Peter Kittel, Frankfurt/M, 2020, 2021, 2022, 2023, 2024