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

[schweindi]

Hallo alle,
ich werkle jetzt schon länger an einigen Programmen für die Schule und brauche jetzt für das letzte noch RSA.

Ich habe eig alles schon fertig geschrieben, leider funzt da irgendetwas nicht ganz perfekt und ich bin mir ziemlich sicher, dass es mit hohen Potenzen und anschließenden modulo Rechnungen zusammenhängt.

So jetzt mal was ich bisher gemacht habe:

Delphi-Quellcode:

p:=p1;
q:=q1;
N:=p*q;
phiN:=(p-1)*(q-1);
repeat
e:=Random(1024);
until ((e mod  phiN)<>0)and(e<2048);
d:=mod_inv(phiN,e);

da sind einmal p, q, N, und phi(N) sowie e und dann das multipl. Inverse von phi(N) und e.
p1 & q1 sind integer generiert aus Random(2048)...

mod_inv(phiN,e) befindet sich in einer dll, die ich für alle Programme verwende:

Delphi-Quellcode:

function mod_inv(A,B:Integer):Integer;export;
var n1,n2,b1,b2,q,r,t:Integer;
Fertig:Boolean;
begin
if a < 1 then
  begin
  Result:=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+65537;
    Result:=b2;
    Fertig:=True;
   end else
    begin
    n1:=n2;
    n2:=r;
    t:=b2;
    b2:=b1-q*b2;
    b1:=t;
    end;
  until Fertig;
  end;
end;

so und hier noch der letzte teil:
Input = ein Text von Edit1.Text
symbcode(Input) = eine funktion, die jeden Buchstaben in die entsprechende Zahl umwandelt (A:1,B:2,C:3...)
ich habe iwo gelesen, man könnte es auch direkt mit den ASCII codes machen und dann glaub ich char() aber ich wollte es mal so probieren.
Die function hab ich schon getestet und sie gibt die richtigen Werte aus.

Delphi-Quellcode:

for i:=1 to length(Input) do
begin
debug:=StrToInt(symbcode(Input)[i]);
Memo1.Lines.Add('Eingabe: '+IntToStr(debug)+' d: '+Inttostr(d));
y:=expmod(debug,e,N);
Memo1.Lines.Add('Code: '+IntToStr(y));
Memo1.Lines.Add('Klartext: '+IntToStr(expmod(y,d,N)));
end;

so und jetzt noch die function expmod(a,b,c)... ich hatte leider keine Ahnung wie ich von den "riesen Zahlen" mod rechen soll, wenn sie hunderte stellen haben, deshalb hab ich diese function verwendet, ka wo ich sie gefunden hab.
(unverändert)

Delphi-Quellcode:

function expmod(b,x,m :integer):extended;export;
  var
    quad,halb,erg:Integer;
   {
    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;
  result := Erg;
end;

bei kleinen werten:
e,d=3
p,q < 100 funktioniert es bei A=01 aber sobald e,d,p,q größer werden oder B=02 eingegeben wird kommt es zu Fehler, so dass der "codierte"Buchstabe plötzlich den Wert 0 bekommt...

sieht jemand schon einen Fehler?

lg
Schweindi

[gammatester]

RSA setzt voraus, daß p und q Primzahlen sind!

[schweindi]

ahaaa... naja daran hab ich eig nicht gedacht

ja ich änder das mal schnell und mal sehen...
danke!

[schweindi]

also, es werden jetzt immer schöne primzahlen verwendet..
2 mögliche Fehler:
1) die verschlüsselung / entschlüsselung ergibt immer noch 0
2) der "Code" "Klartext" ist bei G(7) gerade 75 gewesen... da kann also auch iwas nicht stimmen, aber danke für den primzahlen Hinweis!

[himitsu]

Über RSA findet man Einiges, aber auch nicht zuviel ... schau dir doch einfach mal einige dieser Threads an.

[gammatester]

Das Ergebnis von expmod ist extended, also kann eigentlich

Delphi-Quellcode:

y:=expmod(debug,e,N);
Memo1.Lines.Add('Code: '+IntToStr(y));

nicht übersetzt werden. Wenn y integer ist, geht die erste Zeile nicht, sonst die zweite. Hast Du eventuell expmod in Deinem Code als integer deklariert und die DLL liefert extended? Warum ist überhaupt das Ergebnis von expmod extended, da Du doch alles integer rechnest?

[schweindi]

so ich habe jetzt mal das ergebnis von expmod zu integer gemacht und hab eben auch bemerkt:

Bei RSA muss ja N > text zum verschlüsseln -> ich versuch mal p&q ordentlich groß zu machen und e ein bisschen einzuschränken, damit das auch mal stimmt.

Kann ich da, damit es größer wird, integer ersetzen? Ich weiß, dass extended der größte Typ ist, aber da gibt es doch probleme mim Darstellen bzw bei mir ging aus trunc(extendend) oft ein Floating Point error hervor?

[gammatester]

Die Größe von e ist das kleinste Problem. Wenn Du statt integer überall den größeren Typ int64 nimmst, kannst Du für p,q bis zu ca 55000 gehen.

[schweindi]

ahso... naja ich dachte nur weil der klartext ^e genommen wird, aber ich sehe ja bei expmod ist die hochzahl ja umgangen...

Und noch eine frage, ist es notwendig 2-3 zeichen zusammenzufassen oder kann man, so wie ich jeden buchstaben einzeln verschlüsseln?

was für zahlen kann ich mir da erwarten bei e:=1024, p,q ca. 25000-30000 und die zu verschlüsselnde Zahl 1-41?

EDIT:
Ich habe jetzt mal alle "großen Zahlen" zu Int64 gemacht und es läuft jetzt mal sehr schön, aber nur wenn ich A(01) eingebe...

Dann berechnet er schön:
input = 1
Code = 1 also A

Wenn ich aber zb B(02) eingebe bzw Z(26) dann sieht das so aus:
[B(02)]:
input = 2
d = -20138308
Code = 1 (sollte 2 sein!)
Klartext = 2145688 (entschlüsselt, sollte auch 2 sein)

[Z(26)]:
input = 26
d = 41659327
Code = 1 (sollte 26 sein!)
Klartext = 3188353 (entschlüsselt, sollte auch 26 sein)

also schließe ich richtig, dass "d", also das multiplikative inverse falsch berechnet wird?

[himitsu]

Schalte mal die Überlaufprüfung ein.
siehe Projektoptionen