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! :xmas:

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

[Alexander]

Es ging mir eigentlich nur um den Befehl mod. Der wurde jetzt hier so oft erklärt und ich dachte mir, ich schreibe diese Umformung auch mal dazu.

[Gandalfus]

Zitat:

Zitat von Ryan

Gibt es keinen Variablentyp des Integers, der mehr Zahlen umfasst als der normale?

int64 ?

[Ryan]

Ähm, zu meiner Schande muss ich gestehen ich habe keine Ahnung was es mit der Bezeichnung int64 auf sich hat.... Ist das ein Variablentyp und wenn ja, wie groß ist er?

Und danke für die definition von mod.

[Christian S.]

Hallo!

int64 ist eine Vorzeichenbehaftete Größe im Bereich von –2^63..2^63–1.

Allerdings solltest Du erst einmal die von mir gepostete Function ausprobieren. Das sollte Dich schon mal ein Stück weiter bringen.

MfG
Peter

[Ryan]

Ich daaanke vielmals. Das löst mein Problem, Peter.

Vielen Dank. Ich bin beeindruckt wie schnell das ging - das Forum is klasse.
Nochmals Danke an alle, die was geschrieben haben.

[Ryan]

Das Programm funktioniert jetzt einwandfrei - allerdings bleibt mir eine Frage:

Was macht die BigModulo - funktion (mathematisch gesehen)?
Ich habe versucht es zu verstehen, aber ich bin nicht hinter den Trick gekommen.