PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Contest: Kaskadierte XOR ROT Verschluesslung



Ineluki
06.09.2004, 00: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.

Manuel
06.09.2004, 01:22
Mh, interessanter Contest... Mal sehen, ob ich mitmache, bin mir noch nicht sicher^^.
Einsendeschluss des Quelltextes und Beispielprogrammes (moeglichst ausfuehrbar unter Windows) ist Freitag, der 10.09.2004Äh... ich kann leider fast nur in QBasic richtig gut programmieren. Ist das vorgeschrieben, oder darf ich aufgrund des Wortes "moeglichst" annehmen, das auch DOS-Programme (und natürlich auch DOS-Quellcode) zählen?^^

EDIT: Dann gibt es noch was, was mir irgendwie Kompfzerbrechen bereitet^^:
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.Wie ist das zu verstehen? Als das letzte Zeichen in der kompletten Datei, oder als letztes Zeichen der Zeile, da man ja nur ASCII-Zeichen (laut deiner Beschriftung) verschlüsseln soll? Oder das letzte Zeichen eines Wortes, wobei ENTER und LEERTASTE nicht gezählt werden? Sorry, das ich bei sowas nachfrage, aber es wäre doch peinlich, wenn man im Contest einen lausigen Platz erhält, und das nur, weil man die Beschreibung nicht richtig gerafft hat^^.

Ineluki
06.09.2004, 02:12
Da fuer diesen Algorithmus auch Steuerzeichen wie ENTER (#13) als Zeichen interpretiert werden, versteh ich deine Frage nicht ganz, da es in diesem Text ja dadurch keine Zeilen mehr gibt. Im Prinzip stellt dieser Text eine beliebig lange Folge von Zeichen oder, wenn es dir vom Verstaendnis lieber ist, Zahlen im Wertebreich von 0 bis 255 dar.

Noch ein Hinweis: Der Text braucht werder eingegeben noch aus irgend einer Datei eingelesen werden. Es reicht, wenn er im Quelltext definiert ist, das Programm aber jeden beliebigen anderen Text auch verwenden koennte.

Also bitte sowas vermeiden, weil dann ein laengerer oder kuerzerer Text nicht mehr funktioniert:

const TEXT="ABCDE"
von Index = 1 bis 5 verschluessel Text.Element(Index)

BTW: Die Ausgabe des Verschluesselten Textes wurde um die Klausel erweitert, dass Nichtdruckbare Zeichen, also alle mit ASCII-Codes kleiner als 32 (20h), als '.' ausgegeben werden. Zudem wird nun auch das kleinste compilierte Programm (Anzahl Byte Code) gekuehrt. Zur Praezisierung der Aufgabe wurde nun auch ein Standardtext festgelegt. Ausserdem wurde in meiner Erklaehrung der Kaskadierten Verschluesslung ein Logikfehler beseitigt (wie peinlich) :rolleyes:

Da idR alle DOS Programme auch noch unter Windows lauffaehig sind, kannst du natuerlich auch QBasic verwenden, obwohl mMn diese Sprache nicht unbedingt die Beste fuer LowLevel-Bitoperationen ist ^__^

Ich lass mich aber gern vom Gegenteil ueberzeugen ^__^

YoshiGreen
06.09.2004, 11:31
:eek: Boah, ein Contest... voll ey!
Also ich werde vielleicht teilnhemen, ich bin mir noch nicht so sicher, mal gucken wie ich Zeit finde. Chancen auf einen vorderen Platz habe ich zwar nicht, aber weil du dir die ganze Arbeit gemacht hast, XOR und die Verschlüsselung zu erklären und ich das soga vestanden hab, ist es nur fair wenn ich es versuche ;)

Also Programmiersprachenmäßig keine Begrenzung?! (PB rulez ;p) und eingesand werden soll die .EXe sowie der Quelltext?!

Nochma zur Aufgabenstellung:

