加密技术07-消息认证码与数字签名

消息认证码（Message Authentication Code，简称 MAC）是一种能够识别通信对象发送的消息是否被篡改的认证技术，用于验证消息的完整性，以及对消息进行身份认证。消息认证码的算法中，最常用的是利用散列函数的 HMAC。HMAC 的构成不依赖于某一种具体的散列函数算法。消息认证码能够对通信对象进行认证，但无法对第三方进行认证。此外它也无法防止否认。

主要作用

HMAC 实现原理

HMAC 是一种使用散列函数来构造消息认证码的方法（RFC2014），其中 HMAC 的 H 就是 Hash 的意思。HMAC 中所使用的散列函数并不仅限于一种，任何高强度的散列函数都可以被用于 HMAC，如果将来设计出新的散列函数，也同样可以使用。

对 message 生成消息认证码可以表示为： hmac(message, secret, hash) ，secret 为共享密钥，hash 为所使用散列函数。

（1）密钥填充：如果密钥比散列函数的分组长度要短，就需要在末尾填充 0，直到其长度达到散列函数的分组长度为止。如果密钥比分组长度要长，则要用散列函数求出密钥的散列值，然后将这个散列值用作 HMAC 的密钥。

（2）填充后的密钥与 ipad 的 XOR：将填充后的密钥与被称为 ipad 的比特序列进行 XOR 运算。 ipad 是将 00110110 这一比特序列（即 16 进制的 36）不断循环反复直到分组长度所形成的比特序列，其中 ipad 的 i 是 inner（内部）的意思。XOR 运算所得到的值，就是一个和散列函数的分组长度相同，且和密钥相关的比特序列。这里我们将这个比特序列称为 ipadkey。

（3）与消息组合：将 ipadkey 与消息进行组合，也就是将和密钥相关的比特序列（ipadkey）附加在消息的开头。

（4）计算散列值：将（3）的结果输入散列函数，并计算出散列值。

（5）填充后的密钥与 opad 的 XOR：将填充后的密钥与被称为 opad 的比特序列进行 XOR 运算。opad 是将 01011100 这一比特序列（即 16 进制的 5C）不断循环反复直到达到分组长度所形成的比特序列，其中 opad 的 o 是 outer（外部）的意思。XOR 运算所得到的结果也是一个和散列函数的分组长度相同，且和密钥相关的比特序列，这里我们将这个比特序列称为 opadkey。

（6）与散列值组合：将（4）的散列值拼在 opadkey 后面。

（7）将（6）的结果输入散列函数，并计算出散列值。这个散列值就是最终的 MAC 值。

对消息认证码的攻击

关于防止重放攻击的方式

消息认证码无法解决的问题

由于 MAC 值发送者和接受者都能生成，所以接受者如果要向第三方验证者证明消息的来源为发送者，第三方验证者是无法证明的，因为接受者也是可以生成 MAC 值的；第三方验证者无法判断发送者和接受者谁的主张才是正确的，也就是说，用消息认证码无法防止否认。

数字签名是一种能够对第三方进行消息认证，并能够防止通信对象做出否认的认证技术。数字签名的算法包括 RSA，ELGamal，DSA，椭圆曲线 DSA 等。公钥基础设施（PKI）中使用的证书，就是对公钥加上认证机构的数字签名收构成的。要验证公钥的数字签名，需要通过某种途径获取认证机构自身的合法公钥。

数字签名的方法

直接对消息签名的方法比较容易理解，但实际上并不会使用；对消息的散列值签名的方法稍微复杂一点，但实际中我们一般都使用这种方法。

对数字签名的攻击

数字签名无法解决的问题

用数字签名既可以识别出篡改和伪装，还可以防止否认。也就是说，我们同时实现了确认消息的完整性、进行认证以及否认防止。

然而，要正确使用数字签名，有一个前提，那就是用于验证签名的公钥必须属于真正的发送者。即使数字签名算法再强大，如果你得到的公钥是伪造的，那么数字签名也会完全失效。

为了能够确认自己得到的公钥是否合法，我们需要使用证书。所谓证书，就是将公钥当作一条消息，由一个可信的第三方对其签名后所得到的公钥。

普通的哈希函数是公开的算法，没用到密钥，所以随便一个人都可以用自己的消息计算一个哈希值发给你，你检查后还是合法的消息。但如果你跟对方约定好一个密钥，再计算哈希值，截取的人不知道你们的密钥就不能计算出合法的哈希值。就能保证消息一定是对方发过来的。

4）单向散列函数介绍（Hash Function,哈希函数）：

将任意长度的消息M映射/换算成固定长度值h(散列值，或消息摘要MD, Message Digest)，最大的特点为其具有单向性。

h=H(M)

Hash函数用于消息认证（或身份认证）以及数字签名。

特性：

(1) 给定M，可算出h

(2) 给定h，根据H(M)=h反推出M是非常困难的。

(3) 给定M，要找到另外一个消息M，使其满足H(M)=H(M)=h 是非常困难的。

注 （见 参考E，p75）：

－从理论上说，有很多消息能生成相同的消息摘要。因为消息的长度是任意的，而摘要的长度是固定的。

－对于固定1000 bit的消息和固定128 bit的摘要，平均来说，有2872个消息与之对应，测试似乎不可能成功。

－对于一个128 bit的消息摘要算法，大约需要尝试2128个（长短不一的）消息，才能找到一个消息摘要与给定的摘要数值相吻合（作为攻击，当然该消息可为经篡改后的消息）。注：这里是用无数次的“尝试”，而非简单从h反推出M。

－对于一个128 bit的消息摘要算法，需要尝试264个消息才能找到两个具有相同摘要的消息。

－为什么将消息摘要定为128 bit 因为消息摘要为m bit，任何人想要得到两个具有相同摘要的消息，大约需要尝试2m/2个消息。 若m=64, 则需检查232个消息，这在计算上是可行的。所以使m=128, 检查264个消息目前在计算上是不可行的。

应用举例讲解：

（i） 存储于银行计算机内的用户密码采用散列值，用于保密。

（ii）Alice要Bob写一份关于解雇Fred的报告，而Bob是Fred的朋友，想做“双面人”。

（iii）为文档和程序生成“指纹”或“DNA”。

在实际应用中，Hash函数是基于压缩函数的。

（RefC_p42_Hash函数）

给定任意长度的消息，Hash函数输出长度为m的散列值（即消息摘要）。

压倒函数的输入为

（1） 明文消息分组 Ｍi。

（2） 前一压缩数据的输出 CVi-1 （Compressed Vector）。

注：

-第一个压缩函数的输入Ｍ1为和IV (Initial Vector)。

-压缩函数的输出值为前所有分组的散列值；最后一个分组的散列值即为整个消息的散列值，即消息摘要MD。

Hash函数算法介绍: MD5算法 和 SHA-1算法。

MD5算法：

对任意长度的消息M作为输入，产生一个128 bit的散列值/消息摘要。

（RefC_p43_MD5算法）

算法包括5个步骤：

（1） 附加填充位：填充消息，使消息的长度位一个比512倍数小64位的数，填充位数为1～512。填充方法：原消息的后面第一位填1，其余填0。（例如：设消息为“abc”。）

（2） 附加长度：将原消息的64位表示附加在填充后的消息后面，这时处理后的消息的长度恰好为512的整数倍。（续上例）

若原消息的长度大于264时，则用原消息长度mod264的64位表示附加在填充后的消息后面。

（3） 初始化MD的缓冲区：缓冲区共有4个32 bit的寄存器 A、B、C、D, 各寄存器的初始值为

A: 01 23 45 67

B: 89 ab cd ef

C: fe dc ba 98

D: 76 54 32 10

（4） 按512 bit的消息分组处理输入消息：该步为MD5的主循环，包括4轮。

（RefC_p44_主循环处理）

每个循环均以当前正在处理的512 bit的分组Yq和128 bit的缓冲值ABCD为输入，然后更新缓冲内容。

以上4轮 *** 作类似，每轮进行16次 *** 作，各轮 *** 作过程见下图。

（RefC_p44_某轮执行过程）

每一轮的非线性函数不同，4次所用的非线性函数分别记为 F、G、H、I。

F(X,Y,Z)=(X Y) ((～X) Z)

G(X,Y,Z)=(X Z) ( Y (～Z))

