張靜，權(quán)雙燕，王偉，孫大寶，蔣椅

（1.東莞職業(yè)技術(shù)學(xué)院繼續(xù)教育學(xué)院，廣東 東莞 523808；2.陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 漢中 723001；3.西安石油大學(xué)理學(xué)院，陜西 西安 710065；4.西南交通大學(xué)電氣工程學(xué)院，四川 成都 610031）

基于身份的動(dòng)態(tài)數(shù)字簽名方案

張靜1，權(quán)雙燕2，王偉3,4，孫大寶3，蔣椅3

（1.東莞職業(yè)技術(shù)學(xué)院繼續(xù)教育學(xué)院，廣東 東莞 523808；2.陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 漢中 723001；3.西安石油大學(xué)理學(xué)院，陜西 西安 710065；4.西南交通大學(xué)電氣工程學(xué)院，四川 成都 610031）

數(shù)字簽名是解決信息安全問(wèn)題的重要途徑，用于鑒別用戶身份.隨著計(jì)算機(jī)、網(wǎng)絡(luò)的發(fā)展，安全的用戶數(shù)字簽名顯得尤為重要.目前，現(xiàn)代的數(shù)字簽名技術(shù)正向智能化、密碼化、多因素、大容量和快速響應(yīng)方向發(fā)展.結(jié)合數(shù)論中的中國(guó)剩余定理及RSA公鑰體制，提出了一種基于身份的動(dòng)態(tài)數(shù)字簽名方案.

中國(guó)剩余定理；動(dòng)態(tài)數(shù)字簽名方案；身份

DO I：10.3969/j.issn.1008-5513.2015.02.011

1 引言

隨著計(jì)算機(jī)的廣泛應(yīng)用和計(jì)算機(jī)網(wǎng)絡(luò)的不斷發(fā)展，社會(huì)呈現(xiàn)出信息化、網(wǎng)絡(luò)化的發(fā)展態(tài)勢(shì)，計(jì)算機(jī)輔助協(xié)同工作（CSCW：com puter supported cooperativework）成為可能并長(zhǎng)足發(fā)展，而由此引起的計(jì)算機(jī)系統(tǒng)安全性問(wèn)題不容忽視［1］.網(wǎng)絡(luò)固有的開(kāi)放性、可擴(kuò)充性，使得其安全問(wèn)題日趨明顯［2-3］.保護(hù)信息安全已經(jīng)成為整個(gè)社會(huì)的共識(shí)，各國(guó)都對(duì)信息安全系統(tǒng)的建設(shè)給予極大的關(guān)注與投入.網(wǎng)絡(luò)信息的安全隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展而進(jìn)一步深化和完善.為了防范信息安全風(fēng)險(xiǎn)，新的安全技術(shù)和規(guī)范不斷出現(xiàn)，作為其中關(guān)鍵技術(shù)的密碼學(xué)，近年來(lái)也得到很大的發(fā)展［4-5］.數(shù)字簽名作為解決信息安全問(wèn)題的重要途徑，就顯得尤為重要［6-7］.

2 預(yù)備知識(shí)

2.1 公開(kāi)密鑰密碼

公開(kāi)密鑰密碼就是采用公開(kāi)的加密密鑰和秘密的解密密鑰的一種體制.公開(kāi)的加密密鑰簡(jiǎn)稱公開(kāi)密鑰，記為PK；秘密的解密密鑰稱為秘密密鑰，記為SK.任何人都可以用另一個(gè)使用者的公開(kāi)密鑰來(lái)加密數(shù)據(jù)，而僅僅是那個(gè)知道秘密密鑰的使用者才能將加密的數(shù)據(jù)進(jìn)行解密.加密算法E和解密算法D可以是不同的，亦可以是相同的.通常，E和D都是公開(kāi)的.在這種情況下，整個(gè)體制的安全核心是SK的保密.因此公開(kāi)密鑰必須具有下列特性：

