Übungen zu Computersicherheit
Ziel der Übung ist es, Umgebungen für die verschiedenen kryptographischen Verfahren und Protokolle zu erstellen.
Wir beginnen zunächst mit der Programmierung von ersten einfachen Verschlüsselungsverfahren wie Caesar und Skytale.
Schnittstelle:
Jedes Verschlüsselungsverfahren soll eine eigenstündige Methode bzw. ein eigenständiges Command-Line-Programm sein, das als Eingabe eine Zeichenfolge erhält, in der durch / eingeleitete Optionen oder Sonderzeichen stehen können bzw. müssen.
/c bzw. /d (codieren oder decodieren) muß als letzte Option der Eingabe vor dem zu verarbeitenden Text stehen.
Davor kann die Option /s stehen, hinter der ein Schlüssel eingegeben wird, wenn nicht der Standardschlüsssel verwendet werden soll.
Daneben kann die Option /a stehen, hinter der eine Zeichenfolge eingegeben wird, deren Zeichen als Alphabet statt des Standardalphabets verwendet werden sollen.
Wenn im Schlüssel oder Alphabet das Leerzeichen vorkommen soll, muß das Options-zeichen / vor dem Leerzeichen stehen, auch Tabulator und NewLine können als /n oder /t in einen Schlüssel oder ein Alphabet aufgenommen werden. Auch weitere Sonderzeichen können mit /xxxx aufgenommen werden, wobei xxxx die Nummer des Zeichens als unicode-Zeichen ist.
Caesar:
Beim Verfahren Caesar soll das Standardalphabet aus den Zeichen ABCDEFGHIJKLMNOPQRSTUVWXYZ bestehen und der Standardschlüssel die Zahl 3 sein, Bei der Skytale besteht das Standardalphabet aus allen Zeichen und der Standardschlüssel ist 5 (Spaltenzahl)
Der Caesar muß die Länge (Anzahl der Zeichen) des Alphabets ermitteln und den Schlüssel als natürliche Zahl interpretieren.
(keine Überprüfungen im Programm, weil wir davon ausgehen, daß diese vorher erfolgt sind.)
dann wird jedes Textzeichen, das im Alphabet vorkommt, durch das um den Schlüssel weiter rechts stehende (modulo
Alphabet-Länge) Zeichen ersetzt. Nicht im Alphabet vorkommende Zeichen bleiben an ihrer Stelle und werden nicht ausgetauscht.
das Entschlüsseln geschieht mit demselben Verfahren aber mit AlphabetLänge-Schlüssel als neuem Schlüssel.
Skytale:
Bei der Skytale wird der eingegebene Text zeilenweise in ein Array mit Schlüssel-vielen Spalten eingegeben dann wird das
Array spaltenweise ausgegeben.
Für die Decodierung wird zunächst Textlänge durch Schlüssel mit Rest dividiert. Dann wird der Text in ein Array mit
Quotient+1 Zeilen spaltenweise eingetragen, wobei Rest-viele Spalten vollgeschrieben werden und bei den übrigen Spalten die
letze Zeile frei bleibt.
Überlege, warum es nicht günstig ist, die letzte Zeile beim codieren grundsätzlich mit beliebigen Zeichen bis zum Ende aufzufüllen.
Oberfläche:
Erstelle eine Benutzeroberfläche, in der man zwischen den implementierten Codierverfahren auswählen kann, das Alphabet und den Schlüssel einstellen kann, die die zugehörigen Prüfungen übernimmt und dann bereit steht, beliebige Texte mit den gewählten Verfahren Alphabet und Schlüssel zu codieren oder zu decodieren.
Vigenere:
Als erste Grundlage für professionelle Codierverfahren soll die Codierung mit einem Vigenere-Tableau realisiert werden. Wie bisher soll es möglich sein mit den Optionen /a und /s das Alphabet und den Schlüssel neu festzulegen. Standardalphabet sollen die ASCII-Zeiche 33 ... 126 (! ... ~) und der Standardschlüssel KEY sein. Mit Option /d oder /c wird wie üblich decodieren oder codieren veranlasst und danach kommt als Eingabe nur noch der Text. Zeichen, die nicht im Alphabet vorkommen, werden vom Verfahren ignoriert und einfach an ihrer Stelle stehen gelassen. Soll in Alphabet oder Schlüssel ein / vorkommen, so muß das (wie üblich) als // angegeben werden.
Das Alphabet ist intern ein String A aus l Zeichen (// ist ein Zeichen /) und die Verschlüsselung des Zeichens A[i] mit dem Zeichen A[j] ergibt das Zeichen A[i+j mod l].
Die Ausführungsmodi:
Professionelle kryptographische Codes verwenden Bytefolgen fester Länge n als Ein- und Ausgaben, es handelt sich also
weitestgehend um Blockcchiffren.
Wenn nun aber die Situation (z.B. bei der Verschlüsselung und übertragung eines langen Datenstroms) eine Stromchiffre erfordert,
Wird dies entweder durch einen der in der Vorlesung besprochenen Modi erreicht, oder dadurch, daß auf den Datenstrom ein
pseudo-zufällig erzeugter Bit-, Byte- oder sonstiger Block-strom aufaddiert wird (mit XOR oder binärer Block-Addition oder speziell
bei 16-Bit-Blöcken der bei IDEA besprochene Multiplikation)
In dieser Aufgabe soll eine Oberfläche entwickelt werden, die es ermöglicht, einen Block-code und einen der Modi ECB, AutoKey, CBC, CFB oder OFB auszuwählen und dann einen Datenstrom nach Eingabe eines Schlüssels und ggf. Headers mit Hilfe des gewählten Blockcodes und Modus zu verschlüsseln bzw. zu entschlüsseln
Für die in den Modi benötigte Block-operation + soll sowohl das bitweise XOR als auch die binäre Integer-Addition für die Blocklänge 8, 16 oder 32 des gewählten Codes anwählbar sein.
Wer schon mal weitergehen möchte kann dazu auch die in der Vorlesung besprochene 16-Bit Multiplikation (siehe IDEA) anwählbar machen. Beachte, daß zum Decodieren zu jedem element x sein multiplikatives Inverses x-1 bestimmt werden muß. Das kann man am leichtesten aus der Multiplikationstabelle ablesen, die man vorher erstellen sollte. (Es gibt dazu auch ein numerisches Verfahren ohne Tabelle mit dem Euklidischen Algorithmus, das wir später besprechen.)
Weiterarbeit an den Ausführungsmodi:
Die Oberfläche für die Ausführungsmodi soll intern bereitstellen die drei Operationen
XOR (bitweise XOR für Blöcke beliebiger Länge)
ADD (binäre Addition für natürliche Zahlen int für Blocklängen bis zu 32 Bit
MUL (16-Bit Multiplikation modulo 216+1 auf {1,2,3,...,216-1,216} (216 wird dann als 0 dargestellt)
Diese drei Operationen sollen für die Auswahl der Block-Addition + in den verschiedenen Modi wie auch des
Verschlüsselungsalgorithmus C zur Verfügung stehen. (z.B. C(S,x) = ADD(S,x) , x+y = XOR(x,y) )
Weitere Verschlüsselungen C sollen zur Zeit noch nicht implementiert werden
Die Oberfläche soll zunächst die gewünschte Blocklänge (die per Voreinstellung auch die Schlüssellänge ist) und den gewünschten Modus (ECB, AUTO, CBC, CFB, OFB) abfragen. Danach muß der Schlüssel und der Header angefordert werden (bei ECB kein Header). Schließlich muß noch erfragt werden, ob codiert oder decodiert werden soll. (Für die Decodierung von MUL werden wir erst in der nächsten Übung eine Tabelle der Inversen x-1 zu allen 16-Bit Zahlen mit Hilfe des euklidischen Algorithmus erstellen)
Um auch Schlüssellängen beliebiger Größe zu ermöglichen (Die Oberfläche soll sich aber auf Vielfache von 16 beschränken), sollen die Operationen XOR, ADD und MUL dadurch erweitert werden, daß sie die 16-Bit-Varianten im 16-Bit-Blockweise (wie ECB) auf die gesamte Schlüssellänge erweitern
Bei ADD können wir noch eine zweite Variante ADB (ADD BIG mit Übertrag) zur Übertragung auf Längen erzeugen, die Vielfache von 16 sind.
Für die Addition teilen wir die zu adddierenden Blöcke jeweils in k 16-Bit Blöcke
B0 B1 B2 ... Bk-1 und
C0 C1 C2 ... Ck-1 ein und gehen wie folgt vor:
Angefangen bei Block i=0 und einem Übertrag u=0 werden die Binärzahl Bi und Ci und der Übertrag
als 32-Bit Zahlen addiert, das Ergebnis modulo 216 (die unteren 16 Stellen) sind der Ergebnisblock Di
und der neue Übertrag ist 1, wenn das 32-Bit Ergebnis >= 216 ist (in den oberen 16 Stellen stehen nicht
nur 0'en, sonst ist der neue Übertrag 0 (kurz gesagt der Übertrag ist der Ganzzahlanteil von dem 32-Bit Ergebnis geteilt durch 216). Nun geht es genauso weiter mit den Blöcken i+1 bis alle Blöcke verarbeitet sind
Das Ergebnis der Addition ist nun die Blockfolge D0 D1 D2 ... Dk-1
und der letzte Übertrag aus den Blöcken k-1 wird ignoriert (Rechnung modulo 2k*16)
Bemerkung: hiermit haben wir übrigens schon die langen natürliche Zahlen (bigint) und deren Addition implementiert.