分享 · 2019-12-28 0

Substrate背后的密码学

Substrate中的密码学算法一览

首先我们快速的预览一下Substrate中提供的几种密码学算法：
哈希函数：
  • sha2
  • keccak
  • blake2
  • xxhash
椭圆曲线密码：
  • ed25519
  • sr255519
  • secp256k1
地址格式：
  • SS58
这些密码学原语的定义在代码中都有定义，可以参考链接：
https://github.com/paritytech/substrate/tree/master/primitives/core/src
文档中也有所描述，链接：
https://docs.rs/substrate-primitives/1.0.0/substrate_primitives/

哈希函数 (Hash function)

https://github.com/paritytech/substrate/blob/master/primitives/core/src/hashing.rs 
Substrate中有以下哈希函数可以选择：
  • sha2
    • sha2_256
  • keccak
    • keccak_256
  • blake2
    • blake2_128
    • blake2_256
    • blake2_512
  • xxhash (twox_hash)
    • twox_64
    • twox_128
    • twox_256
 

 哈希函数介绍 

哈希函数的定义是： A function that input binary data（message） and output hash value. 输入任意二进制数据（消息），生成哈希值的函数。
 
哈希函数也称为散列函数或者消息摘要函数（message digest function），消息也称为原像（pre-image），哈希值也称为散列值、消息摘要（message digest）或者指纹（fingerprint）。
 
Hash的原意是古代法语中的“斧子”，后来被形容为“剁碎的肉末”，估计是要的是用斧子一顿乱剁然后搅在一起的感觉吧。哈希函数实际上就是将消息剁碎，再混合成固定长度的哈希值。
 
 特点 
  • 任意长度消息计算出的哈希值都是固定长度的
    • 拿SHA-256来说，无论是16字节的用户密码，5M的图像，512G的U盘中的所有文件，还是1TB的硬盘文件，计算出的哈希值永远是256比特（32字节）
  • 能够快速计算出哈希值
  • 消息不同哈希值也不同
  • 单向性
常见的哈希算法有 MD5，SHA-1，SHA-2，SHA-3。
 
目前不是所有的哈希函数都是安全的：
  • MD5不安全，不推荐使用。
  • SHA-1 2005年强抗碰撞性被王小云团队攻破，除了用于对过去生成的哈希值进行校验，不应该用于新的用途。
  • SHA-2（SHA-256，SHA-384，SHA-512）是安全的。
  • SHA-3（也叫Keccak [kɛtʃak]）是安全的。
 SHA-2（SHA-256，SHA-384，SHA-512）
SHA是Secure Hash Algorithm的缩写，SHA 家族包含了SHA -0到SHA -3。
SHA-2由NIST设计，2001年发布，是SHA-1的继任者，其中包含了6种哈希函数。 
             
实际上6种哈希函数都是由SHA-256和SHA-512衍生出来的，将SHA-256和SHA-512的的结果进行截断就得到了其它4种。
 
SHA-2的实现： 
https://github.com/RustCrypto/hashes Substrate中提供了 sha2_256。
SHA-3（Keccak）
SHA-3的全称是Secure Hash Algorithm – 3。
 
NIST（美国国家标准与技术研究院）通过公开竞争的方式来选拔SHA-3算法，整个选拔经历了5年的时间(11/2/2007 – 10/2/2012)，具体过程如下：
  • 2007年11月，开始公开征集
  • 2008年10月，征集到64个算法，其中51个进入到第一轮
  • 2009年7月，14个算法进入到第二轮
  • 2010年12月，5个算法进入到第三轮
           （https://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf ）
  • 2012年10月，Keccak算法被最终确定为SHA-3标准
Keccak的实现：
https://github.com/debris/tiny-keccak
Substrate中提供了 keccak_256。
Blake2b
Blake2b算法的网站可以参考：https://blake2.net/
 
介绍Blake2b算法之前，先介绍一下Blake2b的前身Blake。Blake的核心算法继承自ChaCha流加密算法（Daniel J. Bernstein发明），Blake于2010年12月被列入SHA-3的最终候选名单，最终没有被选中是因为和SHA-2算法的实现有点类似，NIST的目标是SHA-3尽量与SHA-2不同。
 
