3.4 单向函数加密_解构区块链-QQ阅读男生轻小说网

上QQ阅读APP看书，第一时间看更新

3.4　单向函数加密

密码学中有一种特殊类型的加密技术，但称其为加密实在有点勉为其难，第一因为其不支持解密，第二通常没有密钥。

Alice带来一个筒形背包，里面装的圆柱形的木块的直径与背包一致，恰好装得满满当当。Alice边把木块取出来边对Bob说：“这些木块圆柱直径相等，高度不等，问怎么求背包高度？”

“算这个初等数学题我还是游刃有余的。”Bob不假思索地刷刷写下一个算式：

“这里h_i是各种木块的高度，n_i是背包中这种木块的块数，h就是你背包的高度。”

“好。换一个问题。”Alice当然不会考Bob如此简单的问题，后面肯定会有个大坑在等着，“假如我告诉你各种木块的高度，还告诉你背包的高度，问各需要多少块不同木块正好装满背包？”

Bob认真想了想，无奈地回答：“这是多元一次方程，除非有更多的条件构成方程组，否则只能凑数求解。”

Alice所提的正是有名的背包问题（knapsack problem）。设高度值h_i为已知系数，各种高度对应的块数的集合{n_i}为数据，则从数据计算总高度h是非常容易的，而从总高度反推数据则非常困难。

相似的还有离散对数问题：令质数p满足p-1含有另一大质因子q及一整数g（1＜g＜p-1）。给定整数x，求y=g^x mod p，只需要有限次的乘法运算；但如果给定y、g和p，要求解x，则除了暴力尝试别无他法，在计算上不可行。

3.4.1　单向函数技术原理

单向函数（one-way function）运用了背包问题的原理，如图3.24所示，将原消息作为函数的输入（相当于{n_i}），函数的输出（相当于h）为消息摘要（message digest）。单向函数是将原消息进行处理后生成固定长度（一般比原消息短很多）的数据，无法还原，这是其名为单向的原因所在。单向函数又称为哈希函数（hash function），消息摘要就称为原消息的哈希（hash）。

图3.24　单向函数原理图

哈希值能够在统计上唯一地表征输入值，即把消息进行数学意义上的内容摘要，但从摘要中无法得到比摘要本身更多的关于原有消息的信息，具有安全性。哈希算法需要满足以下关键特性：

（1）单向性。从输入值能够简单、迅速地得到哈希值，而反过来在计算上不可行。

（2）抗冲突性（collision resistant）。给定M，计算上难以找到M′，满足H（M）=H（M′），此谓弱抗冲突性；如果计算上也难以寻找一对任意的M和M′，满足H（M）=H（M′），此谓强抗冲突性。抗冲突性在某种程度上可以认为就是哈希的唯一性。

（3）分布均匀性。存在映射分布均匀性和差分分布均匀性。哈希值中，0和1的数量应该大致相等；输入中每1b的变化，哈希值中应有一半以上的位改变，这被称为雪崩效应（avalanche effect）；反之，要实现使哈希值中出现1b的变化，则输入中至少有一半以上的位必须发生变化。分布均匀性本质上是必须使输入中每一位的信息，尽量均匀地反映到输出的每一位上去，同时输出中的每一位，都是输入中尽可能多的位一起作用的结果。

单纯从理论上看，原消息的编码空间巨大，例如照片、电影，动辄几兆、几百兆字节，而哈希仅有数十个字节长度，编码空间相对很小，哈希冲突的概率应当很高才对。然而，考查实际的数据对象，以英文文章为例，每个字节的256个不同编码中可读ASCII字符只占不到一半，文章大部分字符都是小写字母，有效编码空间大幅缩小，再考虑到文章不是字母的胡乱组合，而是字母构成数量有限的单词、单词组成有意义的语句，这就进一步压缩了编码空间。因此，修改一篇文章，至少要通顺，表达的意思上达到篡改的目的，还要使之输出相同的哈希，无疑是天方夜谭。

单向函数因为具备这些独特的性质，可在信息安全领域发挥巨大作用。哈希携带了原消息的内容特征，不同的消息有不同的哈希，因此也称其为数字指纹（digital fingerprint），就好比人类的指纹可以用来“画押”，与亲笔签名有同等效力，可以用来代表一个人。犯罪现场的指纹鉴定也是同理。

