單向函數(shù)的密碼學(xué)應(yīng)用

費(fèi)如純

(遼寧科技學(xué)院 曙光大數(shù)據(jù)學(xué)院，遼寧 本溪 117004)

單向函數(shù)的密碼學(xué)應(yīng)用

費(fèi)如純

(遼寧科技學(xué)院 曙光大數(shù)據(jù)學(xué)院，遼寧 本溪 117004)

文章討論了單向函數(shù)的定義、安全性要求以及單向函數(shù)在密碼學(xué)中的應(yīng)用，涉及對(duì)稱鑰密碼算法、報(bào)文摘要算法及公開鑰密碼算法，進(jìn)一步闡明了密碼系統(tǒng)的基本思想：只要構(gòu)造出足夠安全的單向函數(shù)，就可以以之為基礎(chǔ)構(gòu)造足夠安全的密碼系統(tǒng)。

單向函數(shù)；對(duì)稱鑰算法；報(bào)文摘要算法；公開鑰算法

隨著計(jì)算機(jī)網(wǎng)絡(luò)的不斷發(fā)展，信息技術(shù)已經(jīng)深入到社會(huì)生活的方方面面，然而網(wǎng)絡(luò)攻擊和信息竊取事件也越來越成為人們關(guān)注的焦點(diǎn)。信息安全關(guān)系國計(jì)民生，不容忽視。信息安全的基礎(chǔ)是密碼學(xué)，而密碼學(xué)則基于計(jì)算復(fù)雜性理論。合法用戶對(duì)重要信息進(jìn)行加密以及合法的授權(quán)用戶對(duì)信息進(jìn)行解密應(yīng)該是能夠快速完成的，即多項(xiàng)式時(shí)間可計(jì)算的；而非法用戶要竊取機(jī)密信息則必須對(duì)已經(jīng)加密的信息進(jìn)行解密，這要求他必須為非法破譯付出不可思議的巨大計(jì)算代價(jià)，即攻擊者即使具有龐大的計(jì)算資源，他在現(xiàn)有科技條件下完成破譯工作也要花費(fèi)指數(shù)時(shí)間，這樣就使得機(jī)密信息成為計(jì)算安全的。

本文對(duì)單向函數(shù)的定義、安全性要求以及單向函數(shù)在密碼學(xué)中的應(yīng)用進(jìn)行了討論，強(qiáng)調(diào)了單向函數(shù)對(duì)安全密碼系統(tǒng)的重要性。

1 單向函數(shù)與私鑰密碼系統(tǒng)

單向函數(shù)與私鑰密碼系統(tǒng)有緊密的關(guān)系，可以說，私鑰密碼系統(tǒng)的基礎(chǔ)就是具有足夠安全性的單向函數(shù)。

1.1 保長函數(shù)及置換

定義1：設(shè)f：∑*→∑*是一個(gè)函數(shù)，如果對(duì)于每一個(gè)x，x和f(x)是等長的，則稱函數(shù)f是一個(gè)保長函數(shù)，否則f是非保長函數(shù)〔1〕。

很明顯，如果保長函數(shù)f的原象空間和象空間都是均勻分布的，則原象空間和象空間的熵是相同的，即信息量相同。一般來說，目前流行的對(duì)稱鑰密碼系統(tǒng)的加密變換和解密變換都是保長的，如數(shù)據(jù)加密標(biāo)準(zhǔn)DES、高級(jí)加密標(biāo)準(zhǔn)AES、國際加密算法IDEA等〔2,3〕。而目前廣泛使用的報(bào)文摘要算法所采用的單向函數(shù)是非保長的，如MD5和SHA-1〔2〕都

是將任意長的報(bào)文變換為128比特的摘要。

定義2：設(shè)f：∑*→∑*是一個(gè)函數(shù)，如果已知x，不存在y≠x使得f(x)=f(y)，則稱函數(shù)f是一個(gè)置換〔1〕。

可以看出，如果置換f的原象空間和象空間是等階的，則任意一個(gè)原象都存在與之對(duì)應(yīng)的唯一的一個(gè)象，任意一個(gè)象都存在與之對(duì)應(yīng)的唯一的一個(gè)原象，顯然f是一個(gè)一一映射。對(duì)于諸如DES、IDEA、AES等對(duì)稱鑰密碼系統(tǒng)的加解密變換，不同明文必然要變換為不同密文，不同密文必然會(huì)解密為不同明文，所以它們都屬于置換，而諸如MD5、SHA-1等報(bào)文摘要算法則可能將不同的報(bào)文變換為相同的摘要，很明顯，它們不是置換。