Blake2算法继承自Blake算法，于2012年12月21日正式对外公开。Blake2速度比 MD5，SHA-1，SHA-2，SHA-3 更快（64位x64和ARM的CPU架构上），安全性优于SHA-2，与SHA-3旗鼓相当。
 
下面的图表是各个哈希算法的速度测试对比，可以看出Blake2b算法的速度是最快的。
             
上面的哈希函数速度测试是在Skylake Intel CPU上做的测试，使用的是单核CPU。如果使用多核CPU，BLAKE2的优势会更加明显。
 
BLAKE2 有两个主要版本，BLAKE2b（BLAKE2）和 BLAKE2s，通常所说的BLAKE2默认指BLAKE2b。BLAKE2b 为 64 位 CPU（包括 ARM Neon）优化，可以生成1-64字节的哈希值；BLAKE2s 为 8-32 位 CPU 优化，可以生成1-32 字节的哈希值。
 
Blake2的实现
https://github.com/cesarb/blake2-rfc
Substrate中提供了：
  •  blake2_128
  •  blake2_256
  •  blake2_512
xxHash 
xxHash的全称是Extremely fast hash algorithm，特点是速度很快。
下表是xxHash和其它哈希算法的速度测试对比，基于2核 Duo @3GHz CPU，Windows 7的32位机器做的测试，可以看出xxHash确实非常快。
             
xxHash的实现：
https://libraries.io/cargo/twox-hash
https://github.com/Cyan4973/xxHash
Substrate中提供了：
  • twox_64
  • twox_128
  • twox_256

秘钥对和签名算法

秘钥对和签名算法背后的核心是椭圆曲线密码学，椭圆曲线密码学（Elliptic Curve Cryptography, ECC）包含三个方面的内容：
  • 基于椭圆曲线的公钥密码（也就是秘钥对）
  • 基于椭圆曲线的数字签名（ECDSA，Elliptic Curve Digital Signature Algorithm）
  • 基于椭圆曲线的秘钥交换
 
目前Substrate提供了三种椭圆曲线密码：
  • ed25519
  • sr255519
  • secp256k1

椭圆曲线基础 

椭圆曲线是指由数学方程定义的一系列点。比如：
y² = x³ + ax + b 
上面的方程叫做Weierstrass/Weierstraß方程。
 
             
通过变换不同的a，b数值得到不同的曲线形状，所以我们可以说椭圆曲线是一个家族，有一系列不同的椭圆曲线。
             
椭圆曲线上的一些数学运算和我们常规意义上的数学运算很不一样，比如“椭圆曲线上的加法运算“是这样定义的（参照上图）：
P + Q+ R = 0 
从几何图形上来说，其中P，Q是曲线上的两个点，R是经过P，Q的直线与椭圆曲线相交的第三个点，-R就是R经过翻转得到的点。从这个加法的定义中我们发现，曲线上两个点相加后可以得到第三个点，并且仍然在这个曲线上。
              
当P = Q时，经过P和Q的直线是一条与曲线相切的直线。这个时候我们就可以定义标量乘法了，P + P = 2P，如果要计算nP实际上就相当于将P相加n次：        
      
实际上我们说的椭圆曲线是由这些离散的nP点组成的，从1P到nP，椭圆曲线既不是椭圆，也不是曲线，只是一群离散的点，基于这些点才可以生成椭圆曲线密码学需要的点。
              
这里我们需要知道的是，已知曲线上的点P，求nP是比较容易的，然而已知P和nP，要是想求n的话，是非常非常困难的，这个性质被成为“椭圆曲线上的离散对数问题”。
这个时候就可以介绍椭圆曲线的公钥密码了，上面公式中的n可以作为私钥，P是椭圆曲线上选定好的一个点，而nP就是公钥。
从上图我们可以直观的看到，如果椭圆曲线的形状变了，那得到的公钥的结果也会不一样。下面我们就介绍一下不同的椭圆曲线。

几种不同的椭圆曲线 

先看一个上面提到过的方程，叫做Weierstrass/Weierstraß方程：
y² = x³ + ax + b
 
这个方程是Weierstrass/Weierstraß方程的简化版，称为”short Weierstraß format”。
实际上，所有的曲线都可以由Weierstrass/Weierstraß方程来表达，不同的曲线只是基于这个方程进行了变量的变换。
 
