RSA-Verschlüsselung

[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