H(X,Y,Z)=X Y Z

I(X,Y,Z)=Y (X (～Z))

其中： ：逻辑按位与 ：逻辑按位或

～：逻辑按位反 ：逻辑按位异或

注：T表：T[i]=232abs(sin(i))

安全散列函数算法（SHA, Secure Hash Algorithm）：

SHA由美国NIST（国家标准与技术研究所）和NSA(国家标准协会)设计，用于数字签名（DS）。

SHA-1为SHA的修改版，于1995年发布。

SHA-1产生消息摘要的过程与MD5类似，但输入为度小于232 bit的消息，而输出为160 bit的散列值（即消息摘要MD），消息仍需填充使其最后为512的整数倍。

注：与MD5比较：

－附加填充位和附加消息长度与MD5相同。

－初始化缓冲器：SHA用两个缓冲区，每个区均有

5个32位的寄存器，分别为 A、B、C、D、E和H0、H1、H2、H3、H4。另有一单字缓冲区。

－按512 bit分组处理输入消息，主循环包括4轮（和MD5一样），但每轮 *** 作20次（MD5为16次）

（详见参考资料）

25 数字信封

用于保证数据在传输过程中的安全。对称加密效率高，但密钥不适合在公共网络传递，而非对称加密传递简单，但效率低下。数字信封技术取二合一，即取对称加密的高效性和非对称加密的灵活性。

（RefB_p385_数字信封）

－两个不同的加密解密过程：明文的加密/解密，密钥的加密/解密。首先使用对称加密算法对数据加密；然后，利用非对称加密算法对对称加密过的密钥进行加密，过程包括：

（1） 发送消息时，发送方生成一个对称密钥。

（2） 发送方使用自己的对称加密的密钥和算法对欲发送的数据进行加密，形成数据密文。

（3） 发送方使用接收方提供的公钥，对自己的密钥进行加密。

（4） 发送方通过网络将加密后的密文和密钥传输到接收方。

（5） 接收方用私钥对加密后的发送方密钥进行解密，获得对称密钥。

（6） 接收方使用还原出的密钥对数据进行解密，得到数据明文。

应用两层加密体制，在内层运用对称加密技术，每次传送消息都可以重新生成新的密钥，保证消息的安全性。在外层，利用非对称加密技术加密对称密钥，保证密钥传递的安全性。

2．6 身份认证技术的发展

网络用户的身份认证可以用下列3中基本方法之一或它们的组合来实现。

（1） 所知（knowledge）: 验证用户的密码，口令等。

（2） 所有（possession）: 所掌握的用户的身份z、护照、xyk等。

（3） 特征（characteristics）:所掌握的用户的指纹、声音、笔记、手型，虹膜，ＤＮＡ、动作等。

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。

在信息安全领域中应用的Hash算法，还需要满足其他关键特性：

第一当然是单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的 Hash 又被称为"消息摘要(message digest)"，就是要求能方便的将"消息"进行"摘要"，但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。

第二是抗冲突性(collision-resistant)，即在统计上无法产生2个散列值相同的预映射。给定M，计算上无法找到M'，满足H(M)=H(M') ，此谓弱抗冲突性；计算上也难以寻找一对任意的M和M'，使满足H(M)=H(M') ，此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)"，在一个10人的团体中，你能找到和你生日相同的人的概率是24%，而在同一团体中，有2人生日相同的概率是117%。类似的，当预映射的空间很大的情况下，算法必须有足够的强度来保证不能轻易找到"相同生日"的人。

第三是映射分布均匀性和差分分布均匀性，散列结果中，为 0 的 bit 和为 1 的 bit ，其总数应该大致相等；输入中一个 bit 的变化，散列结果中将有一半以上的 bit 改变，这又叫做"雪崩效应(avalanche effect)"；要实现使散列结果中出现 1bit 的变化，则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息，尽量均匀的反映到输出的每一个 bit 上去；输出中的每一个 bit，都是输入中尽可能多 bit 的信息一起作用的结果。

Damgard 和 Merkle 定义了所谓"压缩函数(compression function)"，就是将一个固定长度输入，变换成较短的固定长度的输出，这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复"压缩"输入的分组和前一次压缩处理的结果的过程，直到整个消息都被压缩完毕，最后的输出作为整个消息的散列值。尽管还缺乏严格的证明，但绝大多数业界的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息也将是安全的。这就是所谓 Damgard/Merkle 结构：