Ich soll also D mit t und XOR verschlüsseln (keine Ahnung wie man das ausdrückt uch hoffe ihr versteht das und danach i mit D und XOR usw.?!

Ineluki
06.09.2004, 13:16
jup genau so ... das ROTR4 aber nicht vergessen ^^

Dingsi
06.09.2004, 15:17
CPP SKILLZ. \m/.
Ich mach mit. *maschienen anwerf*.

Argh. Muss es wirklich Bit Rotation sein? Reicht Shiften nicht? >_<.

Btw. Ich bin fertig. ^_^.

Manuel
06.09.2004, 15:57
Da fuer diesen Algorithmus auch Steuerzeichen wie ENTER (#13) als Zeichen interpretiert werden, versteh ich deine Frage nicht ganz, da es in diesem Text ja dadurch keine Zeilen mehr gibt. Im Prinzip stellt dieser Text eine beliebig lange Folge von Zeichen oder, wenn es dir vom Verstaendnis lieber ist, Zahlen im Wertebreich von 0 bis 255 dar.Hm, jetzt verstehe ich erst, THX. Da hast du recht, mit QBasic geht das leider (fast?) nicht... Höchstens mit kleineren "Tricks" im Quellcode... muss ich schlichtweg mal ausprobieren, mal sehen, was dabei rauskommt^^.

Jesus_666
06.09.2004, 19:45
Hmm, da fallen mir ein paar Stolperteine ein:
1.) Kleinster Maschinencode: Wie wird das entschieden? Immerhin gibt es himmelweite Unterschiede zwischen C++-Source, den ich mit g++ in eine Linux-ELF kompilieren, C++-Source, den ich mit g++ in eine Windows-PE kompilieren, C++-Source, den ich mit C++ Builder in einer Win-PE kompiliere... Selbst einzelne Builds von g++ unterscheiden sich u.U. in der Größe der erzeugten Binary. Linux-User sind u.U. im Vorteil, da ELFs AFAIK kleiner sind als PEs.
2.) Kleinster Maschinencode: Was ist mit Debugginginformationen etc.? Wenn man ein Programm durch strip laufen läßt ist es eine Ecke kleiner, weil nicht-kritische Teile entfernt werden.
3.) Kleinster Maschinencode: Was ist mit Interpretersprachen wie PHP? AFAIK könnte man kaskadierendes XOR und ROTR4 auch in PHP umsetzen.


Ich werde mal sehen, was ich so zusammengeflickschustert kriege. Fürchtet meine gestripten ELFs (wegen der Größe oder wegen der fatalen Programmierfehler, das wird sich dann zeigen).

YoshiGreen
06.09.2004, 21:51
achja. muss echt schon Freitag Einsendeschluß sein?! Soll das so Low-Level (warum eigentlich Low-Level?) aso son Low-leve-High-Speed-Contest werden?

Würde gerne noch mindestens ein WE drinne haben, weil ich unter der Woche eigentlich nich oder nur sehr schwer die Zeit dafür finde.
Wie sehen die anderen das denn?

Dingsi
12.11.2004, 15:41
Ich beanspruche meinen Titel wieder, und so.

Jesus_666
12.11.2004, 17:58
Ich beanspruche meinen Titel wieder, und so.
Äh?

Wenn es irgendwas ist, das durch die Downtime kaputt gegangen ist mußt du dich an die Admins wenden - ich habe vor einer Virtelstunde erst erfahren, daß das Forum überhaupt wieder on ist. Ob und wie was kaputt ist und wie man's repariert kriegt - keine Ahnung.

Lukas
13.11.2004, 11:54
Ich glaiube, DIngsi hat in irgendeiner Kategorie bei dem Contest gewonnen und beansprucht den Titel des Siegers wieder. Ich kann mich nicht an irgendwelche Sondertitel erinnern.

btw: Durch die Downtime ist das hier mein erster Post im Prog-Forum^^

Jesus_666
13.11.2004, 12:59
Aso. In dem Fall: Herzlichen Glückwunsch, du hast gewonnen.

Dingsi
13.11.2004, 13:07
Ich hab's Jeez ja eigentlich schon im Chat erklärt, dass das nur ein Scherz (und mein erster Post nach dem ~bling~ im ganzen Forum) war. Sonderränge gabs keine, nur der Kürungspost von Luki und die Umfrage sind weg. T_T.

Lukas
13.11.2004, 13:56
Dass es keine Ränge gab, war mir klar. Ich habe mir den Contest und die Codes auch angeguckt und wusste, dass es da nix Besonderes gab. Ich hätte (vielleicht) auch mitgemacht, aber ich habe mir das Prog-Forum erst 'ne halbe Woche nach dem Abgabetermin für die Codes zum ertsen mal angeguckt.

Ach, btw:
Habt ihr inzwischen 'ne Idee für einen neuen Contest? Ich bin immer noch für Scriptsprache.

Jesus_666
13.11.2004, 17:12
Ich hab's Jeez ja eigentlich schon im Chat erklärt, dass das nur ein Scherz (und mein erster Post nach dem ~bling~ im ganzen Forum) war. Sonderränge gabs keine, nur der Kürungspost von Luki und die Umfrage sind weg. T_T.
Ich habe mich gerade gefragt, ob du gewonnen hast. 100% aller Befragten antworteten mit "Ja". Betrachte dich als gekürt.

Siehste, ich denke an alles.