一類特殊函數(shù)在信息密碼學中應(yīng)用證明與算法改進

摘 ?要：本文對單向陷門函數(shù)的概念、設(shè)計原則和應(yīng)用等方面進行了描述。并對單向陷門函數(shù)在密碼學中的應(yīng)用、如何在非對稱加密函數(shù)中實現(xiàn)的算法，及在KDC、PKI中的使用進行了說明，且在Diffie-Hellman算法基礎(chǔ)上提出并研究了一個帶時間戳的公共模非對稱改進加密算法，證明主要的數(shù)學結(jié)論。

關(guān)鍵詞：陷門函數(shù);非對稱加密算法;算法改進

中圖分類號：TP309.7 ? ? ?文獻標識碼：A 文章編號：2096-4706（2019）18-0106-05

Abstract：This paper gives the concept and design principle of one-way trapdoor function，its application in cryptography，how to implement the algorithm in asymmetric encryption function，and how to use it in KDC and PKI. On the basis of Diffie-Hellman algorithm，an improved public modulus asymmetric encryption algorithm with time stamp is proposed and studied，and the main mathematical conclusions are proved.

Keywords：trapdoor function;asymmetric encryption algorithm;algorithm improvement

0 ?引 ?言

身份認證、數(shù)據(jù)的保密性、不可篡改性和防止抵賴性等安全服務(wù)，是信息安全的一項關(guān)鍵技術(shù)。這些技術(shù)離不開函數(shù)，設(shè)計一個單向陷門函數(shù)，可以為網(wǎng)絡(luò)和信息交換提供安全保障。

如果在單向函數(shù)中另加一個條件，使得原先不可解的函數(shù)變?yōu)榭山?，對于加密具有特殊的意義，這就是單向求逆的意義所在，這樣的函數(shù)就是單向陷門函數(shù)。

1 ?密碼學簡介及非對稱密碼體制

密碼學是對加密密碼和破譯密碼的技術(shù)進行分析研究的學科，對信息安全領(lǐng)域中各項技術(shù)起支撐作用。按加密密鑰與解密是否一樣進行劃分，可以分為對稱密鑰和非對稱密鑰。下面我們對這兩種密碼分別進行介紹。

1.1 ?對稱密碼體制

在對稱密鑰中，使用一樣的密鑰對明文和密文進行加解密。

1.2 ?非對稱密碼體制

1976年，Diffie和Hellman第一次提出了公鑰密碼學的概念，以此來解決傳統(tǒng)密碼學中難以保存管理密鑰分配及抗否認的數(shù)字簽名認證問題。這種較為復雜的密碼體制與對稱密碼體制明顯的區(qū)別在于，它使用兩個密鑰，且互不相同和不能相互推出，可以完成對加密明文和解密密文的操作，而且解密密鑰不能僅僅根據(jù)公開密碼算法和另一個密鑰計算得到。

2 ?公鑰密碼PKC的核心元素

公鑰密碼的核心元素主要基于單向函數(shù)、單向陷門函數(shù)、單向散列函數(shù)。

單向陷門函數(shù)的定義：已知x，可容易地計算y=f（x），而給定y，求滿足y=f（x）的x非常困難，當?shù)玫綄?yīng)的陷門t，可以使y=f（x）中x的計算變得容易。

3 ?單向陷門函數(shù)的設(shè)計

單向函數(shù)和陷門函數(shù)是公鑰密碼學的核心，公鑰密碼體制的設(shè)計主要取決于單向陷門函數(shù)的設(shè)計。

事實上給出單向函數(shù)的定義是很棘手的，其原因如下：

（1）由于單向函數(shù)一般求逆都是困難的，故嚴格意義上說陷門函數(shù)不是單向函數(shù);

（2）陷門有可能不唯一，通過大量研究，通過很多陷門就可容易地找到逆。一旦陷門信息的保密性被破壞，求逆就變得容易。

非對稱密碼的原理就是建立在單向陷門函數(shù)基礎(chǔ)之上，加密是容易的方向，每個人都可以利用公鑰加密數(shù)據(jù)，解密卻是難的方向，它的設(shè)計非常困難，在沒有陷門信息的情況下，即使用群集計算機，在可接受的時間內(nèi)也不能解密數(shù)據(jù)。

下面給出一些常見的近似單向函數(shù)：

（1）離散對數(shù)。存在一個大素數(shù)p，p-1含有一大素數(shù)因子q。整數(shù)g滿足：1

