RSA加密是非對稱加密凛澎，由瑞弗斯特(Ron Rivest)薄翅，沙米爾(Adi Shamir)和阿德來門(Len Adleeman)于1978年提出的则吟，它的基礎(chǔ)是歐拉定理北秽，安全性依賴于大數(shù)因子分解的困難性。整個RSA加密運算，要了解一點數(shù)論的基礎(chǔ)朗恳。下面在講解的時候湿颅，需要用到的數(shù)學(xué)知識，我都會在一旁做簡單標(biāo)注粥诫。此文主要包括：
-
RSA加密算法 -
RSA加解密舉例 -
RSA加密的安全性 -
RSA加密算法的正確性證明
RSA加密算法
取兩個大素數(shù)
p和q(p ≠ q)油航，記n = pq，?(n) = (p-1)(q-1)怀浆。選擇正整數(shù)
w谊囚，w與?(n)互素，設(shè)d是w的模?(n)逆执赡，即dw ≡ 1(mod ?(n))镰踏。
RSA密碼算法如下：首先將明文數(shù)字化，后把明文分成若干段沙合，每一個明文段的值小于n奠伪，對每一個明文段m，
加密算法c = E(m) = m^w mod n
解密算法D(c) = c^d mod n
其中加密密鑰w和n是公開的pq?(n)和d是保密的首懈。
- 素數(shù)：只能被
±1和±自己整除的數(shù)绊率，比如2, 3, 5, 7, 11... - 兩數(shù)互素：除
±1之外，沒有其他的公因子究履，比如2 ~ 3滤否，7 ~ 11... -
?(n)：這個是歐拉函數(shù)，是指小于n且與n互素的正整數(shù)的個數(shù)最仑，習(xí)慣上?(1) = 1藐俺。算法中用到的?(n) = (p-1)(q-1)，p和q為素數(shù)盯仪，是歐拉函數(shù)的一個特殊情況紊搪。特殊情況還有n為素數(shù)時，?(n) = n - 1全景。 - 模
n同余：形如a ≡ b(mod n)這樣的算式稱為a b模n同余耀石，即a % n = b % n - 模逆：如果
ab ≡ 1(mod m)，即ab % m = 1爸黄，則稱b是a的模m逆滞伟；由定義可知，a的模m逆就是方程ax ≡ 1(mod m)的解炕贵，其中形如ax ≡ c(mod m)的方程稱一次同余方程梆奈。
RSA加解密舉例
A B 兩人通信，A要傳遞信息給 B称开，這時 B 公布出來加密的公鑰亩钟，A 以此將信息加密乓梨，B收到密文以后用私鑰解密，比如：
公鑰：w = 13, n = 2537
私鑰：p = 43, q = 59, ?(n) = 2436, d = 937(根據(jù) w 和 ?(n) 求出)
A 要傳遞的明文信息數(shù)字化之后為：m = 2106清酥，用公鑰加密為密文：c = 2106^13 % 2537 = 2321
B 收到密文 c = 2321 后扶镀，用私鑰解密為明文：m = 2321^937 % 2537 = 2106
上面加解密都要涉及到模冪乘運算形如：a^b(mod n)。這兒可以利用模運算的一個性質(zhì)：(a*b) % n = [(a % n) * (b % n)] % n
比如2106^13 % 2537 = [(2106 % 2537)(2106^4 % 2537)(2106^8 % 2537)] % 2537 = [(-431) * (-988) * (-601) % 2537] = 2321
求解過程可以使用遞歸求解的方式焰轻，2106^2 % 2537 可以根據(jù) 2106 % 2537 來求臭觉，2106^4 % 2537 可以根據(jù) 2106^2 % 2537 來求。比如 2106^4 % 2537 = [(2106^2 % 2537)(2106^2 % 2537)] % 2537 = (560 * 560) % 2537 = -988
RSA加密的安全性
開頭提到辱志，RSA加密的安全性依賴于大數(shù)因子分解的困難性蝠筑。因為 n 是公鑰公布出來的，如上例中 n = 2537 很容易就可以因為分解揩懒，求得 p = 43 q = 59什乙，繼而求出 ?(n) = 2436, d = 937，這樣就攻破了旭从。但是在實際中稳强，n 選的值一般為 1024位 的二進制整數(shù)，這么大的一個整數(shù)因式分解以目前的技術(shù)水平是不可能因式分解的和悦，對加密要求更高的行為，n 則選為2048位的二進制整數(shù)渠缕。
RSA加密算法的正確性證明
正確性證明需要用到費馬小定理和歐拉定理鸽素，表述如下
- 費馬小定理：若
a p互素，則a^(p-1) ≡ 1(mod p)亦鳞。另一種表示形式a^p ≡ a(mod p)馍忽，這種形式則不要求a p互素。
- 歐拉定理：若
a n互素燕差，則a^?(n) ≡ 1(mod n)遭笋。另一種表示形式a^?(n) ≡ a(mod n)，這種形式則不要求a n互素徒探。
因為m < n瓦呼，故解密算法 D(c) = c^d mod n ? c^d ≡ m(mod n)，又因為加密算法 c = m^w mod n测暗，故 c^d ≡ m(mod n) ? m^dw ≡ m(mod n)央串。又因為 dw ≡ 1(mod ?(n))，所以存在整數(shù) k 使得 dw = k?(n) + 1碗啄。最終轉(zhuǎn)換為證明：m^(k?(n) + 1) ≡ m(mod n)质和，其中k為整數(shù)。關(guān)于此證明可以分兩種情況討論：
m 與 n 互素
由歐拉定理 m^?(n) ≡ 1(mod n) ? m^k?(n) ≡ 1(mod n) ? m^(k?(n) + 1) ≡ m(mod n) 命題得證
m 與 n 不互素
由于 m < n稚字，n = pq饲宿，p 和 q 是素數(shù)且 p ≠ q厦酬，故 m 必含 p 和 q 中的一個為因子，且只含其中的一個為因子瘫想。設(shè) m = cp仗阅，由費馬小定理 m^(q - 1) ≡ 1(mod q) ? m^k?(n) ≡ m^(k(p-1)(q-1)) ≡ 1^k(p-1) ≡ 1(mod q)，從而存在整數(shù) h 使得 m^k?(n) = hq + 1殿托，兩邊同乘于 m 得霹菊，m^(k?(n) + 1) = mhq + m = cphq + m = hcn + m ? m^(k?(n) + 1) ≡ m(mod n) 命題得證
總結(jié)
RSA加密，整個過程的計算量是很大的支竹，只有特別敏感的信息才使用RSA加密旋廷。此文牽扯很多的數(shù)論的知識，也沒有講解的很詳細礼搁，只是用到的地方饶碘，直接給出了結(jié)論，其他一些馒吴，比如歐拉函數(shù)的通用公式扎运，一次同余方程求解方法，費馬小定理和歐拉定理的證明過程饮戳，計算模冪乘運算的通用公式豪治，都沒有做過多的詳解，因為這些不是此文的重點扯罐，如果你對這些感興趣负拟，可以參考下面我列出來的這本參考書，或者和我交流溝通歹河。這是一系列文章的其中一篇掩浙，你可以在這兒Encode & Decode集序找到他其他的兄弟。
參考
- 屈婉玲,耿素云,張立昂. 離散數(shù)學(xué):高等教育出版社
