rsa加密算法c++

千次阅读

2020-05-03 01:38:22

最近因为一些原因对密码学产生了点兴趣，继之前用代码实现BASE64之后最近又搞起了RSA，这让我这个数学渣用从头开始学数学。。。。泪

RSA加密算法

RSA加密算法是由三位MIT大佬发现的，故RSA算法名称由来就是取他们三位名字i的首字母。
RSA算法是一种典型的不对称加密算法，说到不对称加密就会想到对称加密，在密码学加密算法大致可分为两种：对称加密与不对称加密。

对称加密

什么是对称加密，简单来讲就是加密与解密的密钥是相同的，举个简单的栗子，例如我们要对一个字符A加密，字符A即是明文，字符A的ASCII码为65，然后我们用一个十进制数10来做加密密钥，他的加密过程可表示为：密钥+明文，最后得出结果为75即字符K，这里的K即是密文，解密时只需要用相同的密钥10来进行逆运算：75-10就能得到明文，这就是一个最简单的对称加密的例子，当然真正的对称加密算法，过程与密钥不可能这么简单，对称加密代表算法：DES、3DES、TDEA、Blowfish、RC2、RC4、RC5、IDEA、SKIPJACK等。

不对称加密

不对称加密的栗子比较难举，没法用简单的例子来举，总之与对称加密的概念刚好相反，他会用到两个密钥，一个称为公钥，一个称为私钥，通常加密明文时用公钥进行加密，解密时必须要用私钥才能解密，用公钥无法进行解密，代表算法：RSA、Elgamal、背包算法、Rabin、D-H、ECC等。

比较

对称加密算法的优点一目了然：时间复杂度与空间复杂度相对于非对称加密都比较低，而缺点就是不够安全
非对称加密的优点：安全度高，缺点时间空间复杂度较高

这两种加密算法可以结合使用，就能达到相互补短的作用，比如用非对称加密加密密钥然后再用解密出来的密钥再对明文内容进行对称加密，常见https协议大致就用了这样的思路，这样即提高了安全性能又提高了传输速度与资源的占用

RSA算法实现过程

说完上面的前置知识，下面就着重解释RSA算法的实现过程，接下来我来分步骤进行解释：

