Anhang C

In diesem Anhang werden wir uns mit ein paar Hintergrundtheorien beschäftigen, die von Java in verschiedenster Weise genutzt werden. Außerdem finden Sie einige Java-Quellen.

C.1 JAR-Archive oder wie arbeiten Komprimierungstechnologien?

Ab der Version 1.1.1 wurde in das JDK und Java die Möglichkeit integriert, so genannte JAR-Files (Java-Archive mit der Erweiterung .jar) zu nutzen. Damit wird die Datenmenge ziemlich komprimiert. In folgendem kleinen Exkurs wollen wir und ein bisschen mit der Theorie der Datenkomprimierung beschäftigen. Vielleicht wollen Sie ja mal selbst ein Komprimierungsprogramm in Java schreiben. Java bietet durch seine an C/C++ angelegte Programmierungsmöglichkeiten auf Bit-Ebene durchaus die Voraussetzung dafür. Programmiersprachen, die diese Programmierungsmöglichkeiten auf Bit-Ebene nicht so direkt zur Verfügung stellen (z.B. PASCAL) erschweren die Erstellung eines Komprimierungsprogramms wiederum.

C.1.1 Komprimierungsverfahren und Programme

Nahezu jedem Computer-Anwender sind schon verschiedene Komprimierungsprogramme über den Weg gelaufen. Insbesondere Java-Anwendern, denn das JDK wird wie nahezu jedes Softwareprodukt komprimiert verteilt. Im Internet ist es sowieso nur noch möglich, die Daten komprimiert zu verschicken, denn die Datentransferraten sind immer niedrig. JAR-Archive sind daher ein weiterer großer Schritt in Richtung Akzeptanz von Java-Technologie im Internet.

Wir werden uns bei den zu komprimierenden Daten auf Zeichendarstellungen in einem Byte beschränken, was jedoch keine Beschränkung der Allgemeinheit darstellt.

Zuerst stellt sich die Frage, was Komprimierung von Daten heißt? Es bedeutet, Dateien oder Programme zu verkleinern, ohne Informationen zu verlieren. Eine Information, die in der Ursprungsdatei vorhanden ist, muss auch in der verkleinerten Datei wiederzufinden sein. Zusätzlich sollte die verkleinerte Datei auch alle Informationen enthalten, um die Ursprungsdatei (bzw. die vollständige Ursprungsinformation) wieder vollständig herzustellen. Die Anzahl der Bytes (Bits), die zur Darstellung von Daten benötigt wird, soll verringert werden.

Intuitiv ist klar, dass man eine Datei nur bis zu einer gewissen Grenze verkleinern kann, ohne Informationen zu verlieren (wenn es keine Grenze gäbe, könnte man eine Datei immer wieder komprimieren, hätte zum Schluss noch ein Bit übrig und trotzdem noch alle Informationen). Neben der Verkleinerung der Datenmenge ist die Datensicherheit ein Grund für Komprimierung, denn komprimierte Daten lassen sich nicht so ohne Weiteres entschlüsseln - gerade in der Datenfernübertragung. Noch besser sind natürlich spezielle Kodierungsprogramme, die in ihrer Arbeitsweise Komprimierungsprogrammen aber durchaus ähnlich sein können (zumindest einige der Kodierungstechniken).

Einen wesentlichen Nachteil erkauft man sich mit Datenkomprimierung. Entweder man arbeitet mit so genannten Online-Komprimierern, die prinzipiell während des Lesen und Schreibens von Daten komprimieren bzw. entkomprimieren. Dadurch hat man deutlich längere Lese-/Schreibzugriffe auf die Datenträger. Oder man nimmt Packer, die manuell aufgerufen werden und dann die angegebenen Daten komprimieren/dekomprimieren, unabhängig von den normalen Lese-/Schreibzugriffen. Eine dritte Variante sind die so genannten EXE-Komprimierer, die direkt in den Hauptspeicher entpacken, wo das Programm dann sofort gestartet wird. In jedem Fall bedeutet die Verwendung von Packern Zeitaufwand.

Das gleichzeitige Verwenden von verschiedenen Komprimierungsvorgängen macht meist keinen Sinn, da bereits einmal komprimierte Daten in der Regel nicht weiter komprimiert werden. Desgleichen macht die nacheinander folgende Anwendung von verschiedenen Komprimierungsverfahren wenig Sinn. Im Gegenteil - es liegt in der Natur der Sache (wir werden es gleich sehen), dass eine mehrfache Verwendung von Komprimierungsprogrammen meist zu einer erheblichen Vergrößerung der Datenmenge führt.

Welche verschiedenen Methoden zum Komprimieren von Daten gibt es nun? Die Art der Datenkompression ist stark abhängig von der zu verarbeitenden Datei. Nicht jede Komprimierungsart hat bei jedem Typ von Datei den gleichen Erfolg. Bei Dateien, wo sich bestimmte Informationen oft wiederholen, lassen sich recht schnell ordentliche Komprimierungsraten (Komprimierungsrate in % = Größe der Ursprungsdatei / Größe der komprimierten Datei, also je kleiner, desto besser) erzielen, indem man nur angibt, wie oft sich ein Zeichen wiederholt.

Beispiel: Eine Datei, die wie folgt aussieht

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

benötigt 40 Byte (sie besteht aus 40 mal dem Zeichen X).

Die gleiche Information lässt sich auch in X40 verschlüsseln. Diese Datei wäre nur 3 Byte groß. Das Komprimierungsprogramm müsste in der zu verkleinernden Datei nur die Zahl der sich wiederholenden Zeichen ermitteln und in die Zieldatei diese Zahl und einmal das gefundene Zeichen schreiben. Die Entkomprimierung läuft genau umgekehrt. Sobald das Entkomprimierungsmodul eine Zahl findet, schreibt es das vorherige Zeichen in dieser Anzahl in die Zieldatei. Ein entsprechender Algorithmus muss nur in das Komprimierungsprogramm integriert werden.

Dieses Verfahren hat zwei ganz offensichtliche Schwachstellen. Die zu komprimierende Datei darf keine Zahlen enthalten - wie sollte sonst das Entkomprimierungsmodul unterscheiden können, ob die gefundene Zahl die Mengenangabe oder das Zeichen ist. Außerdem wird z.B. kaum eine Textdatei so viele Buchstabenwiederholungen haben, dass dieses Verfahren Erfolg hat - erst ab drei gleichen Buchstaben hintereinander würde die Datei kleiner. Daran sieht man bereits, dass dieses Verfahren i.a. nicht geeignet ist, um beliebige Dateien zu verkleinern. Es hat trotzdem eine große Bedeutung. Grafikformate - z.B. PCX vom Windows-Programm Paintbrush - verwenden ein solches Verfahren, sind also bereits gepackt. Es wird eine gute Komprimierungsrate erzielt, wenn große einfarbige Flächen zu speichern sind.

