改進(jìn)的ECC算法在數(shù)字認(rèn)證中心系統(tǒng)應(yīng)用

劉 軍, 賈松浩, 楊 彩

(南陽(yáng)師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 南陽(yáng) 473061)

0 引 言

安全性高、算法實(shí)現(xiàn)性能更好的橢圓曲線公鑰系統(tǒng)[1](Elliptic Curve Cryptography,ECC)是基于離散對(duì)數(shù)問(wèn)題，使用的是有限域上橢圓曲線的有理點(diǎn)群[2]。但是至今人們尚未找到有限域上橢圓曲線上有理點(diǎn)群的離散對(duì)數(shù)問(wèn)題的亞指數(shù)算法[3]，而且目前的研究結(jié)果表明構(gòu)造出這樣的亞指數(shù)算法的可能性不大[4]。近20年的公鑰密碼和相關(guān)數(shù)論的研究表明，研究整數(shù)分解問(wèn)題的一個(gè)進(jìn)展往往可以被改造用來(lái)研究離散對(duì)數(shù)問(wèn)題，因?yàn)檫@兩個(gè)問(wèn)題的難解程度被認(rèn)為相當(dāng)[5]。因此，可以利用已知的最好算法解決的整數(shù)分解問(wèn)題來(lái)處理離散對(duì)數(shù)問(wèn)題和橢圓曲線離散對(duì)數(shù)問(wèn)題[6]。ECC比RSA的每比特所蘊(yùn)涵的安全性 (比特級(jí)安全性)要高很多，而且隨著密鑰規(guī)模的擴(kuò)大，這種比特級(jí)安全性的優(yōu)勢(shì)在擴(kuò)大[7]。

1 橢圓曲線的加/解密