首先我们需要找两个质数p、q
然后求出p、q的乘积n
然后再取一个欧拉函数φ(n)(欧拉函数百度百科)，φ(n)=(q-1)*(p-1)
然后我们寻找一个公钥e，他要满足以下条件：
1<e<φ(n)
(e,φ(n))=1（公钥e要与φ(n)互质）
然后再去找到一个私钥d，他要满足的条件：
(e*d)%φ(n)=1 (公钥私钥相乘除以φ(n)，余数要为1
现在有了密钥，就该加密环节了，加密过程：
假如我们有一个要发送的数据Y，一个公钥e，首先我们计算Y的e次方即Y^e得到一个数据，然后将这个得到的数据除以n，取得余数，这个取得的余数就是我们需要的密文y，计算过程可表示为:y=(Y^e)%n
现在还要知道如何解密，现在有一个密文y，还有一个私钥d，首先求y的d次方即y^d得到一个数，然后用这个数再除以n，得到的余数就是我们需要的明文Y，计算过程可简单表示为Y=(y^d)%n

然后我们再来看看这种算法能否被破解，假设现在有两端，服务端S，客户端C，S与C之后的通信全部需要进行加密，首先S需要生成公钥与私钥，然后将公钥和一个数n传递给C，并且将私钥保存在本地，C 接收到公钥与n之后就会利用公钥与n来对自己的明文数据或消息进行加密，然后传递给S，S收到后用仅自己拥有的私钥进行解密，再拿到明文消息或数据。

破解方法

让我们康康，在整个传输过程中，作为hacker他能拿到的数据只有公钥e与数字n，他现在需要用这两个数来逆运算推导出私钥d，然后我们在来回头看看私钥d是如何算出来的(e*d)%φ(n)=1，现在我们只知道e与n如果想要再求d就必须要知道φ(n)那φ(n)又是如何计算的呢φ(n)=(q-1)*(p-1)现在我们又需知道p、q才能求出φ(n)，p、q又怎样求，n=p*q，现在不难看出，如果n这个数比较小的话，也许的确有可能通过质数分解求出p、q但如果他是一个非常大的数呢？而RSA算法中常用的是1024比特位的二进制数，就目前技术而言无法将其分解，所以破解RSA加密算法理论上可行，但以目前被普及的技术来说还无法做到（或许、可能、大概、说不定、弄不好有天才数学大佬可以分解吧，但对于普通人来讲是不可能的）当然也有一个特例，那就是量子计算机，但普通人家里谁有量子计算机？

代码实现

实现代码前首先我们要解决几个问题：

如何生成并存储一个1024位128个字节的高精度整数，首先用C语言自带的库很难完成这个工作，那只能考虑第三方库：GMP，这个库支持任意精度的大整数存储与运算
如何得知公钥e与φ(n)互质，用辗转相除法，如果最大公约数为1即为互质，还有一个最快最简单的方法，那就是直接设为一个常用的数字65537即可

首先生成两个大质数：

	mpz_t key_p, key_q, temp_n;
    mpz_t fi, pub_key, pri_key;
    //初始化p,q,n,φ(n),公钥，私钥
    mpz_init(key_p);
    mpz_init(key_q);
    mpz_init(temp_n);
    mpz_init(fi);
    mpz_init(pub_key);
    mpz_init(pri_key);
    /*
    *生成随机1024位质数
    **/
   //随机数种子
    gmp_randstate_t grat;
    //默认生成在随机性与效率之间取一个折中
    gmp_randinit_default(grat);
    //以当前时间作为随机数种子
    gmp_randseed_ui(grat,time(NULL));
    //生成两个个1024位的随机整数
    mpz_urandomb(key_p,grat,1024);
    mpz_urandomb(key_q,grat,1024);
    //生成素数
    mpz_nextprime(key_p,key_p);
    mpz_nextprime(key_q,key_q);

输出结果为：

60317106189242150968029907905478884454926397838
63151192056069393976678696526755735882204871919
60640863409260125737784699838551404308288285427
22202009629439178701380058086593614241889585723
84631477965807444301047539221743520620231455186
51441389685261033128949964706605835556481358609
98173250327588025985739839

66011711808975252037545823728364010624488907689
90643069363083107799625584556500033745996473231
15790980352676928009148324711181846268064324503
83413178315138572996883354239248096907001626608
08392625765952133578008721528020700996465748851
57917174906323291939335096453676892850856698552
86464761830290932578868973

现在我们去计算n与φ(n)：

	/*
    *获得n与φ(n)
    **/
    //p×q得到n
    mpz_mul(temp_n,key_q,key_p);
    //p,q分别减一后相乘得到φ(n),
    //注意结尾的ui表示32位无符号整数
    mpz_sub_ui(key_p,key_p,1);
    mpz_sub_ui(key_q,key_q,1);
    mpz_mul(fi,key_q,key_p);

公钥与私钥获取：

    /*得到公钥e此值可取65537、17、37、47
    *,但要注意，此值除65537以外其他小值
    *做公钥得到的密文是固定不变的，也就是说安全性是不可靠的
    **/
    mpz_set_ui(pub_key,65537);
       
    //逆元运算，求私钥
    mpz_invert(pri_key,pub_key,fi);
    //将公钥私钥与n化为字符串
    mpz_class temp_d(pri_key);
    mpz_class swap_n(temp_n);
    public_key=temp_e.get_str();
    private_key=temp_d.get_str();
    n=swap_n.get_str();

输出结果：

n:
2613885932641755784748607510882050915421352894700858986137412842
0987630493825747297211771889610932122550166024444213136746894207
6644546811985416050557640881973619678619059413712496525559970627
8043143184219087235268656120138267882121069707247964843912512433
8774988087150761110187943552230597253550915681571836928742533421
1054867862933657928417604997759982264669709738037817960310557790
0425911136950171751039667170480765334133554853043160545583229033
5211860578895411731343717290527769002490146989259962541984077360
5698861639713299078187576869256147022559692757370637103995863292
86924700157128795434021572801287758658571
public_key:
65537
private_key:
3988412549615874673464771824895938043275329805607304249717583719
2711949728894742355023531576988467770191137867836814527285188836
3282644631254735570071319837608709093518255967945582686970674012
8542873772401982445440981613650713157637776686830286470104692668
0768097543602485786941641442590593486962960894718764369662545691
8353551197615893923404896499744348438188986738562549978291283277
6902507986697558350861043057925054330262762226384991381287155378
5664270488274091860994402711170314547507999860361506479173635101
8119034090998956073490414694527919620672184154802411523118163683
351078996272709037151947654017045651

我将获取e、d、n的代码单独写成了一个类的成员函数，完整代码：

void RSA::getKey
(
    _Inout_ string& public_key,
    _Inout_ string& private_key,
    _Inout_ string& n
)
{
    mpz_t key_p, key_q, temp_n;
    mpz_t fi, pub_key, pri_key;
    //初始化p,q,n,φ(n),公钥，私钥
    mpz_init(key_p);
    mpz_init(key_q);
    mpz_init(temp_n);
    mpz_init(fi);
    mpz_init(pub_key);
    mpz_init(pri_key);
    /*
    *生成随机1024位质数
    **/
   //随机数种子
    gmp_randstate_t grat;
    //默认生成在随机性与效率之间取一个折中
    gmp_randinit_default(grat);
    //以当前时间作为随机数种子
    gmp_randseed_ui(grat,time(NULL));
    //生成两个个1024位的随机整数
    mpz_urandomb(key_p,grat,1024);
    mpz_urandomb(key_q,grat,1024);
    //生成素数
    mpz_nextprime(key_p,key_p);
    mpz_nextprime(key_q,key_q);
    /*
    *获得n与φ(n)
    **/
    //p×q得到n
    mpz_mul(temp_n,key_q,key_p);
    //p,q分别减一后相乘得到φ(n),
    //注意结尾的ui表示32位无符号整数
    mpz_sub_ui(key_p,key_p,1);
    mpz_sub_ui(key_q,key_q,1);
    mpz_mul(fi,key_q,key_p);
    /*得到公钥e此值可取65537、17、37、47
    *,但要注意，此值除65537以外其他小值
    *做公钥得到的密文是固定不变的，也就是说安全性是不可靠的
    **/
    mpz_set_ui(pub_key,65537);

    //逆元运算
    mpz_invert(pri_key,pub_key,fi);
    //将公钥私钥与n化为字符串
    mpz_class temp_d(pri_key);
    mpz_class swap_n(temp_n);
    mpz_class temp_e(pub_key);
    public_key=temp_e.get_str();
    private_key=temp_d.get_str();
    n=swap_n.get_str();

    mpz_clear(key_p);
    mpz_clear(key_q);
    mpz_clear(temp_n);
    mpz_clear(fi);
    mpz_clear(pub_key);
    mpz_clear(pri_key);
}

_Inout_是我自定义的一个空宏起说明作用，个人习惯不用管他

然后，便是加解密函数，代码比较少，也比较简单，直接用GMP中的模幂函数来求即可：

加密:

string RSA::RSA_Encode
(
    _In_ const char* IN_Data,
     _Inout_ size_t& inoutLen,
    _In_ string public_key,
    _In_ string n
)
{
    mpz_t m,pub_e,temp_n;
    mpz_init(m);
    mpz_init(pub_e);
    mpz_init(temp_n);
    //取得公钥、n、明文，将输入内容统一转化为十进制高精度整数
    mpz_set_str(pub_e,public_key.c_str(),10);
    mpz_set_str(temp_n,n.c_str(),10);
    string out_data;
    /*对字符串循环加密，并用回车隔开
    *防止字符串密文混乱无法辨识
    **/
    for(int i=0;i<inoutLen;i++)
    {
        mpz_set_ui(m,(unsigned long)IN_Data[i]);
        /*
        *模幂操作，取密文
        *c=(m^e) mod n
        **/
        mpz_powm(m,m,pub_e,temp_n);
        //取得字符串
        mpz_class c_data(m);
        out_data.append(c_data.get_str());
        out_data.append("\n");
    }
    inoutLen=out_data.length();

    mpz_clear(m);
    mpz_clear(pub_e);
    mpz_clear(temp_n);
    return out_data;
}

为了解决字符串字符加密后密文存放在一起，无法分清哪个密文属于哪个明文问题，我们采用了使用回车将密文隔开的办法，那么在解密过程中就需要将密文字符串拆解为一个字符串列表来依次处理
解密：

string RSA::RSA_Decode
(
    _In_ string private_key,
    _In_ string n,
    _In_ string c_data,
    _Inout_ size_t& inoutLen
)
{
    vector<string>C_List;
    string temp_str;
    cout<<"\n\n\n\n\n\n";
    //循环拆分字符串，根据原有字符个数拆分为字符串容器列表
    //以此按顺序处理密文
    for(int i=0;i<inoutLen;i++)
    {
        if(c_data.at(i)=='\n')
        {
            C_List.push_back(temp_str);
            temp_str.clear();
            continue;
        }
        temp_str+=c_data.at(i);
    }
    //cout<<"list\n\n"<<C_List.at(0);
    
    mpz_t pri_key,temp_n,C_Data;
    mpz_init(pri_key);
    mpz_init(temp_n);
    mpz_init(C_Data);
    //将字符串转为mpz_t高精度整数
    mpz_set_str(pri_key,private_key.c_str(),10);
    mpz_set_str(temp_n,n.c_str(),10);
    string back_data;
    //循环根据容器个数来判断原本有几个字符，
    //并将其密文解析为明文
    for(int i=0;i<C_List.size();i++)
    {
    	//从字符串取值转化为十进制大整数
        mpz_set_str(C_Data,C_List.at(i).c_str(),10);
        //模幂运算M=(C^d) mod n
        mpz_powm(C_Data,C_Data,pri_key,temp_n);
        //先将取到的明文ASCII转化为C语言基本类型
        //再直接将ASCII码转为字符，再将字符追加进字符串
        //这样就完美还原了明文
        mpz_class CD(C_Data);
        unsigned long lchar=CD.get_ui();
        char words=(char)lchar;
        back_data+=words;
    }
    //返回长度
    inoutLen=back_data.length();
    mpz_clear(pri_key);
    mpz_clear(temp_n);
    mpz_clear(C_Data);
    //返回明文
    return back_data;
}

然后再写一个调试代码：

#include"RSA.h"

int main()
{
    string e,d,n;
    RSA* a=new RSA();
    a->getKey(e,d,n);
    size_t out_len=strlen("啦啦啦");
    string c=a->RSA_Encode("啦啦啦",out_len,e,n);
    cout<<"\n明文:\n啦啦啦\n"<<"密文:\n"<<c<<"\n长度:\n"<<out_len;
    string m=a->RSA_Decode(d,n,c,out_len);
    cout<<"\n\n密文:\n"<<c<<"\n明文:\n"<<m<<"\n长度:\n"<<out_len;
    return 0;
}

加密结果：
在这里插入图片描述

解密结果：
在这里插入图片描述
中文加密没有问题英文加密测试过也是没有问题，所以从上图可以看出仅三个中文字符6个字节的数据就会获得如此庞大的密文，所以不对称加密在传输过程中是极其耗费带宽与时间的，所以并不适合某些高频率传输的场景

完整代码已上传git,地址：
github

数据结构 linux github

更多相关内容

RSA加密算法c++实现
2022-04-07 16:42:20

RSA加密算法的实现，使用c++语言编程，使用dev c++平台编码，文件为cpp格式。经过反复测试代码正确，可搭配RSA讲解教程一起使用，讲解教程点击我的个人主页即可查看，希望能够对你有帮助，谢谢。

收起

RSA加密算法c++简单实现

千次阅读 2019-03-29 13:59:20

RSA是一种非对称加密算法，在公开密钥和电子商业中RSA被广泛使用。它是基于一个很简单的数论事实，两个素数相乘很容易，对两素数乘积因式分解很困难。原理就不再阐述了，我谈谈算法的编程实现过程。一、RSA加密和...

点击打开原文

RSA是一种非对称加密算法，在公开密钥和电子商业中RSA被广泛使用。它是基于一个很简单的数论事实，两个素数相乘很容易，对两素数乘积因式分解很困难。原理就不再阐述了，我谈谈算法的编程实现过程。

一、RSA加密和解密过程是基于以下形式，其中明文为M，密文为C，公匙PU={e, n}，密匙PR={d, n}。

1、准备工作，选择两个大素数p和q，计算p和q的乘积n，计算p-1和q-1的乘积，选择一个与p-1和q-1乘积互质的数e，计算出d

2、加密过程

3、解密过程

程序没有生成大素数，只是列出1000以内的素数，随机取两个素数p和q，利用欧德里德扩展算法计算出e和d，用反复平方法求数的幂

二、程序流程图

#include <iostream>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;


int Plaintext[100];//明文
long long Ciphertext[100];//密文
int n, e = 0, d;

//二进制转换
int BianaryTransform(int num, int bin_num[])
{

	int i = 0,  mod = 0;

	//转换为二进制，逆向暂存temp[]数组中
	while(num != 0)
	{
		mod = num%2;
		bin_num[i] = mod;
		num = num/2;
		i++;
	}

	//返回二进制数的位数
	return i;
}

//反复平方求幂
long long Modular_Exonentiation(long long a, int b, int n)
{
	int c = 0, bin_num[1000];
	long long d = 1;
	int k = BianaryTransform(b, bin_num)-1;

	for(int i = k; i >= 0; i--)
	{
		c = 2*c;
		d = (d*d)%n;
		if(bin_num[i] == 1)
		{
			c = c + 1;
			d = (d*a)%n;
		}
	}
	return d;
}

//生成1000以内素数
int ProducePrimeNumber(int prime[])
{
	int c = 0, vis[1001];
	memset(vis, 0, sizeof(vis));
	for(int i = 2; i <= 1000; i++)if(!vis[i])
	{
		prime[c++] = i;
		for(int j = i*i; j <= 1000; j+=i)
			vis[j] = 1;
	}

	return c;
}


//欧几里得扩展算法
int Exgcd(int m,int n,int &x)
{
	int x1,y1,x0,y0, y;
	x0=1; y0=0;
	x1=0; y1=1;
	x=0; y=1;
	int r=m%n;
	int q=(m-r)/n;
	while(r)
	{
		x=x0-q*x1; y=y0-q*y1;
		x0=x1; y0=y1;
		x1=x; y1=y;
		m=n; n=r; r=m%n;
		q=(m-r)/n;
	}
	return n;
}

//RSA初始化
void RSA_Initialize()
{
	//取出1000内素数保存在prime[]数组中
	int prime[5000];
	int count_Prime = ProducePrimeNumber(prime);

	//随机取两个素数p,q
	srand((unsigned)time(NULL));
	int ranNum1 = rand()%count_Prime;
	int ranNum2 = rand()%count_Prime;
	int p = prime[ranNum1], q = prime[ranNum2];

	n = p*q;

	int On = (p-1)*(q-1);


	//用欧几里德扩展算法求e,d
	for(int j = 3; j < On; j+=1331)
	{
		int gcd = Exgcd(j, On, d);
		if( gcd == 1 && d > 0)
		{
			e = j;
			break;
		}

	}

}

//RSA加密
void RSA_Encrypt()
{
	cout<<"Public Key (e, n) : e = "<<e<<" n = "<<n<<'\n';
	cout<<"Private Key (d, n) : d = "<<d<<" n = "<<n<<'\n'<<'\n';

	int i = 0;
	for(i = 0; i < 100; i++)
		Ciphertext[i] = Modular_Exonentiation(Plaintext[i], e, n);

	cout<<"Use the public key (e, n) to encrypt:"<<'\n';
	for(i = 0; i < 100; i++)
		cout<<Ciphertext[i]<<" ";
	cout<<'\n'<<'\n';
}

//RSA解密
void RSA_Decrypt()
{
	int i = 0;
	for(i = 0; i < 100; i++)
		Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], d, n);

	cout<<"Use private key (d, n) to decrypt:"<<'\n';
	for(i = 0; i < 100; i++)
		cout<<Ciphertext[i]<<" ";
	cout<<'\n'<<'\n';
}


