linuxqtrsa加密解密，使⽤Qt实现⼀个简化版的RSA加密算法这⼀篇⽂章主要是实现⼀个有界⾯的、简化版的RSA加密，学习⾮对称加密的基本原理和算法。
⼯程的代码可以在这⾥下载：资源下载
本⽂⽬录
⼀、RSA算法的基本实现过程
1.公钥/私钥对的⽣成
(1)选择两个不同的素数(质数)p、q
(2)计算它们的乘积n=p×q
(3)计算欧拉函数Ф(n)=(p-1)(q-1)
(4)选择与Ф(n)互素(互质)，并且⼩于Ф(n)的整数e
(5)计算d，使得d×e mod Ф(n) = 1
2.加密和解密的计算
(1)加密公式
(2)解密公式
(3)加密解密的迭代计算
⼆、实验环境
三、关键代码
1.⽣成密钥对
2.加密解密
四、编译结果
⼀、RSA算法的基本实现过程
与对称加密算法中不同，RSA算法的密钥是成对的两个数值，称之为公钥/私钥对。⽽且，公钥/私钥对也不是随机⽣成的两个数值，他们之间必须符合某种特定的关系。
⽬前⽹络使⽤的RSA算法的公钥/私钥长度可达1024bit，甚⾄2048bit。为简化计算起见，本次将减⼩密钥的长度，同时采⽤随机的⽅法产⽣密钥，以降低算法的复杂性。
1.公钥/私钥对的⽣成
⽣成公钥/密钥对的算法基本步骤如下：
(1)选择两个不同的素数(质数)p、q
此处，为了⽅便，将p、q限制为1000以内的素数。同时，为了达到p和q的随机性，先将1000以内的素数存放在⼀个数组中，然后⽣成两个随机数抽取其中的两个不同的素数。注意随机数要加上时间随机种⼦。
(2)计算它们的乘积n=p×q
(3)计算欧拉函数Ф(n)=(p-1)(q-1)
(4)选择与Ф(n)互素(互质)，并且⼩于Ф(n)的整数e欧拉linux系统
此处的e也采⽤随机的⽅法产⽣。
(5)计算d，使得d×e mod Ф(n) = 1
令k=1,2,3,… 搜索直到使得(Ф(n)×k+1)能被e整除，计算d= Ф ( n ) × k + 1 e \frac{Ф(n)×k+1}{e}eФ(n)×k+1。结果的密钥分别为公钥{e,n}和私钥{d,n}。
2.加密和解密的计算
以下的P代表明⽂(Plain)。C代表密⽂(Cipher)。
(1)加密公式
C=Pe mod n
(2)解密公式
P=Cd mod n
(3)加密解密的迭代计算
由于幂运算速度⽐较慢，在这⾥采⽤了下⾯的迭代公式等价替换了幂运算的操作。
C=Pe mod n=(…(((P*P mod n)*P mod n)*P mod n)…)*P mod n(其中需要有e个P相乘)
解密公式也是同理。
⼆、实验环境
软件：Qt Creator 3.3.0(Based on Qt 5.4.0)
系统：Windows 10
三、关键代码
代码中的phi表⽰的是Ф(n)。
1.⽣成密钥对
bool isPrime(int num);//判断是否为素数
int gcd(int a, int b);//求a、b的最⼤公约数
int prime_num[168];//1000以内的素数
int p,q,e,d,n,phi;
long long plain,cipher;//明⽂和密⽂
//⽣成1000以内的素数的数组
int a = 0;
for(int i=1;i<=1000;i++)
{
if(isPrime(i))
{
prime_num[a] = i;
a++;
}
}
/
/随机产⽣p、q并计算n和phi
srand(time(NULL));
p = prime_num[(rand()%168)]; q = prime_num[(rand()%168)]; n = p*q;
phi = (p-1)*(q-1);
//计算e
do{
e = (rand()%(phi-2))+2;
}while(gcd(e,phi) != 1);
//计算d
for(int k=1;;k++)
{
if((phi*k+1)%e == 0)
{
d = (phi*k+1)/e;
break;
}
}
以下是辅助函数。
bool isPrime(int num)
{
if(num == 1)
return false;
for(int i=2;i
{
if(num % i == 0)
return false;
}
return true;
}
int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
2.加密解密
加密迭代计算
cipher = plain;
for(int i=1;i
cipher = (cipher*plain)%n;
解密迭代计算
plain = cipher;
for(int i=1;i
plain = (plain*cipher)%n;
四、编译结果
先在窗⼝中点击“⽣成密钥”，然后再输⼊明⽂(注意明⽂的数字要⼩于n)，最后加密明⽂。明⽂=1234，加密得密⽂为161619。
最后将上⾯获得的密⽂解密⼀下，来验证设计的算法的正确性。
密⽂=161619，解密得到明⽂为1234，与上⾯相符，所以是正确的。
⼯程的代码可以在这⾥下载：资源下载