C++實現(xiàn)RSA加密解密算法是示例代碼

更新時間：2022年09月22日 14:42:25 作者：sunny-ll

非對稱加密方式可以使通信雙方無需事先交換密鑰就可以建立安全通信，因此被廣泛應(yīng)用于身份認證、數(shù)字簽名、等信息交換領(lǐng)域。其中最具有代表性的非對稱加密方式就是RSA公鑰密碼體制。本文將用C++實現(xiàn)RSA加密解密算法，需要的可以參考一下

一、什么是RSA算法

在計算機中常用的加密算法分為兩類：對稱加密算法和非對稱加密算法。

1.對稱加密

在對稱加密技術(shù)中，對信息的加密和解密都使用了相同的密鑰Key，也就是說使用同一個密鑰Key對數(shù)據(jù)進行加密和解密。這種加密方法可簡化加解密的處理過程，信息交換雙方都不必彼此研究和交換專用的加解米算法。如果在交換階段，密鑰Key沒有泄露，那么加密數(shù)據(jù)的機密性和報文的完整性就可以得到保證。

2.非對稱加密

在非對稱加密中，不再只有一個密鑰Key了。在非對稱加密算法中，密鑰被分解為一對，一個稱為公開密鑰，另一個稱為私有密鑰。對于公鑰，可以通過非保密方式向他人公開，而私鑰則由解密方保密，不對別人公開。

3.非對稱加密的應(yīng)用

由于非對稱加密方式可以使通信雙方無需事先交換密鑰就可以建立安全通信，因此被廣泛應(yīng)用于身份認證、數(shù)字簽名、等信息交換領(lǐng)域。其中最具有代表性的非對稱加密方式就是RSA公鑰密碼體制。

二、RSA算法的基礎(chǔ)操作步驟

1.生成公鑰和私鑰

生成公鑰PK和私鑰SK的步驟如下：

（1）隨意選擇兩個大的素數(shù)P、Q，P不等于Q。

此處在算法實現(xiàn)中需要快速的判斷P、Q是否為素數(shù)，代碼如下：

ll primeNum(ll num)   //判斷素數(shù)
{
    if (num == 1 || num == 0)
    {
        return 0;
    }
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            // 不是素數(shù)返回0
            return 0;
        }
    }
    return 1; //是素數(shù)返回1
}

（2）將P、Q兩個素數(shù)相乘得到一個N，即N=PQ

（3）將P、Q分別減一，再相乘，得到一個數(shù)T，即T=（Q-1）*（P-1）

（4）選擇一個整數(shù)E，作為一個密鑰，使E與T互質(zhì)（即E與T的最大公約數(shù)為1），且E必須小于T

此處在算法實現(xiàn)中需要對E與T進行互質(zhì)的判斷（最大公約數(shù)為1）

//判斷兩個數(shù)是否互素
ll coprime(ll a, ll b)  //判斷互質(zhì)
{
    ll t;
    if (a < b)
    {
        t = a; 
        a = b; 
        b = t;
    }
    while (a % b)
    {
        t = b;
        b = a % b;
        a = t;
    }
    //返回值為1，則a，b互素
    return b;
}

（5）根據(jù)公式DE mod T = 1 ，計算出D的值，作為另一個密鑰。

此時根據(jù)算法，逆向求D

    d = 1;
    //求e的乘法逆
    while (((e * d) % t) != 1) 
        d++;

（6）通過以上的步驟就可以求出N，E，D這三個數(shù)據(jù)，其中（N，E）作為公鑰，（N，D）作為私鑰。

（7）生成公鑰和私鑰后，就可以對外發(fā)布了，其中RSA算法的詳細的流程圖如下：

2.用公鑰加密信息

發(fā)送信息的一方收到公鑰PK后，就可以通過公鑰PK對數(shù)據(jù)進行加密，加密的操作步驟如下圖所示，其中明文為：M，密文為：C

明文：M

加密：

密文：C

其中加密的算法，先進行密文的取余運算在加密，代碼如下：

//計算密文
ll candp(ll b, ll p, ll k) //b--明文或密文   p--指數(shù)(e/d)    k--模數(shù)
{
    if (p == 1)
    {
        return b % k;
    }
    if (p == 2)
    {
        return b * b % k;
    }
    if (p % 2 == 0)
    {
        ll sum = candp(b, p / 2, k);
        return sum * sum % k;
    }
    if (p % 2 == 1)
    {
        ll sun = candp(b, p / 2, k);
        return sun * sun * b % k;
    }
}

在進行加密運算

ll encryption()
{
    ll n, e, x, y;
    cout << "請輸入公鑰(e，n)" << endl;
    cin >> e >> n;
    cout << "請輸入明文: (明文需小于" << n << ")" << endl;  //計算密文
    cin >> x;
 
    y = candp(x, e, n);
    cout << "密文為:" << y << endl;
    return 0;
}

3.用私鑰解密信息

接收方持有私鑰（N，D）在接受到密文C后，既可以通過私鑰解密，得到明文M，解密過程如下：

密文：C

解密：

明文：M

其中解密算法，先產(chǎn)生密鑰Key算法：

