非對稱加密技術- RSA演算法數學原理分析

4 人贊了文章

非對稱加密技術，在現在網路中，有非常廣泛應用。加密技術更是數字貨幣的基礎。

所謂非對稱，就是指該演算法需要一對密鑰，使用其中一個（公鑰）加密，則需要用另一個（私鑰）才能解密。 但是對於其原理大部分同學應該都是一知半解，今天就來分析下經典的非對稱加密演算法 - RSA演算法。 通過本文的分析，可以更好的理解非對稱加密原理，可以讓我們更好的使用非對稱加密技術。

題外話: 本博客一直有打算寫一系列文章通俗的密碼學，昨天給站點上https, 因其中使用了RSA演算法，就查了一下，發現現在網上介紹RSA演算法的文章都寫的太難理解了，反正也準備寫密碼學，就先寫RSA演算法吧，下面開始正文。

RSA演算法原理

RSA演算法的基於這樣的數學事實：兩個大質數相乘得到的大數難以被因式分解。 如：有很大質數p跟q，很容易算出N，使得 N = p * q， 但給出N, 比較難找p q（沒有很好的方式， 只有不停的嘗試）

這其實也是單向函數的概念

下面來看看數學演算過程：

1、選取兩個大質數p，q，計算N = p * q 及 φ ( N ) = φ (p) * φ (q) = (p-1) * (q-1)

三個數學概念： 質數(prime numbe)：又稱素數，為在大於1的自然數中，除了1和它本身以外不再有其他因數。 互質關係：如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質關係（coprime）。 φ(N)：叫做歐拉函數，是指任意給定正整數N，在小於等於N的正整數之中，有多少個與N構成互質關係。 >> 如果n是質數，則 φ(n)=n-1。 >> 如果n可以分解成兩個互質的整數之積， φ(n) = φ(p1p2) = φ(p1)φ(p2)。即積的歐拉函數等於各個因子的歐拉函數之積。

2、選擇一個大於1 小於φ(N)的數e，使得 e 和 φ(N)互質

e其實是1和φ(N)之前的一個質數

3、計算d，使得d*e=1 mod φ(N) 等價於方程式 ed-1 = k * φ(N) 求一組解

d 稱為e的模反元素，e 和 φ(N)互質就肯定存在d。

模反元素是指如果兩個正整數a和n互質，那麼一定可以找到整數b，使得ab被n除的餘數是1，則b稱為a的模反元素。

可根據歐拉定理證明模反元素存在，歐拉定理是指若n,a互質，則：

a^φ(n) ≡ 1(mod n) 及 a^φ(n) = a * a^（φ(n) - 1）， 可得a的 φ(n)-1 次方，就是a的模反元素。

4、(N, e)封裝成公鑰，(N, d)封裝成私鑰。 假設m為明文，加密就是算出密文c: m^e mod N = c (明文m用公鑰e加密並和隨機數N取余得到密文c) 解密則是： c^d mod N = m　(密文c用密鑰解密並和隨機數N取余得到明文m)私鑰解密這個是可以證明的，這裡不展開了。

加解密步驟

具體還是來看看步驟，舉個例子，假設Alice和Bob又要相互通信。

1. Alice 隨機取大質數P1=53，P2=59，那N=53*59=3127，φ(N)=3016
2. 取一個e=3，計算出d=2011。
3. 只將N=3127，e=3 作為公鑰傳給Bob（公鑰公開）
4. 假設Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，於是Bob傳回c=1394。 （公鑰加密過程）
5. Alice使用c^d mod N = 1394^2011 mod 3127，就能得到明文m=89。 （私鑰解密過程）

假如攻擊者能截取到公鑰n=3127，e=3及密文c=1394，是仍然無法不通過d來進行密文解密的。

安全性分析

那麼，有無可能在已知n和e的情況下，推導出d？

1. ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。　　2. φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。　　3. n=pq。只有將n因數分解，才能算出p和q。

如果n可以被因數分解，d就可以算出，因此RSA安全性建立在N的因式分解上。大整數的因數分解，是一件非常困難的事情。 只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。

補充模運算規則

1. 模運算加減法： (a + b) mod p = (a mod p + b mod p) mod p (a - b) mod p = (a mod p - b mod p) mod p
2. 模運算乘法： (a * b) mod p = (a mod p * b mod p) mod p
3. 模運算冪 a ^ b mod p = ((a mod p)^b) mod p

? 我的知識星球為各位解答區塊鏈技術問題，歡迎加入討論。

? 關注公眾號「深入淺出區塊鏈」第一時間獲取區塊鏈技術信息，系統學習區塊鏈，打造最好的區塊鏈技術博客。

http://weixin.qq.com/r/8imlvW-EYjIdrSve93zg (二維碼自動識別)