Für reine Textdateien lässt sich auch ein funktionierendes Komprimierungsmodell entwerfen. Bekannterweise können auf dem PC alle verfügbaren Zeichen im ASCII-Code gespeichert werden. Der Unicode von Java kann selbstverständlich genauso als Grundlage dienen (alles mal 2). Wir bleiben aber wie schon angedeutet ohne Beschränkung der Allgemeinheit beim ASCII-Code. Ein Zeichen im ASCII-Code hat genau die Länge von 1 Byte, d.h. 8 Bit. Damit lassen sich im Dualsystem 256 (2 hoch 8) Zeichen darstellen, eben den Umfang der ASCII-Tabelle. Wenn nun maximal 128 (2 hoch 7) Zeichen gespeichert werden sollen, kommt man im Prinzip auch mit 7 Bit aus. Das achte Bit ist bei einer geeigneten Kodierung (d.h. Umsortierung oder Verschiebung) immer 0. Damit könnte man alle reinen Textzeichen (mit Umlauten, Punkt, Komma usw.) zuordnen. Eine reine Textdatei lässt sich mit einem solchen Programm schnell und einfach auf 87,5 % der Ursprungsgröße reduzieren. Aber wie gesagt, dieses Verfahren macht nur für Dateien Sinn, die maximal 128 verschiedene Zeichen beinhalten. In der Praxis wird dieses Verfahren so gut wie nicht verwendet. Allerdings steckt in diesem Modell bereits ein wichtiger Hinweis auf einen wesentlichen Bestandteil von allgemeinen Komprimierungsprogrammen. Zeichen müssen nicht unbedingt in einem Byte (oder 2 Byte beim Unicode) gespeichert werden, sondern können durchaus in einer geringeren Zahl von Bits verschlüsselt werden - natürlich auch in einer größeren Zahl von Bits. Eine erste Idee könnte sein, bei einem Zeichen, das eine gewisse Zahl von führenden Nullen in seinem Code hat, nur ab dem ersten von Null verschiedenen Bit zu speichern. Wenn z.B. das Zeichen A den ASCII-Code 65 hat, wird das binär als 1000001 dargestellt. Also in 7 Bit. Das Zeichen B mit dem ASCII-Code 66 ist binär 1000010. Wenn man sie nun ohne die führenden Nullen hintereinander wegschreibt, erhält man eine reduzierte Größe der Datei. Das Problem ist aber, dass man nicht weiß, wie viel Bit beim Entkomprimieren einzulesen sind, um den vollständigen Code eines Zeichens zu erhalten. Die kodierte Darstellung ist bei diesem Verfahren nicht eindeutig.

Beispiel: 100101 kann ein Zeichen mit dem ASCII-Code 37, aber auch zwei verschiedene Zeichen mit den ASCII-Codes 4 (100) und 5 (101) bedeuten.

Eine Darstellung in der Form 100 101 wäre eindeutig, da hier das Leerzeichen als Begrenzer für ein Zeichen dient. Da aber jedes in Frage kommende Zeichen in einer beliebigen Datei auch vorkommen kann und natürlich auch kodiert werden müsste (auch das Leerzeichen, das in einer Binärdatei natürlich nichts zu suchen hat!), hat man wieder ein ähnliches Problem wie bei der Verschlüsselung von Grafikdateien. Es darf mindestens ein Zeichen - eben der Begrenzer einer Zeichendarstellung - nicht in der Quelldatei vorkommen. Begrenzer eignen sich also nicht, um bei verschieden langer Darstellung von Zeichen die einzelnen Zeichen voneinander zu trennen. Welche Lösung gibt es nun für dieses Problem?

Es werden genau dann keine Begrenzer benötigt, wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt, wenn also nach dem Einlesen von jedem Bit klar ist, ob es noch zur Bitfolge des bis dahin gelesenen Zeichens gehört oder bereits der Anfang eines neuen Zeichens ist. Das allgemeine Verfahren, um einen solchen Code zu bestimmen, wurde 1952 von D. Huffman entdeckt und wird nach ihm die Huffman-Kodierung genannt Die meisten gängigen Komprimierungsverfahren arbeiten mit diesem (meist leicht modifizierten) Huffman-Algorithmus.

C.1.2 Der Huffman-Algorithmus

Bei der Erzeugung des Huffman-Codes hat man im Wesentlichen zwei Probleme zu lösen. Zum einen will man einen kürzeren Code erzeugen und zum anderen soll die Darstellung von Zeichen in dem neuen Code eindeutig sein. Klar ist, dass eine Datei, die nur aus tausend mal dem Buchstaben A besteht, auch in der normalen Form 1000 Byte groß ist. Wenn man nun irgendwo definiert, dass der Buchstabe A binär durch 0 dargestellt werden soll, kann diese Datei in 1000 Bit - tausend mal Null - dargestellt werden. Dies ist viel kleiner und eindeutig, solange bekannt ist, dass eine 0 das Zeichen A bedeutet. Komme nun noch der Buchstabe B genau einmal in dieser Datei vor. Die Datei wäre 1001 Byte groß in der normalen Darstellung. Das Zeichen B sei binär in der Form 1111111111111111 verschlüsselt, also in einer Zeichenkette von 2 Byte. Die kodierte Darstellung ist damit 1016 Bit groß (1000 x 1 Bit + 1 x 16 Bit), also immer noch bedeutend kleiner und eindeutig. Solange man beim Einlesen der kodierten Datei eine 0 findet, hat man einmal das Zeichen A; sobald eine 1 auftritt, muss man bis zur nächsten 0 lesen. Nachdem 16 mal eine 1 vorkam, ist eindeutig dieser Bitfolge das Zeichen B zugeordnet.

Aber wer sagt denn, dass das Zeichen A mit Null und das Zeichen B in der Form 1111111111111111 zu verschlüsseln ist? Man kann ja auch auf die Idee kommen, genau umgekehrt zu verfahren. Oder man hat eine Datei, in der das Zeichen A nur einmal und das Zeichen B 1000-mal vorkommt. Damit wäre die verschlüsselte Datei immer noch eindeutig, aber auf Grund der unglücklichen Wahl des Verschlüsselungsmechanismus ungefähr doppelt so groß wie die Ursprungsdatei (1000 x 16 Bit + 1 x 1 Bit).

Es erscheint also äußert sinnvoll, häufig vorkommende Zeichen in einem kürzeren und selten vorkommende Zeichen in einem längeren Code zu verschlüsseln, unter Umständen auch in einem Code, der mehr als ein Byte groß ist, solange das zugehörige Zeichen nur »selten genug« vorkommt.

Genau dieses ist der erste Schritt beim Erstellen des Huffman-Codes. Es ist in der zu verschlüsselnden Datei die Häufigkeit jedes Zeichens zu ermitteln. Diese bilden dann eine Häufigkeitsmenge aus lauter so genannten Knoten. Der nächste Schritt besteht darin, dem am häufigsten vorkommenden Zeichen den kürztest möglichen Code zuzuordnen, dem seltensten Zeichen den optimalen längsten Code. Zeichen, die überhaupt nicht in der Ursprungsdatei vorkommen, werden nicht verschlüsselt. Wie wird nun ein optimaler und eindeutiger Code ermittelt? Zunächst werden die zwei Zeichen mit den geringsten (von Null verschiedenen) Häufigkeiten genommen (falls mehr als zwei Zeichen die gleiche Häufigkeit haben, kann man sich beliebig entscheiden). Diese beiden bilden einen neuen Knoten, dessen Wert die Summe der Häufigkeiten der beiden erzeugenden Zeichen ist. Danach werden die beiden erzeugenden Knoten gestrichen und der neu erzeugte Knoten in die verbleibende Häufigkeitsmenge - oder auch Menge von Bäumen - aufgenommen.

Die Zahl der Bäume hat sich um 1 reduziert. In der neuen Häufigkeitsmenge sucht man erneut die beiden Knoten mit der geringsten Häufigkeit und fährt wie oben fort. So wird Schritt für Schritt die Anzahl der Bäume reduziert (zwei entfernen und einen hinzufügen). Zum Schluss sind alle Knoten zu einem einzigen Baum verbunden. Nunmehr kann der Huffman-Code abgeleitet werden, indem man die Häufigkeiten an den untersten Knoten des Baumes durch das jeweilige zugehörige Zeichen ersetzt. Wenn man noch vereinbart, dass links in dem binären Baum dem Bit 0 und rechts dem Bit 1 entspricht, kann man jedes vorkommende Zeichen über eine entsprechende Folge darstellen. Diese Kodierung ist eindeutig und es lässt sich mit dem mathematischen Mittel der Induktion beweisen, dass keine Kodierungsstrategie zu einem besseren Ergebnis führen kann als die oben beschriebene Methode. Der Huffman-Code ist i.a. der bestmögliche Code.

