椭圆曲线密码学导论

    书籍
    数学书籍
自1984年Hendrik Lenstra给出基于椭圆曲线的整数因子分解算法后，椭圆曲线在密码学和计算机数论中的应用已得到了很大的发展。椭圆曲线密码属于公钥密码体制，它可以提供与RSA密码体制同样的功能，其安全性建立在椭圆曲线离散对数问题的困难性之上。本书主要是为安全专业人员、技术开发人员和致力于椭圆曲线密码应用的人员提供的，介绍了有限域算法，椭圆曲线算术，针对椭圆曲线离散对数问题的攻击，椭圆曲线参数组和密钥对的生成与确认，数字签名、公钥加密和密钥协商的椭圆曲线协议选择，椭圆曲线密码的软件和硬件实现，旁门攻击技术及其预防对策，等等。此外，本书还为读者提供了大量的算法与参考文献。
本书自成体系，适用于计算机科学、计算机工程、网络设计和网络数据安全领域的工程技术人员、专家以及研究人员，也可供大专院校高年级本科生和研究生作为教材使用。

Darrel Hankerson Aubum大学数学教授，产业顾问；同时是几本关于密码学与数据压缩的图书的合著者。
Alfred Menezes滑铁卢大学数学教授，产业顾问；同时也是几本关于密码学的图书的合著者。
Scott Vanstone滑铁卢大学NSERC／Pitney Bowes产业研究会主席；同时与A．Menezes和P．van Oorschot一道撰写了Applied Cryptography Handbook(《应用密码学手册》，已由电子工业出版社于2005年6月出版)一书，并且是知名Certicom公司的奠基人。
张焕国：武汉大学计算机科学与技术学院教授、博士生导师。主要从事信息安全、容错计算和计算机应用方面的教学与科研工作。现任中国密码学会理事，中国计算机学会客错专业委员会委员，湖北省电子学会副理事长，湖北省暨武汉市计算机学会理事。

第1章 概论
1.1 密码学基础
1.2 公钥密码
1.3 为什么需要椭圆曲线密码
1.4 导读
1.5 注释和进一步参考
第2章 有限域算术
2.1 有限域介绍
2.2 素域算术
2.3 二进制域算术
2.4 最佳扩域算术
2.5 注释和进一步参考
第3章 椭圆曲线算术
3.1 椭圆曲线的概念
3.2 点的表示与群的运算法则
3.3 点乘
3.4 Koblitz曲线
3.5 具有有效可计算自同态的曲线
3.6 用折半进行点乘
3.7 点乘的开销

　　随着计算机和网络技术的高速发展和广泛应用，社会的信息化程度越来越高，但社会对计算机和网络系统的依赖性也越来越大。若计算机和网络系统的安全受到危害，则会危及国家的安全，引起社会的混乱，从而造成重大损失。因此，确保计算机和网络系统的安全已成为世人关注的社会问题，并成为计算机科学技术的热点领域。
　　众所周知，确保信息系统的安全是一个系统工程，必须从整体考虑，从底层着手，综合采取措施，才能比较有效地确保信息系统的安全。硬件结构的安全和操作系统的安全是信息系统安全的基础，而密码等则是关键技术。
　　密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码。密码的发展经历了由简单到复杂、由古典到近代的发展历程，并且在它发展的各个阶段，都为确保信息安全发挥了重要作用。
　　1949年香农发表了题为《保密系统的通信理论》这一著名论文，该论文把密码置于坚实的数学基础之上，标志着密码学作为一门科学的形成。1976年W. Diffie和M．E．Hellman提出了公钥密码的概念，从此开创了一个密码新时代。公钥密码从根本上克服了传统密码在密钥分配上的困难，特别适合计算机网络应用，而且很容易实现数字签名，因而特别受到重视。目前，公钥密码已得到了广泛应用。
　　在国际上研究比较充分而且公认比较安全的公钥密码有，基于大整数因子分解困难性的RSA密码，基于离散对数问题困难性的ELGamal密码，以及基于椭圆曲线离散对数问题困难性的椭圆曲线密码等。
　　人们对椭圆曲线的研究已有100多年的历史，而椭圆曲线密码是Neal Koblitz和Victor Miller于1985年提出来的。目前，椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它可以提供同RSA密码体制同样的功能。然而它的安全性建立在椭圆曲线离散对数问题(ECDLP)的困难性之上。现在求解ECDLP的最好算法具有全指数时间复杂度，与此不同，整数因子分解问题却有亚指数时间算法。这意味着要达到期望的安全程度，椭圆曲线密码可以使用较RSA密码更短的密钥。普遍认为160位椭圆曲线密码可提供相当于1024位RSA密码的安全程度。由于密钥短，所以工程实现的加解密速度较快，并且可节省能源、带宽和存储空间。正因为如此，一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。由于椭圆曲线密码具有上述优点，因此椭圆曲线密码特别适于在航空、航天、卫星及智能卡等系统中应用。
　　加拿大滑铁卢大学的应用密码学研究中心(CACR)是国际著名的椭圆曲线密码研究中心之一。他们在椭圆曲线密码理论与技术方面的研究成果享誉世界。本书的三位作者都是著名的椭圆曲线密码专家。其中Darrel Hankerson是Auburn大学的研究人员，2000年至2004年夏季到滑铁卢大学的应用密码学研究中心(CACR)做访问学者。Alfred Menczes和Scott Vanstone都是滑铁卢大学的教授。
　　本书全面地介绍了椭圆曲线密码的理论、技术与应用，试图为信息安全专业技术人员和椭圆曲线密码应用人员提供一本椭圆曲线密码的基础书籍。本书的一个显著特点是关键技术都给出了算法，从而为工程实现奠定了基础。内容的叙述是面向各种读者的，以使各类读者都能得到他们所需的知识。而且在每章的末尾给出了广泛的论述，为读者提供了有用的参考。
　　本书的第1章概述了密码和椭圆曲线密码。第2章介绍了有限域。第3章介绍了椭圆曲线算术。第4章介绍了椭圆曲线密码的各种协议。第5章详细介绍了椭圆曲线密码的软件和硬件实现技术。本书内容丰富，既有理论基础，又有工程实现技术。关键技术算法化，便于实现应用。讲述深入浅出，便于理解。本书是一本难得的好书，既可用做研究生和高年级本科生的教材，也可供从事信息安全、计算机、通信、电子等领域的科技人员参考。
　　本书的前言、第1章、第2章和第3章由张焕国翻译，第4章、第5章、第6章和附录由王张宜翻译。孟庆树、王邦菊等帮助整理译稿。全书由张焕国统稿和审校。由于译者的专业知识和外语水平有限，书中错误在所难免，敬请读者指正，译者在此先致感谢之意。
　　译者于武汉珞珈山
　　2005．8
　　

