algorithm - Octave 中的 RSA 实现

Question

我试图在 Octave 中实现一个简单的 RSA 计算示例，但在使用大于 9900(质数)的 p 和 q 时遇到问题。我怀疑这是因为 Octave 中的数字大小限制？

我可以尝试另一种方法吗？谢谢

我正在使用此算法生成 key :

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)

正如我所说，对于大于 9900 的 p 和 q，此代码会失败。

非常感谢任何帮助，谢谢。

PS:完整代码可以在这里找到: https://dl.dropboxusercontent.com/u/20809963/rsa.m但它是用捷克语写的。

Answer 1

好的，我重写了生成代码，现在它可以处理更大的数字(p 和 q 高达 ~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