02 März 2014 ~ 8 Kommentare

Vigenère Chiffre in Java: Einfache Verschlüsselung mit Key und Zeichenverschiebung

vigenere_verschluesselung_chiffre_java

Kürzlich hatte ich ja bereits in diesem Beitrag die ganz einfache Caesar Verschlüsselung in Java umgesetzt. Um den “Schwierigkeitsgrad” noch etwas zu erhöhen, war es also nur logisch, sich der nächsten Stufe in der Liste der Verschlüsselungsmethoden anzunehmen, der Vigenère Chiffre. Bei der simplen Caesarmethode haben wir einfach einen Text genommen und alle Zeichen darin um x verschoben (aus einem A wird C, aus einem B ein D bei der Verschiebung um 2 Stellen, und so weiter). Vigenère geht da noch einen Schritt weiter, hier kommt nun auch ein geheimer Key zum Einsatz, anhand dessen verschlüsselt wird, d.h. dass nicht alle Zeichen eines Textes parallel gleich verschoben werden, sondern je nach Schlüssel ganz unterschiedlich. Das Grundprinzip, wie man es von der Caesar Verschlüsselung kennt, bleibt aber gleich.

Zunächst ein kleines Beispiel zur Verdeutlichung: Der Einfachheit halber stellen wir uns dafür ein Alphabet von A bis Z in Großbuchstaben vor und tun für unser Beispiel so, als gäbe es auch nur diese 26 Zeichen, also keine Sonderzeichen, Ziffern oder Kleinbuchstaben. A wäre der erste Buchstabe, Z der 26ste. Nun möchten wir das Wort PROGRAMMIEREN verschlüsseln. Als Key bzw. Schlüssel wählen wir die Zeichenfolge ABC. Wie bei Caesar werden die Buchstaben nun also verschoben, diesmal aber nicht alle gleich, sondern vom Schlüssel abhängig:

PROGRAMMIEREN mit dem Key ABC verschlüsseln:

PROGRAMMIEREN (unser Plaintext)
ABCABCABCABCA (der Key, fortlaufend)
QTRHTDNOLFTHO (das verschlüsselte Resultat daraus)

Und jetzt Schritt-für-Schritt erklärt:

P um A verschieben: Also P um eine Stelle verschieben (A ist der erste Buchstabe im Alphabet). Ergibt Q.

R um B verschieben: R um zwei Stellen verschieben (B ist der zweite Buchstabe). Ergibt T.
O um C verschieben: O um drei Stellen verschieben (C ist der dritte Buchstabe). Ergibt R.

Nun sind wir mit unserem Schlüssel durch, daher fängt man wieder an dessen Start an, verschiebt den nächsten Buchstaben also wieder um A, dann B, C und kommt wieder zurück zu A und so weiter:

G wieder um A verschieben: Ergibt H.
R wieder um B verschieben: Ergibt T.
A wieder um C verschieben: Ergibt D.

Ergibt am Ende QTRHTDNOLFTHO, sollte ich keinen Fehler gemacht haben, da ich das selbst auch nur im Kopf durchgeführt habe.

Anmerkung: Das Beispiel sollte einfach nur anschaulich sein. Man könnte ebenso definieren, dass ein A um null Stellen verschiebt, ein B um eine Stelle und so weiter.

Wie man sieht, ist es schon viel ausgefeilter als die einfache Caesar Chiffre, die jeden Buchstaben gleich verschlüsselt / verschiebt. Umso länger der Schlüssel, umso sicherer die Verschlüsselung. Theoretisch könnte man einen Schlüssel wählen, der genau so lange wie der zu verschlüsselnde Text ist, was die Sicherheit weiter erhöht.