假設(shè)用戶A欲將明文m加密后發(fā)送給B，A需執(zhí)行以下的操作:① 用戶A選定一條橢圓曲線E，并取橢圓曲線上一點(diǎn)作為基點(diǎn)G；② 用戶A選擇一個(gè)私有密鑰k，并生成公開(kāi)密鑰K=kG；③ 用戶A將E、點(diǎn)G和公開(kāi)密鑰K傳給用戶B；④ 用戶B接到信息后，將待傳輸?shù)拿魑木幋a到E上一點(diǎn)M，并產(chǎn)生隨機(jī)整數(shù)r(r

圖1 橢圓曲線加/解密示意圖

2 改進(jìn)的ECC算法

根據(jù)已有的橢圓曲線數(shù)字簽名算法，本文做了進(jìn)一步的改進(jìn)，使其運(yùn)算負(fù)擔(dān)減少、速度提高[8]。在現(xiàn)有的橢圓曲線加密或者簽名過(guò)程中，求逆是主要的運(yùn)算負(fù)擔(dān)，如在驗(yàn)證簽名中，w=s-1(modn)這個(gè)運(yùn)算是很慢的，在此構(gòu)造一種新的簽名方程，在改進(jìn)的ECC算法的計(jì)算過(guò)程中不需要求逆的步驟，因此效率較高[9]。具體闡述如下：① 簽名者確認(rèn)Hash函數(shù)，以生成信息摘要；② 簽名者確定橢圓曲線參數(shù)F=(P,a,h,g,n,h)或(m,f(x),a,h,g,n,h)；③ 簽名者向驗(yàn)證者傳送所確定的Hash函數(shù)，橢圓曲線域參數(shù)；④ 簽名者在有限域G(P)與橢圓曲線點(diǎn)群選定的基礎(chǔ)上選擇密鑰x，由公開(kāi)基點(diǎn)g得公鑰y=xg并公開(kāi)y；⑤ 簽名者選隨機(jī)數(shù)K,1≤K≤n-1；⑥ 計(jì)算r=kg，如果r=0，則轉(zhuǎn)向第⑤步；⑦ 計(jì)算s=mrx-k；⑧ 所得(s,r)作為對(duì)m的簽名，并將(s,r)連同m發(fā)送給驗(yàn)證者；⑨ 驗(yàn)證者計(jì)算r′=sg+mry的值；⑩ 驗(yàn)證者判斷r′=r，相等則簽名成立，否則拒絕簽名。

改進(jìn)的算法減輕了運(yùn)算的負(fù)擔(dān)，提高了整個(gè)運(yùn)算速度，這種方案在提供相同安全性的前提下，對(duì)系統(tǒng)資源的要求更低，更有實(shí)用價(jià)值[10]。

3 算法在數(shù)字認(rèn)證中心系統(tǒng)的應(yīng)用

3.1 數(shù)字認(rèn)證中心系統(tǒng)的結(jié)構(gòu)

本系統(tǒng)設(shè)計(jì)時(shí)，提供公共接口，滿足系統(tǒng)的可擴(kuò)展性，為用戶發(fā)布兩種不同功能類型的數(shù)字證書(shū)：簽名證書(shū)和加密證書(shū)，可以保證更好的安全性[11]。數(shù)字認(rèn)證中心系統(tǒng)采用MVC結(jié)構(gòu)，采用JAVA EE實(shí)現(xiàn)，使用SQL Server2005數(shù)據(jù)庫(kù)存儲(chǔ)各種信息[12]。服務(wù)器端實(shí)現(xiàn)了CA(Certificate Authority)中心的操作，采用圖形化界面，其操作簡(jiǎn)單易用，實(shí)現(xiàn)了一個(gè)認(rèn)證中心系統(tǒng)的全部功能。

數(shù)字認(rèn)證中心系統(tǒng)的設(shè)計(jì)過(guò)程中，對(duì)CA的結(jié)構(gòu)進(jìn)行簡(jiǎn)化和補(bǔ)充：① 考慮到本文研究認(rèn)證中心CA時(shí)，側(cè)重于對(duì)非對(duì)稱加密算法的加密和簽名的應(yīng)用，因而涉及用戶使用的證書(shū)數(shù)量較少，并且涉及實(shí)現(xiàn)的認(rèn)證功能相對(duì)簡(jiǎn)單。在本系統(tǒng)在實(shí)現(xiàn)中，CA同時(shí)完成RA(Register Authority)的功能，CA發(fā)布證書(shū)。② 本系統(tǒng)涉及到兩個(gè)數(shù)據(jù)庫(kù)：一是證書(shū)庫(kù)，存儲(chǔ)了用戶的信息、用戶的證書(shū)信息和撤銷列表信息等；二是私鑰庫(kù)，是對(duì)用戶私鑰的備份。系統(tǒng)結(jié)構(gòu)如圖2所示。

圖2 數(shù)字認(rèn)證中心系統(tǒng)的結(jié)構(gòu)

其中，CA后臺(tái)管理實(shí)現(xiàn)了一個(gè)認(rèn)證中心CA的證書(shū)頒發(fā)、證書(shū)查詢、證書(shū)更新和證書(shū)撤銷等全部功能；系統(tǒng)客戶端實(shí)現(xiàn)的是證書(shū)擁有用戶對(duì)數(shù)字證書(shū)的各種操作。

3.2 基于算法的證書(shū)請(qǐng)求與生成

公鑰證書(shū)即是一個(gè)用戶的公鑰和他的身份的綁定，在綁定前由一個(gè)可以信任的證書(shū)權(quán)威機(jī)構(gòu)(CA)來(lái)證實(shí)用戶的身份，然后這個(gè)可信任CA對(duì)證明該綁定的證書(shū)進(jìn)行數(shù)字簽名。基于ECC公鑰體制中，如果一個(gè)用戶想要申請(qǐng)一個(gè)證書(shū)，將采取下列步驟：① 任何人(如用戶A)想要申請(qǐng)證書(shū)必須個(gè)人向CA申請(qǐng)，因?yàn)镃A要檢驗(yàn)這個(gè)人的身份。 ② 用戶A可以直接向計(jì)算機(jī)輸入他的個(gè)人信息與相應(yīng)的口令。③ CA存貯這些數(shù)據(jù)到一個(gè)臨時(shí)目錄。④ 在這個(gè)階段，將生成一個(gè)密鑰對(duì)(隨機(jī)生成一個(gè)私鑰s及與其相對(duì)的公鑰S=sG)。⑤ 生成密鑰對(duì)后，發(fā)送這個(gè)公鑰(一個(gè)橢圓曲線上的點(diǎn))到CA服務(wù)器。⑥ CA對(duì)用戶A的公鑰及其它一些與該用戶有關(guān)的信息，如個(gè)人姓名、電子郵件地址等進(jìn)行數(shù)字簽名，形成一個(gè)數(shù)字證書(shū)。⑦ 生成證書(shū)以后，CA負(fù)責(zé)把該證書(shū)拷貝到智能卡中，發(fā)送給用戶A。

