(**************************************************************************) (**************************************************************************) (*** ***) (*** Funktionen rund um DES in OCaml ***) (*** ***) (*** Diese Bibliothek enthält einige Funktionen, um mit DES zu ***) (*** arbeiten. Bei den folgenden Funktionen sind 'text', 'key' und ***) (*** 'init' jeweils Listen aus '0' '1', also Bits. Die Länge der Listen ***) (*** ist 64. Außerdem ist bei 'key' jedes achte Bit ein Parity-Bit (xor ***) (*** über die sieben vorhergehenden Bits) ***) (*** ***) (*** + encode_des text key ***) (*** + decode_des text key ***) (*** ***) (*** Ab hier kann 'text' beliebig lang sein ***) (*** ***) (*** + encode_des_ecb text key ***) (*** + decode_des_ecb text key ***) (*** + encode_des_cbc text key init ***) (*** + decode_des_cbc text key init ***) (*** + encode_des_cfb text key init ***) (*** + decode_des_cfb text key init ***) (*** + encode_des_ofb text key init ***) (*** + decode_des_ofb text key init ***) (*** ***) (*** ***) (*** ***) (*** Copyright 2002 by Hannes Keil ***) (**************************************************************************) (**************************************************************************) (* Jedes achte Bit ist ein Parity-Bit. Es berechnet sich per xor aus den sieben vorher gehenden (0 bei geradzahlig vielen einsern, sonst 1) *) let my_key = [ 1; 0; 0; 0; 1; 1; 0; 1; 0; 0; 0; 1; 1; 0; 0; 0; 0; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 0; 0; 0; 1; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 0; 1; 1; 1; 1; 0; 0; 1; 1; 0; 0; 1; 0; 1; 0; 1; 0; 1; 0 ];; let my_init = [ 0; 0; 0; 1; 1; 0; 0; 0; 1; 0; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 0; 0; 1; 1; 1; 0; 0; 0; 0; 1; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 0; 1; 0; 1; 0; 1; 0; 1; 1; 0; 0; 1; 1; 0; 0 ];; let my_text = [ 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 0; 0; 0; 0; 0; ];; let my_text_2 = my_text @ my_text @ [1;0;1;0;1;0];; (**********************************************************) (**********************************************************) (*** ***) (*** Generelle Hilfsfunktionen ***) (*** ***) (**********************************************************) (**********************************************************) (* Einfache Permutation. Dabei ist 'lst' eine Liste, die gemäß 'pi' permutiert werden soll. So etwa: permute [11;12;31;40] [2;4;1;3] -> [12;40;11;31] *) let rec permute lst pi = match pi with | [] -> [] | p::tail -> (List.nth lst (p-1))::(permute lst tail);; (* Links-Rotation. Die Liste 'lst' wird um 'x' Stellen nach links rotiert Bsp: rol [1;2;3;4] 1 -> [2;3;4;1] *) let rec rotate lst x = match (lst, x) with | (_, 0) -> lst | ([], _) -> [] | (a::tail, n) -> rotate (tail@[a]) (n-1);; (* Mit dieser Funktion wird eine Liste in zwei zerteilt. Dabei werden von der Liste 'lst' die ersten 'x' Elemente in eine zweite Liste gesteckt. Die Ausgabe besteht aus einem 2-Tupel *) let rec split_list_rec (lst1, lst2, x) = match (lst1, lst2, x) with | (_, _, 0) -> (lst1, lst2) | (a, [], _) -> (a, []) | (a, b::tail, n) -> split_list_rec (a@[b], tail, n-1);; let split_list lst x = split_list_rec ([], lst, x);; (* xor-Verknüpfung, die aus zwei Bitlisten eine Ergebnisliste generiert *) let rec xor_lists text key = match (text, key) with | ([], []) -> [] | (a::atail, b::btail) when a + b = 1 -> 1::(xor_lists atail btail) | (a::atail, b::btail) -> 0::(xor_lists atail btail) | _ -> failwith("xor_lists: Seems like the two lists are different in size");; (* Diese Funktion erzeugt aus einer gegebenen Dezimalzahl eine Binärdarstellung als Liste aus Bits. Nachdem diese Funktion genau einmal benötigt wird (gleich nach den S-Boxen) und dort eine Binärzahl mit genau 4Bit Länge benötigt wird, gibt's gleich noch eine spezialisierte Funktion dazu. *) let rec dez_to_bin_allg x = match x with | 0 -> [0] | 1 -> [1] | n -> (dez_to_bin_allg (x / 2))@(dez_to_bin_allg (x mod 2));; let dez_to_bin_4 x = match (dez_to_bin_allg x) with | n when (List.length n) = 1 -> [0;0;0]@n | n when (List.length n) = 2 -> [0;0]@n | n when (List.length n) = 3 -> [0]@n | n when (List.length n) = 4 -> n | _ -> failwith("dez_to_bin_4: Number greater than 15");; (* Genau das Gegenteil vom oberen. Hier wird eine Liste aus Bits gegeben und eine Dezimaldarstellung errechnet. Achtung: bin_to_dez_rev benötigt die Zahl 'verkehrt herum', damit der Horner besser greift. *) let rec bin_to_dez_rev lst = match lst with | [] -> 0 | a::tail when a = 1 -> 1 + (bin_to_dez_rev tail) * 2 | a::tail -> (bin_to_dez_rev tail) * 2;; let bin_to_dez lst = bin_to_dez_rev (List.rev lst);; (**********************************************************) (**********************************************************) (*** ***) (*** Verwendete Tabellen ***) (*** ***) (**********************************************************) (**********************************************************) (* Diese Permutation wird auf den 64Bit-Schlüssel angewendet. Dabei werden zum einen die Parity-Bits entfernt und zum anderen wird schon mal ein bissl geschüttelt. *) let init_key_perm = [ 57; 49; 41; 33; 25; 17; 9; 1; 58; 50; 42; 34; 26; 18; 10; 2; 59; 51; 43; 35; 27; 19; 11; 3; 60; 52; 44; 36; 63; 55; 47; 39; 31; 23; 15; 7; 62; 54; 46; 38; 30; 22; 14; 6; 61; 53; 45; 37; 29; 21; 13; 5; 28; 20; 12; 4 ];; (* Diese Permutation wird auf jeden der 16 Teilschlüssel angewendet um ihn endgültig zu einem Teilschlüssel zu machen. *) let sub_key_perm = [ 14; 17; 11; 24; 1; 5; 3; 28; 15; 6; 21; 10; 23; 19; 12; 4; 26; 8; 16; 7; 27; 20; 13; 2; 41; 52; 31; 37; 47; 55; 30; 40; 51; 45; 33; 48; 44; 49; 39; 56; 34; 53; 46; 42; 50; 36; 29; 32 ];; (* Das ist die Tabelle, gemäß der die 2*16 Prä-Teilschlüssel mit 'prep_C_D_keys' erzeugt werden. *) let c_d_shift_table = [ 1; 1; 2; 2; 2; 2; 2; 2; 1; 2; 2; 2; 2; 2; 2; 1 ];; (* Mit dieser Permutation wird der Textblock ganz zu begin bearbeitet *) let init_text_perm = [ 58; 50; 42; 34; 26; 18; 10; 2; 60; 52; 44; 36; 28; 20; 12; 4; 62; 54; 46; 38; 30; 22; 14; 6; 64; 56; 48; 40; 32; 24; 16; 8; 57; 49; 41; 33; 25; 17; 9; 1; 59; 51; 43; 35; 27; 19; 11; 3; 61; 53; 45; 37; 29; 21; 13; 5; 63; 55; 47; 39; 31; 23; 15; 7 ];; (* Diese Permutation wird zu Beginn jeder Schleife verwendet, um den Textblock von 32Bit auf 48Bit zu erweitern. *) let text_exp_perm = [ 32; 1; 2; 3; 4; 5; 4; 5; 6; 7; 8; 9; 8; 9; 10; 11; 12; 13; 12; 13; 14; 15; 16; 17; 16; 17; 18; 19; 20; 21; 20; 21; 22; 23; 24; 25; 24; 25; 26; 27; 28; 29; 28; 29; 30; 31; 32; 1 ];; (* Die Substitutionsboxen (von denen keiner außer der NSA weiß, was sie bedeuten ;-) *) let subst_boxes = [ [ (* S1 *) 14; 4; 13; 1; 2; 15; 11; 8; 3; 10; 6; 12; 5; 9; 0; 7; 0; 15; 7; 4; 14; 2; 13; 1; 10; 6; 12; 11; 9; 5; 3; 8; 4; 1; 14; 8; 13; 6; 2; 11; 15; 12; 9; 7; 3; 10; 5; 0; 15; 12; 8; 2; 4; 9; 1; 7; 5; 11; 3; 14; 10; 0; 6; 13 ]; [ (* S2 *) 15; 1; 8; 14; 6; 11; 3; 4; 9; 7; 2; 13; 12; 0; 5; 10; 3; 13; 4; 7; 15; 2; 8; 14; 12; 0; 1; 10; 6; 9; 11; 5; 0; 14; 7; 11; 10; 4; 13; 1; 5; 8; 12; 6; 9; 3; 2; 15; 13; 8; 10; 1; 3; 15; 4; 2; 11; 6; 7; 12; 0; 5; 14; 9 ]; [ (* S3 *) 10; 0; 9; 14; 6; 3; 15; 5; 1; 13; 12; 7; 11; 4; 2; 8; 13; 7; 0; 9; 3; 4; 6; 10; 2; 8; 5; 14; 12; 11; 15; 1; 13; 6; 4; 9; 8; 15; 3; 0; 11; 1; 2; 12; 5; 10; 14; 7; 1; 10; 13; 0; 6; 9; 8; 7; 4; 15; 14; 3; 11; 5; 2; 12 ]; [ (* S4 *) 7; 13; 14; 3; 0; 6; 9; 10; 1; 2; 8; 5; 11; 12; 4; 15; 13; 8; 11; 5; 6; 15; 0; 3; 4; 7; 2; 12; 1; 10; 14; 9; 10; 6; 9; 0; 12; 11; 7; 13; 15; 1; 3; 14; 5; 2; 8; 4; 3; 15; 0; 6; 10; 1; 13; 8; 9; 4; 5; 11; 12; 7; 2; 14 ]; [ (* S5 *) 2; 12; 4; 1; 7; 10; 11; 6; 8; 5; 3; 15; 13; 0; 14; 9; 14; 11; 2; 12; 4; 7; 13; 1; 5; 0; 15; 10; 3; 9; 8; 6; 4; 2; 1; 11; 10; 13; 7; 8; 15; 9; 12; 5; 6; 3; 0; 14; 11; 8; 12; 7; 1; 14; 2; 13; 6; 15; 0; 9; 10; 4; 5; 3 ]; [ (* S6 *) 12; 1; 10; 15; 9; 2; 6; 8; 0; 13; 3; 4; 14; 7; 5; 11; 10; 15; 4; 2; 7; 12; 9; 5; 6; 1; 13; 14; 0; 11; 3; 8; 9; 14; 15; 5; 2; 8; 12; 3; 7; 0; 4; 10; 1; 13; 11; 6; 4; 3; 2; 12; 9; 5; 15; 10; 11; 14; 1; 7; 6; 0; 8; 13 ]; [ (* S7 *) 4; 11; 2; 14; 15; 0; 8; 13; 3; 12; 9; 7; 5; 10; 6; 1; 13; 0; 11; 7; 4; 9; 1; 10; 14; 3; 5; 12; 2; 15; 8; 6; 1; 4; 11; 13; 12; 3; 7; 14; 10; 15; 6; 8; 0; 5; 9; 2; 6; 11; 13; 8; 1; 4; 10; 7; 9; 5; 0; 15; 14; 2; 3; 12 ]; [ (* S8 *) 13; 2; 8; 4; 6; 15; 11; 1; 10; 9; 3; 14; 5; 0; 12; 7; 1; 15; 13; 8; 10; 3; 7; 4; 12; 5; 6; 11; 0; 14; 9; 2; 7; 11; 4; 1; 9; 12; 14; 2; 0; 6; 10; 13; 15; 3; 5; 8; 2; 1; 14; 7; 4; 10; 8; 13; 15; 12; 9; 0; 3; 5; 6; 11 ] ];; (* Diese Permutation wird in jeder Runde nach den S-Boxen angewendet *) let post_sbox_perm = [ 16; 7; 20; 21; 29; 12; 28; 17; 1; 15; 23; 26; 5; 18; 31; 10; 2; 8; 24; 14; 32; 27; 3; 9; 19; 13; 30; 6; 22; 11; 4; 25 ];; (* Diese Permutation wird auf den Text angewendet, den wir nach 16 Runden erhalten. *) let final_text_perm = [ 40; 8; 48; 16; 56; 24; 64; 32; 39; 7; 47; 15; 55; 23; 63; 31; 38; 6; 46; 14; 54; 22; 62; 30; 37; 5; 45; 13; 53; 21; 61; 29; 36; 4; 44; 12; 52; 20; 60; 28; 35; 3; 43; 11; 51; 19; 59; 27; 34; 2; 42; 10; 50; 18; 58; 26; 33; 1; 41; 9; 49; 17; 57; 25 ];; (**********************************************************) (**********************************************************) (*** ***) (*** Schlüssel vorbereiten ***) (*** ***) (**********************************************************) (**********************************************************) (* Ganz simpler parity-check für den Schlüssel. Wenn der Schlüssel keine Länge von x * 8 mit x \in \N hat, gibt's nen Fehler. *) let rec check_parity lst = match lst with | [] -> true | a::b::c::d::e::f::g::h::tail -> ((a+b+c+d+e+f+g) mod 2 = h) && (check_parity tail) | _ -> failwith("check_parity: length is no multiple of eight");; (* Gegeben ist C[0] bzw. D[0] in 'klst'. Aus diesen werden C[1] bis C[16] bzw. D[1] bis D[16] durch Rotation des jeweiligen Vorgängers erzeugt. Die 16 Prä-Teilschlüssel werden in einer Liste (aus Listen) zurück gegeben. *) let rec prep_c_d_keys klst shift = match shift with | [] -> [] | a::tail -> (rotate klst a)::(prep_c_d_keys (rotate klst a) tail);; (* C und D sind zwei Listen, in denen je 16 Prä-Teilschlüssel enthalten sind. Diese werden zu einer Liste K aus 16 Teilschlüsseln zusammengefügt. Das geschieht nach folgendem Schema: K[i] = C[i] @ D[i] *) let rec merge_key_parts (c, d) = match (c, d) with | ([], []) -> [] | (a::atail, b::btail) -> (a @ b)::(merge_key_parts (atail, btail)) | _ -> failwith("merge_key_parts: Seems like c and d are different in size");; (* An dieser Stelle hat der Schlüssel bereits die erste Permutation durchlaufen und wird in zwei Listen 'c' und 'd' geteilt. Diese Listen werden dann in 16 Prä-Teilschlüssel verwandelt, die dann zu den 16 Teilschlüsseln werden. *) let make_subkeys_of_c_and_d (c, d) = merge_key_parts ((prep_c_d_keys c c_d_shift_table), (prep_c_d_keys d c_d_shift_table));; (* Das hier schüttelt unsere 16 Teilschlüssel durch. Was hier raus kommt, ist eine Liste mit den 16 fertigen Schlüsseln. *) let rec perm_sub_keys lst perm = match lst with | [] -> [] | a::tail -> (permute a perm)::(perm_sub_keys tail perm);; (* Quasi die main-Methode der Schlüsselerzeugung. Gegeben wird der original 64Bit-Schlüssel. Dann wird erstmal auf Parity-Fehler geprüft und die erste Permutation durchlaufen. Der (56Bit-)Schlüssel wird zweigeteilt und diese zwei Teile in 2*16 vermehrt, die dann wiederum zu 16 zusammengefasst werden. Nach einer weiteren Permutation kommt als Ergebnis eine Liste mit 16 48Bit-Teilschlüsseln raus. *) let prep_key key = match (check_parity key) with | false -> failwith ("prep_key: checksum error") | true -> perm_sub_keys ( make_subkeys_of_c_and_d ( split_list (permute key init_key_perm) 28)) sub_key_perm;; (**********************************************************) (**********************************************************) (*** ***) (*** Textblock vorbereiten ***) (*** ***) (**********************************************************) (**********************************************************) (* Hiermit wird der Text bearbeitet, bevor er die 16 Runden durchläuft. Also die Eingangspermutation T *) let init_text text = split_list (permute text init_text_perm) 32;; (* Wenn der Text dann durch alle Runden durch ist, wird er noch einmal hiermit bearbeitet. *) let finish_text (left_text, right_text) = permute (right_text @ left_text) final_text_perm;; (**********************************************************) (**********************************************************) (*** ***) (*** Textblock verschlüsseln ***) (*** ***) (**********************************************************) (**********************************************************) (* Diese nette kleine Funktion berechnet aus Zeile und Spalte den Index in der S-Box. 's' und 'z' sind in Binärdarstellung angegeben, allerdings ist 'z' "`verkehrt herum"' (siehe Kommentar beim 'calc_pos'-Aufruf innerhalb 'use_subst_boxes' *) let calc_pos (s,z) = (bin_to_dez_rev z) * 16 + (bin_to_dez s);; (* Der Nachschlagevorgang in einer S-Box. Die Funktion erledigt gleich alle acht Look-Ups, indem eine Liste aller Eingabebits und eine Liste aller S-Boxen übergeben werden. Diese werden dann per head::tail rekursiv abgearbeitet und die Ergebnisse konkateniert. *) let rec use_subst_boxes text sboxes = match (split_list text 6) with | ([],[]) -> [] | (a, texttail) -> dez_to_bin_4( (* hier steht das Ergebnis aus der S-Box in Dezimalform *) List.nth (List.hd sboxes) (* Position in der S-Box bestimmen. a ist folgendermaßen aufgebaut: z1 sp1 sp2 sp3 sp4 z2 z1,z2 geben die Zeile in der S-Box an sp1 bis sp4 die Spalte. An calc_pos geht also folgender Ausdruck: ([sp1;sp2;sp3;sp4], [z2;z1]) *) (calc_pos (split_list (rotate a 1) 4)) ) @ (use_subst_boxes texttail (List.tl sboxes));; (* Die 16 DES-Runden. Durch die Länge der Liste 'subkeys' wird gewährleistet, daß es auch 16 Runden werden. *) let rec runde subkeys (left_text, right_text) = match subkeys with | [] -> (left_text, right_text) | a::tail -> runde tail (right_text, xor_lists left_text ( permute ( use_subst_boxes (xor_lists a ( permute right_text text_exp_perm)) subst_boxes) post_sbox_perm));; (* Das Ziel des ganzen Strebens. Scotty: Energie! *) let encode_des text key = finish_text(runde (prep_key key) (init_text text));; (**********************************************************) (**********************************************************) (*** ***) (*** Textblock entschlüsseln ***) (*** ***) (**********************************************************) (**********************************************************) (* Data, gehen sie auf Impulsgeschwindigkeit. *) let decode_des text key = finish_text(runde (List.rev (prep_key key)) (init_text text));; (**********************************************************) (**********************************************************) (*** ***) (*** Mehrere Blöcke bearbeiten ***) (*** ***) (**********************************************************) (**********************************************************) (* Diese Funktion erstellt Listen beliebiger Länge aus Null-Bits (quasi /dev/zero). Diese werden von 'fill_64_bits' benötigt. *) let rec get_dummy_list x = match x with | 0 -> [] | n -> 0::(get_dummy_list (n - 1));; (* Eine Hilfsfunktion, die den Klartext auf ein Vielfaches von 64Bit aufstocken soll. Als Füllwerte werden Nuller verwendet, was kryptographisch gesehen nicht unbedingt das Beste ist. *) let fill_64_bits text = match ((List.length text) mod 64) with | 0 -> text | x -> text @ (get_dummy_list (64 - x));; (* Eine Hilfsfunktion, die sicherstellt, daß die Länge des Ciphertextes ein Vielfaches von 64 ist. Andernfalls ist der Ciphertext nicht mit DES verschlüsselt worden (mal diverse Verschleierungstechniken ausgeschlossen). *) let ensure_64_bits text = match ((List.length text) mod 64) with | 0 -> text | _ -> failwith("ensure_64_bits: the ciphertext seems to be broken");; (* Electronic Codebook Mode Der Text wird einfach in 64Bit-Blöcke zerteilt, die einzeln chiffriert werden. *) let rec encode_des_ecb text key = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (encode_des (fill_64_bits txt) key) @ (encode_des_ecb txttail key);; let rec decode_des_ecb text key = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (decode_des (ensure_64_bits txt) key) @ (decode_des_ecb txttail key);; (* Cipher Block Chaining Jeder Textblock wird erst mal mit dem vorherigen Cipherblock xor-Verknüpft. Der erste Textblock wird mit einem Initialisierungsvektor verknüpft. *) let rec encode_des_cbc text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (encode_des (xor_lists (fill_64_bits txt) init) key) @ (encode_des_cbc txttail key (* grad mal wegschaun ... *) (encode_des (xor_lists (fill_64_bits txt) init) key));; let rec decode_des_cbc text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (xor_lists (decode_des (ensure_64_bits txt) key) init) @ (decode_des_cbc txttail key txt);; (* Cipher Feedback Der vorherige Cipherblock wird verschlüsselt und mit dem aktuellen Klartextblock xor-Verknüpft. Der erste Klartextblock wird mit einem Initialisierungsvektor verknüpft. *) let rec encode_des_cfb text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (xor_lists (fill_64_bits txt) init) @ (encode_des_cfb txttail key ( encode_des (xor_lists (fill_64_bits txt) init) key));; let rec decode_des_cfb text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (xor_lists (ensure_64_bits txt) init) @ (decode_des_cfb txttail key (encode_des (* (!) *) (ensure_64_bits txt) key));; (* Output Feedback Jeder Klartextblock wird mit einem Initialisierungsvektor xor-verknüpft. Nach jedem Klartextblock wird der Init.vektor verschlüsselt (also immer und immer wieder) und mit dem nächsten Klartextblock verknüpft. *) let rec encode_des_ofb text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (xor_lists (fill_64_bits txt) init) @ (encode_des_ofb txttail key (encode_des init key));; (* Bis auf ensure_64_bit vs. fill_64_bit sind die beiden identisch *) let rec decode_des_ofb text key init = match (split_list text 64) with | ([], []) -> [] | (txt, txttail) -> (xor_lists (ensure_64_bits txt) init) @ (encode_des_ofb txttail key (encode_des init key));; (* that's all folks *)