一類特殊函數在信息密碼學中應用證明與算法改進

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

關鍵詞：陷門函數;非對稱加密算法;算法改進

中圖分類號：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 ?引 ?言

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

如果在單向函數中另加一個條件，使得原先不可解的函數變為可解，對于加密具有特殊的意義，這就是單向求逆的意義所在，這樣的函數就是單向陷門函數。

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

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

1.1 ?對稱密碼體制

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

1.2 ?非對稱密碼體制

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

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

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

單向陷門函數的定義：已知x，可容易地計算y=f（x），而給定y，求滿足y=f（x）的x非常困難，當得到對應的陷門t，可以使y=f（x）中x的計算變得容易。

3 ?單向陷門函數的設計

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

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

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

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

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

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

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

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

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

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

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

4.1 ?素性測試

很多密碼算法首先需要隨機選擇一個或者多個非常大的素數。可以先產生很大的隨機整數，再判斷該大數是否是素數。當前還沒找到簡單有效的算法確定一個大數是否為素數。下面介紹Miller-Rabin的素數存在性概率檢測法。

6.3 ?橢圓曲線密碼算法

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

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

6.3.1.1 ?密鑰產生

如果系統公開參數是一個橢圓曲線E及模數p，那么使用者可以執行如下步驟。

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

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

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

6.3.1.2 ?加密過程

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

6.3.1.3 ?解密過程

計算明文N=c2-kc1。

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

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

6.3.2.1 ?密鑰產生

如果系統公開參數是一個橢圓曲線E和模數m，那么使用者執行以下過程。

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

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

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

6.3.2.2 ?加密過程

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

（1）選擇一個任意數r∈ZH，H是E包含的一個循環子群。

（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 ?密鑰分發中心、PKI介紹

7.1 ?密鑰分發中心（KDC）

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

7.2 ?PKI

公鑰基礎設施PKI是Public Key Infrastructure的簡稱，PKI是利用公鑰加密技術為網上活動的開展建立一套安全基礎設施。

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

8 ?Diffie-Hellman算法介紹與應用

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

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

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

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

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

樣，使用者乙產生共享密鑰的計算是key= mod p。這兩個計算產生相同的結果：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，因此相當于雙方已經共同擁有了一個相同的密鑰。

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

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

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

c1=me1 mod n

c2=me2 mod n

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

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

（2）通信發起方調用素性算法生成一個很大的素數p，發送給接受方，等待。

（3）通信接受方調用素性算法生成一個很大的素數q，發送給接受方，等待。

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

（5）time=time+1。

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

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

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

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

（10）如果時間time

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

10 ?結 ?論

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

參考文獻：

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

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

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

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

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

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

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