Aber Vorsicht: Echte Sicherheit bietet die Vigenère Verschlüsselung nicht wirklich im Vergleich zu heutigen komplexen Verschlüsselungsverfahren wie AES und anderen. Es ist eher ein schönes anschauliches Beispiel zum Herumspielen mit grundsätzlichen Prinzipien von Verschlüsselung und keinesfalls produktiv zu nutzen! Denn z.B. mit einer Häufigkeitsanalyse lässt sich effektiv diese Verschlüsselung brechen bzw. auf den Schlüssel kommen. Dabei geht man davon aus, dass bestimmte Buchstaben(kombinationen) in unserer Sprache eben ganz natürlich häufiger vorkommen, als andere. Analysiert man einen Text auf bestimmte Redundanzen, kann man irgendwann auf den Schlüssel kommen. Auch kann man z.B. einen Text, bestehend aus nur einem Buchstaben in fortlaufender Wiederholung, verschlüsseln und kann somit den Schlüssel rückrechnen.

Beispiel:

Text AAAAAAAA, Key ABCD

Ergibt verschlüsselt BCDEBCDE.

Schon hat man die Länge des Schlüssels erkannt und auch seinen Inhalt, da man sieht wie weit verschoben wurde.

So, jetzt aber zu einer Java Implementierung des Ganzen. Ich habe mir diesmal etwas mehr Mühe gegeben als beim Caesar, den Code weniger redundant auszulegen und habe sowohl Ver- als auch Entschlüsselung in eine einzige Methode namens crypt() gepackt. Wie man sieht ist diese auch nicht besonders lange. Man übergibt der Methode das Char Array plain, dies ist der zu ver/entschlüsselnde Text. Desweiteren das Char Array key, den Schlüssel, sowie die “Richtung”, in diesem Fall 1 wenn plain verschlüsselt werden soll, 0 wenn es entschlüsselt werden soll.

In einer Schleife wird nun jedes Zeichen durchgegangen und jeweils um die entsprechende Stelle des Keys verschoben. Ist der Key an seinem Ende angelangt, wird wieder mit dessen Anfang begonnen, das stellt man durch “Key MODULO Keylänge” (im Quelltext key[i % key.length]) sicher. Da ich hier wieder mit der kompletten ASCII Tabelle arbeite, wird das Ergebnis nochmals MODULO 128 gerechnet, wie beim Caesar schon, was der Anzahl der Zeichen der ASCII Tabelle entspricht. Dabei geht es einfach nur darum, dass man ein Zeichen ja soweit verschieben könnte, dass es danach z.B. an der Stelle 150 der Zeichentabelle stünde. Da unsere ASCII Tabelle aber nur 128 Stellen hat, wollen wir einfach wieder von vorne beginnen. 150 MODULO 128 ergibt 22, wir fallen also quasi “hinten über und laufen bei 1 weiter” – oder korrekterweise natürlich bei 0, da wir ja in Informatikertermen denken müssen. (150 MODULO 128, sprich “welcher Rest bleibt, wenn man 150 durch 128 teilt?”, das Ergebnis kann dabei nur zwischen 0 und 127 sein).

Hier nun mein Java Code, natürlich wie immer ohne Gewähr. In meinen Tests funktionierte alles wunderbar, man darf nur eben keine deutschen Umlaute verwenden, weil diese naturgemäß mit dem 7 Bit ASCII nicht so gut harmonieren 😉

public class Vigenere {

	public static char[] crypt(char[] plain, char[] key, int richtung) {

		char[] output = new char[plain.length];

		for (int i = 0; i < plain.length; i++) {

			if (richtung == 1) {
				int result = (plain[i] + key[i % key.length]) % 128;
				output[i] = (char) result;
			}
			else if (richtung == 0){
				int result;
				if (plain[i] - key[i % key.length] < 0) result = 
						(plain[i] - key[i % key.length]) + 128;
				else result = (plain[i] - key[i % key.length]) % 128;
				output[i] = (char) result;

			}
		}

		return output;

	}

