Ineluki
05.09.2004, 23:59
Da ja bei meiner Umfrage eindeutig nach mehr Contests verlangt wurde, starte ich mal mit einem einfachen, aber vielleicht fuer im LowLevel Bereich interessierte Programmierer lehrreichen Wettbewerb.
Aufgabenstellung:
Ein im Programm befindlicher beliebiger(!) Text (Ascii 8bit) soll rueckgreifend kaskadiert mit XOR (Startwert = letztes Zeichen des Textes) und BITROTATE RIGHT 4 (8 Bit) verschluesselt und danach ausgegeben (nichtdruckbare Zeichen als '.' ) werden.
Gekuert wird das Programm mit dem kuerzesten Quelltext, das Programm mit dem elegantesten Quelltext und das Programm mit dem kleinsten Maschienencode.
Der zu verschluesselnde Text sei: "Dies ist der zu verschluesselnde Text"
Das Programm sollte aber mit jedem beliebigen Text ebenfalls funktionieren.
Einsendeschluss des Quelltextes und Beispielprogrammes (moeglichst ausfuehrbar unter Windows) ist Freitag, der 10.09.2004
Bewertet wird in einer Offenen Abstimmung des Forums (Vote).
Viel Spass und Glueck dabei ...
Zum Algorithmus
1) Das erste Zeichen wird mit dem letzten Zeichen des Textes mit XOR verschluesselt, und anschliessend wird auf das Ergebnis ROTR 4 angewendet und als erstes Verschluesseltes Zeichen gespeichert.
2) Das naechste Zeichen wird mit dem im vorigen Schritt zu verschluesselnden Zeichen mit XOR Verschluesselt und darauf ROTR 4 angewendet und als naechstes verschluesseltes Zeichen gespeichert.
3) Schritt 2) wird solange wiederholt, bis alle Zeichen verschluesselt sind.
Hintergrundwissen
XOR: Exclusiv-Oder - eine Bitoperation
Alle Zahlen lassen sich bekanntlich in binaerer Darstellung als Faktoren (0 und 1) von Zweierpotenzen darstellen.
Diese sogenannten Bits stellen gleichzeitig auch Wahrheitswerte dar. Hierbei steht 0 fuer falsch und 1 fuer wahr.
Mit der BOOLSCHEN ALGEBRA koennen elementare logische Operationen mit diesen Werten durchgefuehrt werden.
Hierbei gibt es 4 elementare Operationen: NOT, AND, OR, XOR
NOT bildet die logische Umkehrung eines Bits, 0->1 , 1->0
AND verknuepft zwei Logikwerte und ist immer dann 1, wenn beide Parameter auch 1 sind.
0 AND 0 -> 0
0 AND 1 -> 0
1 AND 0 -> 0
1 AND 1 -> 1
OR verknuepft zwei Logikwerte und ist immer dann 1, wenn mindestens einer der beiden Parameter 1 ist.
0 OR 0 -> 0
0 OR 1 -> 1
1 OR 0 -> 1
1 OR 1 -> 1
XOR verknuepft zwei Logikwerte und ist immer dann 1, wen beide Parameter verschieden sind.
0 XOR 0 -> 0
0 XOR 1 -> 1
1 XOR 0 -> 1
1 XOR 1 -> 0
Da jede beliebige Zahl in Binaerfaktoren (bits) zerlegt werden kann, koennen auch beliebige Zahlen mit Boolschen Operatoren verarbeitet werden. Hierbei erfolgt die Abarbeitung bitweise, das heisst, jedes einzelne Bit der ersten Zahl wird mit dem Bit der zweiten Zahl an der selben Position vergliechen, und das Resultat als entsprechendes Bit im Ergebnis gesetzt.
Ein Beispiel:
197 XOR 57 = 252
197 entspricht 11000101b
57 entspricht 00111001b
11000101b XOR
00111001b
------------------
11111100b = 252
Die meisten Programmiersprachen unterstuetzen von Haus aus die Boolsche Algebra.
ROTR: BITROTATE RIGHT - eine Bitoperation
Auch Rotate Right ist eine Bitoperation. Hierbei werden die Bits einer Zahl in binaerer Darstellung nach Rechts geschoben, und zwar um so viele Stellen, wie hinter der Operation stehen. Bei ROTR 4 wird also vier mal um ein Bit verschoben. Ziffern, die dabei aus der begrenzten Stellenanzahl herausfallen, werden auf der andern Seite wieder hereingeschoben. Die Umkehrung stellt ROTL dar, was fuer Rotate Left steht.
Ein Beispiel
49 (8bit) ROTR 1 = 152
49 entspricht 00110001b
00110001b ROTR 1
-----------------------
10011000b = 152
Hierbei ist natuerlich wesentlich, mit wieviel stellen (bit) eine Zahl dargestellt wird. Haetten wir in unserem obigen Beispiel nicht 8 Bit verwendet, sondern die fuehrenden Nullen weggelassen (6bit), waere das Ergebnis 56 gewesen.
Einige Programmiersprachen unterstuetzen von Haus aus die Rotationsoperatoren.
Viele unterstuetzen auch die sogenannten Shift Operatoren ( Wie ROT, nur dass ausgeschobene Bits verfallen und eingeschobene Bits 0 sind. )
Kaskadierte Verschluesselung
Bei der kaskadierten Verschluesslung (insbesondere Haeufig mit XOR verwendet) wird das aktuelle Zeichen mit dem vorherigen/nachfolgenden Zeichen als Ausgangsbasis Verschluesselt. Dieses Vorgehen wird als rueckgreifend bezeichnet, wenn ein bereits verschluesseltes Zeichen (im Ausgangszustand) zur Verschluesslung verwendet wird. Im Gegensatz dazu verwendet die vorgreifende kaskadierte Verschluesslung das folgende Zeichen als Basis.
Ein Beispiel der nachgreifenden kaskadierten Verschluesslung
Der Text "ABCDE" soll nachgreifend kaskadiert verschluesselt werden. Als Startwert dient der letzte Buchstabe.
Als Verschluesslung wird in diesem Beispiel einfach die Nummer des Buchstabens (A=1, B=2) des verschluesselnden Zeichens zur aktuellen Buchstabennummer hinzuaddiert (B(2) + D(4) = F(6)).
Startwert=E
Schritt 1: A+E=F -> F
Schritt 2: B+A=C -> FC
Schritt 3: C+B=E -> FCE
Schritt 4: D+C=G -> FCEG
Schritt 5: E+D=I -> FCEGI
FCEGI entspricht ABCDE
In anderen Worten .. A wird durch E verschluesselt, B durch A, C durch B, D durch C und E durch D.
Ein Beispiel der vorgreifenden kaskadierten Verschluesslung
Der Text "ABCDE" soll vorgreifend kaskadiert verschluesselt werden. Als Endwert dient diesmal der erste unverschluesselte Buchstabe. Es wird die selbe Verschluesslung wie im vorigen Beispiel verwendet.
Endwert = A
Schritt 1: A+B=C -> C
Schritt 2: B+C=E -> CE
Schritt 3: C+D=G -> CEG
Schritt 4: D+E=I -> CEGI
Schritt 5: E+A=F -> CEGIF
CEGIF entspricht ABCDE
In anderen Worten .. A wird durch B verschluesselt, B durch C, C durch D, D durch E und E durch A.
Hinweis: Rueckgreifender und vorgreifender Algorithmus koennen ineinander ueberfuehrt werden, wenn die Laufrichtung umgekehrt und am anderen Ende begonnen wird.
Aufgabenstellung:
Ein im Programm befindlicher beliebiger(!) Text (Ascii 8bit) soll rueckgreifend kaskadiert mit XOR (Startwert = letztes Zeichen des Textes) und BITROTATE RIGHT 4 (8 Bit) verschluesselt und danach ausgegeben (nichtdruckbare Zeichen als '.' ) werden.
Gekuert wird das Programm mit dem kuerzesten Quelltext, das Programm mit dem elegantesten Quelltext und das Programm mit dem kleinsten Maschienencode.
Der zu verschluesselnde Text sei: "Dies ist der zu verschluesselnde Text"
Das Programm sollte aber mit jedem beliebigen Text ebenfalls funktionieren.
Einsendeschluss des Quelltextes und Beispielprogrammes (moeglichst ausfuehrbar unter Windows) ist Freitag, der 10.09.2004
Bewertet wird in einer Offenen Abstimmung des Forums (Vote).
Viel Spass und Glueck dabei ...
Zum Algorithmus
1) Das erste Zeichen wird mit dem letzten Zeichen des Textes mit XOR verschluesselt, und anschliessend wird auf das Ergebnis ROTR 4 angewendet und als erstes Verschluesseltes Zeichen gespeichert.
2) Das naechste Zeichen wird mit dem im vorigen Schritt zu verschluesselnden Zeichen mit XOR Verschluesselt und darauf ROTR 4 angewendet und als naechstes verschluesseltes Zeichen gespeichert.
3) Schritt 2) wird solange wiederholt, bis alle Zeichen verschluesselt sind.
Hintergrundwissen
XOR: Exclusiv-Oder - eine Bitoperation
Alle Zahlen lassen sich bekanntlich in binaerer Darstellung als Faktoren (0 und 1) von Zweierpotenzen darstellen.
Diese sogenannten Bits stellen gleichzeitig auch Wahrheitswerte dar. Hierbei steht 0 fuer falsch und 1 fuer wahr.
Mit der BOOLSCHEN ALGEBRA koennen elementare logische Operationen mit diesen Werten durchgefuehrt werden.
Hierbei gibt es 4 elementare Operationen: NOT, AND, OR, XOR
NOT bildet die logische Umkehrung eines Bits, 0->1 , 1->0
AND verknuepft zwei Logikwerte und ist immer dann 1, wenn beide Parameter auch 1 sind.
0 AND 0 -> 0
0 AND 1 -> 0
1 AND 0 -> 0
1 AND 1 -> 1
OR verknuepft zwei Logikwerte und ist immer dann 1, wenn mindestens einer der beiden Parameter 1 ist.
0 OR 0 -> 0
0 OR 1 -> 1
1 OR 0 -> 1
1 OR 1 -> 1
XOR verknuepft zwei Logikwerte und ist immer dann 1, wen beide Parameter verschieden sind.
0 XOR 0 -> 0
0 XOR 1 -> 1
1 XOR 0 -> 1
1 XOR 1 -> 0
Da jede beliebige Zahl in Binaerfaktoren (bits) zerlegt werden kann, koennen auch beliebige Zahlen mit Boolschen Operatoren verarbeitet werden. Hierbei erfolgt die Abarbeitung bitweise, das heisst, jedes einzelne Bit der ersten Zahl wird mit dem Bit der zweiten Zahl an der selben Position vergliechen, und das Resultat als entsprechendes Bit im Ergebnis gesetzt.
Ein Beispiel:
197 XOR 57 = 252
197 entspricht 11000101b
57 entspricht 00111001b
11000101b XOR
00111001b
------------------
11111100b = 252
Die meisten Programmiersprachen unterstuetzen von Haus aus die Boolsche Algebra.
ROTR: BITROTATE RIGHT - eine Bitoperation
Auch Rotate Right ist eine Bitoperation. Hierbei werden die Bits einer Zahl in binaerer Darstellung nach Rechts geschoben, und zwar um so viele Stellen, wie hinter der Operation stehen. Bei ROTR 4 wird also vier mal um ein Bit verschoben. Ziffern, die dabei aus der begrenzten Stellenanzahl herausfallen, werden auf der andern Seite wieder hereingeschoben. Die Umkehrung stellt ROTL dar, was fuer Rotate Left steht.
Ein Beispiel
49 (8bit) ROTR 1 = 152
49 entspricht 00110001b
00110001b ROTR 1
-----------------------
10011000b = 152
Hierbei ist natuerlich wesentlich, mit wieviel stellen (bit) eine Zahl dargestellt wird. Haetten wir in unserem obigen Beispiel nicht 8 Bit verwendet, sondern die fuehrenden Nullen weggelassen (6bit), waere das Ergebnis 56 gewesen.
Einige Programmiersprachen unterstuetzen von Haus aus die Rotationsoperatoren.
Viele unterstuetzen auch die sogenannten Shift Operatoren ( Wie ROT, nur dass ausgeschobene Bits verfallen und eingeschobene Bits 0 sind. )
Kaskadierte Verschluesselung
Bei der kaskadierten Verschluesslung (insbesondere Haeufig mit XOR verwendet) wird das aktuelle Zeichen mit dem vorherigen/nachfolgenden Zeichen als Ausgangsbasis Verschluesselt. Dieses Vorgehen wird als rueckgreifend bezeichnet, wenn ein bereits verschluesseltes Zeichen (im Ausgangszustand) zur Verschluesslung verwendet wird. Im Gegensatz dazu verwendet die vorgreifende kaskadierte Verschluesslung das folgende Zeichen als Basis.
Ein Beispiel der nachgreifenden kaskadierten Verschluesslung
Der Text "ABCDE" soll nachgreifend kaskadiert verschluesselt werden. Als Startwert dient der letzte Buchstabe.
Als Verschluesslung wird in diesem Beispiel einfach die Nummer des Buchstabens (A=1, B=2) des verschluesselnden Zeichens zur aktuellen Buchstabennummer hinzuaddiert (B(2) + D(4) = F(6)).
Startwert=E
Schritt 1: A+E=F -> F
Schritt 2: B+A=C -> FC
Schritt 3: C+B=E -> FCE
Schritt 4: D+C=G -> FCEG
Schritt 5: E+D=I -> FCEGI
FCEGI entspricht ABCDE
In anderen Worten .. A wird durch E verschluesselt, B durch A, C durch B, D durch C und E durch D.
Ein Beispiel der vorgreifenden kaskadierten Verschluesslung
Der Text "ABCDE" soll vorgreifend kaskadiert verschluesselt werden. Als Endwert dient diesmal der erste unverschluesselte Buchstabe. Es wird die selbe Verschluesslung wie im vorigen Beispiel verwendet.
Endwert = A
Schritt 1: A+B=C -> C
Schritt 2: B+C=E -> CE
Schritt 3: C+D=G -> CEG
Schritt 4: D+E=I -> CEGI
Schritt 5: E+A=F -> CEGIF
CEGIF entspricht ABCDE
In anderen Worten .. A wird durch B verschluesselt, B durch C, C durch D, D durch E und E durch A.
Hinweis: Rueckgreifender und vorgreifender Algorithmus koennen ineinander ueberfuehrt werden, wenn die Laufrichtung umgekehrt und am anderen Ende begonnen wird.