區(qū)塊鏈核心算法之非對稱加密技術(shù)區(qū)塊鏈
如果10個將軍中的幾個同時發(fā)起消息，勢必會造成系統(tǒng)的混亂，造成各說各的攻擊時間方案，行動難以一致。非對稱加密技術(shù)完全可以解決這個簽名問題。
上一篇在曲速未來安全區(qū)中說到的拜占庭協(xié)定中，如果10個將軍中的幾個同時發(fā)起消息，勢必會造成系統(tǒng)的混亂，造成各說各的攻擊時間方案，行動難以一致。誰都可以發(fā)起進攻的信息，但由誰來發(fā)出呢？其實這只要加入一個成本就可以了，即：一段時間內(nèi)只有一個節(jié)點可以傳播信息。當某個節(jié)點發(fā)出統(tǒng)一進攻的消息后，各個節(jié)點收到發(fā)起者的消息必須簽名蓋章，確認各自的身份。
如今，非對稱加密技術(shù)完全可以解決這個簽名問題。
非對稱加密技術(shù)，在現(xiàn)在網(wǎng)絡中，有非常廣泛應用。加密技術(shù)更是數(shù)字貨幣的基礎。
所謂非對稱，就是指該算法需要一對密鑰，使用其中一個（公鑰）加密，則需要用另一個（私鑰）才能解密。非對稱加密，加密與解密使用的密鑰不是同一密鑰，對中一個對外公開，稱為公鑰，另一個只有所有者知道，稱為私鑰。
用公鑰加密的信息只有私鑰才能解開，反之，用私鑰加密的信息只有公鑰才能解開（簽名驗簽）。
代表：RSA算法。速度慢，適合少量數(shù)據(jù)加密。對稱加密算法不能實現(xiàn)簽名，因此簽名只能非對稱算法。
RSA算法原理
RSA算法的基于這樣的數(shù)學事實：兩個大質(zhì)數(shù)相乘得到的大數(shù)難以被因式分解。如：有很大質(zhì)數(shù)p跟q，很容易算出N，使得 N = p * q，但給出N, 比較難找p q（沒有很好的方式， 只有不停的嘗試）
這其實也是單向函數(shù)的概念。
下面來看看數(shù)學演算過程：
選取兩個大質(zhì)數(shù)p，q，計算N = p * q 及 φ ( N ) = φ (p) * φ (q) = (p-1) * (q-1)
質(zhì)數(shù)(prime numbe)：又稱素數(shù)，為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。
互質(zhì)關(guān)系：如果兩個正整數(shù)，除了1以外，沒有其他公因子，我們就稱這兩個數(shù)是互質(zhì)關(guān)系（coprime）。
φ(N)：叫做歐拉函數(shù)，是指任意給定正整數(shù)N，在小于等于N的正整數(shù)之中，有多少個與N構(gòu)成互質(zhì)關(guān)系。
1. 歐拉函數(shù)
定義：對于一個正整數(shù) n ，小于 n 且和 n 互質(zhì)的正整數(shù)（包括 1）的個數(shù)，記作 φ(n).則
證明：
如果n是一個質(zhì)數(shù)，那么φ(n) = n-1
如果n是一個質(zhì)數(shù)p的冪，即n = p^k，則φ(n) = p^k-p^(k-1) = (p-1)*p^(k-1)
歐拉函數(shù)是一個積性函數(shù)，當n,m互質(zhì)的時候，φ(n*m) = φ(n)*φ(m)
2. 歐拉定理
1.定義：如果兩個正整數(shù)a和n互質(zhì)，則n的歐拉函數(shù) φ(n) 可以讓下面的等式成立：
a^φ(n)%n=1
2.選擇一個大于1 小于φ(N)的數(shù)e，使得 e 和 φ(N)互質(zhì)
3.計算d，使得de=1 mod φ(N) 等價于方程式 ed-1 = k φ(N) 求一組解。
4. (N, e)封裝成公鑰，(N, d)封裝成私鑰。假設m為明文，加密就是算出密文c:m^e mod N = c (明文m用公鑰e加密并和隨機數(shù)N取余得到密文c)解密則是：c^d mod N = m (密文c用密鑰解密并和隨機數(shù)N取余得到明文m)
加解密步驟
具體還是來看看步驟，舉個例子，假設Alice和Bob又要相互通信。
Alice 隨機取大質(zhì)數(shù)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可以被因數(shù)分解，d就可以算出，因此RSA安全性建立在N的因式分解上。大整數(shù)的因數(shù)分解，是一件非常困難的事情。只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。
RSA核心算法
快速冪取模算法
算法1：連乘算法，時間復雜度O(n)
算法2：快速冪算法，時間復雜度O(logn)
算法3：快速冪取模算法，時間復雜度O(logn)
素數(shù)判定算法
由于非對稱加密算法的運行速度比對稱加密算法的速度慢很多，當我們需要加密大量的數(shù)據(jù)時，建議采用對稱加密算法，提高加解密速度。
對稱加密算法不能實現(xiàn)簽名，因此簽名只能非對稱算法。
由于對稱加密算法的密鑰管理是一個復雜的過程，密鑰的管理直接決定著他的安全性，因此當數(shù)據(jù)量很小時，我們可以考慮采用非對稱加密算法。
在實際的操作過程中，我們通常采用的方式是：采用非對稱加密算法管理對稱算法的密鑰，然后用對稱加密算法加密數(shù)據(jù)，這樣我們就集成了兩類加密算法的優(yōu)點，既實現(xiàn)了加密速度快的優(yōu)點，又實現(xiàn)了安全方便管理密鑰的優(yōu)點。
1.TMT觀察網(wǎng)遵循行業(yè)規(guī)范，任何轉(zhuǎn)載的稿件都會明確標注作者和來源；
2.TMT觀察網(wǎng)的原創(chuàng)文章，請轉(zhuǎn)載時務必注明文章作者和"來源：TMT觀察網(wǎng)"，不尊重原創(chuàng)的行為TMT觀察網(wǎng)或?qū)⒆肪控熑危?br>
3.作者投稿可能會經(jīng)TMT觀察網(wǎng)編輯修改或補充。