（1）使用者必須高效地計(jì)算出成對(duì)的公開(kāi)密鑰和秘密密鑰，即PK和SK；

（2）在PK已知的情況下，決不允許從有關(guān)PK的知識(shí)中有效地推導(dǎo)出SK；

（3）加密之后繼之以解密便能恢復(fù)原文，即對(duì)EPK域中所有M，都有

解密之后繼之加密以后也能恢復(fù)原文，即對(duì)DSK域中所有M，都有

其中EPK是在公開(kāi)密鑰為PK時(shí)的加密算法，DSK是在秘密密鑰為SK時(shí)的解密算法.

RSA公開(kāi)密鑰密碼是最重要的公開(kāi)密鑰密碼之一，其安全性是基于大整數(shù)分解數(shù)學(xué)問(wèn)題的難解性.

2.1.1 RSA公鑰密碼體制

Ron Rivest和Adi Sham ir以及Leonard Adleman于1978年提出的RSA公鑰密碼體制被認(rèn)為是一個(gè)安全性能良好的密碼體制［8］.

RSA公鑰密碼體制描述如下：

（1）選取兩個(gè)大素?cái)?shù)p和q（保密）.

（2）計(jì)算n=pq（公開(kāi)），?（n）=（p?1）（q?1）（保密）.

（3）隨機(jī)選取正整數(shù)e，1＜e＜?（n），滿足gcd（e,?（n））=1，e是公開(kāi)的加密密鑰.

（4）計(jì)算d，滿足de≡1（mod?（n）），d是保密的解密密鑰.

（5）加密變換：對(duì)明文m∈Zn，密文為c=memod n.

（6）解密變換：對(duì)密文c∈Zn，明文為m=cdmod n.

2.1.2 RSA的安全性討論

RSA公鑰密碼體制的安全性基于大整數(shù)的素分解問(wèn)題的難解性.

盡管尚未在理論上嚴(yán)格證明因子分解問(wèn)題一定是難解的，但經(jīng)過(guò)長(zhǎng)期的研究，迄今沒(méi)有找到一個(gè)有效算法的事實(shí)，使得因子分解問(wèn)題成為眾所周知的難題.這是RSA公鑰密碼體制建立的基礎(chǔ).

從下面的討論可以看出，破譯RSA的明顯方法至少和因子分解問(wèn)題一樣困難.

（1）如果密碼分析者能夠分解n的因子p和q，則就可以容易地求出?（n）和解秘密鑰d，從而破譯RSA.因此，破譯RSA不可能比因子分解問(wèn)題更困難.

（2）如果密碼分析者能夠不對(duì)n進(jìn)行因子分解而求得?（n），則可根據(jù)de≡1（mod（?（n））求得解密密鑰d，從而破譯RSA.因?yàn)?/p>

所以知道?（n）和n就可以容易地求得p和q，從而成功地分解n.因此，不對(duì)n進(jìn)行因子分解而直接計(jì)算?（n）并不比對(duì)n進(jìn)行因子分解更容易.

（3）如果密碼分析者能夠既不對(duì)n進(jìn)行因子分解也不求?（n）而直接求得解密密鑰d，則可計(jì)算ed?1，ed?1是?（n）的倍數(shù).已知利用?（n）的倍數(shù)可以分解出n的因子.因此，直接計(jì)算解密密鑰d并不比對(duì)n進(jìn)行因子分解更容易.

隨著計(jì)算能力的持續(xù)增長(zhǎng)和因子分解算法的不斷完善，為保證RSA的安全性，在實(shí)際應(yīng)用中選取得素?cái)?shù)p和q越來(lái)越大.除了指定n的大小之外，為避免選取容易分解的整數(shù)n，研究人員建議對(duì)p和q采取如下限制：

（1）p和q的長(zhǎng)度應(yīng)該相差不多；

（2）p?1和q?1都應(yīng)該包含大的素因子；

