區(qū)塊鏈之非對(duì)稱加密算法

mcterry 發(fā)布于2019-06-27 18:41 / 2941人閱讀

摘要：二如何理解公鑰和私鑰非對(duì)稱加密算法需要兩個(gè)密鑰公開密鑰和私有密鑰。因?yàn)榧用芎徒饷苁褂玫氖莾蓚€(gè)不同的密鑰，所以這種算法叫作非對(duì)稱加密算法。三非對(duì)稱加密解密原理非對(duì)稱加密算法中，常用的就是算法了，以下就以算法為例來講解非對(duì)稱加密算法的實(shí)現(xiàn)原理。

非對(duì)稱加密，在現(xiàn)在網(wǎng)絡(luò)應(yīng)用中，有這非常廣泛的場(chǎng)景，更是加密貨幣的基礎(chǔ)。本文主要介紹非對(duì)稱加密、解密的原理和過程，以及在區(qū)塊鏈中的使用。

一、非對(duì)稱加密解密過程

A要向B發(fā)送信息，A和B都要產(chǎn)生一對(duì)用于加密、解密的公鑰和私鑰

A保管自己的私鑰，把公鑰告訴B；B保管自己的私鑰，把公鑰告訴A

A要給B發(fā)送信息時(shí)，A用B的公鑰加密信息，因?yàn)锳知道B的公鑰。

A將這個(gè)消息發(fā)給B（已經(jīng)用B的公鑰加密消息）。

B收到這個(gè)消息后，B用自己的私鑰解密A的消息。其他所有收到這個(gè)報(bào)文的人都無法解密，因?yàn)橹挥蠦才有B的私鑰。

二、如何理解公鑰和私鑰

??非對(duì)稱加密算法需要兩個(gè)密鑰：公開密鑰（public key）和私有密鑰（private key）。公開密鑰與私有密鑰是一對(duì)，如果用公開密鑰對(duì)數(shù)據(jù)進(jìn)行加密，只有用對(duì)應(yīng)的私有密鑰才能解密；如果用私有密鑰對(duì)數(shù)據(jù)進(jìn)行加密，那么只有用對(duì)應(yīng)的公開密鑰才能解密。因?yàn)榧用芎徒饷苁褂玫氖莾蓚€(gè)不同的密鑰，所以這種算法叫作非對(duì)稱加密算法。
??非對(duì)稱加密算法實(shí)現(xiàn)機(jī)密信息交換的基本過程是：甲方生成一對(duì)密鑰并將其中的一把作為公用密鑰向其它方公開；得到該公用密鑰的乙方使用該密鑰對(duì)機(jī)密信息進(jìn)行加密后再發(fā)送給甲方；甲方再用自己保存的另一把專用密鑰對(duì)加密后的信息進(jìn)行解密。
??非對(duì)稱密碼的特點(diǎn)：算法強(qiáng)度復(fù)雜、安全性依賴于算法與密鑰，但是由于其算法復(fù)雜，而使得加密解密速度沒有對(duì)稱加密解密的速度快。對(duì)稱密碼體制中只有一種密鑰，并且是非公開的，如果要解密就得讓對(duì)方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對(duì)稱密鑰體制有兩種密鑰，其中一個(gè)是公開的，這樣就可以不需要像對(duì)稱密碼那樣傳輸對(duì)方的密鑰了。這樣安全性就大了很多。

三、非對(duì)稱加密解密原理

非對(duì)稱加密算法中，常用的就是RSA算法了，以下就以RSA算法為例來講解非對(duì)稱加密算法的實(shí)現(xiàn)原理。

RSA算法的基于這樣的數(shù)學(xué)事實(shí)：兩個(gè)大質(zhì)數(shù)相乘得到的大數(shù)難以被因式分解。

RSA加密過程
$$ 密文＝明文^E mod N $$

解釋：也就是說RSA加密是對(duì)明文的E次方后除以N后求余數(shù)的過程。也就是說只要知道E（Encryption）和N（Number），任何人都可以進(jìn)行RSA加密了。其中E、N是RSA加密的密鑰，E和N的組合就是公鑰，我們用(E,N)來表示公鑰

$$ 公鑰＝(E,N) $$

不過E和N不并不是隨便什么數(shù)都可以的，它們都是經(jīng)過嚴(yán)格的數(shù)學(xué)計(jì)算得出的

RSA解密過程

$$ 明文＝密文^D mod N $$

也就是說對(duì)密文進(jìn)行D次方后除以N的余數(shù)就是明文，這就是RSA解密過程。知道D和N就能進(jìn)行解密密文了，所以D和N的組合就是私鑰

$$ 私鑰＝(D,N) $$
從上述可以看出RSA的加密方式和解密方式是相同的，加密是求"E次方的mod N"，解密是求"D次方的mod N"

知道上述的幾個(gè)簡(jiǎn)單公式后，剩下就是計(jì)算各個(gè)參數(shù)對(duì)應(yīng)的值了

求N。準(zhǔn)備兩個(gè)質(zhì)數(shù)p，q，這兩個(gè)數(shù)不能太小，太小則會(huì)容易破解，將p乘以q就是N。

$$ N=p?q $$

求L。L為中間數(shù)，是 (p－1) 和 (q－1) 的最小公倍數(shù)，可用如下表達(dá)式表示

$$ L=lcm（p－1，q－1） $$

求E。E必須滿足兩個(gè)條件：E是一個(gè)比1大比L小的數(shù)，E和L的最大公約數(shù)為1，用gcd(X,Y)來表示X，Y的最大公約數(shù)則E條件如下：

$$ 1 < E < L $$
$$ gcd（E，L）=1 $$
之所以需要E和L的最大公約數(shù)為1是為了保證一定存在解密時(shí)需要使用的數(shù)D。現(xiàn)在我們已經(jīng)求出了E和N也就是說我們已經(jīng)生成了密鑰對(duì)中的公鑰了。

求D。D是由數(shù)E計(jì)算出來的。D、E和L之間必須滿足以下關(guān)系：

$$ 1 < D < L $$
$$ E * D mod L ＝ 1 $$

至此，公鑰和私鑰都都計(jì)算出來了，大家可以自己試著計(jì)算下

四、為何非對(duì)稱加密難以破解

??破解RSA算法的關(guān)鍵就是計(jì)算N、p、q的值，給出兩個(gè)很大的質(zhì)數(shù)p、q，可以計(jì)算N，但知道N，去很難算出p、q，只能不停的嘗試，這就是為什么當(dāng)前RSA很難破解。
??RSA算法的破解與密鑰的長(zhǎng)度有關(guān)，如果密鑰的長(zhǎng)度小于等于256位，一臺(tái)較快的電腦可以在幾個(gè)小時(shí)內(nèi)成功分解其因子。位數(shù)越高因式分解所需時(shí)間也越長(zhǎng)。例如破解RSA-2048（2048-bit）的密鑰需要耗費(fèi)傳統(tǒng)電腦10億年的時(shí)間，而量子計(jì)算機(jī)只需要100秒就可以完成。所以隨著科技的發(fā)展，算法也會(huì)更新?lián)Q代。

歡迎訂閱「K叔區(qū)塊鏈」 - 專注于區(qū)塊鏈技術(shù)學(xué)習(xí)

博客地址：http://www.jouypub.com
簡(jiǎn)書主頁：https://www.jianshu.com/u/756c9c8ae984
segmentfault主頁：https://segmentfault.com/blog/jouypub
騰訊云主頁：https://cloud.tencent.com/developer/column/72548