ITKeyword,专注技术干货聚合推荐

注册 | 登录

非对称加密算法RSA学习

u014634338 分享于 2015-05-08

推荐:Java非对称加密算法--RSA

非对称加密的特点是有两把钥匙,公钥和私钥。公钥加密只能私钥解密;私钥加密只能公钥解密。 在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而解

2018阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/act/ambassador/sharetouser.html?userCode=gh9qh5ki&utm_source=gh9qh5ki

RSA加密算法是最常用的非对称加密算法,RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。 

RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:


RSA算法并不难,只需要一点数论知识就可以理解。

一、互质关系

这个很简单,这里不解释了。

二、欧拉函数

请思考以下问题:

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

φ(n) 的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。

第一种情况

如果n=1,则 φ(1) = 1 。因为1与任何数(包括自身)都构成互质关系。

第二种情况

如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于等于1的整数),则

RSA算法原理

比如 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4。

这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有p^(k-1)个,即1×p、2×p、3×p、…、p^(k-1)×p,把它们去除,剩下的就是与n互质的数。

上面的式子还可以写成下面的形式:

RSA算法原理

可以看出,上面的第二种情况是 k=1 时的特例。

第四种情况

如果n可以分解成两个互质的整数之积,

  n = p1 × p2

  φ(n) = φ(p1p2) = φ(p1)φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

这一条的证明要用到“中国剩余定理”,这里就不展开了,只简单说一下思路:如果a与p1互质(a<p1),b与p2互质(b<p2),c与p1p2互质(c<p1p2),则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能,b的值有φ(p2)种可能,则数对 (a,b) 有φ(p1)φ(p2)种可能,而c的值有φ(p1p2)种可能,所以φ(p1p2)就等于φ(p1)φ(p2)。

第五种情况

因为任意一个大于1的正整数,都可以写成一系列质数的积。

RSA算法原理

根据第4条的结论,得到

RSA算法原理

推荐:Java 加密解密 对称加密算法 非对称加密算法 MD5 BASE64 AES RSA

【前言】 本文简单的介绍了加密技术相关概念,最后总结了java中现有的加密技术以及使用方法和例子 【最简单的加密】 1.简单的概念 明文:加密前的信息 密文:机

再根据第3条的结论,得到

RSA算法原理

也就等于

RSA算法原理

这就是欧拉函数的通用计算公式。比如,1323的欧拉函数,计算过程如下:

RSA算法原理

三、欧拉定理

欧拉函数的用处,在于欧拉定理。”欧拉定理”指的是:

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

RSA算法原理

也就是说,a的φ(n)次方被n除的余数为1。或者说,a的φ(n)次方减去1,可以被n整除。比如,3和7互质,而7的欧拉函数φ(7)等于6,所以3的6次方(729)减去1,可以被7整除(728/7=104)。

欧拉定理的证明比较复杂,这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如,7和10互质,根据欧拉定理,

RSA算法原理

已知 φ(10) 等于4,所以马上得到7的4倍数次方的个位数肯定是1。

RSA算法原理

因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来。

欧拉定理有一个特殊情况。

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成

RSA算法原理

这就是著名的费马定理。它是欧拉定理的特例。

欧拉定理是RSA算法的核心。理解了这个定理,就可以理解RSA。

四、逆元

还剩下最后一个概念:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

RSA算法原理

这时,b就叫做a的逆元。

比如,3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…},即如果b是a的模反元素,则 b+kn 都是a的模反元素。

欧拉定理可以用来证明逆元必然存在。

RSA算法原理

可以看到,a的 φ(n)-1 次方,就是a的逆元。

求逆元可以用扩展欧几里得

==========================================

上面原理介绍转自:这里

RSA算法的加密和解密过程:
    在RSA算法中,每个实体有自己的公钥(e,n)及私钥(d,n),其中n = p*q,p,q是两个大素数,e*d = 1 mod ф(n),显然e应该满足gcd(e,ф(n))=1。实体B加密消息m,将密文在公开信道上传送给实体A。实体A接到密文后对其解密。具体算法如下。
1.公钥的生成算法
    RSA的公钥生成算法十分简单,可以分为四步:
    (1)选择两个素数,p和q;
    (2)计算n = p×q和N = (p-1)×(q-1);
    (3)选择一个与N互质的数d;
    (4)找出一个e,使得e×d = 1 mod N。
    公开密钥是由(e,n)构成,私有密钥由(d,n)构成。