Koblitz曲线
Koblitz曲线的方程为：
y² = x³ + b
 
基于Koblitz曲线，当b = 0时就有了secp256k1曲线：
y² = x³ + 7
 
secp256k1曲线是2000年由SECG（Standards for Efficient Cryptography Group，高效密码组标准）提出的。secp256k1名字的含义：
  • sec：SECG标准
  • p：曲线坐标在素数域
  • 256：素数是256位长
  • k ：是一种 Koblitz 曲线
  • 1：是第一个标准中该类型的曲线
 
蒙哥马利曲线
1987年，Peter L. Montgomery提出了蒙哥马利曲线（Montgomery curve），曲线的方程为：
by² = x³ + ax² + x
 
之后，Daniel J. Bernstein提出了名为Curve25519的蒙哥马利曲线，方程是这样的：
y² = x³ + 486662x² + x
 
Curve25519由著名的密码学家 Daniel J. Bernstein 于 2005年公布，但实际上直到2013年才流行起来，在众多椭圆曲线家族中，由NIST公布的Curve P曲线（使用Weierstrass曲线方程）最为常用。
 
2013年斯诺登曝光“棱镜计划”，指出美国国家安全局（National Security Agency，NSA）在NIST标准中使用的Dual_EC_DRBG算法放置了后门，导致人们对于NIST以及其推出的Curve P（例如secp256r1 被称为 P-256）系列曲线的安全性开始产生了质疑，之后Curve25519开始获得广泛的关注。
 
Curve25519最开始被设计用来进行ECDH（Elliptic Curve Diffie-Hellman，基于椭圆曲线的DH密钥交换）。是目前最快的椭圆曲线密码之一，并且没有专利限制。
 
最开始Curve25519是被命名为DH（Diffie-Hellman密钥交换）函数的，后来为了区分DH函数和DH函数所使用的椭圆曲线，将DH函数命名为X25519，将其所用的椭圆曲线命名为Curve25519。
 
Edwards曲线
还有一种曲线叫做Edwards曲线（爱德华兹曲线），方程式为：
x² + y² = 1 + dx²y²
 
基于Edwards曲线，发明了Twisted Edwards曲线（扭曲爱德华兹曲线，也称为edwards25519 ），Twisted Edwards曲线是Edwards曲线的一般化形式，方程为：
ax² + y² = 1 + dx²y²
 
有意思的是，这几个曲线中是有等价关系的。通过一定的映射，蒙哥马利曲线可以转化为Weierstrass曲线。蒙哥马利曲线和Twisted Edwards曲线具有双有理等价关系，通过双有理映射也可以相互转化。
 

使用椭圆曲线进行签名 

了解了哈希函数和椭圆曲线，我们来说说椭圆曲线的签名算法。
 
其实所有的签名都是“先哈希再签名(hash-then-sign)”，也就是先对消息进行哈希运算得到一个固定长度的哈希值，然后对这个哈希值利用签名算法进行签名。当使用椭圆曲线的签名算法的时候，利用了椭圆曲线上的离散对数问题，使得签名无法被伪造，并且可以很容易的验证签名的有效性，知道是不是给定的公钥签名的。
 
我们看一下签名的过程。
 
进行签名时，首先通过私钥a执行公私钥生成算法，得到两个值：
  • 公钥A
  • 随机数k
 
然后进行签名算法的计算：
  1. 计算随机数 r = H(k, M)。其中H是哈希函数，k是上面得到的随机数，M是消息。
  2. 计算随机点 R = rG。其中G是椭圆曲线上被选定的一个点，每个椭圆曲线都有这个预设值。通过前面的知识我们可以知道R也在椭圆曲线上。
  3. 计算签名 s = (r + H(R, A, M) x) mod p。其中p是一个很大的质数，mod p 表示前面得到的值对p进行模的运算。得到x的过程是，先对私钥a进行哈希运算，然后取得到的哈希值的前一半，即为x。
 
最终得到的 (R, s) 就是数字签名。
 
验证签名时，使用公开的三个参数和一个公式就可以验证了。三个参数包括：
  • 公钥A
  • 签名 (R, s)
  • 消息M
然后验证公式是否成立： sG = R + H(R, A, M) A
 

Ed25519签名算法

Ed25519的目标是在保证安全的前提下，提升性能。
 
