在深入学习区块链时,不可避免的需要了解密码学。区块链算是对密码学的一次整合运用,虽然并无太多创新的密码算法,但也值得深入了解一下。

之前对密码学并无太多的研究,因此买了两本简单的书学了学,在此做一个汇总。

密码,最初的目的是用于对信息加密,计算机领域的密码技术种类繁多。但随着密码学的运用,密码还被用于身份认证、防止否认等功能上。

最基本的,是信息加解密分为对称加密(Sysmmetric Cryptography)和非对称加密(Public-Key Cryptography,Asymmetric Cryptography),这两者的区别是是否使用了相同的密钥。

除了信息的加解密,还有用于确认数据完整性(Integrity)的单向散列(One-Way Hash Function)技术,又称密码检验(Cryptographic Checksum)、指纹 (Fingerprint)、消息摘要 (Message Digest)。

信息的加解密与信息的单向散列的区别是,对称与非对称加密是可以通过密钥解出明文,而单向散列是不可逆的。信息的加解密,密文必定是不定长的,而单向散列可以是定长的。

结合密码学的加解密技术和单向散列技术,又有了用于防止篡改的消息认证码技术,防止伪装的数字签名技术以及认证证书

针对不同的应用场景,可以总结出下表:

威胁 特征 相应技术
窃听 机密性 对称、非对称加密
篡改 完整性 单向散列、消息认证码、数字签名
伪装 身份认证 消息认证、数字签名
否认 不可否认 数字签名

关于密码学的常识:

  1. 不要使用保密的密码算法
  2. 低强度密码比不加密更危险
  3. 任何密码都有被破解的一天。(量子计算机可以在根本上解决此问题,因为量子纠缠可以实现一次性密码本算法)
  4. 密码只是信息安全中的一环,人更重要


信息的加解密

对称密码

对称加密最为常用,效率高。

对称模式可以很好的实现信息的加解密了,但有个棘手的问题,计算机世界,往往加解密需求双方并不在地理上同一位置,仅仅获得密文的一方,没有密钥是无法解密出明文的,如何将密钥顺利安全的传递给对方呢?直接通过网络传输面临着网络窃听,是不安全的。

DES(Data Encryption Standard)

DES 算法是以 64 bits 明文为一个单位(每隔 7 bits 会有一个 checksum bit,因此实际有效为 56 bits),分组对明文进行加密的,是一种分组密码(Block Cipher)算法。DES 算法原理是通过一个称为 Feistel 网络,并经过 N 轮的轮函数的计算实现的。

DES 于 1977 年公布,现已被破解。


三重 DES(Triple-DES)

又称为 TDEA(Triple Data Encryption Algorithm)或 3DES。

3DES 是在 DES 基础算法上的改良,采用 3组 56 bits 共 168 bit 的密钥,对明文数据进行 3次 DES 加密-解密-加密操作,可见,若 3组密码均一样,则 3DES == DES。因此该算法可向下兼容 DES 加密算法。

3DES 考虑了兼容性,但计算性能不高,暂时还未被破解。


AES(Advanced Encryption Standard)

AES 是于 2000 年被采用的最新的对称加密标准,采用了 Rijndael 算法。

Rijndael 算法也是一种分组算法,密钥长度规定为 128 bits,192 bits, 256 bits 三种规格。与 DES 不同,Rijndael 算法没有采用 Feistel 网络,而是采用 SPN 结构,并通过多个轮函数实现的。

SPN 结构和轮函数此处不再展开,简单的说,就是对明文数据分组,然后轮函数是进行一系列的平移、翻转、位之间的交换等操作。具体可以参考 Advanced Encryption Standard, Wikipedia

Rijindael 算法,可自由免费使用,安全、快速,暂未被破解。推荐使用。



非对称密码

非对称加密可以用于解决密钥配送问题。

相对于对称密码加解密采用相同的密码,非对称密码加解密采用的是不同的密钥,公钥和私钥成对,公钥加密的信息,只有相应的私钥才可解密。

  • 对称加密好比大家都用相同的锁对信息加密,加解密双方都拥有相同的钥匙,钥匙(密钥)丢了,锁(明文信息)就开了。
  • 非对称加密,则是向大家派发锁(公钥),大家可以通过锁,对信息加密。锁是公开的,丢了也无所谓。但钥匙(私钥)只有一把,归信息的接受者所有。

