密钥体制（精选3篇）
密钥体制 篇1
在高中数学新课程选修系列3中, 有“信息安全与密码”一个专题, 其中有一个内容介绍密钥可以公开的密码通信问题——公开密钥体制。这种密码体制是将信件的原文x (称为明文) 利用加密钥匙E (它事实上是一个运算或更具体地说是一个函数) 加密成密文y (加密过程为E (x) =y) 发送。收信方收到密文y后再利用与加密钥匙E配对的解密密钥D (它也是一个运算或说是函数) 将之恢复为明文x (解密过程为D (y) =D (E (x) ) =x) 。所以通信的双方就必需拥有一对密钥{E, D}, 在数学上就称这对密钥互为反函数。所有密钥对{E, D}都要保密, 因而称为秘密密钥, 通信体制中, E, D两者若知道其中一个, 一般很容易求出另一个。
上世纪60年代后, 由于互联网提供的便利, 保密通信的需求急剧增加, 通信的领域从过去的军事、外交迅速向金融、商业甚至个人生活拓展。这就带来了一个严重问题:设想一个通信网络有200个用户A1, A2, A3, …, A198, A199, A200要互相进行保密通信, 因每2个用户就需1对密钥, 则整个通信网络需要的密钥为:
合计:199+198+197+…+3+2+1=200×99+1 00=1 9900对, 每个用户要保管他和其余199个用户间的199对密钥, 这无疑给网络管理者在密钥的制作与管理, 用户在密钥秘密保管方面带来了巨大的困难。这就促使密码专家积极寻求新的密码体制。
上世纪70年代中期, 美国年轻的数学家狄菲和计算机专家海尔曼提出采用“单向函数”来设计密码体制的新思路。所谓“单向函数”, 是指由加密密钥 (函数) E求解密密钥 (E的反函数) D极其困难, 或者实际是不可能的。反过来, 由D求E却是容易的, 并且E和D作为函数, 由自变量求函数值的运算也都容易实现。这样, 即使把加密密钥E和具体的加密与解密的算法过程都公开, 如果不知道解密密钥D, 把密文解密成明文的计算也无法实现。按照这种体制, 上述问题就可将所有用户的加密密钥E1, E2, E3, …, E199, E200都公开 (从而称为公钥) , 并汇编成册, 让各用户只秘密保管自己的解密密钥Di (称为私钥, i=1, 2, 3, …, 1 99, 200) 就行了。实施时, 首先由网络管理者为每个用户设计一对密钥{Ei, Di} (这时只需设计200对密钥, 比前述19900对减少了近100倍) , 把私钥Di交各用户Ai自己秘密保管 (这时各用户只需保管1个私钥, 比前述199对减少了近200倍) , 把所有公钥Ei汇编成公钥簿供用户查找。当用户Ai要发信息x给用户Aj时, 则先从公钥簿上查到Aj的公钥Ej, 用Ej对明文信息x加密:Ej (x) =y, 然后将密文y发送, Aj收到y后, 用自己的私钥Dj作用于y:Dj (y) =Dj (Ej (x) ) =x, 解密得明文x。这样, 即使密文被他人截获, 由于只有Aj秘密保管的私钥Dj才能对y解密, 所以截获的信息y对截获者毫无意义。
这种公钥体制创立后, 人们立刻发现还可用它来解决电子签名和身份认证问题。我们知道, 在通常的书信和文件中, 人们常常用签名、印章或指纹来表明自己的身份;收信者也凭此来确认信、文是否来自发信方。数字通信 (密码通信中往往把字母用数字来表示) 中也同样存在这类问题:发信方如何在信息上签名?收信方如何确认发信方的身份?如何辨认信、文是否伪造或被修改过?这些关系到信息安全的问题无疑亟待解决。而公钥体制正好为解决这些问题提供了一条途径:当用户Ai要把信息x签名后发给Aj时, 先用自己的私钥Di作用于x:Di (x) =y, 得到经他签名的信息y, 然后发送。Aj收到信息y后, 就从公钥簿上查到Ai的公钥Ei作用于y, 如果得到信息x (Ei (y) =Ei (Di (x) ) =x) , 就确认了信息是来自Ai的。进一步地, 当Ai要将信息x签名同时加密后发送给Aj时, 则首先将x用私钥Di签名得y:Di (x) =y, 然后查到Aj的公钥Ej对y加密得z:Ej (y) =z, 再将z发送。Aj收到信息z后, 先用自己的私钥Dj作用于z:Dj (z) =Dj (Ej (y) ) =y, 再查得Ai的公钥Ei作用于y:Ei (y) =Ei (Di (x) ) =x, 就得到并确认了是来自Ai的信息x。
但是, 狄菲和海尔曼提出的只是一种思想, 从以上的阐述中我们也知道这种思想是有依据的, 正确的, 可是要让这种思想成为现实还得取决于“单向函数”是否能构造出来。事实上, 1977年美国麻省理工学院三位年轻的密码专家就设计出了“RSA公钥体制”, 作为其“核心部件”的单向函数的构造是依赖于大整数因数分解的困难。因数分解是我们已熟悉的一个概念, 我们还知道除1和它本身外没有其他正整数因数的比1大的整数 (如2, 3, 5, …等) 为素数, 而等式4=2×2, 12=2×2×3, 60=2×2×3×5, …又说明: (1) 任何大于1的整数都可分解成素因数乘积的形式; (2) 整数越大, 分解的难度也越大。下表给出了用现代最快速的算法, 在大型计算机上分解一个大整数所需要的时间。这让我们看到大整数分解目前仍是一个非常困难的问题。让人未曾想到的是, 这种困难恰好被“RSA公钥体制”的创立者们用来构造单向函数并取得成功, 从而使公开密钥体制在现代社会获得了极为广泛的应用。
参考文献
[1]冯克勤.保密通信的发展概况[J].数学通报.2003 (11) .14
[2]教育部基础教育司.师范教育司.普通高中数学课程标准研修[M].北京.高等教育出版社.2004.110-116
[3]人民教育出版社.课程教材研究所等.初等数论初步[M].北京.人民教育出版社.2005.44-45
[4]毛明等.大众密码学[M].北京.高等教育出版社.2005.97-101.107-109
密钥体制 篇2
美国政府于1993年4月提出议案,倡导联邦政府和工业界使用新的具有密钥托管功能的联邦加密标准[1],这是最早的密钥托管方案,它是通过防串扰的芯片(clipper芯片)来实现的。在保密通信领域,存在两种相互矛盾的需要——通信用户对自身隐私的保密性需要与政府为抵制犯罪而进行搭线窃听的需要。而如何在这两种需要中寻求平衡是密钥托管的重要研究内容。
为解决这种矛盾,国内外诸多部门和专家进行了研究[2,3,4]。但是,目前提出的密钥托管方案大都是建立在有某一完全可信赖的部门基础上的,如密钥管理中心KMC,但是在现实生活中,很难找到完全可信任的部门。况且,掌握了大部分重要信息的KMC一旦被攻破,通信用户则无隐私可言。针对这种情况,本方案中,在防止用户、托管代理、监听机构欺诈的同时,将KMC的权力进行了限制,使其无法得到用户的私钥信息,也防止了KMC的欺诈。另外,方案还具有高效性和高安全性。这里采用基于状态树的(k,n)秘密共享算法[5]构造方案,它的运算开销远远低于基于Lagrange多项式插值[6]来构造的秘密共享方案。同时,出于安全性考虑,系统利用基于难解对数问题的ELGamal密码体制[7,8]来实现。
1 密钥托管方案
1.1 系统描述
假设该密钥托管系统包括以下5个主要成员:其中密钥管理中心(KMC),负责为所有用户颁发证书;进行通信的用户A、B,其中要进行密钥托管的用户设为A,其私钥为dA;由P1,P2,…,Pn组成的托管代理,被授权进行用户密钥的托管工作;E是政府的法律执行机构,负责对通信用户进行监听;法律授权机构,负责为监听机构进行法律授权。该系统的会话密钥设为sk,它由通信用户双方事先协商决定,sk在信道传送时使用ELGamal公钥密码体制进行加解密。系统在用户和托管机构之间,监听机构与托管机构之间分别建有安全信道。
1.2 方案的设计
系统基于ELGamal公钥密码体制,由密钥管理中心KMC选取p和g并将它们向系统内用户公开,其中p是一个大的安全素数,而g是GF(P)的一个本原元。若用户需要利用此系统进行通信,则必须先向密钥管理中心注册申请公钥证书。具体步骤如下。
(1)用户A向密钥管理中心申请托管业务,由密钥管理中心发放其身份证IDA。
(2)用户A自己选取部分私钥。首先,用户A随机选取d'∈Zp作为自己的私钥并保存,再计算gd'(modp)将其赋值给Y,最后只将得到的Y传递给密钥管理中心KMC。
(3)密钥管理中心收到Y后,再随机选取两个值t和d''(其中d''∈Zp),通过公式X≡gd"Y≠1(modp),y1≡gt(modp),y2≡(d''Yt)gt(modp),计算得到X、y1和y2。将得到的X公开,并把(y1,y2)回传给用户A。
(4)用户A的私钥由KMC和用户共同决定。用户利用KMC传递的(y1,y2),通过公式d''=(y2(y1d')-1)(modp)计算得到KMC选取的私钥碎片d''。然后,用户计算dA≡(d'+d'')(mod(p-1)),若dA为0,那么需重新注册,否则将所得dA作为自己的私钥,并且将公钥PA≡gdA(modp)公开。
(5)用户A将自己的私钥拆分并交由n个托管代理进行托管。方法为:用户A通过公式dA=d1+d2+…+dn将私钥拆分成n份,再将这些碎片通过秘密信道分发给n个托管代理。将密钥碎片di(i=1,2,…,n)作为托管代理Pi的私钥,用户A计算得它们的公钥Qi,将(di,Qi)发给托管代理,最后用户A公开自己的签名信息。这里采用基于状态树的(k,n)秘密共享方案实现。
(6)托管代理Pi收到用户发送的(di,Qi)后,首先,通过公式Qi≡gdi验证收到的私钥和公钥是否正确。若公式成立,则认为托管的内容是有效的,否则是无效信息,可以要求重新发送。其次,验证用户A的签名信息是否有效。若两项都符合,那么托管代理生成托管证书。(其中托管证书应包括用户A的特定标示符UID、托管代理的标示符、托管代理的公钥和托管证书号。)最后,托管代理用自己的签名私钥对此信息签名后发给KMC,否则不签名。
(7)密钥管理中心KMC在接收到各托管代理的信息后,都要先验证其托管证书的真实性,并且在收到全部代理的信息后,通过公式(1)验证其托管内容的完整性。
若KMC验证公式(1)的等式成立,则证明用户A确实将自己的私钥进行了托管。如果验证全部通过,那么KMC将为用户A颁发公钥证书C(A),否则不予注册。
1.3 用户间的通信
设用户A、B欲使用该系统进行通信,那么双方将在事先共同决定本次通信的会话密钥sk。假设A作为发送方想向接收方B传递消息M,通信过程如下所示。
(1)发送方
发送方A先向接收方B或KMC获得B的公钥证书C(B),再选择随机数c∈Zp,计算(a,b)=(gc(modp),sk*PBc(modp)),其中PB是B的公钥。发送方A通过安全信道向B发送{E1(M,sk),LEAF}。E1(M,sk)是传统密码加密体制,如3DES、IDEA等;而LEAF={(a,b),T,S(H(M,T)),IDA,IDB,C(A)}(其中T代表时戳,H是一个被公开的Hash函数),用户A用自己的私钥对H(M,T)进行签名后得到S(H(M,T))。
(2)接收方
用户B接收到用户A发的消息后,通过解密算法恢复消息。首先,通过ELGamal解密算法恢复事先协商的本次通话密钥sk,计算sk=b*(adB)-1(modp);再由sk得到A传送的消息M。恢复出M后需验证其有效性。利用M求H(M,T),若其与收到的S(H(M,T))中的H(M,T)一致,那么确认本次接收的消息有效,否则无效。
1.4 监听过程
(1)要实现监听,监听机构必须首先向法律授权机构申请并取得监听授权。监听机构在截获用户间通信的信息{E1(M,sk),{(a,b),T,S(H(M,T)),IDA,IDB,C(A)}}后,将监听授权证书和LEAF出示给任意k个托管代理。
(2)托管代理Pi(i=1,2,…,k)在验证了监听机构所持许可证的正确性和时效性后,将Si≡adi(modp)传递给监听机构。
(3)监听机构收到Si(i=1,2,…k)后,计算公式(2)
计算本次会话密钥sk=b*S-1(modp),在利用sk解密E1(M,sk)即可得到明文M,最后,计算H(M,T),验证其是否满足签名方程,若满足则说明M是有效的。
2 性能分析
定理1若成立,则认为托管代理机构托
管并上交给KMC的密钥是完整有效的。
证明
此,托管代理机构托管并上交给KMC的密钥是完整有效的,即用户确实进行了托管,等式成立。
定理2用户A、B通信过程中,B可以通过自己的子密钥计算得到会话密钥sk,从而实现保密通信。
证明sk=b*(adB)-1(modp)=sk*PBc(gc)dB)-1(modp)
因此,B可以通过自己的子密钥dB计算得到会话密钥sk,从而实现保密通信。
3 安全性分析
(1)该方案具有极高的安全性。系统采用的基于离散对数问题困难性的ELGamal密码体制具有更高的抗攻击力。如用户向KMC传递的Y≡gd'(modp),由离散对数的困难性可知,攻击者无法获知用户选取的私钥d'的任何信息;而(k,n)门限方案也具有安全特性,即唯有t个或更多的子密钥才能恢复密钥,方案中的所有等式皆不会泄露任何私钥信息。
(2)该方案可防止用户欺诈、托管代理和密钥管理中心的欺诈。用户的密钥不再由用户独立选取,而是采取了由用户和密钥管理中心各选部分碎片的方式,因而两方都不能独自决定私钥。这里由于用户不具备私钥的绝对选择权致使用户无法欺诈,同时也可以避免阈下信道攻击。系统中,密钥管理中心生成用户证书的必要条件是验证其托管内容的有效性和完整性,这样可以避免用户逃脱托管,同时避免托管代理提交假的或无效份额,避免了用户和托管代理的欺诈问题,从而为政府的合法监听提供了保证。而对于密钥管理中心来说,它无法从用户传递的Y中获知用户自选私钥碎片d'的任何信息,从而防止了KMC的欺诈。
(3)通信时,发送方会在其传递的信息{E1(M,sk),LEAF}中,在LEAF上添加时戳T,并对此时戳一起签名,从而使通信的信息具有了时效性。监听机构若想进行监听,那么它除了需要向委托人出示法院的许可证书外,还需说明进行监听的时间。因此,可防止政府监听机构在获得用户的密钥后伪造用户的签名,并且在合法的监听结束后用户可以不必更新自己的私钥,从而达到保护用户隐私的目的。
(4)方案可避免所谓的“一次监听,永久监听”问题,这里政府的监听机构重构的只是当次通信的会话密钥sk,它无法得知用户之前和以后的通信信息。并且在监听过程中,监听机构并没有获得用户的任何私钥信息,因为监听机构无法从各托管代理传递的Si≡adi(modp)中得知di的信息,即无法得知用户私钥,那么用户也无需在通信后更换私钥。
(5)该方案具有计算量小、效率高的优势。现在常用的Shamir(k,n)门限秘密共享算法的时间复杂度为O(nt-1),而该方案中使用的基于状态树的(k,n)门限秘密共享方案,它的时间复杂度仅为O(t),从而大大节省了计算的时间。
4 结束语
综上所述,论文采用高安全性的ELGamal密码体制和高效率的基于状态树(k,n)门限秘密共享算法,设计了一种可防止欺诈的门限密钥托管方案。经验证,方案具有计算量少、效率高的优势,且在防止用户、托管代理、监听机构欺诈的同时,提出并解决了防止密钥管理中心欺诈的问题。系统具有较强的灵活性和适应性,可根据需要增删成员,有广泛的实用性。
摘要：为寻求用户间秘密安全通信和监听机构合法监听之间的平衡,论文采用ELGamal密码体制和基于状态树的(k,n)门限秘密共享算法,设计了一种高安全性的门限密钥托管方案。经验证,方案在防止用户、托管代理、监听机构欺诈的同时,提出并解决了防止密钥管理中心欺诈的问题。
关键词：门限方案,ELGamal密码体制,密钥托管,KMC
参考文献
[1]Denning D E,Smid M.Key escrowing today[J].IEEE Communication Magazine,1994,32(9):55-68.
[2]M.H.Dehkodi,S.Mashhadi.An efficient threshold verifiable multi-secret sharing[J].Computer Standards&Interfaces,2008,30(3):187-190.
[3]孙晓蓉,工育民.基于RSA的密钥托管方案[J].电子科学学刊,1999,21(6):833-837.
[4]Amr M.Youssef.Cryptanalysis of Boolean permutation-based key escrow scheme[J].Computers and Electrical Engineering,2010,36(1):56-60.
[5]张春生,姚绍文,张险峰.基于状态树的(t,n)门限密钥托管方案[J].计算机工程与应用,2007,43(4):146-149.
[6]L.Luksan,C.Matonoha,J.Vlcek.On Lagrange multipliers of trust-region subproblems[J].Bit Numerical Mathematics,2008,48(4):763-768.
[7]张亚玲,张超奇,马巧梅.读写器可移动的RFID高效认证协议[J].计算机工程,2012,38(1):264-267.
密钥体制 篇3
关键词：RAS密钥算法,攻击方式,密钥长度,安全程度
1 问题的提出
加密与解密就像是一对难兄难弟,纠结不清已经有几千年了,在重重的矛盾中其思想和方法不断地发展。密码学经历过曲曲折折,多次曾面临严重危机。自从20世纪70年代,电子技术、计算技术的迅速发展以及结构代数、可计算性和计算复杂性理论等学科的研究,特别是美国的数据加密标准DES(Data EncryptionStandard)和公开密钥密码体制(public key crypto-system)这两个重要里程碑的出现,密码学又迎来了一个新的发展时期。
由Stanford大学的研究人员Diffie与Hellman于1976年《New Directions in Cryptography》文中提出了公开密钥密码体制的概念。这个概念就是使用不同的加密密钥与解密密钥,形成一种“解密密钥不可能由已知加密密钥计算推导出”的密码体制。
在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出SK。
不久,人们就找到了三种公开密钥密码体制。最著名的就数由美国三位科学家Rivest、Shamir和Adleman于1976年提出,并在1978年《A Method for Obtainning Digital Signature and Public Key Cryptosystems》文中正式发表的RSA公钥体制,它是基于数论中大数分解问题的体制。目前,它在数学上是一个困难问题。RSA算法既能用于数据加密,也能用于数字签名,其理论依据为:寻找两个大素数比较简单,而将它们的乘积分解开则异常困难。
但随着计算机科学和密码学技术的不断发展,密码的安全也受到越来越严峻的挑战。本文就RSA体制密钥长度与安全的关联程度问题进行讨论。
2 RSA算法原理
RSA公开密钥密码体制算法原理如下:选出两个大素数,r1和r2(素数r1和r2通常为100位以上的十进数)。然后计算n=r1*r2和x=(r1-1)*(r2-1)。再选一个与x互质的数设其为d。寻找一个e,且满足e*d=1(mod x)。待选好n、e、d参数后,将明文划分成字符块使得每个明文报文Pi长度m满足0
虽说加密和解密的变换是“互逆”的。但私钥系统把数据作为比特来处理,而公钥系统则把数据作为数字进行函数运算处理,并且这种数学函数是单向的,即在一个方向上是容易的,另一个方向上却异常困难。那么简单地颠倒步骤是无法解密密文。
3 RSA运算的应用
下面用一个简单的例子来说明RSA公开密钥密码算法的工作原理。
取两个素数r1=11,r2=13,r1和r2的乘积为n=r1×r2=143,算出秘密的欧拉函数x=(r1-1)×(r2-1)=120,再选取一个与x=120互质的数,例如e=7,作为公开密钥,e的选择不要求是素数,但不同的e的抗攻击性能力不一样,为安全起见要求选择为素数。对于这个e值,可以算出另一个值d=103,d是私有密钥,满足e×d=1 mod x,其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd(a,b),并可判断a与b是否互素,因此该算法可用来寻找解密密钥。
(n,e)这组数公开,(n,d)这组数保密。
设想需要发送信息x=85。利用(n,e)=(143,7)计算出加密值:
收到密文y=123后,利用(n,d)=(143,103)计算明文:
余数85即是原发送信息。
4 破解RSA的主要方式
RSA中的单向函数是乘法运算。求解乘积的原来两个数的问题就是因子分解。而RSA算法的安全性猜测则完全基于大素数因子分解问题。所以,破解RSA算法主要有三种可能:
1)对所有私有密钥都进行穷举尝试;
2)对n进行两个素数因子分解;
3)对解密算法的运行时间进行统计分析破解。
因此,要防范对RSA的强行攻击,就要用一个大的密钥,e和d的比特数越多越好,当然密钥产生和加解密速度也相应地越慢。
理论证明,使用已知的算法求出d似乎在时间开销上和n的因子分解问题一样大。所以可把因子分解的性能作为评价RSA安全性的标准。也就假设对n的因式分解是很困难的。
当前最好的因子分解的算法有平方筛(quadratic sieve,也叫二次筛)算法、数域筛RSA密码体制(number field sieve.,NFS)算法等等。有人计算,用最快的数域筛因子分解一个664比特的数需要执行1023步,假设一台计算机每秒可执行1亿步,那么100万台计算机的网络完成这个任务也需要40年。由于n就是破解需要分解的数,所以说它的长度就是RSA密钥的长度。
5 破解的密钥长度在不断刷新
在RSA算法中,n的长度是控制该算法可靠性的重要因素。目前129位、甚至155位的RSA加密勉强可解,但目前大多数加密程序均采用231、308甚至616位的RSA算法,因此RSA加密还是相当安全的。据专家测算,攻破155位密钥RSA算法大约需要8个月时间。
2007年,瑞士洛桑理工学院(EPFL)的Arjen Lenstra宣称,利用分布在瑞士EPFL、德国波恩大学、日本电报电话公司等地的三四百台笔记本和台式机的空闲资源,借助专门的数学方程,在经过11个月的努力后破解了一个RSA-307位的RSA密钥,并且已经有能力在不久后破解700位,因此他警告说,在五六年后,随着各种计算、破解技术的不断强大,也许308位的RSA加密都不能完全保险,人们必须寻求更安全的加密技术。
6 小结
其实,在理论上绝对不可破译的密码是存在的,却不可能获取。任何实际的密码都是可破译的。而我们所追求的目标,就是在有限的资源与时间内无法破译的密码体制。
密码专家最近已然利用分布式计算网络破解了数百位的RSA(特定的)加密密钥,虽还没能达到实用的程度,但对密码的安全已构成严峻的挑战,在技术上攻破具有616位密钥的RSA加密算法需要多少时间,我们还难以预测。
实际应用中的RSA加密算法会针对每个用户使用一个特殊的密钥,要破解它们的话就必须逐一分解质因数,这个任务的艰巨性可想而知。因此,至少在目前我们仍可以信赖RSA密码的安全性。
参考文献
[1]陈晓明.数据加密方法的分析[J].科技资讯,2008(9).
[2]韩立东,王小云,许光午.RSA密码系统小CRT解密指数的攻击分析[J].中国科学:信息科学,2011(2).
[3]刘月茹,刘月兰.公开密钥加密算法在网络信息安全中的应用[J].情报科学,2003(1).
[4]黄淑华.计算机网络技术教程[M].北京:机械工业出版社,2004.
[5]郑永辉,祝跃飞,徐洪.RSA的类循环攻击[J].华中科技大学学报:自然科学版,2009(12).