RSA密码算法C++实现

小鱼儿 2023-10-04 16:13 42阅读 0赞

#### 文章目录 ####

*  1. RSA非对称加密原理
 *  2. C++ 随机生成密钥版本
 *  3. 密钥固定e=13版本

## 1. RSA非对称加密原理 ##

> 网上一大把，这里推荐一篇比较好的[博客][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4_size_16_color_FFFFFF_t_70]

## 2. C++ 随机生成密钥版本 ##

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include<string.h>
    #include <math.h>
    #include<algorithm>
    
    using namespace std;
    typedef long long ll;
    
    // e是公钥
    // d是私钥
     
    ll e, d, n;
    
    ll gcd(ll a, ll b)  //求最大公约数
    {
        ll c = 0;
        if(a<b) swap(a,b);
        c = b;
        do
        {
            b = c;
            c = a%b;
            a = b;
        }
        while (c != 0);
        return b;
    }
    
    // 0不是 1是 
    ll isPrime(ll i) //判断i是否是素数
    {
        ll flag=0;
        for(ll a=2; a<i; a++)
        {
            if(i%a==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==1) return 0;
        else return 1;
        
    }
    
    ll myPow(ll a, ll b, ll n)  //求a^b mod n
    {
        ll y;
    
        /*使用二进制平方乘法计算 pow(a,b) % n*/
        y=1;
    
        while(b != 0)
        {
            /*对于b中的每个1，累加y*/
    
            if(b & 1)
                y = (y*a) % n;
    
            /*对于b中的每一位，计算a的平方*/
            a = (a*a) % n;
    
            /*准备b中的下一位*/
            b = b>>1;
        }
    
        return y;
        
    }
    
    void extgcd(ll a,ll b,ll& d,ll& x,ll& y) 
    {
        if(!b)
        {
            d=a;
            x=1;
            y=0;
        }
        else
        {
            extgcd(b,a%b,d,y,x);
            y-=x*(a/b);
        }
    }
    
    ll ModularInverse(ll a,ll b)  //获取(1/a)mod b的结果
    {
        ll d,x,y;
        extgcd(a,b,d,x,y);
        return d==1?(x+b)%b:-1;
        
    }
    
    void KeyGeneration()  //获取公钥密钥
    {
        ll p, q;
        ll phi_n;
    
        do
        {
            do
                p = rand();
            while (p % 2 == 0);
    
        }
        while (!isPrime(p)); 	// 得到素数 p 
    
        do
        {
            do
                q = rand();
            while (q % 2 == 0);
        }
        while (!isPrime(q)); 	// 得到素数q 
    
        n = p * q;
        phi_n = (p - 1) * (q - 1);
    
        do
            e = rand() % (phi_n - 2) + 2; // 1 < e < phi_n
        while (gcd(e, phi_n) != 1);
    
        d = ModularInverse(e,phi_n);
    }
    
    // 一位一位地输出加密的结果 
    ll Encryption(ll value)  //加密
    {
        ll cipher;
        cipher = myPow(value, e, n);
        cout<<cipher;
        return cipher;
    }
    
    // 一位一位地输出解 密的结果 
    void Decryption(ll value)  //解密
    {
        ll decipher;
        decipher = myPow(value, d, n);
       	cout<<decipher;
    }
    int main()
    {
    	/******
    	
    	对6位的数字进行稳定加密 
    
    	******/
    	ll num;
    	cout<<"请输入要加密的明文数字,ctrl+c结束"<<endl;
    	while(cin>>num){
    		ll de;
    		cout<<"输入的明文为"<<num<<endl; 
    	    KeyGeneration();  //获取公钥密钥
    	    cout<<"加密密钥："<<e<<endl; 
    	    cout<<"加密结果为:";
    		de = Encryption( num );
    		cout<<"\n私钥为："<<d;
    //		cout<<"de="<<de<<endl;
    		cout<<"\n解密结果"; 
    		Decryption(de);	
    		cout<<"\n-------------"<<endl;
    	}
        return 0;
    }

## 3. 密钥固定e=13版本 ##

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include<string.h>
    #include <math.h>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    
    char map[30] = {
    	'a', 'b', 'c', 'd', 'e','f','g',
    	'h', 'i', 'j', 'k', 'l', 'm', 'n',
    	'o', 'p', 'q', 'r', 's', 't', 
    	'u', 'v', 'w', 'x', 'y', 'z'
    	};
    //cp存密文， ep存明文 
    char cp[1000], ep[1000];
    int lcp , lep ;
    
    ll getNum(char a, char b){
    	int aa,bb;
    	for(int i=0; i<30; i++){
    		if(map[i]==a){
    			aa = i;
    		}
    		if(map[i]==b){
    			bb = i;
    		}
    	}
    	return aa*100+bb;
    }
    // flag = 1, 解密转换得到的是明文
    // flag = 2 加密转换得到的是密文 
    void toChar(ll num, int flag = 1){
    	int a = num/100;
    	int b = num%100;
    	a %= 26;
    	b %= 26; 
    	cout<<map[a]<<map[b]<<" "<<endl;
    	if(flag==1){
    		ep[lep++] = map[a];
    		ep[lep++] = map[b];
    	} 
    	else if(flag==2){
    		cp[lcp++] = map[a];
    		cp[lcp++] = map[b];
    	}
    }
    
    
    // e是公钥
    // d是私钥
     
    ll e, d, n;
    
    ll gcd(ll a, ll b)  //求最大公约数
    {
        ll c = 0;
        if(a<b) swap(a,b);
        c = b;
        do
        {
            b = c;
            c = a%b;
            a = b;
        }
        while (c != 0);
        return b;
    }
    
    // 0不是 1是 
    ll isPrime(ll i) //判断i是否是素数
    {
        ll flag=0;
        for(ll a=2; a<i; a++)
        {
            if(i%a==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==1) return 0;
        else return 1;
        
    }
    
    ll myPow(ll a, ll b, ll n)  //求a^b mod n
    {
        ll y;
    
        /*使用二进制平方乘法计算 pow(a,b) % n*/
        y=1;
    
        while(b != 0)
        {
            /*对于b中的每个1，累加y*/
    
            if(b & 1)
                y = (y*a) % n;
    
            /*对于b中的每一位，计算a的平方*/
            a = (a*a) % n;
    
            /*准备b中的下一位*/
            b = b>>1;
        }
    
        return y;
        
    }
    
    void extgcd(ll a,ll b,ll& d,ll& x,ll& y) 
    {
        if(!b)
        {
            d=a;
            x=1;
            y=0;
        }
        else
        {
            extgcd(b,a%b,d,y,x);
            y-=x*(a/b);
        }
    }
    
    ll ModularInverse(ll a,ll b)  //获取(1/a)mod b的结果
    {
        ll d,x,y;
        extgcd(a,b,d,x,y);
        return d==1?(x+b)%b:-1;
        
    }
    
    void KeyGeneration()  //获取公钥密钥
    {
        ll p, q;
        ll phi_n;
    	
    	p = 43; q = 59, e=13;
        n = p * q;
        phi_n = (p - 1) * (q - 1);
    
        
    
        d = ModularInverse(e,phi_n);
    }
    
    // 一位一位地输出加密的结果 
    ll Encryption(ll value)  //加密
    {
        ll cipher;
        cipher = myPow(value, e, n);
        cout<<"加密得到的数字="<<cipher<<"\t加密得到的字母=";
    	toChar(cipher, 2);
        return cipher;
    }
    
    // 一位一位地输出解 密的结果 
    void Decryption(ll value)  //解密
    {
        ll decipher;
        decipher = myPow(value, d, n);
       	cout<<"解密得到的数字="<<decipher<<"\t解密得到的字母=";
    	toChar(decipher, 1);
    }
    int main()
    {
    	lcp = 0, lep = 0;
    	char st[] = "cybergreatwall";
    	KeyGeneration();
    	cout<<"e="<<e<<" d="<<d<<" n="<<n <<endl;
    	int len = strlen(st);
    //	cout<<st<<" "<<len<<endl;
    	for(int i=0; i<len; i+=2){
    		cout<<"加密的明文="<<st[i]<<st[i+1]<<endl;
    		ll num = getNum(st[i], st[i+1]);
    		cout<<"明文对应的数字"<<num<<endl;
    		ll de = Encryption( num );
    		Decryption(de);	
    	}
    	cp[lcp] = '\0';
    	ep[lep] = '\0';
    	cout<<"加密的结果为"<<cp<<endl;
    	cout<<"解密的结果为:"<<ep<<endl;
    	
    
        return 0;
    }

--------------------

完结撒花，cv可用

[Link 1]: https://blog.csdn.net/jijianshuai/article/details/80582187?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162339029516780269846997%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162339029516780269846997&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-80582187.first_rank_v2_pc_rank_v29&utm_term=RSA&spm=1018.2226.3001.4187
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210611154442978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzA0MDQ4,size_16,color_FFFFFF,t_70