寻找较大素数，简易实现RSA密码系统matlab

%计算较大素数
function e = PRIMEN(n)
isnot_prime = zeros(1 , n);%判断是否是合数
prime = [];%质数集
if(n == 1)
    e = 1;
    return;
end
for i = 2:n
    if (isnot_prime(i) == 0)
        prime(end + 1) = i;
    end
    for j = 1 : length(prime)
        if((i*(prime(j))>n))
            break;
        end
        isnot_prime(i*(prime(j))) = 1;
        if(mod(i , prime(j)) == 0)
            break;
        end
    end
end
e = prime(end);

寻找随机素数的代码

clc;clear;
w = rand;%w获取0-1的随机数
w1 = floor(10^4*w);%10^4的随机数
w2 = floor(10^4*(1-w));%10^4的另外的随机数
p = PRIMEN(w1);%小于第一个随机数的最大素数
q = PRIMEN(w2);%小于第二个随机数的最大素数
n = p*q;%两个素数的乘积

由于计算机有运行和数据储存限制，这里就用了4次方的随机数。太大容易报错。

生成公钥和私钥

成功获取了两个素数p和q之后,求出两个素数的乘积n = p*q，以及乘积的欧拉函数t = (p – 1)*(q – 1)。

选择一个小于t且与t互逆的正整数e，这里任然采用小于t的最大素数来作为e的取值。然后求出e关于模t的逆元。

之前的文章有讲过四种求逆元的方式。

公钥：pk = [n , e]

私钥： sk = [n , d]

明文为m,密文为c。

加密解密方式

coding：c = m^e mod n

uncoding : m = c^d mod n

实现代码

%计算较大素数
function e = PRIMEN(n)
isnot_prime = zeros(1 , n);%判断是否是合数
prime = [];%质数集
if(n == 1)
    e = 1;
    return;
end
for i = 2:n
    if (isnot_prime(i) == 0)
        prime(end + 1) = i;
    end
    for j = 1 : length(prime)
        if((i*(prime(j))>n))
            break;
        end
        isnot_prime(i*(prime(j))) = 1;
        if(mod(i , prime(j)) == 0)
            break;
        end
    end
end
e = prime(end);

%高次幂的逆元计算
function f = HIGH_POWER_INV(e , n, nn)
E = e;
while(nn>2)
    E = mod(E*e , n);
    nn = nn - 1;
end
f = E;

%计算欧拉函数claculate the Euler function
function e = EULER_F(n)
isnot_prime = zeros(1 , n);%判断是否是合数
prime = [];%质数集
primen = [];%质因数集
if(n == 1)
    e = 1;
    return;
end
for i = 2:n
    if (isnot_prime(i) == 0)
        prime(end + 1) = i;
    end
    for j = 1 : length(prime)
        if((i*(prime(j))>n))
            break;
        end
        isnot_prime(i*(prime(j))) = 1;
        if(mod(i , prime(j)) == 0)
            break;
        end
    end
end
for k = 1:length(prime)
    if(mod(n , prime(k)) == 0)
        primen(end + 1) = prime(k);
    end
end
if(primen(length(primen)) == n)
    e = n-1;
else
    e = n;
    for i = 1 : length(primen)
        e = e*(1 - 1/primen(i));
    end
end
e = floor(e);

%明文加密
function f = coding(m , e , n)
M = m;
while(e>1)
    M = mod(M * m, n);
    e = e - 1;
end
f = M;

%暗文解密
function f = uncoding(c , d , n)
C = c;
while(d>1)
    C = mod(C * c, n);
    d = d - 1;
end
f = C;

clc;clear;
w = rand;%w获取0-1的随机数
w1 = floor(10^4*w);%10^4的随机数
w2 = floor(10^4*(1-w));%10^4的另外的随机数
p = PRIMEN(w1);%小于第一个随机数的最大素数
q = PRIMEN(w2);%小于第二个随机数的最大素数
n = p*q;%两个素数的乘积
t = (p-1)*(q-1);%n的欧拉函数
e = PRIMEN(10^4);%小于nn的某个素数
tt = EULER_F(t);%t的欧拉函数
d = HIGH_POWER_INV(e , t, tt);%e的逆元
M = input('M = ');%明文
PK = [n , e];%生成公钥；
SK = [n , d];%生成私钥；
c = coding(M , e , n);%明文加密 c = m^e (mod n);
m = uncoding(c, d , n);%暗文解密 m = c^d(mod n);
fprintf('PK = [%d ,%d] --- (公钥)\n',PK(1),PK(2));
fprintf('c = %d --- (密文)\n',c);
fprintf('SK = [%d ,%d] --- (私钥)\n',SK(1),SK(2));
fprintf('m = %d --- (明文)\n',m);

运行结果

M = 132
PK = [15047509 ,9973] --- (公钥)
c = 6144046 --- (密文)
SK = [15047509 ,8122641] --- (私钥)
m = 132 --- (明文)

小结

本篇文章是对之前几篇文章所讲内容的综合练习。涉及到求素数，随机数，求逆元这些步骤。

按照我的习惯，还是一堆自定义函数文件，然后最后一个主程序文件。

希望可以对你有所帮助，瑞斯拜。

RSA密码系统

随机寻找两个较大的素数

欧拉筛的算法函数

寻找随机素数的代码

生成公钥和私钥

加密解密方式

实现代码

运行结果

小结

你可能也喜欢