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)
--------------------------------------------------------------------------