3.3 認(rèn)證中心各模塊的設(shè)計(jì)與實(shí)現(xiàn)

數(shù)字認(rèn)證中心系統(tǒng)CA的根證書(shū)和私鑰是所有CA系統(tǒng)的核心。用戶的證書(shū)信息和公鑰信息都是需要經(jīng)過(guò)CA的私鑰進(jìn)行簽名，CA的數(shù)字簽名和算法是數(shù)字證書(shū)的重要內(nèi)容。用戶驗(yàn)證時(shí)，必須擁有CA的公鑰才能解開(kāi)證書(shū)中的CA簽名，所以也必須在瀏覽器中先安裝CA根證書(shū)，得到CA的公鑰。有了數(shù)字認(rèn)證中心系統(tǒng)的根證書(shū)和私鑰，就可以頒發(fā)證書(shū)和對(duì)證書(shū)進(jìn)行各種操作。

(1) 證書(shū)頒發(fā)模塊。頒發(fā)證書(shū)的過(guò)程是一個(gè)將審核通過(guò)的用戶申請(qǐng)信息經(jīng)過(guò)復(fù)雜的編碼、解碼和簽名的過(guò)程。證書(shū)頒發(fā)的流程如圖3所示。

圖3 證書(shū)頒發(fā)的流程

(2) 證書(shū)撤銷模塊。在證書(shū)有效期內(nèi)，數(shù)字認(rèn)證中心系統(tǒng)接受用戶申請(qǐng)或按照有關(guān)國(guó)家機(jī)關(guān)要求廢除證書(shū)。證書(shū)作廢后認(rèn)證中心都需要對(duì)證書(shū)撤銷列表進(jìn)行更新及維護(hù)。

(3) 證書(shū)查詢模塊。證書(shū)查詢包括查看所有已頒發(fā)的證書(shū)信息、查詢特定的用戶證書(shū)和證書(shū)撤銷列表信息。按照一定的查詢條件從數(shù)據(jù)庫(kù)表中查詢出CA簽發(fā)的用戶證書(shū)信息，為管理員進(jìn)行查看或其它操作提供參考。查看所有已頒發(fā)的證書(shū)信息和查詢特定的用戶證書(shū)時(shí)，可查詢數(shù)據(jù)庫(kù)表。

(4) 證書(shū)更新模塊。認(rèn)證中心CA所產(chǎn)生的證書(shū)都有一定的有效期限。所有證書(shū)中都有明確的證書(shū)生存期，表明該證書(shū)的產(chǎn)生日期與失效日期。用戶應(yīng)在證書(shū)過(guò)期前更換新證書(shū)并在數(shù)據(jù)庫(kù)中做相應(yīng)的更改。本數(shù)字認(rèn)證中心系統(tǒng)采用人工更新證書(shū)的方法，在證書(shū)將要到期前，管理員發(fā)Email提示用戶證書(shū)將要到期，是否需要更新證書(shū)，用戶向認(rèn)證中心提交更新請(qǐng)求，管理員審核合格后向CA發(fā)出簽發(fā)請(qǐng)求，CA頒發(fā)新證書(shū)后將證書(shū)送到認(rèn)證中心，管理員發(fā)Email通知用戶證書(shū)已成功更新，用戶可到指定的網(wǎng)址去下載自己的新證書(shū)。在證書(shū)更新時(shí)，不需要再次審核用戶信息，本系統(tǒng)的證書(shū)更新過(guò)程是在撤銷原有證書(shū)的基礎(chǔ)上，為用戶重新頒發(fā)證書(shū)[13]。