	public static void main(String[] args)  {

		Scanner scanner = new Scanner(System.in);

		System.out.println("Zu verschlüsselnden Text eingeben:");

		String plaintext = scanner.nextLine();
		// Zu verschlüsselnden Text einlesen
		// ä,ö,ü funktionieren NICHT richtig!

		char[] plain = plaintext.toCharArray();
		// .. diesen in char Array laden

		System.out.println("Key zum verschlüsseln eingeben:");

		String keytext = scanner.nextLine();
		char[] key = keytext.toCharArray();
		// das gleiche mit dem Key

		int richtung = 1; 
		// 1 = verschlüsseln, 0 = entschlüsseln

		char[] encrypted = crypt(plain, key, richtung);
		// verschlüsseln wir doch mal...

		System.out.println("Der Text sieht verschlüsselt so aus:");
		System.out.println(encrypted);
		//... und geben es aus

		richtung = 0;
		// auf entschlüsseln "umschalten"

		char[] decrypted = crypt(encrypted, key, richtung);
		// jetzt wieder entschlüsseln...

		System.out.println("Und zur Probe wieder zurückentschlüsselt:");

		System.out.println(decrypted);
		// und schauen ob wieder der
		// eingegebene Text herauskommt

		scanner.close();

	}

}

Die Ausgabe des Programmes sieht beispielsweise so aus:

Zu verschlüsselnden Text eingeben:
Hallo Welt!
Key zum verschlüsseln eingeben:
xM7c
Der Text sieht verschlüsselt so aus:
@.#OgmHdAX
Und zur Probe wieder zurückentschlüsselt:
Hallo Welt!

Ich hoffe, der eine oder andere Java-Lernende kann mit meinen Ausführungen und der Erklärung dazu etwas anfangen. Wer weiß, vielleicht wäre das ja mal eine schöne Programmieren-Klausuraufgabe 😉 Rückblickend auf meine Programmieren I Klausur würde das Niveau grob hinkommen, jedenfalls gab es im vergangenen Jahr immerhin “den Caesar” zu lösen.

greg

Blogger bei kleingebloggt
Servus! Mein Name ist Michael Gregor, ich bin E-Commerce Student an der FHWS, Blogger, Webworker und schon IT-Geek seit ich 1994 meinen ersten 386er hatte 🙂

