基于RSA体制的分布式秘钥托管方案研究

毛志芹,程元元

(华北水利水电大学 信息工程系,河南 郑州 450011)

基于RSA体制的分布式秘钥托管方案研究

毛志芹,程元元

(华北水利水电大学 信息工程系,河南 郑州 450011)

基于RSA密码体制对秘钥托管方案进行了进一步的研究和优化实现——多素数RSA密码体制。该优化方案满足了对用户秘钥安全管理与司法部门调查取证之间的协调,有效的解决了“一次监听,永久监听”问题,而且每个托管代理能够验证他所托管的子密钥的有效性,实现分布式托管的优化,规避了“阈下攻击”和托管部门权力滥用等问题。

秘钥托管;多素数RSA体制;分布式托管;监听

近年,计算机密码学不断进展,人们在使用密码算法获得保密消息方面有了可靠的保证,但同时,这也给犯罪提供了条件。如何在用户隐私权和法律授权下的政府机构监听权之间寻找出一种折中方法是近年来密码学界研究的热点课题之一。一方面,为了保护用户的隐私权,密码强度不应减弱;另一方面,为了打击犯罪分子的非法活动,法律授权下的政府机构监听权也应得到保证。

美国政府1993年颁布了EES(Escrow Encryption Standard)[1]体现了对密钥实行法定托管代理的新思路。1995年Shamir[2]提出了部分密钥托管思想,Lenstra等[3]提出时间约束下的托管加密方案,Micali[4-5]提出了公正密钥托管方案和共享伪随机函数密钥托管方案等。但这些方案由于秘钥产生机构和秘钥托管机构独立和单一,都没有很好地解决个权力滥用和“阈下攻击”问题。

为了防止托管机构滥用权力,人们开始将门限密码体制应用于私钥托管,进而提出了门限密钥托管思想。但这些利用门限方案得到的托管方案[6-8]存在很多缺点,一方面,不能及时准确地得知不能正常工作或不愿合作的托管代理,导致密钥恢复时判断重构的密钥是否正确需要试凑解密,影响实时性;另一方面,防止托管机构非法合作恢复密钥而必须保证各个托管机构相互独立,这样很难验证各托管代理保存的子密钥的正确性,而使用户有可能逃避托管,都没有很好地解决“一次监听,永久监听”问题。

鉴于秘钥拖管方面的研究,庄涌提出的基于RSA密码体制的可验证部分秘钥托管方案[9],密钥在产生过程中,每个托管机构分别托管N的分解因子p和q的部分信息(piqi),然后通过用户的通信加密公钥ke加密后传输到用户端以便用户计算私钥d。该过程是其托管方案的瓶颈,因而无法应用于实际,因此本文改进了该算法,把(piqi)改成N的分解因子p1、p2、p3…。

1 优化的分布式秘钥托管方案

1.1 系统描述

在本文讨论的秘钥托管方案中,采用改进的多素数RSA算法,整个方案大致分为4个步骤:(1)t个密钥托管机构分别产生公钥N的素数分解因子p1、p2、…、Pt,验证是否为不同的素数,并将这些分解因子经过Tb、CAb的传输到用户端。(2)用户端自己合成公钥N=p1,p2,p3,…pi和私钥d,并把公钥(e,N)传输到Tb端和CAb端。(3)Tb端T1、T2、…、Tt一起验证用户传过来的公钥N是否由各托管机构共同生成,然后验证结果发送给CAb端。(4)CAb端为用户制作加密公钥证书。

具体托管方案原理如图1所示。

图1 分布式密钥托管方案原理图

1.2 方案分析

1.2.1 算法正确性分析

方案中,托管机构托管公钥N的素数分解因子p1,p2,…,pt,公钥(e,N)中,e由系统指定,N是用户收到p1,p2,…,pt后自己计算的。所以在e,N,N的分解因子确定的情况下,求解同余方程

eN≡1(modφ(N))

(1)

由于gcd(e,φ(N))=1根据一次同余方程的有关定理,知其解为

(e,φ(N))=1

(2)

即存在唯一私钥d。

这样对于明文m∈ZN,应用欧拉定理有

D(E(m))=D(c)=cd(modN)≡med(modN)≡mkφ(N)+1(modN)≡m(modN)

(3)

