Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Kleines RSA Problem Part II: Schlüsselerzeugung


thomas42 - So 17.01.10 21:29
Titel: Kleines RSA Problem Part II: Schlüsselerzeugung
So mein erster Post hier :)
Hoffe das das hier einiegermaßen reinpasst.

Ich habe ein ganz einfaches Programm zum Verschlüsseln bzw. Entschlüsseln einer Zahl mit RSA geschrieben, erhalte allerdings bei der Entschlüsselung stets einen anderen Wert als ich sollte. Habs mittlerweile schon mittem Taschenrechner nachgerechnet, da bekomm ich das richtiege raus.


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
 
function Power(base: integer; exponent: byte): Int64;
begin
  if exponent = 0 then Result := 1
  else begin
    Result := Power(base, exponent shr 1);
    Result := Result * Result;
    if Odd(exponent) then
      Result := Result * base;
  end;
end;

procedure decrypt;
begin
C:=strtoint(form1.Edit2.text);
M:= Power(C,d) mod N;
form1.Edit1.Text:=inttostr(M);
end;

procedure crypt;
begin
M:=strtoint(form1.Edit1.text);
C:=Power(M,e) mod N;
form1.Edit2.Text:=inttostr(C);
end;


procedure TForm1.FormCreate(Sender: TObject);
begin
C:=0;
M:=0;
d:=23;
e:=7;
N:=187;
end;


Die Procedure werden über Buttons aufgerufen, die power-Funktion hab ich mir kopiert, da ich keine Lust hatte die Math-Unit einzubinden. Werte sind noch nicht variabel deklariert ausser C und M natürlich; ist nurn kleiner Ausschnitt.
Jedenfalls erhalte ich dauerhaft bei der Decodierung der Zahl 142 das Ergebnis -85 (wiso überhaupt minus??) statt der gewünschten 65.
Würde mich sehr über etwas Hilfe freuen.

Moderiert von user profile iconNarses: Code- durch Delphi-Tags ersetzt
Moderiert von user profile iconNarses: Topic aus Sonstiges (Delphi) verschoben am So 17.01.2010 um 23:44


jakobwenzel - So 17.01.10 22:12
:welcome: im DF!
Schalt mal in den Projektoptionen die Überlaufprüfung an, wahrscheinlich sind die Zahlen einfach zu groß für Integer / Int64.
Du müsstest dann eine der hier im Forum kursierenden BigNum-Units benutzen


Sirke - So 17.01.10 22:20
Das Problem liegt am Int64, welcher auch negative Zahlen darstellen kann, wodurch der Rest bei der Division ebenfalls negativ ist. Außerdem ist 142^23 ~ 2^164, was niemals in einen Int64 passt!

Als Lösung kann man in jedem Schritt der Power Funktion reduzieren, sodass die Zahlen bei der Berechnung klein bleiben: http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin.C3.A4re_modulo-Exponentiation

Auf jeden Fall würde ich aber für RSA früher oder später zu einer Langzahl Bibliothek wechseln, um auch mal mit größeren Zahlen rechnen zu können.


thomas42 - Mo 18.01.10 20:21
Danke für die Hinweise :D
Hab jetzt von Int auf TBigNum umgestellt und siehe da, es funktioniert :wink:
Dann mach ich mal weiter ^^


thomas42 - Fr 22.01.10 20:33
So eine Woche ist vergangen und ich bin nicht unwesentlich weitergekommen. Allerdings habe ich noch immer ein ähnliches Problem. Sobald ich größere Zahlen benutze stimmen Verschlüsselung und Entschlüsselung meiner Testzahl nicht mehr überein.
Mittlerweile habe ich BigNum2 implementiert und verwende binäres Modulo-Potenzieren. Probleme scheint es bereits beim Schlüsselerzeugen zu geben, da ich z.B. bei p:=1409, q:=1447 und e:=7 einen falschen Privatekey (148334775 statt 1454263; der key ist meist mehrere Dezimalstellen zu groß) erhalte. Sind die Zahlen bereits zo groß oder kann ich meinen Code noch weiter optimieren?
Vielen Dank schonmal im Voraus ;)


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
 
function modpow( b,  x, n:TBigNumber):TBigNumber; // binäres modulo potenzieren   liefert lösung von b^x mod n
var z: TBigNumber;
begin
z:=(BMD_StrToBigNum('1',false));
b:=BM_Modulo(b,n);
while BM_CompareNE(x,(BMD_StrToBigNum('0',false))) do begin
  if BM_CompareNE(BM_Modulo(x,(BMD_StrToBigNum('2',false))),(BMD_StrToBigNum('0',false))) then  z:= BM_Modulo(BM_Multiply(z,b),n);
  b:=BM_Modulo(BM_Multiply(b,b), n);
  x:= BM_Divide(x,(BMD_StrToBigNum('2',false)));

