RSA кодирование...

реализую РСА кодирование но наткнулся вот на какую фигню...
дописал всё доконца вроде как работает , но расшифрование происходит неверное ...
начал выяснять в чём дело взял большие числа из примера в книги...
неудаётся найти ключ d в этом алгоритм... он ищется но со значениями в книге расходится...
вот алгоритм нахождения д :

e:=strtoint(edit3.text); // мы сами вводим простое число... нод его и Ф равен 1(всё правильно вообщем )
for d:=2 to f-1 do
begin
if ((d*e) mod f) = 1 then break; // если такое д находится то прыгаем из цикла
end;

label6.caption:=inttostr(d);

и так значения : p=2357 q=2551 получили n=6012707 f=(p-1)(q-1)=6007800
выбрали e = 3674911 , и вот d ищется по ф-ле ed=1(mod f) в книги получилось
d=422191 у меня d=3527239
возможно из-за этого и происходит неправиьное декодирование ... помогите не могу понять ошибку...

 

а почему не воспользоваться GMP например? Там для поиска D можно юзать mpz_invert (инверсию по phi(N)) - и предельно оптимизировано будет.

 

это как ?

 

библиотека GMP (GNU MultiPrecision library) - скачай и компилируй

 

а без всяких доп. библиотек...???

 

hiiamnoob
какой тип у d, e, f?

 

var
Form1: TForm1;
n,p,q,f,d,e,z:integer;
cry:array of integer;
mas : array of char;
s : string;
вот...

 

hiiamnoob
умножь (6007800-1)*3674911, в integer явно не влезает

 

ну а если взять значение поменьше то кодирование или декодировани идём коряво вот прога вся, что не так ?:
function Z_GCD(a, b: Integer): Integer;
var
c: Integer;
begin
while b <> 0 do
begin
c := a mod b;
a := b;
b := c;
end;
Result := a;
end;


Function Prost(n:integer):Boolean;
var k:Boolean;
i:integer;
begin
k:=true;
if n<>2 then
for i:=2 to trunc(sqrt(n))+1 do
if (n/i)=trunc(n/i) then
begin
k:=False;
Break;
end;
Prost:=k;
end;
{$R *.dfm}


procedure TForm1.Button1Click(Sender: TObject);
begin
p:=strtoint(edit1.text);
q:=strtoint(edit2.text);
n:=q*p;
label3.caption:=inttostr(n);
prost (p);
if prost (p) = false then showmessage('данное p - не простое');
prost (q);
if prost (q) = false then showmessage('данное q - не простое');
f:=(p-1)*(q-1);
label4.Caption:=inttostr(f);
end;

procedure TForm1.Button2Click(Sender: TObject);
begin

e:=strtoint(edit3.text);

for d:=2 to f-1 do
begin
if ((d*e) mod f) = 1 then break;
end;

label6.caption:=inttostr(d);
end;

procedure TForm1.Button3Click(Sender: TObject);
var
Mas : array [1..9592] of LongInt;
N, i, k : LongInt;
Root : Integer;
Flag : Boolean;

begin
k := 0;
for N := 2 to f do
begin
i := 1;
Flag := True;
Root := Round(Sqrt(N)) + 1;
while (i <= k) and (Mas < Root) and Flag do
begin
if N mod Mas = 0 then
Flag := False;
i := i + 1
end;
if Flag then
k := k + 1;
Mas[k] := N;

for d:= 2 to f-1 do
if ((d*n) mod f) = 1 then listbox1.items.add(inttostr(n));


end;
end;

procedure TForm1.Button5Click(Sender: TObject);
var i,t,j,x,m:integer;w:char ;

begin
s:=edit4.text;
i:=0;
while i<=length(s) do
begin
setlength(cry,i+1);
SetLength(mas,i+1);
mas:=s;
inc(i);
end;
i:=1;
while i<=length(s) do
begin
w:=mas;
x:=ord(w);
label10.Caption:=label10.Caption+' '+inttostr(x);
m:=x;
for t:=1 to e-1 do
begin
x:=(x*m mod n);
end;
cry:=x;
inc(i);

label5.Caption:=label5.Caption+' '+inttostr(x);
end;

end;


procedure TForm1.Button6Click(Sender: TObject);
var x,m,i,t:integer;
begin
i:=1;
while i<= length(s) do
begin
label11.caption:=label11.caption+' '+inttostr(cry);
inc(i);
end;