在下图中，任意长度的消息被分拆成符合压缩函数输入要求的分组，最后一个分组可能需要在末尾添上特定的填充字节，这些分组将被顺序处理，除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外，当前分组将和前一个分组的压缩函数输出一起被作为这一次压缩的输入，而其输出又将被作为下一个分组压缩函数输入的一部分，直到最后一个压缩函数的输出，将被作为整个消息散列的结果。

MD5 和 SHA1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

1) MD4

MD4(RFC 1320)是 MIT 的 Ronald L Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位 *** 作数的位 *** 作来实现的。它的安全性不像RSA那样基于数学假设，尽管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻击了它3轮变换中的 2 轮，证明了它并不像期望的那样安全，但它的整个算法并没有真正被破解过，Rivest 也很快进行了改进。

下面是一些MD4散列结果的例子：

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0

MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24

MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d

MD4 ("message digest") = d9130a8164549fe818874806e1c7014b

MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9

MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4

MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

2) MD5

MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。它较MD4所做的改进是：

1) 加入了第四轮

2) 每一步都有唯一的加法常数；

3) 第二轮中的G函数从((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 变为 ((X ∧ Z) ∨ (Y ∧ ～Z))以减小其对称性；

4) 每一步都加入了前一步的结果，以加快"雪崩效应"；

5) 改变了第2轮和第3轮中访问输入子分组的顺序，减小了形式的相似程度；

6) 近似优化了每轮的循环左移位移量，以期加快"雪崩效应"，各轮的循环左移都不同。

尽管MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

消息首先被拆成若干个512位的分组，其中最后512位一个分组是"消息尾+填充字节(1000)+64 位消息长度"，以确保对于不同长度的消息，该分组不相同。64位消息长度的限制导致了MD5安全的输入长度必须小于264bit，因为大于64位的长度信息将被忽略。而4个32位寄存器字初始化为A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它们将始终参与运算并形成最终的散列结果。

接着各个512位消息分组以16个32位字的形式进入算法的主循环，512位消息分组的个数据决定了循环的次数。主循环有4轮，每轮分别用到了非线性函数

F(X, Y, Z) = (X ∧ Y) ∨ (～X ∧ Z)

G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ～Z)

H(X, Y, Z) =X ⊕ Y ⊕ Z

I(X, Y, Z) = X ⊕ (Y ∨ ～Z)

这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下 *** 作：将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果与第4个相加，再加上32位字和一个32位字的加法常数，并将所得之值循环左移若干位，最后将所得结果加上a、b、c、d之一，并回送至ABCD，由此完成一次循环。

所用的加法常数由这样一张表T[i]来定义，其中i为164，T[i]是i的正弦绝对值之4294967296次方的整数部分，这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性性。

当所有512位分组都运算完毕后，ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子：

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661

MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72

MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0

MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b

MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f

MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a

参考相应RFC文档可以得到MD4、MD5算法的详细描述和算法的C源代码。

3) SHA1 及其他

SHA1是由NIST NSA设计为同DSA一起使用的，访问http://wwwitlnistgov/fipspubs可以得到它的详细规范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。因为它将产生160bit的散列值，因此它有5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是4轮，但每轮进行20次 *** 作，非线性运算、移位和加法运算也与MD5类似，但非线性函数、加法常数和循环左移 *** 作的设计有一些区别，可以参考上面提到的规范来了解这些细节。下面是一些SHA1散列结果的例子：

SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1

其他一些知名的Hash算法还有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的这些都属于"纯"Hash算法。还有另2类Hash算法，一类就是基于对称分组算法的单向散列算法，典型的例子是基于DES的所谓Davies-Meyer算法，另外还有经IDEA改进的Davies-Meyer算法，它们两者目前都被认为是安全的算法。另一类是基于模运算/离散对数的，也就是基于公开密钥算法的，但因为其运算开销太大，而缺乏很好的应用前景。