非对称加密流程

  1. 接收方生成公私钥对,私钥由接收方保管
  2. 接收方将公钥发送给发送方
  3. 发送方通过公钥对明文加密,得到密文
  4. 发送方向接收方发送密文
  5. 接收方通过私钥解密密文,得到明文

无法解决公钥认证的问题,可能被中间人伪造公钥。


RSA(Rivest-Shamir-Adleman)

RSA 是非对称加密找那个最著名的加密算法,于 1978年由 Ron Rivest, Adi Shamir,Reonard Adleman 三人共同发明。

RSA 生成公私钥对的方法,是基于以下数学公式,

CipherText=PlainTextE mod N\text{CipherText}=\text{PlainText}^E\text{ mod }N

PlainText=CipherTextD mod N\text{PlainText}=\text{CipherText}^D\text{ mod }N

其中公钥为 E+NE+N,私钥为 D+ND+N

RSA 的安全性,是基于现阶段对大整数的质因数分解未发现高效的算法。一旦发现,则 RSA 就能够破译。


强度比较

密码强度,默认的 RSA 长度为 2048 bit

AES(bit) RSA(bit)
128 3072
192 7680
256 15360

存在问题

  1. 效率慢,因此工业场景下,往往是通过非对称加密配送密钥,对称加密加密明文的混合加密方式,最著名的如 SSL
  2. 公钥认证问题难。消息发送方无法确认公钥的身份问题,应该收到甲的公钥,却收到了乙的。
  3. 无法避免中间人攻击。可能被人于中间劫持后,发送一个伪造的公钥,此公钥加密后的密文,可以被劫持者解密,之后所有的密文都对劫持者透明了。
  4. 选择密文攻击,即通过不断的发送请求,分析请求的反馈,猜测密钥和明文。有改良算法 RSA-OAEP (Optimal Asymmetric Encryption Padding)最优非对称加密填充,该算法是通过对明文前加入认证信息头,若信息头校验失败,则拒绝请求。
  5. 密码劣化,随着算力的提升,密码的安全性下降。

其它非对称加密

  • ECC(Elloptic Curve Cryptography) 椭圆曲线密码
  • EIGamal
  • Rabin



混合密码系统

混合加密就是对称加密与非对称加密的结合。由于对称加密算法速度快,强度高,而非对称加密算法效率低,但能解决密钥配送问题。因此可以通过非对称加密配送对称密钥,再采用对称密钥用来加密的方式,实现网络的密钥配送与通信加密。

一般实践中,公钥通过证书认证配送,而对称加密用的密钥是每次随机产生。因此公钥密码的强度应该高于对称密码,因为对称密码只对当前一条信息负责,而非对称密码会影响到过完与未来所有的通信。


分组密码加密模式

加密模式是针对密码分组或流加密所采用的迭代模式。

  • 分组密码:Block Cipher,每次只能处理特定长度的数据的密码算法
  • 流密码:对数据流进行连续处理的一类密码算法。需要保持内部状态

不同的分组加密方式,就有不同的加密模式:

  • ECB 模式:Electronic CodeBlock mode 电子密码本模式。将明文分组加密后的结果,直接成为密文分组。最为简单直接,但有安全漏洞。因为分组规律简单,因此可以直接操作密文的分组后的顺序来修改明文的顺序,实现明文内容的修改。
  • CBC 模式:Cipher Block Chaining mode 密码分组链接模式。首先将明文分组与前一个密文分组进行 XOR 异或运算,然后加密。由于第一个分组不存在前一个密文,因此需要提供一个分组长度的序列,称为初始化向量 Initialization Vector,缩写为 IV
  • CTS 模式:Cipher Text Stealing。
  • CFB 模式:Cipher FeedBack mode 密文反馈模式。前一组密文被送回密码算法的输入端
  • OFB 模式:Output FeedBack mode 输出反馈模式。密码算法的输出会反馈到密码算法的输入中的流密码
  • CTR 模式:CountTeR mode 计数器模式。CTR 模式是一种通过将逐次累加的计数器进行加密来生成密钥流的流密码

单向散列

单向散列技术是为了保证信息的完整性,防止信息被篡改的一项技术。