3.4 安全性分析

由于計(jì)算量小和處理速度快，改進(jìn)ECC的實(shí)現(xiàn)可以選取比RSA小得多的大數(shù)，實(shí)現(xiàn)速度要比RSA、DSA快得多。存儲(chǔ)空間占用小，密鑰尺寸和系統(tǒng)參數(shù)與RSA、DSA相比要小得多。160位ECC與1 024位RSA、DSA具有相同的安全強(qiáng)度。

改進(jìn)ECC算法的安全性基于橢圓曲線點(diǎn)群上離散對(duì)數(shù)問(wèn)題(ECDLP)的難解性，基于模運(yùn)算的整數(shù)因式分解問(wèn)題和離散對(duì)數(shù)問(wèn)題是存在亞指數(shù)時(shí)間復(fù)雜度的運(yùn)算法。同時(shí)，改進(jìn)ECC把實(shí)數(shù)域上的乘法運(yùn)算、指數(shù)運(yùn)算等映射成橢圓曲線上的加法運(yùn)算，比其他公鑰密碼體系更快，更容易實(shí)現(xiàn)，成本更低。

改進(jìn)ECC算法還具有一些更高級(jí)的安全特性，如在設(shè)計(jì)前向保密的密碼方案、抵抗密碼實(shí)現(xiàn)中的計(jì)算錯(cuò)誤等方面比RSA具有優(yōu)勢(shì)。

4 結(jié) 語(yǔ)

為了解決數(shù)字認(rèn)證中心系統(tǒng)的安全認(rèn)證問(wèn)題，研究了 ECC算法，并和RSA算法、DSA算法進(jìn)行了安全性分析和比較。把改進(jìn)的ECC算法運(yùn)用到數(shù)字認(rèn)證中心系統(tǒng)的實(shí)現(xiàn)過(guò)程中，設(shè)計(jì)了一個(gè)認(rèn)證中心CA——數(shù)字認(rèn)證中心系統(tǒng)，實(shí)現(xiàn)數(shù)字證書(shū)的管理功能：證書(shū)的頒發(fā)、證書(shū)的更新、證書(shū)的查詢和證書(shū)的撤銷等功能，能夠比較完整的實(shí)現(xiàn)一個(gè)用戶從最初的注冊(cè)到獲得數(shù)字證書(shū)，到對(duì)擁有證書(shū)進(jìn)行各種操作的過(guò)程。同時(shí)，本系統(tǒng)為用戶發(fā)布兩種不同功能類型的數(shù)字證書(shū)：簽名證書(shū)和加密證書(shū)。算法分析說(shuō)明改進(jìn)的ECC算法安全性更好，更容易實(shí)現(xiàn)，成本也更低。

[1] 秦志光. 密碼算法的現(xiàn)狀與發(fā)展研究[J]. 計(jì)算機(jī)應(yīng)用, 2004, 24(2):3-4.

QIN Zhi-guang. Cryptography Algorithm—Survey Trends[J]. Computer Applications,2004,24(2):3-4.

[2] 姬 睿,申 輝. 基于信息安全領(lǐng)域的密碼技術(shù)[J].實(shí)驗(yàn)室研究與探索, 2010,29(9):67-72.

JI Rui, SHEN Hui.The Research of Public-key Cryptography in Information Security Teachnology[J].RESEARCD AND EXPLORATION lN LABORATORY, 2010,29(9):67-72.

[3] 劉 鐸,戴一齊.計(jì)算橢圓曲線上多標(biāo)量乘的快速算法[J]. 計(jì)算機(jī)學(xué)報(bào),2008, 31(7):1131-1138.

LIU Duo, DAI Yi-qi. A New Algorithm of Elliptic Curve Multi-Scalar Multiplication[J].CHINESE JOURNAL OF COMPUTERS, 2008, 31(7):1131-1138.

[4] 寧國(guó)強(qiáng),李謝華,尹張飛.一種安全的即時(shí)通信解決方案[J]. 計(jì)算機(jī)工程與應(yīng)用,2011, 47(3):82-83,93.

