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

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

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

一、什么是RSA算法

在計(jì)算機(jī)中常用的加密算法分為兩類：對(duì)稱加密算法和非對(duì)稱加密算法。

1.對(duì)稱加密

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

2.非對(duì)稱加密

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

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

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

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

1.生成公鑰和私鑰

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

（1）隨意選擇兩個(gè)大的素?cái)?shù)P、Q，P不等于Q。

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

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

（2）將P、Q兩個(gè)素?cái)?shù)相乘得到一個(gè)N，即N=PQ

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

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

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

//判斷兩個(gè)數(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 ，計(jì)算出D的值，作為另一個(gè)密鑰。

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

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

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

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

2.用公鑰加密信息

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

明文：M

加密：

密文：C

其中加密的算法，先進(jìn)行密文的取余運(yùn)算在加密，代碼如下：

//計(jì)算密文
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;
    }
}

在進(jìn)行加密運(yùn)算

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

3.用私鑰解密信息

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

密文：C

解密：

明文：M

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

ll key()
{
    ll p, q, t, n, e, d;
    cout << "請(qǐng)輸入兩個(gè)素?cái)?shù) p,q: " << endl;    //輸入兩個(gè)素?cái)?shù)q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素?cái)?shù)" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的歐拉函數(shù)
    t = (p - 1) * (q - 1);
 
    cout << "請(qǐng)輸入密鑰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;
}

在進(jìn)行解密：

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

三、AC代碼

新建一個(gè)頭文件RSA.h

#pragma once
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
// 判斷素?cái)?shù)
ll primeNum(ll num);
// 判斷互質(zhì)
ll coprime(ll a, ll b);
// 計(jì)算密文
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("*****        請(qǐng)選擇所需功能          *****\n");
    printf("*****          1.生成鑰匙            *****\n");
    printf("*****          2.加密                *****\n");
    printf("*****          3.解密                *****\n");
    printf("*****          4.退出                *****\n");
    printf("------------------------------------------\n");
}
ll primeNum(ll num)   //判斷素?cái)?shù)
{
    if (num == 1 || num == 0)
    {
        return 0;
    }
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            // 不是素?cái)?shù)返回0
            return 0;
        }
    }
    return 1; //是素?cái)?shù)返回1
}
//判斷兩個(gè)數(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;
}
//計(jì)算密文
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 << "請(qǐng)輸入兩個(gè)素?cái)?shù) p,q: " << endl;    //輸入兩個(gè)素?cái)?shù)q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素?cái)?shù)" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的歐拉函數(shù)
    t = (p - 1) * (q - 1);
 
    cout << "請(qǐng)輸入密鑰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 << "請(qǐng)輸入公鑰(e，n)" << endl;
    cin >> e >> n;
    cout << "請(qǐng)輸入明文: (明文需小于" << n << ")" << endl;  //計(jì)算密文
    cin >> x;
 
    y = candp(x, e, n);
    cout << "密文為:" << y << endl;
    return 0;
}
//解密
ll decode()
{
    ll n, d, x, y;
    cout << "請(qǐng)輸入私鑰(d，n)" << endl;
    cin >> d >> n;
    cout << "請(qǐng)輸入密文: ";  //計(jì)算密文
    cin >> y;
 
    x = candp(y, d, n);
    cout << "明文為:" << x << endl;
    return 0;
}

在寫出主函數(shù)test.c,對(duì)上面的函數(shù)進(jìn)行調(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 << "輸入錯(cuò)誤,請(qǐng)重新輸入" << endl;
        }
    }
}
void menu1()
{
    printf("******************************************\n");
    printf("******************************************\n");
    printf("*****     歡迎來(lái)到RSA加密測(cè)試系統(tǒng)   ******\n");
    printf("******************************************\n");
    printf("******************************************\n");
}
int main()
{
    menu1();
    RSA();
    return 0;
}