麻豆国内精品欧美在线-麻豆国内精品久久久久久-麻豆国产在线观看一区二区-麻豆国产在线观看免费-麻豆国产原创-麻豆国产一区二区在线观看

上一篇在曲速未來(lái)安全區(qū)中說(shuō)到的拜占庭協(xié)定中，如果10個(gè)將軍中的幾個(gè)同時(shí)發(fā)起消息，勢(shì)必會(huì)造成系統(tǒng)的混亂，造成各說(shuō)各的攻擊時(shí)間方案，行動(dòng)難以一致。誰(shuí)都可以發(fā)起進(jìn)攻的信息，但由誰(shuí)來(lái)發(fā)出呢？其實(shí)這只要加入一個(gè)成本就可以了，即：一段時(shí)間內(nèi)只有一個(gè)節(jié)點(diǎn)可以傳播信息。當(dāng)某個(gè)節(jié)點(diǎn)發(fā)出統(tǒng)一進(jìn)攻的消息后，各個(gè)節(jié)點(diǎn)收到發(fā)起者的消息必須簽名蓋章，確認(rèn)各自的身份。

如今，非對(duì)稱加密技術(shù)完全可以解決這個(gè)簽名問(wèn)題。

非對(duì)稱加密技術(shù)，在現(xiàn)在網(wǎng)絡(luò)中，有非常廣泛應(yīng)用。加密技術(shù)更是數(shù)字貨幣的基礎(chǔ)。

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

用公鑰加密的信息只有私鑰才能解開(kāi)，反之，用私鑰加密的信息只有公鑰才能解開(kāi)（簽名驗(yàn)簽）。

代表：RSA算法。速度慢，適合少量數(shù)據(jù)加密。對(duì)稱加密算法不能實(shí)現(xiàn)簽名，因此簽名只能非對(duì)稱算法。

RSA算法原理

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

這其實(shí)也是單向函數(shù)的概念。

下面來(lái)看看數(shù)學(xué)演算過(guò)程：

選取兩個(gè)大質(zhì)數(shù)p，q，計(jì)算N = p * q 及 φ ( N ) = φ (p) * φ (q) = (p-1) * (q-1)

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

互質(zhì)關(guān)系：如果兩個(gè)正整數(shù)，除了1以外，沒(méi)有其他公因子，我們就稱這兩個(gè)數(shù)是互質(zhì)關(guān)系（coprime）。

φ(N)：叫做歐拉函數(shù)，是指任意給定正整數(shù)N，在小于等于N的正整數(shù)之中，有多少個(gè)與N構(gòu)成互質(zhì)關(guān)系。

1. 歐拉函數(shù)

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

證明：

如果n是一個(gè)質(zhì)數(shù)，那么φ(n) = n-1

如果n是一個(gè)質(zhì)數(shù)p的冪，即n = p^k，則φ(n) = p^k-p^(k-1) = (p-1)*p^(k-1)

歐拉函數(shù)是一個(gè)積性函數(shù)，當(dāng)n,m互質(zhì)的時(shí)候，φ(n*m) = φ(n)*φ(m)

2. 歐拉定理

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

a^φ(n)%n=1

2.選擇一個(gè)大于1 小于φ(N)的數(shù)e，使得 e 和 φ(N)互質(zhì)

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

4. (N, e)封裝成公鑰，(N, d)封裝成私鑰。假設(shè)m為明文，加密就是算出密文c:m^e mod N = c (明文m用公鑰e加密并和隨機(jī)數(shù)N取余得到密文c)解密則是：c^d mod N = m　(密文c用密鑰解密并和隨機(jī)數(shù)N取余得到明文m)

加解密步驟

具體還是來(lái)看看步驟，舉個(gè)例子，假設(shè)Alice和Bob又要相互通信。

Alice 隨機(jī)取大質(zhì)數(shù)P1=53，P2=59，那N=53*59=3127，φ(N)=3016

取一個(gè)e=3，計(jì)算出d=2011。

只將N=3127，e=3 作為公鑰傳給Bob（公鑰公開(kāi)）

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

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

安全性分析

那么，有無(wú)可能在已知n和e的情況下，推導(dǎo)出d？

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

RSA核心算法

快速冪取模算法

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

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

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

素?cái)?shù)判定算法

由于非對(duì)稱加密算法的運(yùn)行速度比對(duì)稱加密算法的速度慢很多，當(dāng)我們需要加密大量的數(shù)據(jù)時(shí)，建議采用對(duì)稱加密算法，提高加解密速度。

對(duì)稱加密算法不能實(shí)現(xiàn)簽名，因此簽名只能非對(duì)稱算法。

由于對(duì)稱加密算法的密鑰管理是一個(gè)復(fù)雜的過(guò)程，密鑰的管理直接決定著他的安全性，因此當(dāng)數(shù)據(jù)量很小時(shí)，我們可以考慮采用非對(duì)稱加密算法。

在實(shí)際的操作過(guò)程中，我們通常采用的方式是：采用非對(duì)稱加密算法管理對(duì)稱算法的密鑰，然后用對(duì)稱加密算法加密數(shù)據(jù)，這樣我們就集成了兩類加密算法的優(yōu)點(diǎn)，既實(shí)現(xiàn)了加密速度快的優(yōu)點(diǎn)，又實(shí)現(xiàn)了安全方便管理密鑰的優(yōu)點(diǎn)。