i:=1;
while i<=length(s) do
begin
x:=cry;
m:=x;
for t:=1 to d-1 do
begin
x:=((x*m) mod n);
end;
label8.Caption:=label8.Caption+' '+inttostr(x);
mas:=chr(x);
label9.Caption:=label9.Caption+' '+mas;
inc(i);


end;
end;

end.

 

ну что никто не поможет?

 

Умножение и возведение в степень по модулю длинных чисел руками собрался делать? Только время зря убъешь, имхо.
Если не хочешь делать как все (т.е. нормально) возьми в качестве примера исходник зомби - в 29А-8 кажется есть (rsalib.asm) - там на асме это реализовано. Вполне рабочий вариант, но по времени - в разы медленнее GMP (это к вопросам о библиотеках). К тому же, GMP линкуется в модуль статически, поэтому библиотек в понимании "дополнительных длл" у тебя не будет.

 

hiiamnoob
Вся RSA вкратце выглядит так:

modulus = P * Q
phi = lcm(P-1,Q-1) //http://en.wikipedia.org/wiki/Least_common_multiple

// Calculate or choose E
// 1 < E < modulus
// E must be ODD
// E and phi are co-prime - GCD(e,phi) == 1

D = E^-1 mod phi // http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

 

Еск... а как нормельно чем не нравится вот такое возведение в степень ?
m:=x;
for t:=1 to e-1 do
begin
x:=(x*m mod n);
end;
в данном случе реализуем y=x^e mod n

 

...мдя - а обратный процесс каким образом планируется сделать?
d как правило имеет тот же порядок что и phi(N), тогда как phi(N) имеет порядок самого N - получается, чтобы возвести в степень d тебе надо будет провести примерно (число с порядком N) итераций.
Вообще, возведение руками если все же хочешь сделать, посмотри алгоритм Карацубы, да даже в том же исходнике rsalib - используется куда как более оптимизированный вариант.
Как это сделано в rsalib, например, возводим число m в степень e по модулю N:
- показатель степени (e) в битовом представлении сканируется от младшего бита к старшему - если найдена 1 - умножаем предыдущий результат на m, иначе - возводим предыдущий результат в квадрат. - сложность алгоритма - lg2(e) итераций, следовательно, для обратного преобразования (возведение в степень d) понадобится всего lg2(d), что даже для 1024 битного модуля не очень много.

 

m:=x;
for t:=1 to d-1 do
begin
x:=(x*m mod n);
end;
в данном случе реализуем x=y^d mod n
это оюбратный... напишите или дайте ссылкке на ресуры где всё ясно написанно... а то вы пишете... а мне это ничего и не помогает скажем так...

 

ECk
Это не Карацуба, это exponentiation by squaring (второе название - square-and-multiply algorithm). http://en.wikipedia.org/wiki/Exponentiation_by_squaring
Карацуба же придумал ускорение умножения. http://en.wikipedia.org/wiki/Karatsuba_multiplication
для преобразования с закрытым ключом (d) было бы разумнее применить китайскую теорему об остатках - получится куда как быстрее. http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem

hiiamnoob
Мы то пишем, только ты похоже или не читаешь или не понимаешь
Вообще рекомендую следующую литературу (если проблем с английским нету)
Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.
Там в разделе Efficient Implementation есть эффективные алгоритмы для работы с длинной математикой такие как: Addition and subtraction, Multiplication, Squaring, Division, Montgomery reduction, Montgomery multiplication, Barrett reduction, Binary gcd algorithm, Lehmer’s gcd algorithm, Binary extended gcd algorithm, Chinese remainder theorem for integers, Garner’s algorithm, пачка разных exponentiation включая наиболее быстрый Montgomery exponentiation.
В общем все что тебе надо. + описано достаточно понятным языком.
Могу прислать мылом всю книгу в pdf (~4.8 Mb) или только этот раздел (~370 Kb)

 

CreatorCray
Читай внимательнее

Я разве сказал что в rsalib.asm Карацуба?

 

вё нашёл в чём ошибка!!! просто Д у меня бралось равное Ф так как бежали по д... вообщем ступил я конкретно... теперь всё декодирует... но с числами 200+ иногда проблемы я так понимаю это из-за слишком больши чисел? (для интегера )

 

Вообще-то числа должны быть размером 128 байт. (Сравни с размером интеженра - 4 байта.)

 

ECk
>> Читай внимательнее
>> Я разве сказал что в rsalib.asm Карацуба?
В след раз просьба выражать свои мысли яснее, или хотя бы правильно расставлять знаки препинания. Потому как из фразы:

напрашивается предположение что описываемый далее алгоритм как раз и есть тот самый алгоритм Карацубы.
:beer: