RSA 加密算法在C++中的实现 面向初学者(附代码)

这篇具有很好参考价值的文章主要介绍了RSA 加密算法在C++中的实现 面向初学者(附代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

概述

博文的一,二部分基础知识的铺垫。分别从密码学,数论两个方面为理解RSA算法做好了准备。第三部分是对RSA加密过程的具体介绍,主要涉及其密钥对(key-pair)的获取。前三个部分与编程实践无关,可以当作独立的关于RSA加密算法的介绍。第四部分开始介绍在编程层面实现RSA算法的基础知识,主要涉及一些算法,如拓展欧几里得算法米勒-拉宾素性检验算法,是为C++中实现RSA加密所作的铺垫。第五部分阐述了面向初学者实现RSA算法的思路,以及其局限,可改善之处。第六部分为提供的参考代码。

一. RSA算法的密码学基础

  密钥:明文转换为密文,对于窃听者来说,密钥和明文等价

  对称加密(symmetric cryptograph),特征在于加密和解密使用同一个密钥。

  非对称加密(asymmetric cryptography),也被称作公钥加密(public-key cryptography)。最主要的特征在于使用公钥加密,私钥解密

  下面我们通过一个例子,来简述非对称加密的过程,假设A,B两人进行公钥加密通信,则整个通信的过程,由信息接受者B启动(A为信息发出者)。

  B首先通过一定算法生成包含公钥,私钥的密钥对(key-pair),然后将公钥发送给A自己保留私钥,请求A利用这个公钥对信息进行加密。

  A利用该公钥对信息进行加密后,将密文传送给B,B利用自己的私钥对密文进行解密。

  值得注意的是:首先公钥是可公开的,因为光凭借公钥只能加密,而并不能解密,所以不用担心公钥传输过程中被窃听者截获,同理也不用担心密文被截获,因为唯一能够破解密文的密钥在信息接收者处。

  RSA算法(Rivest-Shamir-Adleman 取自开发者首字母),正是一种公钥密码算法

二. RSA算法的数论基础

(看之前需要理解同余符号的含义)

1.欧拉函数

对于正整数n,不大于n,且与n互素的数的个数记为

2.欧拉定理

 (其弱化形式,即在n为素数时,变为费马小定理

证明需要用到群论知识,与RSA算法关联不大,故在此不加赘述,可参考:

 欧拉定理 证明及推论_有钱哥哥家的的博客-CSDN博客_欧拉定理证明

3.同余的一些基本性质:

/1:乘积同余:即两数乘积,与两数模n的余数的乘积,关于模n同余,证明可以通过将两数写作kn+q(q为余数)的形式,比较其乘积与q1,q2乘积在模n时的结果。

/2:幂运算同余:若,则,证明可以通过移项,由因式定理可知,其必有a-b这个因式

4.逆元

若,则称a为b,关于模n的逆元

三.RSA算法介绍

我们用A来代表明文,B代表经过RSA算法加密后的密文。则可以用一个等式来阐明A,B间的关系:,且,即B为A的e次方后除以n的余数。其中(e,n)为公钥。

(d,n)为私钥,则私钥满足的关系为

下面我们来看如何得到公钥和私钥组成的密钥对(需要用到二.介绍的数学知识)。

1.得到公钥:

选取两个充分大的素数p,q, 其乘积的值即为n,在得到n后,计算其欧拉函数的值,即在1到n-1中有多少数与n互素。

因为n包含两个质因子p,q,所以在1到n-1中包含p,q因子的数均与n不互素。

包含p因子的有p,2p,3p一直到p(q-1),同理含q的有q到q(p-1)。一共p+q-2个数

则在这n-1个数中与n互素的数一共有n-1-(p+q-2)=n-p-q+1,且n可以写作p*q,可以得到:

我们选取与互素的小于的数e,则(e,n)组成公钥。

2.得到私钥:

取e关于的逆元为d,则得到(d,n)私钥。

下面来证明为何(d,n)为私钥

即证明:

两侧同时取e次幂可以得到

因为d为e的逆元,所以c++ rsa,c++,算法,密码学,网络安全,将该等式带入到上式中,我们可以得到:

欧拉定理可知,由同余的性质中的幂运算同余知,两侧同时取k次幂,可以得到:

,再由同余基本性质中的乘积同余,可知,此即为公钥的条件,于是我们发现在d取e 关于的逆元时,两者等价,即私钥条件成立。

上述生成的公钥与密钥组成的密钥对便可用于加密。

RSA算法核心在于,对于一个大数的质因数分解是很困难的,一旦能够发现对于大数质因数的高效算法,RSA就能够被破译。

四.RSA在C++实现的算法基础

在利用c++实现RSA加密时,含需要一些补充的算法知识:

1.裴蜀定理(Bezout’s lemma):

一定存在整数x,y,使得线性方程组ax+by=gcd(a,b)成立。而ax+by=gcd(a,b)则称为裴蜀等式。

2.拓展欧几里得算法(extended Euclidean algorithm):

欧几里得算法(辗转相除法)常用于求算最大公约数(gcd),而拓展欧几里得算法则是在具备欧几里得算法的功能前提下,增加了求解裴蜀等式的功能。而在我们通过公钥(e,n)计算私钥(d,n)时,就需要用到拓展欧几里得算法。

因为,可以写作c++ rsa,c++,算法,密码学,网络安全

又因为,故上式可化为c++ rsa,c++,算法,密码学,网络安全,符合裴蜀等式。

d与-k分别为欲求的x,y,故可以使用拓展欧几里得算法来求解

 关于拓展欧几里得算法的细节可以参考:扩展欧几里得算法详解__Warning_的博客-CSDN博客_扩展欧几里得

3.米勒-拉宾素性检验(Miller-Rabin prime test)

RSA加密的关键在于其最初生成的两个充分大的素数p,q,其大小决定了密码破译的难度。但是要随机生成两个大素数是比较困难的,所以RSA算法中大多都采用通过米勒-拉宾素性检验的伪素数来作为p,q。

米勒-拉宾素性检验是基于费马小定理,对给定的任意奇数进行检验,检验通过则代表其有概率为素数,在进行多次检验后,若都通过,则其为素数的概率会非常高,可以作为素数使用。

五.RSA算法在C++中的实现

基本思路:

1.随机素数p,q的获取:利用数组,生成一定范围内一定质数的数表,产生随机数i,j对应素数数组的下标,由此达到在数表中随机选取素数的功能。

2.密钥的获取:利用拓展欧几里得算法获取d的值。

3.加密过程:将输入字符的ASCII码值进行RSA加密,密文为一串数字,实现方法是用字符数组与整型数组间的值传递。

局限与改善:

1.没有使用米勒-拉宾素性检验来获取大素数,而是用素数数表产生的素数对,其构成的密钥空间小,一旦数表范围被获取,则密钥极有可能被破解。

2.加密文本的读入没有涉及文件的读写层面,需要依靠人为输入,较为不方便。

3.部分计算没有考虑在选取充分大的素数时可能产生的数据溢出问题。

六.C++代码

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

int exgcd(int a, int b,int *x,int *y)                                     //拓展欧几里得算法
{
    if(b==0)
    {
        *x=1;
        *y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int temp=*x;
    *x=*y;
    *y=temp-a/b*(*y);
    return gcd;
}

int isprime(int a)                                                          //素数判断
{
    int i;
    for(i=2;i<1+(a/2);i++){
        if(a%i==0)return 1;
    }
    return 0;
}

void primegenerator(int prime[10])                             //生成素数表
{
    int i,j=0;
    for(i=91;i<=1000;i++){
        if(isprime(i)==0){
            prime[j]=i;
            j++;
        }
      if(j>9)break;
    }
}


int main()
{
    int prime[10];
    primegenerator(prime);
    int seed,p,q;
    seed=time(0);
    srand((unsigned int)seed);                              //生成在范围内的随机素数p,q
    p=rand()%9;
    do{
        q=rand()%9;
    }while(q==p);
    int e,d,n,fi_n,r,nu,w1,w2;


    int a;
    cout<<"请选择加密/解密"<<endl;
    cout<<"输入0代表加密"<<' '<<"输入1代表解密"<<endl;
    cin>>a;
    char minwen[1000];

    int i,j,mi;
    if(a==0){
         n=prime[p]*prime[q];
         fi_n=(prime[p]-1)*(prime[q]-1);
         for(r=fi_n/2;n>=1;r--){                                                 //求得公钥
           if(exgcd(r,fi_n,&w1,&w2)==1){
             e=r;
              break;
          }
       }
       r=exgcd(e,fi_n,&d,&nu);
        cout<<"请输入明文"<<endl;
        scanf("%s",minwen);
        int shuma_minwen[strlen(minwen)];
        for(i=0;i<strlen(minwen);i++){
            shuma_minwen[i]=minwen[i];
        }
        int shuma_miwen[strlen(minwen)];                                         //录入结束,开始加密
        for(i=0;i<strlen(minwen);i++){
                mi=shuma_minwen[i];
                shuma_miwen[i]=1;
            for(j=1;j<=e;j++){
                shuma_miwen[i]=(shuma_miwen[i]*mi)%n;
            }
        }
        cout<<"密文为"<<endl;
        for(i=0;i<strlen(minwen);i++){
            cout<<shuma_miwen[i]<<' ';                                       //加密结束,输出密文,私钥
        }
        cout<<endl<<"密文长度为"<<i<<endl;
        cout<<endl<<"解密私钥为"<<endl;
        cout<<d<<' '<<n<<endl;
    }
    else if(a==1){
        int shuma_jiemiwen[10000];

         cout<<"请输入密文长度"<<endl;
        int k;
        cin>>k;
        cout<<"请输入密文"<<endl;                                                      //录入密文
        int t=0;
        for(i=0;i<k;i++){
            cin>>shuma_jiemiwen[i];
        }
        int sizel=k;

        cout<<"请输入私钥(d,n) (分别输入d,n用空格隔开)"<<endl;
        int d1,n1;
        cin>>d1>>n1;
        int ming;
        int shuma_jieminwen[sizel];                                                    //开始解密
        for(i=0;i<sizel;i++){
                ming=shuma_jiemiwen[i];
                shuma_jieminwen[i]=1;
            for(j=0;j<d1;j++){
                shuma_jieminwen[i]=shuma_jieminwen[i]*ming%n1;
            }
        }

        char jieminwen[sizel];
        for(i=0;i<sizel;i++){
            jieminwen[i]=shuma_jieminwen[i];
        }
        cout<<"明文为"<<endl;                                                        //输出明文
        for(i=0;i<sizel;i++){
            cout<<jieminwen[i];
        }
    }
    return 0;
}
 

这里提供的代码部分参考于以下链接:

C语言实现简单的RSA加解密算法_♡Starry.的博客-CSDN博客_rsa加密算法代码c语言

 但是做了一些改善

1.由随机数与素数表的对应关系,给出素数对(p,q),无需人为输入

2.计算逆元d时,采用拓展欧几里得算法,时间复杂度更低

但仍有一些点可以继续改进

1.没有使用米勒-拉宾素性检验来获取大素数,密码安全性较低

2.加密文本的读入没有涉及文件的读写层面,较为不方便。

此代码可以供初学者简单体会RSA加密的基本过程,以及主要算法,进一步优化有待探讨。文章来源地址https://www.toymoban.com/news/detail-810339.html

到了这里,关于RSA 加密算法在C++中的实现 面向初学者(附代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2022 年面向初学者的15 个计算机视觉项目创意案例

    计算机视觉是人工智能领域最热门的话题之一。 但 试图找出学习和掌握该领域的最佳方法很容易混淆。 我们的建议? 不要陷入分析理论概念的困境。 相反,将您的概念知识与实践经验相结合,开始构建您自己的计算机视觉模型!  在本文中,我们将与您分享一堆计算机视

    2024年02月05日
    浏览(91)
  • RSA加密算法Python实现

    1977年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法.RSA算法的特征如下: RSA算法是非对称加密算法,及算法的加密密钥与解密密钥不同 RAS是基于大数分解问题实现的算法, RSA算法的密钥长度一般为

    2024年01月18日
    浏览(43)
  • C# 实现对称加密算法(AES)与非对称加密算法(RSA),包含前端加密对应算法实现

    一种既简单速度又快的加密方式,加密与解密使用的都是同一个密钥,别名又叫做:单密钥加密;对称加密有很多公开算法,并且因为它效率很高,所以适用于加密大量数据的场合;但其密钥的传输过程是不安全的,并且容易被破解,密钥管理起来也相对麻烦。 需要两个密钥

    2024年02月09日
    浏览(68)
  • RSA 加密解密算法实现(简单,易懂)!!!

    目录 一、什么是RSA算法 1.对称加密 2.非对称加密 3.非对称加密的应用 二、RSA算法的基础操作步骤 1.生成公钥和私钥 2.用公钥加密信息  3.用私钥解密信息 三、AC代码 六、RSA算法的测试  七、共勉     在计算机中常用的加密算法分为两类: 对称加密算法和非对称加密算法。

    2024年01月20日
    浏览(68)
  • C语言实现简单加密算法 凯撒密码 RSA算法 简介及实现

    凯撒密码的核心思想就是移位。 将明文的每一个字符 在 密码系统所支持字符序列中向右平移N,映射得到新的字符从而实现加密,而解密则相反向左平移N。加密的Key即为N。 加密  解密 在如今的万维网环境中,如果A要向B发送数据,需要先加密这个数据,因为在一些不安全

    2024年02月08日
    浏览(53)
  • 算法初学者指南:理解排序算法

            排序是计算机科学中的基本问题之一,也是数据处理的核心步骤。从最简单的个人项目到复杂的工业级应用,排序都扮演着关键角色。本文将介绍四种常见的排序算法:冒泡排序、插入排序、快速排序和堆排序,旨在帮助算法初学者理解这些基本概念。         冒泡

    2024年01月23日
    浏览(59)
  • 初学者怎么学习c++(合集)

      学习c++方法1 找一本好的书本教材,辅助看教学视频。好的教材,可以让你更快更好的进入C/C++的世界。在校学生的话,你们的教材通常都是不错的。如果是自学,推荐使用谭浩强出的C/C++经典入门教材。看视频是学习比较直观的方式。建议先看课本,不懂的地方,更看视频

    2024年02月16日
    浏览(63)
  • 公开密钥加密之RSA算法【概念+计算+代码实现】

    🌈推荐阅读:http://t.csdn.cn/nQfIY🔥 安全算法:公开密钥加密之RSA算法 公开密钥加密(又称“非对称加密”)是加密和解密使用不同密钥的一种加密方法。包括公开密钥和私有密钥(成对生成的,网上有工具网站)。 公开密钥(public key,后面简称P):加密用的密钥 私有密钥

    2023年04月17日
    浏览(107)
  • Java代码实现RSA算法加密解密文件功能

    底层算法不做赘述,想要了解自行百度。 RSA属于非对称加密,非对称加密有公钥和私钥两个概念,私钥自己拥有,不能给别人,公钥公开。根据应用的不同,我们可以选择使用不同的密钥加密: 签名:使用私钥加密,公钥解密。用于让所有公钥所有者验证私钥所有者的身份

    2024年02月12日
    浏览(56)
  • C++ 测试框架 GoogleTest 初学者入门篇 丙

    *以下内容为本人的学习笔记,如需要转载,请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/RIztusI3uKRnoHVf0sloeg 开发者虽然主要负责工程里的开发任务,但是每个开发完毕的功能都是需要开发者自测通过的,所以经常会听到开发者提起单元测试的话题。那么今天我就

    2023年04月15日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包