我們最常用的密碼RSA簡要分析：
RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。--百度百科
RSA算法基于一個十分簡單的數(shù)論事實：將兩個大質(zhì)數(shù)相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。
設(shè)n=a*b(a,b為質(zhì)數(shù))
m=(a-1)*(b-1)
任取一個數(shù)字e，使得(e,m)=1,即e與m互質(zhì)。
所以，可得，
存x,y使得
x*e+y*m=1,
==>
xe≡1（mod m）
任取一個常數(shù)C，由費馬小定理可知：
C^(a-1)≡1(mod a)
C^(b-1)≡1(mod b)
費馬小定理：若p是素數(shù)或者(p,A)=1, A為任意正整數(shù),則
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為質(zhì)數(shù)，所以(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的倍數(shù), xe-1=q*m=q*(a-1)(b-1)
所以：
C^(xe-1)≡1(mod a*b)
又因為n=ab，所以：
C^xe≡C(mod n)
現(xiàn)在我們將n,e這兩個數(shù)作為公鑰n,x這兩個數(shù)作為密鑰，
現(xiàn)在我們明白了以下問題:
首先我們說的“密鑰”是指誰？由于RSA密鑰是（公鑰+模值）、（私鑰+模值）分組分發(fā)的，單獨給對方一個公鑰或私鑰是沒有任何用處，所以我們說的“密鑰”其實是它們兩者中的其中一組。但我們說的“密鑰長度”一般只是指模值的位長度。目前主流可選值：1024、2048、3072、4096...
當(dāng)我們要將一個數(shù)C用公鑰加密發(fā)送給私鑰持有者的時候，我們就計算
C^e mod n = z
僅僅根據(jù)z這個值是很難重新計算回C的值的，即使知道n和e也不可以。但是當(dāng)我們拿到這個結(jié)果，然后我們又知道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