没有通过分析和差分攻击考验的算法，大多都已经夭折在实验室里了，因此，如果目前流行的Hash算法能完全符合密码学意义上的单向性和抗冲突性，就保证了只有穷举，才是破坏Hash运算安全特性的唯一方法。为了对抗弱抗冲突性，我们可能要穷举个数和散列值空间长度一样大的输入，即尝试2^128或2^160个不同的输入，目前一台高档个人电脑可能需要10^25年才能完成这一艰巨的工作，即使是最高端的并行系统，这也不是在几千年里的干得完的事。而因为"生日攻击"有效的降低了需要穷举的空间，将其降低为大约122^64或122^80，所以，强抗冲突性是决定Hash算法安全性的关键。

在NIST新的 Advanced Encryption Standard (AES)中，使用了长度为128、192、256bit 的密钥，因此相应的设计了 SHA256、SHA384、SHA512，它们将提供更好的安全性。

Hash算法在信息安全方面的应用主要体现在以下的3个方面：

1) 文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。它常被用在下面的2种情况下：

第一是文件传送后的校验，将得到的目标文件计算 md5 checksum，与源文件的md5 checksum 比对，由两者 md5 checksum 的一致性，可以从统计上保证2个文件的每一个码元也是完全相同的。这可以检验文件传输过程中是否出现错误，更重要的是可以保证文件在传输过程中未被恶意篡改。一个很典型的应用是ftp服务，用户可以用来保证多次断点续传，特别是从镜像站点下载的文件的正确性。

更出色的解决方法是所谓的代码签名，文件的提供者在提供文件的同时，提供对文件Hash值用自己的代码签名密钥进行数字签名的值，及自己的代码签名证书。文件的接受者不仅能验证文件的完整性，还可以依据自己对证书签发者和证书拥有者的信任程度，决定是否接受该文件。浏览器在下载运行插件和java小程序时，使用的就是这样的模式。

第二是用作保存二进制文件系统的数字指纹，以便检测文件系统是否未经允许的被修改。不少系统管理/系统安全软件都提供这一文件系统完整性评估的功能，在系统初始安装完毕后，建立对文件系统的基础校验和数据库，因为散列校验和的长度很小，它们可以方便的被存放在容量很小的存储介质上。此后，可以定期或根据需要，再次计算文件系统的校验和，一旦发现与原来保存的值有不匹配，说明该文件已经被非法修改，或者是被病毒感染，或者被木马程序替代。TripWire就提供了一个此类应用的典型例子。

更完美的方法是使用"MAC"。"MAC" 是一个与Hash密切相关的名词，即信息鉴权码(Message Authority Code)。它是与密钥相关的Hash值，必须拥有该密钥才能检验该Hash值。文件系统的数字指纹也许会被保存在不可信任的介质上，只对拥有该密钥者提供可鉴别性。并且在文件的数字指纹有可能需要被修改的情况下，只有密钥的拥有者可以计算出新的散列值，而企图破坏文件完整性者却不能得逞。

2) 数字签名

Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。

在这种签名协议中，双方必须事先协商好双方都支持的Hash函数和签名算法。

签名方先对该数据文件进行计算其散列值，然后再对很短的散列值结果--如Md5是16个字节，SHA1是20字节，用非对称算法进行数字签名 *** 作。对方在验证签名时，也是先对该数据文件进行计算其散列值，然后再用非对称算法验证数字签名。

对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点：

首先，数据文件本身可以同它的散列值分开保存，签名验证也可以脱离数据文件本身的存在而进行。

再者，有些情况下签名密钥可能与解密密钥是同一个，也就是说，如果对一个数据文件签名，与对其进行非对称的解密 *** 作是相同的 *** 作，这是相当危险的，恶意的破坏者可能将一个试图骗你将其解密的文件，充当一个要求你签名的文件发送给你。因此，在对任何数据文件进行数字签名时，只有对其Hash值进行签名才是安全的。

3) 鉴权协议

如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

需要鉴权的一方，向将被鉴权的一方发送随机串（"挑战"），被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较（"认证"），如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。

POP3协议中就有这一应用的典型例子：

S: +OK POP3 server ready <1896697170952@dbcmtviewcaus>

C: APOP mrose c4c9334bac560ecc979e58001b3e22fb

S: +OK maildrop has 1 message (369 octets)