和ECDSA 类似，EdDSA（Edwards-Curve Digital Signature Algorithm，爱德华兹曲线数字签名算法）也属于椭圆曲线密码；和ECDSA不同的是，EdDSA采用了不同的椭圆曲线和签名算法。
 
EdDSA 采用了Twisted Edwards曲线作为椭圆曲线，签名算法采用了Schnorr算法作为签名的生成和验证。
 
Ed25519是一种EdDSA的实现 ，由 Daniel J. Bernstein 等人设计，采用的曲线参数完全公开，并说明了参数选取的意义，保证曲线中并未内置后门。
 
Ed25519实现：
https://github.com/dalek-cryptography/ed25519-dalek
 

sr25519签名算法 

Substrate中还使用了一个Ed25519的衍生版本，叫做sr25519，也称为Schnorrkel/Ristretto x25519，解决了使用Ed25519实现复杂协议的安全问题。
这里简单解释一下这个安全问题。
 
我们需要知道的是，定义一个ECC，需要6个参数：
（p, a, b, G, n, h)
 
其中的h叫做余因子(cofactor)，余因子的值最好为1，要不然会产生安全问题，比如其中之一的可以导致加密货币被无限增发，Monero在2017年就发现并修复了这样一个问题，好在当时没有产生损失。
 
secp256k1和secp256r1的余因子是1，不存在这些安全问题；而Edwards曲线的余因子都大于4，其中Ed25519使用的曲线的余因子是8，都存在这些安全问题。
 
这是椭圆曲线本身的问题，如果要避免这个问题，就需要在上层使用这个曲线的地方解决这个问题，Mike Hamburg的 Decaf 论文 提供了解决这个问题的方案，并且只有非常少量的性能损耗。
 
简单的说，就是通过数学方法，将余因子从4转换成1。然而Decaf方案只解决了余因子为4的曲线问题，并没有解决余因子为8的曲线的问题。
 
为了解决这个问题， Ristretto Group 将Decaf 论文中的方法进行了改进，增加了对余因子为8的曲线的支持。
 
Web3基金会在 Schnorrkel 这个库中也实现了这项改进，称其为Schnorrkel/Ristretto x25519，简称sr25519，并将其用于Substrate。
 
这个库还支持其他的协议，例如分层确定性密钥派生（Hierarchical Deterministic Key Derivation，HDKD）, 多签（multi-signatures，MuSig）, VRF (verifiable random function，可验证随机函数)。
 
Substrate的账户对于ed25519和sr25519这两种签名都是支持的。对于简单的签名来讲，两种协议有用相同的安全性。
 
ed25519可以用来支持硬件安全模块（Hardware security module，HSM）以及需要外部秘钥管理的地方。而sr25519提供了更多的区块链友好的功能，例如分层确定性密钥派生和多签，这些复杂的协议使用sr25519来实现会更加安全。
 
更多的对于这部分的内容，可以参考波卡中的秘钥信息，链接
https://wiki.polkadot.network/docs/en/learn-keys 。
 
这里还需要提到的一个实现是bip39，增加了对sr25519的支持： 
https://github.com/paritytech/substrate-bip39

secp256k1

因为sr25519比较新，很多硬件钱包不支持，Substrate引入了硬件支持更广泛的secp256k1曲线，并已于2019年10月上线Kusama。
 
secp256k1是在Bitcoin和Ethereum上使用的椭圆曲线，大家应该相对熟悉，这里不对secp256k1做过多介绍。
 
secp256k1实现：
https://github.com/paritytech/libsecp256k1 包含的功能：
  • 从私钥生成公钥
  • 给消息签名
  • 验证签名
  • 从签名消息中恢复出公钥
  • 秘密的分享（Shared secrets，不确定是啥东西）

地址格式

Substrate上使用的地址格式叫做SS58，是专门设计给基于Substrate开发的链的。
基本的格式:
base58encode ( concat ( <address-type>, <address>, <checksum> ) )
 
SS58是基于比特币中使用的Base58Check地址格式开发的，设计目标是可以通过账户地址识别出不同的Substrate链。使用的base58encode编码函数和比特币中使用的编码函数是一样的，不同的地方，SS58的前缀是地址类型，校验和使用的是blake2-256哈希函数。
 