//算法初始化
void Initialize()
{
	int i;
	srand((unsigned)time(NULL));
	for(i = 0; i < 100; i++)
		Plaintext[i] = rand()%1000;

	cout<<"Generate 100 random numbers:"<<'\n';
	for(i = 0; i < 100; i++)
		cout<<Plaintext[i]<<" ";
	cout<<'\n'<<'\n';
}

int main()
{
	Initialize();

	while(!e)
		RSA_Initialize();

	RSA_Encrypt();

	RSA_Decrypt();

	return 0;
}

运行结果：

收起

展开全文

C++实现RSA加密算法
2013-04-11 20:46:30

本例是基于VS2012平台，对于RSA加密算法的实现

收起
rsa加密算法c++实现
热门讨论 2011-06-08 19:59:27

如下式加密算法部分： void CRSAUtilDlg::OnButtonDecrypt() { UpdateData(); CBigNumber cipher; cipher.StringHexFrom(m_strMessageC); BYTE by[8192]; m_pbDE.SetRange(0, 100); DWORD dwTicks = ...

收起
visual c++ vc实现RSA加密算法是最常用的非对称加密算法.zip
2021-01-29 11:52:51

visual c++ vc实现RSA加密算法是最常用的非对称加密算法.zip

收起
RSA加密算法的实现
2018-11-04 19:27:27

此算法的根据学习的密码学，按照自我个人多RSA算法的理解，通过编程实现的，有不完善的地方，请多多包含，且代码仅供参考。

收起
非对称加密算法：RSA算法的C++实现与Java实现
2021-04-23 21:54:30

包括RSA算法的两种语言实现，原理正确，可以正常运行，对应博客为：https://blog.csdn.net/qq_41112170/article/details/104904340

收起

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

2022-07-21 16:48:57

E,N)加密密钥。5.当E=17，L=41580时计算D，得出D=22013。(D,N)解密密钥。4.计算E随机选取一个结果（例E=17）2.加密密钥PK（公开），解密密钥SK（私有）。（1）p,q两个质数,通过线下筛法获取。且E与L互质，即gcd（1，...

