RSA-Verschlüsselung

[brushmate]

Hi,

ich versuch gerade die RSA-Verschlüsselung zu programmieren, bin jetzt auch eigentlich fertig damit, aber das Programm lässt sich nicht starten, bzw. hängt sich auf.
Es wird noch icht einmal das formular erstellt...

Könnt ihr mir sagen wodrann's liegt?

[TurboMartin]

Beim ertsellen deiner Form kommt es zur starken Auslastund deines Programms. Das kommt daher, dass du beim Erzeugen deiner Form direkt dein TRSA erstellst. Beim Erstellen führst Du eine sehr unperformante suche nach deinen 2 Primzahlen aus. Jenachdem, wie dein PC dich mag, kann es sein dass diese Suche so zur Endlosschleife wird. Zudem prüfst Du deine Zahl dann mit jeder Zahl darunter. Dabei könntest Du direkt die Teilbarkeit durch alle Primzahlen bis Zufallszahl/2 (nicht optimiert). Das ist eigentlich das grobe. Am besten ins OnShow, und dann warte ne Zeit lang.
[edit]hier mehr zur Primzahlfindung[/edit]

[generic]

Warum willst du das Rad neu erfinden? Es gibt doch OpenSSL. Da ist alles drin was man braucht.

[xxl1]

er schreibt da ne facharbeit drüber, steht hier

[brushmate]

jep^^

die methode wie ich die primzahlen finde hat ohne den rest einwandfrei funktioniert und auch schnell..
ich hab jetzt mal den zahlen bereich aus dem der eine zahl raten soll auf 30 geändert und der erstellt trotzdem nicht die form
also liegts wohl eher nicht daran

[brushmate]

onShow funktioniert auch nicht alo der erzeugt kein formular

[g1o2k4]

das problem mit der endlosschleife von:

Delphi-Quellcode:

  repeat
    help := random(46340);
  until isPrime(help);

wurde ja schon angesprochen. wenn du es so machen willst solltest du wenigstens die geprüften zahlen aus der menge der zahlen von 0..46340 rausstreichen indem du sie zum beispiel in ein array oder stringlist schreibst und bei jedem schleifen durchlauf prüfst, ob die zahl bereits getestet wurde. aber selbst das ist verschwenderisch programmiert.

und zu dem isPrime test:

Delphi-Quellcode:

function TRSA.isPrime(x: Integer): Boolean;
var i, t: integer;
begin
  t := round(sqrt(x));
  for i := 2 to t do   
    if x mod i = 0 then
      begin          
        result := false; 
        exit;
      end;
    result := true;
end;

ist zwar auch nicht perfekt aber immerhin nur sqrt(x) schleifendurchläufe statt x.


