|
Verschluesseln mit Schwerpunkt DES
DES steht fuer Data Encryption Standard und stellt eine Art Daten zu verschluesseln dar. Der DES beinhaltet den DEA Data Encryption Algorithm. Das Ganze wurde 1976-1977 von IBM entwickelt, und 1977 als US-Verschluesselungsstandard genormt. Zuerst entstand in unabhaengiger Arbeit der sogenannte Lucifer-Algorithmus, der eine Schluessellaenge von 128 Bits verwendete. Danach schaltete sich die NSA National Security Agency ein. Sie fuehrte zusammen mit IBM die Tests ueber die Sicherheit von DES durch, waehrend derer die Schluessellaenge auf 56 Bit gekuerzt wurde. Berichte, was die Tests ergeben haben, sind wie die Auswahlkriterien gewisser Interna des DEA unter Verschluss. Es existieren aber inzwischen einige unabhaengige Studien, z.T. auf theoretischer Ebene. WARUM VERSCHLUESSELN ? Zuerst mal generell: Wieso wird verschluesselt ? Naja konkret um andere 'Leute' davon abzuhalten, ihre Nase in Dinge zu stecken, die sie 'meiner' Meinung nach nix angehen. Das koennten Rechnungen, Datenbanken, Finanz- buchhaltungen sein. Oder Programme, die man vor der Einsicht anderer schuetzen will, und die sich dann zur Laufzeit selbst 'decodieren' Oder irgendwelche persoenlichen elektronische Briefe. Natuerlich hat die Verschluessleung auch gewisse Nachteile. Wenn man naemlich den Schluessel vergisst, ist die Information so gut wie wegge- worfen... Ein Rueckblick und Varianten zu DES Die ersten detaillierten Informationen zu 'Verschluesselng' (im Gegensatz zu den 'Geheimsprachen' von Priestern und Schamanen ist uns von den Spartanern (400 v.Chr) ueberliefert. Da wurde von Heerfuehrern, die unter einander geheime Nachrichten austauschen wollten ein schmaler Streifen Pergament um einen Stab gewickelt und dann beschriftet. Der Bote kannte diesen Trick nicht, und jemand der diese Botschaft entschluesseln wollte, wusste also nicht, wie er die Buchstaben zu sinnvollen Worten machen sollte. Ein Verfahren das bis anhin noch in verschiedenen Varianten verwendet wird, schreibt man Julius Caesar zu. Er ersetzte jeden Buchstabe des Alphabeths durch einen anderen, und legte so regelrechte Uebersetzungs-Tafeln und -'Buecher' an. Das geht so, dass zum Beispiel die Nachricht BRVTVS IST BOES zu CSWVWT KTV CPFT wird. Hier, bei dieser 'Uebersetzungstabelle' entspricht ein B einem C ein I einem K ein V einem W etc. (das koennte man zwar auch nur als eine einfache Verschie- bung auffassen, aber schliesslich hab ich das ja im Kopf gemacht :-) Heute werden beim Militaer bei Sprechfunkverbindungen jeweils Buchstaben resp. Silben oder haeufige Woerter durch Zahlen oder andere Woerter ersetzt. Schwaechen sind bei diesen (einfachen) Verfahren natuerlich vorhanden: Beim Tauschen von Buchstaben und sogar Buchstabenpaaren nach jeweils einer Tabelle bleiben die Haeufigkeiten von Buchstaben erhalten; das heisst mit etwas Geschick und Kenntniss der Sprache, in der die Botschaft geschrieben wurde, ist das Entschluesseln ohne grosse Muehe moeglich. Es gibt fuer die Crypto-Analysis inzw. grosse 'Standard'-Werke die die Haeufigkeiten von Buchstaben, Buchstabenpaaren, Silben und Phonemen in vielen Sprachen zur Verfuegung stellen. In dieser Art der Verschluesselung ist man noch viel weiter gegangen. Man kann einen Text anhand mehrer Tabellen Verschluesseln. Also ueber mehrere Stufen nacheinander (z.B. ein B wird zuerst zu einem C und in einem zweiten Durchgang zu einem F), was alleine noch nicht viel bringt (zwei Ersetz-Tabellen lassen sich ja leicht auf eine zusammenfassen), aber wenn nach jedem versch- luesseltem Zeichen eines Textes fuer das naechste Zeichen ein anderer Schluessel (sprich eine andere Tabelle) genommen wird, steigt die Sicherheit enorm! Je mehr verschiedene (unabhaengige) Schluessel man nacheinander verwendet, um jeweils einen Teil (Buchstaben pro Buchstaben) des Textes zu verschluesseln, desto groesser wird die Sicherheit, da nicht mal mehr Wiederholungen von Buchstabenkombinationen auftreten koennen. (Jedes Buch zur Cryptanalysis kann dazu viel mehr erzaehlen :-) Vielleicht doch noch zwei Beispiele zu diesen Ersetztabellen: Zuerst der heisse Draht zw. Washington und Moskau: (eine Telex-Verbindung, wie viele nicht wissen) Beim Verschicken von Meldungen von einem Ort zum andern: Jeder Buchstabe der Meldung wird nach einer anderen Tabelle ver- schluesselt. Es werden also jedesmal soviele Tabellen verwendet, wie der Text Zeichen hat. Das ist der einzige absolut sichere Schluessel, den man bis jetzt kennt, der nicht zu 'knacken' ist. ENIGMA: (ein den Deutschen wohl bekannter Name fuer eine der gelungensten Chiffriermaschinen) Die ENIGMA besteht aus mehreren Scheiben die auf beiden Seiten kreisfoermig angeordnete Kontakte enthalten. Diese Kontakte sind im Innern keuz und quer verbunden, so dass eine Scheibe eine Substitutionstabelle darstellt. Wird nun ein Buchstabe in die ENIGMA getippt, so gelangt er an die Aussenseite der ersten Scheibe. Dieses Signal kommt nun auf der anderen Seite der Scheibe an einem anderen Ort 'heraus' und gelangt auf die gleiche Art durch zwei weitere Scheiben. Dort sind die Kontakte ueber Steckverbindungen verknuepft, und das Signal wandert auf einem anderen Weg durch die gleichen drei Scheiben zurueck. Wieder auf Vorderseite angekommen, wird es dann an einem Laempchen angezeigt, und der Chiffreur erhaelt so der zu seiner gedrueckten Taste den korrespondierenden Schluesselbuchstaben. Allerdings werden nach jedem Tasten- druck die Scheiben verdreht... Es handelt sich also um eine Verschluesselung mit einer maximalen Schluessellaenge von 17576 Zeichen (26^3). "Dummerweise" hatte die ENIGMA ein paar konstruktions- und gebrauchsbedingte Schwaechen, so dass den Englaendern dann eine Entschluesselung in weniger als 42000 Jahren (wie sie von den Deutschen zur Entschluesselung eines Textes veran- schlagt wurden) gelang. Heute wichtige Verschluesselungsverfahren werden normalerweise auf Computern angewendet, einfach weil die Maschinen schneller sind als Menschen. Logo. In Diskussion stehen die Verfahren DES, FEAL und RSA. DES wird weiter unten ausfuehrlich beschrieben, FEAL ist eine stark abgespeckte Version von DES, die nichts desto trotz als aehnlich Sicher betrachtet wird. Ziel einer Verschluesselung dieser Art ist einfach, als Output einen Bitstrom zu erzeugen, der von einem zufaellig erzeugten Bitstrom nicht unterschieden werden kann. DES und FEAL scheinen das sehr gut zu erreichen. Der Unterschied von DES zu RSA ist folgender: - RSA bereibt zur Verschluesselung einen viel hoeheren Rechenaufwand! (Faktor 1000 ist noch untertrieben) - RSA benutzt oeffentliche Schluessel. Das ist ein grosser Vorteil: Man kann denjenigen die einem etwas schicken wollen einfach ein paar Schluessel zur Auswahl geben, und die Verschluesseln ihren Text damit. Das hat den grossen Vorteil gegenueber DES etc. dass der Schluessel nicht geheimgehalten werden muss. Wie RSA (Inverser Schluessel - Rivest, Shamir & Adlemann) funktioniert will ich nur ganz kurz dem Prinzip nach erklaeren. Der oeffentliche Schluessel besteht zur Hauptsache aus zwei GROSSEN (200 Stellen und mehr) Primzahlen die miteinander multipliziert werden. Will jemand einen Text entschluesseln, muss er dazu rausfinden, wie diese zwei Primzahlen lauten. Stichwort: Faktorisierung einer Zahl. Und das das rechenaufwenig ist, wird jeder leicht einsehen. Ein verschluesselter Text muss heutzutage nicht 'auf Ewig' geheim bleiben: Wenn jemand zum Entschluesseln nun mit den besten Rechnern zwei Wochen braucht, und man will nur einem guteen Kollgen die Lottozahlen von naechster Woche mitteilen, dann reicht die Sicherheit des verwendeten Algorithmus sicher... (na, zumindest in den meisten Faellen, bei den Lotto- zahlen wuerde wohl auch noch nach zwei Wochen ein Staatsanwalt aktiv :-) Wie funktioniert DES (DEA-Kernroutinen) Wichtig zum Verstanedniss des DEA ist nur der eigentliche Kernalgorithmus, der jeweils 64-Bit-Blocke verschluesselt. Wie diese 64-Bit-Bloecke dann weiterhin behandelt und evt. verknuepft werden, lasse ich hier ausser acht. Es wird ein 56-Bit Schluessel und 64 Bit Daten gegeben, daraus entstehen 64 Bit Schluesseltext. Der gleiche Input erzeugt in der Kernroutine immer den gleichen Output. DES verwendet einige Tabellen mit standardisiertem Namen. Sourcen fuer DES sind z.T als PD auf *nix-Systemen sowie VMS und VM/CMS sowie IBM's, Amigas und ST's vorhanden. (Beim Autor dieses Textes sind C-Sourcen fuer Unix,VMS,Atari,Amiga erhaeltlich) Ablauf des DES-Algorithmus: Der DEA teilt sich in zwei Teile. Zuerst wird nach dem folgenden Verfahren aus einem Input von 56 Bit ein DEA-interner Schluessel mit der Laenge 768 Bit generiert. Wer den DES etwas sicherer machen will, kann das ganz einfach ueber einen kleinen Trick erreichen. Er lasst dieses Expandieren des 56-Bit- Schluessel-Inputs einfach aus, und gibt direkt einen zufaelligen! 768-Bit- Schluessel vor. Das erhoeht statistisch gesehen die Sicherheit des DES um einen Faktor 2^(768-56). Aber lassen wir diese 'Details' einfach mal auf der Seite... Aus einem 56-Bit-Schluessel (Das nierderwertigste Bit jedes Schluesselbytes geht verloren (-> 8 Bytes), respektive wird mit dem obersten Bit ver- knuepft (SUN-Implementation)) werden 16 Unterschluessel gebildet, die je eine Laenge von 48 Bit haben. Das beginnt, indem der 64-Bit-Block des Schluessels durch die Funktion pc1 durchgeschleust wird. Dabei bleiben von den urspruenglichen 64 Bit nur 56 uebrig, die in zwei Unterschluessel C0 und D0 verteilt werden. Kleines Beispiel :-) ----------------------------------------------------------------- | Bit 1 | Bit 2 | Bit 3 | Bit 4 | Bit 5 | Bit 6 | Bit 7 | Bit 8 | ----------------------------------------------------------------- | V ------------------------- ------------------------- | Bit 3 | Bit 1 | Bit 7 | | Bit 6 | Bit 2 | Bit 5 | ------------------------- ------------------------- C0 D0 Man sieht n paar Bits gehen verloren, der Rest wird wild vertauscht und zu zwei Bloecken aufgetrennt. (56 Bit des Schluessels werden einfach nach einer Tabelle an eine andere Stelle gebracht. So wird Bit 57 des Original-Schluessels zum Bit 1 von C0, Bit 4 des Schluessels zum letzten (28-sten) Bit von D0) Mit Hilfe dieser 2 Unterschluessel werden nun die 16 Schluessel K1 bis K16 erzeugt, indem C0 und D0 jeweils um 1 oder 2 Bit nach links rotiert werden, und dann aus diesen 56 Bit mit Hilfe der Tabelle pc2 48 Bit selektiert werden. Diese Bits bilden den Schluessel Ki. Also nochmal ausfuehrlich: Wir haben Ci und Di (Am Anfang ist das C0 und D0) Jetzt machen wir einen Shift, das heisst, wir rotieren alle Bits von Ci und Di um ein oder zwei Stellen nach links. 1001010 -> 0010101 Jetzt setzen wir Ci und Di (nach dem ersten Rotieren koennen wir sie mit C1 und D1 bezeichnen, wieder zusammen. Also haben wir wieder ein Bitfeld mit 56 Bit. Daraus waehlen wir anhand der Tabelle PC2 48 Bit aus vertauschen die wild und nennen das Ergebniss Ki (Beim ersten Mal also K1) Jetzt wird wieder rotiert, und ausgewaehlt und das ganze 16 mal. Das gibt so K1 bis K16. Dabei wird beim ersten, zweiten, neunten und letzten Durchlauf Ci und Di um 1 Bit rotiert, sonst um zwei. Technisch gesehen: Nach dem Rotieren kann man Ci und Di wieder als zusammenhaengend betrachten, (Bit 1-28 Ci Bit 29-56 Di), und fuehrt darauf die Permutation pc2 aus. Das heisst Bit 14 von CiDi wird zu Bit 1 vom Unterschluessel Ki, Bit 1 von CiDi wird Bit 5 in Ki etc. Am Schluss bleiben so die 16 Schluessel Ki, mit je 48 Bit Inhalt. (Anm. d. Setzers: man muss dies nicht alles im Kopf nachvollziehen, oder..?) Diese 16 Unterschluessels bleiben auch bei einem laengeren Verschluesselungs- vorgang immer gleich. (Natuerlich koennte man auch dies zum steigern der Sicherheit varieren :-) Die Verschluesselung der 64 Bit Daten laueft nun wie folgt ab: Zuerst wird wieder (DES macht das liebend gern) permutiert. Dieses Mal mit der Tabelle ip. Bit 58 des Inputs wird so zu Bit 1 des Outputs etc. Das heisst wir stecken mal unsere 64 Bit Source in die DEA-Kernroutine. Die vertauscht diese 64 Bit wild miteinander. Die entstehenden 64 Bit werden aufgeteilt: Bit 1-32 (DES kennt kein 0-tes Bit) wandern nach L0, Bit 33-64 nach R0. Also wieder ein Aufteilung in zwei Haelften, wie bei der Generierung der Schluessel auch schon, nur dass die Haelften Li und Ri heissen ... Jetzt kommen 16 Durchlaeufe, in denen eine Kernfunktion f(Ri,Ki) auf Li und Ki einwirkt. Also zuerst wandern K1 und R0 in die Funktion f. Man merke K1 war der erste Unterschluessel, den wir vorher generiert haben, R0 ist die rechte Haelfte des soeben wild vertasuchten 64-Bit-Blocks Diese Funktion f() macht nun 'irgendwas' mit dem Ri das reingesteckt wird. Nach dem Durchlaufen der Funktion f() wird der Inhalt von Ri,Li vertauscht, und R(i+1) mit Li XOR-verknuepft. L1 ist also R0, R1 ist L0 XOR f(R0,K1). R1 ist also L0 XOR das Ergebniss der vorher ausgefuehrten Funktion f. Kompliziert? Warten Sie mal die Funktion f() ab... Nun wandern R1 und K2 in die Funktion f. Das Ergebnis wird mit L1 geXORt, und wird zu R2, waehrend R1 zu L2 wird. So geht das weiter bis alle 16 Schluessel Ki verarbeitet sind. Die letzte Operation ist also: R15 wird zu L16 und R16 ist das Ergebnis von L15 XOR f(R15,K16) Am Ende werden L16 und R16 nochmal vertauscht, das heisst R16 liefert die Bits 1-32 und L16 die Bits 33-64 des Outputs, dann wandert das durch die Funktion fp die genau das inverse der Permutation ip macht.(Also Bits wild vertasuchen:-) Das heisst Bit 40 des Inputs wird zu Bit 1 des Outputs etc. So entstehen 64 Bit, die das verschluesselte Aequivalent zu den 64 Input- Bits darstellen. Um 64 Bit zu entschluesseln, anstatt sie zu verschluesseln, laesst man genau die gleiche Prozedur wie oben nochmal ablaufen. Mit einem Unterschied. Die Schluessel K1 bis K16 werden nich in der aufsteigenden Reihenfolge der Funktion f() zugefuehrt, sondern in absteigender Reihenfolge, ausserdem werden die zwei Haelften der 64 Bit am Anfang vertauscht, bei der Bildung von R0 und L0, und dafuer am Ende nicht. Nun die Funktion f(Ri,Ki): Input in diese Funktion sind 32 Bit Text und 48 Bit Schluessel. Zuerst werden die 32 Bit Text zu 48 Bit aufgeblasen. Das geschieht mit der Funktion ei, die bei mir (nach einer Idee die ich Ende September in einer Anleitung zum SUN-DES gefunden habe, und die den gesamten Verschluesselungsvorgang um etwa den Faktor 8-10 schneller macht) implizt in der SP-Permutation enthalten ist. Auch die Permutationen S und P, siehe weiter unten, sind bei mir zu einem 2D-Array zusammengesetzt, in dem alle Moeglichkeiten tabellarisch behandelt werden. Zur Erklaerung beschreibe ich jetzt trotzdem, wie die Definition des Algorithmus die Funktion f() durchfuehrt, die Beschreibung meiner Methode ist im Listing eingebunden und mit dem dazugehoerigen Programmtext auch viiiiel verstaendlicher. Also. Wir fangen an mit 32 Bit Text und 48 Bit Schluessel. Diese 32 Bit Text muessen auf 48 Bit expandiert werden. Das geschieht indem verschiedene Bits doppelt gezaehlt werden; das besorgt die Funktion ei. Wir haben nach Benutzen von ei 48 Bit Text und 48 Bit Schluessel. Das Expandieren sieht vereinfacht so aus: ------------------------------------------------- | Bit 1 | Bit 2 | Bit 3 | Bit 4 | Bit 5 | Bit 6 | ------------------------------------------------- | V ------------------------------------------------------------------------- | Bit 6 | Bit 1 | Bit 2 | Bit 2 | Bit 3 | Bit 4 | Bit 4 | Bit 5 | Bit 6 | ------------------------------------------------------------------------- Nun haben wir also einen Schluessel und einen aufgeblasenen Input: Darauf wird ein XOR ausgefuehrt. Nun werden die entstehenden 48 Bit in 8 6-Bit-Haeppchen aufgeteilt. Jedes dieser 6-Bit-Haeppchen wird in einer der 8 S-Boxen zu 4 Bit Output reduziert. (Die S-BOX S1 ist fuer die ersten 6 Bit zustaendig, die S-Box S8 fuer die letzten 6 Bit) Man stelle sich unter einer S-Box eine Tabelle mit vier Reihen und 16 Spalten vor. Jeder Tabellen- eintrag besteht aus einer Vier-Bit Zahl. Um einen Tabelleneintrag anzusprechen, braucht man 6 Bit (2 Bit geben die Reihe 1-4 an, 4 Bit die Spalte 1-16) Wenn man nun am so bestimmten Ort der S-Box hineingreift, erhaelt man eine 4-Bit- zahl, die man als Output der S-Box bezeichnet. Dabei geben (bei der Tabellen-Version) das erste(lo) und das letzte(hi) Bit die Reihe der S-Box an (z.b. 0xxxx0 1.Reihe 0xxxx1 2.Reihe etc) und die mitteleren vier Bits die Spalte (0-15) der S-Box. Der Wert 110100 (3. Reihe, 10. Kolonne) in der ersten S-Box wuerde also in den Wert 1001 (9) umgewandelt werden. Aus 6 Bit Input entstehen dabei 4 Bit Output! Nun werden diese entstandenen 8 Nibbles (a 4 Bit) durch die Permutation P32i auf die 32 Bit endgueltigen Output der Funktion f verteilt (Bit 1 des ersten Nibbles geht zu Bit 16 des Outputs etc), also nochmal alles wild miteinander vertauscht, und das leifert f(Ri,Ki) dann dem Aufrufenden als Output zurueck. Un das war auch schon alles. So zum Lesen, ist das Ganze natuerlich irre kompliziert, aber im Programm sieht man recht bald, was so vor sich geht... AUFWAND DES DEA Wie man anhand des Technischen Beschriebs von vorher wohl merkt, ist die Realisierung mit rein softwaremaessigen Mitteln verhaeltnissmaessig rechenaufwendig. Es lassen sich aber, duch Aufbau von ein paar trickreichen Tabellen, viele dieser Bitvertauschungen in einfache indizierte Abbildungen und Verkuepfungen (OR's) umwandeln. - Literaturverweise Data Encryption Standard Federal Information Processing Standards (FIPS) Publication 46, US Department of Commerce / National Bureau of Standards, Jan. 15,1977 Validating the Correctness of Hardware Implementations of the NBS Encryption Standard NBS Special Pubilcation 500-20, US Department of Commerce/ National Bureau of Standards, 1977 Katzan, H. The Standard Data Encryption Algortihm, Petrocelli Books Inc, New York, 1977 BYTE Publications March 1979 The DES, An Overwiew, Robert V Meushaw Horster P. Kryptologie, Bibliografisches Institut, Reihe Informatik Bd. 47 Structure in the S-Boxes of the DES (extended abstract) E.F. Brickwell/ J.H. Moore/M.R. Purtill ... weiteres theoretisches Material beim Vortragenden erhaeltlich Meine Ur-Quelle: CCC (Dank an Bernd Fix + Frank Simon) Autor Germano Caronni fuer die Chalisti 3 (Dezember 1989) -------------------------------------------------------------------------- |
[Contrib]
[Chalisti]
[03]
Verschluesseln mit Schwerpunkt DES