区块链的密码学基础
原文：shuwoom.com/?p=643
一、哈希算法
（1）概念
哈希算法又稱為哈希函數(shù)、散列算法、散列函數(shù)，它能從任何數(shù)據(jù)長(zhǎng)度生成一個(gè)固定長(zhǎng)度的消息摘要（如下圖）。對(duì)于某個(gè)特定的消息而言，這個(gè)消息摘要（或哈希值）可以看做是這個(gè)消息的指紋，且該消息是唯一表示。哈希函數(shù)是數(shù)字簽名和驗(yàn)證的核心部分。
（2）哈希算法的特性
- 單向性
哈希函數(shù)必須具有單向性，也就是說(shuō)給定一個(gè)輸入，通過(guò)哈希函數(shù)可以得到一個(gè)散列值，但是反過(guò)來(lái)，給定一個(gè)散列值，是無(wú)法獲得輸入的。換句話說(shuō)，就是給定一個(gè)散列值（指紋），我們不可能找到對(duì)應(yīng)的消息。 - 沖突避免
很難找到兩個(gè)不同的消息，使得產(chǎn)生的哈希值一致（發(fā)生沖突）。 - 輸入敏感
原始數(shù)據(jù)任何微小的變動(dòng)都會(huì)導(dǎo)致哈希值完全不一樣 - 正向快速
給定消息和哈希算法，在有限時(shí)間和有效資源內(nèi)計(jì)算出哈希值
（3）哈希碰撞
哈希碰撞也就是說(shuō)存在不同的消息（輸入），使得哈希函數(shù)的輸出，也就是散列值一樣，這種概率非常非常低。以下面的md5為例，兩個(gè)輸入有細(xì)微差別，但是哈希值是一樣的：
| 123456789101112131415 | # coding: utf-8import hashlib # 兩段HEX字節(jié)串，注意它們有細(xì)微差別a = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef") b = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef") # 輸出MD5，它們的結(jié)果一致print(hashlib.md5(a).hexdigest())print(hashlib.md5(b).hexdigest()) ### a和b輸出結(jié)果都為：cee9a457e790cf20d4bdaa6d69f01e41cee9a457e790cf20d4bdaa6d69f01e41 |
以CRC32為例，它的摘要長(zhǎng)度為32bit，也就是說(shuō)存在2^32種可能。如今互聯(lián)網(wǎng)頁(yè)面總數(shù)在2008年的時(shí)候就已經(jīng)超過(guò)1萬(wàn)億，如果采用CRC32的摘要，那么發(fā)生哈希碰撞的就很多。而MD5的摘要長(zhǎng)度為128bit，也就是有2^128種可能，但是目前已經(jīng)證明MD5算法是不安全的。同樣的SHA1算法(160bit)也被證明是不安全的，推薦使用SHA256算法才比較安全。
（4）常見(jiàn)哈希算法
目前比較流行的哈希算法有MD5、SHA-1和SHA-2
- MD4
MD4已經(jīng)被證明時(shí)不夠安全的，不推薦使用
- MD5
MD5是MD4的改進(jìn)版本，輸出是128bit。同樣，MD5也被證明了不具備強(qiáng)抗碰撞性，也是不夠安全的
- SHA-1
SHA是一個(gè)哈希函數(shù)族，SHA-1算法的哈希值長(zhǎng)度為160bit，抗窮舉性比MD5和MD4更好。但是SHA-1已經(jīng)被證明不具備“強(qiáng)抗碰撞性”（谷歌已經(jīng)攻破SHA-1），
SHA-2
SHA-224、SHA-256、SHA-384，和 SHA-512 算法統(tǒng)稱為SHA-2，算法原理跟SHA-1類似。
總結(jié)來(lái)說(shuō)，MD5和SHA-1已經(jīng)不夠安全，推薦至少使用SHA-256算法。
（5）應(yīng)用
哈希算法的應(yīng)用主要體現(xiàn)在以下3個(gè)方面：
- 文件校驗(yàn)
- 數(shù)字簽名
- 鑒權(quán)協(xié)議（安全通信）
二、非對(duì)稱加密技術(shù)
（1）概念
非對(duì)稱加密算法也稱為公鑰加密算法，其分為3個(gè)部分，分別是：公鑰、私鑰和加密解密算法。
非對(duì)稱加密往往需要密碼學(xué)安全偽隨機(jī)數(shù)生成器來(lái)產(chǎn)生一對(duì)秘鑰（公鑰和私鑰），這兩者是成對(duì)的，公鑰是可以公開(kāi)的，而私鑰則是用戶自己保留。用私鑰加密的數(shù)據(jù)只有公鑰才可以解密（反過(guò)來(lái)，用公鑰加密的數(shù)據(jù)，只有私鑰可以解密）。公鑰和私鑰之間的這種數(shù)學(xué)關(guān)系，使得私鑰可以用于生成特定消息的簽名。而這個(gè)簽名可以在不暴露私鑰的前提下通過(guò)公鑰進(jìn)行驗(yàn)證。
也就是說(shuō)我對(duì)一段消息用私鑰進(jìn)行簽名（也就是加密），然后把這個(gè)數(shù)據(jù)連同簽名和我的公鑰發(fā)送給對(duì)方，對(duì)方就可以通過(guò)公鑰對(duì)簽名進(jìn)行驗(yàn)證（解密）對(duì)比數(shù)據(jù)從而驗(yàn)證數(shù)據(jù)的有效性。
在比特幣系統(tǒng)中，公鑰生成的錢包地址用于接收比特幣，而私鑰則用于比特幣支付時(shí)的交易簽名。
在支付比特幣時(shí)，比特幣的所有者需要在交易中提交自己的公鑰和該交易的簽名。而比特幣網(wǎng)絡(luò)中所有節(jié)點(diǎn)可以通過(guò)所提交的公鑰和簽名進(jìn)行驗(yàn)證，從而確認(rèn)支付者對(duì)交易的比特幣的所有權(quán)。
（2）加密、解密過(guò)程
- 加密過(guò)程：通過(guò)加密算法和公鑰對(duì)明文進(jìn)行加密，得到密文
- 解密過(guò)程：通過(guò)解密算法（這里加密、解密算法要一樣）和秘鑰進(jìn)行解密，得到明文。
如下圖所示，加密過(guò)程是單向的，公鑰加密后的密文只能用對(duì)應(yīng)的私鑰解密。
（3）常見(jiàn)非對(duì)稱加密算法
- RSA
- ElGamal
- 背包算法
- Rabin（RSA的特例）
- 迪菲－赫爾曼密鑰交換協(xié)議中的公鑰加密算法
- 橢圓曲線加密算法（英語(yǔ)：Elliptic Curve Cryptography, ECC）
其中使用最廣泛的是RSA算法（由發(fā)明者Rivest、Shmir和Adleman姓氏首字母縮寫而來(lái)）是著名的公開(kāi)秘鑰加密算法，ElGamal是另一種常用的非對(duì)稱加密算法。
（4）應(yīng)用
非對(duì)稱加密算法的應(yīng)用非常廣泛，下面列舉常見(jiàn)的幾種
- 數(shù)字簽名
- 數(shù)字證書
- 加密通信HTTPS
（5）python編程實(shí)現(xiàn)
生成密鑰對(duì)
| 12345678 | def create_genisus_keypair(): # 第一個(gè)節(jié)點(diǎn)的密鑰對(duì) pubkey, privkey = rsa.newkeys(1024) with open('genisus_public.pem', 'w+') as f: f.write(pubkey.save_pkcs1().decode()) with open('genisus_private.pem', 'w+') as f: f.write(privkey.save_pkcs1().decode()) |
直接打開(kāi)genisus_public.pem和genisus_private.pem，我們可以看到一長(zhǎng)串的字符串。
| 12345678910111213141516171819202122 | genisus_public.pem：-----BEGIN RSA PUBLIC KEY-----MIGJAoGBAJIiGuUOlhKFQEHIr5YXa9uajM+sI5FEZ/8RJdR5EOC4Wo+9bZfyrvnuPRBtK7PJzUXHdXCaNohPzA5IuiEpkoELPyWfCozQF9FAgK2Gyf1rBeC7e2lUvuwIh5IXhRjC2Rom6wiJRWXn/W0/EezrXl8YlYmrRR1Boa9OB1RFJvJXAgMBAAE=-----END RSA PUBLIC KEY-----genisus_private.pem：-----BEGIN RSA PRIVATE KEY-----MIICYAIBAAKBgQCSIhrlDpYShUBByK+WF2vbmozPrCORRGf/ESXUeRDguFqPvW2X8q757j0QbSuzyc1Fx3VwmjaIT8wOSLohKZKBCz8lnwqM0BfRQICthsn9awXgu3tpVL7sCIeSF4UYwtkaJusIiUVl5/1tPxHs615fGJWJq0UdQaGvTgdURSbyVwIDAQABAoGAOiw7ep3A3iSPfOCQDXbLaANxNKa5DfYmVCKWZavALUUWQAxPmWJxh2rwgh6DfDHEdpe9R5MMTF0/xRvsQGQvZU2sNNhA2ebVOB4mMCPcURYWCbJXjT14IC7rfwPpYnkpiCHxP+HBS2xjMyf63vk7tKR/zCfzm9tsDAKqKuFUYPECRQCrQpiuYxp2ZnchszwR15q0HUpU8/HdCQlKdBK2fa4M2Y1xPqNjpOlQ2B8zCS3aOQ/9nhbVaRy0LqFDsUjPPJsTqbaSyQI9ANpwsv1MHkpYGlYSrCItFS1oRoD/foxByVdVORCtarA0z9xeAm8kEi9HcnZf2jsYvqHAeQsTtuPw0PvMHwJEXL0+csilztHj1zL452yKkNh/pQtIwPogttmuPHZIZxrz9gwGbHIkCixOkNN6qf5Wg281TDGUYpoRp9d75wUZsQcpH8kCPE0rvYBREO5w27UG2bslNDMbgLT4DkwcvbXVzNhAe82OitSufauoEaiUVDLPwDhakJZyehDYwSccH6ilPwJFAIhBzCQ61A2zfEJlgKeuX3OJGq1pywpnv+vFyqnDc4T6oEW9kfnrAI+6x4L4jyyHOWMNfkAPajtkQ+YwxZqUmKL8ixr0-----END RSA PRIVATE KEY----- |
加密、解密
| 12345678910111213141516 | # 導(dǎo)入密鑰with open('genisus_private.pem', 'r') as f: privkey = rsa.PrivateKey.load_pkcs1(f.read().encode()) with open('genisus_public.pem', 'r') as f: pubkey = rsa.PublicKey.load_pkcs1(f.read().encode()) # 明文message = 'hello world' # 公鑰加密crypto = rsa.encrypt(message.encode(), pubkey) # 私鑰解密message = rsa.decrypt(crypto, privkey).decode()print(message) |
三、數(shù)字簽名
（1）概念
數(shù)字簽名，就是只有信息的發(fā)送者才能產(chǎn)生的別人無(wú)法偽造的一段數(shù)字串，這段數(shù)字串同時(shí)也是對(duì)信息的發(fā)送者發(fā)送信息真實(shí)性的一個(gè)有效證明。它是進(jìn)行身份鑒別和網(wǎng)上安全交易的通用技術(shù)。
數(shù)字簽名應(yīng)用了前2節(jié)所說(shuō)到的非對(duì)稱加密技術(shù)（公鑰加密算法）和哈希算法。
（2）功能
- 數(shù)字簽名主要有三個(gè)作用：
- 保證信息傳輸?shù)耐暾?#xff08;完整性）
- 發(fā)送者身份認(rèn)證（鑒權(quán)）
- 防止交易中發(fā)生抵賴（不可抵賴性）
數(shù)字簽名是加密過(guò)程，數(shù)字簽名驗(yàn)證是解密過(guò)程。
（3）簽名和驗(yàn)證
- 發(fā)送者簽名過(guò)程
數(shù)字簽名是發(fā)送方首先通過(guò)一個(gè)哈希算法將獲取信息的一個(gè)摘要
然后通過(guò)秘鑰對(duì)這個(gè)摘要進(jìn)行簽名
最后把簽名和原文一起發(fā)送給接收者 - 接收者驗(yàn)證過(guò)程
數(shù)字簽名驗(yàn)證，接收者收到發(fā)送者發(fā)送的簽名和原文后，首先進(jìn)行分離
采用跟發(fā)送者一樣的哈希算法提取原文的摘要
然后用發(fā)送者的公鑰對(duì)簽名進(jìn)行解密獲得解密后的摘要
兩者對(duì)比，如果一致，則說(shuō)明收到的信息是完整的，在傳輸過(guò)程中沒(méi)有被修改過(guò)。
這里，讀者細(xì)心想會(huì)發(fā)現(xiàn)，如果一個(gè)黑客，將發(fā)送者的私鑰和接收者手上擁有的發(fā)送者的公鑰都替換成黑客自己的私鑰和公鑰。那這個(gè)時(shí)候接收者，在驗(yàn)證的時(shí)候是無(wú)法發(fā)現(xiàn)問(wèn)題的，因?yàn)楹灻玫乃借€是黑客的私鑰，驗(yàn)證用的公鑰也是黑客的公鑰，兩者是成對(duì)的。這就變成了對(duì)公鑰是否合法的驗(yàn)證，那么要解決這個(gè)問(wèn)題就涉及到數(shù)字證書的概念（如下圖所示）。這個(gè)讀者可以看我另外寫的一篇文章《數(shù)字證書是什么》，這里就不展開(kāi)講。
（4）應(yīng)用
數(shù)字簽名技術(shù)的應(yīng)用很廣泛，例如個(gè)人安全郵件證書、訪問(wèn)安全https站點(diǎn)、網(wǎng)上簽約、電子交易等。
（5）python編程實(shí)現(xiàn)
首先生成一對(duì)秘鑰（公鑰和私鑰）
| 1234567891011121314151617 | # 明文message = 'hello world' # 導(dǎo)入密鑰with open('genisus_private.pem', 'r') as f: privkey = rsa.PrivateKey.load_pkcs1(f.read().encode()) with open('genisus_public.pem', 'r') as f: pubkey = rsa.PublicKey.load_pkcs1(f.read().encode())# 私鑰簽名signature = rsa.sign(message.encode(), privkey, 'SHA-1') # 公鑰驗(yàn)證try: rsa.verify(message.encode(), signature, pubkey)except rsa.pkcs1.VerificationError: print 'invalid' |
關(guān)注我的微信公眾號(hào)（shuwoom的博客），每周定期推送文章：
參考：
https://www.jianshu.com/p/bf1d7eee28d0
https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
http://www.infoq.com/cn/news/2017/02/google-first-sha1-collision
http://blog.jobbole.com/106733/
https://baike.baidu.com/item/%E6%95%B0%E5%AD%97%E7%AD%BE%E5%90%8D
https://blog.csdn.net/u011630575/article/details/53241027
總結(jié)
- 上一篇： 如何学习Python数据爬虫？
- 下一篇： API设计中防重放攻击