美文网首页
加解密算法-RSA

加解密算法-RSA

作者: 倦飞知还 | 来源:发表于2018-08-09 11:49 被阅读0次

    概述

    RSA是"非对称加密算法",非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey)。公钥与私钥是配对的,用公钥加密的数据只有配对的私钥才能解密,反之亦然。因加解密使用两个不同的密钥,所以这种算法叫作非对称加密算法。

    非对称算法的在应用的过程如下,假设发送方向接收方发送消息(明文):

    1.接收方生成公钥和私钥,公钥公开,私钥保留;

    2.发送方将要发送的消息采用公钥加密,得到密文,然后将密文发送给接收方;

    3.接收方收到密文后,用自己的私钥进行解密,获得明文。

    数学基础

    主要包括素数、互质数、欧拉函数、模运算

    2.1互质

    公因数只有1的两个数,叫做互质数;又称互素,若N个整数的最大公因子是1,则称这N个整数互质。

    2.2 欧拉函数

    当n=p1*p2,且p1、p2互质时,有

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

    即积的欧如果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)。拉函数等于各个因子的欧拉函数的积。

    e.对于任意一个大于1的正整数,都可以写成

    n=p1k1p2k2…prkr,其中,p1,p2,…,pk为质数。

    由d可知

    φ(n)= φ(p1k1)φ(p2k2)…φ(prkr),

    再由c可知

    φ(n)= p1k1p2k2…prkr(1-1/p1)(1-1/p2)…(1-1/pr)

    φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pr)

    这就是欧拉函数的通用计算公式。

    2.3 欧拉定理

    欧拉定理:

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

    aφ(n)≡1(mod n)

    上式表示,a的φ(n)次方被n除的余数为1,或者叙述为,a的φ(n)次方减去1后可以被n整除。注意,φ(n)是n的欧拉函数。

    欧拉定理的特殊情况:如果正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成就是我们所说的费马小定理

    ap-1≡1(mod p)

    2.4模反元素

    模反元素:

    如果两个正整数a和n互质,那么一定可以找到整数b,使得ab-1被n整除,或者说ab被n除的余数是1。这时b被称为a的模反元素。公式如下:

    ab≡1(mod n)

    注意,模反元素并不唯一,如果b是a的模反元素,则b+kn都是a的模反元素。

    欧拉定理可以用来证明模反元素的必然存在:

    aφ(n)= a×aφ(n)-1≡1(mod n)

    密钥的生成与加解密

    密钥生成

    密钥生成的步骤如下:

    1.随机选择两个不相等的质数p和q;

    2.计算p和q的乘积n(将n转换为二进制后,二进制的长度就是密钥的长度,实际应用中一般选择1024位、2048位);

    3.计算n的欧拉函数φ(n);

    4.随机选择一个整数e,其中φ(n)>e>1,且e与φ(n)互质(实际应用中e一般选为65537);

    5.计算e对于φ(n)的模反元素d;

    6.将n和e封装成公钥,n和d封装成私钥。

    举例:

    1.随机选择两个不相等的质数47和59;

    2.二者的乘积为47×59=2773,2773转化为二进制为1010,1101,0101,长度为12位,所以密钥的长度为12位;

    3.根据欧拉函数公式φ(n)=n(1-1/p)(1-1/q)计算,φ(2773)= 2773×(1-1/47)(1-1/59)=(47-1)(59-1)=2668;

    4.随机选择一个整数e=63,2668>63>1,并且63与2668互质;

    5.计算63对于2668的模反元素d,根据公式ed≡1(mod φ(n)),有63d-1=2668k,由欧几里得扩展公式计算得d=847。

    6.公钥(n,e)=(2773,63),私钥(n,d)=(2773,847)。

    加解密

    加密

    假设发送方向接收方发送信息m,m未加密,我们称之为明文。发送方从接收方获得的公钥为(n,e),加密公式为

    me=c(mod n)

    其中,m必须是整数,而且m必须比n小。

    m,e,n已知,从上面的公式中计算出c,c就是加密后的信息,我们称之为密文。发送方将密文发送给接收方。

    解密

    接收方从发送方接收到密文c,用自己的配对私钥(n,d)进行解密,解密公式为

    cd=m(mod n)

    已知c,n,d,从上面公式中计算出m,就是发送方发过来的明文。

    举例:

    1.加密

    根据上面计算出的公钥(n,e)=(2773,63),假如m=244,根据公式me=c(mod n),可计算出密文c=465。

    2.解密

    根据上面计算出的私钥(n,d)=(2773,847),已知c=465,根据公式cd=m(mod n),可计算出明文m=244。

    相关文章

      网友评论

          本文标题:加解密算法-RSA

          本文链接:https://www.haomeiwen.com/subject/gegxbftx.html