1.2 單向函數(shù)

定義3：單向置換f是一個(gè)保長置換，它滿足如下性質(zhì)〔1〕：

(1) f是多項(xiàng)式時(shí)間可計(jì)算的；

(2) 對(duì)于每一臺(tái)多項(xiàng)式時(shí)間概率圖靈機(jī)M、每一個(gè)k和足夠大的n，都有Pr[M(f(x))=x]≤n-k，這里x是隨機(jī)選擇的長度為n的串。

根據(jù)單向置換的定義可知，如果已知x則很容易求出f(x)(多項(xiàng)式時(shí)間可計(jì)算)，但已知y很難求出一個(gè)x使得y=f(x)，即難以求逆。由定義3的(2)，對(duì)于任意的多項(xiàng)式時(shí)間概率圖靈機(jī)，能夠根據(jù)f(x)反演x的概率不大于n-k，實(shí)際上就是否認(rèn)了單向置換的多項(xiàng)式時(shí)間反演算法的存在性。

定義4：單向函數(shù)f是一個(gè)保長函數(shù)，它滿足如下性質(zhì)〔1〕：

(1) f是多項(xiàng)式時(shí)間可計(jì)算的；

(2) 對(duì)于每一臺(tái)多項(xiàng)式時(shí)間概率圖靈機(jī)M、每一個(gè)k和足夠大的n，都有Pr[M(f(x))=y，其中f(x)=f(y)]≤n-k，這里x是隨機(jī)選擇的長度為n的串。

根據(jù)單向函數(shù)的定義可知，如果已知x則很容易求出f(x)(多項(xiàng)式時(shí)間可計(jì)算)，但已知x很難求出一個(gè)y使得f(x)=f(y)，即難以找到碰撞。由定義4的(2)，對(duì)于任意的多項(xiàng)式時(shí)間概率圖靈機(jī)，能夠找到碰撞的概率不大于n-k，實(shí)際上就是否認(rèn)了單向函數(shù)的多項(xiàng)式時(shí)間反演算法的存在性。

這里的單向置換和單向函數(shù)的定義都是理想化的。實(shí)際上，單向置換和單向函數(shù)的存在性是未證明的。目前在密碼學(xué)中所使用的都是“所謂的”單向置換和單向函數(shù)，只要目前尚未找到它們的多項(xiàng)式時(shí)間反演或碰撞算法，我們就暫時(shí)認(rèn)為它們是單向的。雖然我們不能證明所采用的單向函數(shù)是理論上安全的，但只要能夠保證現(xiàn)實(shí)的計(jì)算安全就可以了。

1.3 密碼學(xué)中的單向函數(shù)

在密碼學(xué)中所使用的單向函數(shù)有如下幾種類型：單向散列函數(shù)和陷門單向函數(shù)。單向散列函數(shù)一般也稱為單向Hash函數(shù)，它一般是非保長的，這和嚴(yán)格的單向函數(shù)的定義有較大的出入。單向散列函數(shù)一般用于報(bào)文摘要算法。陷門單向函數(shù)是帶有陷門的單向函數(shù)，一般是保長的，用于對(duì)稱鑰加密解密算法。所謂陷門即只有授權(quán)使用者知道卻不為非授權(quán)用戶所知的秘密，利用陷門進(jìn)行單向函數(shù)的反演是多項(xiàng)式時(shí)間可計(jì)算的。

在密碼學(xué)中所使用的單向函數(shù)f需要滿足如下安全性要求〔2-4〕：

(1) 已知x，計(jì)算f(x)可在多項(xiàng)式時(shí)間內(nèi)完成；

(2) 已知y，求解x使之滿足y=f(x)是非常困難的，暫無多項(xiàng)式時(shí)間算法；

(3) 抗碰撞性；

(4) 對(duì)輸入的變化非常敏感；

(5) 映射分布均勻性(均衡性)；

(6) 相關(guān)免疫性；

(7) 非線性性。