（3）gcd（p?1,q?1）應(yīng)該很小.

2.1.3 中國(guó)剩余定理

中國(guó)剩余定理是春秋時(shí)的孫子最先提出并應(yīng)用的，因此又稱孫子定理.在中國(guó)古代的多本數(shù)學(xué)專著中都有這一問(wèn)題的描述和解法，最為著名的是唐朝和尚一行提出的解法，稱為大衍求一術(shù).

中國(guó)剩余定理本質(zhì)上是求解同余方程組.在現(xiàn)代數(shù)論中，中國(guó)剩余定理具有十分重要的理論地位與應(yīng)用價(jià)值［9-11］.例如在雷達(dá)領(lǐng)域中，中國(guó)剩余定理被用在脈沖多普勒雷達(dá)上，解目標(biāo)的距離模糊和速度模糊，在線天線陣接收雷達(dá)中解測(cè)角的模糊；在信號(hào)處理的理論中，基于中國(guó)剩余定理的數(shù)論變化是一種重要的快速變換方法，只是目前還缺乏對(duì)其物理意義的描述而使其應(yīng)用受到一定的限制；在IC設(shè)計(jì)中，應(yīng)用中國(guó)剩余定理可以獲得高效的IIR濾波器設(shè)計(jì)的方法.

中國(guó)剩余定理：

如果n≥2，而m1,m2,···,mn是兩兩互素的n個(gè)正整數(shù)，令

式中

則同時(shí)滿足同余方程

的正整數(shù)解為：

的正整數(shù)解，即Mi為mi模的乘逆.

3 基于身份的動(dòng)態(tài)數(shù)字簽名方案

“動(dòng)態(tài)簽名”是與“靜態(tài)簽名”相對(duì)而言的，它們的主要區(qū)別在于一個(gè)“動(dòng)態(tài)簽名”只能使用一次，而且每次不同；而“靜態(tài)簽名”則重復(fù)多次使用，每次都一樣.在簽名過(guò)程中加入不確定因素，使每次簽名過(guò)程中傳送的信息都不相同，以提高簽名過(guò)程安全性.系統(tǒng)接收到簽名后做一個(gè)驗(yàn)算即可驗(yàn)證用戶的合法性.

3.1 系統(tǒng)的初始化過(guò)程

且di＜IDi，有

SC利用每個(gè)用戶的驗(yàn)證密鑰di以及IDi（i=1,2,···,n）.求滿足同余方程：

的正整數(shù)解為：

式中，

f是一個(gè)雙向函數(shù)，由a,b可以求得f（a,b），相反由f（a,b）也可求得a,b.系統(tǒng)中的參數(shù)總結(jié)如下：

（1）SC保留的秘密信息：?（n）,p,q；

（2）系統(tǒng)公開(kāi)信息：x0,n，雙向函數(shù)f；

（3）用戶ui保留的秘密信息：ei；

（4）用戶保留的公開(kāi)信息：IDi.

3.2 簽名過(guò)程

假設(shè)有一用戶ui（i=1,2,···,n）,將要對(duì)文章m簽名，他提交由身份識(shí)別符IDi，時(shí)間T和文章m雜湊函數(shù)t（m）構(gòu)成的口令

驗(yàn)證過(guò)程：任意用戶利用di=x0mod IDi求出用戶的驗(yàn)證密鑰di，對(duì)簽名進(jìn)行驗(yàn)證，求出雙向函數(shù)值fei（t（m）,T），繼而求得t（m）和T，驗(yàn)證T值是否符合要求，若不符合，則表明口令被重播或修改；若符合要求，則驗(yàn)證t（m）是否與用戶先前提交的m相關(guān)，若相關(guān)，則通過(guò)驗(yàn)證；若不同，則拒絕該用戶.

3.3 安全性及性能分析

