Hash 算法与数字摘要

Hash （哈希或散列）算法它能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash值），并且不同的明文很难映射为相同的Hash值。

Hash 定义

Hash （哈希或散列）： 能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash值），并且不同的明文很难映射为相同的 Hash 值。
Hash 值在应用中又常被称为指纹或摘要（digest）。Hash 算法的核心思想也经常被应用到基于内容的编址或命名算法中

一个优秀的Hash算法将能实现如下功能：

• 正想快速： 给定明文和 Hash 算法，在有限时间和有限资源内能计算得到Hash值
• 逆向困难: 给定（若干）Hash值，在有限时间内很难（基本不可能）逆推出明文
• 输入敏感： 原始输入信息发生任何改变，新产生的 Hash 值都应该出现很大不同
• 冲突避免： 很难找到两端内容不同的明文，使得它们的 Hash 值一致（发生碰撞）、

冲突避免：有时候又称为“抗碰撞性”，分为：

• 弱抗碰撞性： 如果给定明文前提下，无法找到与之碰撞的其他明文，则算法具有“弱碰撞性”
• 强抗碰撞性： 如果无法找到任意两个发生 Hash 碰撞的明文，则算法具有“强抗碰撞性”

常见算法

目前常见的 Hash 算法包括 MD5 和 SHA系列算法，MD5算法和SHA1已经被破解，一般推荐使用SHA2-256或更安全的算法

性能

Hash算法分为：

• 计算敏感型（一般都是）： 意味着计算资源是瓶颈，主频越高的 CPU 运行Hash 算法的速度也越快。因此可以通过硬件加速来提升Hash计算的吞吐量。
• 非计算敏感型： 例如 scrypt 算法，计算过程需要大量的内存资源，节点不能通过简单地增加更多的 CPU 来获得 Hash 性能的提升。这样的Hash算法经常用于在 避免算力攻击的场景

数字摘要

数字摘要：对数字内容进行Hash运算，获取唯一的摘要值来指代原始完整的数字内容。数字摘要是 Hash算法最重要的一个用途。利用Hash函数的抗碰撞性特点，数字摘要可以解决确保内容未被篡改过的问题。

Hash攻击与防护

Hash 算法并不是一种加密算法，不能用于对信息的保护。但Hash算法常用于对口令的保存上。例如用户登录网站，网站后台保存口令的Hash值，每次登录进行比对即可，即便数据库泄露，也无法从 Hash值还原口令，只能进行穷举。

Hash攻击： 由于有时用户设置口令的强度不够，只是一些常见的简单字符串，如password,123456等。有人专门搜集了这些常见口令，计算对应的Hash值，制作成字典。这样通过Hash值可以快速反查到原始口令。这一类以空间换时间的攻击方法包括字典攻击和彩虹表攻击（只保存一条Hash链的首尾值，相对字典攻击可以节省存储空间）等。

Hash攻击防范方法：为了防范这一类攻击，一般采用加盐（salt）的方法。保存的不是口令明文的 Hash值，而是口令明文再加上一段随机字符串（即“盐”）之后的Hash值。Hash结果和“盐”分别存放在不同的地方，这样只要不是两者同时泄露，攻击者就很难破解了。

加解密算法

加解密算法是密码学的核心技术，可分为两大基本类型：

image.png

加解密系统基本组成

现代加解密系统的典型组件一般包括： 加解密算法、加密密钥、解密密钥。其中，加解密算法自身是固定不变的，并且一般是公开可见的。密钥则是关键的信息，需要安全地保存起来，甚至通过特殊硬件进行保护。对同一种算法，密钥需要按照特定算法每次加密前随机生成，长度越长，则加密强度越大。加解密基本过程如下：

image.png

密码学实现的安全往往是通过算法所依赖的数学问题来提供，而并非通过对算法的实现过程进行保密。

对称加密算法

对称加密算法，加密和解密过程的密钥是相同的。

• 优点：加解密效率（速度快，空间占用小）和加密强度都很高。
• 缺点：参与方都需要提前持有密钥，一旦有人泄露则安全性被破坏，另外如何在不安全通道中提前分发密钥也是个问题，需要借助Diffie-Hellman协议或非对称加密方式来实现。

对称密码从实现原理上可以分为两种：

• 分组密码： 将明文切分为定长数据块作为基本加密单位，应用最为广泛。分组对称加密代表算法包括 DES、3DES、AES、IDEA等
• 序列密码： 每次只对一个字节或字符进行加密处理，且密码不断变化，只用在一些特定领域，如：数字媒介的加密等。序列密码，又称流密码，每次通过伪随机数生成器来生成伪随机密钥串。

对称加密算法适用于大量数据的加解密过程；不能用于签名场景；并且往往需要提前分发好密钥；

非对称加密算法

非对称加密可以很好的解决对称加密中提前分发密钥的问题。非对称加密中，私钥一般需要通过随机数算法生成，公钥可以根据私钥生成。公钥一般公开，他人可获取的；私钥一般是个人持有，他人不能获取

非对称加密算法：

• 优点： 是公私钥分开，不安全通道也可使用。
• 缺点：是处理速度（特别是生成密钥和解密过程）往往比较慢，一般比对称加解密算法慢2~3个数量级；同时加密强度也往往不如对称加密算法。

非对称加密算法的安全性往往需要基于数学问题来保障，目前主要有基于大数质因子分解、离散对数、椭圆曲线等经典数学难题进行保护。代表算法包括： RSA、ElGamal、椭圆曲线（ECC）、SM2等系列算法。目前普遍认为RSA类算法可能在不远的将来被破解，一般推荐可采用安全强度更高的椭圆曲线系列算法。

选择明文攻击

在非对称加密中，由于公钥是公开可以获取的，因此任何人都可以给定明文，获取对应的密文，这就带来选择明文攻击的风险。 在已知明文攻击、已知密文攻击、选择明文攻击中，最有威胁的为选择明文攻击。

• 已知明文攻击： 得到了一些给定的明文和对应的密文
• 已知密文攻击： 只知道密文，只能通过统计特性分析其中有什么规律了
• 选择明文攻击：通过公钥加密一些常用语，截取发送方的密文和公钥加密后的密文对比获取信息。

为了规避选择明文攻击这种风险，现有的非对称加密算法都引入了一定的保护机制。对同样的明文使用同样密钥进行多次加密，得到的结果完全不同，这就避免了选择明文攻击的破坏。实现上有多种思路：

• 对明文先进行变形，添加随机的字符串或标记，再对添加后结果进行处理。
• 先用随机生成的临时密钥对明文进行对称加密，然后再对对称密钥进行加密，即混合利用多种加密机制。

混合加密机制

混合加密机制同时结合了对称加密和非对称加密的优点。先用计算复杂度高的非对称加密协商出一个临时的对称加密密钥（也称为会话密钥）然后双方通过对称加密算法传递的大量数据进行快速的加解密处理。

HTTPS 在传统的HTTP层和TCP层之间通过引入 Transport Layer Security/Secure Socket Layer（TLS/SSL）加密层来实现可靠的传输
HTTPS 为典型应用案例：

image.png

离散对数与Diffie-Hellman 密钥交换协议

Diffie-Hellman（DH）密钥交换协议是一个经典协议，使用该协议可以在不安全信道完成对称密钥的协商，以便后续通信采用对称加密。

DH的缺点：

• 阻塞性攻击：没有提供双方身份的任何信息. 它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥.受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作.
• 容易遭受中间人的攻击

消息认证与数字签名

消息认证码和数字签名技术通过对消息的摘要进行加密，可用于消息放篡改和身份证明问题。

消息认证码

消息认证码： 全称是“基于Hash的消息认证码”。消息认证码基于对称加密，可以用于对消息完整性进行保护。

基本过程： 对某个消息利用提前共享的对称密钥和Hash算法进行加密处理，得到HMAC值。该HMAC值持有方可以证明自己拥有共享的对称密钥，并且也可以利用HMAC确保消息内容未被篡改。

消息认证码一般用于证明身份的场景， 主要问题是需要共享密钥

数字签名

数字签名基于非对称加密，既可以用于证实某数字内容的完整性，又同时可以确认来源。

典型的场景： A通过信道发给B一个文件（一份信息），B如何获知收到的文件即为A发出的原始版本？A可以先对文件内容进行摘要，然后用自己的私钥对摘要进行加密（签名），之后同时将文件和签名发给B。B收到文件和签名后，用A的公钥来解密签名，得到数字摘要，与收到文件进行摘要后的结果进行比对。如果一致，说明该文件确实是A发的（别人无法拥有A的私钥），并且文件内容没有被修改过（摘要结果一致）

知名的数字签名算法包括DSA 和 安全强度更高的ECSDA等。
除普通的数字签名应用场景外，针对一些特定的安全需求，产生了一些特殊数字签名技术：

• 盲签名： 签名者需要在无法看到原始内容的前提下对信息进行签名。盲签名可以实现对所签名内容的保护，防止签名者看到原始内容。另一方面，盲签名还可以实现防止追踪，签名者无法将签名内容和签名结果进行对应。
• 多重签名：即n个签名者中，收集到至少m个（n>=m>=1）的签名，即认为合法。其中，n是提供的公钥高数，m是需要匹配公钥的最少的签名个数
• 群签名：即某个群组内一个成员可以代表群组进行匿名签名。签名可以验证来自于该群组，却无法准确追踪到签名的是哪个成员
• 环签名： 环签名是一种简化的群签名。签名者首先选定一个临时的签名者集合，集合中包括签名者自身。然后签名者利用自己的私钥和签名集合中其他人的公钥就可以独立地产生签名，而无需他人的帮助。签名者集合中的其他成员可能并不知道自己被包含在最终的签名中 。环签名在保护匿名性方面有很多的用途。

安全性

数字签名算法自身的安全性由数学问题进行保障，但在使用上，系统的安全性也十分关键。目前常见的数字签名算法往往需要选取合适的随机数作为配置参数，配置参数不合理的使用或泄露都会造成安全漏洞，需要进行安全保护。

数字证书

对于非对称加密算法和数字签名来说，很重要的一点就是公钥的分发。但在传输过程中，公钥有没有可能是伪造的呢？传输过程中有没有可能被篡改？一旦公钥出了问题，则整个建立在其上的安全体系的安全性将不复存在。

数字证书机制： 可以证明所记录信息的合法性，比如证明某个公钥是某个实体（如组织或个人）的，并且确保一旦内容被篡改能被探测出来，从而实现对用户公钥的安全分发。

根据保护公钥的用途，可以分为：

• 加密数字证书：用于保护用于加密信息的公钥
• 签名验证数字证书：用于保护用于进行解密签名进行身份验证的公钥
  一般情况下，证书需要由证书认证机构来进行签发和背书

证书规范

一般来说，一个数字证书内容可能包括基本数据（版本、序列号）、所签名对象信息（签名算法类型、签发者信息、有效期、被签发人、签发的公开密钥）、CA的数字签名，等等。目前使用最广泛的标准为ITU和ISO联合制定的X.509的 v3 版本规范
证书的颁发者还需要对证书内容利用自己的私钥添加签名，以防止别人对证书内容进行篡改。

证书格式

X.509规范中一般推荐使用PEM格式来存储证书相关的文件。证书文件的文件名后缀一般为.crt或.cer，对应私钥文件的文件名后缀一般为.key，证书请求文件的文件名后缀为.csr。有的时候也统一用.pem作为文件名后缀。此外还有DER格式，是采用二进制对证书进行保存，可以与PEM格式互相转换。

证书信任链

证书中记录了大量信息，其中最重要的包括“签发的公开密钥”和“CA数字签名”两个信息。因此，只要使用CA的公钥再次对着个证书进行签名比对，就能证明某个实体的公钥是否是合法的。

那么怎么证明用来验证对实体证书进行签名的CA公钥自身是否合法呢？

• 可以通过上层的CA颁发的证书来进行认证
• 某些根CA可以通过预先分发证书来实现信任基础
  证书作为公钥信任的基础，对其生命周期进行安全管理十分关键。

PKI 体系

在非对称加密中，公钥可以通过证书机制来进行保护，但证书的生成、分发、撤销等过程并没有在X.509规范中进行定义。安全地管理和分发证书可以遵循PKI（Public Key Infrastructure）体系来完成。PKI体系核心解决的是证书生命周期相关的认证和管理问题。PKI是建立在公私钥基础上实现安全可靠传递消息和身份确认的一个通用框架，并不代表某个特定的密码学技术和流程。

PKI 基本组件

PKI至少包括如下核心组件：

• CA（Certification Authority）: 负责证书的颁发和作废，接收来自RA的请求，是最核心的部分。（主要完成对证书信息的维护）
• RA（Registration Authority）: 对用户身份进行验证，校验数据合法性，负责登记，审核过了就发给CA
• 证书数据库： 存放证书，多采用X.500系列标准格式。可以配合LDAP目录服务管理用户信息

操作流程： 用户通过RA登记申请证书，提供身份和认证信息等；CA审核后完成证书的制造，颁发给用户。用户如果需要撤销证书则需要再次向CA发出申请。

证书的签发

CA对用户签发证书实际上是对某个用户公钥，使用CA的私钥对其进行签名。这样任何人都可以用CA的公钥对该证书进行合法性验证。验证成功则认可该证书中所提供的用户公钥内容，实现用户公钥的安全分发。

用户证书的签发可以有两种方式：

• 由CA直接来生成证书（内含公钥）和对应的私钥发给用户
• 由用户自己生成公钥和私钥，然后由CA来对公钥内容进行签名（这种方式整个过程中，用户可以保持私钥信息的私密性，不会被其他方获知包括CA方）

证书的撤销

证书超过有效期后会作废，用户也可以主动向CA申请撤销某证书文件。

CA 无法强制收回已经颁发出去的数字证书，因此为了实现证书的作废，往往还需要维护一个撤销证书列表，用于记录已经撤销的证书序号。（所以第三方验证某个证书时，第一步就是检查该证书是否在撤销列表中，如果存在则无法验证通过。如果不在则继续后续验证）

Merkle 树结构

Merkle（默克尔）树：又叫哈希树，是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。区块链出现之前，广泛用于文件系统和P2P系统中。

image.png

主要特点：

• 最下面的叶节点包含存储数据或其哈希值
• 非叶子几点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值
  默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味着树根的值实际上代表了对底层所有数据的“数字摘要”

默克尔树的应用场景有如下：

• 快速比较大量数据：对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时，则意味着两组数据必然相同。否则，必然存在不同。（由于Hash计算的过程可以十分迅速，预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势）
• 快速定位修改： 一旦发现某个节点如Root的数值发生变化，沿着Root->N4->N1，即可快速定位到实际发生改变的数据块D1
• 零知识证明： 如何向他人证明拥有某组数据（D0...D3）中包括给定某个内容D0而不暴露其他任何内容。方法：通过构造如上图所示的一个默克尔树，公布N1、N5、Root。D0拥有者通过验证生成的Root是否跟提供的值一致，即可很容易检测D0包括D1、D2、D3的存在。整个过程无法获知其他内容。

布隆过滤器

布隆过滤器： 是一种基于Hash的高效查找结构，能够快速（常数时间内）回答“某个原始是否在一个集合内”的问题。

应用场景：布隆过滤器因为其高效性大量应用于网络和安全领域，例如信息检索、垃圾邮件规则、注册管理等

基于Hash的查找

基于Hash的快速查找算法： Hash可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很小。因此，可构成以个很好的“内容——》索引”的生成关系。（内容Hash后为索引通过索引可在数组中快速的查找当前内容）

基于Hash的快速查找算法的缺点：当映射后的值限制在一定范围（如总数组的大小）内时，会发现 Hash 冲突的概率会变高，而且范 围越小，冲突概率越大。很多时候，存储系统的大小又不能无限扩展，这就造成算法效率的下降。为了提高空间利用率，后来人们基于Hash算法思想设计出了布隆过滤器结构。

更高效的布隆过滤器

布隆过滤器： 采用多个Hash函数来提高空间利用率。对于同一个给定输入来说，多个Hash函数计算出多个地址，分别在位串的这些地址上标记为1。进行查找时，进行同样的计算过程，并查看对应原始，如果都为1，则说明较大概率是存在该输入。

优点：大大提高了空间利用率，可以使用较少的空间来表示较大集合的存在关系。

总结： 无论是Hash算法，还是布隆过滤器，基本思想都是基于内容的编址。Hash函数存在冲突，布隆过滤器也存在冲突。这就造成了两种方法都存在误报的情况，但绝对不会漏报。

同态加密

同态加密

同态加密： 是一种特殊的加密方法，允许对密文进行处理得到任然是加密的结果。即对密文直接进行处理，跟对明文进行处理后再对处理结果加密，得到的结果相同。
优点：同态加密可以保证实现处理者无法访问到数据自身的信息

问题与挑战

同态加密的两个应用场景：

• 同态加密在云计算和大数据时代意义十分重大。从安全角度讲，用户还不敢将敏感信息直接放到第三方云上进行处理。如果有了比较实用的同态加密技术，则可以放心实用各种云服务，同时各种数据分析过程也不会泄露用户隐私
• 对于区块链技术，实用同态加密技术，运行在区块链上的只能合约可以处理密文，而无法获知真实数据，极大地提高了隐私安全性。

目前全同态的加密方案主要包括“基于理想个的方案”、“基于整数上近似GCD问题的方案”、“基于带扰动学习问题的方案”。已知的同态加密技术往往需要较高的计算时间或存储成本，相比传统加密算法的性能和强度还有差距。

函数加密

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

其他问题

零知识证明

零知识证明： 证明者在不想验证者提供任何额外信息的前提下，使验证者相信某个论断是正确的。

零知识证明至少要满足三个条件：

• 完整性： 真实的证明可以让验证者成功验证
• 可靠性： 虚假的证明无法让验证者保证通过验证，但允许存在小概率例外
• 零知识： 如果得到证明，无法从证明过程中获知除了所证明信息之外的任何信息

量子密码学

量子密码学：随着量子计算和量子通信的研究而受到越来越多的关注，将会对已有的密码学安全机制产生较大的影响。

社交工程学

即便存在理论上完美的技术，也不存在完美的系统！
个人理解：系统中有人的组成部分并不是坚不可破的，因为人带有社会属性，通过社会学攻击可以轻易的攻破理论上完美的系统。

总结

image.png