特点:

  1. 无论消息长度,计算出的长度永远不变
  2. 快速计算
  3. 消息不同,散列值不同,需要具有抗碰撞性 Collision Resistance
    • 弱抗碰撞性:给定散列值,找到和该消息具有相同散列值的另一条消息是困难的
    • 强抗碰撞性:任意散列值,找到散列值相同的两条不同的消息是困难的
  4. 具有单向性 one-way,不可由散列值推出原消息

单向散列算法

MD(Message Digest)

MD 散列算法分为 MD4, MD5 两套算法,都可计算出 128 bits 的散列。MD 系列算法已经被中国科学家王小云破解(可于有限时间内找出碰撞)。


SHA(Secure Hash Algorithm)

SHA 是单向散列算法的一个标准的统称,其下又分为 SHA-1, SHA-2, SHA-3 三套算法。

其中 SHA-1 可生成 160 bit 散列值,已被攻破(由王小云、姚期智联手破解),不推荐使用。


SHA-2 可生成不同长度的散列,如 256 bits (SHA-256), 384 bits (SHA-384), 512 bits (SHA-512),同时对输入的消息长度存在一定限制,SHA-256 上限接近于 26412^{64}-1 比特,SHA-384、SHA512 则接近于 212812^{128}-1 比特。


SHA-3,是 2012 年被采用的最新标准,采用了 Keccak 算法。

Keccak 算法的优点:

  1. 采用与 SHA2 完全不同的结构
  2. 结构清晰,易于分析
  3. 适用于各种硬件,性能优越
  4. 可生成任意长度
  5. 对消息长度无限制
  6. 可采用双工结构,输入同时输出,提升效率

MD4,5, RIPEMD, RIPEMD-160, SHA-1, SHA-2 均采用 MD 结构(Merkle-Damgard construction)

SHA-3 采用海绵结构

算法 散列长度,bit 输入长度
MD4 (Message Digest 4) 128 已破解
MD5 128 已破解
SHA-1 160 264=2048 PB2^{64} = 2048 \text{ PB} 谨慎使用,不推荐
SHA2 (SHA-224) 224 (32*8 - 32) 2642^{64} - 32 表示截去 32 bit,下同
SHA2 (SHA-256) 256 (32*8) 同上
SHA2 (SHA-512/224) 224 (64*8 - 288) 同上
SHA2 (SHA-512/256) 256 (64*8 - 256) 同上
SHA2 (SHA-384) 384 (64*8 - 128) 21282^{128}
SHA2 (SHA-512) 512 同上
SHA-3 无限制
RIPEMD-128 已破解
RIPEMD-160 谨慎使用,是比特币采用的
RIPEMD-256
RIPEMD-320

对散列的攻击

  • 暴力破解,冗余碰撞

  • 生日攻击,针对强抗碰撞性



消息认证码 MAC

单向散列可以解决篡改的问题,但消息是来自可信一方,还是来自伪装者,却无法解决。伪装者完全可以发送有害的信息和该信息的散列,而接受者却无法分辨。

消息认证码技术可以解决此类问题。

消息认证码(Message Authentication Code),简写为 MAC。通过发送方与接收方共享密钥,通过该共享密钥对计算 MAC 值。


MAC 使用步骤

消息认证码使用步骤:

  1. 发送方 A 与接收方 B 共享密钥
  2. 发送方 A 通过密钥计算 MAC 值 = MAC-A
  3. 发送方 A 发送原消息 + MAC-A
  4. 接收方 B 对原消息通过密钥计算 MAC 值 = MAC-B
  5. 接收方 B 比较 MAC-A 与 MAC-B,若一致则成功。

MAC 实现

MAC 实现的关键,是获得一串需要与共享密钥相关而且足够有区分度的串

因此,可以通过多种方式获得 MAC 值,如单向散列、分组密码截取最后一组作为 MAC 值、流密码、非对称加密等。


针对 MAC 的问题

  1. 密钥配送的问题,因为 MAC 需要发送者与接收者使用相同的密钥
  2. 重放攻击,窃取某一次通信中的正确的 MAC,然后攻击者重复多次发送相同的信息。由于信息与 MAC 可以匹配,在不知道密钥的情况下,攻击者就可以完成攻击。以下方法可以避免:
    • 序号,约定信息中带上递增序号,MAC 值为加上序号的 MAC。
    • 时间戳,约定信息中带上时间戳
    • 随机数 nonce,每次传递前,先发送随机数 nonce,通信是带上 nonce
  3. 暴力破解
  4. 无法防止否认,因为密钥是共享的,接收者可以伪造对发送者不利的信息。