一、基本概念

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

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

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

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

二、RSA加密

Hide: 密文

Expose: 明文 $Hide = Expose^{E} modN$

( E , N ) : 加密密钥

三、RSA解密

Hide: 密文

Expose: 明文 $Hide = Exprose^{D}modN$

( D , N ) : 解密密钥

四、具体实现

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

（2）N : N = p * q

（3）L: $L = \phi (pq)=(p - 1)*(q - 1)$

（4）E: $E\epsilon \left ( 1,L \right )$ 且 E与L互质，即gcd（1，L）==1

（5）D： $D\epsilon \left ( 1,L \right )$ 且 E * D mod L = 1

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

#include <iostream>
#include <algorithm>

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<iostream>

using namespace std;

typedef long long ll;

ll gcd(ll x,ll y)//x>y
{
	int t;
	if(x<y)
	{
		t=x;
		x=y;
		y=x;
	}
	return y==0 ? x : gcd(y , x%y);
}

int main()
{
	ll p,q,L={L的值}#;
	
	for(int E=2;E<=L;E++)
	{
		if(gcd(L,E)==1)cout<<E<<endl;
	}
	return 0;
}

5. D的计算

#include<iostream>

using namespace std;

typedef unsigned long long ll;

ll gcd(ll x,ll y)//x>y
{
	ll t;
	if(x<y)
	{
		t=x;
		x=y;
		y=x;
	}
	return y==0 ? x : gcd(y , x%y);
}