ll key()
{
    ll p, q, t, n, e, d;
    cout << "請輸入兩個素數(shù) p,q: " << endl;    //輸入兩個素數(shù)q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素數(shù)" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的歐拉函數(shù)
    t = (p - 1) * (q - 1);
 
    cout << "請輸入密鑰e: " << endl;
    cin >> e;
    d = 1;
    //求e的乘法逆
    while (((e * d) % t) != 1) 
        d++;
 
    cout << "n = p * q = " << n << endl;
    cout << "t = (p - 1) * (q - 1) = " << t << endl;
    cout << ("公鑰(e,n)為:(") << e << "," << n << ")" << endl;
    cout << ("私鑰(d,n)為:(") << d << "," << n << ")" << endl;
    return 0;
}

在進行解密：

ll decode()
{
    ll n, d, x, y;
    cout << "請輸入私鑰(d，n)" << endl;
    cin >> d >> n;
    cout << "請輸入密文: ";  //計算密文
    cin >> y;
 
    x = candp(y, d, n);
    cout << "明文為:" << x << endl;
    return 0;
}

三、AC代碼

新建一個頭文件RSA.h

#pragma once
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
// 判斷素數(shù)
ll primeNum(ll num);
// 判斷互質(zhì)
ll coprime(ll a, ll b);
// 計算密文
ll candp(ll b, ll p, ll k);
// 生成密鑰
ll key();
//加密
ll encryption();
//解密
ll decode();
// 菜單
void menu();

將函數(shù)寫在RSA.cpp中，用于主函數(shù)RSA（）的調(diào)用代碼如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include "RSA.h"
void menu()
{
    printf("------------------------------------------\n");
    printf("*****        請選擇所需功能          *****\n");
    printf("*****          1.生成鑰匙            *****\n");
    printf("*****          2.加密                *****\n");
    printf("*****          3.解密                *****\n");
    printf("*****          4.退出                *****\n");
    printf("------------------------------------------\n");
}
ll primeNum(ll num)   //判斷素數(shù)
{
    if (num == 1 || num == 0)
    {
        return 0;
    }
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            // 不是素數(shù)返回0
            return 0;
        }
    }
    return 1; //是素數(shù)返回1
}
//判斷兩個數(shù)是否互素
ll coprime(ll a, ll b)  //判斷互質(zhì)
{
    ll t;
    if (a < b)
    {
        t = a; 
        a = b; 
        b = t;
    }
    while (a % b)
    {
        t = b;
        b = a % b;
        a = t;
    }
    //返回值為1，則a，b互素
    return b;
}
//計算密文
ll candp(ll b, ll p, ll k) //b--明文或密文   p--指數(shù)(e/d)    k--模數(shù)
{
    if (p == 1)
    {
        return b % k;
    }
    if (p == 2)
    {
        return b * b % k;
    }
    if (p % 2 == 0)
    {
        ll sum = candp(b, p / 2, k);
        return sum * sum % k;
    }
    if (p % 2 == 1)
    {
        ll sun = candp(b, p / 2, k);
        return sun * sun * b % k;
    }
}
//生成密鑰
ll key()
{
    ll p, q, t, n, e, d;
    cout << "請輸入兩個素數(shù) p,q: " << endl;    //輸入兩個素數(shù)q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素數(shù)" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的歐拉函數(shù)
    t = (p - 1) * (q - 1);
 
    cout << "請輸入密鑰e: " << endl;
    cin >> e;
    d = 1;
    //求e的乘法逆
    while (((e * d) % t) != 1) 
        d++;
 
    cout << "n = p * q = " << n << endl;
    cout << "t = (p - 1) * (q - 1) = " << t << endl;
    cout << ("公鑰(e,n)為:(") << e << "," << n << ")" << endl;
    cout << ("私鑰(d,n)為:(") << d << "," << n << ")" << endl;
    return 0;
}
//加密
ll encryption()
{
    ll n, e, x, y;
    cout << "請輸入公鑰(e，n)" << endl;
    cin >> e >> n;
    cout << "請輸入明文: (明文需小于" << n << ")" << endl;  //計算密文
    cin >> x;
 
    y = candp(x, e, n);
    cout << "密文為:" << y << endl;
    return 0;
}
//解密
ll decode()
{
    ll n, d, x, y;
    cout << "請輸入私鑰(d，n)" << endl;
    cin >> d >> n;
    cout << "請輸入密文: ";  //計算密文
    cin >> y;
 
    x = candp(y, d, n);
    cout << "明文為:" << x << endl;
    return 0;
}

在寫出主函數(shù)test.c,對上面的函數(shù)進行調(diào)用即可：

#include "RSA.h"
void RSA()
{
    while (1)
    {
        menu();
        ll i = 0;
        cin >> i;
        switch (i)
        {
        case 1:
            key();
            break;
        case 2:
            encryption();
            break;
        case 3:
            decode();
            break;
        case 4:
            exit(0);
        default:
            cout << "輸入錯誤,請重新輸入" << endl;
        }
    }
}
void menu1()
{
    printf("******************************************\n");
    printf("******************************************\n");
    printf("*****     歡迎來到RSA加密測試系統(tǒng)   ******\n");
    printf("******************************************\n");
    printf("******************************************\n");
}
int main()
{
    menu1();
    RSA();
    return 0;
}