2024年8月25日发(作者：示木)
维普资讯
２００７年ｌＯ月 电 脑 学 习 第５期
高效安全的椭圆曲线密码体制
白永祥
摘 要：介绍了椭圆曲线的基本知识和椭圆曲线密码体制。分析了其安全性。
关键词：椭圆曲线密码体制 安全性 攻击 加密 解密
中图分类号：ＴＰ３０９．７ 文献标识码： Ａ 文章编号：１００２—２４２２（２００７）０５—００５３—０２
Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ ａｎｄ Ｉｔｓ Ｓｅｃｕｒｉｔｙ
Ｂａｉ Ｙｏｎｇｘｉａｎｇ
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｋｎｏｗｌｅｄｇｅ ｏｆ ｔｈｅ ｅｌｌｉｐｔｉｃ ｃｕｌ－ｖｅ、ｅＵｉｐｆｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｓｙｓｔｅｍ，ａｎｄ ａｎａｌｙｚｅｓ ｉｔｓ ｓｅｃｕｒｉｔｙ．
Ｋｅｙｗｏｒｄ：Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ Ｓｅｃｕｒｉｔｙ Ａｔｔａｃｋ Ｅｎｃｒｙｐｔ Ｄｅｃｒｙｐｔ
１椭圆曲线密码体制理论
ｚ
上的素曲线和在ＧＦ（２ｍ）上构造的二元曲线。对于ｚ上的
１．１椭圆曲线定义
素曲线，其变量和系数在集合（０，１，…，ｐ－１）中取值，运算
一
般椭圆曲线的方程为：ｙ。＋ａ）【ｙ＋Ｉ）ｙ＝ｘ’＋ｃｘ：＋ｄｘ＋ｅ，也称
为模Ｐ运算。对于在ＧＦ（２ ）上的二元曲线，变量和系数在
为Ｗｅｉｅｒｓｔｒａｓｓ方程，其中ａ，ｂ，Ｃ，ｄ和ｅ可以是实数，ｘ和Ｙ在
２ｍ内取值，而 圣算为ＧＦ（２ｍ）里的运算。这两种加法运算
实数集上取值，再加上一个特定点Ｏ（无穷远点）称为Ｒ上
规则与上面在实数上的运算很相似，只是后者为有限域上
的椭圆曲线。人们同样也可以定义有理数，复数，有限域上
的离散值。
的椭圆曲线，一般形式如：Ｅ（ｋ）＝（（ｘ，Ｙ）∈ｋ２：ｙ ＋ａｘｙ＋ｂｙ＝
１．２椭圆曲线密码体系加密算法原理
ｘ，＋ｃｘ：＋ｃｌｘ＋ｅ）Ｕ ｆＯ。从几何的角度利用弦切法可以在Ｅ ｏ】
（１）密钥对生成：输入：参数组（Ｐ，Ｅ，Ｐ，ｎ）；输出：公
（Ｒ）上定义一个代数群系统。对于椭圆曲线上的点Ｐ、Ｑ，做
钥Ｑ和私钥ｄ；选择ｄ∈Ｒ［１，ｎ一１］；计算Ｑ＝ｄＰ：返回
直线（Ｐ＝０，则为过点Ｐ的切线）和椭圆曲线交第三个点一
（Ｑ．ｄ）。
Ｒ，Ｒ为一Ｒ关于Ｘ轴的对称点。可以写成Ｐ＋Ｑ＝Ｒ，将方程
（２）加密算法：输入参数组（Ｐ，Ｅ，Ｐ，ｎ），公钥Ｑ，明文
限制为下述形式就足够：ｙ２＝ｘ３＋ａｘ＋ｂ，这时椭圆曲线如下图
ｍ；将明文ｎｌ表示为Ｅ（Ｆｐ）上的点Ｍ；选择ｋ∈Ｒ［１，ｎ一１】：
１、图２、图３：
计算Ｃ１＝ｋＰ；计算Ｃ２＝Ｍ＋ｋＱ。
（３）解密算法：输入：椭圆曲线参数纽（Ｐ，Ｅ，Ｐ，ｎ），私
Ｊ
＿ ｌ
？Ｉ Ｉ
钥ｄ，密文（Ｃ１，Ｃ２）；计算Ｍ＝Ｃ２～ｄＣ１，并从点取出明文Ｍ。
厂、 ’
２椭圆曲线密码体制的安全性分析
＿ ｌ
Ｉ ｆ ｒ
ｆ
椭圆曲线密码体制是建立在椭圆曲线离散对数问题难
八
解性之上的，它的安全性依赖于对椭圆离散对数问题
＿＿
、
（ＥＣＤＬＰ）的攻击。对ＥＣＤＬＰ的攻击目前有两种途径：
、
，＋＃冉＝０
２．１适用于所有椭圆曲线的一般攻击方法
，’尊ｔ＾
｛
图１
图２ 图３
（１）穷举搜索法。设椭圆曲线的基点为Ｇ．Ｇ的阶为ｎ，
则ＥＣＤＬＰ为已知Ｐ和Ｇ，通过Ｐ＝ｋＧ求ｋ。简单计算Ｇ的倍
从这个定义出发，可以定义椭圆曲线上的点加运算：图
乘：Ｇ，２Ｇ…，直到找到Ｐ，这种算法最坏需要ｎ步椭圆曲线
１：Ｐ≠±０，Ｐ＋Ｑ＝Ｒ，Ｒ是过点Ｐ，Ｑ的直线与曲线Ｅ（Ｋ）的另
点加。
一
交点一Ｒ关于ｘ轴的对称点；图２：Ｐ＝Ｑ，Ｐ＋Ｑ＝Ｐ＋Ｐ＝２Ｐ＝Ｒ，
（２）Ｓｈａｎｋｓ的小步大步算法：
Ｒ是过Ｐ点作Ｅ（Ｒ）的切线与Ｅ（Ｒ）的交点关于一Ｒ的对
具体方法为：首先预计并存储Ｇ的某些倍数（小步）然
称点；图３：定义与Ｙ轴平行的直线与Ｅ（Ｒ）交于Ｐ，Ｑ以
后对于某个整数ｂ，计算Ｐ—ｂＧ，Ｐ一２ｂＧ，…（大步），直到Ｐ—
及无穷远点Ｏ，Ｏ作为单位元，于是有Ｐ＋（一Ｐ）：Ｐ—Ｐ＝Ｏ。
ｉｂＧ在预存储的表中出现，这里可以利用二分查找法，因此
椭圆曲线密码体制使用的是变元和系数均为有限域中
其速度优于穷举搜索。
元素的椭圆曲线。密码应用中使用两类椭圆曲线是定义在
自永祥渭南职业技术学院计算机系讲师（陕西渭南７ｌ４０ｏＯ），研究方向：网络与信息安全 修改稿收到日期：２００７－０４—０２
・
５３ ・
维普资讯
２００７年ｌ０月 电 脑 学 习 第５期
用ＶＢ模拟实现Ｗｅｂ页码聚类推荐算法
宋秀芹’ 孙新燕 赵丽敏
摘 要：介绍了利用ＶＢ模拟实现在线页面聚类推荐算法的方法。并给出相应的源代码程序。
关键词：ＶＢ
中图分类号
算法 用户聚类
文献标识码Ｂ 文章编号：１００２—２４２２（２ｏｏ７）０５—００５４加３ ＴＰ３９３
Ｕｓｉｎｇ ＶＢ ｔｏ Ｓｉｍｕｌａｔｅ Ｃｌｕｓｔｅｒｉｎｇ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｏｎ Ｗｅｂ Ｐａｇｅ
Ｓｏｎｇ Ｘｉｕｑｉｎ Ｓｕｎ Ｘｉｎｙａｎ Ｚｈａｏ Ｌｉｍｉｎ
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｅｘｐｏｕｎｄｓ ｔｈｅ ｍｅｔｈｏｄ ｔｏ ｓｉｍｕｌａｔｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｎ Ｗｅｂ ｐａｐｅ，ａｎｄ ｐｒｅｓｅｎｔｓ ｔｈｅ
ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｓｏｕｒｃｅ ｐｒｏｇｒａｍ．
Ｋｅｙｗｏｒｄ：ＶＢ Ａｌｇｏｒｉｔｈｍ Ｕｓｅｒ Ｃｌｕｓｔｅｒｉｎｇ
电子商务因其成本低廉、快捷，不
受时空限制等优点在全球范围内迅速
算出符合他的需求的页面集合，正是
类结果向其推荐页面集。具体过程如
下：
推荐引擎应完成的任务。
ｌ Ｗｅｂ页面聚类推荐算法介绍
聚类算法是基于一定的距离尺度
将相互距离很近的用户进行聚类，聚
得到普及和发展。用户对网络 提供
的众多商品信息并非完全感兴趣，通
常要通过多次浏览才能找到需求的商
品；另一方面商家也不能全面了解用
户的个人需求，提供给用户的是干篇
一
１．１构建Ｕｓｅｒ—ＵＲＬ矩阵并计算用户
相似度
页面推荐需要用户提供评价来确
定用户的兴趣，在Ｗｅｂ服务器的环境
下，用户兴趣度的评价可以通过Ｗｅｂ
类后的用户被视为若干个不同的类，
在同一个类中的门ｊ户具有很高的相似
性，当一个新用户访问页面时根据聚
律的界面，无法维护稳定的客户关
访问挖掘自动获得。有两个指标可以
用来衡量用户的访问兴趣度：一个是 系。推荐引擎如何为当前ｆ｝】户寻找计
（３）ＰｏＨａｒｄ ｓ ｒｈｏ算法。这种算法是小步一大步算法的 数的Ｆ２Ⅱ．域来避免此类攻击。
（３）乘积算法攻击：这是一种对同一个椭圆曲线密码
系统的攻击，在一个确定的椭圆曲线密码系统下，如果被并
行Ｐｏｌｌａｒｄ＇ｓ ｒｈｏ算法解决了，那么这个ＥＣＤＬＰ所作的工作
能被用来加速其它的ＥＣＤＬＰ的解决。
还有其它几种针对特殊曲线的攻击，总之，从目前来看
对ＥＣＤＬＰ最好的攻击算法是并行Ｐｏｌｌａｒｄ＇ｓ ｒｈｏ，其运行时
间为（、／ 而／２ｒ）步点加运算。有学者指出，如果ｎ＝１０￣－
随机版本，它的运行时间与小步一大步算法差不多，只是需
要很小的存储空间。还有一种是并行ＰｏＨａｒｄ＇ｓ ｒｈｏ算法，算
法需在几个处理器上并行，是日前对ＥＣＤＬＰ最好的攻击方
法。
（４）Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法。Ｐｏｈｌｉｇ和Ｈｅｌｌｍａｎ提出了一
个求解ＤＬＰ的方法，该方法可以用来试图解决ＥＣＤＬＰ。首
先将Ｎ分解为Ｎ－－Ｉ１ｐｅ． （其 ｛。Ｐ。均为素数， ０，１，…，ｔ—
ｉ：０
２ ，花费１０００万美元建立的具有３２５０００处理并行Ｐｏｌ—
ｌａｒｄ Ｓ ｒｈｏ算法来解决某个ＥＣＤＬＰ需要３２天左右，可见代
价是十分昂贵的，而在实际应用中我们选择ｎ≥２ ．因此可
以说椭圆密码体制是十分安全的。
１），给定Ｎ，该算法将ＥＣＤＬＰ分解成ｅ０＋ｅｌ＋…＋ｅ『．１￣ｌ＜ｏｇＮ个
子ＥＣＤＬＰ，如果Ｎ的素因予ｐｉ都很小（ｉ＝Ｏ，１，…，ｔ一１），则
这些子ＥＣＤＩ２都能很容易求解。因此我们要求给ＥＣＣ所
选椭圆曲线的阶Ｎ有大的素因予，最好Ｎ就是素数，这样
就可以保证用该方法求ＥＣＤＬＰ时，其时间复杂度是指数级
的。
２．２对特殊椭圆曲线的攻击方法
（１）ＭＯＶ攻击；此类攻击只对超奇异椭圆曲线有效，
参考文献
［１］Ｗｉｌｉａｍ Ｓｔａｌｌｉｎｇｓ著．密码编码学与网络安全［Ｍ］第四版．
孟庆树，等译．北京；电子工业出版式社，２００６：２１６－２２５．
［２］Ｄａｒｒｅｌ Ｈａｎｋｅｒｓｏｎ．椭圆曲线密码学导论［ＭＩ．张焕国，等
译．北京：电子工业出版社，２００５：１２—１３．
该转化导致了亚指数的ＥＣＤＬＰ求解算法。
（２）Ｗｅｆｔ ｄｅｓｃｅｎｔ攻＿击：这种方法只适合特征为２的复
合域，在椭圆曲线密码的实际应用中，我们可选择ｍ为素
【３】祝跃飞，张亚娟著．椭圆曲线公钥密码导引【Ｍ】＿北京：
科学出版社，２０ｏ６：ｌ１ｌ—ｌ１６．
修改稿收到日期：２００７－０５－０８ 宋秀芹Ｌ“东德州学院汁算机系副敦授（２５３０２３），研究方向：计算机基础教育与数据库技术
・５４・
2024年8月25日发(作者：示木)
维普资讯
２００７年ｌＯ月 电 脑 学 习 第５期
高效安全的椭圆曲线密码体制
白永祥
摘 要：介绍了椭圆曲线的基本知识和椭圆曲线密码体制。分析了其安全性。
关键词：椭圆曲线密码体制 安全性 攻击 加密 解密
中图分类号：ＴＰ３０９．７ 文献标识码： Ａ 文章编号：１００２—２４２２（２００７）０５—００５３—０２
Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ ａｎｄ Ｉｔｓ Ｓｅｃｕｒｉｔｙ
Ｂａｉ Ｙｏｎｇｘｉａｎｇ
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｋｎｏｗｌｅｄｇｅ ｏｆ ｔｈｅ ｅｌｌｉｐｔｉｃ ｃｕｌ－ｖｅ、ｅＵｉｐｆｉｃ ｃｕｒｖｅ ｃｒｙｐｔｏｓｙｓｔｅｍ，ａｎｄ ａｎａｌｙｚｅｓ ｉｔｓ ｓｅｃｕｒｉｔｙ．
Ｋｅｙｗｏｒｄ：Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ Ｓｅｃｕｒｉｔｙ Ａｔｔａｃｋ Ｅｎｃｒｙｐｔ Ｄｅｃｒｙｐｔ
１椭圆曲线密码体制理论
ｚ
上的素曲线和在ＧＦ（２ｍ）上构造的二元曲线。对于ｚ上的
１．１椭圆曲线定义
素曲线，其变量和系数在集合（０，１，…，ｐ－１）中取值，运算
一
般椭圆曲线的方程为：ｙ。＋ａ）【ｙ＋Ｉ）ｙ＝ｘ’＋ｃｘ：＋ｄｘ＋ｅ，也称
为模Ｐ运算。对于在ＧＦ（２ ）上的二元曲线，变量和系数在
为Ｗｅｉｅｒｓｔｒａｓｓ方程，其中ａ，ｂ，Ｃ，ｄ和ｅ可以是实数，ｘ和Ｙ在
２ｍ内取值，而 圣算为ＧＦ（２ｍ）里的运算。这两种加法运算
实数集上取值，再加上一个特定点Ｏ（无穷远点）称为Ｒ上
规则与上面在实数上的运算很相似，只是后者为有限域上
的椭圆曲线。人们同样也可以定义有理数，复数，有限域上
的离散值。
的椭圆曲线，一般形式如：Ｅ（ｋ）＝（（ｘ，Ｙ）∈ｋ２：ｙ ＋ａｘｙ＋ｂｙ＝
１．２椭圆曲线密码体系加密算法原理
ｘ，＋ｃｘ：＋ｃｌｘ＋ｅ）Ｕ ｆＯ。从几何的角度利用弦切法可以在Ｅ ｏ】
（１）密钥对生成：输入：参数组（Ｐ，Ｅ，Ｐ，ｎ）；输出：公
（Ｒ）上定义一个代数群系统。对于椭圆曲线上的点Ｐ、Ｑ，做
钥Ｑ和私钥ｄ；选择ｄ∈Ｒ［１，ｎ一１］；计算Ｑ＝ｄＰ：返回
直线（Ｐ＝０，则为过点Ｐ的切线）和椭圆曲线交第三个点一
（Ｑ．ｄ）。
Ｒ，Ｒ为一Ｒ关于Ｘ轴的对称点。可以写成Ｐ＋Ｑ＝Ｒ，将方程
（２）加密算法：输入参数组（Ｐ，Ｅ，Ｐ，ｎ），公钥Ｑ，明文
限制为下述形式就足够：ｙ２＝ｘ３＋ａｘ＋ｂ，这时椭圆曲线如下图
ｍ；将明文ｎｌ表示为Ｅ（Ｆｐ）上的点Ｍ；选择ｋ∈Ｒ［１，ｎ一１】：
１、图２、图３：
计算Ｃ１＝ｋＰ；计算Ｃ２＝Ｍ＋ｋＱ。
（３）解密算法：输入：椭圆曲线参数纽（Ｐ，Ｅ，Ｐ，ｎ），私
Ｊ
＿ ｌ
？Ｉ Ｉ
钥ｄ，密文（Ｃ１，Ｃ２）；计算Ｍ＝Ｃ２～ｄＣ１，并从点取出明文Ｍ。
厂、 ’
２椭圆曲线密码体制的安全性分析
＿ ｌ
Ｉ ｆ ｒ
ｆ
椭圆曲线密码体制是建立在椭圆曲线离散对数问题难
八
解性之上的，它的安全性依赖于对椭圆离散对数问题
＿＿
、
（ＥＣＤＬＰ）的攻击。对ＥＣＤＬＰ的攻击目前有两种途径：
、
，＋＃冉＝０
２．１适用于所有椭圆曲线的一般攻击方法
，’尊ｔ＾
｛
图１
图２ 图３
（１）穷举搜索法。设椭圆曲线的基点为Ｇ．Ｇ的阶为ｎ，
则ＥＣＤＬＰ为已知Ｐ和Ｇ，通过Ｐ＝ｋＧ求ｋ。简单计算Ｇ的倍
从这个定义出发，可以定义椭圆曲线上的点加运算：图
乘：Ｇ，２Ｇ…，直到找到Ｐ，这种算法最坏需要ｎ步椭圆曲线
１：Ｐ≠±０，Ｐ＋Ｑ＝Ｒ，Ｒ是过点Ｐ，Ｑ的直线与曲线Ｅ（Ｋ）的另
点加。
一
交点一Ｒ关于ｘ轴的对称点；图２：Ｐ＝Ｑ，Ｐ＋Ｑ＝Ｐ＋Ｐ＝２Ｐ＝Ｒ，
（２）Ｓｈａｎｋｓ的小步大步算法：
Ｒ是过Ｐ点作Ｅ（Ｒ）的切线与Ｅ（Ｒ）的交点关于一Ｒ的对
具体方法为：首先预计并存储Ｇ的某些倍数（小步）然
称点；图３：定义与Ｙ轴平行的直线与Ｅ（Ｒ）交于Ｐ，Ｑ以
后对于某个整数ｂ，计算Ｐ—ｂＧ，Ｐ一２ｂＧ，…（大步），直到Ｐ—
及无穷远点Ｏ，Ｏ作为单位元，于是有Ｐ＋（一Ｐ）：Ｐ—Ｐ＝Ｏ。
ｉｂＧ在预存储的表中出现，这里可以利用二分查找法，因此
椭圆曲线密码体制使用的是变元和系数均为有限域中
其速度优于穷举搜索。
元素的椭圆曲线。密码应用中使用两类椭圆曲线是定义在
自永祥渭南职业技术学院计算机系讲师（陕西渭南７ｌ４０ｏＯ），研究方向：网络与信息安全 修改稿收到日期：２００７－０４—０２
・
５３ ・
维普资讯
２００７年ｌ０月 电 脑 学 习 第５期
用ＶＢ模拟实现Ｗｅｂ页码聚类推荐算法
宋秀芹’ 孙新燕 赵丽敏
摘 要：介绍了利用ＶＢ模拟实现在线页面聚类推荐算法的方法。并给出相应的源代码程序。
关键词：ＶＢ
中图分类号
算法 用户聚类
文献标识码Ｂ 文章编号：１００２—２４２２（２ｏｏ７）０５—００５４加３ ＴＰ３９３
Ｕｓｉｎｇ ＶＢ ｔｏ Ｓｉｍｕｌａｔｅ Ｃｌｕｓｔｅｒｉｎｇ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｏｎ Ｗｅｂ Ｐａｇｅ
Ｓｏｎｇ Ｘｉｕｑｉｎ Ｓｕｎ Ｘｉｎｙａｎ Ｚｈａｏ Ｌｉｍｉｎ
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｅｘｐｏｕｎｄｓ ｔｈｅ ｍｅｔｈｏｄ ｔｏ ｓｉｍｕｌａｔｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｎ Ｗｅｂ ｐａｐｅ，ａｎｄ ｐｒｅｓｅｎｔｓ ｔｈｅ
ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｓｏｕｒｃｅ ｐｒｏｇｒａｍ．
Ｋｅｙｗｏｒｄ：ＶＢ Ａｌｇｏｒｉｔｈｍ Ｕｓｅｒ Ｃｌｕｓｔｅｒｉｎｇ
电子商务因其成本低廉、快捷，不
受时空限制等优点在全球范围内迅速
算出符合他的需求的页面集合，正是
类结果向其推荐页面集。具体过程如
下：
推荐引擎应完成的任务。
ｌ Ｗｅｂ页面聚类推荐算法介绍
聚类算法是基于一定的距离尺度
将相互距离很近的用户进行聚类，聚
得到普及和发展。用户对网络 提供
的众多商品信息并非完全感兴趣，通
常要通过多次浏览才能找到需求的商
品；另一方面商家也不能全面了解用
户的个人需求，提供给用户的是干篇
一
１．１构建Ｕｓｅｒ—ＵＲＬ矩阵并计算用户
相似度
页面推荐需要用户提供评价来确
定用户的兴趣，在Ｗｅｂ服务器的环境
下，用户兴趣度的评价可以通过Ｗｅｂ
类后的用户被视为若干个不同的类，
在同一个类中的门ｊ户具有很高的相似
性，当一个新用户访问页面时根据聚
律的界面，无法维护稳定的客户关
访问挖掘自动获得。有两个指标可以
用来衡量用户的访问兴趣度：一个是 系。推荐引擎如何为当前ｆ｝】户寻找计
（３）ＰｏＨａｒｄ ｓ ｒｈｏ算法。这种算法是小步一大步算法的 数的Ｆ２Ⅱ．域来避免此类攻击。
（３）乘积算法攻击：这是一种对同一个椭圆曲线密码
系统的攻击，在一个确定的椭圆曲线密码系统下，如果被并
行Ｐｏｌｌａｒｄ＇ｓ ｒｈｏ算法解决了，那么这个ＥＣＤＬＰ所作的工作
能被用来加速其它的ＥＣＤＬＰ的解决。
还有其它几种针对特殊曲线的攻击，总之，从目前来看
对ＥＣＤＬＰ最好的攻击算法是并行Ｐｏｌｌａｒｄ＇ｓ ｒｈｏ，其运行时
间为（、／ 而／２ｒ）步点加运算。有学者指出，如果ｎ＝１０￣－
随机版本，它的运行时间与小步一大步算法差不多，只是需
要很小的存储空间。还有一种是并行ＰｏＨａｒｄ＇ｓ ｒｈｏ算法，算
法需在几个处理器上并行，是日前对ＥＣＤＬＰ最好的攻击方
法。
（４）Ｐｏｈｌｉｇ—Ｈｅｌｌｍａｎ算法。Ｐｏｈｌｉｇ和Ｈｅｌｌｍａｎ提出了一
个求解ＤＬＰ的方法，该方法可以用来试图解决ＥＣＤＬＰ。首
先将Ｎ分解为Ｎ－－Ｉ１ｐｅ． （其 ｛。Ｐ。均为素数， ０，１，…，ｔ—
ｉ：０
２ ，花费１０００万美元建立的具有３２５０００处理并行Ｐｏｌ—
ｌａｒｄ Ｓ ｒｈｏ算法来解决某个ＥＣＤＬＰ需要３２天左右，可见代
价是十分昂贵的，而在实际应用中我们选择ｎ≥２ ．因此可
以说椭圆密码体制是十分安全的。
１），给定Ｎ，该算法将ＥＣＤＬＰ分解成ｅ０＋ｅｌ＋…＋ｅ『．１￣ｌ＜ｏｇＮ个
子ＥＣＤＬＰ，如果Ｎ的素因予ｐｉ都很小（ｉ＝Ｏ，１，…，ｔ一１），则
这些子ＥＣＤＩ２都能很容易求解。因此我们要求给ＥＣＣ所
选椭圆曲线的阶Ｎ有大的素因予，最好Ｎ就是素数，这样
就可以保证用该方法求ＥＣＤＬＰ时，其时间复杂度是指数级
的。
２．２对特殊椭圆曲线的攻击方法
（１）ＭＯＶ攻击；此类攻击只对超奇异椭圆曲线有效，
参考文献
［１］Ｗｉｌｉａｍ Ｓｔａｌｌｉｎｇｓ著．密码编码学与网络安全［Ｍ］第四版．
孟庆树，等译．北京；电子工业出版式社，２００６：２１６－２２５．
［２］Ｄａｒｒｅｌ Ｈａｎｋｅｒｓｏｎ．椭圆曲线密码学导论［ＭＩ．张焕国，等
译．北京：电子工业出版社，２００５：１２—１３．
该转化导致了亚指数的ＥＣＤＬＰ求解算法。
（２）Ｗｅｆｔ ｄｅｓｃｅｎｔ攻＿击：这种方法只适合特征为２的复
合域，在椭圆曲线密码的实际应用中，我们可选择ｍ为素
【３】祝跃飞，张亚娟著．椭圆曲线公钥密码导引【Ｍ】＿北京：
科学出版社，２０ｏ６：ｌ１ｌ—ｌ１６．
修改稿收到日期：２００７－０５－０８ 宋秀芹Ｌ“东德州学院汁算机系副敦授（２５３０２３），研究方向：计算机基础教育与数据库技术
・５４・