當y、g、p為給定的值，求x=loggy mod p則變?yōu)殡x散對數(shù)問題。目前最快的達到L（p）次運算的方法，運算復雜度為L（p）=exp{（lnpln（lnp））1/2}。

（2）因數(shù)分解問題。通過算法給出大素數(shù)p和q，計算n=pq，只需要一次乘法運算。若已知n，求p和q，即為因數(shù)分解問題，運算次數(shù)最少需要T（n）次，次數(shù)T（n）=exp{m（lnnln（lnn））1/2}，其中m為大于1的自然數(shù)。在實際密碼算法操作中，整數(shù)n可取309位十進制。比如當n為300時，每μs運算一次，因子分解運算次數(shù)1.5E20次，所需時間為4E15年。

（3）背包問題。已知有限個自然數(shù)序列組合B=（b1，b2，…，bn），xi取0或1中的一個值時，求S=xibi，至多僅需要n-1次加法運算;如果給定B和S，求xi非常困難。各種情況共有2n種可能，當n規(guī)模很大時，在計算上是不可行的。

4 ?素性測試、求模逆元算法介紹

4.1 ?素性測試

很多密碼算法首先需要隨機選擇一個或者多個非常大的素數(shù)?？梢韵犬a(chǎn)生很大的隨機整數(shù)，再判斷該大數(shù)是否是素數(shù)。當前還沒找到簡單有效的算法確定一個大數(shù)是否為素數(shù)。下面介紹Miller-Rabin的素數(shù)存在性概率檢測法。

6.3 ?橢圓曲線密碼算法

橢圓曲線上每個點另加一個叫做無窮遠點構(gòu)成的SET，其中定義了一個加法運算，這就構(gòu)成一個阿貝爾群。在等式kD=D+D+…+D=S中，已知k和點D求點S比較容易，反之已知點S和點D求k卻是相當困難的，這個問題則叫做橢圓曲線上點阿貝爾群的離散對數(shù)問題（Elliptic Curve Discrete Logarithm Proble，ECDLP）。橢圓曲線密碼算法就是利用這個非常困難的問題研究設(shè)計的。

6.3.1 ?ElGaml的橢圓曲線密碼求解過程

6.3.1.1 ?密鑰產(chǎn)生

如果系統(tǒng)公開參數(shù)是一個橢圓曲線E及模數(shù)p，那么使用者可以執(zhí)行如下步驟。

（1）選擇一個任意整數(shù)k，滿足0

（2）選擇一個任意點A∈E，并運算B=kA。

（3）公鑰就是（A，B），私鑰就是k。

6.3.1.2 ?加密過程

假設(shè)明文N為E上的一點。首先選擇一個任意的整數(shù)r∈Zp，其次運算密文（c1，c2）=（rA，N+rB）。密文有兩點。

6.3.1.3 ?解密過程

計算明文N=c2-kc1。

6.3.2 ?Menezes-Vanstone梅內(nèi)澤斯的橢圓曲線密碼求解過程

Menezes-Vanstone梅內(nèi)澤斯的橢圓曲線密碼求解過程是效率很高的橢圓曲線加密法，其明文可以不落在橢圓曲線E上。

6.3.2.1 ?密鑰產(chǎn)生

如果系統(tǒng)公開參數(shù)是一個橢圓曲線E和模數(shù)m，那么使用者執(zhí)行以下過程。

（1）選擇一個任意整數(shù)k，滿足0

（2）選擇一個任意點A∈E，運算B=kA。

（3）公鑰是（A，B），私鑰是k。

6.3.2.2 ?加密過程

假設(shè)明文N=（n1，n2），明文的點可在E上也可不在E上。

（1）選擇一個任意數(shù)r∈ZH，H是E包含的一個循環(huán)子群。

（2）算出密文（C1，C2），有：

C1=rA，Y=（y1，y2）=rB，C2=（c21，c22）=（y1×n1 mod m，y2×n2 mod m）

6.3.2.3 ?解密過程

（1）算出Z=（z1，z2）=kC1。

（2）算出明文N=（c21×z1-1 mod m，c22×z2-1 mod m）。

7 ?密鑰分發(fā)中心、PKI介紹

7.1 ?密鑰分發(fā)中心（KDC）