Jetzt muss nur noch jedes in der Ursprungsdatei vorkommende Zeichen durch seinen neuen Code ersetzt werden. Zusätzlich muss noch irgendwo in der komprimierten Datei (im Header) für eine spätere Entkomprimierung hinterlegt werden, welcher Code welchem Zeichen entspricht. Meist werden dort noch diverse weitere statistische und technische Parameter gespeichert. Diese Maßnahme vergrößert die Datei wieder geringfügig und macht auch deutlich, dass eine Komprimierung von Dateien nur dann Sinn macht, wenn der Headerteil der komprimierten Datei nicht größer ist als der Komprimierungsfaktor. Daher würde z.B. ein erneutes Komprimieren eines bereits komprimierten Codes in der Regel keine Vorteile bringen, sondern den Code eher noch vergrößern (der neue Header muss ja noch zusätzlich gespeichert werden und der Code war ja in der Regel schon optimal).

Für Java hat dies einige unangenehme Konsequenzen. In diesen JAR-Archiven können neben .class-Dateien auch Image- und Sound-Dateien verpackt werden.

Für .class-Dateien lassen sich sehr gute Komprimierungsraten erzielen, aber Image- und Sound-Dateien sind normalerweise schon hochkomprimiert. Ein Verpacken von vielen Image- und Sound-Dateien in JAR-Dateien kann also sogar dazu führen, dass diese sogar größer ist als die Summe der einzelnen Dateien. In diesem spezielen Fall bleibt nur der Vorteil, dass die Applikation in einer einzigen HTTP-Transaktion übertragen wird und nicht in vielen einzelnen Übertragungsschritten. Statt vieler einzelner und unkomprimierter Dateien wird beim Laden aus dem Netz ein gepacktes Archiv übertragen.

Wir wollen an einem Beispiel den Huffman-Algorithmus durchsprechen. Unser zu komprimierender Beispieltext lautet wie folgt:

EXTREMER ERNST

Es sind 13 Zeichen (lassen wir einmal das Leerzeichen außer Acht) und damit wäre der Text 13 Byte groß. Nach Durchzählen der Zeichen ergibt sich, dass E viermal, R dreimal, T zweimal und alle anderen Zeichen einmal vorkommen. Dies kann beispielsweise eine einfache Java-Routine leicht lösen.

Verfolgen wir auf unser Beispiel bezogen unsere einzelnen Schritte zur Erstellung eines Huffman-Codes. Die häufig vorkommenden Zeichen sollen den kürzesten Code, die seltener vorkommenden den längeren Code bekommen. Der Code muss zudem eindeutig sein, denn nur auf Grund einer Eindeutigkeit lässt er sich wieder eindeutig entkomprimieren. Führen wir also diesen Schritt beim Huffman-Verfahren in unserem Beispiel durch.

Die Anzahl der jeweiligen Zeichen (die Häufigkeitsmenge) - ist in unserem Beispiel (4, 3, 2, 1, 1, 1, 1). Wir versuchen also, dem am häufigsten vorkommenden Zeichen (E, da es viermal vorkommt) den kürztest möglichen Code zuzuordnen, dem seltensten Zeichen den optimalen längsten Code (wir habe 4 Zeichen zur Auswahl, die jeweils nur einmal vorkommmen - da müssen wir uns gleich entscheiden). Zunächst nehmen wir zwei der Zeichen mit den geringsten (von Null verschiedenen) Häufigkeiten. Da wir 4 Zeichen mit gleicher Häufigkeit haben, kann man sich beliebig entscheiden. Die beiden ausgewählten Zeichen bilden einen neuen Knoten, dessen Wert die Summe der Häufigkeiten der beiden erzeugenden Zeichen ist. Danach werden die beiden erzeugenden Knoten gestrichen und der neu erzeugte Knoten in die verbleibende Häufigkeitsmenge aufgenommen. In unserem Beispiel sind es (eine willkürliche Auswahl unter den 4 Kandidaten mit der Häufigkeit 1) N und M. Die neue Häufigkeitsmenge sieht dann so aus: (4, 3, 2, 2, 1, 1). Die Zahl der Bäume hat sich um eins reduziert, denn es sind offensichtlich nur noch 6 Einträge in der Häufigkeitsmenge (gegenüber 7 am Anfang). In der neuen Häufigkeitsmenge sucht man erneut die beiden Knoten mit der geringsten Häufigkeit (in unserem Fall S und X, denn die haben noch den Häufigkeitswert 1 - das Tupel NM hat nun den Häufigkeitswert 2) und fährt fort, die Anzahl der Bäume zu reduzieren. Zum Schluss sind alle Knoten zu dem Baum verbunden, den wir unten sehen. Leiten wir jetzt den Huffman-Code ab. Wir verfolgen in dem binären Baum von der Wurzel (W) den Weg zu jedem Zeichen. Nach der oben getroffenen Vereinbarung ist eine linke Abzweigung an einem Konten dem Bit 0 zugeordnet und rechts dem Bit 1. Um zu dem Zeichen E zu kommen, müssen wir von der Wurzel aus zweimal links verzweigen. Daraus folgt zweimal das Bit 0. Die Kodierung für das häufigste Zeichen ist nur 2 Bit groß, was einer (eindeutigen) Komprimierung auf 25 % entspricht.

Nehmen wir Zeichen S. Dies ist eines der Zeichen, die am seltensten vorkommen. Der Weg von der Wurzel aus ist links, rechts, rechts, links (= 0110), eindeutig und mit 4 Bit immer noch halb so groß wie die orginale ASCII-Codierung in einem Byte. Wenn Sie sich den Baum ansehen, werden Sie anhand der Wege und Verzweigungen von der Wurzel zu einem Zeichen immer die eindeutige Huffman-Verschlüsselung des Zeichens ableiten können.

(Alle Striche sollen von einem Knoten (Zahl) zum anderen verbunden sein)

W=Wurzel

E   N   M   S   X T     R
                         
4   1   1   1   1 2     3
|   \   /   \   / |     |
|     2       2   |     |
|     \       /   |     |
|       \   /       \   /
  \       4           5  
    \   /           /    
      8           /      
        \       /        
          \   /          
            13 = W        

Tabelle C.1:   Ein Huffman-Baum

Daraus ergibt sich folgender Code für die vorkommenden Zeichen - von der Wurzel W aus gesehen:

E = 00
N = 0100
M = 0101
S = 0110
X = 0111
T = 10
R = 11

C.1.3 Selbstextrahierende Programme

Eine Besonderheit in der Welt der Komprimierung sind die so genannten selbstextrahierenden Programme oder auch SFX-Archive. Diese sind im Prinzip lauffähige Programme, deren einziger Zweck es ist, bei Aufruf die in dem Archiv komprimierten Daten zu extrahieren. Im Header dieser Archive ist also in lauffähiger Form die vollständige Information enthalten, wie die komprimierten Daten zu extrahieren sind, der Rest ist die »normale« gepackte Datei. Die meisten gängigen Packer sind in der Lage, selbstextrahierende Archive zu erzeugen. Die Vorteile liegen auf der Hand. Zum einen ist die Anwendung einfach. Keine kryptischen Befehlszeilen, nur das Programm starten. Zum anderen muss man nicht im Besitz des Komprimierungsprogramms sein, um die Daten zu extrahieren. Da aber die meisten Packer Sharwareprodukte sind und man sie sich nahezu von überall, ob aus CompuServe, von diversen CDs mit Shareware oder auch von kommerziell vertriebenen Softwarepaketen besorgen kann, ist dieses eigentlich kein gewichtiges Argument. Man findet sogar inzwischen so viele gute Sharewarepacker, dass praktisch kein Markt für kommerzielle Produkte vorhanden ist. Die meisten Vertreiber von Shareware legen den verwendeten Packer mit bei. Selbstextrahierende Archive haben auch einen großen Nachteil. Sie sind einfach größer, weil eben die Extrahierungsfunktion in lauffähiger Form in jeder Datei mit gespeichert werden muss. Bei dem früher in der DOS-Welt weit verbreiteten ARJ ist das SFX-Modul ca. 15 KByte groß.

C.1.4 Wie groß ist die Reduzierung der Datenmenge?

