MOD

[Ryan]

Hallo

Ich arbeite derzeit an einer RSA Verschlüsselung und habe ein echtes Problem mit dem mod - Befehl. Irgenwie scheint es, als ob er falsche Werte ausgibt.
Könnte mir jemand sagen, was genau der Befehl mod tut.

Vielen Dank.

[Matze]

Hi!

Herzlich Willkommen in der DP!

mod gibt den Rest aus, der beim Dividieren entsteht.

Code:

Beispiel:

5/3=1 Rest 2

[b]Div[/b] gigt die 1 aus
[b]Mod[/b] die 2

[MrSpock]

Hallo Ryan,

zunächst einmal herzlich willkommen im Delphi-PRAXIS Forum.

Wenn du mit MOD die Modulo Funktion meinst, so gibt die diese den Rest beim Teilen des ersten Operanden durch den 2. zurück. So ist z.B. 6 MOD 4 = 2. Für negative Zahlen ist es etwas komplizierter.

[Ryan]

Vielen Dank für die Information!

Das Problem habe ich gefunden:

Für die RSA Verschlüsselung ist es nötig power(x,d) mod Modul zu berechnen. Ich arbeite zwar nur mit kleinen Zahlen - (Modul = 143, d = 103, und x ist ein ascii - wert von irgendeinem zu verschlüsselnden Zeichen) - aber trozdem kommt die Powerfunktion meistens über die Grenze der höchsten Integerzahl. Realzahlen kann ich hier nicht verwenden, weil Modul sich nur mir Integern berechnen lässt.
Ihr wisst nicht zufällig eine Lösung für das Problem?

Und was das Forum betrifft : Ich finde es großartig und freue mich hier zu sein, habe noch nie ein so gut gemachtes und designtes Delphi-Forum gesehen.

[Chewie]

mod berechnet den Rest einer Ganzzahldivision. Wie willst du den Rest einer Ganzzahldivsion berechnen, wenn du Fließkommazahlen hast?

Du müsstest dann schon einen eigenen Datentyp für große Zahlen machen und da eine mod-Funktionalität reinbasteln. Sowas gibts aber bestimmt schon fertig.

[Nikolas]

So wie ich dein Problem verstehe, hast du dass Problem, dass x^113 größer als der Größte integer wird und dann mist baut.

Vielleicht hilft dir das weiter:

ein Beispiel:
47^29 (mod 91) = (47^16 mod 91) * (47^8 mod 91) *(47^2 mod 91) * (47^2 mod 91) *(47^1 mod) 91

Das heisst, du kannst den Exponenten verkleinern (29=16+8+2+2+1), dann einzeln modulo anwenden und am Ende wieder zusammenbauen.

Ich hoffe dass hilft dir,

Tox

[Alexander]

Folgendes müsste die MOD-Funktion ersetzen können:

Code:

 x mod y = x–(x div y)*y

[Nikolas]

@ Alexander:

Ich glaube das Problem stellt sich schon vor dem mod, nämlich dann wenn bei der entschlüsselung vom RSA der Verschlüsselte Wert mit einem Schlüssel potenziert werden muss und dann noch mit mod verarbeitet werden (o.Ä). Das Problem stellt sich dabei, dass dieser Wert zu groß ist, als das man ihn ohne großen Aufwand speichern könnte.
Und dann bringt diese Umformung auch nicht mehr viel.

Toxman

[Ryan]

Genau das ist das Problem toxman - dein Ansatz ist interessant, aber auch nicht unbedingt einfach zu verwirklichen.
Gibt es keinen Variablentyp des Integers, der mehr Zahlen umfasst als der normale?
Wie programmieren Delphiprogrammierer RSA?

[Christian S.]

Hallo!

Folgende Function habe ich mal für die Berechnung des Modulo in RSA benutzt. War allerdings in Java, ich hoffe, ich habe beim Umschreiben nichts falsch gemacht. Ein paar Stichproben verliefen positiv.

Delphi-Quellcode:

//x^k mod m
function bigModulo (x, k, m : Integer) : Integer;
VAR bit : Array[0..63] OF Boolean;
    i : Integer;
begin
  i := 0;
  while k > 0 do
  begin
    bit[i] := (k mod 2) = 1;
    k := k div 2;
    inc(i);
  end;

  result := 1;

  dec(i);
  while i >= 0 do
  begin
    result := result * result;
    result := result mod m;

    if bit[i] then
    begin
      result := result * x;
      result := result mod m;
    end;

    dec(i);
  end;
end;

MfG
Peter