Donnerstag, 8. Januar 2009

 

Caesar-Verschlüsselung

Allgemeines

Erstellen Sie ein Projekt klasse-caesar-name, z.B. 2cd-caesar-mueller.

Schreiben Sie ein Programm zum Knacken einfacher Caesar-Chiffren (z.B. A->C, B->D, C->E,..., Y->A, Z->B).

Verschlüsseln: Der Klartext wird zunächst in Kleinbuchstaben umgewandelt, wobei alle Zeichen, die keine Buchstaben sind, entfernt werden. Dann wird der über die Kommandozeile angegebene Schlüssel Zeichen für Zeichen angewendet. Zum Schluss soll eine zufällige Auswahl an Buchstaben wieder in Großbuchstaben umgewandelt werden und Leerzeichen eingefügt werden.

Entschlüssen: Der verschlüsselte Text wird wieder komplett in Kleinbuchstaben umgewandelt, danach wird der Schlüssel auf der Kommandozeile genau umgekehrt zeichenweise angewendet.

In beiden Fällen wird der (de-)kodierte Text ausgegeben

Knacken des Codes: Folgendes Verfahren funktioniert nur bei längeren sinnvollen Texten. Ermittle die Häufigkeiten der Zeichen. Das häufigste Zeichen entspricht dem E (zweithäufigstes ist das A), d.h. der Schlüssel muss entsprechend angesetzt werden.


Aufgabe 1 – Caesar, readStream(), writeStream()