例如，有一份带上哈希的电子合同，如图3.25所示，倘若合同被篡改，哪怕只是改了一个小数点，用同样的单向函数得到的哈希将发生巨大的变化，而且几乎不可能伪造一份具有相同哈希的合同，所以数字指纹可以用来验证合同真伪。然而，如果合同篡改者同时用虚假合同生成了新的哈希，替换了原有的数字指纹，则反而会带来“虚假的真实”的弊端。因此，数字指纹在实际运用时还需要结合其他密码学技术，例如配合公钥加密，才能切实保障其安全性。

图3.25　数字指纹应用示例

再例如，网络用户在客户端输入用户名、密码（口令）登录几乎是每天要做的事。如果直接把用户输入的密码传送到服务端进行验证，就存在两方面的安全隐患：一是传输过程中可能被窃听，明文密码就暴露了；二是服务端数据库存储的明文密码也有暴露风险（例如被“脱库”或被“内鬼”窃取账号）。为防范登录密码安全风险，网络系统通常采用对密码作哈希的方法，客户端向服务器传输的是密码的哈希值，而服务端存储的也是哈希值，不影响登录验证，也不会暴露用户密码，这是单向函数加密技术的成功应用范例。

但是网络登录密码单纯采用哈希加密手段仍然存在安全风险，例如攻击者截取到哈希值后，至少有两种手法可实现攻击：一种是“重放攻击”，即直接向服务端传送密码哈希值要求登录，服务端会照样放行；另一种是“字典攻击”，即利用事先做好的密码串－哈希值对应表（因为大部分人会用便于记忆的单词和词组来做密码），查表“恢复”密码明文。抵抗这一风险的做法是采用“哈希加盐”的一次性登录（Single-time Sign-On，SSO）方案，如图3.26所示，每次登录使用随机数作为“盐”（salt），与密码哈希拼接后再做哈希，从而实现每次登录都传输不同的密文（随机数可事先传输或随密文传输，不影响安全性）。

图3.26　一次性口令技术原理

单向函数的另一项重要用途是信息标识。如果需要识别大数据量的信息对象，例如不同的电影，“全量比较”费力不讨好，则可生成信息对象的数字指纹，例如32B的定长哈希，作为类似身份证号码的ID，检索时只需出示ID，存储、传输、比对、查找都很便捷。例如网上P2P下载应用就是采用DHT（分布式哈希表）方法，从各个用户终端上寻找大文件的不同片段，实现并发式下载。

比特币系统设计中大量运用了成熟的单向函数加密技术，将单向函数各种技术特点和功能发挥得淋漓尽致：

•　数据缠结——利用哈希对原消息的变化极其敏感的特性，构造数据之间的缠结关系，防范信息篡改和伪造，包括：形成区块之间的链和生成交易默克尔树。

•　信息标识——利用哈希短小（压缩性）、等长、抗冲突等特性，以之为区块和交易的标识，非常便于存储和检索。

•　地址编码——利用哈希单向转换的特性，生成比特币用户地址，既提高了安全性、规范性、隐蔽性，又实现了可验证。

•　交易签名——利用哈希作为原消息数字指纹的特性，对资金归属和使用规则进行签名锁定，并可验证、解锁，实现智能化交易。

常用的单向函数算法有CRC、MD、RIPEMD、SHA等。

3.4.2　CRC算法

循环冗余码（Cyclic Redundancy Check，CRC）通常不被当作单向函数来看待，常用在网络通信中的数据链路层，例如作为传输检错的帧校验序列（Frame Check Sequence，FCS）编码。但CRC码确实就是一种单向函数，而且适合流式数据，可以边传输边计算哈希，具备独特的能力。

CRC码是一种线性分组码，一般为16b或32b数值，编码和解码方法简单，能够达到0.0047%以下漏检率，可检测出所有奇数个随机错误以及长度小于或等于生成多项式阶数的突发错误。

设：生成多项式P（x）为n阶，传输的比特流为M，则生成nb的CRC码R（x）。生成多项式是系数为1或0的一元多次多项式，其最高指数就是阶。例如，P（x）=x⁷+x⁵+x+1，阶为7，对应8b二进制数为10100011。

CRC码计算公式为：R（x）=（M×2ⁿ）modP（x）。即原消息比特流M扩展到n位后作为被除数，并以生成多项式P（x）转换而来的二进制数据为除数，做按位除法，取余数R（x）扩展到n位即为CRC码。

CRC码紧接在M比特流的后面进行传输，信息接收方采用同样的生成多项式进行按位除法运算以验证：R′（x）=（M×2ⁿ+R（x））mod P（x），若R′（x）=0，说明M无差错，否则说明传输有误（存在误码或被篡改）。

如图3.27所示为计算余数的按位除法的竖式运算法示例，其中每一步采用的不是减法，而是按位异或运算。