数字签名

由于 MAC 无法解决否认的问题是由于采用的相同的密钥,那么采用公私钥对就可以解决啦~

采用非对称加密的消息认证码的技术,就是数字签名。

  • 在非对称加密中,私钥用来解密,公钥用来加密
  • 在数字签名技术中,私钥用来加密,公钥用来解密

数字签名步骤

  1. 签名方 A 生成非对称公私钥对 public-key、private-key
  2. A 向消息接收方 B 发送公钥 publi-key
  3. A 采用 private-key 加密(一般是对消息的散列值进行加密),生成数字签名
  4. A 将消息与数字签名发往 B
  5. B 采用 public-key 解密数字签名
  6. B 验证数字签名

由于用于解密的是公钥,是公开的。因此任何人都可以验证数字签名。


数字签名实现

数字签名的核心,就是非对称加密,在前文已经介绍了一些非对称加密算法,均可用于数字签名之中。

常见的有如下几种:

  • RSA
  • ElGamal
  • DSA
  • ECDSA(Elliptic Curve Signature Algorithm),结合椭圆曲线算法的数字签名技术
  • Rabin

数字签名的问题

数字签名由于采用了非对称加密,因此可以防止否认。但发送方怎么能知道所收到的公钥就是接收方私钥所对应的公钥呢?

如果不小心采用了攻击者的公钥,然后接收了攻击者私钥签名的信息,公私钥完全匹配,于是信息就被接受了,那么就 GG 了。

因此,业界便推出了证书。由权威机构颁布,认证公钥的合法性,那么就 OK 啦~



证书

对数字签名所发布的公钥进行权威的认证,便是证书。证书可以有效地避免中间人攻击的问题。

  • PKC:Public-Key Certificate,公钥证书,简称证书。
  • CA:Certification Authority,认证机构。对证书进行管理,负责 1.生成密钥对、2. 注册公钥时对身份进行认证、3. 颁发证书、4. 作废证书。其中负责注册公钥和身份认证的,称为 RA(Registration Authority 注册机构)
  • PKI:Public-Key Infrastructure,公钥基础设施,是为了更高效地运用公钥而制定的一系列规范和规格的总称。比较著名的有PKCS(Public-Key Cryptography Standards,公钥密码标准,由 RSA 公司制定)、X.509 等。PKI 是由使用者、认证机构 CA、仓库(保存证书的数据库)组成。
  • CRL:Certificate Revocation List 证书作废清单,是 CA 宣布作废的证书一览表,会带有 CA 的数字签名。一般由处理证书的软件更新 CRL 表,并查询证书是否有效。

证书使用步骤

下图比较详细的阐述了证书的使用步骤

上图摘自 《图解密码技术》一书(结城浩 著,周自恒 译,人民邮电出版社出版)第 10.2 章节图 10-1。

证书的层级

对于认证机构的公钥,可以由其它的认证机构施加数字签名,从而对认证机构的公钥进行验证,即生成一张认证机构的公钥证书,这样的关系可以迭代好几层,一直到最高一层的认证机构时该认证机构就称为根CA,根CA会对自己的公钥进行数字签名叫做自签名


针对证书的问题

  1. 公钥注册前进行攻击
  2. 注册相似信息进行攻击,例如 Bob 和 BOB,一旦没看清,就会泄露信息
  3. 窃取 CA 的私钥进行攻击,CA 的私钥一旦被泄露,需要通过 CRL 通知客户
  4. 伪装成 CA 进行攻击,一般证书处理软件只采纳有限的根 CA
  5. 利用 CRL 发布时间差,私钥被盗-通知 CA-发布 CRL,均存在时间差,攻击者可以利用此时间差进行攻击
  6. 利用 CRL 发布时间差否认信息。发布有害信息-通知 CA 作废证书-发布 CRL,由于存在时间差,恶意消息的发布者完全可以否认恶意消息是由其发出的。



参考资料

[1] 《图解密码技术》 结城浩 著,周自恒 译,人民邮电出版社出版
[2] Graphic Cryptology, https://xiaoxueying.gitbooks.io/graphic-cryptology/content/
[3] 《Java 加密与解密的艺术》
[4] Advanced Encryption Standard, Wikipedia, https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Description_of_the_cipher