在上面的一段POP3协议会话中，双方都共享的对称密钥（鉴权口令字）是tanstaaf，服务器发出的挑战是<1896697170952@dbcmtviewcaus>，客户端对挑战的应答是MD5("<1896697170952@dbcmtviewcaus>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb，这个正确的应答使其通过了认证。

散列算法长期以来一直在计算机科学中大量应用，随着现代密码学的发展，单向散列函数已经成为信息安全领域中一个重要的结构模块，我们有理由深入研究其设计理论和应用方法。

hash（哈希）算法、MD5都属于单向散列函数。不同的是，不同源数据的hash算法结果可能相同，而MD5不会相同。即：hash是多对一函数，md5属于一对一函数。MD5一般用于数据的可信性校验，有时也用于密码的单向加密（但是现在这种加密结果可以被破解）。

目前为止，本书中只讨论到对称加密。假设一个密码系统不只有一个密钥，而是有一对密钥，其中公钥可以自由地发布，而私钥由自己保管。其他人可以使用你的公钥来加密数据，这个信息只有你的私钥可以解密，这个被称为 公钥加密（public-key encryption）

很长一段时间，这都被认为是不可能的。然而从1970年开始，这一类型的算法开始出现。第一个广为流传的是MIT的三位密码学家：Ron Rivest，Adi Shamir 和Leonard Adleman提出的RSA。

公钥算法并不仅仅用来加密，实际上本书之前的部分已经提到过公钥算法而其不是直接用在加密上。有三个与公钥算法相关的主题

从表面来看，公钥加密好像可以淘汰之前提到的对称密钥算法。对于任何事情都可以使用公钥加密，也不需要对称密钥系统中的密钥交换过程。然而在实际的密码学系统中，可以看到到处都是混合的加密，公钥加密在其中起着重要作用，但是大部分的加解密以及认证工作还是基于对成密钥算法的。

目前来看最重要的原因是性能。与流密码（原生的流密码或者其他）算法相比，公钥加密机制实在是太慢了。RSA通常情况下需要2048位也就是256个字节。其加密需要029百万次循环，解密需要1112百万次循环。而对称加密和解密只需要每字节约10次循环。这也意味着在对称密钥算法中，解密256位数据，只需要3000次循环，这个效率是非对称版本的4000次。而目前的密码系统使得对称加密更快了，在AES-GCM硬件加速或者Salsa20/ChaCha20只需要2或者4次每字节，更大程度上提高了性能。

实际的密码系统中还有更多其他的问题。例如对于RSA来说，它不能加密任何比它大的信息，通常情况是小于或者等于4096位，比大部分的需求要小的多。当然最重要的问题依然是上述的速度的问题。

本节简单描述RSA背后的数学问题。其本身并不能产生安全加密机制。之后会看到在其上构造的密码指导OAEP。

为了产生一个key，需要挑选两个大素数p和q，这些数需要随机私密的挑选。将两者相乘的到N，这个是公开的。然后选择一个加密指数e，这个也是公开的。通常这个数是3或者65537因为这些数的二进制形式中仅有很少量的1。计算指数会更有效。（N，e）是公钥，任何人都可以用公钥来加密消息M，得到密文C。

接下来的问题是解密，有一个解密指数d，可以将C转化会M。如果指导p和q，d很容易计算。可以使用d来解密消息：

RSA的安全性依赖于对于不知道d的人来说解密 *** 作是不可能的，并且在只知道（N，e）的情况下d的计算是非常难的。

类似于很多密码系统，RSA依赖于特定数学问题的难度。给定密文C，和公钥（N，e），反推出明文M。这被称为RSA难题。

最直接的方法是将N分解为pq。给定p和q，攻击者只需要重复密钥拥有者的过程来计算产生d即可。

幸运的是，没有一个算法可以在合理的时间内分解这么大的数。不幸的是，目前也无法证明该算法一定不存在。更加糟糕的是，有一个理论上的算法，被称为Shor's Algorithm，可以在量子计算机上在合理的时间内分解一个数。目前，量子计算机还离我们有些远，但是未来某天可能就会成为现实。到时候RSA就变得不再有效。

本节中仅仅提到了分解大数这个最直接的方式来攻击RSA。在接下来的部分可以看到一系列针对RSA的实际攻击，其主要依赖于一些具体的实现。

目前，没有已知的实际的攻破RSA的方法。但这不意味着使用RSA的系统没有被攻破过。和其他被攻破的系统一样，应用中有很多组成部分，一旦其中的某部分没有恰当的使用，就会使整个系统变得不可用。更多有关RSA实施的细节的，参考Bon99和AV96，本部分只提及一些有趣的部分。

Salt是一个用python写的供应系统。它有一个模块叫做 cypto ，它没有使用已有的密码学系统，而是实现了一个自己的，其中使用的RSA和AES由第三方库提供。

很长一段时间里，Salt使用的公钥指数e是1，这也就意味着P e=P 1=P(mod N)。这也就意味着结果的密文就是明文。目前该问题已经被修复，这里只是为了提醒大家，不要实现自己的加密系统。Salt现在支持了SSH作为传输蹭，但是先前提到的DIY的RSA/AES系统依然存在，并且还是默认的传输层。

OAEP是Optimal asymmetric encryption padding的简称，是RSA填充的一种。它的结构类似于下图（文档中这个图有问题，下面是正确的图）：

最终产生的需要被加密的数据是X||Y，是n位长，这个n是N的位数。它使用一个随机的块R它的长度是k，在这个标准中，k是一个定值。消息首先需要用0填充被扩充到n-k位。图中左边的长度为n-k位，右边的长度为k。随机块R和以0扩充的M，M||000使用两个陷阱函数，G和H。陷阱函数都是从一个方向计算非常简单，但是逆转非常的难。世纪中通常为hash函数。

G的输入是k位，输出是n-k位，H的输入是n-k位，输出是k位。

然后结果的X和Y被连接在一起，然后由标准的RSA来进行加密产生密文。

解密的时候，要反过来 *** 作。接收者收到X||Y，他们是指导k的，因为这个是协议里的定值。所以前n-k是X，后k位是Y。

想要得到M，M||000,需要去计算

可以看出，对于一些H和G来说，需要所有的X和Y才能找到M。对于H和G有很多种基于Hash函数的选择。

绝大多数的公钥加密只能一次加密一小块，一般都远小于要发送的信息。另外这些算法还很慢，比对称加密要慢的多。通常非对称加密用来连接密码系统。

有了公钥密码和密钥交换，是密码学里面两个非常重要的部分，因为人们总是需要与其他人交换私密的信息。有了这两个技术就可以安全地和其他人交流。

目前为止讨论的加密都没有任何形式的身份认证。这也就意味着对消息进行加密和解密，并不能验证得到的消息确实是发送者发送的原本的消息。

没有身份认证的加密可以提供隐私性，但是如之前章节所言，没有身份认证，尽管攻击者不知道任何原文的信息，他任然可以修改加密的信息。接收这些消息会泄漏一些私密的信息，这也就意味着私密性不在。例如之前第7章提到的CBC的填充攻击。

综上所言，出了加密私密的信息之外，还需要对其进行身份认证。通常身份认证都是对消息增加一些额外的可计算的信息。类似于加密，身份认证也分为对称类型的和非对称类型的。对称类型的通常被称为消息认证（message authentication），非对称类型的通常被称为数字签名。

下一章先介绍一下另一个密码学中的重点：hash函数。hash在产生签名和消息认证等过程中都需要用到。

[Bon99] Dan Boneh Twenty years of attacks on the RSA cryptosystem Notices of the AMS , 46:203–213, 1999 URL: http://cryptostanfordedu/dabo/papers/RSA-surveypdf

[AV96] Ross Anderson and Serge Vaudenay Minding your pʼs and qʼs In In Advances in Cryptology - ASIACRYPT’96, LNCS 1163 , 26–35 Springer� Verlag, 1996 URL: http://wwwclcamacuk/~rja14/Papers/psandqspdf

哈希值，又称：散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。

散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。

散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

扩展资料：

哈希值的性质：

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。

这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。

但也可能不同，这种情况称为“散列碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。

输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

典型的散列函数都有非常大的定义域，比如SHA-2最高接受(2-1)/8长度的字节字符串。同时散列函数一定有着有限的值域，比如固定长度的比特串。

在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的单射。散列函数必须具有不可逆性。

-哈希值