Man kann keine allgemein gültige Aussage zur Reduzierung der Datenmenge machen, denn diese hängt massiv von den zu komprimierenden Dateien ab. So schaffen moderne Packer bei Textdateien (dazu zählen natürlich auch Java-Source-Dateien) sogar Komprimierungsraten bis zu 10 % (also nur noch 10 % der Orignalgröße), während sich DOS-Programme auch in günstigen Fällen kaum unter 50 % verkleinern lassen. Wenn die Programme mit Overlaytechnik arbeiten, wird die Rate schlechter. Auch Windows-Programme sind kritische Kandidaten für Packer. Noch schlechter sieht die Rate bei Grafikdateien aus, die sich manchmal überhaupt nicht oder im besten Fall auf 70 % komprimieren lassen - der Grund dafür ist, dass Grafikformate bereits komprimiert sind (s.o.). Java-Klassen sind als Bytecode ein Mittelding zwischen Textdateien und komprimiertem Maschinencode. Es lassen sich recht gute Komprimierungsraten erzielen. Die genauen Raten sind von der Struktur der Klasse abhängig. Sie bewegen sich zwischen 30 % und 40 %.

C.2 Wie funktionieren Verschlüsselungsverfahren?

Digitaler Datenaustausch hat Hochkonjunktur. Nicht nur HTML-Seiten und Java-Applets, auch immer mehr Daten werden nicht mehr per Papier, Fax oder Telefon verschickt, sondern mittels digitaler Datenträger oder Leitungen auf die Reise geschickt. Auch sensible Angaben, die nicht unbedingt von unbefugten Personen ausgewertet werden sollen. Denken Sie nur an Online-Banking oder Online-Shopping mit Angabe der Kreditkartennummer. Deshalb raten sämtlich Experten, die Daten vor dem Verschicken in eine Form zu bringen, die ein widerrechtliches Auswerten verhindert oder zumindest erschwert. Dies übernehmen so genannte Verschlüsselungs- oder Kryptographieprogramme bzw. speziell in Programme eingebaute Funktionen zum Kodieren.

Ursprünglich wurden Verschlüsselungsverfahren bei der Übermittlung von militärischen und diplomatischen Nachrichten eingesetzt. Schon aus der Römerzeit sind Verschlüsselungsverfahren für Nachrichten bekannt, und eine der gängigsten Verschlüsselungsalgorithmen ist nach Julius Cäsar benannt, die Cäsar-Chiffre.

Der Schutz vor unberechtigter Nutzung von Computern hat sich inzwischen auf allen Ebenen - sowohl auf Großrechnern und Client-Server-Systemen, aber auch auf Stand-Alone-PCs - durchgesetzt (wer hat es schon gerne, wenn jedermann private Dateien lesen kann?). Passwörter und Zugangsbeschränkungen zu verschiedenen Bereichen sind überall üblich. Hat ein Datenspion jedoch diese Zugangsbeschränkungen überwunden, kann er oft frei Daten auswerten.

Noch schlimmer ist die Situation, wenn Informationen ein geschlossenes Computersystem verlassen und auf die Reise zu einem anderen System gehen. Sowohl der Datenträger, der per Postweg verschickt wird, als auch die E-Mail oder die Datei, die per Internet oder einem kommerziellen Netzwerk zu einem Empfänger unterwegs ist, können relativ leicht abgefangen und ohne Spuren zu hinterlassen kopiert/analysiert werden. Eine Nachricht läuft im Internet normalerweise über mehrere Server, bis sie ihr Ziel erreicht. Verschlüsseln musst für sensible Daten unbedingt sein. Wie aber werden Daten verschlüsselt, wie arbeiten Kodierungsprogramme?

C.2.1 Verschlüsselungs- bzw. Kryptographieprogramme

Um die Arbeitsweise von Verschlüsselungsprogrammen zu verstehen, sollte man sich erst einmal deutlich machen, was das Ziel der Verschlüsselung sein soll. Geheimhaltung! Dazu bedienen sich die Kodierungsprogramme einer recht alten mathematischen Wissenschaft, der Kryptologie. Diese Wissenschaft besteht aus zwei sich ergänzenden Teilgebieten, der Kryptographie und der Kyptoanalyse. Vereinfacht gesagt, versucht die Kryptographie Systeme für eine geheime Kommunikation zu entwickeln, während das Ziel der Kryptoanalyse die Entschlüsselung derselben ist. Man kann sich der Kryptologie nähern, indem man sie sich als eine Art Spiel vorstellt.

Allgemeine Spielregeln

Wie lauten nun die Spielregeln der Kryptologie, was ist das Ziel? Das Spiel besteht im Allgemeinen darin, dass ein Spieler - der Sender - Daten zu einem zweiten Spieler - dem Empfänger - übermitteln will. Es kann sich durchaus um dieselbe Person handeln, z.B. dann, wenn Daten auf einem Rechner geschützt werden sollen und der Sender/Empfänger zwischenzeitlich die Daten aus dem Augen verliert (Feierabend oder so). Der Sender nimmt die zu übermittelnden Daten, den Quelltext, und wandelt sie in eine geheime Form, den Chiffretext, um. Diese Umwandlung erfolgt mit einer geeigneten Verschlüsselungsmethode und zugehöriger Verschlüsselungsparametern. Nach der Umwandlung wird die Botschaft - der Chiffretext - auf den Weg zum Empfänger geschickt (bzw. auf dem Rechner bis zum nächsten Laden abgelegt). Wenn der Empfänger nun die erhaltene Botschaft lesen will, müssen ihm sowohl die zur Verschlüsselungsmethode passende Entschlüsselungsmethode als auch die Verschlüsselungsparameter bekannt sein. Mit diesen Angaben kann er dann den Chiffretext in den Quelltext zurückwandeln.

Ein weiterer Mitspieler - der Kryptoanalyst (der verschieden von Sender und Empfänger sein sollte, sonst ist das Spiel langweilig) - versucht nun, die Daten auf dem Weg vom Sender zum Empfänger abzufangen und zu analysieren. Dazu muss er zum einen die Methode, zum Anderen die Parameter herausfinden, um dann den Chiffretext wieder in den Quelltext zu übersetzen.

Ein solches Spielsystem wird in der Informatik ein Kryptosystem genannt.

Sicherheit contra Ökonomie

Einfache und komplexe Verschlüsselungsverfahren unterscheiden sich im Wesentlichen durch die Anzahl und die Komplexität ihrer Verschlüsselungsparameter. In der Regel gilt, ein Kryptosystem ist umso sicherer, je komplexer der Verschlüsselungsparameter ist oder je mehr Verschlüsselungsparameter vorhanden sind.

Bei mehreren Parametern wird nach Anwendung des ersten Parameters ein Zwischencode erzeugt, auf den dann der folgende Parameter angewendet wird. Das Verfahren wird so oft wiederholt, bis alle Parameter abgearbeitet sind. Bei der Dekodierung werden die Parameter dann in umgekehrter Reihenfolge angewandt.

Allerdings wird bei komplexen Verfahren auch die Bedienung immer komplizierter, zeitaufwändiger und immer unökonomischer. Ähnlich wie bei einem Zahlenschloß mit immer mehr Nummern. Die Frage nach Aufwand und Nutzen ist von zentraler Bedeutung. Im Prinzip ist es möglich, Kryptosysteme zu entwickeln, die nahezu unmöglich zu knacken sind (denken Sie im Extremfall an ein Zahlenschloss mit vielen Millionen Zahlen). Eine Kodierung und die - berechtigte - Dekodierung einer Botschaft wäre allerdings mit einem erheblichen Aufwand verbunden.

Auch einfache Verschlüsselung schützt