NING Guo-qiang, LI Xie-hua, YIN Zhang-fei. Solution to secure instant messaging[J].Computer Engineering and Applications,2011,47(3):82-83,93.

[5] 李 楠,谷 山,蘇錦海. SAKI方案的分析及改進(jìn)[J]. 計(jì)算機(jī)工程,2010,36(23):116-118.

LI Nan, GU Shan, SU Jin-hai. Analysis and Improvement of Separable and Anonymous Identity-based Private Key Issuing Scheme[J]. Computer Engineering,2010,36(23):116-118.

[6] 劉 巧,彭新光.基于ECC的嵌入式系統(tǒng)的一次性口令方案[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(4):1212-1216.

LIU Qiao, PENG Xin-guang. One-Time Password Scheme of emhedded system based on ECC[J].COMPUTER ENGINEERING AND DESIGN,2013,34(4):1212-1216.

[7] 李 浪,楊 柳,李肯立,等.一種橢圓曲線密碼算法ECC旁路攻擊方法研究[J].計(jì)算機(jī)應(yīng)用研究,2013,30(3):889-890.

LI lang, YANG Liu, LI Ken-li,etal. Research on side-channel attack methods of ECC[J].Application Research of Computers,2013,30(3):889-890.

[8] 魏先民. 改進(jìn)的ECC算法在網(wǎng)絡(luò)信息安全中的研究[J].計(jì)算機(jī)科學(xué),2013,40(1):136-138.

WEI Xian-min. Research on Improved ECC Algorithm in Network and Information Security[J].Computer Science, 2013,40(1):136-138.

[9] 肖自金,周 海,吳麗珍. 基于橢圓曲線ElGamal代理加密機(jī)制的MANET組密鑰分發(fā)方案[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(3):139-144.

XIAO Zi-jin, ZHOU Hai, WU Li-zhen. A New ECC Elgamal Proxy Eneryption-based Group Key Distribution Scheme for Manet[J].Computer Applications and Software, 2013,30(3):139-144.

[10] 吳學(xué)慧,牛志華,王 潮. 基于橢圓曲線密碼的RFID安全協(xié)議[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2010, 31(24): 5165-5167,5182.

WU Xue-hui, NIU Zhi-hua, WANG Chao. Security protocol of RFID based elliptic curve cryptography[J].Computer Engineering and Design, 2010, 31(24): 5165-5167,5182.

[11] 劉 淳,張鳳元,張其善.基于智能卡的RSA與ECC算法的比較與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用,2007,43(4):96-98,118.

LIU Chun, ZHANG Feng-yuan, ZHANG Qi-shan. Comparing and implementation of ECC and RSA algorithms on Smartcard[J]. Computer Engineering and Applications, 2007,43(4):96-98,118.

[12] 康鴻雁.基于ECC的RFID組證明協(xié)議分析及改進(jìn)[J]. 計(jì)算機(jī)工程,2013,39(1):153-156,163.

KANG Hong-yan. Analysis and Improvement of Grouping-proof Protocol for RFID Based on ECC[J]. Computer Engineering, 2013,39(1):153-156,163.

[13] 姚劍波,張 濤. 抗側(cè)信道攻擊的安全有效橢圓加密算法[J]. 計(jì)算機(jī)應(yīng)用研究,2012,29(12):4639-4643.

YAO Jian-bo, ZHANG Tao. Safe and effective elliptic encryption algorithm resistance against side-channel attack[J]. Application Research of Computers, 2012,29(12):4639-4643.

[14] 楊同豪,郁 濱. 基于身份的ZigBee節(jié)點(diǎn)認(rèn)證方案[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2012,33(11):4127-4130.

YANG Tong-hao, YU Bin. Identity-based authentication Scheme for ZigBee nodes[J]. Computer Engineering and Design, 2012,33(11):4127-4130.

[15] 陳丹偉,薛青晗,章 韻. 基于ECC的RDP認(rèn)證機(jī)制研究[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,32(5):32-37.

CHEN Dan-wei, XUE Qing-han, ZHANG Yun. Research of RDP authentication system based on ECC[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2012,32(5):32-37.