图3.27　CRC按位除法示例

CRC码生成多项式的选择非常重要，是保障检错能力的基础。国际标准中较常用的生成多项式有：

•　CRC-16=x¹⁶+x¹⁵+x²+1；

•　CRC-CCITT=x¹⁶+x¹²+x⁵+1；

•　CRC-32=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1。

3.4.3　MD算法

消息摘要（Message Digest，MD）是一种经典的单向函数加密算法，由R.Rivest于1989—1992年间开发并升级，分为MD2、MD4和MD5，其中MD5算法使用最为广泛。

MD5以512b（64B）分组为单位来处理输入信息，输出128b（16B）哈希值。

首先对信息进行填充，在信息的尾部填充一个1和连续的0，直到满足位长度对512求余的结果等于448（即n×512+448），其后附加64b原信息长度值（以byte为单位）。

MD5对4个32b的链接变量（chaining variable）分别设置初始值为：V_a=0x01234567，V_b=0x89abcdef，V_c=0xfedcba98，V_d=0x76543210。执行算法流程如下：

（1）令a=V_a，b=V_b，c=V_c，d=V_d。

（2）将输入的512b分组划分成16个32b子分组m_j，j=0，1，2，…，15。

（3）进行4轮运算，每轮由16步组成，每步为K（A，B，C，D，m_j，s，t_i）函数运算（如图3.28所示），K函数表示为：A=B+（（A+k（B，C，D）+m_j+t_i）＞＞s），K∈{F，G，P，Q}，k∈{f，g，p，q}，＞＞s表示循环右移s位，s是常数（图3.28中对应数值）。在第i步中（i=1，2，…，64），以i为弧度值，可计算常数为：t_i=int（2³²×|sin（i）|）。分别用于4轮运算的4个非线性函数如下（每轮一个，均为按位逻辑运算：&与，|或，~非，⊕异或）：

f（x，y，z）=（x&y）|（（~x）&z）

g（x，y，z）=（x&z）|（y&（~z））

p（x，y，z）=x⊕y⊕z

q（x，y，z）=y⊕（x|（~z））

（4）计算：V_a=V_a+a，V_b=V_b+b，V_c=V_c+c，V_d=V_d+d。

（5）若存在更多512b分组，回到（1）继续运算，否则算法结束。

图3.28　MD5 4轮函数运算表

图3.28 (续)

对所有原消息分组运算完毕后，最后输出V_a、V_b、V_c、V_d的级联{V_a|V_b|V_c|V_d}，即为128b（16B）的MD5值。

例如，第2轮的第1步（总第17步）为G（a，b，c，d，m₁，s，t₁₇），表示：

a=b+（（a+g（b，c，d）+m₁+t₁₇）＞＞s）

即为：

a=b+（（a+（（b&d）|（c&（~d）））+m₁+t₁₇）＞＞s）

也即：

a=b+（（a+（（b&d）|（c&（~d）））+m₁+0xf61e2562）＞＞5）

采用MD5加密字符串（例如加密口令）的样例如下（第一个例子为空字符串，即长度为0的字符串）：

      md5(＂＂)=D41D8CD98F00B204E9800998ECF8427E
      md5(＂a＂)=0CC175B9C0F1B6A831C399E269772661
      md5(＂abc＂)=900150983CD24FB0D6963F7D28E17F72
      md5(＂message digest＂)=F96B697D7CB7938D525A2F31AAF161D0
      md5(＂abc…z＂)=C3FCD3D76192E4007DFB496CCA67E13B

可见MD5单向函数生成的哈希具备非常随机的外观，原字符串哪怕仅发生微小的变化，哈希值的很多位都会随之而变，杜绝了推测攻击的可能性。

3.4.4　RIPEMD算法

RIPEMD（RACE Integrity Primitives Evaluation Message Digest）是一种单向函数算法，由Hans Dobbertin、Antoon Bosselaers和Bart Preneel等3人在MD4的基础上于1996年提出，与MD5一样都是着眼于改善MD4存在的安全缺陷。RIPEMD算法共有4个标准RIPEMD-128、RIPEMD-160、RIPEMD-256和RIPEMD-320，其对应输出长度分别为16B、20B、32B和40B。让人难以置信的是256和320这两种标准只是在128和160的基础上修改了初始参数和S-box来达到输出为256b和320b的目的，所以，256的强度和128相当，而320的强度和160位相当。其中RIPEMD-160在比特币系统的地址生成算法中得到运用，在此之前RIPEMD基本上处于默默无闻的状态。

