与区块链相关的密码学

HeavyIndustry 2019-02-19


HASH 算法 (哈希函数 / 散列函数 / 杂凑函数)

Hash 能将明文映射为较短固定长度的二进制 hash 值(原消息的“散列值 [Hash Value]”或“消息摘要 [Message Digest]”),并且不同的明文很难映射为相同的 hash 值。一个优秀的 hash 算法能够实现:

  • 正向快速:给定明文和 hash 算法,在有限时间和有限资源内能计算出 hash 值。
  • 逆向困难:给定 hash 值,在有限时间内很难逆推出明文。
  • 输入敏感:原始输入信息修改一点信息,产生的 hash 值看起来应该有很大不同。
  • 冲突避免(抗碰撞性):很难找到两端内容不同的明文,使得其 hash 值一致。

Hash 函数有两类:消息摘要算法(MD5)和安全散列算法(SHA)。

目前流行的 hash 算法包括 MD4(不够安全)、MD5(比 MD4 安全但慢,生成128位消息摘要)、SHA1(模仿MD5)、SHA2(SHA-224、SHA-256、SHA-384、SHA-512,类似于SHA-1算法)。

一般的 hash 算法都是算力敏感型,计算资源是瓶颈,主频越高的 CPU 进行 hash 的速度也越快。也有一些非算力敏感型的 hash 算法如 scrypt,需要大量内存资源,节点不能通过简单的增加更多CPU 来获得 hash 性能的提升。

Hash 函数在数字签名和消息完整性检测等方面有着广泛的应用。

SHA-1 :任意长度生成 160 位消息摘要。5个参与运算的32位寄存器,消息分组和填充方式与MD5相同。

SHA-2 :输出长度可取224位、256位、384位、512位,分别对应SHA-224、SHA-256、SHA-384、SHA-512。还包含SHA-512/224、SHA-512/256。

SHA-3 :Keccak算法,采用 Sponge 结构,分为吸收和榨取两阶段。

RIPEMD160:RACE原始完整性校验消息摘要 ,旨在替代128位Hash函数MD4、 MD5和RIPEMD。RIPEMD家族包括RIPEMD-128、RIPEMD-160、 RIPEMD-256、 RIPEMD-320。

加密算法

公钥私钥体系:加解密算法、公钥、私钥。

加密过程中,通过加密算法和公钥,对明文进行加密,获得密文。

解密过程中,通过解密算法和私钥,对密文进行解密,获得明文。

根据公钥和私钥是否相同,算法可以分为对称加密和非对称加密。两种模式互补,或者组合使用。

对称加密:公钥和私钥相同。代表算法包括 DES、3DES、AES、IDEA。适用于大量数据的加解密,不能用于签名场景。

优点是加解密速度快,空间占用小,保密强度高。

缺点是参与多方都需要持有密钥,一旦泄漏则安全性被破坏,另外如何分发密钥也是个问题。

非对称加密:公钥和私钥不同,公钥一般是公开可获取的,私钥一般是个人持有不能被他人获取。代表算法包括:RSA、EIGamal、椭圆曲线系列算法ECC。一般适用于签名场景或密钥协商,不适于大量数据的加解密。

优点是公私钥分开,容易管理,并且容易完成密钥分发。

缺点是加解密速度慢。

组合机制:先用计算复杂度高的非对称加密协商一个临时的对称加密密钥(会话密钥),然后双方再通过对称加密对传递的大量数据进行加解密处理。

椭圆曲线方程:主流的公钥加密技术,

公钥私钥的产生算法


数字摘要

对数字内容进行 hash 运算,获取唯一的摘要值来指代原始数字内容,用以解决确保内容没被篡改过的问题。

数字签名和数字证书

数字签名:类似在纸质合同上签名确认合同内容,数字签名用于证实某数字内容的完整性和来源。

A 发给 B 一个文件。 A 先对文件进行摘要,然后用自己的私钥进行加密,将文件和加密串都发给 B。 B 收到后文件和加密串,用 A 的公钥来解密加密串,得到原始的数字摘要,跟对文件进行摘要后的结果进行比对。如果一致,说明该文件确实是 A 发过来的,并且文件内容没有被修改过。