Jedoch auch einfache Methoden schützen bereits Daten. Sogar dann, wenn der Kryptoanalyst Kenntnis von einer der beiden notwendigen Informationen hat und ihm die zweite Information fehlt. Selbst bei nur einem Verschlüsselungsparameter ist es mit einem gewissen Aufwand verbunden, diesen Parameter zu finden, und wenn er nicht über das Entschlüsselungsverfahren informiert ist, d.h. nicht im Besitz eines passenden Dekodierungsprogrammes ist, bedeutet es eine nicht unerhebliche Erschwerung bei der Auswertung des Chiffretexts. Auch hier ist ein Vergleich mit einem einfachen Fahrradzahlenschloss nicht abwegig. Für Profis zwar kein Hindernis, dagegen so einfach im Vorbeigehen lässt sich das Fahrrad von einem Laien nicht entwenden.

C.2.2 Einige Verschlüsselungsverfahren

Schauen wir uns einmal ein paar Beispiele für bekannte Verschlüsselungsverfahren an.

Cäsar-Chiffre

Eine relativ einfache und schon recht alte Verschlüsselungsmethode ist die Cäsar-Chiffre. Diese Verschlüsselungsmethode lautet wie folgt: Für jeden im Quelltext vorkommenden Buchstaben des Alphabets setze im Chiffretext einen um einen festen Parameter versetzten Buchstaben. Wenn beispielsweise im Quelltext der erste Buchstabe des Alphabets - ein A - auftaucht und der Verschlüsselungsparameter 3 ist (angeblich der von Cäsar benutzte Parameter), wird im Chiffretext der vierte Buchstabe des Alphabets - ein D - genommen, usw. Hat man einen Buchstaben vom Ende des Alphabets, wird wieder von vorne gezählt, also aus z.B. dem letzten Buchstaben des Alphabets - Z - wird in unserem Fall ein C. Die Dekodierung läuft entsprechend umgekehrt.

Dieses Verfahren ist allerdings relativ einfach zu knacken, da der Kryptoanalyst - sofern er die Methode erraten hat - nur die verwendete Konstante ermitteln muss. Da bestimmte Buchstaben in jeder Sprache mit verschiedener Häufigkeit vorkommen, ist die Bestimmung dieser Verschlüsselungskonstanten meist schnell zu bewerkstelligen. In der deutschen Sprache kommt das E am häufigsten vor und dementsprechend wird mit hoher Wahrscheinlichkeit das am häufigsten im Chiffretext vorkommende Zeichen diesem E entsprechen. Die Differenz zwischen dem häufigsten Chiffrezeichen und dem E ist als Verschlüsselungskonstante einen Test wert. Sofern der damit ermittelte Text einen Sinn ergibt, war es sehr wahrscheinlich ein Treffer.

Was tun bei binären Zeichen?

Neben der relativen Unsicherheit hat unser Cäsar-Chiffre-Verfahren bisher noch einen weiteren Makel. Bis jetzt steht noch nicht fest, wie das Verfahren bei Zeichen reagieren soll, die nicht im Alphabet vorkommen. Bei Texten auf Papier (oder Textdateien) hat dies geringe Auswirkungen, aber was ist mit allgemeinen Dateien?

Bei Zahlen ist das Verfahren leicht zu übertragen, jedoch was ist mit Sonderzeichen, Umlauten oder anderen binären Zeichen? Die Lösung dieses Problems führt über die Art, wie Zeichen auf Computern dargestellt werden - die ASCII-Tabelle oder eine entsprechende Kodierung. Statt des Alphabets wird diese Tabelle als Basis genommen, also ein Zeichen mit dem ASCII-Wert 100 bekommt in unserem Fall im Chiffretext den ASCII-Wert 103.

Bei binären Dateien - keinen reinen Textdateien - ist die einfache Cäsar-Chiffre trotzdem wirkungsvoll. Durch die bereits in der Quelldatei vorkommenden Steuerzeichen ist ein Erraten der verwendeten Konstanten extrem erschwert (das E ist wahrscheinlich nicht mehr das häufigste Zeichen des Quelltextes), selbst wenn man mit einem passenden Programm die verschlüsselte Datei analysieren kann. Wenn sich ein Kryptoanalyst ungeschickt anstellt, muss er bis zu 256 Konstanten ausprobieren.

Man kann also davon ausgehen, dass bereits das Cäsar-Chiffre-Verfahren für viele Gelegenheiten ausreicht. Damit soll dem Leichtsinn nicht die Tür geredet werden. Ganz im Gegenteil. Sämtliche sensiblen und auswertbaren oder anderweitig manipulierbare Informationen sollten - sofern die Brisanz es notwendig macht - auf jeden Fall besser verschlüsselt werden, wenn Sie über das Internet verschickt werden. Die Frage ist aber, wie kompliziert ein Verfahren überhaupt sein muss.

Wenn Sie erwarten, dass Ihre speziellen Daten gezielt abgefangen werden, sollte das Verfahren natürlich so sicher wie möglich sein. Normalerweise wird ein Datenspion jedoch einen zentralen Platz (beispielsweise einen Server) überwachen und dort mit Programmen automatisch nach interessanten Informationen suchen, etwa sämtliche Mails automatisch nach dem Schlüsselbegriff »Kreditkartennummer« durchforsten lassen. Falls die Mail nur nach der Cäsar-Chiffre verschlüsselt ist (also der ASCII-Code nur verschoben), wird der Begriff »Kreditkartennummer« schon so verstellt, dass er den automatischen Routinen nicht mehr auffällt.

Die Cäsar-Chiffre oder andere einfache Verfahren können übrigens auch dazu verwendet werden, eine kompliziertere Verschlüsselung zu verschleiern. Dabei wird das Verschlüsselungsverfahren so trickreich aufgebaut, dass es die Entschlüsselung der einfachen Variante bewusst einkalkuliert und damit eine falsche Spur legen will. Wenn der Datenspion das Verfahren geknackt hat und eine lesbare, aber uninteressante Information erhält, wird er wahrscheinlich die weitere Entschlüsselung abbrechen. In diesem Fall muss noch mindestens eine weitere Verschlüsselungsebene mit einem zugehörigen Verfahren existieren, aus der dieser Zwischencode dann weiter bearbeitet wird.

Sichere Verfahren

Dennoch, seit Cäsar ist viel Zeit vergangen, und die Cäsar-Chiffre ist auch für Binärdateien nicht die sicherste Verschlüsselungsvariante. Leistungsfähiger ist eine Methode, wo die Kodierung über Tabellen erfolgt. Bei Programmen sind diese Tabellen intern im Code gespeichert - sonst wäre es sinnlos. Es gibt keine feste Konstante, sondern jedes mögliche Zeichen des Quelltextes bekommt eineindeutig (d.h. eindeutig hin- und zurück zuzuordnen) ein anderes Zeichen aus der Tabelle zugeordnet. Auch bei dieser Methode gilt, dass sie für reine Texte über die Häufigkeit bestimmter Buchstaben bzw. Buchstabenpaare zu knacken ist, bei Binärdateien ist sie entsprechend sicherer.

Die Vigenere-Chiffre

Eine recht sichere Möglichkeit Daten zu verschlüsseln, ist die Vigenere-Chiffre, eine Verallgemeinerung der Cäsar-Chiffre. Eine sich wiederholende Folge von Zeichen bildet einen Schlüssel, aus dem der Verschlüsselungsparameter für jedes Zeichen des Quelltextes einzeln berechnet wird (Addition des Quellzeichens und des Schlüsselzeichens).

Beispiel mit ASCII-Werten:

Der Schlüssel bestehe aus 4 Zeichen - 100 101 102 103.

Quelltext: 50 54 100 50 100 54 100 100
Schlüssel (periodisch): 100 101 102 103 100 101 102 103
Chiffretext: 150 155 202 153 200 155 202 203

Tabelle C.2:   Verschlüsselung nach dem Vigenere-Chiffre

Der wesentliche Vorteil dieses Verfahrens liegt darin, dass gleiche Zeichen im Quelltext (in unserem Beispiel Ord(50)) im Chiffretext unter Umständen durch unterschiedliche Zeichen dargestellt werden (Ord(150) oder Ord(153)), je nach Position im Quelltext.