int main()
{
	ll p,q,L={L的值}#,E={E的值}#;
	
	for(ll D=2;D<=L;D++)
	{
		if((E%L)*(D%L)%L==1)cout<<D<<endl;
	}
	return 0;
}

五、例子

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<iostream>
#include<cstdio>
#include<algorithm>

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<<"加密后："<<num<<endl;
	
	num=RSAEnc(num,D);
	cout<<"解密后："<<num<<endl;
	
	return 0;
}

结果检验为正确

本人是菜鸡，写这些主要是想记录一些自己的成长过程，如有写的不好的地方欢迎大佬指点指正！

参考:

RSA加密算法原理_张维鹏的博客-CSDN博客_rsa加密算法原理

算法学习笔记(3) RSA原理与证明_HarmoniaLeo的博客-CSDN博客

收起

展开全文

java servlet

RSA加密算法讲解及C++实现

千次阅读 2022-04-07 14:53:24

RSA加密算法的实现，使用c++语言编程。经过反复测试代码正确，可搭配源码一起使用。

一.加密原理

此步骤讲解建立在了解欧拉函数等数学基础和密码学基础上的。

步骤	举例
1.找出质数 P、Q	设P=1 Q=11
2.计算公共模数 *N=PQ**	N=PQ=311=33
3.欧拉函数 *F(N)=(P-1)(Q-1)**	F(33)=F(3)F(11)=(3-1)(11-1)=20
4.计算公钥E 1<E<F(N),E与FN互质	E可取3.7.9.11.13.17.19 假设E=3
5.计算私钥D *ED%F(N)=1**	3*D%20=1 故D取7
6.公钥加密 C= $M^{E}$ modN	假设M=2 C=8
7.私钥解密 M= $C^{D}$ modN	故解得M=2