Kerberos身份認證通過讓被認證方和認證方知曉的Key來鑒定對方的真實身份。用這個Key加密的數(shù)據(jù)包可在客戶端與服務(wù)器之間傳送，因此這個Key是短效密鑰。由于這個密鑰僅在一次Session（會話）中有效，稱這個Key是client和server之間的Session Key（會話密鑰）。

7.2 ?PKI

公鑰基礎(chǔ)設(shè)施PKI是Public Key Infrastructure的簡稱，PKI是利用公鑰加密技術(shù)為網(wǎng)上活動的開展建立一套安全基礎(chǔ)設(shè)施。

為完善、規(guī)范這些互聯(lián)網(wǎng)交易活動，各個國家對其進行了很多年的攻堅，形成了一套初步的互聯(lián)網(wǎng)安全解決策略，這就是PKI。PKI采用證書發(fā)布維護管理公鑰，通過認證中心CA（Certificate Authority），把客戶的公鑰和客戶的其他信息（如名稱、算法、頒布機構(gòu)、有效期、E-mail、身份證號等）放在一起，通過PKI查詢確認，對傳輸?shù)臄?shù)字信息進行加密，確保信息傳輸?shù)谋Ｃ苄?、完整性、真實性和抗抵賴?/p>

8 ?Diffie-Hellman算法介紹與應(yīng)用

Diffie-Hellman是指通過非對稱加密實現(xiàn)一種確保共享對稱密鑰安全穿越不安全網(wǎng)絡(luò)的方法，它是OAKLEY密鑰確定協(xié)議的一個組成部分。Whitefield與Martin Hellman在上世紀提出了安全的密鑰交換協(xié)議，稱其為Diffie-Hellman密鑰交換協(xié)議/算法。

基于本原根的定義及其性質(zhì)，可以確定Diffie-Hellman密鑰交換步驟，對該操作過程描述如下：

（1）有兩個對外公開的參數(shù)，一個素數(shù)p和一個整數(shù)a，a是p的一個本原根。

（2）如果使用者甲和乙希望交換一個密鑰，使用者甲選擇一個作為私有密鑰的隨機數(shù)X甲（X甲

（3）使用者甲產(chǎn)生密鑰的方式是key= mod p。同

樣，使用者乙產(chǎn)生共享密鑰的計算是key= mod p。這兩個計算產(chǎn)生相同的結(jié)果：key=（Y乙）^X甲 mod p=（a^X乙 mod p）^X甲 mod p=（a^X乙）^X甲 mod p=a^（X乙X甲） mod p=（a^X甲）^X乙 mod p=（a^X甲 mod p）^X乙 mod p=（Y甲）^X乙 mod p，因此相當于雙方已經(jīng)共同擁有了一個相同的密鑰。

（4）由于X甲和X乙是不公開的，一個網(wǎng)絡(luò)侵入者可利用的參數(shù)值僅為p、a、Y甲和Y乙，所以網(wǎng)絡(luò)侵入者被迫使用離散對數(shù)來確定密鑰，這是一件很困難的事，對于大素數(shù)p，計算出離散對數(shù)幾乎是不可能的。

9 ?帶時間戳的公共模非對稱加密算法介紹

如果通信雙方不想利用KDC或PKI的基礎(chǔ)設(shè)施，這樣的通信過程復雜，會導致時間延誤，成本相對比較高，也不易實現(xiàn)，現(xiàn)提出一個簡化方便的通信算法，不需要第三方來進行服務(wù)，手續(xù)簡單，有相當高的安全性，對于臨時需要加密傳輸?shù)臄?shù)據(jù)能夠馬上實施。此算法的實現(xiàn)不考慮使用對稱加密技術(shù)是因為在第三方攻擊者用Sniffer或者Wireshark這樣的網(wǎng)上抓包軟件進行分析攻擊的情況下，其安全性不高，并且密碼本身的交換約定是一個容易泄密的過程。這個算法基于RSA思想，并作了一定的優(yōu)化改進，約定雙方都有一對公鑰public key和私鑰private key，為了簡化操作約定，這兩對公鑰的模module相同，這樣更加方便，但是安全性相對降低，如果雙方交換這個模就容易被攻破原文，且這個模由誰來約定也是一個問題，如果由一方來確定就不夠公平公正，導致通信雙方的信任產(chǎn)生問題。下面來論證一下，如果這個模n被獲取了，雙方的公鑰e1、e2被獲取，這時，攻擊者得到兩組密文：

