【掃盲班—密碼算法解析】
如果您還是密碼學(xué)小白，那你需要先簡(jiǎn)單了解一下常用的密碼算法：對(duì)稱(chēng)加密、非對(duì)稱(chēng)加密、數(shù)字簽名和摘要算法。
＜對(duì)稱(chēng)加密＞
對(duì)稱(chēng)加密又叫傳統(tǒng)密碼算法，就是加密和解密使用同一個(gè)密鑰。潛伏里面孫紅雷通過(guò)電臺(tái)收聽(tīng)到一堆數(shù)字，然后拿出一本書(shū)（密碼本）比對(duì)，找到數(shù)字對(duì)應(yīng)的漢字，就明白上級(jí)傳達(dá)的是什么指令了。而軍統(tǒng)的監(jiān)聽(tīng)臺(tái)沒(méi)有密碼本，只看到一堆沒(méi)有意義的數(shù)字。
用數(shù)學(xué)公示表示就是：
▲加密：Ｅk(P) = C
▲解密: Ｄk(C) = P
這里E表示加密算法，D表示解密算法，P表示明文, C表示密文。留意以后會(huì)經(jīng)?？吹?。常見(jiàn)的對(duì)稱(chēng)加密方法有DES、3DES、Blowfish、RC2、AES以及國(guó)密的SM4。
有同學(xué)會(huì)問(wèn)，什么是國(guó)密??？很機(jī)密么？沒(méi)那么夸張，其實(shí)它的全稱(chēng)叫“國(guó)家商用密碼”，是為了保障商用密碼安全，國(guó)家商用密碼管理辦公室制定了一系列密碼標(biāo)準(zhǔn)。
<非對(duì)稱(chēng)加密>
對(duì)稱(chēng)加密又快又方便，但是有個(gè)很大的坑——密碼本容易被偷或被破解。從紅軍到二戰(zhàn)，勝利的最大貢獻(xiàn)其實(shí)就是破解密碼。紅軍在數(shù)十倍的包圍圈里面自由跳來(lái)跳去，那兩臺(tái)大功率電臺(tái)功勞莫大。
怎么能夠防止這種情況呢？1977年三位數(shù)學(xué)家Rivest、Shamir 和 Adleman 設(shè)計(jì)了一種算法(所以叫RSA)，把密鑰分成兩個(gè)，一個(gè)自己持有叫私鑰(Private Key)，另一個(gè)發(fā)給對(duì)方，還可以公開(kāi)，叫公鑰(Public Key)，實(shí)現(xiàn)用公鑰加密的數(shù)據(jù)只能用私鑰解開(kāi)：
▲加密: E公鑰(P) = C
▲解密: D私鑰(C) = P
這下就不用再頭痛如何把密碼本給對(duì)方或被破解了，私鑰由自己保管，敵方攔截到密文也沒(méi)有辦法。
除了RSA之外，常見(jiàn)的非對(duì)稱(chēng)算法還有Elgamal、背包算法、Rabin、D-H、ECC（橢圓曲線加密算法）以及國(guó)家商用密碼SM2算法。
非對(duì)稱(chēng)算法核心原理其實(shí)就是設(shè)計(jì)一個(gè)數(shù)學(xué)難題，使得用公鑰和明文推導(dǎo)密文很容易，但是很難根據(jù)公鑰、明文和密文推導(dǎo)私鑰。
RSA是基于大整數(shù)因式分解難度，也就是兩個(gè)質(zhì)數(shù)相乘很容易，但是找一個(gè)大數(shù)的質(zhì)因子非常困難，理論上破解RSA-2048(2048-bit)的密鑰可能需要耗費(fèi)10億年的時(shí)間。
這兒說(shuō)點(diǎn)題外話：強(qiáng)烈不建議使用RSA，原因如下：
▲容易被破解：RSA-768可以在3個(gè)小時(shí)內(nèi)破解，1024在理論上100小時(shí)內(nèi)也可以破解。所以使用RSA，長(zhǎng)度起步要2048。但是數(shù)學(xué)家彼得·舒爾研究了一個(gè)針對(duì)整數(shù)分解問(wèn)題的量子算法 (舒爾算法)，理論上破解2048的RSA在100秒之內(nèi)(好在量子機(jī)還未投入使用)。
▲慢：密鑰長(zhǎng)度加到2048可以提升安全，但是計(jì)算過(guò)慢。
<數(shù)字簽名>
有了非對(duì)稱(chēng)加密，數(shù)字簽名就很容易理解了。
乙方收到甲方傳過(guò)來(lái)的一串信息，怎么能夠確定確實(shí)是甲方而不是有人偽造呢？
我們把非對(duì)稱(chēng)加密反過(guò)來(lái)做就可以了，因?yàn)橹挥屑追阶约翰懦钟幸环菝孛艿乃借€，他拿這個(gè)私鑰對(duì)數(shù)據(jù)進(jìn)行加密得到密文 C = EA私(M)，乙方持有甲方的公鑰，解密明文P = DA公(C)，如果能夠解密成功就證明信息確實(shí)是甲方所發(fā)。
不過(guò)通常不需要對(duì)發(fā)送信息的整個(gè)內(nèi)容都加密，那樣太慢。只需要計(jì)算一個(gè)信息的唯一信息摘要并對(duì)信息摘要加密解密即可，下面就會(huì)講到數(shù)據(jù)摘要算法（俗稱(chēng)HASH算法），這也是數(shù)字簽名的算法名稱(chēng)，很多時(shí)候是一個(gè)摘要算法 非對(duì)稱(chēng)算法，例如SHA1RSA, SHA256RSA等。
<摘要算法>
俗稱(chēng)HASH算法，學(xué)名雜湊算法，也就是從明文P生成較短的固定長(zhǎng)度的雜湊值，保證不同的輸入產(chǎn)生的輸出是唯一的(重復(fù)幾率非常非常小)。這樣就可以廣泛用于完整性檢查、數(shù)字簽名等場(chǎng)景。
常見(jiàn)的摘要算法有MD5、RIPEMD、SHA和國(guó)密的SM3。MD5不建議使用，已經(jīng)被爆。
【實(shí)戰(zhàn)班—區(qū)塊鏈應(yīng)用】
區(qū)塊鏈提供了通過(guò)機(jī)器算法解決參與人之間的信任問(wèn)題的全新方案，其核心的核心就是在不完全信任的各方，通過(guò)深度使用密碼學(xué)算法來(lái)保證數(shù)據(jù)的不可篡改特性。
本節(jié)結(jié)合實(shí)際區(qū)塊鏈中的應(yīng)用，讓大家在了解區(qū)塊鏈的同時(shí)，一起驚嘆原來(lái)加密算法還可以這么用。
<比特幣之誰(shuí)能動(dòng)我的錢(qián)>
比特幣是公有鏈，賬本分布在無(wú)中心的節(jié)點(diǎn)上，任何一個(gè)節(jié)點(diǎn)都可以發(fā)出一個(gè)轉(zhuǎn)讓比特幣的交易。那我的比特幣是如何保證不被別人轉(zhuǎn)走的呢？
假設(shè)你擁有100比特幣（好有錢(qián)喲），那么在公開(kāi)賬本上存有一個(gè)數(shù)據(jù)結(jié)構(gòu)，即所謂的UTXO，其主要內(nèi)容有：
▲index: 索引
▲value: 金額
▲hash：一個(gè)SHA256的數(shù)據(jù)摘要
▲script: 腳本，這個(gè)是重點(diǎn)要講的
這個(gè)script是一串可執(zhí)行的二進(jìn)制代碼，比特幣定義了一個(gè)基于堆棧的腳本執(zhí)行器，可以執(zhí)行加減乘除、移位、HASH、驗(yàn)簽等算法，類(lèi)似于常見(jiàn)的科學(xué)計(jì)算器。當(dāng)你想花費(fèi)持有的比特幣時(shí)，首先需要執(zhí)行作為輸入交易對(duì)應(yīng)UTXO的腳本(script)，稱(chēng)之為“解鎖腳本”，只有執(zhí)行成功才能繼續(xù)。
最常用的一個(gè)解鎖腳本就是P2PKH腳本：
解鎖時(shí)傳入簽名和公鑰組成完整腳本：
翻譯起來(lái)就是： “公鑰的HASH160等于<腳本里面的值>并且用這個(gè)公鑰對(duì)HASH值驗(yàn)證簽名能夠通過(guò)”。計(jì)算通過(guò)，才可以花費(fèi)這筆資金。
因?yàn)樗借€保存在你自己手上，其他人無(wú)法計(jì)算出一個(gè)滿足條件的簽名，從而保證了這筆資金只有你自己可以使用。
這里除了數(shù)字簽名外，還有一點(diǎn)體現(xiàn)了中本聰真的很聰明，賬本上不會(huì)存儲(chǔ)你的公鑰，而是其HASH160(雙HASH,SHA256 RIPEMD160)，由于HASH是單向的，從HASH無(wú)法反向推導(dǎo)公鑰，這樣大大減少未來(lái)量子機(jī)會(huì)帶來(lái)的風(fēng)險(xiǎn)。
<區(qū)塊鏈-HASH鏈之如何防止篡改>
前面講了數(shù)字簽名在比特幣的用法，這里結(jié)合區(qū)塊鏈數(shù)據(jù)結(jié)構(gòu)本身講一下HASH的用法。
一個(gè)塊只是組織數(shù)據(jù)的結(jié)構(gòu)，這里暫不詳述，關(guān)鍵是塊里面有個(gè)重要的參數(shù) – 前一塊的HASH，這樣就形成一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)。
我們把數(shù)據(jù)豎起來(lái)看，就像是玩積木游戲，節(jié)點(diǎn)你一塊我一塊向上羅，每一塊和前一塊都有個(gè)鉤子。如果這個(gè)時(shí)候有人試圖篡改之前的一筆交易，勢(shì)必會(huì)導(dǎo)致那個(gè)塊的HASH變了，那為了使得改過(guò)的交易被大家認(rèn)可，他可以以這個(gè)被改過(guò)的塊為起點(diǎn)，重新計(jì)算后面所有的塊，關(guān)鍵是還得比拼得過(guò)全世界其他的節(jié)點(diǎn)，目前還沒(méi)人能夠做到。
這里就突出了HASH算法的特點(diǎn)：
▲數(shù)據(jù)改變一點(diǎn)點(diǎn)，HASH改變非常大。
▲無(wú)法給不同的數(shù)據(jù)計(jì)算出相同的HASH(或者說(shuō)非常難)。
<比特幣和以太坊的公私鑰—ECC算法>
RSA又慢又不安全，所以比特幣和以太坊都不采用，而是使用了更安全的橢圓曲線算法 – ECC來(lái)做非對(duì)稱(chēng)加密基礎(chǔ)算法。ECC的210位算法難度就相當(dāng)于RSA 2048的難度，性能則是數(shù)量級(jí)的區(qū)別。那么橢圓算法又是何方神圣呢？
前面講過(guò)非對(duì)稱(chēng)算法無(wú)非是設(shè)計(jì)一個(gè)數(shù)學(xué)難題，使得單向計(jì)算很方便，而反向計(jì)算很難，如RSA使用因式分解的原理，兩個(gè)大質(zhì)數(shù)相乘很容易，但大數(shù)分解質(zhì)因子很難。
橢圓算法ECC其實(shí)就是利用乘法容易，而除法難的特點(diǎn)，設(shè)計(jì)一個(gè)乘法：K = k * G，其中大K是公鑰，小k是私鑰，G是生成點(diǎn)。由私鑰推導(dǎo)公鑰很容易，只需要k個(gè)G相加即可。但是從公鑰推導(dǎo)私鑰很難，也就是無(wú)法計(jì)算公鑰K除以G。
當(dāng)然這個(gè)加法不能用我們?nèi)粘５恼麛?shù)加減法，而是利用函數(shù) 所定義的一個(gè)特殊橢圓曲線上散列點(diǎn)的特性定義的加法。其中p是一個(gè)常數(shù)。不同p可以設(shè)計(jì)成不同的曲線，比特幣使用的p = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1，這個(gè)曲線的名稱(chēng)就叫secp256k1。這是一個(gè)非常大的數(shù)，曲線上的點(diǎn)是一個(gè)復(fù)雜散點(diǎn)，為了方便展示，這里用小很多的17階曲線表示加法的定義：
加法定義就是曲線上任意兩個(gè)點(diǎn)P1和P2，必有第三個(gè)點(diǎn)P3，是P1和P2連線的延長(zhǎng)線與曲線相交點(diǎn)的x軸映射的點(diǎn)，定義P1 P2=P3。通過(guò)數(shù)學(xué)算法可以證明這種點(diǎn)滿足加法乘法交換律：
▲A B C = A (B C)
▲A*(B C) = A*B A*C
暫且不進(jìn)行證明贅述，需要說(shuō)明的是這里為了完善計(jì)算還定義了無(wú)窮遠(yuǎn)點(diǎn)O(相當(dāng)于0)，滿足：P1 O = P1。（思考一下：如果P1 P2 = O，那么P1 = -P2了嗎？）
ECC加密過(guò)程：
▲K = k * G， 大K是公鑰，小k是私鑰；
▲把明文編碼成曲線上的點(diǎn)M；
▲生成一個(gè)隨機(jī)數(shù)r；
▲計(jì)算密文C1=M r*K, C2 = r*G，其中大K是公鑰；
▲對(duì)方收到密文后，可以計(jì)算C1 - kC2 = M，其中小k是私鑰；
▲攻擊者得到C1、 C2，公鑰K以及基點(diǎn)G，沒(méi)有私鑰是無(wú)法計(jì)算出M的。
ECC算法用很短的密鑰就能達(dá)到RSA2048的安全強(qiáng)度，而且計(jì)算速度有數(shù)量級(jí)的提高，所以目前應(yīng)用很普遍，國(guó)密中的SM2就是基于ECC算法的。
【實(shí)驗(yàn)班-如何使用算法】
這些算法感覺(jué)還是挺復(fù)雜的，我們小白能用起來(lái)么？
不要只說(shuō)不練，我們就實(shí)際操刀體驗(yàn)一下。
其實(shí)是別人把框架和算法都寫(xiě)好的啦，比如JAVA，在JDK里面就集成了Java密碼學(xué)框架 (Java Cryptography Architecture - JCA)，直接拿來(lái)用就行了，其他如C#，C 甚至JavaScript都有類(lèi)似的。
<對(duì)稱(chēng)加密>
把大象關(guān)進(jìn)冰箱需要三步，把明文轉(zhuǎn)成密文也只需要四步：
▲生成一個(gè)密鑰（如果已經(jīng)有密鑰，這步也省了），如：
▲取一個(gè)加密器:
▲初始化成加密模式:
▲加密:
怎樣把密文解密呢？初始化成解密模式就可以了。
SM4是國(guó)密4算法，初始化的時(shí)候斜杠后面的ECB、PKCS7…是什么？那是因?yàn)镾M4是分組算法，在加密的時(shí)候會(huì)把明文先分成固定長(zhǎng)度段，那就需要定義分組的模式和填充模式，只要加密解密用同樣的模式就行了。當(dāng)然不同的分組和填充模式各自有特點(diǎn)，那超出本文范圍了，有興趣的同學(xué)自學(xué)吧。
<非對(duì)稱(chēng)加密>
復(fù)習(xí)一下非對(duì)稱(chēng)加密和對(duì)稱(chēng)加密有什么區(qū)別??？密鑰分成公私鑰對(duì)。
所以和對(duì)稱(chēng)加密區(qū)別只是：
▲在生成密鑰的時(shí)候是一對(duì)，叫KeyPair。
▲加密的時(shí)候用一個(gè)如公鑰，解密用另一個(gè)。
<摘要算法>
和加密提供了Cipher幫助類(lèi)一樣，HASH算法Java提供了MessageDigest幫助類(lèi)，只需要調(diào)用getInstance就可以獲取一個(gè)實(shí)例：
其參數(shù)是HASH算法，如SHA-256, SM3, MD5等。
調(diào)用update方法設(shè)置內(nèi)容，然后調(diào)用digest就拿到HASH了。
<數(shù)字簽名>
簽名:
驗(yàn)簽:
又比大象多一步。
<內(nèi)參必讀>
有幾個(gè)要點(diǎn)在實(shí)際使用過(guò)程中必須要注意。
▲JDK自帶的JCE實(shí)現(xiàn)算法不全
這里有兩個(gè)原因：
(1)國(guó)家安全出口保護(hù)規(guī)定（美國(guó)）
根據(jù)美國(guó)安全出口規(guī)定，不能對(duì)某些國(guó)家出口RSA2048、AES256等以上安全算法。解決辦法是到JDK的下載站上下載Java Cryptography Extension (JCE) Unlimited Strength Jurisdiction Policy，解壓縮到JRE的lib/security下即可。
(2)國(guó)密和擴(kuò)展算法缺失
免費(fèi)提供的不能強(qiáng)求，不過(guò)還是有很多開(kāi)源和商用的加密組件，這里推薦使用Bouncy Castle，雖然不是最快的，但是完全開(kāi)源，支持C#, C , Java多種語(yǔ)言。
把Bouncy Castle集成到JRE有兩種方法，一種是修改JRE的java.security增加一個(gè)Provider，另一種直接在代碼初始化的時(shí)候調(diào)用Security.addProvider加進(jìn)去即可:
▲Android 使用Bouncy Castle注意
Bouncy Castle(BC)很強(qiáng)大，Google的android內(nèi)核也集成了。但是，由于安全要求，這個(gè)加密包是閹割過(guò)的，自己再集成BC又導(dǎo)致包沖突。
解決辦法是換個(gè)包名，到https://rtyley.github.io/spongycastle/可以獲取。
【提高班-隱私保護(hù)】
由于區(qū)塊鏈?zhǔn)窃诜峭耆湃蔚囊唤M參與人之間，通過(guò)算法解決信任問(wèn)題，之前講述的算法保證了數(shù)據(jù)不可篡改，只有自己才可以操作自己的數(shù)據(jù)，但是還欠缺一個(gè)很重要的課題 – 隱私。
隱私和不可篡改其實(shí)有些相互矛盾，要實(shí)現(xiàn)不可篡改，就得讓其他人來(lái)驗(yàn)證數(shù)據(jù)，比如公有鏈?zhǔn)侨W(wǎng)用戶都來(lái)驗(yàn)證；但是隱私又想只有授權(quán)的人才可以驗(yàn)證，甚至希望其他人能驗(yàn)證但是不知道數(shù)據(jù)，比如盲簽名、同態(tài)算法等。本節(jié)講述在非安全環(huán)境下處理安全數(shù)據(jù)的一些方法。
<數(shù)字信封>
用非對(duì)稱(chēng)算法可以把機(jī)密信息安全傳給指定的接收人，通常我們會(huì)使用對(duì)方的公鑰進(jìn)行加密，同時(shí)使用自己的私鑰對(duì)數(shù)據(jù)進(jìn)行簽名。數(shù)字信封提供了一個(gè)更方便強(qiáng)大的方法，使得信息只有特定的接收人才可以閱讀。
數(shù)字信封的功能類(lèi)似于普通信封，內(nèi)容被包起來(lái)，上面寫(xiě)了接收人，只有接收人才能拆信。
制作信封方法：
▲準(zhǔn)備一個(gè)生成器
▲添加接收人:
接收人可以是公鑰證書(shū)、普通公鑰或者密碼，可以有多。
▲制作信封
拆信封時(shí)，只要憑自己的公鑰找到自己的收件人信息，然后用持有的私鑰抽取內(nèi)容即可。
<組簽名和環(huán)簽名>
通常一個(gè)合同是以公司的名義進(jìn)行簽署的，例如公司A有三個(gè)合同經(jīng)辦人C1、C2、C3，均可以代表公司簽署合同。
這里有幾個(gè)要求：
▲所簽署的合同使用公司的公鑰可以驗(yàn)證確實(shí)是公司所簽署；
▲能夠進(jìn)一步確定合同經(jīng)辦人的身份；
▲經(jīng)辦人如離職被吊銷(xiāo)個(gè)人證書(shū)，不影響已有業(yè)務(wù)數(shù)據(jù)。
按照孫子定理，n個(gè)整數(shù)(公鑰)的同余方程組是有唯一解的，那么理論上根據(jù)組員公鑰集合{K1, K2, ..., Kn}選擇一組模M，可以求解x做組因子, 實(shí)現(xiàn)組員使用自己的私鑰ki和x可以對(duì)密文進(jìn)行解密 D(ki, x, C) = P。
類(lèi)似的原理可以應(yīng)用到數(shù)字簽名，實(shí)現(xiàn)：
▲群組簽名：機(jī)構(gòu)使用群組公鑰做自己的公鑰，可以通過(guò)驗(yàn)證簽名確定簽名屬于指定的機(jī)構(gòu)，而機(jī)構(gòu)管理員可以進(jìn)一步確定是那個(gè)成員簽署的。
▲環(huán)簽名：對(duì)于匿名要求，可以確定簽名是來(lái)自于一個(gè)群組的成員，但是無(wú)法確定是具體哪個(gè)成員簽署的。
<同態(tài)加密>
私密數(shù)據(jù)的處理通常是在組內(nèi)進(jìn)行，但是使用區(qū)塊鏈技術(shù)后，私密數(shù)據(jù)的處理可能會(huì)需要在無(wú)中心的節(jié)點(diǎn)上，甚至是第三方的節(jié)點(diǎn)進(jìn)行處理。這時(shí)就需要把要處理的數(shù)據(jù)在保密狀態(tài)下進(jìn)行。
例如股東A有100股，賣(mài)出60股剩余40股，這是一個(gè)減法操作。如果這個(gè)過(guò)程在智能合約中，智能合約又運(yùn)行在多個(gè)非完全信任的節(jié)點(diǎn)上，如果需要將真實(shí)股份數(shù)量加密，則需要實(shí)現(xiàn)一個(gè)減法同態(tài)：
C3 = C1 - C2, 其中C1,2,3均是密文，執(zhí)行減法的節(jié)點(diǎn)無(wú)法知道實(shí)際余額和發(fā)生額，但是股東A可以使用自己的密鑰解密 D(C3) = P = P1-P2, 其中P表示明文，D表示界面算法。
目前已實(shí)現(xiàn)的算法主要有：
▲Paillier方案
概率公鑰加密，基于復(fù)合剩余類(lèi)的困難問(wèn)題。滿足加法和數(shù)乘同態(tài)。
▲B(niǎo)GV和RLWE方案
BGV和RLWE都是基于LWE(Learning With Errors)難題的同態(tài)算法, 支持加法、乘法、減法和移位運(yùn)算的同態(tài)。源碼在github上開(kāi)源- HElib。
▲基于其他數(shù)學(xué)難題的方案
如基于決斷問(wèn)題等。
全同態(tài)算法雖然實(shí)現(xiàn)已經(jīng)取得很大進(jìn)展，但其實(shí)現(xiàn)效率還遠(yuǎn)未達(dá)到實(shí)用要求。
全同態(tài)算法是密碼學(xué)的圣杯，等待您來(lái)奪取！
原文作者：恒生技術(shù)之眼
聯(lián)系客服