Je länger der Schlüssel ist, d.h. je weniger Perioden auftreten, desto sicherer wird das Verfahren, aber auch gleichzeitig unökonomischer. Im Extremfall ist der Schlüssel genauso lang, wie der zu verschlüsselnde Text. Dieses Verfahren wird dann Vernam-Chiffre genannt und ist eines der sichersten - bekannten - Kryptoverfahren, das von vielen wichtigen Institutionen benutzt wird, sofern die Brisanz der Botschaft den Aufwand rechtfertigt.

Wie gelangt ein Schlüssel zum Empfänger?

Neben der Übermittlung einer Nachricht vom Sender zum Empfänger gibt es das Problem, wie man den Schlüssel sicher übermittelt. Wenn der Schlüssel geknackt oder gestohlen wurde, nützt das beste Verfahren nichts. Daher muss der Schlüssel getrennt von der Nachricht über einen möglichst sicheren Weg zum Empfänger gelangen. Oder aber, er wird ganz öffentlich verteilt.

C.2.3 PGP oder wie Java verschlüsselt

Wie ist der eben angeführte Widerspruch zu klären? Eine relativ neue und zuverlässige Verschlüsselungsvariante arbeitet mit zwei Schlüsseln, einem privaten Schlüssel, der nur beim Sender verbleibt, und einem öffentlichen Schlüssel, der verschickt wird. Diesen zweiten Schlüssel darf jeder kennen, denn er wird ausschließlich zum Kodieren einer Nachricht benutzt. Zum Dekodieren kann er nicht verwendet werden. Die Folge ist, dass bis jetzt nur der Empfänger des Schlüssels an den Sender des Schlüssels eine kodierte Botschaft senden kann, die ausschließlich dieser dann mit seinem privaten Schlüssel dekodieren kann. Will der potenzielle Sender eine kodierte Nachricht verschicken, muss er also erst von dem potenziellen Empfänger den öffentlichen Schlüssel erhalten.

Dieses Verfahren hat den riesigen Vorteil, dass der Dekodierungsschlüssel niemals verteilt werden muss und es äußerst sicher ist. Es lässt sich auch mit den oben genannten Methoden kombinieren. Man muss aber einen großen Aufwand mit dem Verschicken und Verwalten der verschiedenen Kodierungs-Schlüssel treiben.

PGP (Pretty Good Privacy) nutzt beispielsweise das Zweischlüsselsystem (öffentlicher und privater Schlüssel) mit einem 1024 Bit-Schlüssel. In der Vergangenheit gab es bzgl. der Verwendung eines längeren Schlüssels erhebliche Probleme, denn in den USA fallen Verschlüsselungssysteme unter die Exportbestimmungen für militärische Geheimnisse. Aber auch in Deutschland gibt es eine Diskussion, inwieweit überhaupt Verschlüsselungsverfahren benutzt und vertrieben werden dürfen, die interessierte Behörden nicht nach Belieben entschlüsseln können. Offizielles Argument für die Gegner von sicheren Verschlüsselungsverfahren ist, dass auch kriminelle Kreise solche Verfahren nutzen könnten.

C.2.4 Die heutigen Standard-Algorithmen

In der heutigen Verschlüsselungstechnik werden im Wesentlichen drei verschiedene Standards verwendet:

DES

Der Data Encryption Standard (DES) stammt aus den Siebzigerjahren. Zur Verschlüsselung werden 56 Bit verwendet, was zu einer Anzahl von 2 hoch 56 Schlüsseln führt. Es handelt sich um einen symmetrischen Algorithmus mit einem frei wählbaren Schlüssel zum Ver- und Entschlüsseln der Daten. Mithilfe dieses Schlüssels wird der Orginaltext jeweils in 64-Bit-Blöcke umgewandelt. Dies geschieht durch Substitution und Permutation, also das Ersetzen und Vertauschen einzelner Bits nach festen Regeln. In 16 Durchläufen wird die eine Hälfte der Daten mit einem auf 48 Bit reduzierten Schlüssel unter Verwendung einer XOR-Funktion chiffriert, um anschließend mit der anderen Hälfte der Daten verknüpft zu werden. Für jeden Durchlauf wird ein neuer Schlüssel erzeugt.

IDEA

Der Intenational Data Encryption Algorithm (IDEA) ist ziemlich neu (Beginn der Neunzigerjahre). Er basiert auf einem 128-Bit-Schlüssel, bietet also 2 hoch 128 Möglichkeiten zur Erzeugung des Verschlüsselungscodes. Wie bei DES werden auch hier jeweils 64 Bits der Daten verschlüsselt. IDEA teilt die Originaldaten jedoch nicht in zwei Hälften, sondern benutzt vier Viertel zu je 16 Bit. Diese Blöcke werden mit einem Teil des 128-Bit-Schlüssels in acht Durchläufen verknüpft. Nach den letzten Durchlauf werden die Viertel in einem neunten Durchgang noch einmal mit vier weiteren Teilschlüsseln bearbeitet. Der Schlüssel wird durch Rotation der Bits um 25 Stellen jeweils neu festgelegt.

RSA

RSA (die jeweils ersten Buchstaben der Nachnamen der Erfinder Rivest, Shamir und Adleman) stammt wie DES aus den Siebzigerjahren. RSA beruht auf der Zerlegung großer Zahlen in ihre Primfaktoren und Moduloverfahren bezüglich dieser Primzerlegung. Die Originaldaten werden nicht in Blöcke unterteilt, sondern wie eine einzige große Zahl behandelt. Es gibt bei dem Verfahren einen zusammengesetzten öffentlichen Schlüssel zum Verschlüsseln und einen privaten Schlüssel zum Entschlüsseln.

C.2.5 Eine kleine Abschlussbemerkung zum Thema

Es ist zwar eine Binsenweisheit, aber jeder sollte sich klar darüber sein, dass es keine absoluten Schutz gegen eine unberechtigte Dekodierung von Informationen gibt. Auch der beste Code ist zu knacken. Durch Zufall. Mit System. Oder mit viel Zeit und genau das ist der springende Punkt: Eine Information hat nur innerhalb einer gewissen Zeitspanne einen Wert. Je länger eine Dekodierung dauert, umso wahrscheinlicher wird die Information keinen Wert mehr für den Kryptoanalyst haben.

C.3 Von der Dezimalrechnung abweichende Rechenarten

Vielen Lesern dürfte Binär-, Oktal- und Hexadezimalrechnung vertraut sein. Dennoch soll ein kleiner Exkurs noch einmal die Grundlagen diskutieren.

Normalerweise nutzt man in der Mathematik die so genannte Dezimalrechnung. Dabei stehen 10 verschiedene Symbole zur Darstellung einer Zahl zur Verfügung: die bekannten Zahlen von 0-9. Dies ist aber relativ willkürlich und auf keinen Fall zwingend. Das in der Computerwelt überall verwendete Binärsystem ist das bekanntete Beispiel.

C.3.1 Binärrechnung

Die Binärrechnung soll nur ganz kurz angedeutet werden. Bei Verwendung der Basis 2 können dementsprechend nur 2 Zustände in einem Zeichen kodiert werden: 0 und 1. Wenn mehr Zeichen dargestellt werden sollen, muss man mehr Stellen nehmen. Das ist im Dezimalsystem (und anderen Systemen wie dem Oktal- oder das Hexadezimalsystem) genauso, was man oft deshalb nicht zur Kenntnis nimmt, da es uns selbstverständlich erscheint (Zahlen, die größer als 9 sind, werden zusammengesetzt: 10, 11, 23456 usw.).

Hier folgt eine kleine Tabelle mit den wichtigsten Umrechnungen aus dem Dezimalsystem in das Binärsystem.

Dezimaldarstellung Binärdarstellung
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
16 10000
32 100000
64 1000000
128 10000000
255 11111111

Tabelle C.3:   Dezimal versus binär

C.3.2 Oktalrechnung

