C++實現RSA加密解密演演算法是範例程式碼

2022-09-24 14:01:42

一、什麼是RSA演演算法

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

1.對稱加密

在對稱加密技術中，對資訊的加密和解密都使用了相同的金鑰Key，也就是說使用同一個金鑰Key對資料進行加密和解密。這種加密方法可簡化加解密的處理過程，資訊交換雙方都不必彼此研究和交換專用的加解米演演算法。如果在交換階段，金鑰Key沒有洩露，那麼加密資料的機密性和報文的完整性就可以得到保證。

2.非對稱加密

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

3.非對稱加密的應用

由於非對稱加密方式可以使通訊雙方無需事先交換金鑰就可以建立安全通訊，因此被廣泛應用於身份認證、數位簽章、等資訊交換領域。其中最具有代表性的非對稱加密方式就是RSA公鑰密碼體制。

二、RSA演演算法的基礎操作步驟

1.生成公鑰和私鑰

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

（1）隨意選擇兩個大的素數P、Q，P不等於Q。

此處在演演算法實現中需要快速的判斷P、Q是否為素數，程式碼如下：

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

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

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

（4）選擇一個整數E，作為一個金鑰，使E與T互質（即E與T的最大公約數為1），且E必須小於T

此處在演演算法實現中需要對E與T進行互質的判斷（最大公約數為1）

//判斷兩個數是否互素
ll coprime(ll a, ll b)  //判斷互質
{
    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）根據公式DE mod T = 1 ，計算出D的值，作為另一個金鑰。

此時根據演演算法，逆向求D

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

（6）通過以上的步驟就可以求出N，E，D這三個資料，其中（N，E）作為公鑰，（N，D）作為私鑰。

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

2.用公鑰加密資訊

傳送資訊的一方收到公鑰PK後，就可以通過公鑰PK對資料進行加密，加密的操作步驟如下圖所示，其中明文為：M，密文為：C

明文：M

加密：

密文：C

其中加密的演演算法，先進行密文的取餘運算在加密，程式碼如下：

//計算密文
ll candp(ll b, ll p, ll k) //b--明文或密文   p--指數(e/d)    k--模數
{
    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

其中解密演演算法，先產生金鑰Key演演算法：

ll key()
{
    ll p, q, t, n, e, d;
    cout << "請輸入兩個素數 p,q: " << endl;    //輸入兩個素數q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素數" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的尤拉函數
    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;
// 判斷素數
ll primeNum(ll num);
// 判斷互質
ll coprime(ll a, ll b);
// 計算密文
ll candp(ll b, ll p, ll k);
// 生成金鑰
ll key();
//加密
ll encryption();
//解密
ll decode();
// 選單
void menu();

將函數寫在RSA.cpp中，用於主函數RSA（）的呼叫程式碼如下：

#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)   //判斷素數
{
    if (num == 1 || num == 0)
    {
        return 0;
    }
    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            // 不是素數返回0
            return 0;
        }
    }
    return 1; //是素數返回1
}
//判斷兩個數是否互素
ll coprime(ll a, ll b)  //判斷互質
{
    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--指數(e/d)    k--模數
{
    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 << "請輸入兩個素數 p,q: " << endl;    //輸入兩個素數q,p
    cin >> p >> q;
    if (primeNum(p)==0||primeNum(q)==0)
    {
        cout << "輸入的p或q不是素數" << endl;
        return 0;
    }
    n = p * q;
 
    //t為n的尤拉函數
    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;
}

在寫出主函數test.c,對上面的函數進行呼叫即可：

#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加密測試系統   ******n");
    printf("******************************************n");
    printf("******************************************n");
}
int main()
{
    menu1();
    RSA();
    return 0;
}