RIPEMD-160算法以32b字为计算单元，输入16个32b字X（i）组成的分组，输出5个32b字（即20B）的级联。输入消息的填充方式与MD5相同。

每个分组的运算进行5轮，每轮分别对16个32b字进行操作，共80步。每一步分为左、右两部分操作，执行逻辑均为：A=（A+f（B，C，D）+X+K）≪s+E；C=C≪10（≪s为循环左移s位，+为模2³²加法）。

定义算法所用的160个32b常量如下所示，其中：K（j）用于左侧操作，K′（j）用于右侧操作，j为0~79步操作步骤（每行为1轮）：

定义r（j）、r′（j）为输入分组的32b字X（i）的选择下标。在不同的轮次及左右侧操作中，16个字的计算次序各有不同。

在一种改进的RIPEMD算法中，设ρ（i）={7，4，13，1，10，6，15，3，12，0，9，5，2，14，11，8}（i=0，1，2，…，15），又设π（i）=9i+5（mod 16），则5轮运算中采用的r（j）、r′（j）为（均为mod 16运算）：

但在标准的RIPEMD算法中，5轮运算中采用的r（j）、r′（j）固定定义为：

      r(j)=j                                                     r′(j)=5，14，7，0，9，2，11，4，13，6，15，8，1，10，3，12  0≤j≤15
      r(j)=7，4，13，1，10，6，15，3，12，0，9，5，2，14，11，8  r′(j)=6，11，3，7，0，13，5，10，14，15，8，12，4，9，1，2  16≤j≤31
      r(j)=3，10，14，4，9，15，8，1，2，7，0，6，13，11，5，12  r′(j)=15，5，1，3，7，14，6，9，11，8，12，2，10，0，4，13  32≤j≤47
      r(j)=1，9，11，10，0，8，12，4，13，3，7，15，14，5，6，2  r′(j)=8，6，4，1，3，11，15，0，5，12，2，13，9，7，10，14  48≤j≤63
      r(j)=4，0，5，9，7，12，2，10，14，1，3，8，11，6，15，13  r′(j)=12，15，10，4，1，5，8，7，6，2，13，14，0，3，9，11  64≤j≤79

各个步骤使用的循环左移位数s（j）和s′（j）（在一种改进的RIPEMD算法中移位次数的定义有所不同，且两侧相同）按标准定义为：

      s(j)=11，14，15，12，5，8，7，9，11，13，14，15，6，7，9，8′  s(j)=8，9，9，11，13，15，15，5，7，7，8，11，14，14，12，6  0≤j≤15
      s(j)=7，6，8，13，11，9，7，15，7，12，15，9，11，7，13，12′  s(j)=9，13，15，7，12，8，9，11，7，7，12，7，6，15，13，11  16≤j≤31
      s(j)=11，13，6，7，14，9，13，15，14，8，13，6，5，12，7，5′  s(j)=9，7，15，11，8，6，6，14，12，13，5，14，13，13，7，5  32≤j≤47
      s(j)=11，12，14，15，14，15，9，8，9，14，5，6，8，6，5，12′  s(j)=15，5，8，11，14，14，6，14，6，9，12，9，12，5，15，8  48≤j≤63
      s(j)=9，15，5，11，6，8，13，12，5，12，13，14，11，8，5，6′  s(j)=8，5，12，9，12，5，14，6，8，13，6，5，15，13，11，11  64≤j≤79

每轮每个步骤的运算所用的5个非线性按位操作函数（⊕异或、∧与、∨或、~非）分别为：

f（j，x，y，z）=x⊕y⊕z　　（0≤j≤15）

f（j，x，y，z）=（x∧y）∨（~x∧z）（16≤j≤31）

f（j，x，y，z）=（x∨~y）⊕z　　（32≤j≤47）

f（j，x，y，z）=（x∧z）∨（y∧~z）　　（48≤j≤63）

f（j，x，y，z）=x⊕（y∨~z）　　（64≤j≤79）

RIPEMD-160算法开始时，首先初始化级联变量：h₀=0x67452301，h₁=0xEFCDAB89，h₂=0x98BADCFE，h₃=0x10325476，h₄=0xC3D2E1F0。算法流程如下：

（1）初始化临时变量。

A=A′=h₀，　B=B′=h₁，　C=C′=h₂，　D=D′=h₃，　E=E′=h₄

（2）对16个32b字X（i）进行5轮共80步左、右两侧的运算。

（3）若存在更多分组，回（1）继续运行；否则算法结束。