二.C++实现

实现步骤：首先实现加解密算法、接着实现pqed的生成

其中包括：扩展欧几里得算法、加密函数、解密函数、质数的判定函数、互质的判断等独立函数

3.1实现加解密算法

用最基本思路来做加解密很简单，即为上述6、7步的实现。

void RSAEnc(int& num,int e,int n){
	unsigned long temp = (unsigned long)pow(num,e) % n;
	num = (int)temp;
}

但是很遗憾的是，稍微大一点的数字，都会出现溢出问题。因此，为防止空间时间复杂性过大，在此我们采用二分快速幂算法，用于加快幂次取模速度。

参考博文：快速幂算法（全网最详细地带你从零开始一步一步优化）_刘扬俊的博客-CSDN博客_快速幂算法

什么？没看懂？什么？太长了看不下去？行吧行吧，我们来总结下：

首先，最重要的是了解取模运算运算法则【原理感兴趣的可以自行百度】：

$(a*b)%p = (a%p*b%p)%p$

$(a*b*c)%p = ((a%p)*(b%p)*(c%p))%p$

接着根据这个法则，我们可以根据RSA算法要求推出（E个(M%N)）：

$M^{E}modN=M^{E}%N=((M%N)*...*(M%N))%N$

明白这一点我们就可以，使用取模算法优化我们的代码了，如果使用的指数不太大的完全够用。但是如果幂数很大的情况，还是可能出现溢出问题的。

void RSAEnc(int& num,int e,int n){
//取模运算的运算法则
	int temp = 1;
	for(int i=1;i<=e;i++){
		temp = temp * (num % n);
	}
	num = temp % n;
}

因此我们使用能算出指数非常大的快速幂算法，它通过减小指数的大小，使我们的循环次数大大减小了。【二次快速幂过程主要看上述博文的动画演示，这个动画比较通俗易懂】