（1）口令驗(yàn)證方案中采用了時(shí)間標(biāo)志IDi及T用來(lái)鑒別申請(qǐng)用戶，又用來(lái)防止口令重播.某個(gè)用戶uj利用原來(lái)ui已發(fā)送的口令

將T改為T′，即將

以u(píng)j的名義進(jìn)行簽名，但因?yàn)樗荒苄薷膄ei（t（m）,T）中的T，所以不能通過(guò)驗(yàn)證.

（2）IDi作為身份識(shí)別符，還起到了信息隱藏的作用.x0公開(kāi)，省去了公開(kāi)di公鑰表.

（3）方案采用了RSA公鑰密碼體制，提供安全性保證.

［1］譚凱軍，諸鴻文.一種基于孫子定理的會(huì)議密鑰的分配機(jī)制［J］.小型微型計(jì)算機(jī)系統(tǒng)，1999，20（3）：181-184.

［2］盧鐵成.信息加密技術(shù)［M］.成都：四川科學(xué)技術(shù)出版社，1989.

［3］Bruce Schneier.應(yīng)用密碼學(xué)［M］.北京：機(jī)械工業(yè)出版社，2000.

［4］聶元銘，丘平.網(wǎng)絡(luò)信息安全技術(shù)［M］.北京：科學(xué)出版社，2001.

［5］盧開(kāi)澄.計(jì)算機(jī)密碼學(xué)-計(jì)算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)保密與安全［M］.2nd ed.北京：清華大學(xué)出版社，1998.

［6］Goutam Saha，M ina Desai，A rghya Ghosh，et al.Digital Signature M odeling in E-Business［J］.International Conference on E-Business Engineering（ICEBE），2014，DOI：10.1109/ICEBE.2014.67.

［7］Tsujii S，Gotaishi M，Tadaki K，et al.Proposal of a Signature Schem e Based on STS Trapdoor［J］.Post-Quantum Cryptography，2010，6061：201-207.

［8］陳魯生，沈世鎰.現(xiàn)代密碼學(xué)［M］.北京：科學(xué)出版社，2002.

［9］楊世輝.孫子定理探源［J］.涪陵師專學(xué)報(bào)，2000，16（2）：71-75.

［10］閔嗣鶴，嚴(yán)士健.初等數(shù)論［M］.北京：高等教育出版社，2007.

［11］阮傳概.近世代數(shù)及其應(yīng)用［M］.北京：北京郵電學(xué)院出版社，1988.

2010 M SC：03C65

A dynam ic d igital signatu re schem e on iden tity

Zhang Jing1，Quan Shuangyan2，Wang Wei3，4，Sun Dabao3，Jiang Yi3

（1.Departm ent of Continous Education of Dongguan Polytechnic College，Dongguan 523808，China；2.College of Mathematics and Com puter Science of Shaanxi University of Technology，Hanzhong 723001，China；3.College of Sciences of Xi'an Shiyou University，Xi′an 710065，China；4.College of Electrical Engineering of Southwest JiaoTong University，Chengdu 610031，China）

D igital signature is an im portant way to solve the problem of inform ation security，which used to identify the user's identity.W ith the developm ent of com puter and network，security user digital signature scheme is very im portant.So far，modern digital signature technology is developing to the direction of the intelligentialize，encipherm ent，multi-factor，large capacity and rapid response.In this paper，combining the Chinese rem ainder theorem of the number theory w ith RSA pub lic key schem e，a dynam ic signature schem e on identity is p roposed.

Chinese rem ainder theorem，dynam ic digital signature schem e，identity

O 29；TP393.08

A

1008-5513（2015）02-0204-06

2014-12-19.

國(guó)家自然科學(xué)基金面上項(xiàng)目（61175055）；中國(guó)博士后科學(xué)基金面上一等資助項(xiàng)目（2013M 540716）；漢中市科技局專項(xiàng)科研計(jì)劃項(xiàng)目（2013hzzx41）.

張靜（1981-），碩士，講師，研究方向：信息及編碼、密碼學(xué).