第２３卷第５期 ２０１３年５月 计算机技术与发展 ＣＯＭＰＵ ｒＥＲ ＩＥＣＨＮＯＬＯＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ Ｖｏ１．２３ Ｎｏ．５ Ｍａｖ． ２０１３ 离散对数问题攻击算法的改进 汤鹏志，何涛，李彪 （华东交通大学基础科学学院，江西南昌３３００１３） 摘要：在求解离散对数问题上有袋鼠攻击、生日攻击、小步一大步攻击、指数积分攻击等多种方法，而小步一大步攻击算法 是比较通用且高效的。为了提高攻击算法的速度，改善算法的效率，提出的改进算法牺牲了适当的存储空间，但在运算之 前通过奇偶判断筛选过程减少了判断的次数甚至有数量级的减少。性能分析表明，改进的算法在性能上优于原算法。并 且预处理过程中产生的数据可以重复利用来求解同一群下不同生成元的离散对数问题，这又进一步减少了算法的运算复 杂度。 关键词：离散对数；小步一大步攻击算法；奇偶判断 中图分类号：ＴＰ３０９ 文献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２０１３）０５—０１２７—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３—６２９Ｘ．２０１３．０５．０３３ Ｉｍｐｒｏｖｅｄ Ａｔｔａｃｋ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ Ｐｒｏｂｌｅｍ ＴＡＮＧ Ｐｅｎｇ－ｚｈｉ，ＨＥ Ｔａｏ，ＬＩ Ｂｉａｏ （Ｓｃｈｏｏｌ ｏｆ Ｂａｓｉｃ Ｓｃｉｅｎｃｅ，Ｅａｓｔ Ｃｈｉｎａ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ ３３００１３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅｒｅ ａｒｅ ｋａｎｇａｒｏｏ ａｔｔａｃｋ，ｂｉｒｔｈｄａｙ ａｔｔａｃｋ，ｂａｂｙ－ｓｔｅｐ—ｇｉｎｔ—ｓａｔｅｐ ａｔｔａｃｋ，ｅｘｐｏｎｅｎｔｉａｌ ｉｎｔｅｇｒａｌ ａｔｔａｃｋ ａｎｄ ｏｔｈｅｒ ｍｅｔｈｏｄｓ ｉｎ ｓｏｌ— ｖｉｎｇ ｔｈｅ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｈｍ ｐｒｔｏｂｌｅｍ．Ｔｈｅ ｂａｂｙ～ｓｔｅｐ—ｇｉａｎｔ—ｓｔｅｐ ａｔｔａｃｋ ａｌｇｏｒｉｈｍ ｉｔｓ ｍｏｒｅ ｖｅｒｓａｔｉｌｅ ａｎｄ ｅｆｉｃｉｆｅｎｔ．Ｉｎ ｏｒｄｅｒ ｔＯ ｉｍｐｒｏｖｅ ｔｈｅ ｓｐｅｅｄ ｏｆｔｈｅ ａｔｔａｃｋ ａｌｇｏｒｉｈｍ ｔｎｄ ｔａｈｅ ｅｆｉｃｉｆｅｎｃｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｈｍ，ｔｔｈｅ ａｌｇｏｒｉｔｈｍ ｐｒｏｐｏｓｅｄ ｉｓ ｉｍｐｒｏｖｅｄ ａｔ ｔｈｅ ｅｘｐｅｎｓｅ ｏｆ ｔｈｅ ａｐｐｒｏｐｒｉａｔｅ ｓｔｏｒａｇｅ ｓｐａｃｅ．Ｂｙ ｔｈｅ ｐａｒｉｔｙ ｏｐｅｒａｔｏｒ ｂｅｆｏｒｅ ｔｈｅ ｊｕｄｇｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｃｅｓｓ ｒｅｄｕｃｅ ｔｈｅ ｎｕｍｂｅｒ ｆｊｕｄｇｍｅｎｔ，ｅｖｅｎ ｔｏｈｅ ｅｄｕｃｔｒｉｏｎ ｏｆ ｈｅ ｍａｇｎｉｔ— ｔｕｄｅ．Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅａｎａｌｙｓｉｓ ｓｈｏｗｓｔｈａｔｔｈｅｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｏｕｔｐｅｒｆｏｒｍｓｔｈｅ ｏｒｉｇｉｎａｌａｌｇｏｒｉｔｈｍ．Ａｎｄｔｈｅ ｄａｔａ ｇｅｎｅｒａｔｅｄｉｎｔｈｅ ｐｒｅ— ｔｒｅａｔｍｅｎｔ ｐｒｏｃｅｓｓ Ｃａｎ ｂｅ ｒｅｕｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｈｅ ｇｅｎｅｒｔａｔｏｒ ｕｎｄｅｒ ｈｅ ｓａｎｌｔｅ ｇｒｏｕｐ ｏｆ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ．Ｔｈｉｓ ｆｕｒｔｈｅｒ ｒｅｄｕｃｅｓ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｈｅ ａｔｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｈｍ；ｔｂａｂｙ－ｓｅｐ－ｇｉｔｎｔａ—ｓｔｅｐ ａｔｔａｃｋ ａｌｇｏｒｉｈｍ；ｐａｒｔｉｔｙ ｊｕｄｇｍｅｎｔ Ｏ 引 言 离散对数公钥加密算法是目前最为热门的加密算 法，其安全性远远高于ＲＳＡ算法，Ｄｉｆｉｆｅ—Ｈｅｌｌｍａｎ密钥 协议、Ｅ１Ｇａｍａｌ密码及其相关变种的签名方案都 是建立在离散对数问题之上。针对离散对数问题的攻 建了链表，执行过程中的查表操作大大降低了算法的 效率，增加了算法的执行时间。 同时由于基于离散对数问题的各种签名方案 的提出，如何有效地利用离散对数构造安全有效的方 案也是面临的难题，所以从离散对数问题的攻击方法 人手，可以更好地通过离散对数问题提出更有效的方 案。文中结合文献［８］提出的奇偶判断思想，提出了 种新的攻击离散对数的方法，与传统算法比较该算 一击方法，已知的指数积分攻击 、小步一大步攻击 、 袋鼠攻击 、生日攻击 等攻击算法，不同的攻击算法 针对基于不同群下的离散对数问题效率不一，Ｐｏｌｌａｒｄ— Ｈｅｌｌｍａｎ 算法针对群的阶只有小素因子时攻击特别 有效，而ｉｎｄｅｘ—ｃａｌｃｕｌｕｓ 算法是亚指数攻击算法，只 法提高了执行效率并降低了时间复杂度。 对特定的群有效。传统的小步一大步攻击算法由于构 １ 预备知识 给定一个元素ｙ，且已知存在一个整数 ，对一个 收稿日期：２０１２—０８—０２：修回日期：２０１２一ｌ１一Ｏ５ 基金项目：国家自然科学基金资助项目（１１０６１０１４）；江西省教育青 固定的基ｂ，有Ｙ＝ｂ ，如何求解 ，就是一个离散对数 问题。 年科学基金项目（ＧＪＪ１１６７５）；江西省教育科研项目（ＧＪＪ１１６７８） 作者简介：汤鹏志（１９６１一），男，江西九江人，硕士，教授，主要研究方 一定义１：给定一个素数Ｐ，Ｚｐ 的一个生成元ａ及 个元素口∈Ｚｐ ，寻找整数ｘ（０≤ ≤Ｐ一２），使得 ｍｏｄｐ。 向为信息系统及其安全；何涛（１９９０一），男，江西丰城人，硕士研究 生，主要研究方向为信息安全。 上述给出的是离散对数问题的定义，直观上看该 ・１２８・ 计算机技术与发展 第２３卷 问题的困难性取决于问题的规模以及参数的选择，根 据离散对数假设 可知在充分大的有限域中，对于所 有的情形，不存在求解离散对数问题的有效算法。然 而现实世界中事物是有界的，则一定存在多项式时间 解法。通过规定适当的下界使得多项式时间解法所运 行的时间是一个难以对付的大数，正因如此该问题的 难解性构成了包括Ｄｉｆｉｆｅ—Ｈｅｌｌｍａｎ密钥分配，ＥｌＧａｍａｌ 公钥密码等在内的很多密码的安全性基础 ’ 。 定理１：设Ｇ＝（ｏ）是循环群，则有： （１）若Ｇ是无限循环群，则Ｇ只有两个生成元，即 ｎ和０～。 （２）若Ｇ是ｎ阶循环群，则Ｇ含有 （ｎ）个生成 元，对于任何小于等于ｎ且与／１，互质的正整数ｒ，ｏ 是 Ｇ的生成元。 证明（１）：显然（ｎ ） Ｇ，对于任何ｎ ∈Ｇ，０ 都可以表示成为ａ 的幂，则可以得到ｏ ＝（ａ ）一后， 从而得到Ｇ （ｎ ），则Ｃ／， 是Ｇ的生成元。 假设ｂ也是Ｇ的生成元，则Ｇ＝（６），由口∈Ｇ可 知存在整数ｔ，使得ｎ：６ 。又由ｂ∈Ｇ＝（。）知存在 整数ｍ，使得ｂ＝ｏ ，从而有口＝ｂ ＝（０ ）『＝ｎ ，由消 去律得口一 ＝ｅ，因为Ｇ是无限群，必有ｍｔ一１＝０，从 而证明ｍ＝ｔ＝１或者ｍ＝ｔ＝一１，即６＝口或者ｂ＝０一。 （２）只要证明：对于任何正整数ｒ（ｒ≤ｎ），ｎ 是 Ｇ的生成元当且仅当ｎ与ｒ互质。 充分性：设凡与ｒ互质，且ｒ≤ｎ，那么存在整数 ， 使得１／，Ｆ＋ｎ ＝１，根据拉格朗日定理的推论有。＝ ｎ” ”＝（０ ）“（０ ） ＝（口 ） ，贝０可以推出Ｖ ０ ∈Ｇ，口 ：（ｎ ）ｕｋ∈（０ ），即Ｇ （ａ ），显然可知（０ ） Ｇ， 从而有Ｇ：（ｏ ）。 必要性：设ｏ 是Ｇ的生成元，则ｌ ｏ ｌ＝ｎ，令ｒ和ｎ 的最大公约数为ｄ，则存在正整数ｔ使得ｒ＝ｄｔ，则有 （ａ ） ＝（ｏ ）－ｇ＝（０ ）‘＝ｅ，根据群的性质可知 ＩＩ是ｎ／ｄ的因子，即ｎ整除ｎ／ｄ，从而证明了ｄ＝１。 命题１若６以＝１ｔｏｏ＠，则ｌｏｇ。ｂ是偶数，否则是奇 数。 证明：设 ＝ｌｏｇ ｂｍｏｄｎ，则６＝ａ￣ｍｏｄｐ。由 （ｎ以） ＝口“＝１ｍｏａｐ，则０ ：±ｌｍｏｄｐ。因０的阶为 ｎ，有Ⅱ ≠ｌｍｏｄｐ，从而６以＝０ ＝（一１） ｍｏ＠，也 即６以＝１ｍｏｄｐ时，ｌｏｇ。ｂ是偶数，否则是奇数。 ２小步一大步攻击算法及分析 算法１ Ｓｔｅｐ１ ｓ １，Ｍ １，￡ｔ Ｎｕｌｌ，ｍ ｒｎ÷］ Ｓｔｅｐ２ ｆｏｒｊ＊－４３ ｔｏ／７／，——１ Ｓｔｅｐ２．１ ｓ＋＿ Ｓｔｅｐ３根据第二个坐标对有序对（ ，ｏ ）进行排 序，得到链表 ， Ｓｔｅｐ４ ｆｏｒ ｉ ０ ｔｏ ｍ一１ Ｓｔｅｐ４．１“ ６Ⅱ一 ｓｔｅｐ５根据第二个坐标对有序对（ｉ，ｂａ－ｉ）进行排 序，得到链表 ： Ｓｔｅｐ６通过查找 。和 两个链表中（，ａｗ）和 ． （ｉ．６口 ）中第二个坐标相同的有序对 ｓｔｅｐ７ Ｌｏｇ。ｂ＋＿（ 一 ）ｍｏｄｎ结束 以群乘法为基本运算单位来分析该算法的时间和 空间复杂度。 在Ｓｔｅｐｌ中为了快速计算首先要预先计算ｏ 并缓 存，利用平方乘算法来进行高次幂运算，此步的时间复 杂度为Ｄ（１ｏｇｍ）。 在Ｓｔｅｐ２中空间复杂度为Ｄ（ｍ），一共要计算ｍ 次，时间开销为Ｄ（ｍ）。 在Ｓｔｅｐ３中要对生成的有序对进行排序，利用快 速排序算法，算法的时间复杂度为０（ｍｌｏｇｍ），空间 复杂度为０（ｍ），同样Ｓｔｅｐ５的时间复杂度和空间复 杂度和本步相同。 在Ｓｔｅｐ４中空间复杂度为Ｄ（ｍ），一共要计算ｍ 次，并且由于增加了求逆的运算，求逆的算法时间复杂 度为Ｏ（１ｏｇａ），Ｓｔｅｐ４．１的开销为Ｄ（ｍ）。 在ｓｔｅｐ６中由于要查找两个生成的链表中第二坐 标相同的有序对，需要对两链表逐一比较，最大的比较 次数为Ｄ（ｎ），平均比较次数为Ｄ（ｎ／２）。 算法成功停机的充要条件是ｂ∈（ｎ），（ｎ）为由 。生成的群。 必要性：成功停机说明算法１的Ｓｔｅｐ６中的等式 ｎ ＝），＝ｂａ 成立，则ｂ＝口‘ “ ，由于１≤ｉ ≤ｍ，有 ０≤ ＋ ，又０是生成元，所有６∈（ｏ）。 充分性：因为ｂ∈（ｎ），０≤ｌｏｇ ６≤ｎ一１，ｍ＝ ｒ 卞］，所以０≤ｌｏｇ。ｂ≤ｎ一１≤ｍ２—１。令１≤ｉ≤ ｍ且ｌｏｇ ６：阿＋ｉ，则可知１≤ｉ≤ｍ。当ｉ， 满足１≤ ｉ，＿『≤ｍ时，１０ｇ。ｂ可以写成ｌｏｇ ｂ＝ ＋ｉ。口是生成元， 有ｂ＝口‘阿 ，即Ⅱ ＝ｂａ～，则算法１的ｓｔｅｐ６一定可 以成功，所以算法１可以成功停机。 ３改进的算法 首先利用算法１的结束条件计算出满足条件的 （ｉ，ｐ对，把（ ， ）对根据命题１的奇偶判断条件进行 奇偶性分组，然后通过命题１的判断结果得到ｌｏｇ ｂ的 奇偶性，再结合ｌｏｇ。ｂ和（ｉ，ｆ）对的奇偶性进行快速求 解离散对数问题。给出算法如下： 第５期 汤鹏志等：离散对数问题攻击算法的改进 ・１２９・ 算法２ Ｓｔｅｐｌ预处理 Ｓｔｅｐ１．１ ｆｏｒ ｉ＋－１ ｔｏ，ｎ Ｓｔｅｐ１．１．１ ｆｏｒ １ ｔｏ ｍ ４改进算法的性能分析 根据群乘法为基本运算单位，分析改进的算法的 时间空间复杂性。 在Ｓｔｅｐｌ预处理中，算法根据结束条件计算出 （ｉ，一对的奇偶分组，时间复杂度为Ｄ（ｎ），空间复杂 度为Ｄ（ｎ／２），相比算法１此步骤的复杂度上相对较 大，考虑到算法的效率问题，这一步可以在计算之前预 先做好，对于相同的ｎ条件下，不同的生成元所产生的 奇偶链表是相同的，即在不改变ｎ的情况下，得到的奇 Ｓｔｅｐ１．１．２ ｉｆ（ｍｉ— ）ｉ １ｍｏｄ２ｎ Ｓｔｅｐ１．１．３ Ｌ１十一（ｉ， ）Ｌｌ存储奇数（ ， ）对 Ｓｔｅｐ１．１．４ ｅｌｓｅ ２一（ｉ， ） ：存储偶数（ｉＪ）对 Ｓｔｅｐ２系统初始化 Ｓｔｅｐ２．１ ５＋＿－１，“ １， ｌ Ｎｕｌｌ，Ｌ２＋＿－Ｎｕｌｌ，Ｌ３＋Ｉ Ｎｕｌｌ，Ｌ４ Ｎｕｌｌ Ｓｔｅｐ２．２ ｍ．＿－ｒ 卞］，ｍ转换成具有较小海明权 重¨¨的表示形式 Ｓｔｅｐ３判断奇偶性 Ｓｔｅｐ３．１ ｆｏｒ ＋＿１ ｔｏ ｍ Ｓｔｅｐ３．１．１ ｓ ｓ×口 Ｓｔｅｐ３．１．２ Ｌ３（ｓ） Ｓｔｅｐ３．２ ｆｏｒ ｉ １ ｔｏ １７１， Ｓｔｅｐ３．２．１ Ｍ “Ｘ ｎ Ｓｔｅｐ３．２．２ Ｌ４（ｓ） Ｓｔｅｐ３．３ ｉｆ ６ ＝１ｍｏ＠ｔｈｅｎ Ｓｔｅｐ３．３．１ ｆｏｒ（ｉ√）ｉｎ Ｌ２（ｉ， ） Ｓｔｅｐ３．３．２ｉｆ（ （ ）） ＝ｂ・ （ ），运用多精度平 方乘算法 计算（厶（ ）） Ｓｔｅｐ３．３．２．１ Ｌｏｇ。ｂ （ｍｊ— ）ｍｏｄｎ结束 Ｓｔｅｐ３．３．３ ｅｌｓｅ ｇｏ ｔｏ Ｓｔｅｐ３．３．１ Ｓｔｅｐ３．４ ｅｌｓｅ Ｓｔｅｐ３．４．１ ｆｏｒ（ｉＪ）ｉｎ Ｌｌ（ｉ Ｓｔｅｐ３．４．２ｉｆ（厶（．７）） ＝ｂ・Ｌ４（ ），运用多精度平 方乘算法计算（Ｌ，（ ）） Ｓｔｅｐ３．４．２．１ Ｌｏｇ ｂ＋－（ｍｊ＇一 ）ｍｏｄｎ结束 Ｓｔｅｐ３．４．３ ｅ］ｓｅ ｇｏ ｔｏ Ｓｔｅｐ３．４．１ 算法成功停机的充要条件是６∈（ｏ），（ｏ）为由 。生成的群。 必要性：成功停机说明算法２的Ｓｔｅｐ３．３．２．１或者 ｓｔｅｐ３．４．２．１中的等式（厶（『）） ＝６・厶（ ）成立，也 ．即等式０ ＝ｙ＝ｂａ‘成立，则ｂ＝口‘ ，由于１≤ｉＪ≤ ｍ，有０≤阿一ｉ，又０是生成元，所有ｂ∈（口）。 充分性：因为ｂ∈（Ⅱ），０≤ｌｏｇ。６≤ｎ一１，ｍ＝ ｒｎ十］，所以０≤ｌｏｇ ｂ≤ｎ一１≤ｍ 一１。令１≤ｉ≤ ｍ且ｌｏｇ。ｂ＝耐一 ，则可知１≤ｉ≤ｍ。当 ， 满足１≤ ， ≤ｍ时，ｌｏｇ。ｂ可以写成ｌｏｇ。ｂ＝耐一ｉ。口是生成元， 有ｂ＝０（ｍＪ ’，即０ ＝ｂａ‘，则算法２的Ｓｔｅｐ３．３．２．１或 者Ｓｔｅｐ３．４．２．１一定可以成功，所以算法２可以成功停 机。 偶链表可以提供给同一群的不同生成元求解离散对数 问题。 在Ｓｔｅｐ２中把高阶的幂指数利用较小的海明权重 形式表示，在计算高阶幂运算中可以减少乘法的次数， 显著提高算法的运算速度，提高的效率在１１％左右， 并且Ｓｔｅｐ２．２中不需要计算Ⅱ ，提高了该算法的计算 效率和存储空间。 在Ｓｔｅｐ３．１中，首先计算口的各次幂值，然后通过 Ｓｔｅｐ３．３判断结果值ｌｏｇ ｂ的奇偶性，根据判断结果的 奇偶性，利用预处理中得到的奇偶（ｉ， ）对，只需遍历 （ ． ）对中的奇数对链表或者偶数对链表，利用 （ｉ， ）对直接验证得到结果，时间复杂度为Ｄ（ｎ／４）， 同时不需要利用哈希表来对结果进行处理，直接查表 即可，查表时间为Ｄ（１）。 在Ｓｔｅｐ３．３和Ｓｔｅｐ３．４中利用多精度平方乘算法 可以提高运算速度，同时利用事先计算的。的各次幂 值，直接查询即可参与多精度平方乘运算，查表时间为 Ｄ（１）。 随着计算机发展的不断提高，计算机的计算能力 和计算机硬件的配置已经有了很大的进步，随着计算 机的普及和性能上的提升，以前相对较复杂的算法已 经逐步得到了改善和优化，同时对于一个算法而言，空 间的消耗对于一个算法的权重越来越小，相对于空间 复杂度，算法的时间复杂度的提升显的更加重要。在 计算效率上的提升是一个好的算法的重要指标。 ５算法对比分析 根据上面的算法分析，可以总结出以上两个算法 的不同之处。 １）预处理过程。算法１没有预处理过程，而算法 ２在预处理过程中产生了２个根据判定条件得到的奇 偶链表，并且该奇偶链表在ｍ值没有改变的情况下可 以重复使用，可以减少在ｍ值相同时的重复计算过 程，提高了代码的重用性和计算结果的利用率，并利用 其来求解同群下不同生成元的离散对数问题。 ２）求逆操作。算法１在计算中需要先计算ａ 并 ・１３０・ 计算机技术与发展 第２３卷 缓存，而算法２中不需要求逆操作，因此算法２在计算 效率上更高。 都是相同的，根据定理１可知在求解同一群下其他生 成元的离散对数情况时，可以直接利用算法２中得到 的（ ， ）对来进行计算，通过这一方法可以减少算法２ ３）高次幂运算。算法１中在计算高次幂中利用平 方乘算法计算，而在算法２中的处理是首先利用较小 的海明权重表示法表示幂指数，减少了幂运算中的乘 的预处理过程，降低算法的运算量。 法次数，然后再利用多精度平方乘算法进行相应的高 次幂计算，该算法比平方乘算法计算效率更高，在高次 幂运算步骤中可以更快地计算得到相应的结果。 ７结束语 文中针对小步大步算法与改进的算法进行了性能 上的分析，上述表明算法的改进是正确可行的。随着． ４）表元素的查找次数。算法１中的Ｓｔｅｐ２和算法 ２中的Ｓｔｅｐ３．１的计算量是一样的，而算法１在比较过 程中需要进行查表比较，最大计算量在Ｄ（ｎ），平均计 算量是０（ｎ／２）；而算法２利用预处理过程中得到的 范围，只需直接查找，最大计算量为Ｄ（ｎ／４），平均下 来计算量仅有０（ｎ／８）。在算法运算次数上有倍数的 降低。 ５）链表的处理。算法１在对链表处理时使用哈希 函数来得到无碰撞的值，而在算法２中利用生成元的 性质可知在小于群的阶范围内，ａ‘是无碰撞的，所以 算法２不需要使用哈希函数。也就在查表过程中可以 提高效率，这在性能上也是一个提升。 表１为原算法与改进算法对比。 表１原算法与改进算法对比 ６进一步的应用 通过求解某一群中的离散对数问题，利用在求解 过程中所得到的中间数据，可以加以分析和利用，对同 群下其他生成元的离散对数的求解问题进行分析。根 据算法２的中心思想，发现算法２中预处理过程中是 利用群的阶作为输入参数，和生成元的选取无关，利用 这个特征，可以利用算法２中预处理过程中的数据对 离散对数问题的求解简化处理。 考虑在同一群下其他生成元的离散对数的问题， 可以重复利用算法２中预处理过程中得到的（ ， 对 奇偶链表，针对同一群下的其他生成元，群的阶是不变 的，则根据算法２可知其他生成元所对应的（ｉ， ）对 硬件条件的日益强大，牺牲适当的存储空间来降低计 算的复杂度，提高算法的效率也是一种可行的方案。 加大代码的重用率、有效利用中间过程产生的数据来 简化计算过程也是在Ｅｔ后密码系统的实现过程中需要 考虑和探讨的问题。 参考文献： ［１］ Ｊｏｈａｎｎｅｓ Ｂ，Ｄａｍｉａｎ Ｗ．Ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ：ｒｅｃｅｎｔ ｐｒｏｇｒｅｓｓ ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｄｉｎｇ Ｔｈｅｏｒｙ，Ｃｒｙｐｔｏｇｒａ— ｐｈｙ ａｎｄ Ｒｅｌａｔｅｄ Ａｒｅａｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０００：４２— ５６． ［２］Ｄｏｕｇｌａｓ Ｒ Ｓ．Ｃｒｙｐｔｏｇｒａｐｈｙ ｔｈｅｏｙｒ ａｎｄ ｐｒａｃｔｉｃｅ［Ｍ］．２ｎｄ ｅｄ． 冯登国，译．北京：电子工业出版社，２００３：１９３—２２７． ［３］Ｍａｏ Ｗｅｎｂｏ．现代密码学理论与实践［Ｍ］．王继林，译．北 京：电子工业出版社，２００４． ［４］ 周玉洁，冯登国．公开密钥密码算法及其快速实现［Ｍ］．北 京：国防工业出版社，２００２． ［５］王晚，杜伟章．基于离散对数问题的多级代理盲签名方 案［Ｊ］．计算机应用，２０１１，３１（７）：１９０４—１９０５． ［６］ 欧海文，叶顶峰，杨君辉，等．关于同时基于因子分解与离 散对数问题的签名［Ｊ］．通信学报，２００４，２５（１０）：１４３ —１４７． ［７］ 李发根，辛向军，胡予濮．基于离散对数和因子分解签名方 案的改进［Ｊ］．中国铁道科学，２００６，２７（５）：１３２—１３５． ［８］ 张海波，王小非，夏学知，等．一个改进的离散对数问题攻 击算法［ｊ］．计算机应用，２００７，７２（４）：８４３—８４５． ［９］ 胡进，何德彪，陈建华，等．基于椭圆曲线同源的公钥密 码［Ｊ］．北京工业大学学报，２０１１，３７（６）：９１６—９２０． ［１０］阎军智，李凤华，马建峰．基于Ｄｉｉｆｅ—Ｈｅｌｌｍａｎ算法的分层 密钥分配方案［Ｊ］．电子学报，２０１１，３９（１）：１１９－１２３． ［１１］Ｍｕｉｒ Ｊ Ａ，Ｓｔｉｎｓｏｎ Ｄ Ｒ．Ｏｎ ｔｈｅ ｌｏｗ ｈａｍｍｉｎｇ ｗｅｉｇｈｔ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｐｒｏｂｌｅｍ ｆｏｒ ｎｏｎａｄｊａｅｅｎｔ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ［Ｊ］． ＡＥＣＣ，２００６，１６（６）：４６１—４７２． ［１２］Ｍｅｎｅｚｅｓ Ａ Ｊ，ｖａｎ Ｏｏｒｓｃｈｏｔ Ｐ Ｃ，Ｖａｎｓｔｏｎｅ Ｓ Ａ．Ｈａｎｄｂｏｏｋ ｏｆ ａｐｐｌｉｅｄ ｃｙｒｐｔｏｇｒａｐｈｙ［Ｍ］．胡磊，王鹏，译．北京：电子 工业出版社，２０ｏ５．
