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种哈希函数。 
       Substrate背后的密码学-Rebase      
实际上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个算法进入到第三轮
 Substrate背后的密码学-Rebase          (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算法的速度是最快的。
       Substrate背后的密码学-Rebase      
上面的哈希函数速度测试是在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确实非常快。
       Substrate背后的密码学-Rebase      
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ß方程。
 
       Substrate背后的密码学-Rebase      
通过变换不同的a,b数值得到不同的曲线形状,所以我们可以说椭圆曲线是一个家族,有一系列不同的椭圆曲线。
       Substrate背后的密码学-Rebase      
椭圆曲线上的一些数学运算和我们常规意义上的数学运算很不一样,比如“椭圆曲线上的加法运算“是这样定义的(参照上图):
P + Q+ R = 0 
从几何图形上来说,其中P,Q是曲线上的两个点,R是经过P,Q的直线与椭圆曲线相交的第三个点,-R就是R经过翻转得到的点。从这个加法的定义中我们发现,曲线上两个点相加后可以得到第三个点,并且仍然在这个曲线上。
       Substrate背后的密码学-Rebase       
当P = Q时,经过P和Q的直线是一条与曲线相切的直线。这个时候我们就可以定义标量乘法了,P + P = 2P,如果要计算nP实际上就相当于将P相加n次:        
Substrate背后的密码学-Rebase      
实际上我们说的椭圆曲线是由这些离散的nP点组成的,从1P到nP,椭圆曲线既不是椭圆,也不是曲线,只是一群离散的点,基于这些点才可以生成椭圆曲线密码学需要的点。
       Substrate背后的密码学-Rebase       
这里我们需要知道的是,已知曲线上的点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背后的密码学-Rebase       

总结

本文介绍了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