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

目录

RSA密码系统

随机寻找两个较大的素数

欧拉筛的算法函数

 寻找随机素数的代码

生成公钥和私钥

加密解密方式

实现代码

运行结果

小结

首先来了解一下什么是RSA算法。

RSA密码系统

RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，被认为是最优秀的公钥方案。RSA算法的核心原理是：随机选择两个大素数，将两个素数的乘积作为加密核心。从两个大素数的乘积进行因式分解求出两个大素数的过程是NP困难的，十分费时，暴力破解很难，所以具有较高的安全性。

在百度百科上有详细的内容，可以参考一下，本文只做略述。

RSA算法_百度百科

随机寻找两个较大的素数

我们可以利用随机数生成函数randn，来生成一个0~1之间的随机数，乘以适当的倍数，达到要想的数量级，然后求出小于这个数的最大素数。 

求最大素数的方法还是用的欧拉筛的算法。感兴趣的读者可以去看一看讲欧拉定理求逆元的那篇文章。

代码如下：

欧拉筛的算法函数

%计算较大素数
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 --- (明文)

小结

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

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

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