Die oktale Darstellung von Zahlen ist nicht so geläufig wie die binäre Darstellung. Allerdings besteht von der Logik her kein wesentlicher Unterschied. Sämtlich Werte werden nur zur Basis 8 dargestellt. Es gibt dementsprechend 8 Zustände, die in einem Zeichen kodiert werden: 0 bis 7. Ab der Zahl 8 erweitert man um eine Stelle, ab der Zahl 64 wieder um eine Stelle usw. Hier folgt eine kleine Tabelle mit den wichtigsten Umrechnungen aus dem Dezimalsystem in das Oktalsystem.

Dezimaldarstellung Oktaldarstellung
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
16 20
17 21
18 22
63 77
64 100
511 777
512 1000
4096 10000
32768 100000

Tabelle C.4:   Dezimal versus oktal

C.3.3 Hexadezimalrechnung

Die Hexadezimalrechnung ist meist sogar geläufiger als die oktale Darstellung, obwohl hier das Problem besteht, dass mit den herkömmlichen Zahlen 0-9 nicht genug Zeichen zur Darstellung sämtlicher Zeichen der hexadezimalen Darstellung zur Verfügung stehen. Java stellt einer hexadezimalen Darstellung von Zahlen immer ein 0x (oder auch 0X) voran. Sämtlich Werte werden hier nun zur Basis 16 dargestellt. Es gibt dementsprechend 16 Zustände, die in einem Zeichen kodiert werden: 0 bis 9 und noch 6 weiteren Zeichen, die das Dezimalsystem nicht mehr liefert. Man weicht auf das Alphabet aus und verwendet für die fehlenden 6 Zeichen Buchstaben. Meist nimmt man Großbuchstaben, aber Kleinbuchstaben gehen im Prinzip auch. Nach dem Zeichen F, das der Dezimalzahl 15 entspricht, erweitert man um eine Stelle, nach dem Zeichen FF - der Zahl 255 - wieder um eine Stelle usw. Hier folgt eine kleine Tabelle mit den wichtigsten Umrechnungen aus dem Dezimalsystem in das Hexadezimalsystem.

Dezimaldarstellung Hexadezimaldarstellung
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 A
11 B
12 C
13 D
14 E
15 F
16 10
17 11
18 12
19 13
20 14
21 15
22 16
23 17
24 18
25 19
26 1A
27 1B
28 1C
29 1D
30 1E
31 1F
32 20
254 FE
255 FF
256 100
4095 FFF
4096 1000
65535 FFFF
65536 10000

Tabelle C.5:   Dezimal versus hexadezimal

C.4 Die Theorie des Zweierkomplements bei ganzen Zahlen

Ganzzahlige Variablen werden in Java allesamt als Zweierkomplement-Zahlen mit Vorzeichen verwendet. Zweierkomplement ist eine Methode, um negative ganze Zahlen durch Bits darzustellen. Am einfachsten wird eine Erklärung anhand eines Beispiels. Dabei soll ohne Beschränkung der Allgemeinheit ein Datentyp mit 8 Bit (Datentyp>byte) herangezogen werden.

Jede ganze Zahl wird auf binärer Ebene wie folgt dargestellt.

DezimalZahl =           bit8*(2 hoch 7) + bit7*(2 hoch 6) + 
          bit6*(2 hoch 5) + bit5*(2 hoch 4) + bit4*(2 hoch 3) +
          bit3*(2 hoch 2) + bit2*(2 hoch 1) + 
          bit1*(2 hoch 0)

Beachten Sie, dass (2 hoch 0) = 1 gilt (und nicht = 0)!

Beispiele:

3 = 00000011 = 0*(2 hoch 7) + 0*(2 hoch 6) + 0*(2 hoch 5) 
+ 0*(2 hoch 4) + 0*(2 hoch 3) + 0*(2 hoch 2) 
+ 1*(2 hoch 1) + 1*(2 hoch 0) 
= 0 + 0 + 0 + 0 + 0 + 0 + 2 + 1

5 = 00000101 = 0*(2 hoch 7) + 0*(2 hoch 6) + 0*(2 hoch 5)
+ 0*(2 hoch 4) + 0*(2 hoch 3) + 1*(2 hoch 2)
+ 0*(2 hoch 1) + 1*(2 hoch 0)
= 0 + 0 + 0 + 0 + 0 + 4 + 0 + 1

7 = 00000111 = 0*(2 hoch 7) + 0*(2 hoch 6) + 0*(2 hoch 5)
+ 0*(2 hoch 4) + 0*(2 hoch 3) + 1*(2 hoch 2)
+ 1*(2 hoch 1) + 1*(2 hoch 0)
= 0 + 0 + 0 + 0 + 0 + 4 + 2 + 1

Nehmen wir uns nun das Beispiel 7 vor. Die letzten drei Bit sind auf den Wert 1 gesetzt, alle davor auf den Wert 0. Wie kann man aber nun einen negativen Wert wie -7 darstellen?

Der wahrscheinlich offensichtlichste Ansatz ist wohl, ein Bit (naheliegenderweise das erste, also das am weitesten links stehende) als Vorzeichen-Bit zu verwenden. Etwa, wenn es den Wert 1 hat, die Zahl als negativ zu interpretieren und wenn es den Wert 0 hat, als positiv. Alles andere (sprich die restliche Darstellung der Zahl) bliebe gleich. Dieser Ansatz hat Einiges für sich, aber den wesentlichen Nachteil, dass in dem Fall sämtliche arithmetischen Operationen für Ganzzahlen kompliziert würden.

Die Methode der Zweierkomplement-Arithmetik stellt wesentlich einfachere Algorithmen für binäre Arithmetik und Typkonvertierung zur Verfügung. Man kann wie folgt vorgehen: Stellen Sie eine Zahl positiv da und ziehen Sie davon den Wert 1 ab.

Beispielsweise die Zahl 256, und davon 1 abgezogen ergibt 255. Binär ist 256 in 2 Byte darzustellen und sieht so aus: 0000000100000000. Davon 1 (triviale Binärdarstellung 00000001) abgezogen ergibt binär 11111111 = 255.

Uns interessiert nur, was im letzten Byte passiert ist. Übertragen wir die Situation auf das letzte Byte: 00000000 - 00000001 = 11111111

Dies heißt jetzt dezimal 0 - 1 = -1. Wir haben die Darstellung von einer negativen Zahl. Wenn wir nun den Vorgang einfach weiter fortsetzen, werden wir die Darstellung aller negativen Zahlen bekommen.

Dezimal: -1 - 1 = -2
Binär: 11111111 - 00000001 = 11111110
Dezimal: -1 - 2 = -3
Binär: 11111111 - 11111110 = 11111101
Dezimal: -1 - 3 = -4
Binär: 11111111 - 11111101 = 11111100
Dezimal: -1 - 4 = -5
Binär: 11111111 - 11111100 = 11111011

Tabelle C.6:   Binärrechnungen

Es ist offensichtlich, dass zur Darstellung einer negativen Zahl nur von der analogen positiven Zahl (dem positiven Komplement) die Zahl 1 abgezogen und dann sämtliche Bits umgedreht werden müssen.

Diese Aufteilung des Wertebereichs in negativen und positiven Anteil ist auch der Grund, warum beispielsweise in einem Byte Werte von -128 (= - 2 hoch 7) bis 127 (= + (2 hoch 7) - 1) dargestellt werden. Die Null zählt noch zum positiven Anteil. In Java hat dies dann auch die zwangsläufige Folge, dass das am weitesten links stehende Bit als Vorzeichenbit dient. Wenn das Vorzeichenbit den Wert 1 hat, dann ist der Wert negativ, sonst positiv. So ganz falsch war also unser ursprünglicher Denkansatz nicht, nur musste er ein wenig erweitert werden. Dies führt beispielsweise bei Operationen auf Byte-Variablen zu einigen auf den ersten Blick überraschenden Ergebnissen:

127+1=-128 
127+9=-120 
127+127=-2

C.5 Farbangaben in Java und JavaScript

