Kleines RSA Problem Part II: Schlüsselerzeugung

thomas42 · Hält's aus hier Beiträge: 6

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.

markieren

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 Narses: Code- durch Delphi-Tags ersetzt
Moderiert von Narses: Topic aus Sonstiges (Delphi) verschoben am So 17.01.2010 um 23:44

jakobwenzel · Verfasst: So 17.01.10 23:12

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

_________________
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.

Sirke · Beiträge: 208 Erhaltene Danke: 2

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: de.wikipedia.org/wik...odulo-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 · Hält's aus hier Beiträge: 6

Danke für die Hinweise

Hab jetzt von Int auf TBigNum umgestellt und siehe da, es funktioniert :wink:

Dann mach ich mal weiter ^^

thomas42 · Hält's aus hier Beiträge: 6

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

markieren

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 · Verfasst: So 24.01.10 05: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.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

thomas42 · Hält's aus hier Beiträge: 6

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:

markieren

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 · Beiträge: 208 Erhaltene Danke: 2

Grundsätzlich sieht der Code iwie NICHT richtig aus?!

markieren

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:

Warum rechnest du r = m^1 mod e und nicht einfach r = m mod e?
markieren

Delphi-Quelltext
1:

r:= BM_PowerMod(m,(BMD_StrToBigNum('1',false)),e);
Was macht die Variable sign? Evtl ist das die "Subtraktion" für das oben angesprochene Problem am Ende, aber iwie werde ich daraus nicht schlau...
Verwende für die konstanten Ausdrücke wie BMD_StrToBigNum('0',false) am besten Konstanten wie ZERO, um das Lesen des Codes zu vereinfachen!
Kommentare an Funktionen von Funktionen von Funktionen von Funktionen, um wieder einmal das Lesen zu vereinfachen:
markieren

Delphi-Quelltext
1:

x1:=BM_Add((BM_Multiply(q,x1)),x0); // x1 = q * x1 + x0

Eine langsame Alternative zum Invertieren: e^( phi(m) - 1 ) mod m = d

BenBE · Verfasst: So 24.01.10 19: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 ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

thomas42 · Hält's aus hier Beiträge: 6

@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 · Verfasst: So 24.01.10 22: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.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

thomas42 · Hält's aus hier Beiträge: 6

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 · Verfasst: Mo 25.01.10 18: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.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme