Hash函数

Hash函数能将任意长度的输入变换为固定长度的输出且不可逆的单向密码体制。它的主要功能是数字签名和消息完整性检验。

原理

Hash函数是一个单向函数，从明文到密文的不可逆映射，只有加密过程，没有解密过程。

Hash函数可以将满足要求的任意长度的输入进行转换，从而得到固定输出，输出称为原消息的散列值（Hash Value）或消息摘要（Message Digest）。Hash的数学表达： $h =H(m)$ ，H是Hash函数，m是任意长度明文，h是固定长度的Hash值。

如果两个不同的消息 $x,x^\prime$ ，有 $H(x) =H(x^\prime)$ ，则称发生了一个碰撞。

典型的Hash函数有两类：消息摘要算法（MD5）和安全散列算法（SHA）。

Hash函数的特点：

易计算：对于任意给定的消息，计算其Hash值比较容易。

单向性：对于给定的Hash值h，要找到 $m^\prime$ 使得 $H(m^\prime) =h$ 在计算上是不可行的，即求Hash的逆很困难。

抗碰撞性：理想的Hash函数是无碰撞的，但在实际算法的设计中很难做到这一点。有两种抗碰撞性：一种是弱抗碰撞性，即对于给定的消息，要发现另一个消息，满足H（x）=H（y）在计算上是不可行的；另一种是强抗碰撞性，即对于任意一对不同的消息（x,y），使得H（x）=H（y）在计算上也是不可行的。

SHA-1算法

输入：最大长度小于 $2^{64}$ 位的消息，输入消息以512位的分组为单位进行处理

输出：160位bit的消息摘要。

实现速度高、容易实现、应用范围广

（1）填充：对输入的消息进行填充，要求 $len(message)\equiv 448(\mod 512)$ ，填充的方式为第一位是1，余下各位是0。再将消息被填充前的长度以大端的方式附加在上一步留下的最后64位中。即使消息的长度满足所希望的长度也必须进行填充，填充长度范围是1-512

（2）初始化缓冲区，可以用160位来存放Hash函数的初始变量、中间摘要及最终摘要，但首先必须进行初始化，对每个32位的初始变量赋值

$H_0 = 0x67452301\\ H_1 =0xefcdab89\\ H_2 =0x98badcfe\\ H_3 = 0x10325476 \\ H_4 =0xc3d2e1f0$

3）进入消息处理主循环，处理消息块：一次处理512位的消息块，总共进行4轮处理，每轮进行20次操作，如图所示。这4轮处理具有类似的结构，但每轮所使用的辅助函数和常数都各不相同。每轮的输入均为当前处理的消息分组和缓冲区的当前值A、B、C、D、E，输出仍放在缓冲区以替代旧的A、B、C、D、E的值。第四轮的输出再与第一轮的输入CVq 相加，以产生CVq+1 ，其中加法是缓冲区5个字中的每个字与CVq 中相应的字模232相加。

4）输出：所有的消息分组都被处理完之后，最后一个分组的输出即为得到的消息摘要值。

SHA-2算法

SHA-2算法分别有SHA-224,SHA-256,SHA-384,SHA-512,分别对应输出长度为256位，384位，512位

SHA-256和SHA-512是很新的Hash函数，前者定义一个字为32位，后者则定义一个字为64位。实际上二者的结构是相同的，只是在循环运行的次数、使用常数上有所差异。SHA-224及SHA-384则是前述两种Hash函数的截短型，它们利用不同的初始值做计算。

椭圆曲线加密

椭圆曲线密码体制（Elliptic Curve Cryptosystem，ECC）是1985年由Koblitz N和Miller V提出的，其安全性是建立在求解椭圆曲线离散对数问题困难性的基础上的，在同等密钥长度的情况下ECC的安全强度要远高于RSA体制等其他密码体制。

另一方面，在安全性相当的情况下，ECC所使用的密钥长度更短，这也就意味着对于带宽和存储空间的需求相对较小。

椭圆曲线密码体制的安全性，依赖于椭圆曲线上离散对数问题（Elliptic Curve Discrete Logarithm Problem，ECDLP）的难解性。

椭圆曲线方程

常用于密码系统的基于有限域 $GF(p)$ 上的椭圆曲线是由方程：

y^2 = x^3 +ax+b (\mod p)

其中 $a,b,x,y \in GF(p), 4a^3+27b^2 \ne 0, p \ is\ a\ prime\ and\ p>3$

通常用 $E_p(a,b)$ 来表示这类曲线。

在这类椭圆曲线上，通常有以下的运算规则：

椭圆曲线点乘规则具体如下：

公钥和私钥的产生算法：

（1）选择一个椭圆曲线 $E:y^2=x^3+ax+b(\mod p)$ ，构造一个椭圆曲线Abel群 $E_p(a,b)$

（2）选择生成元 $G=(x_0,y_0)$ ，G应得满足 $nG=0$ ，n是一个素数

（3）选择一个小于n的整数 $n_B$ 作为其私钥，然后产生公钥 $P_B=n_BG$ ，用户的公钥为 $(E,n,G,P_B)$ ，私钥为 $n_B$

ECDSA数字签名

椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm,ECDSA）基于ECDLP，是使用椭圆曲线对数字签名算法（Digital Signature Algorithm，DSA）的模拟。

ECDSA数字签名算法流程：

准备参数： $E_p(a,b),G,sk=d,pk=dG$

签名：签名者A利用私钥对消息m进行签名，具体方法如下;

(1)随机选择一个整数k

(2)计算 $kG=(x_1,y_1),r\equiv x_1\mod n$

(3)计算 $e=H(m), s=k^{-1}(e+dr)\mod n$

其中 $(r,s)$ 是A对消息m的签名

验证：

（1）验证 $r,s \in [1,n-1]$

（2）计算 $e=H(m), w =s^{-1}\mod n, u_1 =ew\mod n,u_2 =rw\mod n$

（3）计算 $X=u_1G+u_2Q=(x_1,y_1)$

ECDSA在安全性方面的目标是能抵抗选择明文（密文）攻击。

比特币区块链中，每个交易都需要用户使用私钥签名，只有采用该用户公钥验证通过的交易，比特币网络才会承认。

Bloom filter

Bloom filter是一种节省空间、高效率的数据表示和查询结构。它可以利用位数组很简洁地表示一个集合，并能以很高的概率判断一个元素是否属于这个集合。因此，这种数据结构适合应用在能容忍低错误率的场合。

技术原理

传统的判断一个元素是不是在一个集合中，通常的做法是把所有的元素都保存下来，然后比较确定它是不是在其中。但是，当元素的个数增大时，我们需要的空间和时间都会线性变大，检索速度也会越来越慢。Bloom filter采用的是Hash函数的方法，将一个元素映射到一个m长度的阵列上的一个点，当这个点是时，那么这个元素在集合内，反之则不在集合内。

工作原理如下：

（1）初始化状态，Bloom filter是一个m位数组，每一位都置为0

（2）为了表达 $S=\{x_1,...,x_n\}$ 这样有n个元素的集合，Bloom filter使用k个相互独立的Hash函数，分别将集合中的每个元素映射到 $\{1,2,...m\}$ 中，对于任意一个元素x，第i个Hash函数映射的位置h(x)会被置为1