这么先进的加密算法RSA你知道吗?

时间:2021-09-01 03:09:31

前面有人让我讲解一下RSA算法,今天我就用我所学的知识讲解一下,首先我们先了解一下RSA

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

这么先进的加密算法RSA你知道吗?

在了解非对称性加密的时候我们需要了解什么叫对称性加密。我们就那徐克导演拍的电影《智取威虎山》,其中的一段对话

  • 土匪:天王盖地虎!
  • 杨子荣:宝塔镇河妖!
  • 土匪:野鸡闷头钻,哪能上天王山!
  • 杨子荣:地上有的是米,喂呀,有根底!
  • 土匪:拜见过阿妈啦?
  • 杨子荣:他房上没瓦,非否非,否非否!

通过他们的对话我们知道 土匪在试探杨子荣的身份。当土匪说,天王盖地虎,我就必须说 宝塔镇河妖!也就是双方都知道 这段话是什么意思。翻译成程序员的话就是 双方都有加密的密钥。因此对称加密也可以说是秘密交易者的暗号。

不过对称加密有一个很大的问题,密钥容易泄露。土匪的暗号被杨子荣知道了这个就很容易取得了他们的信任。

RSA加密

我们需要先预习一下还给数学老师的知识

欧拉函数

在数论中,存在正整数 n,小于n并且与n互质的正整数的数目称为n的欧拉函数记着φ(n)。例如:

  • φ(7) 7对应的比7小的与7互质的数有1、2、3、4、5、6共6个,因此φ(7)=6;
  • φ(8) 8对应的比8小的与8互质的数有1,3,5,7共4个,因此φ(8)=4;
  • φ(9) 9对应的比9小的与9互质的数有1,2,4,5,6,7,8共7个,,因此φ(9)=7。

这么先进的加密算法RSA你知道吗?
通式(P是数N的质因数)

  • φ(10)=10×(1-1/2)×(1-1/5)=4;
  • φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
  • φ(49)=49×(1-1/7)=42。

若m n互质:φ(n * m)=φ(n)* φ(m),如果n为质数那么φ(n)=n-1。

分解质因数求值:φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。

欧拉定理

如果两个正整数m和n互质,那么m的φ(n) 次方对n取余衡等于1。m^φ(n)%n≡1。

费马小定理

存在一个质数p,而整数a不是p的倍数,则存在a^(p-1)%p≡1。费马小定理是欧拉定理的特殊情况。因为φ(p)=p-1(任何数都与质数互质)。

模反元素

如果两个正整数e和x互质,那么一定存在一个整数d,使得ed-1能够被x整除,则称d是e对x的模反元素。e * d % x≡1,那么e * d ≡ k*x+1。

由以上定理得出以下几个公式:

m^φ(n)%n≡1

m^(k * φ(n))%n≡1 两端同乘以m

m^(k * φ(n)+1)%n≡m

e * d≡k * x+1

m^e * d%n≡m 替换第3步k * φ(n)+1

而m^e*d%n≡m就是我们需要的一个非对称加密的公式。m为明文,e和d分别对应的是公钥私钥。迪菲卡尔曼秘钥交换对公式拆分:

  • m^e%n=c 加密
  • c^d%n=m 解密

其中c为通过e加密后的密文,然后通过d可以解出明文m。因此:

  • 公钥: e、n
  • 秘钥:d、n
  • 明文:m
  • 密文:c

RSA加密过程

取两个质数p1、p2;

确定n值,n=p1 * p2,n值一般会很大长度一般为1024个二进制位;

确定φ(n),φ(n)=(p1-1) * (p2-1);

确定e值,1

确定d值,e*d%φ(n)=1;

加密 c=m^e%n;

解密m=c^d%n。

实际验证:

p1=3, p2=7;

n=p1 * p2=3 * 7=21;

φ(n)=(p1-1) * (p2-1)=2*6=12;

1

e * d % φ(n)=5 * d % 12=1,得d=17;

设置明文m=3,则c = m^e % n = 3^5 % 21=12;

解密密文m=c^d % n=12^17 % 21=3。

通过上面的讲解我们知道在RSA 加密中用到的几6个参数

p1  

p2  

 

φ(n)  

 

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

e*d%φ(n)=1 (只有知道e和φ(n),才能算出d。)

φ(n)=(p1-1) * (p2-1) (只有知道p1和p2,才能算出φ(n)。)

n=p1*p2 (只有将n因数分解,才能算出p和q。)

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。*这样写道:

"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"

或许你看到这里还不相信,我写个程序挨着试 不就可以破解出来吗?例如 21 你或许会很快的分解成 3×7 但是这个数再大一点 比如 这个质数 2^57,885,161-1 它有超过1千7百万个数位 如果让传统计算机来验证他是不是质数 估计可以跑到天荒地老。

原文地址:https://www.toutiao.com/a6909656008197603843/