RSA - Problem bei der verschlüsselung/entschlüsselung

[gammatester]

Was ist eigentlich Dein 'd'? Normalerweise ist es der geheime Entschlüssellungsexponent und der ändert sich natürlich nicht.

[gammatester]

Dein mod_inv hat einen Bug (außerdem hat es eine ungewöhnliche Parameterreihenfolge: inv_mod(a,b) berechnet nicht 1/a mod b sondern 1/b mod a, solltest du vielleicht mal ändern, zumindest aber hinschreiben). Ich zeige mal die korrigierte Version und ein simples Testproramm mit kleinen Werten:

Delphi-Quellcode:

program t_mrsa2;

{$ifdef WIN32}
{$apptype console}
{$endif}

function mod_inv(A,B:longint):longint;
  {-liefert 1/B mod A}
var
  n1,n2,b1,b2,q,r,t:longint;
  Fertig:Boolean;
begin
  if a < 1 then begin
    mod_inv:=a;
  end
  else begin
    Fertig:=False;
    n1:=A;
    n2:=B;
    b1:=0;
    b2:=1;
    repeat
       r:=n1 mod n2;
       q:=n1 div n2;
       if r=0 then begin
         if b2 < 0 then b2:=b2+A; {Fehler!! statt 65537 muss hier A stehen}
         mod_inv:=b2;
         Fertig:=True;
       end
       else begin
         n1:=n2;
         n2:=r;
         t :=b2;
         b2:=b1-q*b2;
         b1:=t;
       end;
    until Fertig;
  end;
end;

function expmod(b,x,m: longint): longint;
  var
    quad,halb,erg:longint;
   {
    Berechnet die diskrete Exponentialfunktion b hoch x modulo m
    unter ausschließlicher Verwendung der Operationen Quadrieren
    und Multiplizieren. Der Rest wird nach jeder Operation bestimmt,
    um große Zwischenergebnisse zu vermeiden
    mod bezeichnet die Modulo-Operation
    div bezeichnet die ganzzahlige Division
   }
begin
  Quad := b; {basis}
  Halb := x; {hochzahl}
  Erg := 1;  {Ergebnis}
  while Halb > 0 do
    begin
      if Halb mod 2 > 0 then
         Erg := (Erg * Quad) mod m;
       Quad := (Quad * Quad) mod m;
       Halb := Halb div 2;
    end;
  expmod := Erg;
end;

var
  p,q,n,e,d,phi,i,x,y: longint;
begin
  p := 17;
  q := 19;
  n := p*q;
  phi := (p-1)*(q-1);
  e := 5;
  d := mod_inv(phi,e);
  writeln('d=',d);
  for i:=0 to 255 do begin
    x := expmod(i,e,n);
    y := expmod(x,d,n);
    if y<>i then writeln('Fehler: y<>i für i=',i);
    if (i<11) or (i>240) then writeln(i:5, x:5, y:5);
  end;
end.

Und hier die Ausgabe, die zeigt, daß alle Zeichen von 0..255 richtig ver/entschlüsselt werden. Setz mal die Werte p=17, q=19, e=5 in Dein Programm ein und vergleiche, ob die Ergebniss dann übereinstimmen.

Wenn alles OK, must Du Dir klar sein, daß RSA in dieser Größenordnung nur für Lernzwecke genutzt werden sollte, keinesfalls für wirkliche Anwendungen.

Code:

>DCC32 -b t_mrsa2.pas
Borland Delphi for Win32 compiler version 18.0
Copyright (c) 1983,2005 Borland Software Corporation
t_mrsa2.pas(39) Warning:
t_mrsa2.pas(85)
86 lines, 0.66 seconds, 12508 bytes code, 12176 bytes data.

>T_MRSA2.EXE
d=173
    0    0    0
    1    1    1
    2   32    2
    3  243    3
    4   55    4
    5  218    5
    6   24    6
    7   11    7
    8  145    8
    9  263    9
   10  193   10
  241   90  241
  242  276  242
  243  116  243
  244  194  244
  245  215  245
  246   94  246
  247   76  247
  248  210  248
  249  146  249
  250  224  250
  251  302  251
  252  199  252
  253  138  253
  254  220  254
  255  221  255

[himitsu]

Zitat von gammatester:

außerdem hat es eine ungewöhnliche Parameterreihenfolge

och, sowas läßt sich ja leicht beheben

- die beiden Parameter umgedreht
- Das Funktionsergebnis über Result, statt Funktionsnamen
* (leichter zu erkennen, ob Funktionsaufruf oder Ergebniszuweisung)
- die Fertig-Variable abgeschaft

Delphi-Quellcode:

program t_mrsa2;

{$ifdef WIN32}
  {$apptype console}
{$endif}

function mod_inv(A, B: LongInt): LongInt;
  {liefert 1 / A mod B}
var
  n1, n2, b1, b2, q, r, t: LongInt;