ich hab auch mal nen primzahl generator gemacht...dabei hatte ich ein array of boolean genommen und jeden array index geprüft ob es eine primzahl ist, wenn ja array[index] := true, wenn nein := false. dann könntest du am ende alle true-werte in ein neues array schreiben und dann neues_array[random(high(neues_array)] machen. dann wird dir eine zufällige primzahl ausgegeben.

[g1o2k4]

ich kann dir die primzahl generierung auch schicken wenn du willst, aber so schwer ist das ja eigentlich nicht.

[brushmate]

Wie schon gesagt glaube ich eigentlich nicht, dass es daran liegt, dass er zu lange braucht um die Primzahlen zu finden. ich kann das random(46340) auch auf random(3) setzen und der macht immer noch nix... Und aus 3 Zahlen 2 mögliche Primzahlen mit meiner Methode zu raten kann wohl nict sehr lange dauern

[brushmate]

Soo hab den Fehler jetzt gefunden:

Delphi-Quellcode:

constructor TRSA.create();
var help: Integer;
begin
  randomize;
  repeat
    help := random(46340);
  until isPrime(help);
  p := help;
  repeat
    repeat
      help := random(46340);
    until isPrime(help);
    q := help;
  until p <> q;
  N := p*q;
  phi := (p-1)*(q-1);
  repeat                                  //
    e := random*(N-1);                    //
  until (e > 1) and ((ggT(e, N)) = 1);    //irgendein Fehler
  repeat
    d := random*N;
  until modulo((e*d), phi) = 1;
  p := 0;
  q := 0;
  phi := 0;
end;

Der Fehler liegt in der markierten Schleife...

[fortuneNext]

Schon lustig, eine Facharbeit schreibe ich auch über Kryptographie, aber RSA ist bei mir nur einer der 5 behandelten Algorithmen :D
Bei mir ist jetzt aber auch ein winzig kleines Problem aufgetaucht, und ich bin mir nicht sicher, ob ich ein neues Topic eröffnen soll... Der Titel trifts hier eigentlich ganz gut :D

Und zwar:
p = 7
q = 13
N = 91
Eul N = 72
e = 23
d = 47
Klartext = 1337
Verschlüsselt: 84
Entschlüsselt: 63

Das macht doch keinen Sinn.
Das Problem liegt scheinbar in der modularen Exponentation. Ist normal, dass ein solch falsches Ergebnis herauskommt? Ich kann es mir ja im Prinzip vorstellen, denn mod 91 auf eine 1337 anzuwenden kann ja nicht zum gewünschten Ergebnis führen...
Gut, dass mir der Fehler jetzt schon auffällt - Abgabe am Montag.
:-O

Delphi-Quellcode:

function ExpMod(b, x, m: integer): integer;
var
  quad, halb: integer;
begin
  quad := b;
  halb := x;
  Result := 1;
  while halb > 0 do
  begin
    if halb mod 2 > 0 then
      Result := (Result * quad) mod m;
    quad := (quad * quad) mod m;
    halb := halb div 2;
  end;
end;

Delphi-Quellcode:

function TRSA.Decrypt(text:String; d, N:integer):string;
var
  x, temp:integer;
begin     {
  temp := 1;
  for x := 1 to d do
    temp := (temp * StrToInt(text) mod N);
  Result := IntToStr(temp);              }
  Result := IntToStr(ExpMod(StrToInt(text), d, N));
end;

(Das im Kommentar bringt dasselbe Ergebniss, ist auch dieselbe Methode wie zum Verschlüsseln. So ganz hab ich noch nicht verstabden, wozu die Exponentation gebraucht wird, man kann es ja auch einfach berechnen...
Auf jeden Fall weiss ich nicht ob ich was falsch gemacht habe, oder ob ich vielleicht nur schlechte Zahlen gewählt habe?
Danke!

Grüße
fortuneNext

[Klaus01]

Zitat:

Zitat von fortuneNext

So ganz hab ich noch nicht verstanden, wozu die Exponentation gebraucht wird, man kann es ja auch einfach berechnen...

Überlege Dir doch mal wie groß die Zahlen werden wenn p und q mal etwas größer werden.
Das schaft der Wertebereich von Power nicht mehr,

Grüße
Klaus

[Klaus01]

@brushmate

.. könnte der Fehler/das Problem hier liegen?

Delphi-Quellcode:

e := random*(N-1);

Laut der delphi Hilfe liefert random ein float Wert zurück.

Zitat:

Zitat von DelphiHilfe

Random returns a random number within the range 0 <= X < Range. If Range is not specified, the result is a real-type random number within the range

0 <= X < 1.

Dann wird es später schwierig mit der ggT Funktion
und dann hast Du eine wunderbare Endlosschleife.

Grüße
Klaus

[brushmate]

Das habe ich jetzt mit round behoben funktioniert auch recht schnell...allerdings kommt dann in der nächsten repeat-Schleife wieder dasselbe Problem. round hilft dabei auch nicht

Ich hab mal mit einer for schleife alle werte ausprobiert die e annehmen könnte(aus dem von mir definierten Zahlenbereich) passen aber irgendwie alle nicht bei dem d*e mod phi = 1

[Klaus01]

.. warum multiplizierst Du denn random mit einem Wert?
Willst Du nicht einen zufälligen Wert aus einem Wertebereich?

also anstelle

Delphi-Quellcode:

e:= random*(N-1)

so

Delphi-Quellcode:

e:=random(N-1)

?

Grüße
Klaus

[brushmate]

In der Delphi-Hilfe steht, dass random ohne Paramater einen Wert 0 < x <= 1 zurückgibt (einen float-wert). Als Parameter kann nur Integer übergeben werden N ist aber Extended. Durch die Multiplikation kann der Zufallswert also höchstens N-1 werden

[Klaus01]

Zitat:

Zitat von brushmate

In der Delphi-Hilfe steht, dass random ohne Paramater einen Wert 0 < x <= 1 zurückgibt (einen float-wert). Als Parameter kann nur Integer übergeben werden N ist aber Extended. Durch die Multiplikation kann der Zufallswert also höchstens N-1 werden

.. aber auch wieder ein extended Wert und so weit ich weiß fußt RSA
auf Ganzzahloperationen.

Wieso ist N extended
p (integer) mit q(integer) multipliziert ergibt doch wieder einen, wenn auch großen, Integerwert.

Grüße
Klaus

[brushmate]

Das mit den ganzen Zahlen besteht ja auch weiterhin. durch das round wird der Wert für e ja ganzzahlig.

Ich speichere p*q in N und N ist Extended. Integerwerte kann man ja in Float Variablen speichern.

[brushmate]

So funktioniert jetzt...kann allerdings nur die 1 verschlüsseln :-D ansonsten kommt ein Overflow Fehler

[fortuneNext]

Zitat:

Zitat von Klaus01

Zitat:

Zitat von fortuneNext

So ganz hab ich noch nicht verstanden, wozu die Exponentation gebraucht wird, man kann es ja auch einfach berechnen...

Überlege Dir doch mal wie groß die Zahlen werden wenn p und q mal etwas größer werden.
Das schaft der Wertebereich von Power nicht mehr,

Grüße
Klaus

Hmmm kann es sein, dass der kommentierte Code schon diese Exponentation ist? x_X Dann hab ich die nämlich gemacht, ohne zu wissen, was das ist :D
Fraglich ist dann für mich noch, warum das laut Wikipedia nicht auch bei der Verschlüsselung gemacht wird, dort kommen doch ähnlich hohe Wert vor...
Und ob das richtig so ist mit der Verschlüsselung ist mir noch unklar, aber dafür mach ich mal nen eigenes Topic auf ;-)

http://www.delphipraxis.net/internal...015915#1015915

[Klaus01]

Hallo brushmate,

ich habe mal so einiges in Deiner mRSA Unit geändert (u.a. extended nach Int64 geändert)
Kannst es Dir ja einmal anschauen.

Grüße
Klaus

[brushmate]

wow...vielen Dank