我们最常用的密码RSA简要分析：
RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。--百度百科
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
设n=a*b(a,b为质数)
m=(a-1)*(b-1)
任取一个数字e，使得(e,m)=1,即e与m互质。
所以，可得，
存x,y使得
x*e+y*m=1,
==>
xe≡1（mod m）
任取一个常数C，由费马小定理可知：
C^(a-1)≡1(mod a)
C^(b-1)≡1(mod b)
费马小定理：若p是素数或者(p,A)=1, A为任意正整数,则
A^(p-1) ≡ 1 (mod p)
引理1（华罗庚文集2 P21 定理2）
若a1≡b1,a2≡b2,则a1a2≡b1b2(mod m),
由此可得一下推论
a1n≡b1n(mod m)
由引理1得出推论1：
(C^(a-1))^(b-1) ≡1^(b-1) (mod a)
(C^(b-1))^(a-1) ≡1^(a-1) (mod b)
即
a | C^(a-1)(b-1)-1
b | C^(a-1)(b-1)-1
又因为a，b为质数，所以(a,b)=1,所以ab | C^(a-1)(b-1)-1
即：
C^(a-1)(b-1) ≡1(mod a*b)
其实这里还可以得到推论2：
若a≡b (mi) ,i=1,2···，m,则
a≡b(mod [m1，m2，···，ms])
证明同上。
由于xe-1是m的倍数, xe-1=q*m=q*(a-1)(b-1)
所以：
C^(xe-1)≡1(mod a*b)
又因为n=ab，所以：
C^xe≡C(mod n)
现在我们将n,e这两个数作为公钥n,x这两个数作为密钥，
现在我们明白了以下问题:
首先我们说的“密钥”是指谁？由于RSA密钥是（公钥+模值）、（私钥+模值）分组分发的，单独给对方一个公钥或私钥是没有任何用处，所以我们说的“密钥”其实是它们两者中的其中一组。但我们说的“密钥长度”一般只是指模值的位长度。目前主流可选值：1024、2048、3072、4096...
当我们要将一个数C用公钥加密发送给私钥持有者的时候，我们就计算
C^e mod n = z
仅仅根据z这个值是很难重新计算回C的值的，即使知道n和e也不可以。但是当我们拿到这个结果，然后我们又知道n和 x 的时候，我们可以计算：
z^x mod n =(C^e mod n)^x mod n =C^xe mod n=C
是不是很神奇又将C给解了出来。
参考链接：
https://www.zhihu.com/question/48927324/answer/113359990?utm_source=qq&utm_medium=social
网友评论