modpow:= (z);
end;
end;


function invers_mod(e,m:TBigNumber):TBigNumber; //berechnung der modularen inversen über erw. euklid. algo. -->private key -->schlüsselberechnung

  var m0,x0,x1,y0,y1,xx,yy,q,r,sign:TBigNumber;


function modpow2( b,  x, n:TBigNumber):TBigNumber;
//nochmal ne kopie von modpow, da delphi es hier drin deklariert haben will

modpow2:= (z);

end;
end;
begin
  m0:=m; x0:=BMD_StrToBigNum('1',false); x1:=BMD_StrToBigNum('0',false); y0:=BMD_StrToBigNum('0',false); y1:=BMD_StrToBigNum('1',false); sign:=BMD_StrToBigNum('1',false);
  while BM_CompareNE(e,BMD_StrToBigNum('0',false)) do Begin
    q:=BM_Divide(m,e);
    r:= modpow2(m,(BMD_StrToBigNum('1',false)),e);
    m:=e;
    e:=r;
    xx:=x1;
    yy:=y1;
    x1:=BM_Add(BM_Multiply(q,x1),x0);
    y1:=BM_Add(BM_Multiply(q,y1),y0);
    x0:=xx;
    y0:=yy;
    sign:=BM_Sub(BMD_StrToBigNum('0',false),sign);
  End;
  y0:=BM_Multiply(BM_Sub(BMD_StrToBigNum('0',false),sign),y0);
  if  BM_CompareL(y0,m)  then y0:=BM_Add(m0,y0);
  result:=y0;
  Buffer3:=result;
end;

end;
end;

procedure decrypt;
begin
C:=BMD_StrToBigNum(form1.Edit7.text,false);
d:=BMD_StrToBigNum(form1.Edit4.Text,false);
M:= modpow(C,d,N);
form1.Edit5.Text:=BMD_BigNumToStr(M,false);
end;

procedure crypt;
begin
M:=BMD_StrToBigNum(form1.Edit5.text,false);
C:= modpow(M,pe, N);
form1.Edit7.Text:=BMD_BigNumToStr(C,false);
end;


BenBE - So 24.01.10 04:33
Das Potenzieren modulo einer Zahl ist in BigNum2 eigentlich implementiert. Warum verwendest du diese Implementierung (BM_ExpMod IIRC) nicht? Die ist vor allem auf Geschwindigkeit optimiert und dürfte damit schneller als deine Compare-Variante sein (ExpMod greift intern auf die Zahlendarstellung bereits zu und kann damit in Linearzeit [f. BM_Mul € O(1), n=Zahl der Binärstellen des Exponenten] potenzieren).

Ansonsten rücke deinen Source bitte einmal ein und gewöhne Dir eine optische Gliederung von Funktionsblöcken an. Das Vereinfacht das Lesen des Sources auch ohne Beachtung der Kommentare ;-) Grob gesagt: i.d.R. brauch nur ein Kommentar je Sinn-Abschnitt kommentiert werden, was meist 5-10 Zeilen sind. Das funktioniert aber nur, wenn der Source entsprechend strukturiert ist.


thomas42 - So 24.01.10 17:39
Danke für den Hinweis mit mit BM_PowerMod :)

Verkürzt meinen Quelltext natürlich enorm. Was die Ordentlichkeit angeht, ich werd mir Mühe geben.
Allerdings besteht mein Problem noch immer. Habs jetzt durch Testen auf die Schlüsselerzeugung (Privatekey) eingrenzen können. Das Ver- und Entschlüsseln funktioniert bei größeren Zahlen Problemlos, nur der Erweiterte Euklidische Algorithmus macht Probleme:

Ein kleines Beispiel:
Public Key= 160
e= 7
Privatekey= 23
korrekter Privatekey= 23 ->ok
---
Public Key= 1409*1447= 2038823
e= 7
Privatekey= 148334775
korrekter Privatekey= 1454263 -> ???? mehrere Dezimalstellen zuviel + andere ziffern

Hier der Fragliche Code-Ausschnitt:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
 
function invers_mod(e,m:TBigNumber):TBigNumber;
  var m0,x0,x1,y0,y1,xx,yy,q,r,sign:TBigNumber;

begin
  m0:=m;
  x0:=BMD_StrToBigNum('1',false); 
  x1:=BMD_StrToBigNum('0',false); 
  y0:=BMD_StrToBigNum('0',false); 
  y1:=BMD_StrToBigNum('1',false); 
  sign:=BMD_StrToBigNum('1',false);
    while BM_CompareNE(e,BMD_StrToBigNum('0',false)) do begin
      q:=BM_Divide(m,e);
      r:= BM_PowerMod(m,(BMD_StrToBigNum('1',false)),e);
      m:=e;
      e:=r;
      xx:=x1;
      yy:=y1;
      x1:=BM_Add((BM_Multiply(q,x1)),x0);
      y1:=BM_Add((BM_Multiply(q,y1)),y0);
      x0:=xx;
      y0:=yy;
      sign:=BM_Sub(BMD_StrToBigNum('0',false),sign);
    end;
  y0:= BM_Multiply(BM_Sub(BMD_StrToBigNum('0',false),sign),y0);
    if  BM_CompareL(y0,m)  
      then y0:=BM_Add(m0,y0);
  invers_mod:=y0;
  Buffer3:=y0;
