一些公钥密码体制在阿贝尔群上的扩展.docx

第3卷第3期本溪冶金高等专科学校学报Vd．3No．32001年9月JoURNALOFBENXI．COLI脚OFMETALUJRGYS印．200l文章编号：1008—3723(2001)03—0020—04一些公钥密码体制在阿贝尔群上的扩展费如纯(本溪冶金高等专科学校计算机系，辽宁本溪117022)摘要：公钥密码体制对于计算机安全和信息必威体育官网网址具有重要意义，因此公钥密码体制是密码学领域的一个研究热点。本文讨论了一些公钥密码体制(ElGaIllal加密与解密算法、Diffie—HdIman密钥交换方案和Shamir协议)在阿贝尔群上的扩展，它们的安全性均建立在阿贝尔群上离散对数求解困难性的基础之上。关键词：公钥密码体制；阿贝尔群；离散对数；安全通信中图分类号：TP309文献标识码：AHelhnan密钥交换体制和Sh锄ir的三次通过协议在O引言阿贝尔群上的扩展，它们的安全性均建立在阿贝尔群上离散对数求解困难性的基础之上，另外还对信息嵌1976年，Diffie和Hellman首次提出了成对密钥入问题进行了说明。的概念：一个加密密钥和一个解密密钥，而从一个密钥推导另一个密钥在计算上是不可能的。几个月后，1阿贝尔群及离散对数问题他们发表了著名的论文“密码学的新方向”[1】，开创了公开密钥密码体制的研究。也成为现代密码学产我们首先来看一下什么是阿贝尔群。设G是一生的标志，从此，许多密码学者对公开密钥密码体制个集合，“☆”是定义在G上的一个二元运算，则G，进行了广泛而深入的研究，数据加密、密钥交换、数字☆是一个群当且仅当G，☆满足：签名、秘密共享和零知识证明等密码学领域的研究得(1)封闭性：对于任意的a∈G，b∈G，均有a☆b到了空前迅猛的发展。1978年，Markle和Hellman∈G；开发了第一个得以推广的公开密钥加密算法：一次背(2)结合性：对于任意的a，b，c∈G，均有(a☆b)包算法【2J，但这个算法在1982年就被Sh锄ir(3】找到☆c=a☆(b☆c)；、了破译的方法。1978年，Rivest、shamir和Adl锄an(3)单位元：存在e∈G，使得对于任意a∈G，均设计出了第一个成熟的具有里程碑意义的公开密钥有a☆e=e☆a=a，这里的e称为单位元；算法：著名的RSA算法【4]，此算法可以用于数据加(4)逆元：对于任意a∈G，均存在b∈G，使得a密，也可以用于数字签名。到目前为止，还没有找到☆b=b☆a=e，这里的b称为a的逆元，记为b=a～。破解礤、A算法的很好方法。1985年，ElGamal设计一个群G，☆是阿贝尔群，当且仅当它再满了可以用于数据加密和数字签名的ElQIITlal体制【5】，足如下条件：、目前，这个体制还没有被证明是不安全的。另外，(5)交换性：对于任意的a∈G，b∈G，均有a☆bDiffie和Hellman提出了一种公钥密码体制【6】，允许=b☆a。双方或多方通过密钥交换协议秘密地进行密钥的传下面讨论阿贝尔群上的离散对数问题。送。Sh锄ir提出了信息秘密传送的三次通过协设G，☆是一个阿贝尔群，则G，☆上的议(6】，允许通信双方不用协商密钥就可以安全地通离散对数问题为：已知a，b∈G且a≠e，求s∈zo使信。得b=as。这里a3表示a☆a☆一☆a(共s项)。已知s本文首先讨论了阿贝尔群以及阿贝尔群上的离∈zo时，计算b=as有快速算法，是非常容易的，计散对数问题，然后重点讨论了E1Gamal体制、Diffie—算量只有O(10簖8)。但是，已知a，b∈G且a≠e，求s收稿日期：2001一07—08作者简介：费如纯(1968一)，男，河北人，本溪冶金高等专科学校计算机系讲师，工学硕士万方数据∈Zo使得b=as却是困难的。这个特性使得我们可ElGamal体制既可以用于加密，也可以用于数字以在阿贝尔群上构造基于离散对数问题的公钥密码签名。ElQ吼al的加密体制可以被扩展到素数阶群体制。上。设G，☆是p阶阿贝尔群，其中p是一个大命题1设G，☆是一个有限阿贝尔群，a∈素数。要产生一对密钥，首先选择G中一个不是单G，则必定存在s∈Zo使得as=e。位元的元素g，选择小于p的一个随机数x，然后计算证明：若a=e，结论显然成立。y=g】【，公开密钥是p、g和y，秘密密钥是x。若a≠e，使用反证法，假设不存在s∈zo使得as设甲要向乙传送信息M∈G，甲已知乙的公开密=e，则不存在u，v∈Z0且uv使得au=av(不然钥p、g和y，但不知乙的秘密密钥x。甲对信息M加的话可得u—v使得aul=e)，则a1，a2，是一个无密的步骤如下：重复元素的序列且这些元素均属于G，但由于G是(1)选择一个随机数k，使k与p一1互素；一个只有IG1个元素的有限集合，因此假设不成立，(2)计算a=gk，b=yk☆M；命题得证。(3)将a和b作为密文