上述安全性要求中前三條是最基本的?？古鲎残苑譃閮煞N：弱抗碰撞性和強(qiáng)抗碰撞性。如果已知x，難以在多項(xiàng)式時(shí)間求解y滿足f(x)=f(y)，則稱單向函數(shù)f具有弱抗碰撞性。如果攻擊者難以在多項(xiàng)式時(shí)間找到x和y滿足f(x)=f(y)，則稱單向函數(shù)f具有強(qiáng)抗碰撞性。強(qiáng)抗碰撞性比弱抗碰撞性的要求更高，也更符合密碼學(xué)的要求。對(duì)輸入的變化非常敏感即指雪崩效應(yīng)，當(dāng)單向函數(shù)的輸入發(fā)生微小變化時(shí)，輸出所發(fā)生的變化要盡可能大，一般要求輸入的任意一個(gè)比特發(fā)生變化都將引發(fā)至少一半的輸出比特發(fā)生變化。映射分布均勻性是指單向函數(shù)的結(jié)果要盡可能分布均勻，并且每個(gè)輸出結(jié)果中“0”比特和“1”比特的個(gè)數(shù)要均衡。設(shè)單向函數(shù)具有n個(gè)變元，如果函數(shù)值與任意t個(gè)變元是線性無關(guān)的，而與某t+1個(gè)變元相關(guān)，則稱該單向函數(shù)的相關(guān)免疫階為t，單從這一個(gè)角度來看，單向函數(shù)的相關(guān)免疫階越高越好。

1.4 單向函數(shù)與對(duì)稱鑰密碼系統(tǒng)

定義5：在保證計(jì)算安全的密碼學(xué)中，陷門單向函數(shù)f是滿足如下條件的單向函數(shù)：

(1) 已知k和m，在k作用下求c=fk(m)是多項(xiàng)式時(shí)間可計(jì)算的；

(2) 在未知k而已知c時(shí)，求m使得c=fk(m)尚不存在多項(xiàng)式時(shí)間概率算法；

(3) 在已知k和c時(shí)，求m使得c=fk(m)是多項(xiàng)式時(shí)間可計(jì)算的。

很明顯，利用陷門單向函數(shù)可以構(gòu)造對(duì)稱鑰密碼系統(tǒng)，其中m作為明文，c作為密文，k作為密鑰(陷門)，函數(shù)f作為加密算法，條件(1)是指加密用戶用密鑰可以快速對(duì)明文進(jìn)行加密，條件(3)是指解密用戶用與加密密鑰相同的密鑰可以快速對(duì)密文進(jìn)行解密，在此條件下函數(shù)f可逆，而條件(2)是指竊聽者在不掌握密鑰的情況下進(jìn)行破譯是計(jì)算上不可行的。陷門單向函數(shù)一般是保長的。

1.5 單向函數(shù)與報(bào)文摘要

除了對(duì)稱鑰密碼系統(tǒng)以外，單向函數(shù)在密碼學(xué)中的另一個(gè)廣泛的應(yīng)用領(lǐng)域是報(bào)文摘要算法，所使用的單向函數(shù)稱為單向散列函數(shù)。

單向散列函數(shù)的輸入是一個(gè)可能很大的報(bào)文。將長報(bào)文分成若干大小相同的分組依次輸入，產(chǎn)生定長的輸出，再反饋回去與下一個(gè)分組共同作為輸入，依次類推，最后一個(gè)輸出作為整個(gè)報(bào)文的摘要。因此，無論輸入的報(bào)文長度如何，報(bào)文摘要算法產(chǎn)生的輸出都是等長的。

基于單向函數(shù)的報(bào)文摘要算法可以用于對(duì)報(bào)文進(jìn)行完整性檢查。當(dāng)發(fā)送方發(fā)送一個(gè)報(bào)文時(shí)，也將該報(bào)文的摘要一起進(jìn)行發(fā)送，接收方收到報(bào)文后計(jì)算該報(bào)文的摘要，將它與接收到的摘要相比較，以確定報(bào)文內(nèi)容在傳輸過程中是否發(fā)生改變。為防止攻擊者篡改報(bào)文，報(bào)文摘要算法一般與數(shù)字簽名算法相結(jié)合來保證報(bào)文的完整性和發(fā)送方的不可否認(rèn)性。

2 天窗函數(shù)與公鑰密碼系統(tǒng)

2.1 天窗函數(shù)