begin
  if B >= 1 then begin
    n1 := B;
    n2 := A;
    b1 := 0;
    b2 := 1;
    while true do begin
       r := n1 mod n2;
       q := n1 div n2;
       if r = 0 then begin
         if b2 < 0 then b2 := b2 + B;
         Result := b2;
         Break;  // oder gleich Exit;
       end;
       n1 := n2;
       n2 := r;
       t  := b2;
       b2 := b1 - q * b2;
       b1 := t;
    end;
  end else
    Result := B;
end;

function expmod(b, x, m: LongInt): LongInt;
  var
    quad, halb, erg: LongInt;
   {
    Berechnet die diskrete Exponentialfunktion b hoch x modulo m
    unter ausschließlicher Verwendung der Operationen Quadrieren
    und Multiplizieren. Der Rest wird nach jeder Operation bestimmt,
    um große Zwischenergebnisse zu vermeiden.
    - mod bezeichnet die Modulo-Operation
    - div bezeichnet die ganzzahlige Division
   }
begin
  Quad := b; {Basis}
  Halb := x; {Exponent}
  Erg  := 1; {Ergebnis}
  while Halb > 0 do
    begin
      if Halb mod 2 > 0 then
         Erg := (Erg * Quad) mod m;
       Quad := (Quad * Quad) mod m;
       Halb := Halb div 2;
    end;
  Result := Erg;
end;

var
  p, q, n, e, d, phi, i, x, y: LongInt;
begin
  p   := 17;
  q   := 19;
  n   := p * q;
  phi := (p - 1) * (q - 1);
  e   := 5;
  d   := mod_inv(e, phi);
  WriteLn('d=', d);
  for i := 0 to 255 do begin
    x := expmod(i, e, n);
    y := expmod(x, d, n);
    if y <> i then WriteLn('Fehler: y<>i für i=', i);
    if (i < 11) or (i > 240) then WriteLn(i:5, x:5, y:5);
  end;
end.

Für größere berechnugsräume gibt es Int64.
Extended kann zwar theoretisch größere Werte enthalten, aber es gibt nur 19-20 signifikante Dezimalstellen ... alles andere wird Aufgrund des internen Formates quasi weggerundet.
Int64 hat genausoviele Stellen, aber keine Rundungsfehler.

Für mehr mußt du dann auf andere Mittel ausweichen: BigNumber, BigInt oder Dergleichen
TBigInt

[gammatester]

Zitat von himitsu:

- Das Funktionsergebnis über Result, statt Funktionsnamen
(leichter zu erkennen, ob Funktionsaufruf oder Ergebniszuweisung)