但实际上，最重要思想还的就是咱们上述的取模运算运算法则和指数分半，底数平方。

最终优化后即为：

加解密算法示例：

void RSAEnc(int& num,int e,int n){
//取模运算的运算法则
	int temp = 1;
	while(e > 0){
		if(e & 1){
			temp = temp*num%n;
		}
		e >>= 1;
		num = num*num%n;
	}
	num = temp;
}

2.2实现pqed的生成

对于pqed的生成我的实现思路是根据RSA加密原理的步骤一步步往下撸。

2.2.1找出质数P、Q

我使用的是p、q由用户输入，因此仅需要判定p、q是否为素数

示例：

bool IsPrime(int n){
	if(n <= 1)
		return false;
	for(int i=2;i<sqrt(n);i++){
		if((n%i) == 0)
			return false;
	}
	return true;
}

2.2.2计算公共模数**N=P*Q**

这不用说了吧

2.2.3欧拉函数**F(N)=(P-1)*(Q-1)**

这也不用说了吧

2.2.4计算公钥E

分为随机数的生成与互质的判定。

随机数生成：rand随机生成的数的取值范围为[0,x)，故x取fn-2，最终结果再加2，e的取值范围为[2,fn)中的整数。

		srand((int)time(0));
		e = rand()%(fn-2)+2;

互质的判定：辗转相除法求解最大公约数，当余数为0，除数为1时，两数互质。通俗点就是，这俩数的最大公约数为1，那可不就是互质嘛。

//互质的判断
bool IsCOPrime(int x,int y){
	int z;
	while(x%y !=0){
		z = x%y;
		x = y;
		y = z;
	}
	if(z == 1)
		return true;
	return false;
}

2.2.5 计算私钥D

在敲代码的时候，看了很多的讲关于扩展欧几里得算法的文章，通俗易懂的很少，推荐这一篇：扩展欧几里德算法详解_zhj5chengfeng的博客-CSDN博客_扩展欧几里得算法

我们用的是对乘法逆元的计算：

$E*D% \varphi (N)=1$

可以表示为：

$E*D\equiv 1(mod\varphi (N))$

再对比上述文章中的：

$a*x\equiv 1(mod m)$

很熟悉了是不是，我们直接套用就ok了。

int e_gcd(int a,int b,int&x,int&y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int  ans = e_gcd(b,a%b,x,y);
	int temp = x;
	x = y;
	y = temp-a/b*y;
	return ans;
}
//生成私钥d=cal(e,fn);
int cal(int a,int m){
	int x,y;
	int gcd = e_gcd(a,m,x,y);
    if(1%gcd !=0) return -1;
	x *= 1/gcd;
	m = abs(m);
	int ans = x%m;
	if(ans <= 0) ans +=m;
	return  ans;
}

完整代码

完整cpp看这里

不过我相信，聪明的你，看完了一定能自己写出来的对吧？看什么看，还不点赞！

收起

展开全文

RSA加密算法C++实现
2016-04-17 10:15:08

非对称RSA加密算法的C++实现，有公钥和私钥，可完整运行

收起
RSA加密算法C++
2010-12-17 00:24:25

RSA加密算法C++，密码学课上编的，128位，cmd运行

收起
RSA加密算法的C++实现（仅为理解用）
2020-10-08 13:29:40

这篇文章是RSA加密算法的简易版本，密钥支持不了1024位，水平有限，只是拿来作为理解RSA加密的（怕自己以后忘了） #include<iostream> #include<cmath> using namespace std; int fast_mod(int base,...

收起
RSA加密算法 C++ 实现
热门讨论 2010-07-29 11:29:05

RSA加密算法 C++ 实现，RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止...

收起
RSA公钥加密算法C++实现（可运行）
千次阅读 2021-10-14 20:17:53

#include #include #include "time.h" #include using namespace std; unsigned char msg[8] ={ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' };...j 参考自RSA加密解密C++实现_ermeiyao11的博客-CSDN博客_c++实现rsa加解密

收起
RSA-2048算法代码（C++）
2019-07-31 11:22:21

用C++实现的RSA算法代码，秘钥长度可调，没有依赖外部库。基于VS 2017实现。

收起
RSA加密算法 C++实现
千次阅读 2017-06-23 21:29:28

上信息安全课，老师布置了几个大作业，其中一个为RSA加密算法的实现，不能用Java写。出于兴趣，决定尝试。完成之后，为了便于查找，于是写下这篇文章，以备后续查看。也供大家一起学习，一起进步。 1、预备知识 1.1 ...

收起
非对称性加密算法——RSA算法原理及C++实现
千次阅读 多人点赞 2021-03-18 09:23:20