Erstellen Sie eine Klasse Caesar mit einem Konstruktor Caesar(int key). key ist der Schlüssel (Verschiebung der Zeichen für das De-/Kodieren.

public String readStream(BufferedReader in) liest bis zu EOF alles in einen String. Implementieren Sie die Methode möglichst effizient (Stichwort "Shlemiel the Paitner").

public void writeSream(PrintWriter out, String content) schreibt den gesamten String content auf den Stream out (Datei oder stdout).



Aufgabe 2 – prepare()

public String prepare(String content) entfernt aus content alle Zeichen, die nicht Buchstaben von A bis Z sind und wandelt alle verbleibenden Buchstaben in Kleinbuchstaben um.



Aufgabe 3 – crypt()

public String crypt(String content) verschlüsselt den Text content mit dem im Konstruktor angegebenen key.

Ist key == 0, so bleibt der Text wie er ist, bei key == 1, wird aus jedem A ein B, aus jedem B ein C usw. ist key == 10, so wird aus dem A ein K, aus dem B ein L usw. aus dem Z wird I.



Aufgabe 4 – disguise()

public String disguise(String content) verschleiert den Text durch zufälliges Einstreuen von Leerzeichen bzw. durch zufälliges Umwandlen in Großbuchstaben. Verwenden Sie die Hilfsmethode aus der Datei disguise (vgl. Hinweise).



Aufgabe 5 – decrypt()

public String decrypt(String content) entschlüsselt den Text content mit dem aus dem Konstruktor angegebenen key (bzw. dem aus Aufgabe 6 ermittelten key). Z.B. bei key == 3 wird aus einem A ein X, aus B ein Y, aus C ein Z, aus D ein A usw.



Aufgabe 6 – crack()

public String crack(String content) entschlüsselt den Text, indem das häufigste Zeichen ermittelt wird. Dieses Zeichen entspricht also statistisch gesehen dem E. Ist zum Beispiel das häufigste Zeichen ein K, so ist der Schlüssel key = K-E, also 6. Dann wird die Methode decrypt() verwendet, um den Text zu dekodieren.



Aufgabe 7 – main()

Erstellen Sie eine main()-Methode, sodass die Klasse als Programm verwendet werden kann.

Das Programm soll immer aus einer Datei lesen, die Ausgabe soll entweder auf stdout oder in eine Datei erfolgen.

Verschlüsseln bedeutet immer die Kombination prepare(), crypt() und disguise(), Entschlüsseln entsprechend prepare(), decrypt().

Aufruf: java Caesar [-h] key eingabedatei [ausgabedatei]

-h ... Hilfe ausgeben und Programm beenden

key ... besteht aus dem Zeichen c für crypt, d für decrypt und k für crack() sowie im Falle von c und d aus einer Zahl, welche die Verschiebung angibt.

eingabedatei ... aus dieser Datei wird gelesen

ausgabedatei ... in diese Datei wird geschrieben, wird sie nicht angegeben, so ist auf stdout auszugeben.

Aufrufbeispiele:

java Caesar -h ... gibt Hilfe aus

java Caesar c5 text geheim ... verschlüsselt den Text aus Datei text mit dem Schlüssel 5 und speichert das Ergebnis in Datei geheim.

java Caesar d5 geheim ... entschlüsselt die Datei geheim mit dem Schlüssel 5 und gibt das Ergebnis auf stdout aus.

java Caesar k geheim ... knackt die Datei geheim und gibt das (hoffentlich richtig entschlüsselte) Ergebnis auf stdout aus.


Lösungsansatz:

Zunächst ein Lösungsansatz für das Ver- und Entschlüsseln durch Erzeugung eines Strings mit dem verschobenen Alphabet. Dazu verwenden wir einen String zeichensatz, der alle gültigen Zeichen enthält (Kleinbuchstaben 'a' bis 'z'). Dann erzeugen wir mit dem Schlüssel einen String shiftText, der den um den Schlüssel verschobenen Zeichensatz enthält.

Beispiel für Schlüssel 3:
String text = "abcdefghijklmnopqrstuvw";
String shiftText = "defghijklmnopqrstuvwxyzabc"; // Schlüssel 3
Das Verschlüsseln (bzw. Entschlüsseln) funktioniert dann so:

public String crypt(String text) {
StringBuffer sb = new StringBuffer(text.length());
for (char c : text.toCharArray()) {
sb.append(shiftText.charAt(zeichensatz.indexOf(c)));
}
return sb.toString();
}

Der Index eines Zeichens wird mittels der Stringfunktion indexOf() im String zeichensatz ermittelt. Dieser Index ist dann das gesuchte (verschlüsselte) Zeichen in shiftText.

Eine Klasse Code, die obige Methode implementiert finden Sie im Anschluss, sie erfüllt noch nicht die gesamten Anforderungen der Aufgabe!

/**
* Code: code.Code.java
*
* 08.01.2009, Harald R. Haberstroh
*/

package code;

/**
* Caesarverschlüsselung.
*
* @author Harald R. Haberstroh (hp)
*
*/
public class Code {

private final String zeichensatz = "abcdefghijklmnopqrstuvwxyz"; // Zeichensatz
private String shiftText; // verschobener Zeichensatz

/**
* @param code
* Verschiebung des Alphabets
*/
public Code(int code) {
int len = zeichensatz.length();
StringBuffer sb = new StringBuffer(len);
if (code < 0) {
code += len;
}
for (int i = 0; i < len; i++) {
int idx = (i + code) % len;
sb.append(zeichensatz.charAt(idx));
}
shiftText = sb.toString();
}

/**
* verschlüsselt (entschlüsselt) Text mit gegebenen Code, indem Zeichenweise
* verschoben wird (Caesar-Code).
*
* @param text
* zu verschlüsselnder Text (nur Kleinbuchstaben ohne Umlaute und
* 'ß')
* @return verschlüsselter Text
*/
public String crypt(String text) {
StringBuffer sb = new StringBuffer(text.length());
for (char c : text.toCharArray()) {
sb.append(shiftText.charAt(zeichensatz.indexOf(c)));
}
return sb.toString();
}

/**
* vorbereiten des Texts, indem alles auf Kleinbuchstaben und nur mehr Zeichen
* aus Zeichensatz 'zeichensatz'.
*
* @param text
* Rohtext
* @return vorbereiteter Text
*/
public String prepare(String text) {
StringBuffer sb = new StringBuffer(text.length());
for (char c : text.toCharArray()) {
c = Character.toLowerCase(c);
if (zeichensatz.indexOf(c) >= 0) { // gültig
sb.append(c);
}
}
return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
Code code = new Code(3);
System.out.println(code.zeichensatz);
System.out.println(code.shiftText);
Code decode = new Code(-3);
String text = "Hallo, das ist streng geheim!";
String ctext = code.crypt(code.prepare(text));
System.out.println(ctext);
text = decode.crypt(ctext);
System.out.println(text);
}
}

Im folgenden finden Sie eine Lösung der gesamten Aufgabenstellung, wobei zum Ver-/Entschlüsseln jeweils ein Array als Kodierungstabelle verwendet wird. Der Index wird erzeugt, indem das Zeichen in einen int-Wert umgewandelt wird und davon der int-Wert vom 'a' abgezogen wird.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;

/**
* lehrer-caesar-haberstroh/.Caesar.java
* @author (c) 2008, Harald R. Haberstroh
* 16.12.2008
*/

/**
* @author Harald R. Haberstroh (hh)
*
*/
public class Caesar {
private int key;

/**
* default für's Knacken.
*/
public Caesar() {
key = 0;
}

/**
* @param key
*/
public Caesar(int key) {
this.key = key;
}

/**
* liest eine ganze Textdatei.
*
* @param in
* geöffneter BufferedReader (Inputstream)
* @return gelesener String
* @throws IOException
*/
public String readStream(BufferedReader in) throws IOException {
StringBuilder sb = new StringBuilder();
String line;
while ((line = in.readLine()) != null) {
sb.append(line);
sb.append("\n");
}
return sb.toString();
}

/**
* schreibt den String in Textdatei.
*
* @param out
* PrintStream zum Schreiben
* @param content
* Text zum Speichern
*/
public void writeStream(PrintWriter out, String content) {
out.write(content);
out.flush();
}

/**
* entfernt alles, was kein Buchstabe und macht die dann zu Kleinbuchstaben.
*
* @param content
* zu konvertierender Text
* @return konvertierter Text
*/
public String prepare(String content) {
StringBuilder sb = new StringBuilder();
for (char c : content.toCharArray()) {
if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z') {
sb.append(Character.toLowerCase(c));
}
}
return sb.toString();
}

/**
* veschlüsselt Text mit Caesar-Chiffre und key.
*
* @param content
* zu verschlüsselnder Text
* @return verschlüsselter Text
*/
public String crypt(String content) {
StringBuilder sb = new StringBuilder();
char[] table = new char[26];
for (int i = 0; i < table.length; i++) {
char cryptChar = (char)((int)'a' + (i + key) % table.length);
table[i] = cryptChar;
}
for (char c : content.toCharArray()) {
sb.append(table[(int)c - (int)'a']);
}
return sb.toString();
}

/**
* verschleiert Text, indem zufällige Groß-/Kleinschreibung verwendet wird und
* zufällig Leerzeichen eingefügt werden.
*
* @param content
* zu verschleiernder Text
* @return verschleierter Text
*/
public String disguise(String content) {
StringBuilder sb = new StringBuilder();
for (char c : content.toCharArray()) {
sb.append(disguise(c));
}
return sb.toString();
}

/**
* für's disguise, immer selbe Folge von Zufallszahlen.
*/
private Random rand = new Random(23);

/**
* @param c
* Zeichen
* @return zufällig Groß/Klein, zufällig Leerezichen dazu
*/
private String disguise(char c) {
if (rand.nextBoolean()) {
c = Character.toUpperCase(c);
}
if (rand.nextBoolean()) {
return Character.toString(c) + " ";
} else {
return Character.toString(c);
}
}

/**
* entschlüsseln mit Caesar-Chiffre.
*
* @param content
* zu entschlüsselnder Text.
* @return entschlüsselter Text
*/
public String decrypt(String content) {
StringBuilder sb = new StringBuilder();
char[] table = new char[26];
for (int i = 0; i < table.length; i++) {
int shift = (i - key) < 0 ? (i - key) + table.length : i - key;
char cryptChar = (char)((int)'a' + shift);
table[i] = cryptChar;
}
for (char c : content.toCharArray()) {
sb.append(table[(int)c - (int)'a']);
}
return sb.toString();
}

/**
* versucht den key zu finden, indem das häufigste Zeichen ermittelt wird,
* welches dem 'E' entspricht.
*
* @param content
* verschlüsselter Text
* @return hoffentlich Klartext
*/
public String crack(String content) {
int[] hauf = new int[26];
for (char c : content.toCharArray()) {
hauf[(int)c - (int)'a']++;
}
char e = 'e';
int max = 0;
for (int i = 0; i < hauf.length; i++) {
if (hauf[i] > max) {
max = hauf[i];
e = (char)((int)'a' + i);
}
}
key = (int)e - (int)'e';
System.out.println("key = " + key);
String ret = decrypt(content);
return ret;
}

/**
* Hilfe ausgeben
*/
private static void help() {
System.out
.println("Aufruf: java Crypt [-h] key eingabedatei [ausgabedatei]");
System.out
.println("key besteht aus Zeichen plus Zahl, c...crypt, d...decypt, "
+ "k...cracken");

}

/**
* @param args
* [-h] key eingabedatei [ausgabedatei]
*/
public static void main(String[] args) {
if (args.length >= 2) { // scheint OK
if (args[0].equals("-h")) {
help();
} else {
try {
BufferedReader in = new BufferedReader(new FileReader(args[1]));
PrintWriter out = new PrintWriter(System.out);
if (args.length == 3) {
out = new PrintWriter(args[2]);
}
Caesar caesar;
String eingabe;
String ausgabe;
switch (args[0].charAt(0)) {
case 'c': // crypt
caesar = new Caesar(Integer.parseInt(args[0].substring(1)));
eingabe = caesar.readStream(in);
ausgabe = caesar.disguise(caesar.crypt(caesar.prepare(eingabe)));
caesar.writeStream(out, ausgabe);
break;
case 'p': // prepare
caesar = new Caesar(Integer.parseInt(args[0].substring(1)));
eingabe = caesar.readStream(in);
ausgabe = caesar.prepare(eingabe);
caesar.writeStream(out, ausgabe);
break;
case 'd': // decypt
caesar = new Caesar(Integer.parseInt(args[0].substring(1)));
eingabe = caesar.readStream(in);
ausgabe = caesar.decrypt(caesar.prepare(eingabe));
caesar.writeStream(out, ausgabe);
break;
case 'k': // crack
caesar = new Caesar();
eingabe = caesar.readStream(in);
ausgabe = caesar.crack(caesar.prepare(eingabe));
caesar.writeStream(out, ausgabe);
break;
default:
System.err.println("Ungültiger Aufruf (key), Hilfe mit -h");
}
} catch (FileNotFoundException e) {
System.err
.println("Datei nicht gefunden: " + e.getLocalizedMessage());
} catch (IOException e) {
System.err.println("Ein-/Ausgabefehler: " + e.getLocalizedMessage());
} catch (NumberFormatException e) {
System.err.println("Ungültiger Aufruf (key), Hilfe mit -h");
}
}
} else if (args.length >= 1 && args[0].equals("-h")) { // Hilfe
help();
} else { // Fehler
System.err.println("Ungültiger Aufruf, Hilfe mit -h");
}
}

}



Sinnvollerweise wird man bei dieser Lösung noch das Erzeugen der Tabelle in eine eigene Methode auslagern, die dann im Konstruktor bzw. in crack() aufgerufen wird.

Labels: , , ,


Kommentare:
Der zweithäufigste Buchstabe im deutschen Alphabet ist nicht das A sondern das N mit 9,78%.
 

Kommentar veröffentlichen

Abonnieren Kommentare zum Post [Atom]





<< Startseite

This page is powered by Blogger. Isn't yours?

Abonnieren Posts [Atom]