C++实现基础RSA加密算法

一、基本概念

1.RSA加密算法为非对称加密方法，即加密与解密使用不同的密钥。

2.加密密钥PK（公开），解密密钥SK（私有）。

3.加密算法E与解密算法D都公开

4.具体数学证明参考：算法学习笔记(3) RSA原理与证明_HarmoniaLeo的博客-CSDN博客

二、RSA加密

Hide: 密文

Expose: 明文                        

( E , N ) : 加密密钥                       

三、RSA解密

Hide: 密文

Expose: 明文                        

( D , N ) : 解密密钥         

四、具体实现

（1）p , q : 两个质数,通过线下筛法获取

（2）N : N = p * q

（3）L: 

（4）E:    且 E与L互质，即gcd（1，L）==1

（5）D： 且 E * D mod L = 1

1. 获取两个质数p，q（线性筛法）

#include 
#include 

using namespace std;

const int N = 10000100;

//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << primes[--cnt] << endl;
    return 0;
}

2. N的获取

N = p * q即可

3. L的计算

据公式L = (p-1)*(q-1)

4. E的计算

#include

using namespace std;

typedef long long ll;

ll gcd(ll x,ll y)//x>y
{
	int t;
	if(x 
 
5. D的计算
 
#include

using namespace std;

typedef unsigned long long ll;

ll gcd(ll x,ll y)//x>y
{
	ll t;
	if(x 
五、例子
 
1. 当p = 199，q = 211时
 
2. L = (p - 1)*(q - 1) = 198 * 210 = 41580
 
3. N = p * q = 41989
 
4. 计算E：随机选取一个结果（例 E = 17）
 
 
5.  当E = 17 ，L = 41580时 计算D，得出D = 22013
 
 
 
 
6. 带入样例代码中测试
 
#include
#include
#include

using namespace std;

typedef unsigned long long ULL;

ULL N,L,E,D;

ULL RSAEnc(ULL num,ULL Z)//RSA加解密  num为数据 Z为指数项 
{
	
	ULL ans=1;
	ULL i=Z;
	while(i>0)
	{
		if(i&1)
		{
			ans=((ans%N)*(num%N))%N;
		}
		num=((num%N)*(num%N))%N;
		i=i>>1;
	}
	return ans%N;
}

int main()
{
	ULL num;
	N=41989;E=17;D=22013;
	
	cin>>num;
	
	num=RSAEnc(num,E);
	cout<<"加密后："< 
结果检验为正确
 
 
 本人是菜鸡，写这些主要是想记录一些自己的成长过程，如有写的不好的地方欢迎大佬指点指正！
 
参考:
 
RSA加密算法原理_张维鹏的博客-CSDN博客_rsa加密算法原理
 
算法学习笔记(3) RSA原理与证明_HarmoniaLeo的博客-CSDN博客