什么是非对称加密算法三. 双方交换信息工作流程四.密钥生成数学原理五.总结公钥和私钥生成步骤六.解决大数运算1.getCountAdd() 解决大数相加2. getCountExp() 解决大数幂运算3. getCountmod() 解决大数求余七.举个...

收起

字符串
rsa加密算法的c++简单实现
2011-05-25 22:26:30

rsa加密算法是密码学的基础算法，利用编程语言进行简单的实现是必备技能

收起
rsa_c.zip_RSA算法_rsa_rsa c++_rsa 加密_rsa加密
2022-07-14 13:16:13

rsa加密算法源程序

收起
c++通过openssl实现rsa加密解密【windows版】
2019-06-18 20:28:28

c++通过使用openssl实现rsa加密解密算法，网上有很多文章和例子，但是大部分都是linux版的，并且内容不全、代码老旧等各种问题，导致最后无法调试，这里提供的源码是用code::blocks编写的c++源码，可以直接运行...

收起
rsa加密算法源代码c++实现.pdf
2020-12-12 11:14:02

收起
【信息安全】RSA非对称加密算法原理（详解和C++代码实现）
千次阅读 2021-05-30 20:44:36

1.RSA非对称加密 (1)选择两个素数p和q ,计算n=p*q和欧拉函数φ(n)=(p-1)(q-1)，选择整数e，使gcd(φ(n), e)=1（即φ(n)和e是互素），1<e<φ(n)； (2)计算e的逆元d=e-1mod φ(n)（即ed = 1 mod φ(n)）； (3)...

收起
RSA_C++实现,rsa算法c语言实现,C,C++
2021-09-10 22:30:10

经典的对称加密算法RSA算法的C++实现版本，亲测完美运行

收起
基于C++的RSA加密算法
2013-10-29 10:05:23

程序由Visual Studio 2008编写，针对RSA那个程序，需先安装Visual Studio 2008运行库“vcredist_x86_vs2008_sp1.exe”（已经附带），否则程序将无法正常运行。

收起
C++ Aes与Rsa加密算法使用
2020-08-06 17:03:31

rsa = RSA_generate_key(MAX_RSA_KEY_LENGTH, RSA_F4, nullptr, nullptr); unsigned char pubKeyData[MAX_RSA_KEY_LENGTH] = { 0 }; int pubKeyLen = i2d_RSAPublicKey(rsa, nullptr); unsigned char* p = ...

收起

openssl
RSA 加密算法的实现与破解
千次阅读 2021-10-20 18:47:53

实验二：实现RSA加密算法，根据已知明文计算出RSA的加密密文，并解密。 1、选择一对不同的、足够大的素数 p，q。 2、计算 n=pq。 3、计算 f(n)=(p-1)(q-1)，同时对 p, q 严加保密，不让任何人知道。 4、找一个与...

收起

RSA加密算法

对称加密

不对称加密

比较

RSA算法实现过程

破解方法

代码实现

RSA加密算法c++实现

RSA加密算法c++简单实现

点击打开原文

C++实现RSA加密算法

rsa加密算法c++实现

visual c++ vc实现RSA加密算法是最常用的非对称加密算法.zip

RSA加密算法的实现

非对称加密算法：RSA算法的C++实现与Java实现

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

RSA加密算法讲解及C++实现

目录

一.加密原理

二.C++实现

3.1实现加解密算法

加解密算法示例：

2.2实现pqed的生成

2.2.1找出质数P、Q

2.2.2计算公共模数N=P*Q

2.2.3欧拉函数F(N)=(P-1)*(Q-1)

2.2.4计算公钥E

2.2.5 计算私钥D

完整代码

RSA加密算法C++实现

RSA加密算法C++

RSA加密算法的C++实现（仅为理解用）

RSA加密算法 C++ 实现

RSA公钥加密算法C++实现（可运行）

RSA-2048算法代码（C++）

RSA加密算法 C++实现

非对称性加密算法——RSA算法原理及C++实现

rsa加密算法的c++简单实现

rsa_c.zip_RSA算法_rsa_rsa c++_rsa 加密_rsa加密

c++通过openssl实现rsa加密解密【windows版】

rsa加密算法源代码c++实现.pdf

【信息安全】RSA非对称加密算法原理（详解和C++代码实现）

RSA_C++实现,rsa算法c语言实现,C,C++

基于C++的RSA加密算法

C++ Aes与Rsa加密算法使用

RSA 加密算法的实现与破解

rsa加密算法c++

2.2.2计算公共模数**N=P*Q**

2.2.3欧拉函数**F(N)=(P-1)*(Q-1)**