Dein mod_inv hat einen Bug (außerdem hat es eine ungewöhnliche Parameterreihenfolge: inv_mod(a,b) berechnet nicht
1/a mod b sondern
1/b mod a, solltest du vielleicht mal ändern, zumindest aber hinschreiben). Ich zeige mal die korrigierte Version und ein simples Testproramm mit kleinen Werten:
Delphi-Quellcode:
program t_mrsa2;
{$ifdef WIN32}
{$apptype console}
{$endif}
function mod_inv(A,B:longint):longint;
{-liefert 1/B mod A}
var
n1,n2,b1,b2,q,r,t:longint;
Fertig:Boolean;
begin
if a < 1
then begin
mod_inv:=a;
end
else begin
Fertig:=False;
n1:=A;
n2:=B;
b1:=0;
b2:=1;
repeat
r:=n1
mod n2;
q:=n1
div n2;
if r=0
then begin
if b2 < 0
then b2:=b2+A;
{Fehler!! statt 65537 muss hier A stehen}
mod_inv:=b2;
Fertig:=True;
end
else begin
n1:=n2;
n2:=r;
t :=b2;
b2:=b1-q*b2;
b1:=t;
end;
until Fertig;
end;
end;
function expmod(b,x,m: longint): longint;
var
quad,halb,erg:longint;
{
Berechnet die diskrete Exponentialfunktion b hoch x modulo m
unter ausschließlicher Verwendung der Operationen Quadrieren
und Multiplizieren. Der Rest wird nach jeder Operation bestimmt,
um große Zwischenergebnisse zu vermeiden
mod bezeichnet die Modulo-Operation
div bezeichnet die ganzzahlige Division
}
begin
Quad := b;
{basis}
Halb := x;
{hochzahl}
Erg := 1;
{Ergebnis}
while Halb > 0
do
begin
if Halb
mod 2 > 0
then
Erg := (Erg * Quad)
mod m;
Quad := (Quad * Quad)
mod m;
Halb := Halb
div 2;
end;
expmod := Erg;
end;
var
p,q,n,e,d,phi,i,x,y: longint;
begin
p := 17;
q := 19;
n := p*q;
phi := (p-1)*(q-1);
e := 5;
d := mod_inv(phi,e);
writeln('
d=',d);
for i:=0
to 255
do begin
x := expmod(i,e,n);
y := expmod(x,d,n);
if y<>i
then writeln('
Fehler: y<>i für i=',i);
if (i<11)
or (i>240)
then writeln(i:5, x:5, y:5);
end;
end.
Und hier die Ausgabe, die zeigt, daß alle Zeichen von 0..255 richtig ver/entschlüsselt werden. Setz mal die Werte p=17, q=19, e=5 in Dein Programm ein und vergleiche, ob die Ergebniss dann übereinstimmen.
Wenn alles OK, must Du Dir klar sein, daß RSA in dieser Größenordnung nur für Lernzwecke genutzt werden sollte,
keinesfalls für wirkliche Anwendungen.
Code:
>DCC32 -b t_mrsa2.pas
Borland Delphi for
Win32 compiler version 18.0
Copyright (c) 1983,2005 Borland Software Corporation
t_mrsa2.pas(39) Warning:
t_mrsa2.pas(85)
86 lines, 0.66 seconds, 12508 bytes code, 12176 bytes data.
>T_MRSA2.EXE
d=173
0 0 0
1 1 1
2 32 2
3 243 3
4 55 4
5 218 5
6 24 6
7 11 7
8 145 8
9 263 9
10 193 10
241 90 241
242 276 242
243 116 243
244 194 244
245 215 245
246 94 246
247 76 247
248 210 248
249 146 249
250 224 250
251 302 251
252 199 252
253 138 253
254 220 254
255 221 255