TMT观察网_独特视角观察TMT行业

上一篇在曲速未來安全區中說到的拜占庭協定中，如果10個將軍中的幾個同時發起消息，勢必會造成系統的混亂，造成各說各的攻擊時間方案，行動難以一致。誰都可以發起進攻的信息，但由誰來發出呢？其實這只要加入一個成本就可以了，即：一段時間內只有一個節點可以傳播信息。當某個節點發出統一進攻的消息后，各個節點收到發起者的消息必須簽名蓋章，確認各自的身份。

如今，非對稱加密技術完全可以解決這個簽名問題。

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

所謂非對稱，就是指該算法需要一對密鑰，使用其中一個（公鑰）加密，則需要用另一個（私鑰）才能解密。非對稱加密，加密與解密使用的密鑰不是同一密鑰，對中一個對外公開，稱為公鑰，另一個只有所有者知道，稱為私鑰。

用公鑰加密的信息只有私鑰才能解開，反之，用私鑰加密的信息只有公鑰才能解開（簽名驗簽）。

代表：RSA算法。速度慢，適合少量數據加密。對稱加密算法不能實現簽名，因此簽名只能非對稱算法。

RSA算法原理

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

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

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

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

質數(prime numbe)：又稱素數，為在大于1的自然數中，除了1和它本身以外不再有其他因數。

互質關系：如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質關系（coprime）。

φ(N)：叫做歐拉函數，是指任意給定正整數N，在小于等于N的正整數之中，有多少個與N構成互質關系。

1. 歐拉函數

定義：對于一個正整數 n ，小于 n 且和 n 互質的正整數（包括 1）的個數，記作 φ(n).則

證明：

如果n是一個質數，那么φ(n) = n-1

如果n是一個質數p的冪，即n = p^k，則φ(n) = p^k-p^(k-1) = (p-1)*p^(k-1)

歐拉函數是一個積性函數，當n,m互質的時候，φ(n*m) = φ(n)*φ(m)

2. 歐拉定理

1.定義：如果兩個正整數a和n互質，則n的歐拉函數 φ(n) 可以讓下面的等式成立：      

a^φ(n)%n=1

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

3.計算d，使得de=1 mod φ(N) 等價于方程式 ed-1 = k φ(N) 求一組解。

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又要相互通信。

Alice 隨機取大質數P1=53，P2=59，那N=53*59=3127，φ(N)=3016

取一個e=3，計算出d=2011。

只將N=3127，e=3 作為公鑰傳給Bob（公鑰公開）

假設Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，于是Bob傳回c=1394。 （公鑰加密過程）

Alice使用c^d mod N = 1394^2011 mod 3127，就能得到明文m=89。 （私鑰解密過程）

安全性分析

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

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

RSA核心算法

快速冪取模算法

算法1：連乘算法，時間復雜度O(n)

算法2：快速冪算法，時間復雜度O(logn)

算法3：快速冪取模算法，時間復雜度O(logn)

素數判定算法

由于非對稱加密算法的運行速度比對稱加密算法的速度慢很多，當我們需要加密大量的數據時，建議采用對稱加密算法，提高加解密速度。

對稱加密算法不能實現簽名，因此簽名只能非對稱算法。

由于對稱加密算法的密鑰管理是一個復雜的過程，密鑰的管理直接決定著他的安全性，因此當數據量很小時，我們可以考慮采用非對稱加密算法。

在實際的操作過程中，我們通常采用的方式是：采用非對稱加密算法管理對稱算法的密鑰，然后用對稱加密算法加密數據，這樣我們就集成了兩類加密算法的優點，既實現了加密速度快的優點，又實現了安全方便管理密鑰的優點。