当前位置:   article > 正文

非对称加密算法Rsa原理解析_非对称加密数学原理

非对称加密数学原理

目录

 

一、RSA加密算法概述

二、RSA加密算法的数学原理

三、 RSA的破解原理


一、RSA加密算法概述

RSA加密算法是非对称加密算法中的一种,在1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的,并取三人名字的首字母命名该算法。

RSA加密算法因其可靠的安全性(目前看来是十分安全的),得到了广泛的认可和使用,ISO(国际标准化组织)、ITU(国际电信联盟)及SWIFT(环球同业银行金融电讯协会)等国际标准组织均采用RSA作为加密标准,PGP等协议也采用RSA算法来传输会话密钥和数字签名;在本篇文章中,将详细讲解RSA算法中的数学原理和加密本质;

二、RSA加密算法的数学原理

(1)素数:一个大于1的数字,如果只能被1和这个数字本身整除,那么我们就称这个数字为素数,

例如7只能被1和7整除,所以7是素数,8能被1、2、4和8整除,所以8不是素数;

(2)互素:如果两个数m,n的最大公约数是1,那么称m与n互素,记作:(m,n)=1;

(3)φ(n):对于任意一个数n,φ(n)表示哪些与n互素并且小于n的数字的总数;

例如,φ(8)=4,因为只有1、3、5、7与8互素;φ(5)=4,(1,2,3,4都是);

(4)在(1)(2)(3)的基础上引出一个重要的定理,如果n是一个素数,那么φ(n)=n-1;

(5)φ(n)具有传递性:p,q是素数,那么φ(p)=p-1; φ(q)=q-1;n=p*q;此时φ(n)=φ(p)*φ(q)=(p-1)(q-1);

(6)广义欧几里得除法:,如果(m,n)=1即(m,n互素),那么一定存在整数s,t使得t*m+n*s=1(“+”号也可以写成“-”号);可以理解为t*m比n的s倍还要多1,也可以表示为t*m=1 mod n;其中mod表示求余数;

(6)欧拉定理:p是一个素数,(a,p)=1,即a和p互素,那么a^φ(p)=1 mod p;这是一个著名的定理,证明过程很复杂,我们直接忽略;

(7)RSA的定理模型:

设p,q是两个素数,n=p*q;

假设整数e满足1<e<φ(n),(e, φ(n))=1;

1、 那么e,φ(n)就满足了定理(5),所以就存在整数s、d,e*d+s* φ(n)=1;

2、 假设存在一个整数a,(a,n)=1;那么a和q,p也应该互素,即(a,p)=1;(a,q)=1;

既然(a,p)=1;那就满足了定理(6);所以a^φ(p)=1 mod p;

等式两边同时做φ(q)次幂运算,得到(a^φ(p))^φ(q)=1^φ(q) mod p,

整理得a^(φ(p)*φ(q))=1 mod p;

套用定理(5),φ(n)=φ(p)*φ(q),所以a^φ(n)=1 mod p;

等式两边同时做s次幂运算,得到a^(s*φ(n))=(1^s) mod p=1 mod p;

左右在个乘以a,得到a^(1+(s*φ(n)))=a mod p;

这是我们发现1+(s*φ(n))不就是e*d吗?(套用1、结论);所以:

a^(e*d)=a mod p;①这是一个重要的结论,同理,q,p在本质上是相同的,所以

a^(e*d)=a mod q;②

算式①和算式②可以利用中国剩余定理得出结论a^(e*d)=a mod (p*q);中国剩余定理是比较复杂的,不过我们可以狭义的理解为这样的数学题,一个整数,被5除余1,被7除余1,那么这个整数最小是多少呢?答案是36,因为这个整数一定被5*7=35除余1,所以它是36,71,106……所以最小是36;

那么a^(e*d)=a mod (p*q)就很好理解了,因为n=p*q;所以a^(e*d)=a mod n;

这个算式是非常有价值的,因为a在算了e次幂后,再算d次幂竟然又算回来了,依然等于a;这个过程非常符合我们的加密和解密过程;而且e,d是不相同的,所以加密和解密过程将满足非对称的关系;所以我们可以这样设计RSA加密算法:

(8)RSA加密算法数学表达:

三、 RSA的破解原理

几乎所有关于RSA算法安全性的介绍都会提到,RSA算法的安全性基于大素数相乘不可分解的数学原理;那么它究竟是什么意思呢?

我们还是要看这个算式e*d+s* φ(n)=1;这是上文中结论1的算式;它也可以表示成上图的模式:e*d=1 mod φ(n);

其中n和e是公钥,是公开的给大家的,要想破解RSA算法,我就必须通过这个算式算出d来,但是φ(n)是多少我们也不知道;

在数学中,有这样一个事实,如果X*Y=Z,*表示数学运算,如果我们只知道X是多少,不知道Z,那么你是永远也算不出Y的;所以我们需要从已知的n出发,算出φ(n),进而算出d;

因为φ(n)=φ(p)φ(q)=(p-1)(q-1),所以我们只需要算出p和q,而n=p*q;因此RSA破解的核心问题就变成了分解n;当n的位数比较少时,我们可以通过计算机,运用遍历的方法,暴力破解出p和q,但是如果p,q是非常大的素数时呢?例如p,q是2048位的素数,那么暴力破解的耗时将剧增,这也就是所谓的大素数相乘不可分解的数学难题。

 

参考文献:https://blog.csdn.net/love_hot_girl/article/details/81164757

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/698801
推荐阅读
相关标签
  

闽ICP备14008679号