2.加密算法
    实体B的操作如下:
    (1)得到实体A的真实公钥(e,n);
    (2)把消息表示成整数m,0<m≤n-1;
    (3)使用平方-乘积算法,计算C = Ek(m) = m^e mod n;
    (4)将密文C发送给实体A。
3.解密算法
    实体A接收到密文C,使用自己的私钥d计算m = Dk(C) = C^d mod n,m∈Zn。

下面是自己用C++写的代码:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cmath>
using namespace std;
typedef long long  LL;
const int MAXSIZE=1024;
class RSA
{
public:
    LL p;
    LL q;
    LL e;
    LL N;
    
private:
    LL d;
    LL n;
public:
    bool MakePrivateKey()  //产生私钥
    {
        this->d=cal(e, N);
        return true;
    }
    
    bool GetPrivateKey(LL &d,LL &n)//获得私钥对
    {
        d=this->d;
        n=this->n;
        return true;
    }
    bool GetPublicKey(LL &e,LL &n) //获得公钥对
    {
        e=this->e;
        n=this->n;
        return true;
    }

    LL gcd(LL a,LL b) //欧几里得
    {
        if (b==0)
        {
            return a;
        }
        return gcd(b, a%b);
    }
    LL exgcd(LL a,LL b,LL &x,LL &y)   //扩展欧几里得
    {
        if (b==0)
        {
            x=1;
            y=0;
            return a;
        }
        LL r=exgcd(b, a%b, x, y);
        LL t=y;
        y=x-(a/b)*y;
        x=t;
        return r;
    }
    LL cal(LL a,LL n)  //求乘法逆元
    {
        LL x,y;
        LL gcd=exgcd(a, n, x, y);
        if (1%gcd!=0)
        {
            return -1;
        }
        x*=1/gcd;
        if (n<0)
        {
            n=-n;
        }
        LL ans=x%n;
        if (ans<=0)
        {
            ans+=n;
        }
        return ans;
    }
    bool Check_Set_e(LL e)  //检查e是否合法,如果合法并设置e
    {
        if (gcd(N, e)!=1 || e<=1 || e>=N)
        {
            return false;
        }
        this->e=e;
        return true;
    }
    LL QuickMode(LL a,LL b,LL mod)  //快速幂模M 算法
    {
        
        LL ans=1;
        LL base=a;
        while (b!=0)
        {
            if (b&1)
            {
                ans=ans*base%mod;
            }
            base=base*base%mod;
            b>>=1;
        }
        return ans;
    }
    LL isprime(LL a)    //素数判断
    {
        for (LL i=2; i<=sqrt(a); i++)
        {
            if (a%i==0)
            {
                return 0;
            }
        }
        return 1;
    }
    bool rsa_encrypt(char *mw,LL *cm)  //加密
    {
        LL len=strlen(mw);
        for (LL i=0; i<len; i++)
        {
            cm[i]=QuickMode(mw[i], e, n);
        }
        return true;
    }
    
    bool rsa_encrypt(LL *mw,LL len,LL *cm)  //加密2
    {
        for (LL i=0; i<len; i++)
        {
            cm[i]=QuickMode(mw[i], e, n);
        }
        return true;
    }
    
    
    void showcm(LL *cm,LL len)   //显示密文
    {
        for (LL i=0; i<len; i++)
        {
            printf("%lld",cm[i]);
        }
        printf("\n");
    }
    
    void showmw(char *mw)    //显示明文
    {
        printf("%s\n",mw);
    }
    
    void showcm_int(char *cm)    //显示密文
    {
        LL len=strlen(cm);
        for (LL i=0; i<len; i++)
        {
            printf("%d",cm[i]);
        }
    }
    
    void showmw_int(char *mw)    //显示明文
    {
        
        LL len=strlen(mw);
        for (LL i=0; i<len; i++)
        {
            printf("%d",mw[i]);
        }
    }
    void show_int(LL *mw_or_cm,LL len)
    {
        for (LL i=0; i<len; i++)
        {
            printf("%lld",mw_or_cm[i]);
        }
    }
    
    bool rsa_decrypt(char *mw,LL *cm,LL len)  //解密
    {
        for (LL i=0; i<len; i++)
        {
            mw[i]=QuickMode(cm[i], d, n);
        }
        return  true;
    }
    
    bool rsa_decrypt(char *mw,char *cm,LL len)  //解密2
    {
        for (LL i=0; i<len; i++)
        {
            mw[i]=QuickMode(cm[i], d, n);
        }
        return  true;
    }
    