8 Kommentare zu “Vigenère Chiffre in Java: Einfache Verschlüsselung mit Key und Zeichenverschiebung”

  1. Vince 10 März 2014 at 19:28 Permalink

    Hey hey, nicht schlecht soweit. Deutliche Verbesserung 🙂 Drei kleine Anmerkungen zu deinem Java-Code:

    Du könntest dir das äußere IF sogar sparen, wenn du die Richtung mathematisch in deine Formel einbaust, statt sie nur als Pseudo-Boolean zu verwenden, dann wäre Integer nämlich auch sinnvoll. Also der Faktor +1 für vorwärts, -1 für rückwärts:

    int offset = (plain[i] + (key[i % key.length]) * richtung) % 128;
    output[i] = (char) offset;

    Wofür du das andere IF im Rückwärtsfall brauchst, will sich mir auch nicht erschließen. Normalerweise klappt die Modulo-Operation in beide Richtungen. Das heißt, wenn du mal unter 0 rauskommst, kippt die Zahl und du landest wieder im oberen Zahlenbereich. Wenn du es richtig anstellst, brauchst du beide IFs nicht.

    Du nennst deine Variable “offset”, aber semantisch ist es keiner. Bei dir ist es der Ergebniswert, also würde ich die Variable “result” nennen.

  2. greg 10 März 2014 at 20:01 Permalink

    Danke für deine Anmerkungen, vorallem das mit dem “offset” werde ich einarbeiten. Die Namensgebung war noch ein Relikt aus meinen ersten Ansatzen mit dem Caesar 🙂

    Um die zwei IFs scheint man aber dennoch nicht herumzukommen. Bei deinem Ansatz funktioniert zwar die Ver-, nicht aber die Entschlüsselung korrekt, da der Modulo sich in Java bei negativen Zahlen nicht korrekt verhält. So ist 10 Modulo 3 = 1, aber -10 Modulo 3 = -1 unter Java, richtig wäre jedoch = 2. Probiere es mal auszuführen, wie du vorgeschlagen hast, es kommt nicht mehr der Ursprungstext heraus. Daher frage ich ab, ob ich bei der Zurückverschiebung, die ja eine negative Operation ist, unter Null komme und addiere in diesem Fall wieder die 128 hinzu.

    Vielleicht täusche ich mich aber auch und du hast uneingeschränkt recht – manchmal übersieht man einfach etwas und fühlt sich selbst weiterhin im Recht. In diesem Fall müsstest du mich daher nochmals genauer darauf stoßen, da mir meine Ausführungen soweit schlüssig erscheinen.

  3. Vince 10 März 2014 at 22:14 Permalink

    “da mir meine Ausführungen soweit schlüssig erscheinen” … pöh

    Ein bisschen Initiative könntest du ruhig zeigen 😉 Du hast Recht, der Java-Modulo ist ein bisschen zickig, aber mit einem kleinen Kniff lässt sich das leicht umgehen. Die IFs lassen sich beide problemlos weglassen:

    So sieht deine neue crypt()-Methode aus:

    public static char[] crypt(char[] plain, char[] key, int richtung) {

    char[] output = new char[plain.length];

    for (int i = 0; i < plain.length; i++) {

    int result = (plain[i] + (key[i % key.length] * richtung) +128) % 128;
    output[i] = (char) result;

    }

    return output;

    }

  4. Vince 10 März 2014 at 22:19 Permalink

    Kann man seine Beiträge hier nicht mehr editieren? Hmm.

    Wollte noch ergänzen, dass mir deine Version besser gefällt, weil du sie selbst ausgetüftelt hast. Das ist 10 mal mehr Wert als jede noch so optimierte Version 🙂

  5. greg 10 März 2014 at 22:29 Permalink

    “pöh”? Ach, du wirst mich schon richtig verstanden haben 😛 Das ist genau das, was ich meinte. Ich habe herumprobiert, bin aber vorhin nicht auf die einfache Lösung gekommen, die 128 direkt grundsätzlich hinzu zu addieren. Ich hatte zwar schon so eine Ahnung, dass ich derjenige sein muss, der sich täuscht – was aufgrund deines großen Wissensvorsprungs auf dem Gebiet einfach logisch war – aber insgeheim dennoch gehofft, dass du dir einen Lapsus erlaubt hast 😉

    Ohne Frage ist deine Variante damit die elegantere. Ich denke, ich lasse meine Version aber erstmal oben so stehen (korrekt ist sie ja auch), deine Verbesserungen daran sind ja hier in den Kommentaren gut sichtbar und durch die Diskussion auch gut nachvollziehbar. So hat jeder was davon.

  6. Vince 10 März 2014 at 22:47 Permalink

    Nein, stimmt schon, ich wusste nicht mehr wie der %-Operator sich im negativen Bereich verhält. Hab mich da getäuscht, so einfach ging es also doch nicht. Aber ich wusste immerhin noch, dass man das ganz leicht korrigieren kann. Jetzt hatte ich wenigstens mal wieder einen Grund, Eclipse zu starten.

    Wie schon gesagt, aus autodidaktischer Sicht ist deine Lösung sinnvoller. Bin schon gespannt was als nächstes kommt 😉

  7. greg 10 März 2014 at 22:58 Permalink

    Na, dann haben wir am Ende möglicherweise ja sogar beide ein wenig dazugelernt oder zumindest aufgefrischt in deinem Fall 😉

    Sehen wir mal, was mir als nächstes einfällt, das neue Semester wird aber sicher von alleine einiges mitbringen 🙂

  8. OsG 16 September 2014 at 09:14 Permalink

    Joooo ,lääuft bei dir 😉


Hinterlasse einen Kommentar

Kommentare werden moderiert, es kann also etwas dauern, bis dein Kommenatar angezeigt wird.

RSS abonnieren
Twitter Profil