Potenzieren ohne Power-Funktion

[Faffy]

Hey Leute,

wir machen gerade eine RSA-Verschlüsselung & dafür benötige ich natürlich folgende Foreml zur Berechnung der Verschlüsselung:

Delphi-Quellcode:

C := V mod(N);

Dabei ist C die Verschlüsselung, V der zu verschlüsselnde Text hoch den öffentlichen Schlüssel & N das Produkt aus den beiden Primzahlen (P & Q).

Mein Problem dabei ist, dass ich die Potenz

Delphi-Quellcode:

V := X^E;

nicht mit

Delphi-Quellcode:

V := Power(X, E);

rechnen darf, da V nicht Extended sein darf. Denn ist V Extended, so lässt sich V nicht mit

Delphi-Quellcode:

mod(N)

berechnen.

(E ist der öffentliche Schlüssel & X der zu verschlüsselnde Text).

Hoffe ihr könnt mir helfen.

Gruß
Faffy

[gammatester]

In einem solchen Fall benutzt man die http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation, wobei bei jedem Produkt mod N reduziert wird, siehe meine Funktion hier http://www.delphipraxis.net/780375-post23.html

Gruß Gammatester

[himitsu]

Man kann das Extended doch auch wieder zu einem Integer runde (Round) oder abschneiden (Trunc).

Zur hälft hilft dir IntPower.

Aber wenn es sonst nicht geht, dann .... Wie hattest du das Potenzieren denn mal in der Schule gelernt?
Das kannst du ja nachmachen. (am Billigsten mit einer Schleife und * )

[gammatester]

Zitat:

Zitat von himitsu (Beitrag 1245993)

Man kann das Extended doch auch wieder zu einem Integer runde (Round) oder abschneiden (Trunc).

Zur hälft hilft dir IntPower.

Das bringt doch alles nix weil zB selbst 12345^5678 ~ 0.3065E23232 nicht in ein extended passt, aber 12345^5678 mod (997*101) = 25102 einfach zu berechnen ist. Es hilf nichts: nach jedem Schritt mod N bilden! Wenn N kleiner Maxint=2^31-1 kann man mit int64 rechnen:

Delphi-Quellcode:

int64(a)*int64(b) mod N

[himitsu]

Er hatte ja nicht verraten, wie groß seine Werte sind und ob die nicht doch rein passen.
Aber mit aktiver Überlaufprüfung, wäre es dann schon aufgefallen. :stupid: