非对称加密技术

1、非对称加密技术 -RSA 算法数学原理分析 非对称加密技术，在现在网络中，有非常广泛应用。加密技术更 是数字货币的基础。所谓非对称，就是指该算法需要一对密钥， 使用其中一个(公钥) 加密，则需要用另一个(私钥)才能解密。但是对于其原理大部分同学应该都是一知半解， 今天就来分析下 经典的非对称加密算法 -RSA 算法。通过本文的分析，可以更好的理解非对称加密原理,可以让我们更好的使用非对称加密技术。RSA 算法原理RSA 算法的基于这样的数学事实： 两个大质数相乘得到的大数难 以被因式分解。女口：有很大质数p跟q,很容易算出N,使得N=p*q , 但给出N,比较难找pq(没有很好的方式，只有不停

2、的尝试) 这其实也是单向函数的概念下面来看看数学演算过程：1选取两个大质数p, q,计算N=pq 及 (N)= (p) (q)=(p-1)*(q-1)2. 三个数学概念：质数(primenumbe):又称素数，为在大于1的自然数中，除了 1 和它本身以外不再有其他因数。互质关系 ：如果两个正整数,除了 1 以外,没有其他公因子,我 们就称这两个数是互质关系( coprime)。 (N):叫做欧拉函数，是指任意给定正整数 N，在小于等于N 的正整数之中,有多少个与 N 构成互质关系,如果 n 是质数,则 ( n)=n-1 。如果n可以分解成两个互质的整数之积，(n)= (p1p2)= (p1)

3、(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。3选择一个大于1小于中(N)的数e,使得e和中(N)互质4. e其实是1和 (N)之前的一个质数5. 计算d,使得de=1mod (N)等价于方程式ed-1=k (N求一组解。6. d称为e的模反元素，e和 (N)互质就肯定存在d。7. 模反元素是指如果两个正整数 a和n互质，那么一定可以找 到整数b,使得ab被n除的余数是1,则b称为a的模反元素。可根据欧拉定理证明模反元素存在，欧拉定理是指若n,a互质，则：aA (n)三 1(mod n)及 aA (n )=a*a( (n )-1),可得 a 的 (n)-1 次方，就是a的模反元素。8.

4、(N,e)封装成公钥，(N,d)封装成私钥。假设m为明文，加密就是算出密文 c:mAmod N=c(明文m用公钥e加密并和随机数N取余得到密文c) 解密则是：cAd mod N=m(密文c用密钥解密并和随机数 N取余得到明文m)9. 私钥解密这个是可以证明的，这里不展开了。加解密步骤具体还是来看看步骤，举个例子，假设 Alice 和 Bob 又要相互通 信。1. Alice 随机取大质数 P仁53,P2=59那 N=53*59=3127, (N)=30162. 取一个e=3,计算出d=2011。3. 只将N=3127,e=3作为公钥传给Bob(公钥公开)4. 假设Bob需要加密的明文 m=89

5、,c=89A3 mod 3127=1394于是Bob传回c=1394o(公钥加密过程)5. Alice 使用 cAd mod N=1394八2011mod 3127就能得到明文 m=89(私钥解密过程)假如攻击者能截取到公钥n=3127,e=3及密文c=1394,是仍然无法 不通过 d 来进行密文解密的。安全性分析那么，有无可能在已知n和e的情况下，推导出d?1. ed=l(mod (n)。只有知道e和 (n),才能算出d。2. (n)=(p-1)(q-1)。只有知道p和q,才能算出 (n)。3. n二pq。只有将n因数分解，才能算出p和q。如果n可以被因数分解，d就可以算出，因此RSA安全性建立在 N 的因式分解上。大整数的因数分解，是一件非常困难的事情。只要密钥长度足够长，用 RSA加密的信息实际上是不能被解破 的。补充模运算规则1. 模运算加减法：(a+b)mod p=(a mod p+b mod p) mod p(a-b)mod p=(a mod p-b mod