定義6：設(shè)有函數(shù)族{fi}，用一個(gè)函數(shù)表示為f：∑*×∑*→∑*，對(duì)每一個(gè)i∈∑*和m∈∑*，f(i,m)=fi(m)。稱f為標(biāo)引函數(shù)〔1〕。

設(shè)M表示明文空間，K表示密鑰空間，C表示密文空間，顯然，加密變化E：K×M→C和解密變換D：K×C→M均屬于標(biāo)引函數(shù)。

定義7：天窗函數(shù)f是帶有輔助的多項(xiàng)式時(shí)間概率圖靈機(jī)G和輔助函數(shù)h的標(biāo)引函數(shù)，滿足如下性質(zhì)〔1〕：

(1) f和h是多項(xiàng)式時(shí)間可計(jì)算的；

(2) 令是G的隨機(jī)輸出，對(duì)于每一個(gè)多項(xiàng)式時(shí)間概率圖靈機(jī)E、每一個(gè)k和足夠大的n以及隨機(jī)的長度為n的串x，都有Pr[E(i, fi(x))=y，其中fi(x)= fi(y)]≤n-k；

(3) 對(duì)于每一個(gè)n、每一個(gè)長為n的x、G輸出的每一個(gè)，都有h(t, fi(x))=y，其中fi(x)= fi(y)。

從天窗函數(shù)的定義可以看出，標(biāo)引函數(shù)f和輔助函數(shù)都是易于計(jì)算的，但在已知i而未知t的情況下難以對(duì)標(biāo)引函數(shù)進(jìn)行反演，而在已知i和t的情況下利用輔助函數(shù)h則易于對(duì)標(biāo)引函數(shù)f進(jìn)行反演。實(shí)際上，天窗函數(shù)可以歸類于陷門單向函數(shù)，t提供了反演f的陷門。

2.2 天窗函數(shù)與公鑰密碼系統(tǒng)

根據(jù)天窗函數(shù)的定義，令m為明文，c為密文，則利用天窗函數(shù)可以構(gòu)造公鑰密碼系統(tǒng)，其中公開鑰為i，秘密鑰為t，加密變換為c= fi(m)，解密變換為m=h(t, c)，在這里，要求函數(shù)fi是一一映射或一對(duì)多映射。公鑰密碼系統(tǒng)很重要的一個(gè)組成部分是公開鑰、秘密鑰的生成，則天窗函數(shù)定義中的輔助的多項(xiàng)式時(shí)間概率圖靈機(jī)G即可作為密鑰對(duì)生成器。

已知公開鑰i，加密方很容易用函數(shù)f對(duì)明文m進(jìn)行加密，形成密文c；合法的解密方已知秘密鑰t，很容易利用函數(shù)h對(duì)密文c進(jìn)行解密，得到明文m；攻擊者不知道秘密鑰t，他利用公開鑰i、加密函數(shù)f和解密函數(shù)h要獲得密文c所對(duì)應(yīng)的明文m是異常困難、計(jì)算上行不通的。顯然，從公開鑰i難以導(dǎo)出秘密鑰t是最起碼一項(xiàng)要求。

3 結(jié)論

從上述討論可知，單向函數(shù)無論對(duì)私鑰密碼系統(tǒng)還是對(duì)公鑰密碼系統(tǒng)都是至關(guān)重要的，是這些密碼系統(tǒng)的基礎(chǔ)，只有設(shè)計(jì)足夠安全的單向函數(shù)，才能夠在此基礎(chǔ)上設(shè)計(jì)安全的密碼系統(tǒng)。

〔1〕 Sipser M.著，段磊譯．計(jì)算理論導(dǎo)引(第三版)〔M〕．北京：機(jī)械工業(yè)出版社，2015．

〔2〕 楊波．現(xiàn)代密碼學(xué)〔M〕．北京：清華大學(xué)出版社，2015．

〔3〕 吳文玲，馮登國，張文濤．分組密碼的設(shè)計(jì)與分析〔M〕．北京：清華大學(xué)出版社，2009．

〔4〕 胡予濮，張玉清，肖國鎮(zhèn)．對(duì)稱密碼學(xué)〔M〕．北京：機(jī)械工業(yè)出版社，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

費(fèi)如純(1968-)，男，河北昌黎人，遼寧科技學(xué)院曙光大數(shù)據(jù)學(xué)院教授，博士。研究方向：大數(shù)據(jù)，信息安全.

TP309.3

A