Entwickler-Ecke

Algorithmen, Optimierung und Assembler - XOR-Entschlüsselungsproblem


Master_of_Magic - Di 12.07.05 23:23
Titel: XOR-Entschlüsselungsproblem
Ich hab ein Tool, in den ein String verschlüsselt werden muss. Da die Verschlüssung nicht 100% sicher sein muss (hauptsache der String ist nicht ohne weiteres lesbar) hab ich mich für ne einfach XOR Verschlüsselung mit Random One-Time-Pad entschieden. Da ich mit XOR kaum Erfahrung habe, hab ich einfach einen Codeschnipsel hier aus dem Forum verwendet und für meine Verwendung umfunktioniert. Die Verschlüsselung sieht momentan ungefähr so aus(gekürzt):


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
procedure TForm1.cmdencrypt(Sender: TObject);
var idcomb,actid:String;
text:array of byte absolute idcomb;
key,verschtext:array[0..64of byte;
Reg:TRegistry;
i,init:integer;
begin
  idcomb:='Dieser String wird verschlüsselt';
  init:=32541187//wird später zufallsgeneriert, zum debuggen festgelegt
  RandSeed:=init;
  for i:=0 to (Length(idcomb)) do key[i]:=random(255);
  for i:=0 to (Length(idcomb)) do verschtext[i]:=text[i] xor key[i];
  for i:=0 to (Length(idcomb)) do actid:=actid + Inttohex(verschtext[i],0);
  actid:=actid+inttohex(init,0);
end;


Soweit, sogut. Mit dieser Funktion als Basis hab ich versucht, einen entschlüsselungsalgo zu basteln:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
procedure TForm1.Button1Click(Sender: TObject);
var actid,text:String;
idcomb:array of byte absolute text;
key,entschidcomb:array[0..64of byte;
i:integer;
begin
  actid:=AnsiLeftStr(txtid.Text,strtoint(txtkeylength.Text)*2);  //txtkeylength enthält die Länge des Strings und damit die des Schlüssels (OTP!)
  randseed:=Strtoint('$' + AnsiRightStr(txtid.Text,Length(txtid.Text)-2-strtoint(txtkeylength.Text)*2));
  for i:=0 to (strtoint(txtkeylength.Text)) do key[i]:=random(255);
  i:=0//Der Key wird meiner Meinung nach korrekt entschlüsselt und eingelesen
  //die Hextostr-Umwandlung ist hier wohl nur beim ersten Zeichen korrekt, danach kommen falsche Werte
  While i<Length(actid) do
  Begin
    text:=text+Chr(StrToIntDef('$'+Copy(actid,i,2),0));
    Inc(i,2);
  End;
  for i:=0 to (strtoint(txtkeylength.Text)) do entschidcomb[i]:= key[i] xor idcomb[i] ;
end//wegen den Problemen bei der Hex-Umwandlung ist auch keine Entschlüsselung möglich


Kann mir jemand helfen und mir sagen, was ich da falsch mache? Und evtl. Tipps geben, wie ich das ganze Vereinfachen kann? Ich hab ja relativ viele Variablen benutzt, weil ich keine andere Möglichkeit kannte. Evtl. kann mir einer von euch ne einfachere Version geben. Der Code sollte folgendes machen:
Verschlüsseln eines Strings mit einem zufallsgenerierten (Random-)OTP-Key. Der String sollte danach Hexadezimal angezeigt werden und RandSeed ebenfalls als Hex angehängt werden. Die Verschlüsselung wandelt dann den Hex-Randseed wieder um, rekonstruiert den Key und entschlüsselt damit den Text.

Ich hoffe, das war verständlich und ihr könnt mir dabei helfen, den Algo zu vervollständigen oder mir einen einfacheren Weg zu zeigen.
Und ja, ich weiß, dass dieser Algorythmus nicht sonderlich schwer zu knacken ist. Darum geht es mir aber auch nicht!


JayEff - Di 12.07.05 23:29

ich würde schlicht kein xor nehmen, weil da seltsame zeichen wie #13 oder soetwas rauskommen kann. nimm doch z.b. ... +!
mein kleiner Algo:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function verschluesseln(text,key:string):string;
var i:integer;
begin
for i:=1 to length(text) do
  result:=result+char(byte(ord(text[i]) + ord(key[i]))); //Vorrausgesetzt, key und text sind gleichlang.
end;
function ent(text,key:string):string;
var i:integer;
begin
for i:=1 to length(text) do
  result:=result+char(byte(ord(text[i]) - ord(key[i]))); //Vorrausgesetzt, key und text sind gleichlang.
end;
Du siehst, ist ganz einfach ^^

Ach übrigens: XOR hat die nette eigenschaft, dass das entschlüsseln und das verschlüsseln exakt die gleiche procedure ist... einfach mal das selbe machen. Hab mir deinen code aber nicht angesehen.


Master_of_Magic - Mi 13.07.05 14:11

Das bei XOR 'seltsame Zeichen' rauskommen, macht nix, da sie eh als Hex-Wert dargestellt werden. Dein Algorythmus basiert ja eigentlich nur auf Byte-Verschiebung, was meienr Meinung nach einiges leichter zu knacken ist.

Und wenn du meinen Cod eangesehen hättest, wäre dir aufgefallen, dass ich durchaus verstanden habe, dass die Entschlüssulung fast exakt wie die Verschlüsselung abläuft. :wink:


Mein Problem ist ja eher die Umwandlung in die einzelnen Hex-Werte und die Tatsache, dass ich irgendwie das Gefühl hab, ein paar Sachen weglassen zu können (beim Umwandeln ...)


retnyg - Mi 13.07.05 14:15


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
function xorEnc(s:string;key:byte):string;
var i,l: integer;
begin
  result := s;
  l:=length(s);
  if l > 0 then
    for i := 1 to l do result[i] := char(byte(result[i]) xor key);
end;


ManuelGS - Mi 13.07.05 14:23

Rück mal den Quelltext als Ganzes raus.


DaRkFiRe - Mi 13.07.05 16:02


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
function strXOR(text,key:STRING):STRING;
var I:INTEGER;
var R:STRING;
begin
  R:=text;
  for I:=1 to LENGTH(text) do
    R[I]:=CHAR(BYTE(R[I]) XOR BYTE(key[((I-1MOD LENGTH(key))+1]));
  Result:=R;
end;



Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
Beispiel:

Text: ABCDEFGHIJ
Key : 123456

Verschlüsselung
Text mit Wiederholung von Key:

ABCDEFGHIJ
   XOR
1234561234


Die binäre XOR Operation ist kommutativ und assoziativ. Die Verschlüsselungs und Entschlüsselungsfunktion sind daher dieselben!


JayEff - Mi 13.07.05 16:21

user profile iconMaster_of_Magic hat folgendes geschrieben:
Dein Algorythmus basiert ja eigentlich nur auf Byte-Verschiebung, was meienr Meinung nach einiges leichter zu knacken ist.
kein bisschen. Die Sicherheit eines Algos basiert immer auf der Situation, dass der Algo selbst bekannt ist, nur das PW soll die sicherheit ausmachen. Und sche*** egal welchen Algo du nimmst, beides ist nur polyalphabetische Substitution, nichts anderes. Darum sind sie exakt gleich sicher.


Master_of_Magic - Mi 13.07.05 20:05

Juhuuuu, ich habs endlich hinbekommen *freu*
Ich hab zwar nochmal von vorne angefangen, aber mit der Hilfe eurer Codeschnipsel funktioniert es nun meiner Meinung nach. Hier mal der Code:

XOR-Funktion(wird für beide Richtungen neutzt):

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
function TForm1.strXOR(text,key:String):String;
var i: integer;
begin
  result := text;
  for i := 1 to length(text) do result[i] := char(byte(result[i]) xor byte(key[i]));
end;


Verschlüsselungsfunktion:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
procedure TForm1.encryptClick(Sender: TObject);
var winid,idcomb,actid,key,code:String;
Reg:TRegistry;
i,tick:integer;
begin
  idcomb:='Text zum Verschlüsseln';
  tick:=gettickcount;
  RandSeed:=tick;
  key:=idcomb; //braucht man die Längenzuweisung? Bzw. warum gibts in der nächsten Zeile bei key[i] nen Fehler, wenn ich keine Längenzuweisung mache?
  for i:=1 to (Length(key)) do key[i]:=chr(random(255));
  code:=strxor(idcomb,key);
  for i:=1 to (Length(code)) do actid:=actid+inttohex(byte(code[i]),2);
  actid:=actid+inttohex(tick,2);
end;


Entschlüsselungsfunktion:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure TForm1.decryptClick(Sender: TObject);
var actid,code,key:String;
i,keylength:integer;
begin
  keylength:=strtoint(txtkeylength.text); //hier muss die Key bzw. Text-Länge übergeben werden
  randseed:=strtoint('$'+copy(txtid.Text,keylength*2+1,15));
  Setlength(key,keylength); //auch hier muss ich ne Längenzuweisung machen, sonst gibts in der nächsten Zeile bei Key[i] nen Fehler!?
  for i:=1 to keylength do key[i]:=chr(random(255));
  i:=1;
  While i<keylength*2 do
  Begin
    code:=code+Chr(StrToIntDef('$'+Copy(txtid.text,i,2),0));
    Inc(i,2);
  End;
  actid:=strxor(code,key);
end;


Jetzt würd ich von euch gerne wissen, ob ich irgendwo was wichtiges vergessen hab. Weil ansonsten werden die Prozeduren eingebaut und verwendet... :)


ScorpionKing - Mi 13.07.05 20:11

Der Code sieht soweit gut aus, bau ihn mal ein, und schau ob dir das Ergebnis gefällt! :wink:


DaRkFiRe - Do 14.07.05 11:40

Was macht strXOR eigentlich, wenn key kürzer ist als der Text!?

Dann wird auf key zugegriffen - auf einen Index größer als die Länge von Key, weil ja bis Länge (Text) gelaufen wird L(Key) < L(Text) - Zugriffsverletzung!

Nimm lieber meine Variante mit MOD-Funktion, da dort nach dem letzten Zeichen quasi im Key neu angefangen wird. Ich habs im Post noch erklärt!


ScorpionKing - Do 14.07.05 14:48

user profile iconDaRkFiRe hat folgendes geschrieben:
Was macht strXOR eigentlich, wenn key kürzer ist als der Text!?


Angenommen wir wollen Mathematikwettbewerb verschlüsseln, und unser Key heißt Hallo Dann nimmt es den Key sooft hintereinander bis wir auf die länge des zu verschlüssenden Wortes kommen! Sprich:

Quelltext
1:
2:
Mathematikwettbewerb
HalloHalloHalloHallo


MfG, ScorpionKing!


Master_of_Magic - Do 14.07.05 17:44

@DaRkFiRe
Du hast recht, dass das nicht funktionieren würde, allerdings ist mein Key immer gleich lang wie der Text (siehe Verschlüsselungsalgorythmus!). Da es sich um ein One-Time-Pad handelt, spielt also die Key-Länge keine Rolle.
Deshalb hab ich auch deine Mod-Funktion nicht komplett übernommen :wink:

Aber ansonsten hab ich bisher keine Fehler finden können ... scheint zu funktionieren :D