    bool rsa_decrypt(LL *mw,LL *cm,LL len)  //解密3
    {
        for (LL i=0; i<len; i++)
        {
            mw[i]=QuickMode(cm[i], d, n);
        }
        return  true;
    }
    
    
    bool Set_P_Q(LL p,LL q) //检查p,q是否合法并设置p,q,N,n
    {
        if (!isprime(p) && !isprime(q))
        {
            return false;
        }
        
        this->p=p;
        this->q=q;
        this->N=(p-1)*(q-1);
        this->n=p*q;
        return true;
    }
    LL GetN()  //获得N
    {
        return this->N;
    }
};

int main()
{
    LL p,q,e,len;
    RSA rsa;
    char mw[MAXSIZE];  //明文
    LL cm[MAXSIZE];   //密文
    printf("请输入素数p,q:");
    while (1)
    {
        scanf("%lld%lld",&p,&q);
        if (!rsa.Set_P_Q(p,q))
        {
            printf("p或q不是素数,请重新输入:");
        }
        else
        {
            
            break;
        }
    }
    printf("选择整数e(e为素数,且 1<e<%lld):",rsa.GetN());
    while (1)
    {
        scanf("%lld",&e);
        
        if (!rsa.Check_Set_e(e))
        {
            printf("输入的e有误,请重新输入:");
        }
        else
        {
            break;
        }
    }
    rsa.MakePrivateKey();
    printf("请选择是加密还是解密(加密请输入0,其余输入表示解密):");
    int x;
    scanf("%d",&x);
    if (x==0)
    {
        printf("请选择输入明文类型(整型or字符串)整型输入0,其余输入表示字符串:");
        scanf("%d",&x);
        if(x==0)
        {
            LL mw[MAXSIZE];
            printf("请输入明文长度:");
            scanf("%lld",&len);
            printf("请输入明文:");
            for (LL i=0; i<len; i++)
            {
                scanf("%lld",&mw[i]);
            }
            rsa.rsa_encrypt(mw,len,cm);
            printf("明文后密文为:");
            rsa.showcm(cm, len);
           // rsa.show_int(cm, len);
            
        }
        else
        {
            printf("请输入明文(字符串):");
            scanf("%s",mw);
            rsa.rsa_encrypt(mw,cm);
            printf("加密后的密文为:");
            rsa.showcm(cm, strlen(mw));
        }
        
        
    }
    else
    {
        printf("请选择输入密文类型(整型or字符串)整型输入0,其余输入表示字符串:");
        scanf("%d",&x);
        if(x==0)
        {
            printf("请输入密文的长度(密文为整数):");
            LL len;
            scanf("%lld",&len);
            printf("请输入密文(密文为整数):");
            for (LL i=0; i<len; i++)
            {
                scanf("%lld",&cm[i]);
            }
            LL mw2[MAXSIZE];
            rsa.rsa_decrypt(mw2,cm,len);
            printf("解密后的明文为:");
            rsa.show_int(mw2,len);
        }
        else
        {
            char cm2[MAXSIZE];
            printf("请输入密文的长度(密文字符串):");
            gets(cm2);
            rsa.rsa_decrypt(mw,cm2,strlen(cm2));
            mw[len]='\0';
            printf("解密后的明文为:");
            rsa.showmw(mw);
        }
        
    }
    return 0;
}

看起来挺长的,其实实质性的就只有一点点,很多其余的函数是为了完善部分功能,程序中的密文,明文输出有几种,以及加密函数也有几种,其实本质都是一样,只是呈现的方式不一样,为了更好的测试数据,所有这里把密文,明文分成了字符型还是整数型,其实本质是一样的。 测试情况:整型加密,解密的结果和书本上的数据是一致的,字符串加密不软件数据测试一样,但是这些测试数据都不是很多,稍后将进行大量测试,并给出图示。 注:该实现代码只是记录本人的学习过程,只简单的进行了处理实现,本不是完全实现RSA并用于工程中。





推荐:RSA非对称加密算法,加密和签名

RAS算法: 1、用RSA算法生成一对密钥,公钥发放给外部客户,私钥自己保管;有以下应用场景:      【公钥加密、私钥解密】或者【私钥签名、公钥验证】 2、非对称

RSA加密算法是最常用的非对称加密算法,RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数
在线网页数据采集器

相关阅读排行


用户评论

游客

在线网页数据采集器

相关内容推荐

vivo京东自营官方旗舰店

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。