Ist aber nicht portabel! Außerdem könnte man es dann doch gleich durchsichtiger machen (hab's anders genannt, damit keine Verwirrung entsteht):

Delphi-Quellcode:

function mod_inv1(A,B:longint):longint;
  {-liefert 1/A mod B, 0 wenn nicht invertierbar d.h. ggt(A,B) <> 1}
var
  n1,n2,b1,b2,q,t:longint;
begin
  n1 := B;
  n2 := A;
  b1 := 0;
  b2 := 1;
  while n2<>0 do begin
    q  := n1 div n2;
    t  := n2;
    n2 := n1 - q*n2;
    n1 := t;
    t  := b2;
    b2 := b1 - q*b2;
    b1 := t;
  end;
  if n1<>1 then mod_inv1 := 0
  else if b1<0 then mod_inv1 := b1+B
  else mod_inv1 := b1;
end;

[himitsu]

Wieso eigentlich nicht portabel?
Selbst FPC/Lazarus sollte doch wohl Result kennen, denn dieses stammt ja noch aus den Pascal-Anfangszeiten und gehört praktisch zur grundlegenden Syntax.

[edit]
OK, die Anfangszeiten sind für mmich jetzt einfach mal solange ich mich zurückerinnern kann.

[gammatester]

Zitat von himitsu:

Wieso eigentlich nicht portabel?
Selbst FPC/Lazarus sollte doch wohl Result kennen, denn dieses stammt ja noch aus den Pascal-Anfangszeiten und gehört praktisch zur grundlegenden Syntax.

Ich weiß zwar nicht, was Du unter Pascal-Anfangszeiten verstehst, aber zB alle Borland/Turbo-Pascalversionen und alle Free-Pascal in nativen Modi kennen es nicht (FPC muss erst in den Delphi-Kompatibilitäts-Modus schalten).

Vielleicht sollten wir diesen Tread aber nicht so 'zumüllen' und erst mal Schweindis Antwort(en) abwarten.

[schweindi]

also d ist eben das multipl. Inverse von e... und es kommt immer ein anderer Wert raus, weil ich es in die loop reingeschrieben hab -> fehler

ja, die absolute Zahl ist natürlich auch dumm danke für die Korrektur!

Ich werde, wenn mal die Verschlüsselung richtig geht, auf BigInt etc umsteigen und für den Anfang reicht es fürs Lernen aus.

Das mit portable verstehe ich nicht ganz- worum gehts da genau?? (ist es wichtig, wenn ich das Programm nur so verwenden will, also compiled ohne Schnittstelle zu anderen?

Ich melde mich wenn ich alles verändert habe.
lg

[Aphton]

Wie es aussieht, hast du dich nicht ausreichend genug mit der Materie beschäftigt.
Ich habe vor einiger Zeit mal ein Referat über RSA gehalten. Ich lade mal die PP Präsentation hoch, evt. hilft es dir.

Btw. Du wirst noch einem ganz anderen Problem begegenen:
Das Ergebnis von X mod Y liegt im Wertebereich von {0..Y-1}.

Was heißt das?
Beim RSA-Algorithmus verschlüsselt man, indem man das zu Verschlüsselnde (X) hernimmt, es mit der Encryption-Potenz (E) potenziert und modulo RSA-Modul (N) rechnet.
Sieht dann so aus --> Y = X^E mod N.

Hierbei musst du beachten, dass foglende Bedingung erfüllt ist:
X < N

Falls nicht, kann X nicht mehr zurückberechnet werden - siehe dazu Entschlüsselung und den Fett gedruckten Teil dieser Nachricht:
X = Y^D mod N.

MfG

[ele]

Ich verstehe ja das das ein Schulprojekt ist, aber RSA mit Int64??

Ein Int64 ist lächerlich schnell faktorisiert und bietet daher Null Sicherheit. Ein RSA-Schlüssel sollte in der Praxis mindestens 1024 Bits lang sein. Besser 2048, da man annimt, dass man in wenigen Jahren in der Lage sein wird 1024-Bit Schlüssel innerhalb einer vernünftigen Zeit zu knacken.

Als Lernprojekt ist das OK, aber es soll ja nicht jemand auf die Idee kommen, sowas in einem echten Produkt zu machen.

Ausserdem: Das verschlüsseln mit RSA ist relativ zeitaufwändig (zumindest wenn man mit genügend grossen Zahlen arbeitet). Deshalb wir in der Praxis meist ein symmetrisches Verschlüsselungsverfahren gewählt. Dieser Schlüssel kann dann mit RSA verschlüsselt und sicher übertragen werden.

Nur so zur Info, da ich das jetzt nirgendwo gelesen habe...

[schweindi]

jaja, klar aber wie schon einige geschrieben haben ist das jetzt nur zu Testzwecken, wenn ich da schon solche Denkfehler drinnen habe, wie soll ich dann etwas mit "großen" Zahlen verstehen, die ich mir garnicht vorstellen kann.

Also ich habe die functions wie folgt geändert:

Delphi-Quellcode:

function expmod(b, x, m: LongInt): LongInt; 
  var 
    quad, halb, erg: LongInt; 
   { 
    Berechnet die diskrete Exponentialfunktion b hoch x modulo m 
    unter ausschließlicher Verwendung der Operationen Quadrieren 
    und Multiplizieren. Der Rest wird nach jeder Operation bestimmt, 
    um große Zwischenergebnisse zu vermeiden. 
    - mod bezeichnet die Modulo-Operation 
    - div bezeichnet die ganzzahlige Division 
   } 
begin 
  Quad := b; {Basis} 
  Halb := x; {Exponent} 
  Erg  := 1; {Ergebnis} 
  while Halb > 0 do 
    begin 
      if Halb mod 2 > 0 then 
         Erg := (Erg * Quad) mod m; 
       Quad := (Quad * Quad) mod m; 
       Halb := Halb div 2; 
    end; 
  Result := Erg; 
end;

function mod_inv(A,B:Int64):Int64;export;
  {liefert 1 / A mod B} 
var n1,n2,b1,b2,q,r,t:Int64;
begin 
  if B >= 1 then begin 
    n1 := B; 
    n2 := A; 
    b1 := 0; 
    b2 := 1; 
    while true do begin 
       r := n1 mod n2; 
       q := n1 div n2; 
       if r = 0 then begin 
         if b2 < 0 then b2 := b2 + B; 
         Result := b2;
         Break;  // oder gleich Exit;
       end; 
       n1 := n2; 
       n2 := r; 
       t  := b2; 
       b2 := b1 - q * b2; 
       b1 := t; 
    end; 
  end else 
    Result := B; 
end;

und wenn ich jetzt, wie du es geschrieben hast, die Schleife von 0-255 durchlaufen lasse steht folgendes da:

Fehler: y<>i für i=0
x:5 y:5 z:5
x:5 y:5 z:5
Fehler: y<>i für i=2
x:5 y:5 z:5
Fehler: y<>i für i=3
x:5 y:5 z:5
Fehler: y<>i für i=4
x:5 y:5 z:5
Fehler: y<>i für i=5
x:5 y:5 z:5
Fehler: y<>i für i=6
x:5 y:5 z:5
Fehler: y<>i für i=7
x:5 y:5 z:5
Fehler: y<>i für i=8
x:5 y:5 z:5
Fehler: y<>i für i=9
x:5 y:5 z:5
Fehler: y<>i für i=10
x:5 y:5 z:5
Fehler: y<>i für i=11
Fehler: y<>i für i=12
Fehler: y<>i für i=13
Fehler: y<>i für i=14
Fehler: y<>i für i=15

usw.............. hmmm sollte glaub ich nicht so sein