最后级联h₀、h₁、h₂、h₃、h₄，即为20B的RIPEMD-160哈希。采用RIPEMD-160单向函数对字符串进行哈希的样例如下：

      RIPEMD160(＂＂)=9C1185A5C5E9FC54612808977EE8F548B2258D31
      RIPEMD160(＂a＂)=0BDC9D2D256B3EE9DAAE347BE6F4DC835A467FFE
      RIPEMD160(＂abc＂)=8EB208F7E05D987A9B044A8E98C6B087F15A0BFC
      RIPEMD160(＂message digest＂)=5D0689EF49D2FAE572B881B123A85FFA21595F36
      RIPEMD160(＂abc…z＂)=F71C27109C692C1B56BBDCEB5B9D2865B3708DBC

3.4.5　SHA算法

安全哈希算法（Secure Hash Algorithm，SHA）是单向函数加密算法之一，包括SHA-1和SHA-2，SHA-2具体分为SHA-224、SHA-256、SHA-384和SHA-512，1995年发布为美国联邦标准。SHA-1在SSL、SSH、S/MIME和IPSec等许多安全协议中广为使用，被视为MD5的继任者，但人们也对其安全性存在质疑，相比之下SHA-2更为安全，其算法与SHA-1基本一致，SHA-256在比特币系统中得到大量运用。

SHA-1以512b（32B）分组为处理单位，输出160b值；SHA-2中SHA-xyz表示输出xyzb值，前两者分组大小与SHA-1相同为512b（32B），后两者为1024b（64B）。

SHA-1算法如下（所有变量为32b字长，计算均为mod 2³²）。

对原消息的预处理与MD5算法相同：在原消息的尾部填充一个1和连续的0，直到满足位长度对512求余的结果等于448（即n×512+448），其后附加64b原消息长度值（以byte为单位）。

设置级联变量初始值为h₀∶=0x67452301，h₁∶=0xEFCDAB89，h₂∶=0x98BADCFE，h₃∶=0x10325476，h₄∶=0xC3D2E1F0。将原消息分为512b长度的分组（Chunk），依次处理每个分组，直到处理完全部分组。

（1）将分组分为16个32b字w[i]（i=0，1，2，…，15）。

（2）将w[i]（i=0，1，2，…，15）扩展成80个32b字（＜＜循环左移，⊕异或）：

（3）临时变量赋值：{a，b，c，d，e}={h₀，h₁，h₂，h₃，h₄}。

（4）主处理程序（循环80轮次；&与，|或，~非）：

（5）级联变量赋值：{h₀，h₁，h₂，h₃，h₄}={h₀+a，h₁+b，h₂+c，h₃+d，h₄+e}。

（6）若已为最后分组，则进行第（7）步；否则返回第（1）步处理下一分组。

（7）Hash值为h₀、h₁、h₂、h₃、h₄顺序级联而成（160b）。

SHA-2算法加强了各个字的位元混合程度，以提升安全强度。以SHA-256为例，算法如下（所有变量为32B字长，计算均为mod 2³²）。

初始化变量：h₀∶=0x6A09E667，h₁∶=0xBB67AE85，h₂∶=0x3C6EF372，h₃∶=0xA54FF53A，h₄∶=0x510E527F，h₅∶=0x9B05688C，h₆∶=0x1F83D9AB，h₇∶=0x5BE0CD19。

对64个常量赋值k[0，1，2，…，63]∶=

续表

（1）将分组分为16个32b字w[i]（i=0，1，2，…，15）。

（2）将w[i]（i=0，1，2，…，15）扩展成64个32b字（＞＞循环右移，＞＞＞逻辑右移，⊕异或，+加）：

（3）临时变量赋值：{a，b，c，d，e，f，g，h}={h₀，h₁，h₂，h₃，h₄，h₅，h₆，h₇}。

（4）主处理程序（循环64轮次；&与，|或，~非）：

（5）中间变量赋值：

{h0，h1，h2，h3，h4，h5，h6，h7}

={h₀+a，h₁+b，h₂+c，h₃+d，h₄+e，h₅+f，h₆+g，h₇+h}。

（6）若已为最后分组，则进行第（7）步；否则返回第（1）步处理下一分组。

（7）Hash值为h₀、h₁、h₂、h₃、h₄、h₅、h₆、h₇顺序链接而成（256b）。

SHA-224与SHA-256的算法基本相同，除了h₀~h₇的初始值不同且SHA-224输出时截掉h₇的值（因此为224b）。SHA-512和SHA-256的结构相同，但是，SHA-512处理64B字，执行80次循环，两者循环移位量不同。SHA-384和SHA-512的不同点为：h₀~h₇的初始值不同，SHA-384输出时截掉了h₆和h₇的值。