Wenn man Farbangaben in Java und JavaScript (oder auch HTML) vornehmen will, hat man normalerweise zwei Varianten zur Definition:

C.5.1 Die direkte Angabe eines Farbnamens

Wenn Sie eine Methode, Funktion oder Variable finden, wo Farbangaben eine Rolle spielen und Sie einfach einen standardisierten Namen verwenden können, sind Sie in einer recht glücklichen Situation. Die Eingabe eines Farbnamens ist einfach - es sind die normalen, englischen Farbbezeichnungen. Da es aber noch keine standardisierten Farbnamen gibt, ist die Interpretation der Farbangabe häufig vom Darstellungsmedium - etwa einem Browser bei HTML-Seiten oder JavaScript - abhängig. Wenn das Darstellungsmedium einen Farbnamen nicht kennt, wird es sie nicht darstellen können. Außerdem gibt es nicht für jede denkbare Farbnunance (16,7 Millionen Farben) einen Namen. Flexibler ist da schon die Angabe eines hexadezimalen RGB-Werts.

C.5.2 Die Farbangabe mittels RGB-Werten in Hexadezimalform

Die hexadezimale Variante einer Farbangabe hat den Vorteil, unabhängig vom Darstellungsmedium zu sein, und es stehen im Prinzip 16,7 Millionen Farben zur Verfügung. Die Farben müssen aus hexadezimalen Angaben zu den drei Grundfarben Rot, Grün und Blau zusammengestellt werden. Dabei ist jede hexadezimale Farbdefinition 6-stellig. Die ersten beiden Stellen sind der Rot-Wert, die Stellen drei und vier der Grün-Wert und die letzten beiden Stellen beschreiben den Blau-Wert.

Eine hexadezimale Ziffer hat bekanntlich 16 Zustände. Für jeden Farbwert (Rot, Grün, Blau) stehen 2 Stellen zur Verfügung. Das macht 16 x 16 (= 256) mögliche Zustände pro Farbwert. Aus diesen 256 Farbnuancen pro Einzelfarbe ergibt sich die Gesamtzahl der Farbzustände (256 * 256 * 256 = 16777216) durch Mischen der einzelnen Farbnuancen entsprechend ihrem Anteil.

Wenn wir die RGB-Werte in dezimaler Form (jeweils 2 Byte mit hexadizmalen Werten ergeben den Wertebereich von 0 bis 255) verwenden, erhalten wir die folgenden Beispiele:

Farbe Standardfarbname Rot-Wert Grün-Wert Blau-Wert
Weiß Color.white 255 255 255
Hellgrau Color.lightGray 192 192 192
Grau Color.gray 128 128 128
Dunkelgrau Color.darkGray 64 64 64
Schwarz Color.black 0 0 0
Rot Color.red 255 0 0
Rosa Color.pink 255 175 175
Orange Color.orange 255 200 0
Gelb Color.yellow 255 255 0
Grün Color.green 0 255 0
Magenta Color.magenta 255 0 255
Cyan Color.cyan 0 255 255
Blau Color.blue 0 0 255

Tabelle C.7:   Farbangaben

C.6 Erläuterung der Kurzschreibweisen von Operatoren

Die Kurzschreibweise von Operatoren ist eines der C-Erbstücke, die sicher nicht jeder sofort eingängig findet. Wem die verkürzte Schreibweise von Operatoren nicht ganz so vertraut ist, sollen die Operatoren +=, -=, *=, /= anhand von Beispielen und ihrer ausgeschriebenen Langform erläutert werden.

Operator Beispiel Langform
+= n += 42 n = n + 42
-= n -= 42 n = n - 42
*= n *= 2 n = n * 2
/= n /= 4 n = n / 4
%= n %= 5 n = n % 5
&= n&=1 n=n&1
|= n|=1 n=n|1
^= n^=2 n=n^2
<<= n<<=1 n=n<<1
>>= n>>=2 n=n>>2
>>>= n>>>= 3 n=n>>>3

Tabelle C.8:   Kurzschreibweisen für Operatoren

C.7 Java-Quellen im Internet

Selbstverständlich ist die Java-Adresse http://java.sun.com. Aber auch jenseits davon lohnt es sich zu schauen. Hier folgen einige Quellen rund um Java.

Die angegebenen Links können sich in der Aktualität durchaus überholen und als tote Links herausstellen. Das Internet lebt halt.

Java-Quellen im Internet gibt es wie Sand am Meer. Selbstverständlich ist Sun mit seinen Töchtern die erste Wahl, wenn Sie Orginalinformationen zu Java suchen. Aber auch andere große Firmen stellen Informationen zu Java zur Verfügung, wenn sie diese Technik unterstützen. Diese Informationen sind aber fast immer in Englisch. Es gibt aber auch zahlreiche deutsche Java-Quellen im Internet. Die deutschsprachige Java-Seite - Kaffee & Kuchen - finden Sie unter http://java.seite.net/. Dort gibt es zahlreiche Informationen rund um Java. Vor allem finden Sie dort Querverweise zu den interessantesten Java-Quellen im deutschsprachigen Raum. Das Java House unter http://www.bodo.com/java.htm sollten Sie sich einmal ansehen, wenn Sie kostenlose Applets suchen, die Magdeburger Java-Seite (http://java.cs.uni-magdeburg.de/), wenn Sie eine umfangreiche Linkliste mit Dokumentationen, Tools, News, Mailing Lists, FAQs, Java-Verzeichnisse und Downloads benötigen.

Selbstverständlich bieten sich die großen Suchdienste als Einstieg zu diverse Quellen für Applets und zahlreiche weitere Java-Informationen an. Als Beispiel sei hier nur Yahoo, der Urvater der Suchmaschinen angeführt, der sogar eine spezielle Java-Seite führt (http:// www.yahoo.com/Computers_and_Internet/Programming_Languages/Java/).

Viele Anregungen zur Erstellung von eigenen Applets können Sie sich von fremden Applets holen. Da viele der Seiten mit Applets auch die Orginalquelltexte beinhalten, kann man da viel lernen. Aber natürlich auch viel Spaß haben, denn es finden sich viele schöne Programme dort.

Wenn Sie sich für Chaos-Theorie und Fraktale interessieren, ist die Seite http://www.student.nada.kth.se/~d94-rol/fractals/javaapps.html sicher sehr hilfreich. Sie finden dort eine echtzeitberechnete Juliamengenanimation, die wie die bekannteren, verwandten Apfelmännchen zu der Fraktaltheorie gehört.

Dass Java nicht unbedingt zu den Performance-Killern (positiv gemeint) gehört, muss leider zugegeben werden. Wenn Sie die Geschwindigkeit Ihres Java-Runtime-Systems, inkl. Garfikspeed, Speicher usw. testen wollen, hilft Ihnen das BenchBeans-Applet (http://www.cs.tu-berlin.de/~mondraig/english/benchbeans.html).

Sowohl optisch als auch als wissenschaftliche Demonstration sehr spannend ist der NPAC Visible Human Viewer ( http://www.npac.syr.edu/projects/vishuman/VisibleHuman.html). Dort können Sie hier einen Menschen in Form einer Simulation in Scheiben schneiden.

Basic und Java miteinander zu verbinden scheint erstmal so, als wolle man eine Ente gegen einen Ferrari antreten lassen. Zwar ist eine Ente bedeutend schöner, orgineller und praktischer, aber hat im Rennen doch keine Chance. So scheint das wohl auch mit einer Basic-Java-Verbindung zu sein. Im Ernst, da gibt es eine BASIC-Implementation in Java für diejenigen, die keine Lust haben, Java zu lernen und dennoch Java-Applets erstellen wollen. Sie nennt sich HotTea (http://www.mbay.net/~cereus7/HotTEA.html). Skurril, aber dennoch faszinierend.


© Copyright Markt+Technik Verlag, ein Imprint der Pearson Education Deutschland GmbH
Elektronische Fassung des Titels: Java 2 Kompendium, ISBN: 3-8272-6039-6 Kapitel: Anhang C