素域上椭圆曲线密码的高效实现.pdfVIP

维普资讯 第 5O卷 第 3期 武汉大学学报 (理学版) Vo1．5O No．3 2004年 6月 J．WuhanUniv．(Nat．Sci．Ed．) June2004，335～338 文章编号 ：1671—8836(2004)03—0335—04 素域上椭圆曲线密码的高效实现 汪朝晖 ，陈建华 ，涂 航 ，李 莉 (1．武汉大学 数 学与统计学院，湖北 武汉 430072； 2．武汉大学 计算机学院，湖北 武汉 430072) 摘 要：给出了几个素域上的算术运算和素域上椭圆曲线算术运算的高效实现算法，从而解决了椭圆曲线密 码 (ECC)实现中影响效率的几个关键算法设计 问题，且就 ECC加密机制和签名机制的选择提出了建议 ，最终形成 一 套高效的素域上 ECC加密算法和签名算法 的实现方案．该方案适应多种软件和硬件实现条件 ，具有较好 的通用 性 ． 关 键 词 ：椭 圆曲线密码 ；加密 ；签名 中图分类号 ：TN918 文献标识码 ：A 良好 的通用性和灵活性 ，适用于多种软／硬件环境下 1 椭 圆曲线密码 的 ECC实现． 椭 圆 曲线 密码 (ECC)自 1985年 由 Neal 2 素域上算术运算的实现 Koblitz_l和 VictorMiller_2提 出以来，由于它 比 RSA更具优势 (更强的安全性 、更高的实现效率 、更 实现 ECC之前，首先要确定 曲线的基域 ，目前 省的实现代价)，因此吸引了大批密码学工作者就其 在国际上主要有两种选择 ：素数域 (记为 F)或二元 安全性和实现方法作 了大量 的研究，并已逐渐被国 扩域 (记为 )，本文讨论 F 上 ECC的实现方案 ， 际各大标准组织采纳作为公钥密码标准 (IEEE 该方案对 上的ECC实现同样有参考价值． P1363、ANSIX9、ISO／IEC、和 IETF等)． 实现 F 上 的 ECC，需要用到 F 上 的加法、减 实现 ECC算法 ，要就基域的选取、基域上算术 运算的实现方法、椭 圆曲线上算术运算 的实现方法 法、乘法 (包括平方)、求逆和取模这几种算术运算 ， 和密码机制的确定共 4个层次作出综合选择．这需 根据分析和测试作者发现 ：模加 (加后取模)和模减 要综合考虑各种因素，包括安全性要求、实现 的性能 (减后取模)的运算速度是模乘运算(乘后取模)的 要求和实现平 台的资源条件 (如 ：处理速度 、软件或 10倍 以上；求逆运算时间与约 70个模乘相当；ECC 固件环境 中的程序空 间和数据空 间的大小 、硬件 电 运算 70 左右的时间消耗在模乘运算上．考虑到上 路的逻辑 门数和功耗等)．过去十几年来 ，就 ECC的 述 因素 ，同时也因为 F 上的模加 、模减 、乘法 、平方 实现出现了许多学术文章，但大部分这样 的文章或 和求逆都 已有成熟的快速算法 ，在制定 ECC实现方 者只论述 ECC实现 中的某一个层次的算法 (如基域 案时，只需考虑使运算尽量少涉及 F 上 的求逆 ，同 上的算术运算或椭 圆曲线上 的算术运算)或者并没 时要设计高效的对乘