Реализация RSA в Octave

Question

Я пытаюсь реализовать простой пример вычисления RSA в Octave, но у меня возникла проблема при использовании p и q больше 9900 (простых чисел). Я подозреваю, что это из-за ограничения размера числа в Octave?

Есть ли другой подход, который я могу попробовать? Благодаря

Я использую этот алгоритм для генерации ключей:

function [n,Phi,d,e] = rsa (p,q) 
x=2;i=1; 
n=p*q;       %to calculate n 
Phi=(p-1)*(q-1);     %to calculate Phi 

e=(Phi/4); 
while x > 1 
    e--;      %to calculate e (I know it should be random) 
    x = gcd(Phi, e); 
end 

val1=0; 
d=Phi-e; 
while(val1!=1); 
    d--;      %to calculate d (this is really nasty way, anyone can help?) 
    val1=mod(d*e,Phi); 
end 
endfunction 

, а затем я прочитал сообщение, закодировать его в ASCII и зашифровать его

function result = modexp (base, exponent, modulus) 
result = 1; 
base = mod(base, modulus); 
    while (exponent > 0) 
     if (mod(exponent, 2) == 1) 
      result = mod((result * base) ,modulus); 
     end 
     exponent = bitshift(exponent,-1); 
     base = mod((base * base) ,modulus); 
    end 
endfunction 

по телефону

Msg = toascii(Msg,x); %my function to convert message to ASCII 

for j= 1:x 
    cipher(j)= modexp(Msg(j),e,n); %message encryption 
end 

display(cipher); 

for j= 1:x 
    message(j)= modexp(cipher(j),d,n); %message decryption 
end 

display(message) 

Как я уже говорил, этот код не работает для p и q больше, чем 9900.

Любая помощь будет очень признательна, спасибо.

PS: весь код можно найти здесь: https://dl.dropboxusercontent.com/u/20809963/rsa.m , но это написано на чешском языке.

Answer 1

OK, я переписал генерирующую код, теперь он работает с большими числами (р и ц до ~ 45000)

function [n,Phi,d,e] = rsa (p,q) 
x=2;i=1; 
n=0;Phi=0;e=0;d=0; 
n=uint64(n); Phi=uint64(Phi); d=uint64(d); e=uint64(e); 

n=p*q; 
Phi=(p-1)*(q-1); 

e = input('e:'); 

if(gcd(Phi,e) > 1) 
    while gcd(Phi, e) > 1 
     if(e<=2) 
      e = Phi/4; 
     else 
      e--; 
     end 
    end 
    printf('e = %i', e); 
end 

if gcd(e,Phi) ~= 1 
    error('d can't be calculated') 
end 
    [c,a,b] = gcd(e,Phi); 
    d = mod(a,Phi); 
endfunction 

Остальная часть кода похожа, я просто литейные все для uint64 :)

Мой код находится здесь, если кто-то хочет попробовать это https://dl.dropboxusercontent.com/u/20809963/rsa.m