单向函数的密码学应用
2017-03-11费如纯
费如纯
(辽宁科技学院 曙光大数据学院，辽宁 本溪 117004)
单向函数的密码学应用
费如纯
(辽宁科技学院 曙光大数据学院，辽宁 本溪 117004)
文章讨论了单向函数的定义、安全性要求以及单向函数在密码学中的应用，涉及对称钥密码算法、报文摘要算法及公开钥密码算法，进一步阐明了密码系统的基本思想：只要构造出足够安全的单向函数，就可以以之为基础构造足够安全的密码系统。
单向函数；对称钥算法；报文摘要算法；公开钥算法
随着计算机网络的不断发展，信息技术已经深入到社会生活的方方面面，然而网络攻击和信息窃取事件也越来越成为人们关注的焦点。信息安全关系国计民生，不容忽视。信息安全的基础是密码学，而密码学则基于计算复杂性理论。合法用户对重要信息进行加密以及合法的授权用户对信息进行解密应该是能够快速完成的，即多项式时间可计算的；而非法用户要窃取机密信息则必须对已经加密的信息进行解密，这要求他必须为非法破译付出不可思议的巨大计算代价，即攻击者即使具有庞大的计算资源，他在现有科技条件下完成破译工作也要花费指数时间，这样就使得机密信息成为计算安全的。
本文对单向函数的定义、安全性要求以及单向函数在密码学中的应用进行了讨论，强调了单向函数对安全密码系统的重要性。
1 单向函数与私钥密码系统
单向函数与私钥密码系统有紧密的关系，可以说，私钥密码系统的基础就是具有足够安全性的单向函数。
1.1 保长函数及置换
定义1：设f：∑*→∑*是一个函数，如果对于每一个x，x和f(x)是等长的，则称函数f是一个保长函数，否则f是非保长函数〔1〕。
很明显，如果保长函数f的原象空间和象空间都是均匀分布的，则原象空间和象空间的熵是相同的，即信息量相同。一般来说，目前流行的对称钥密码系统的加密变换和解密变换都是保长的，如数据加密标准DES、高级加密标准AES、国际加密算法IDEA等〔2,3〕。而目前广泛使用的报文摘要算法所采用的单向函数是非保长的，如MD5和SHA-1〔2〕都
是将任意长的报文变换为128比特的摘要。
定义2：设f：∑*→∑*是一个函数，如果已知x，不存在y≠x使得f(x)=f(y)，则称函数f是一个置换〔1〕。
可以看出，如果置换f的原象空间和象空间是等阶的，则任意一个原象都存在与之对应的唯一的一个象，任意一个象都存在与之对应的唯一的一个原象，显然f是一个一一映射。对于诸如DES、IDEA、AES等对称钥密码系统的加解密变换，不同明文必然要变换为不同密文，不同密文必然会解密为不同明文，所以它们都属于置换，而诸如MD5、SHA-1等报文摘要算法则可能将不同的报文变换为相同的摘要，很明显，它们不是置换。
1.2 单向函数
定义3：单向置换f是一个保长置换，它满足如下性质〔1〕：
(1) f是多项式时间可计算的；
(2) 对于每一台多项式时间概率图灵机M、每一个k和足够大的n，都有Pr[M(f(x))=x]≤n-k，这里x是随机选择的长度为n的串。
根据单向置换的定义可知，如果已知x则很容易求出f(x)(多项式时间可计算)，但已知y很难求出一个x使得y=f(x)，即难以求逆。由定义3的(2)，对于任意的多项式时间概率图灵机，能够根据f(x)反演x的概率不大于n-k，实际上就是否认了单向置换的多项式时间反演算法的存在性。
定义4：单向函数f是一个保长函数，它满足如下性质〔1〕：
(1) f是多项式时间可计算的；
(2) 对于每一台多项式时间概率图灵机M、每一个k和足够大的n，都有Pr[M(f(x))=y，其中f(x)=f(y)]≤n-k，这里x是随机选择的长度为n的串。
根据单向函数的定义可知，如果已知x则很容易求出f(x)(多项式时间可计算)，但已知x很难求出一个y使得f(x)=f(y)，即难以找到碰撞。由定义4的(2)，对于任意的多项式时间概率图灵机，能够找到碰撞的概率不大于n-k，实际上就是否认了单向函数的多项式时间反演算法的存在性。
这里的单向置换和单向函数的定义都是理想化的。实际上，单向置换和单向函数的存在性是未证明的。目前在密码学中所使用的都是“所谓的”单向置换和单向函数，只要目前尚未找到它们的多项式时间反演或碰撞算法，我们就暂时认为它们是单向的。虽然我们不能证明所采用的单向函数是理论上安全的，但只要能够保证现实的计算安全就可以了。
1.3 密码学中的单向函数
在密码学中所使用的单向函数有如下几种类型：单向散列函数和陷门单向函数。单向散列函数一般也称为单向Hash函数，它一般是非保长的，这和严格的单向函数的定义有较大的出入。单向散列函数一般用于报文摘要算法。陷门单向函数是带有陷门的单向函数，一般是保长的，用于对称钥加密解密算法。所谓陷门即只有授权使用者知道却不为非授权用户所知的秘密，利用陷门进行单向函数的反演是多项式时间可计算的。
在密码学中所使用的单向函数f需要满足如下安全性要求〔2-4〕：
(1) 已知x，计算f(x)可在多项式时间内完成；
(2) 已知y，求解x使之满足y=f(x)是非常困难的，暂无多项式时间算法；
(3) 抗碰撞性；
(4) 对输入的变化非常敏感；
(5) 映射分布均匀性(均衡性)；
(6) 相关免疫性；
(7) 非线性性。
上述安全性要求中前三条是最基本的。抗碰撞性分为两种：弱抗碰撞性和强抗碰撞性。如果已知x，难以在多项式时间求解y满足f(x)=f(y)，则称单向函数f具有弱抗碰撞性。如果攻击者难以在多项式时间找到x和y满足f(x)=f(y)，则称单向函数f具有强抗碰撞性。强抗碰撞性比弱抗碰撞性的要求更高，也更符合密码学的要求。对输入的变化非常敏感即指雪崩效应，当单向函数的输入发生微小变化时，输出所发生的变化要尽可能大，一般要求输入的任意一个比特发生变化都将引发至少一半的输出比特发生变化。映射分布均匀性是指单向函数的结果要尽可能分布均匀，并且每个输出结果中“0”比特和“1”比特的个数要均衡。设单向函数具有n个变元，如果函数值与任意t个变元是线性无关的，而与某t+1个变元相关，则称该单向函数的相关免疫阶为t，单从这一个角度来看，单向函数的相关免疫阶越高越好。
1.4 单向函数与对称钥密码系统
定义5：在保证计算安全的密码学中，陷门单向函数f是满足如下条件的单向函数：
(1) 已知k和m，在k作用下求c=fk(m)是多项式时间可计算的；
(2) 在未知k而已知c时，求m使得c=fk(m)尚不存在多项式时间概率算法；
(3) 在已知k和c时，求m使得c=fk(m)是多项式时间可计算的。
很明显，利用陷门单向函数可以构造对称钥密码系统，其中m作为明文，c作为密文，k作为密钥(陷门)，函数f作为加密算法，条件(1)是指加密用户用密钥可以快速对明文进行加密，条件(3)是指解密用户用与加密密钥相同的密钥可以快速对密文进行解密，在此条件下函数f可逆，而条件(2)是指窃听者在不掌握密钥的情况下进行破译是计算上不可行的。陷门单向函数一般是保长的。
1.5 单向函数与报文摘要
除了对称钥密码系统以外，单向函数在密码学中的另一个广泛的应用领域是报文摘要算法，所使用的单向函数称为单向散列函数。
单向散列函数的输入是一个可能很大的报文。将长报文分成若干大小相同的分组依次输入，产生定长的输出，再反馈回去与下一个分组共同作为输入，依次类推，最后一个输出作为整个报文的摘要。因此，无论输入的报文长度如何，报文摘要算法产生的输出都是等长的。
基于单向函数的报文摘要算法可以用于对报文进行完整性检查。当发送方发送一个报文时，也将该报文的摘要一起进行发送，接收方收到报文后计算该报文的摘要，将它与接收到的摘要相比较，以确定报文内容在传输过程中是否发生改变。为防止攻击者篡改报文，报文摘要算法一般与数字签名算法相结合来保证报文的完整性和发送方的不可否认性。
2 天窗函数与公钥密码系统
2.1 天窗函数
定义6：设有函数族{fi}，用一个函数表示为f：∑*×∑*→∑*，对每一个i∈∑*和m∈∑*，f(i,m)=fi(m)。称f为标引函数〔1〕。
设M表示明文空间，K表示密钥空间，C表示密文空间，显然，加密变化E：K×M→C和解密变换D：K×C→M均属于标引函数。
定义7：天窗函数f是带有辅助的多项式时间概率图灵机G和辅助函数h的标引函数，满足如下性质〔1〕：
(1) f和h是多项式时间可计算的；
(2) 令
(3) 对于每一个n、每一个长为n的x、G输出的每一个
从天窗函数的定义可以看出，标引函数f和辅助函数都是易于计算的，但在已知i而未知t的情况下难以对标引函数进行反演，而在已知i和t的情况下利用辅助函数h则易于对标引函数f进行反演。实际上，天窗函数可以归类于陷门单向函数，t提供了反演f的陷门。
2.2 天窗函数与公钥密码系统
根据天窗函数的定义，令m为明文，c为密文，则利用天窗函数可以构造公钥密码系统，其中公开钥为i，秘密钥为t，加密变换为c= fi(m)，解密变换为m=h(t, c)，在这里，要求函数fi是一一映射或一对多映射。公钥密码系统很重要的一个组成部分是公开钥、秘密钥的生成，则天窗函数定义中的辅助的多项式时间概率图灵机G即可作为密钥对生成器。
已知公开钥i，加密方很容易用函数f对明文m进行加密，形成密文c；合法的解密方已知秘密钥t，很容易利用函数h对密文c进行解密，得到明文m；攻击者不知道秘密钥t，他利用公开钥i、加密函数f和解密函数h要获得密文c所对应的明文m是异常困难、计算上行不通的。显然，从公开钥i难以导出秘密钥t是最起码一项要求。
3 结论
从上述讨论可知，单向函数无论对私钥密码系统还是对公钥密码系统都是至关重要的，是这些密码系统的基础，只有设计足够安全的单向函数，才能够在此基础上设计安全的密码系统。
〔1〕 Sipser M.著，段磊译．计算理论导引(第三版)〔M〕．北京：机械工业出版社，2015．
〔2〕 杨波．现代密码学〔M〕．北京：清华大学出版社，2015．
〔3〕 吴文玲，冯登国，张文涛．分组密码的设计与分析〔M〕．北京：清华大学出版社，2009．
〔4〕 胡予濮，张玉清，肖国镇．对称密码学〔M〕．北京：机械工业出版社，2002．
Cryptographic Application of One-way Functions
FEI Ru-chun
(DawnSchoolofBigdata,LiaoningInstituteofscienceandTechnology,Benxi,Liaoning, 117004,China)
This paper discusses the definition, security and cryptographic application of one-way function, involving symmetrical key cryptography algorithms, message digest algorithms and public key cryptography algorithms, and illuminates the basic idea of cryptosystem: if a one-way function with strong security is constructed, a cryptosystem with strong security can be designed on the basis of the constructed one-way function.
One-way Function；Symmetrical Key Algorithm； Message Digest Algorithm；Public Key Algorithm
10.3969/j.issn.1008-3723.2017.01.001
(j)cnki 1008-3723 2017.01.001
2016-12-09
费如纯(1968-)，男，河北昌黎人，辽宁科技学院曙光大数据学院教授，博士。研究方向：大数据，信息安全.
TP309.3
A