c1=me1 mod n

c2=me2 mod n

由于e1與e2互素，攻擊者可以解出兩整數(shù)r和s，滿足：根據(jù)素數(shù)的性質(zhì)r×e1+s×e2=1，在這個等式中，r和s有一個為負數(shù)，假設(shè)s為負數(shù)，則攻擊者很容易算出明文m=（c1）r×（）-s，這樣在一組用戶之間共享n就不會很安全。設(shè)計的算法由雙方共同產(chǎn)生模n，這個模是由兩個素數(shù)p、q來確定，并且，這兩個素數(shù)是較大的正整數(shù)，由雙方各產(chǎn)生一個，然后傳給對方，其安全性由后面的兩個因素來保證，獲得了兩個素數(shù)p、q，就可計算出模n，再計算出歐拉數(shù)，再由歐拉數(shù)產(chǎn)生一個逆元，這個逆元就是私鑰，不傳給對方，這是安全因素一。安全因素二采用時間戳來使系統(tǒng)通信更加安全，主動通信方每過一個時間片約定更換新的模，即使第三方通過非法手段獲取兩個素數(shù)p、q，但是通過模n來求逆元是一個非常難的事，即使偶然破解出來，但是每隔一個時間片素數(shù)p、q的值發(fā)生了改變，這樣確保整個通信是安全的。下面給出實現(xiàn)的具體算法。

（1）約定一個數(shù)s作為一個時間片，time=0。

（2）通信發(fā)起方調(diào)用素性算法生成一個很大的素數(shù)p，發(fā)送給接受方，等待。

（3）通信接受方調(diào)用素性算法生成一個很大的素數(shù)q，發(fā)送給接受方，等待。

（4）通信雙方計算模n=p*q，歐拉函數(shù)?（n）=（p-1）*（q-1）。

（5）time=time+1。

（6）通信發(fā)起方調(diào)用素性算法，找一個素數(shù)e1，使gcd（e1，?（n））=1，發(fā)送e1給接收方，再調(diào)用求逆元算法求d1，滿足d1*e1=1（mod ?（n））。

（7）通信接受方調(diào)用素性算法，找一個素數(shù)e2，使gcd（e2，?（n））=1，發(fā)送e2給發(fā)送方，再調(diào)用求逆元算法求d2，滿足d2*e2=1（mod ?（n））。

（8）通信發(fā)送方對原碼m進行加密得出密碼c，其計算公式為c=md1*e2（mod n）。time=time+1。

（9）通信接受方對密文c進行解密得出原文m，其計算公式為m=cd2*e1（mod n）。

（10）如果時間time

這個算法可用于通信雙方進行密鑰交換，向?qū)Ψ絺鬟f一個對稱密鑰，也可以對不復雜的通信直接進行加密傳輸，通過雙非對稱密鑰進行傳輸。這個過程不需要第三方進行公鑰傳遞，實現(xiàn)身份認證和信息傳遞。

10 ?結(jié) ?論

上述所涉及的加密算法都是基于單向陷門函數(shù)設(shè)計，這些算法沒有絕對的優(yōu)劣性，而是可以在不同的情境下使用。當沒有KDC第三方協(xié)議分發(fā)中心并且沒有大量信息交換情形下，安全性更高的選擇是用改進算法，即帶時間戳的公共模非對稱加密算法。

參考文獻：

[1] 郭姝，施滔滔，張新玉.基于單向陷門函數(shù)的加密算法 [J].硅谷，2009（18）：97.

[2] 孫永雄，趙永哲，楊永健，等.基于遍歷矩陣的單向（陷門）函數(shù)的構(gòu)造方案 [J].吉林大學學報（信息科學版），2006（5）：555-560

[3] 郭亞軍，宋建華，李莉，等.信息安全原理與技術(shù)（第2版） [M].北京：清華大學出版社，2013：111-115.

[4] 武春嶺.信息安全技術(shù)與實施（第2版） [M].北京：電子工業(yè)出版社，2015：99-102.

[5] 覃中平，張煥國，喬秦寶，等.信息安全數(shù)學基礎(chǔ) [M].北京：清華大學出版社，2006.

[6] 張賢科.初等數(shù)論 [M].北京：高等教育出版社，2016.

作者簡介：江忠（1966-），男，漢族，四川渠縣人，副教授，本科，研究方向：計算機教育、高等數(shù)學、初等數(shù)學。