　　代数、代数几何和数论学者对椭圆曲线的研究可追溯到19世纪中叶。现在已有大量描述椭圆曲线美好和优雅特性的论著。1984年，Hendrik Lenstra给出了一个独具创意的基于椭圆曲线的整数因子分解算法。这一成功推动了研究工作者去开拓椭圆曲线在密码学和计算数论中的其他应用。
　　公钥密码的概念是由W.Diffie和M．Hellman于1976年提出的。第一个实际的公钥密码是1977年R．Rivest，丸Shamir和L.Adleman提出的RSA公钥密码体制。RSA密码是现在最著名的公钥密码之一，它的安全性建立在整数因子分解的困难性之上。椭圆曲线密码(ECC)是1985年由N．Kobfitz和V.Miller提出的。椭圆曲线密码属于公钥密码体制，它可以提供同RSA密码体制同样的功能。然而它的安全性建立在椭圆曲线离散对数问题(ECDLP)的困难性之上。现在求解ECDLP最好的算法具有全指数时间复杂度，与此不同，整数因子分解问题却有亚指数时间算法。这意味着对于达到期望的安全程度，椭圆曲线密码可以使用较RSA密码更短的密钥。例如，普遍认为160位的椭圆曲线密码可提供相当于1024位RSA密码的安全程度。由于密钥短而获得的优点包括加解密速度快、节省能源、节省带宽和节省存储空间。
　　受众 本书试图为安全专业人员、技术开发人员和致力于椭圆曲线密码应用的人员提供一本基础书籍。内容的叙述是面向各种读者的，并且假设读者具有不高于大学程度的计算机科学、工程和数学的基础。本书不是写给理论专家的，它明显缺少数学证明。本书的覆盖面相当宽，并在每章的末尾给出了大量的文献，为读者提供了有用的参考。
　　总体介绍 本书第2章集中介绍有限域算术，第3章集中介绍椭圆曲线算术。第4章首先介绍针对ECDLP的各种攻击方法，然后介绍椭圆曲线参数组和密钥对的生成与确认，以及数字签名、公钥加密和密钥协商的椭圆曲线协议选择。本书没有介绍针对ECDLP的各种攻击的数学细节，也没有论述椭圆曲线点的计数算法，因为许多数学工作者对此已经非常熟悉(以简明易读的形式阐述这些内容本身就是一种极大的挑战)。第2章、第3章和第4章的内容选取主要考虑了ECC的标准，这些标准由公认的标准化机构所制定，如椭圆曲线数字签名算法(ECDSA)的标准PIPS l86-2就是由美国国家标准与技术研究所(NIST)制定的。第5章详细介绍了椭圆曲线密码的软件和硬件的有效实现技术，并且还介绍了"旁门攻击"技术及其预防对策。虽然第5章的内容是有限的，但是我们希望它能给软件开发人员和硬件设计人员提供一些有益的工程借鉴。
　　致谢 非常感谢曾给过我们有益的建议和帮助的人们。他们是Mike Brown，Eric Fung，John Goyo，Rick Hite，Rob Lambert，Laurie Law,James Muir,Arash Reyhani-Masoleh，Paul Schellenberg，Adrian Tang，Edlyn Teske和Christof Zalka。特别感谢Helen D'Souza，他为本书设计了精美的艺术插图。还要感谢Cindy Hankerson和Sherry Shannon-Vanstone；是他们建议在书的插图中采用自然曲线的图案。最后我们感谢Springer出版社的编辑Wayne Wheeler和Wayne Yuhasz，感谢他们所给予的不断鼓励和支持。
　　读者可以通过我们的网站获得本书的更新和勘误信息，以及我们的联系信息。我们的网址是http：／／www．cacr．math．uwaterloo．caJecc／。我们非常感激读者能够发现并告诉我们书中的错误和缺陷。
　　Darrel R．Hankerson，AlfredJ．Menezes，Scott A．Vanstone
　　Auburn & Waterloo
　　2003．6