多重签名:

n 个持有人中,收集到至少 m 个的签名,即认为合法,这种签名被称为多重签名。其中, n 是提供的公钥个数, m 是需要匹配公钥的最少签名个数。

群签名:

环签名:

属于一种简化的群签名。签名者首先选定一个临时的签名者集合,集合中包括签名者自身。然后签名者利用自己的私钥和签名集合中其他人的公钥就可以独立的产生签名,而无需他人的帮助。签名者集合中的其他成员可能并不知道自己被包含在其中。

数字证书:

数字证书用来证明某个公钥是谁的。对于数字签名应用来说,很重要的一点就是公钥的分发。一旦公钥被人替换,则整个安全体系将被破坏掉。

怎么确保一个公钥确实是某个人的原始公钥?这就需要数字证书机制。数字证书由证书认证机构 CA 来签发。

数字证书内容可能包括版本、序列号、签名算法类型、签发者信息、有效期、被签发人、签发的公开密钥、CA数字签名、其他信息等等。

其中,最重要的包括签发的公开密钥、CA 数字签名两个信息。因此,只要通过这个证书就能证明某个公钥匙合法的,因为带有 CA 的数字签名。

更进一步,怎么证明 CA 的签名合法不合法呢?

类似的,CA 的数字签名合法不合法也是通过CA 的证书来证明的。主流操作系统和浏览器里会提前预置一些 CA 的合法证书,然后所有基于其认证的签名都会自然被认为合法。

ECDSA 数字签名

Schnorr 数字签名

PKI (Public Key Infrastructure)体系

PKI 是综合多重密码学手段来实现安全可靠传递消息和身份的一个框架和规范。一般情况下包括:

CA(Certification Authority):负责证书的颁发和作废,接受来自 RA 的请求;

RA(Registration Authority):对用户身份进行验证,校验数据合法性,负责登记,审核通过就给发 CA;

证书数据库:存放证书,一般采用 LDAP 目录服务,标准格式采用X.500 序列。

CA 是最核心组件,主要完成对公钥的管理。 用户基于 PKI 体系要申请一个证书,一般可由 CA 来生成证书和私钥,也可以自己生成公钥和私钥,然后由 CA 来对公钥进行签发。

Merkle 树(哈希树)

 
与区块链相关的密码学

一种二叉树,由一个根节点、一组中间节点和一组叶节点组成。可推广成多叉树。

最下面的叶节点包含存储数据或其 hash 值,每个中间节点是它的两个孩子节点内容的 hash 值,根节点也是由它的两个子节点内容的 hash 值组成。

特点:底层数据的任何变动,都会传递到其父节点,一直到树根。

应用场景:

  • 快速比较大量数据:当两个Merkle 树 root 相同时,则意味着所代表的数据必然相同。
  • 快速定位修改:若 D1 被修改,会影响到 N1、N4 和 root。因此沿着 root->N4->N1,可以快速定位到改变的D1。
  • 零知识证明:如何证明某个数据(D0...D3)中包含给定内容 D0, 构造一个 Merkle 树,公布 N0,N1,N4,root,D0 拥有者可以很容易检测 D0 存在,但不知道其他内容。


 同态加密(Homomorphic Encryption)

 一种特殊的加密方法,允许对密文进行处理得到仍然是加密的结果,即对密文直接进行处理,跟对明文进行处理再加密,得到相同的结果。

代数上为同态性。包含加法同态(Paillier、Benaloh算法)、乘法同态(RSA、ElGamal算法)、减法同态和除法同态。

同时满足加法同态和乘法同态,则意味着代数同态(全同态)。满足四种同态则位算数同态。

云上适用的同态加密技术,使得用户可以将隐私信息直接放到第三方云上处理,但已知的同态加密技术需要消耗大量的计算时间,还远达不到实用的水平。

函数加密

同态加密保护的是数据本身,而函数加密保护的是处理函数本身,即让第三方看不到处理过程的前提下,对数据进行处理。

该问题已被证明是不存在对多个通用函数的任意多 key 的方案,目前仅能做到对某个特定函数的一个 key 的方案。

相关推荐