| www.r-krell.de |
| Webangebot für Schule und Unterricht, Software, Fotovoltaik und mehr |
Willkommen/Übersicht > Informatik > Informatik-Seite j)
Teil j): Kryptologie I
Eine vollständige Übersicht aller meiner Seiten "Informatik mit Java" gibt's auf der Informatik-Hauptseite!
In diesem Teil j) befindet sich der erste Teil meiner Ausführungen zur Kryptologie, nämlich die Kryptologie I mit:
Die Fortsetzung "Kryptologie II" folgt auf einer eigenen Seite!
zum Seitenanfang / zum Seitenende
Die Kryptologie wird oft als die Wissenschaft vom Geheimhalten von Nachrichten (durch die Kryptografie) sowie vom Enträtseln abgefangener geheimer Botschaften (durch die Kryptoanalyse) definiert. Das Entdecken oder Entschlüsseln einer geheimen Botschaft durch den rechtmäßigen Empfänger, der im Besitz des richtigen Schlüssels ist, gehört danach eher noch zur Kryptografie. Denn unter der Kryptonanalyse versteht man eigentlich nur den Angriff auf Nachrichten, die man nach Wunsch des Absenders nicht hätte lesen sollen, und wo man nicht im Besitz des (vollständigen) Schlüssels ist.
Je nach eingesetztem Verfahren werden bzw. wurden klassischerweise verschiedene Hauptzweige der Kryptologie unterschieden:
Auch wenn Buchstabenpaare oder größere Nachrichtenblöcke (mehrere Buchstaben gemeinsam) verschlüsselt werden, spricht man von Chiffrierung. Codierung bedeutet, dass man Klartextbegriffe durch andere Wörter oder Aussagen durch unverfängliche Redewendungen ersetzt, also sich etwa mit seinem Partner darauf einigt, von Rosen und Tulpen zu sprechen, wenn man Desktop-PCs oder Laptops meint, damit ein unberechtigter Lauscher nicht den wahren Gegenstand der Verhandlung erfährt. In der Praxis bzw. bei vielen Autoren werden allerdings die Begriffe nicht so streng getrennt, sondern z.B. Codierung, Chiffrierung und Verschlüsselung nahezu synonym verwendet.
Schien die Kryptologie früher eher eine Domäne der Militärs und Geheimdienste, so ist mit der Verbreitung von Computern, dem prinzipiell leicht abhörbaren Internet, Geld- und Kreditkarten und der zunehmenden Verbreitung von Online-Einkäufen und Online-Banking ein großer ziviler Bedarf an der Kryptologie entstanden: Die bei Online-Einkäufen einzugebenden privaten Daten und Kontoverbindungen bzw. Kartennummern sollen durch verschlüsselte Übertragung geschützt werden; die per Internet-Download erhältlichen Aufgabenstellungen für das Zentralabitur sollen nur von berechtigten Nutzern (Schulen mit den entsprechenden Abiturfächern) aus geschützten Bereichen herunter ladbar sein und sind so verschlüsselt, dass nur der Schulleiter den Download mit seinem geheimen Schlüssel in lesbaren Text verwandeln kann. Aber auch am Geldautomaten oder an der Supermarktkasse soll bei Kartenzahlung prüfbar sein, ob die eingegeben Geheimzahl (PIN) richtig ist, ohne dass der PIN offen im Chip oder auf dem Magnetstreifen der Karte stehen darf, wo er von einem Kartendieb oder unehrlichen Finder mit einem billigen Lesegerät ausgelesen werden könnte. Bei zunehmenden Phishing-Attacken (wo sich Kriminelle als vermeintliche Bankangestellte ausgeben oder Bankwebseiten nachahmen, um Kunden zur Eingabe von Kontonummer und Passwörtern zu verleiten, die so in falsche Hände gelangen) wird es außerdem immer wichtiger, auch Authentifikationsmöglichkeiten bereit zu stellen (Beweismöglichkeit, dass eine Nachricht tatsächlich vom angegebenen Absender stammt).
Insofern fasst man heute den Kryptologie-Begriff etwas weiter und nennt vielfach folgende Ziele der Kryptografie:
Gelegentlich wird noch als viertes Ziel genannt:
Beim Beispiel der Übertragung von Zentralabituraufgaben ist hingegen die Anonymität weder nötig noch gewünscht -- nicht bei jeder Anwendung der Kryptografie müssen immer alle Ziele erreicht werden; viele Anwendungen geben sich mit der Erreichung eines Ziels zufrieden.
Bei der Kryptoanalyse geht es umgekehrt wieder darum, die Wirksamkeit der eingesetzten Schutzmechanismen zu prüfen, Schwachstellen zu entdecken und auszunutzen, kurz die genannten Ziele zu testen oder gar zu brechen. Kryptografie und Kryptoanalyse zusammen bilden wieder die Kryptologie und befinden sich im ewigen Wettstreit, der zum Fortschritt der Kryptologie beiträgt.
zum Seitenanfang / zum Seitenende
1. Steganografie
Hier geht es darum, die Nachricht zu verbergen. Bestenfalls fällt gar nicht auf, dass Sender und Empfänger in Kontakt treten, weil die Nachricht z.B. in einem im Internet abgelegten Bild versteckt ist, das von Vielen angesehen und herunter geladen wird. Aber nur der berechtigte Empfänger weiß von der Nachricht, sucht danach und findet sie. Wird die versteckte Nachricht vor dem Verstecken zusätzlich noch verschlüsselt und in kleine Teile zerlegt auf mehrere Bild- und Musikdateien verteilt, so wird auch durch eine zufällige unberechtigte Entdeckung nicht sofort die Botschaft sichtbar.
Auch wenn im Internet spezielle Steganografie-Programme angeboten werden, lassen sich eigene Versuche auch ohne zusätzliche Software ausführen. Zunächst wird etwa mit einem einfachen Texteditor (wie z.B. notepad) eine reine ANSI-Text-Datei klartext.txt mit dem zu versteckenden Text erzeugt. Dann nimmt man eine Grafikdatei, etwa meine ursprüngliche Vorlage KryptoHauptzweige.gif für das im vorigen Abschnitt gezeigte Bild. Befinden sich beide Dateien im gleichen Ordner, so kann man dort unter der (Dos-)Eingabeaufforderung den Befehl
copy /b KryptoHauptzweige.gif + klartext.txt if-j-kryptozweige.gif
ausführen. Dadurch entsteht eine neue Bilddatei namens if-j-kryptozweige.gif, die im Bildbetrachtungsprogramm unverändert aussieht, aber den Text aus der Klartext-Datei zusätzlich am Ende beinhaltet. Der Zusatztext wird aber nicht im angezeigten Bild, sondern nur durch das Öffnen der neuen Bilddatei mit einem Hexeditor sichtbar. Steht kein eigener Hexeditor (wie etwa HxD oder HexCellent) zur Verfügung, so kann auch der im kostenlosen und empfehlenswerten Grafikprogramm Irfanview vorhandene Hex-Viewer benutzt werden:
Tatsächlich wurde dem im vorigen Abschnitt gezeigten Bild der Zusatztext genau auf diese Weise hinzugefügt. Nach Rechtsklick in die Zeichnung und "Bild speichern unter.." können Sie die Grafik auf Ihren Rechner herunter laden und dort entsprechend untersuchen.
Die Methode des Zusammenkopierens funktioniert nicht nur bei Bildern im .gif-Format, sondern beispielsweise auch bei .jpg-Bildern. Dort kann der Zusatztext sogar am Anfang oder am Ende hinzugefügt werden, ohne die Darstellung des Bildes zu stören. Grundsätzlich können Bildern nicht nur einfache Texte, sondern z.B. auch Tabellenkalkulations-Arbeitsblätter o.ä. versteckt hinzugefügt werden. Allerdings fällt gerade bei den komprimierenden Formaten auf, wenn die Datei für ein kleines Bild plötzlich sehr große Ausmaße hat. Mit dem kurzen Klartext in meinem Beispiel wurde die Dateigröße von ursprünglich 6 auf 7 kB vergrößert -- das erweckt noch keinen Argwohn. Natürlich gehen die Zusatzinhalte sofort verloren, wenn ein Übermittler das Bild in einem Bildbearbeitungsprogramm öffnet und erneut speichert oder auch mit einem Formatkonverter in ein anderes Bildformat überträgt.
zum Seitenanfang / zum Seitenende
2. Klassische (symmetrische) Chiffrier-Verfahren
Bei der Verschlüsselung (der Kryptografie im engeren Sinne) wird die Nachricht nicht versteckt, sondern so verändert, dass ein Angreifer nur eine sinnlose Buchstabenfolge sieht, die er nicht deuten kann. Bei den symmetrischen Verfahren wird zum Verschlüsseln und zum Entschlüsseln die selbe Zusatzinformation, der gleiche "Schlüssel", benötigt. Der Schlüssel muss i.A. getrennt von der Nachricht sicher und geheim übertragen werden und darf nicht in fremde Hände fallen, weil mit dem Schlüssel das Entwirren des Geheimtextes leicht fällt. Schließlich soll der berechtigte Empfänger ja den Klartext wiederherstellen können.
Im Folgenden sollen einige
klassische Verfahren vorgestellt und in Java programmiert werden. Die grafische Benutzer-Oberfläche kann
für alle Verfahren gleich sein: Zwei Textfelder dienen der Ein- bzw. Ausgabe von Klar- oder Geheimtext; ein
drittes Textfeld nimmt den Schlüssel auf. Mit zwei Schaltflächen kann entweder das Ver- oder das
Entschlüsseln befohlen werden. Radiobuttons erlauben die Auswahl des gewünschten Verfahrens.
Damit die Oberfläche CryptoRahmen fertig bereit gestellt werden kann, bevor die einzelnen Verfahren programmiert wurden, empfiehlt sich die Verwendung eines Interfaces: alle Verfahren müssen dieses Interface CryptoAction implementieren, d.h. die beiden Methoden verschlüssele und entschlüssele bereit stellen. Die Oberflächen-Schaltflächen rufen die Interface-Methoden auf; zur Laufzeit werden diese durch die gleichnamigen Methoden des dann gerade gewählten Verfahrens ersetzt (späte Bindung; Polymorphie):
zum Seitenanfang / zum Seitenende
2a) Skytale (Transposition)
Schon die alten Griechen haben dieses Transpositionsverfahren benutzt. Der Klartext wird zeilenweise auf ein Band bzw. auf einen um einen Zylinder gewickelten Papierstreifen geschrieben. Nach dem Abwickeln stehen die Buchstaben in scheinbar unsinniger Reihenfolge auf dem Papierstreifen und lassen den Klartext nicht ohne Weiteres erkennen. Zum Entschlüsseln muss ein Zylinder mit gleichem Radius bzw. gleichem Umfang verwendet werden -- der Zylinder-Umfang ist praktisch der Schlüssel.
Für die Programmierung sind verschiedene Ansätze denkbar. Hat der Zylinder z.B. einen Umfang von 5 Buchstaben, dann gilt beim Verschlüsseln: Der 0. Klartextbuchstabe ist immer auch der 0. Geheimtextbuchstabe. Der nächste, erste Klartextbuchstabe steht hingegen an der 5. Stelle (= 0 + Umfang) des Geheimtextes, der 2. Klartextbuchstabe steht an der 10. Stelle (= 5 + Umfang) im Geheimtext, usw. Ist die nullte Zeile voll, so kommt der vorderste (=0.) Buchstabe der nächsten, ersten Klartextzeile an die 1. Stelle auf dem Band (=Geheimtext), der folgende Klartext-Buchstabe an die 6. Stelle (= 1 + Umfang) des Geheimtextes, der nächste Klartext-Buchstabe an die 11. Stelle im Geheimtext, usw. Etwas Augenmerk muss auf das Textende gerichtet werden: Einfach ist es, nur volle Windungen zuzulassen und bei einem kürzeren Klartext, der weniger Zeichen als das Produkt aus Umfang und Windungszahl hat, die letzten Zeichen der letzten Klartextzeile frei zu lassen (Variante I). Soll hingegen der Geheimtext nur so lang sein wie die Klartextbotschaft, dann ist die letzte Windung nicht vollständig und die letzten Klartext-Zeilen können kürzer sein als die 0. Zeile (Variante II). Beide Verfahrens-Varianten können zu verschiedenen Geheimtexten führen!
Grundsätzlich ist die (ohnehin geringe) Sicherheit des Verfahrens noch schlechter, wenn ein unnötig langes Band zum Verschlüsseln verwendet wird. Gibt es im Extremfall mehr Windungen als Klartextbuchstaben und damit nur eine Klartextzeile, dann stehen im Geheimtext die Klartextbuchstaben -- jeweils nur durch viele Leerzeichen getrennt -- in der richtigen Reihenfolge unter- bzw. hintereinander und die Botschaft kann leicht gelesen werden. Ebenfalls fehlt jede Schutzwirkung bei höchstens einer Windung und einem Umfang größer oder gleich der (Klar-)Textlänge.
Ein abgefangener Skytale-Geheimtext kann auch ohne Kenntnis des geheimen Schlüssels (=Umfangs) immer relativ leicht "geknackt" werden: Für einen Brute-Force-Angriff müssen als Schlüsselwerte (=Umfänge) nur die natürlichen Zahlen zwischen 2 und der Textlänge ausprobiert werden -- mit einem Computer ist das in kürzester Zeit machbar. Der richtige Schlüssel ist der, der zu einem lesbaren Text führt. Wegen der hohen Regelmäßigkeit des Verfahrens ist i.A. nicht zu befürchten, dass auch falsche Schlüssel zu sinnvollen Texten führen. Die richtige Klartextnachricht muss daher nicht erst aus einer Vielzahl weiterer sinnvoller Texte heraus gesucht werden. Sinnvolle Texte können auch von Computerprogrammen recht gut erkannt werden: Man unterwirft den entschlüsselten Text etwa der aus Textverarbeitungsprogrammen bekannten Rechtschreibprüfung verschiedener Sprachen und hält den Text und die Sprache für sinnvoll und richtig, wo kaum bzw. die weitaus wenigsten Fehler auftreten.
| public class CryptoSkytaleII implements CryptoAction // Variante II -- R. Krell für Webseite www.r-krell.de/if-java-j.htm, 16.1.2011 { public String verschlüssele (String klartext, String zusatz) { char[] geheim = new char[klartext.length()]; // Char-Reihung statt String, um Zeichen .. // .. an beliebige Stellen des Geheimtextes schreiben zu können int umfang = alsGanzzahl (zusatz); // Schlüssel/Umfang wie in zusatz angegeben int i = 0; // Beginn mit dem 0. Klartextbuchstaben for (int zeilenNr = 0; zeilenNr < umfang; zeilenNr++) // Klartext wird zeilenweise gelesen. { // Die Zeilenzahl ist durch den Umfang des Zylinders begrenzt. for (int pos = zeilenNr; pos < klartext.length(); pos = pos+umfang) { // pos gibt richtige Stelle des aktuellen Klartextbuchstabens im Geheimtext an geheim[pos] = klartext.charAt(i); i++; // i ist Stelle des aktuellen Klartextbuchstabens im Klartext } } return (new String(geheim)); // die Char-Reihung wird als String zurück gegeben } public String entschlüssele (String geheimtext, String zusatz) { // Umkehrung des Verschlüsselns String klartext = ""; int umfang = alsGanzzahl (zusatz); for (int zeilenNr = 0; zeilenNr < umfang; zeilenNr++) { for (int pos = zeilenNr; pos < geheimtext.length(); pos = pos+umfang) { klartext = klartext + geheimtext.charAt(pos); } } return (klartext); } private int alsGanzzahl (String zusatz) { int zahl = -1; try { zahl = Integer.parseInt(zusatz); } catch (NumberFormatException e) { } return (zahl); } } |
zum Seitenanfang / zum Seitenende
2b) Cäsar-Verschlüsselung (monoalphabetische Substitution mit verschobenem Alphabet)
Schon Julius Cäsar hat seine Tagebucheinträge chiffriert. Statt des normalen Alphabets benutzte er ein
um drei Zeichen verschobenes Alphabet. Immer, wenn in Klartext ein 'a' vorkam, schrieb er 'd'. Und für jedes 'f'
schrieb er 'i', usw. Heute bezeichnet man jede Chiffrierung, die durch die Verschiebung des Alphabets um ein oder
mehrere Zeichen bewirkt wird (also nicht nur die Verschiebung um drei Zeichen), als Cäsar-Verschlüsselung.
Da es nur 26 mögliche Schlüssel gibt, kann ein Angreifer natürlich recht schnell alle möglichen
Verschiebungen durchprobieren und so den Klartext finden. Bei längerem Text ist es sogar sehr wahrscheinlich,
dass der häufigste Geheimbuchstabe für das Klartext-'e' steht -- den mit Abstand häufigsten Buchstaben
in normalem deutschem Text. Damit kann man die Verschiebung sogar ohne Durchprobieren anderer Schlüssel sofort
erkennen und den Geheimtext ganz schnell entschlüsseln. Das Verfahren bietet also nur eine sehr geringe
Sicherheit.
Das nachfolgende Beispiel wurde durch Verschiebung um 7 Zeichen verschlüsselt; der im Geheimtext häufigste
Buchstabe 'l' entspricht dem Klartext-'e', woraus sich die Verschiebung 7 leicht erschließen lässt.
Die Programmierung des Cäsar-Verfahrens ist nicht sonderlich schwer. Und zum Entschlüsseln wird einfach die Verschiebungsrichtung umgekehrt:
| public class CryptoCaesar implements CryptoAction { // R. Krell für Webseite www.r-krell.de/if-java-j.htm, 16.1.2011 public String verschlüssele (String klartext, String zusatz) { String geheimtext = ""; int verschiebung = Integer.parseInt (zusatz); char bst; int nr; klartext = klartext.toUpperCase(); for (int i=0; i < klartext.length(); i++) { bst = klartext.charAt(i); // bst ist der Buchstabe an/von i-ter Stelle des Klartextes nr = (int)bst-(int)'A'; // nr ist die zu bst gehörende Nummer, A=0, B=1, C=2, .. Z=25 (für %) if (bst >='A' && bst<='Z') // Nur echte Buchstaben werden chiffriert; Rest nicht { nr = (nr + verschiebung + 26) % 26; // +26 wegen %-Problemen mit negativen Zahlen; } // % 26, weil vorn rausgeschobener Geheimalphabet-Teil hinten angehängt wird geheimtext = geheimtext + (char)(nr + (int)'A'); // Rückverwandl. in ASCII-Nummer bzw. in ein Schriftzeichen } return (geheimtext); } public String entschlüssele (String geheimtext, String zusatz) { return (verschlüssele (geheimtext, "-"+zusatz)); // Minuszeichen für Verschiebung in Gegenrichtung } } |
In den 1990er Jahren wurde eine Zeit lang die Cäsar-Verschiebung um 13 Zeichen unter der Bezeichnung ROT-13 als einfache e-Mail-Verschlüsselung verwendet: Vorteil des Verfahrens ist, dass bei insgesamt 26 Buchstaben des Alphabets die erneute Verschiebung um 13 Zeichen wieder zum Klartext führt, d.h. Ver- und Entschlüsselung mit der gleichen Methode (ohne Vorzeichenänderung) ausgeführt werden konnten. Nachteil ist die sehr geringe Sicherheit, da Verfahren und Schlüssel allgemein bekannt waren (und ROT-13 auch sonst wie jede Cäsar-Chiffrierung schnell durch einen brute-force-Angriff oder mit einer Häufigkeitsanalyse knackbar ist). Der Name ROT-13 kommt von 'rotation', weil die bei der Verschiebung vorne heraus geschobenen 13 Zeichen des Geheimalphabets hinten wieder rein kommen.
zum Seitenanfang / zum Seitenende
2c) Monoalphabetische Substitution mit Verwirbelung des Alphabets
Damit nach der Entdeckung des einen häufigsten Buchstabens nicht sofort -- wie beim Cäsar-Verfahren -- der ganze Geheimtext entschlüsselt werden kann, bietet sich an, das Alphabet nicht einfach zu verschieben, sondern außerdem die Reihenfolge der Buchstaben im Geheim-Alphabet zu ändern. Damit sich Sender und Empfänger die vereinbarte Reihenfolge merken können, verwendet man gerne ein leicht merkbares bedeutungshaltiges Wort wie etwa 'Informatiktest'. Die Buchstaben des Merkworts werden (ohne Doppelungen) an den Anfang des Geheimalphabets geschrieben; danach werden die restlichen, unverbrauchten Geheimbuchstaben in der natürlichen Reihenfolge aufgefüllt. Deshalb empfiehlt sich, im Merkwort auch Buchstaben vom Ende des Alphabets zu verwenden -- sonst erscheinen zu viele hintere Buchstaben unverschlüsselt!
Wegen der sehr vielen 26! = 4 * 1026 Möglichkeiten, die 26 Buchstaben des Alphabets verschieden anzuordnen, ist ein Brute-Force-Angriff zum Durchprobieren aller möglichen Schlüssel hier um sehr viele Größenordnungen aufwändiger als beim einfachen Cäsarverfahren und praktisch unmöglich: Selbst ein Computer, der pro Sekunde 10 Millionen verschiedene Geheimalphabet-Anordnungen ausprobieren und prüfen könnte, bräuchte zum Durchspielen aller Möglichkeiten 1,3 * 1012 Jahre -- das wäre noch knapp das 100-fache des Alters unseres Universums! Trotzdem ist das Verfahren -- wie auch jede andere monoalphabetische Chiffrierung, wo jeder Klartextbuchstabe immer durch den gleichen Geheimtextbuchtaben oder das gleiche Geheimzeichen verschlüsselt wird -- keineswegs sicher: Bei längerem Text kann relativ leicht über eine Häufigkeitsanalyse die Klartext-Entsprechung der meisten Geheim-Buchstaben herausgefunden werden und der Rest wird dann durch Probieren oder wegen häufiger Buchstabenkombination gefunden -- ohne dass man das Merkwort bzw. den Schlüssel braucht. Die Sicherheit eines Verfahrens hängt also nicht von der Vielzahl möglicher Schlüssel ab, wenn es andere effektive Angriffsmethoden gibt!
Auch der Computer muss zuerst das Geheim-Alphabet erzeugen, bevor das Verschlüsseln möglich ist. Zum effektiven Entschlüsseln werden die Buchstabenpaare besser zuvor nach den Geheimbuchstaben sortiert bzw. wird ein passendes KlarABC direkt zusammen mit dem GeheimABC erzeugt (hier nicht gezeigt):
| public class CryptoMerkwort implements CryptoAction { // R. Krell für Webseite www.r-krell.de/if-java-j.htm, 16.1.2011 char[] geheimABC = new char[26]; // ärgerlicherweise kann in Java eine Reihung nicht durch .. // .. Buchstaben indiziert werden, sondern Index fängt immer mit der Zahl 0 an private void erzeugeGeheimABC (String kennwort) // erzeugt das Geheimtextalphabet { boolean[] verwendet = new boolean[27]; // damit jeder Buchstabe nur einmal vorkommt for (int i=0; i<26; i++) { verwendet[i] = false; } kennwort = kennwort.toUpperCase(); char bst; int nr; int i = 0; // aktuelle Position im Geheimalphabet for (int pos=0; pos<kennwort.length()&&i<26; pos++) { bst = kennwort.charAt(pos); // Buchstabe bst von der Stelle pos im Merkwort nr = (int)bst - (int)'A'; // Zu bst gehörige nr für den Reihungs-Index; A=0, B=1, C=2, .. , Z=25 if (nr>=0 && nr<26 && !verwendet[nr]) // nur echte Buchstaben, keine Doppelungen/Mehrfachverwendung gleicher Buchstaben { geheimABC[i] = bst; // Füllt bst an aktuelle Stelle ins Geheimalphabet verwendet[nr] = true; // Merkt sich, dass bst bzw. nr verwendet wurde i++; } } for (bst='A'; bst<'Z'; bst++) // füllt Geheimalphabet mit restl. Buchstaben auf { if (!verwendet[nr]) // nur alle bisher nicht verwendeten Buchstaben { geheimABC[i] = bst; i++; } } } public String verschlüssele (String klartext, String zusatz) { erzeugeGeheimABC(zusatz); // Erzeugen des Geheimalphabets, s.o. klartext = klartext.toUpperCase(); String geheimtext = ""; char bst; for (int i=0; i < klartext.length(); i++) { bst = klartext.charAt(i); if (bst >='A' && bst<='Z') // nur echte Buchstaben chiffrieren { geheimtext = geheimtext + geheimABC[(int)bst-(int)'A']; } else geheimtext = geheimtext + bst; } return (geheimtext); } |
Tabellen mit Angaben über die typischen Buchstabenhäufigkeiten finden sich z.B. bei
zum Seitenanfang / zum Seitenende
2d) Vigenère-Verfahren, Vernam, One-Time-Pad (polyalphabetische Substitution)
Um dem bei längeren monoalphabetisch chiffrierten Texten sehr leichten Angriff über die Häufigkeitsanalyse vorzubeugen, wurden in der Vergangenheit schon verschiedene Altenativen probiert: Durch zusätzliche Zeichen im Geheimalphabet hat man z.T. für die häufigsten Buchstaben weitere Übersetzungsmöglichkeiten bereit gestellt, sodass z.B. ein Klartext-'e' auf drei Arten chiffriert werden kann und keines dieser Geheim-Zeichen auffällig häufig ist. Oder man verschlüsselt nicht einzelne Buchstaben, sondern -- wie etwa beim Playfair-Verfahren -- immer Buchstabenpaare gemeinsam. Allerdings sind auch die Häufigkeiten von Buchstabenpaaren in normalen Texten leicht zu ermitteln und bekannt (siehe Verweise am Ende des vorigen Abschnitts 2c)) und die Zahl von maximal 262 = 676 theoretisch möglichen Buchstabenpaaren (von denen längst nicht alle wirklich in der deutschen Sprache vorkommen) ist bei weitem nicht groß genug, um einem computergestützten Angriff länger als ein paar Sekunden(-bruchteile) zu widerstehen.
Größere Sicherheit bieten nur Verfahren, wo jeder Klartext-Buchstaben nicht immer mit dem gleichen Buchstaben des Geheimalphabets, sondern immer wieder anders chiffriert wird. Dadurch werden Häufigkeitsunterschiede verwischt: Wenn mal das Klartext-'e' durch das Geheimtext-'m' chiffriert wird und ein paar Zeichen später das seltene Klartext-'q' wieder zu 'm' wird, hat am Ende das 'm' -- und idealerweise auch jeder andere Geheimtextbuchstabe -- eine fast gleiche, mittlere Häufigkeit, die keine Rückschlüsse mehr auf den Klartext zulässt. Das bedeutendste und bekannteste dieser so genannten polyalphabetischen Chiffrier-Verfahren ist das Vigenère-Verfahren.
Wird wieder die Klartext-Nachricht "Ein Beispiel" etwa mit dem Schlüsselwort "Geld" nach Vigenère verschlüsselt, so wird das Schlüsselwort wiederholt über die Nachricht geschrieben und jeder Klartext-Buchstabe gerade durch seine Entsprechung aus dem Geheimalphabet chiffriert, das mit dem Buchstaben des Schlüsselworts anfängt. Der vorderste, 0-te Buchstabe 'E' wird also mit dem G-Alphabet, der nächste Buchstabe 'i' mit dem E-Alphabet, dann das 'n' mit dem L-Alphabet usw. verschlüsselt. Das Klaralphabet (und gleichzeitig auch das Geheimalphabet bei einem 'A' im Schlüsselwort) ist das oberste, das A-Alphabet im Vigenère-Quadrat.
Das ist leicht programmiert:
| public class CryptoVigenere implements CryptoAction // R.
Krell für Webseite www.r-krell.de/if-java-j.htm, 18.1.2011 // hier wird das Schlüsselwort auch über Leer- und Satzzeichen geschrieben! { public String verschlüssele (String klartext, String zusatz) { String kennwort = zusatz.toUpperCase(); // Keine Kontrolle der Eingabe: darf nur Buchstaben enthalten char bst; // für Klartext-Buchstaben int k = 0; // Index k geht Buchstaben des Kenn- bzw. Schlüsselworts durch String ausgabe = ""; // Hier wird die Ausgabe der erzeugte Geheimtext for (int i=0; i < klartext.length(); i++) { bst = klartext.charAt(i); if (bst >='A' && bst<='Z') // Nur echte Buchstaben chiffrieren { ausgabe = ausgabe + (char)(((int)bst-(int)'A' + (int)kennwort.charAt(k)-(int)'A')%26 + (int)'A'); } else ausgabe = ausgabe + bst; // Andere Zeichen (z.B. Leerzeichen) unverändert übernehmen k = (k+1) % kennwort.length(); // Kenn-(=Schlüssel-)wort ggf. wiederholen } return (ausgabe); } public String entschlüssele (String geheimtext, String zusatz) { // Wie Verschlüsseln, nur mit - statt + bei Verschiebung String kennwort = zusatz.toUpperCase(); char bst; int k = 0; String ausgabe = ""; for (int i=0; i < geheimtext.length(); i++) { bst = geheimtext.charAt(i); if (bst >='A' && bst<='Z') { ausgabe = ausgabe + (char)(((int)bst-(int)'A' - (int)kennwort.charAt(k)+(int)'A' + 26)%26 + (int)'A'); } // +26, um nicht den Rest von einer negativen Zahl ermitteln zu müssen else ausgabe = ausgabe + bst; k = (k+1) % kennwort.length(); } return (ausgabe); } } |
Wer nicht selbst programmieren will und auch nicht mein Applet benutzen möchte, findet übrigens einen schönen und fertig nutzbaren "Vigenerizer" auf http://einklich.net/etc/vigenere.htm. Dort sind Ver- und Entschlüsselung in Javascript programmiert; außerdem erhält man viele weitere Informationen zum Vigenère-Verfahren.
Jahrhundertelang galt das Vigenère-Verfahren als sicher. Seit 150 Jahren weiß man allerdings, dass die Wiederholung des Schlüsselworts Gefahren birgt: Bei einem vierstelligen Schlüsselwort (wie im oben gezeigten Beispiel mit dem Schlüsselwort GELD) ist jeder vierte Buchstabe monoalphabetisch mit dem gleichen Geheim-Alphabet verschlüsselt: Der 0., 4., 8. .. Buchstabe ist mit dem G-Alphabet, der 1., 5., 9. .. Buchstabe ist mit dem E-Alphabet, das 2., 6., 10. .. Zeichen mit dem L-Alphabet chiffriert, usw. Entsprechend existieren doch Angriffsmöglichkeiten, die ein Arbeitsblatt aus meinem Unterricht erläutert bzw. an Hand entsprechender Aufgaben nachvollziehen lässt. Auf dem Blatt werden u.a. zwei Versionen des Kasiski-Tests sowie eine Friedman-Formel zur Bestimmung der Schlüsselwortlänge vorgestellt:
Und weil meine Schülerinnen und Schüler
zusätzlich zur vorgeführten Übung auf dem Arbeitsblatt den Angriff auf das traditionelle
Vigenère-Verfahren mit kurzem, sich wiederholenden Schlüssel gerne noch an weiteren Geheimtexten
ausprobieren wollten, habe ich noch ein Java-Applet geschrieben, das die auf dem Blatt beschriebenen Schritte --
1) Erstellung eines Vigenère-Geheimtextes, 2) Analyse des Geheimtextes nach Kasiski und Friedman zur
Bestimmung der Schlüssellänge n und 3) Zerlegen des Geheimtextes in n Teiltexte zur
Häufigkeitsanalyse -- ausführt und so die Erstellung weiterer Aufgaben vereinfacht. Auch fremder Geheimtext
kann eingegeben und analysiert werden; zum Schluss kann er mit dem vermuteten Schlüssel dechiffriert werden:
Die einzig wirklich sichere Verschlüsselungs-Möglichkeit nach Vigenère besteht darin, ein Schlüsselwort zu nehmen,
Einen solchen einmaligen, langen Zufallsschlüssel nennt man One-Time-Pad (OTP; Einmalblock -- weil solche Schlüssel auf die Blätter eines Blocks geschrieben und nach Benutzung abgerissen und vernichtet werden mussten). Tatsächlich ist das Vigènere-Verfahren mit OTP nicht nur wirklich sicher, sondern sogar das einzige beweisbar sichere Verschlüsselungsverfahren überhaupt: Wegen der Zufälligkeit des Schlüssels liefert ein Brute-Force-Angriff (mit dem Durchspielen aller möglichen Schlüsselwörter) alle möglichen Klartexte gleicher Länge -- die meisten bestehen zwar nur aus sinnlosem Buchstabensalat, aber es wird auch sehr viele sinnhaltige Texte geben, von denen sich aber keiner auszeichnet, sodass die echte Klarnachricht in vielen gleich-langen anderen möglichen Botschaften versteckt bleibt.
Ob man den Geheimtext beim Vigenère-Verfahren wie hier als Buchstabenfolge angibt, oder ob man die Zeichen vorher in Zahlen umwandelt und vielleicht auch das Schlüsselwort nicht mit Buchstaben, sondern z.B. als Zahlenwurm notiert und die Verschiebung durch Rechenoperation ersetzt (beliebt: Addition ohne Zehnerübertrag oder -- bei Dualdarstellung der Zahlen -- bitweises XOR), ist für die Sicherheit des Verfahrens ohne Bedeutung. Letztlich handelt es sich nur um verschiedene Darstellungsformen der gleichen Idee der polyalphabetischen Verschlüsselung. Die Variante mit (Dual-)Zahlen wird in manchen Büchern als Vernam-Verfahren bezeichnet, während bei anderen Autoren die Vigenère-Verschlüsslung mit einem Schlüssel, der mindestens die Textlänge hat, als Vernam-Verfahren bezeichnet wird. Ist im letzten Fall der Schlüssel beispielsweise der Text aus einem allgemein zugänglichen Buch (oder auch der an einen kurzen Anfangs-Schlüssel angehängte Klartext) bzw. irgendein Text in einer natürlichen Sprache, so ist das Verfahren wegen der Regelmäßigkeiten dieser Sprache doch wieder angreifbar und erreicht nicht die Sicherheit des zufälligen OTP-Verfahrens.
Und letztlich steckt die Idee von Vigenère mit OTP auch in Verschlüsselungsmaschinen wie etwa der Enigma: Hier wurde das lange zufällige OTP-Schlüsselwort während des Chiffrierens durch Drehung von Walzen erzeugt, deren komplizierte Verdrahtung dann pseudo-zufällige Folge-Drehungen bzw. die Chiffrierung mit jeweils pseudo-zufälliger Verschiebung erzeugte. Statt den gesamten langen Schlüssel geheim zu übermitteln, brauchte dann nur die Anfangsstellung der Walzen mitgeteilt werden, wenn der Empfänger mit seiner Maschine aus diesen Anfangswerten die gleichen pseudo-zufälligen Drehungen erzeugen konnte. Die Mitteilung der Anfangswerte, die ebenfalls verschlüsselt, aber leider doppelt erfolgte, bot allein durch die Wiederholung letztlich erfolgreich genutzte Angriffsmöglichkeiten, während der Unterschied der Pseudo-Zufallsfolge von echten zufälligen Zahlen offenbar so gering war, dass er während des Zweiten Weltkrieges nicht zur Analyse benutzt werden konnte.
zum Seitenanfang / zum Seitenende
Interaktives Applet zu 2a) bis 2d)
Das zu Beginn des 2. Kapitels, noch vor dem Abschnitt 2a) gezeigte Applet kann auf einer Sonderseite gestartet und ausprobiert werden: Es verbindet die vorstehenden Programmtexte unter einer Oberfläche:
Kryptografie-Applet auf Extra-Seite starten
zum Seitenanfang / zum Seitenende
3. Geheimnisaustausch ohne Weitergabe eines Schlüssels
Bis in die 1970er Jahre hielt man es für selbstverständlich, dass der rechtmäßige Empfänger einer verschlüsselten Nachricht in den Besitz des Schlüssels kommen muss, um den Geheimtext entschlüsseln zu können. Bei den vorstehend beschriebenen, deswegen als symmetrisch bezeichneten Verfahren, wird ja zum Entschlüsseln genau der gleiche Schlüssel gebraucht wie zum Verschlüsseln. Der Schlüssel muss über einen sicheren Kanal übermittelt werden. Werden One-Time-Pads benutzt, so muss für jede Kommunikation ein einmaliger, nicht wieder zu verwendender langer Schlüssel zufällig erzeugt und sicher ausgetauscht werden.
Nimmt man allerdings ein mehrfaches Hin- und Herschicken in Kauf, können Botschaften verschlüsselt ausgetauscht werden, ohne dass auch der Schlüssel weitergegeben werden muss! Möchte A eine Nachricht an B schicken, die Dritte nicht mitlesen können, kann dies wie folgt geschehen:
Voraussetzung für das Funktionieren des Verfahrens ist allerdings der Einsatz von Verschlüsselungsverfahren, bei denen nach Vertauschen der Entschlüsselungsreihenfolge immer noch der gleiche Text heraus kommt, d.h. wo vB-1(G3) = vB-1(vA-1(G2)) = vB-1(vA-1(vB(G1) = vB-1(vA-1(vB(vA(K)))) = K ist. Dazu muss vB-1(vA-1(vB(vA(K)))) = (vB-1 o vA-1 o vB o vA)(K) = (vB-1 o vB o vA-1 o vA)(K) = (id o id)(K) = K gelten, also vA-1 o vB kommutativ sein (o bezeichne die Hintereinanderausführung [Komposition] von Funktionen; id die identische Funktion id(x) = x. Mit v wird die Verschlüsselung bzw. mit v-1 die Entschlüsselung durch A bzw. B notiert). Dies geht mit Cäsar und Vigenère, aber nicht mit Playfair oder der monoalphabetischen Verschlüsselung mit Merkwort! Das Verfahren scheint so sicher wie die eingesetzten Verschlüsselungsverfahren, da ja nie der unverschlüsselte Klartext versandt wird. Ein Angreifer, der den vollständigen Nachrichtenverkehr zwischen A und B abhört, kann allerdings aus dem Vergleich von G1 und G2 möglicherweise den Schlüssel von B bestimmen und damit dann auch selbst G3 entschlüsseln. Außerdem können A und B jeweils durch Vergleich ihrer eigenen und der zurückgeschickten Nachrichten den Schlüssel des anderen ermitteln, sodass A und B ihre privaten Schlüssel immer nur einmal verwenden können. Höhere Sicherheit bieten daher nur Verfahren, wo der Vorher-/Nachher-Vergleich anders als bei den oben vorgestellten Verfahren keine Berechnung des verwendeten Schlüssels zulässt. Entsprechende Einweg-Funktionen, etwa Potenzieren mit einem Modulus, werden im nächsten Kapitel (auf der Seite if-java-k) besprochen. Mit einer solchen Funktion ist der hier vorgestellte Geheimnisaustausch ohne Preisgabe des Schlüssels auch als Shamir's No-Key-Algorithm bekannt. Die versandte Datenmenge ist allerdings dreimal so groß wie die eigentliche Nachricht K, da statt dessen ja G1, G2 und G3 übermittelt werden. Auch der Ver- und Entschlüsselungsaufwand ist wegen der Vielzahl der nötigen Umwandlungen dreimal so hoch.
zum Seitenanfang / zum Seitenende
Auf der nächsten Seite "Informatik mit Java, Teil k): Kryptologie II" folgen die Schlüsselvereinbarung nach Diffie, Hellman und Merkle, das RSA-Verfahren und Ausführungen zur elektronischen Signatur (mit Hashwerten und dem RSA-Verfahren):
weiter zur nächsten Seite Kryptologie II
zurück zur Informatik-Hauptseite
(Die anderen Java-Seiten werden am besten auf der Informatik-Hauptseite ausgewählt)