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

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

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

中圖分類號(hào)：TP309.7 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 ?引 ?言

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

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

1 ?密碼學(xué)簡(jiǎn)介及非對(duì)稱密碼體制

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

1.1 ?對(duì)稱密碼體制

在對(duì)稱密鑰中，使用一樣的密鑰對(duì)明文和密文進(jìn)行加解密。

1.2 ?非對(duì)稱密碼體制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 ?素性測(cè)試、求模逆元算法介紹

4.1 ?素性測(cè)試

很多密碼算法首先需要隨機(jī)選擇一個(gè)或者多個(gè)非常大的素?cái)?shù)。可以先產(chǎn)生很大的隨機(jī)整數(shù)，再判斷該大數(shù)是否是素?cái)?shù)。當(dāng)前還沒找到簡(jiǎn)單有效的算法確定一個(gè)大數(shù)是否為素?cái)?shù)。下面介紹Miller-Rabin的素?cái)?shù)存在性概率檢測(cè)法。

6.3 ?橢圓曲線密碼算法

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

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

6.3.1.1 ?密鑰產(chǎn)生

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

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

（2）選擇一個(gè)任意點(diǎn)A∈E，并運(yùn)算B=kA。

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

6.3.1.2 ?加密過程

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

6.3.1.3 ?解密過程

計(jì)算明文N=c2-kc1。

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

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

6.3.2.1 ?密鑰產(chǎn)生

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

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

（2）選擇一個(gè)任意點(diǎn)A∈E，運(yùn)算B=kA。

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

6.3.2.2 ?加密過程

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

（1）選擇一個(gè)任意數(shù)r∈ZH，H是E包含的一個(gè)循環(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身份認(rèn)證通過讓被認(rèn)證方和認(rèn)證方知曉的Key來鑒定對(duì)方的真實(shí)身份。用這個(gè)Key加密的數(shù)據(jù)包可在客戶端與服務(wù)器之間傳送，因此這個(gè)Key是短效密鑰。由于這個(gè)密鑰僅在一次Session（會(huì)話）中有效，稱這個(gè)Key是client和server之間的Session Key（會(huì)話密鑰）。

7.2 ?PKI

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

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

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

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

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

（1）有兩個(gè)對(duì)外公開的參數(shù)，一個(gè)素?cái)?shù)p和一個(gè)整數(shù)a，a是p的一個(gè)本原根。

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

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

樣，使用者乙產(chǎn)生共享密鑰的計(jì)算是key= mod p。這兩個(gè)計(jì)算產(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，因此相當(dāng)于雙方已經(jīng)共同擁有了一個(gè)相同的密鑰。

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

9 ?帶時(shí)間戳的公共模非對(duì)稱加密算法介紹

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

c1=me1 mod n

c2=me2 mod n

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

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

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

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

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

（5）time=time+1。

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

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

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

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

（10）如果時(shí)間time

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

10 ?結(jié) ?論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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