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

第C++實(shí)現(xiàn)RSA加密解密算法是示例代碼目錄一、什么是RSA算法1.對(duì)稱加密2.非對(duì)稱加密3.非對(duì)稱加密的應(yīng)用二、RSA算法的基礎(chǔ)操作步驟1.生成公鑰和私鑰2.用公鑰加密信息3.用私鑰解密信息三、AC代碼四、RSA算法的測(cè)試

一、什么是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è)稱為公開(kāi)密鑰，另一個(gè)稱為私有密鑰。對(duì)于公鑰，可以通過(guò)非保密方式向他人公開(kāi)，而私鑰則由解密方保密，不對(duì)別人公開(kāi)。

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ù)，代碼如下：

llprimeNum(llnum)//判斷素?cái)?shù)

if(num==1||num==0)

return0;

for(inti=2;i*i=num;i++)

if(num%i==0)

//不是素?cái)?shù)返回0

return0;

return1;//是素?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ù)是否互素

llcoprime(lla,llb)//判斷互質(zhì)

llt;

if(ab)

t=a;

a=b;

b=t;

while(a%b)

t=b;

b=a%b;

a=t;

//返回值為1，則a，b互素

returnb;

}

（5）根據(jù)公式DEmodT=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ì)算密文

llcandp(llb,llp,llk)//b--明文或密文p--指數(shù)(e/d)k--模數(shù)

if(p==1)

returnb%k;

if(p==2)

returnb*b%k;

if(p%2==0)

llsum=candp(b,p/2,k);

returnsum*sum%k;

if(p%2==1)

llsun=candp(b,p/2,k);

returnsun*sun*b%k;

}

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

llencryption()

lln,e,x,y;

cout"請(qǐng)輸入公鑰(e，n)"endl;

cinen;

cout"請(qǐng)輸入明文:(明文需小于"n")"endl;//計(jì)算密文

cinx;

y=candp(x,e,n);

cout"密文為:"yendl;

return0;

3.用私鑰解密信息

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

密文：C

解密：

明文：M

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

llkey()

llp,q,t,n,e,d;

cout"請(qǐng)輸入兩個(gè)素?cái)?shù)p,q:"endl;//輸入兩個(gè)素?cái)?shù)q,p

cinpq;

if(primeNum(p)==0||primeNum(q)==0)

cout"輸入的p或q不是素?cái)?shù)"endl;

return0;

n=p*q;

//t為n的歐拉函數(shù)

t=(p-1)*(q-1);

cout"請(qǐng)輸入密鑰e:"endl;

cine;

d=1;

//求e的乘法逆

while(((e*d)%t)!=1)

d++;

cout"n=p*q="nendl;

cout"t=(p-1)*(q-1)="tendl;

cout("公鑰(e,n)為:(")e","n")"endl;

cout("私鑰(d,n)為:(")d","n")"endl;

return0;

}

在進(jìn)行解密：

lldecode()

lln,d,x,y;

cout"請(qǐng)輸入私鑰(d，n)"endl;

cindn;

cout"請(qǐng)輸入密文:";//計(jì)算密文

ciny;

x=candp(y,d,n);

cout"明文為:"xendl;

return0;

三、AC代碼

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

#pragmaonce

#includestdio.h

#includeiostream

#includestdlib.h

#includealgorithm

#includecmath

usingnamespacestd;

typedeflonglongll;

//判斷素?cái)?shù)

llprimeNum(llnum);

//判斷互質(zhì)

llcoprime(lla,llb);

//計(jì)算密文

llcandp(llb,llp,llk);

//生成密鑰

llkey();

llencryption();

lldecode();

//菜單

voidmenu();

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

#define_CRT_SECURE_NO_WARNINGS1

#include"RSA.h"

voidmenu()

printf("------------------------------------------\n");

printf("*****請(qǐng)選擇所需功能*****\n");

printf("*****1.生成鑰匙*****\n");

printf("*****2.加密*****\n");

printf("*****3.解密*****\n");

printf("*****4.退出*****\n");

printf("------------------------------------------\n");

llprimeNum(llnum)//判斷素?cái)?shù)

if(num==1||num==0)

return0;

for(inti=2;i*i=num;i++)

if(num%i==0)

//不是素?cái)?shù)返回0

return0;

return1;//是素?cái)?shù)返回1

//判斷兩個(gè)數(shù)是否互素

llcoprime(lla,llb)//判斷互質(zhì)

llt;

if(ab)

t=a;

a=b;

b=t;

while(a%b)

t=b;

b=a%b;

a=t;

//返回值為1，則a，b互素

returnb;

//計(jì)算密文

llcandp(llb,llp,llk)//b--明文或密文p--指數(shù)(e/d)k--模數(shù)

if(p==1)

returnb%k;

if(p==2)

returnb*b%k;

if(p%2==0)

llsum=candp(b,p/2,k);

returnsum*sum%k;

if(p%2==1)

llsun=candp(b,p/2,k);

returnsun*sun*b%k;

//生成密鑰

llkey()

llp,q,t,n,e,d;

cout"請(qǐng)輸入兩個(gè)素?cái)?shù)p,q:"endl;//輸入兩個(gè)素?cái)?shù)q,p

cinpq;

if(primeNum(p)==0||primeNum(q)==0)

cout"輸入的p或q不是素?cái)?shù)"endl;

return0;

n=p*q;

//t為n的歐拉函數(shù)

t=(p-1)*(q-1);

cout"請(qǐng)輸入密鑰e:"endl;

cine;

d=1;

//求e的乘法逆

while(((e*d)%t)!=1)

d++;

cout"n=p*q="nendl;

cout"t=(p-1)*(q-1)="tendl;

cout("公鑰(e,n)為:(")e","n")"endl;

cout("私鑰(d,n)為:(")d","n")"endl;

return0;

llencryption()

lln,e,x,y;

cout"請(qǐng)輸入公鑰(e，n)"endl;

cinen;

cout"請(qǐng)輸入明文:(明文需小于"n")"endl;//計(jì)算密文

cinx;

y=candp(x,e,n);

cout"密文為:"yendl;

return0;

lldecode()

lln,d,x,y;

cout"請(qǐng)輸入私鑰(d，n)"endl;

cindn;

cout"請(qǐng)輸入密文:";//計(jì)算密文

ciny;

x=candp(y,d,n);

cout"明文為:"xendl;

return0;

}

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

#include"RSA.h"

voidRSA()

while(1)

menu();

lli=0;

cini;

switch(i)

case1:

key();

break;

case2:

encryption();

break;

case3:

decode();

break;

case4:

exit(0);

default:

cout"輸入錯(cuò)誤,請(qǐng)重新輸入"endl;

voidmenu1()

printf("******************************************\n");

printf("******************************************\n");

printf("*