同理可证E(D(m))=m,因此E(D(m)=D(E(m))=m,这说明无论用于加密还是数字签名,该方案都遵循多素数RSA加密体制的原理,因此都是正确的。

1.2.2 公钥的可验证性分析

为防止“阈下攻击”用户恶意修改N值,需要验证用户传输过来的(e,N)是否是按秘钥托管机构要求产生的。对于N的正确性,可以通过下面的定理证明。

证明 假设各密钥托管机构托管的安全素数是p1、p2、…、pt,则需证明用户传输过来的N′是否等于各密钥托管机构想产生的N=p1,p2,p3,…,pt。

1.2.3 安全性分析

此方案依据的仍是标准RSA体制数学难题,并没有引入其他问题,没有扩大RSA密码体制的安全性基础。

首先,素数p1,p2,…,pt的产生和存储阶段,都经过了加密机的秘钥加密,因此产生和存储阶段是安全的。其次,传输阶段,传输前要用用户的通信加密秘钥的公钥进行加密,然后传输给用户,根据共钥密码学的相关知识,只有用户通过私钥才能解密,因此,传输安全。第三,私钥的安全性,当用户收到加密后的p1,p2,…,pt时,公钥的计算N=p1,p2,p3,…,pt和求解同余方程e d≡1(modφ(N))的过程都是用户在客户端单独计算的,因此私钥d的计算过程安全。第四,在多素数RSA密码体制下,各密钥托管机构Ti只拥有pi的信息,而无法获得N的完全分解信息。进而解决了托管机构权利滥用问题,这可以通过定理2得到证明。

定理2 如果IF问题是困难的,则无法获得N的完全分解信息。

最后,每个密钥托管机构Ti维护着素数备用数据库和素数正用数据库、素数归档数据库,分别管理未使用、正在使用的和已经使用过的公钥N的素因子pi,(i=1,2,…,t)的信息。如果想恢复用户的私钥d,至少需要t-1个密钥托管机构联合计算N。同时,一次司法监听之后素数数据库就会更新一次,有效预防了“一次监听,永久监听”的问题,使用户通信的安全性得到保障。

2 结束语

综上,分布式密钥托管方案基于多素数RSA密码体制,其托管对象不再是用户的私钥d,而是与计算用户私钥d直接相关的模N的安全素数分解因子pi。方案把目前独立的密钥托管机构联合起来,实现联合托管;托管机构和用户共同产生用户密钥,从而防止了用户的“阈下攻击”,托管过程中;用户不会向托管机构泄漏未托管的部分私钥的任何信息,从而避免了“早期恢复”问题;具有一定的门限能力,即对于由个密钥托管机构共同生成用户的公钥N,只有t-1个托管机构的联合才能恢复出用户的私钥来;监听过程中没有泄露加密会话密钥的密钥和托管代理所托管的子密钥的任何信息,监听机构只能获得用户某一次通信的会话密钥。

当然在密钥托管等方面,相比国外,国内的理论研究水平还是有一定的差距,有很多新概念和新技术是由国外的专家研究率先提出的,后来国内的学者也针对这些技术提出了新的改进。虽然在理论研究方面基本能够跟上国际水平的脚步,但对于信息安全技术来说,在技术和产品实现方面还要依赖其它的技术,如集成电路等技术的进步。

[1] Denning D E,Sm Id M.Key escrow ing today[J].IEEE Communications Magazine,1994,32(9):58-68.

[2] Shamir A.Partial key escrow:A new approach to software key escrow[M].Washington:Proceeding of Key Escrow Conference,1995.

[3] Len Stra A K,Winkler P,Yacobi Y.A key escrow system with W arrant bound[C].In:ProcCrypto’95,1995:197-207.

[4] Micali S.Fair cryptosystems[M].Cambridge,Massachusetts:Massachusetts Institute of Technology,1994.

[5] Micali S,Ney R.A simple method for generating and sharing pseudo-random functions with application to clipper-like key escrow system[C].In:ProcCrypto’95,1995:184-196.

[6] 杨波,马文平,王育民.一种新的密钥分割门限方案及密钥托管体制[J].电子学报,1998,26(10):1-3.

[7] Nechvatal J.A public-key-based key escrow system[J].Journal of Systems Software,1996,35(1):73-83.

[8] Denning D E,Branstad D K.A taxonomy of key escrow encryption systems[J].Communications of the ACM,1996,39(3):34-40

[9] 庄涌.PKI中的可验证部分密钥托管[J].计算机学报,2006,29(9):1584-155.

Research on the Distributed Key Escrow Scheme Based on RSA

MAO Zhiqin,CHENG Yuanyuan

(Department of Information Engineering,North China University of Water Resources and Electric Power,Zhengzhou 450011,China)

Based on RSA cryptography system,this paper carries out a further research on and optimization of the secret key escrow scheme,called Multi-prime RSA Cryptosystem.This optimization scheme satisfies the coordination between the user secret key security management and the judicial department’s investigation and evidence collection,effectively solving the problem of “once monitoring,permanent monitoring”.And each escrow agent can verify the validity of the sub-key it manages to realize the optimization of distributed hosting,and avoid such troubles as “subliminal channel attack” and abuse of power by the hosting department.

secret key escrow;multi-prime RSA cryptosystem

2014- 07- 23

毛志芹(1986—),女,硕士研究生。研究方向:密码学信息安全。E-mali:523339560@qq.com。程元元(1987—),女,硕士研究生。研究方向:代理签名。

10.16180/j.cnki.issn1007-7820.2015.04.042

TP309

A

1007-7820(2015)04-158-03