end;

form1.Edit4.Text:=BMD_BigNumToStr(invers_mod(pe,phiN),false); //und hier der Aufruf für die Funktion

Ideen?


Sirke - So 24.01.10 18:07
Grundsätzlich sieht der Code iwie NICHT richtig aus?!

Delphi-Quelltext 
1:
2:
 
x1:=BM_Add((BM_Multiply(q,x1)),x0);
y1:=BM_Add((BM_Multiply(q,y1)),y0);

Ich meine beim EEA wird in der Schleife an dieser Stelle subtrahiert und nicht addiert! Aber vllt verwendest du hier auch eine andere Implementierung!? Schau dir diese Stelle auf jeden Fall einmal genauer an...

Dann noch ein paar Anmerkungen:
Eine langsame Alternative zum Invertieren: e^( phi(m) - 1 ) mod m = d


BenBE - So 24.01.10 18:21
Das letzte offizielle Release von BigNum2 beherrscht noch keine Zahlen mit Vorzeichen. Dazu müsstest Du dir die erweiterte Version von Flamefire angucken. Hatte bisher noch keine Zeit, seine Patches bei mir zu übernehmen ...


thomas42 - So 24.01.10 21:15
@Srike
Die Formalien werde ich berücksichtiegen, würden auch meinen original Quelltext um einieges ordentlicher machen :)
Zum Thema Algorithmus, hab mir mal 2 andere implementiert, kommt der selbe bzw. leicht anderer Murks raus.

@BenBE
Erstmal Danke, dass du überhaupt BigNum zur Verfügung stellst.
Was die negativen Zahlen angeht: sie scheinen der Kern des Problems zu sein. Ich muss ja mehrmals
BM_Sub(BMD_StrToBigNum('0',false),sign)// 0 - sign
rechnen. Kommt natürlich was komplett falsches raus (0-66 ~ 200 oO).

Du rätst mir die Version von FlameFire zu nutzen, wo bekomme ich die her? Hier im Forum kursieren ja diverse Versionen, nur dass die nicht wirklich helfen bzw. ich nicht weiß ob sie die Richtigen sind. Ist es mit FlameFires Erweiterungen überhaupt möglich z.B. 0-66=-66 korrekt zu berechnen?

Vielen Dank im Voraus ;)


BenBE - So 24.01.10 21:29
Schau in dem Thread zu Bignum auf der letzten Seite; da hatte Flamefire die gepostet. Mit der ist das Rechnen mit Vorzeichen dann möglich.

Und dass meine Version da was anderes liefert, ist auch soweit klar, weil die halt nicht für das Rechnen mit Vorzeichen ausgelegt war. Wie gesagt: Wenn ich die Zeit dazu finde, baue ich das in der offiziellen Version mal alles zusammen ein.

Weiterer Tipp: Arbeite mit Hex-Strings bei den Zahlen, die werden schneller gelesen. Macht bei einer Ziffer zwar nix groß aus, aber für größere Zahlen kann die Umwandlung durchaus ewig brauchen.

Ferner ggf. noch zu den Subtraktionen: Da jegliche Rechenoperationen module N erfolgen, solltest du statt 0 - 66 N - 66 rechnen. Aber wie gesagt: Mit Flamefires Version entfällt diese explizite Prüfung der Vorzeichengeschichten, wobei es trotzdem ratsam ist, bei Restklassen Vorzeichen zu vermeiden.


thomas42 - Mo 25.01.10 16:52
Ok, dann haben wirs ja fast geschfft :)

Hab mir jetzt die letzte Unit von Falmefire von der 3 Seite des Big-Num-Threat geladen und die Alte sofort ersetzt.
Funktionieren tuts nur immer noch nicht. Inwieweit muss ich jetzt noch den Quelltext abändern? (Stichwort TSJ, ich kann ja wohl nicht alles lassen wie es ist oder? hab da leider noch keine so große Erfahrung mit)

Besten Dank ;)


BenBE - Mo 25.01.10 17:40
Flamefire hatte dort nur die TSJ*-Methoden entsprechend ergänzt. Die ganzen BM_*-Funktionen selber stellen nur die Primitive dar, um überhaupt rechnen zu können. Du müsstest also auf die Nutzung der Klasse umstellen, um mit Vorzeichen zu arbeiten. Nutzung ist eigentlich identisch zu meinen Funktionen, nur halt eben OOP.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!