目前支持的一些值以及含义:
  • 00000000b..00110000b (0..48): Account/address identifiers on networks:
  • 00000000b (0) Polkadot Live (SS58 checksum preimage)
  • 00000001b (1) Polkadot Live (AccountId checksum preimage)
  • 00000010b (2) Polkadot Canary (SS58 checksum preimage)
  • 00000011b (3) Polkadot Canary (AccountId checksum preimage)
  • 00010000b (16) Kulupu (SS58 checksum preimage)
  • 00010001b (17) Kulupu (Reserved)
  • 00010100b (20) Dothereum (SS58 checksum preimage)
  • 00010101b (21) Dothereum (AccountId checksum preimage)
  • 00101010b (42) Generic Substrate wildcard (SS58 checksum preimage)
  • 00101011b (43) Generic Substrate wildcard (AccountId checksum preimage)
  • 00110000b..01000000b (48..64): Bare public keys of primary cryptography
  • 00110000b (48) Schnorr_Ristretto 25519 (“S_R 25519”) key
  • 00110001b (49) Edwards Ed25519 key
  • 00110010b (50) ECDSA SECP256k1 key
  • 01000000b..11111111b (64-255) Reserved for future address format extensions.
 
下面是我画的一个生成SS58的流程图，应该可以比较清楚的看到SS58的生成过程。            

总结

本文介绍了Substrate中用到的密码学知识，包括哈希函数，椭圆曲线密码，地址格式这几个方面，试图通过尽量简洁的语言将这些知识讲清楚，如果有问题，欢迎大家和我交流。

参考资料

blake:
  • https://blake2.net/
  • https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2
  • https://zh.wikipedia.org/wiki/BLAKE
  • https://zhuanlan.zhihu.com/p/28563960
sha:
  • https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F
  • https://en.wikipedia.org/wiki/SHA-2
  • https://zh.wikipedia.org/wiki/SHA-2
  • https://csrc.nist.gov/projects/hash-functions/sha-3-project
polkadot/substrate:
  • https://wiki.polkadot.network/docs/en/learn-cryptography
  • https://zhuanlan.zhihu.com/p/84322255
  • https://research.web3.foundation/en/latest/polkadot/keys/
  • https://github.com/paritytech/substrate/wiki/External-Address-Format-(SS58)
椭圆曲线：
  • https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
  • http://suntus.github.io/2019/05/31/ECC%E7%AE%97%E6%B3%95/
  • https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3
ed25519:
  • https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/
  • https://en.wikipedia.org/wiki/Curve25519
  • https://en.wikipedia.org/wiki/Twisted_Edwards_curve
  • https://webencrypt.org/twistededwardscurve/
  • http://netinfo-security.org/article/2017/1671-1122-0-9-122.html
  • https://en.wikipedia.org/wiki/EdDSA#Ed25519
  • https://zhuanlan.zhihu.com/p/44243140
  • https://zhuanlan.zhihu.com/p/76783431
  • https://tiannian.me/2018/12/28/cryptography/ed25519/
  • https://www.getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html
  • https://tools.ietf.org/html/rfc7748
  • decaf： https://eprint.iacr.org/2015/673.pdf
Ristretto：
  • https://ristretto.group/why_ristretto.html
  • https://doc.dalek.rs/curve25519_dalek/ristretto/index.html
secp256k1:
  • https://www.oreilly.com/library/view/mastering-bitcoin-2nd/9781491954379/ch04.html
  • https://medium.com/polkadot-network/kusama-cc-2-prepos-a0ce785bb629
  • https://www.johndcook.com/blog/2018/08/21/a-tale-of-two-elliptic-curves/
  • https://www.johndcook.com/blog/2018/08/14/bitcoin-elliptic-curves/
  • https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%AF%86%E7%A0%81%E5%AD%A6
  • https://en.bitcoin.it/wiki/Secp256k1
  • https://www.ietf.org/rfc/rfc5480.txt
  • https://learnblockchain.cn/books/geth/part3/sign-and-valid.html
  • https://crypto.stackexchange.com/questions/58506/what-is-the-curve-type-of-secp256k1

 

本文首发于一块plus社区 https://mp.weixin.qq.com/s/Mrm9ZAmFXriOpalDqOLelQ

Harry

Rebase contributor

You may also like...

Leave a Reply