基于Koblitz椭圆曲线的公钥密码体制实现技术研究

摘要

随着计算机技术、网络技术，特别是Intemet技术的飞速发展和广泛普及，人类社会正处于由工业经济向信息经济的深刻变革之中，信息化已经成为当今世界经济和社会发展的倍增器，成为了衡量综合国力的重要标志。目前，各种基于网络的应用系统层出不穷，如电子政务和电子商务等，但由此也带来了信息安全问题。现代密码技术作为解决信息安全问题的主要手段，其重要性得到了普遍认同，对它的理论研究和应用研究已成为计算机领域重要的研究方向。 自1949年Shannon发表《保密通信的信息理论》将密码学研究纳入科学轨道以来，现代密码学基本可分为以DES为代表的对称密码学和以RSA为代表的公钥密码学。由于公钥密码体制的非对称结构，使得它不仅可应用于数据加密，还可被广泛地应用于身份识别、数字签名、密钥协商和电子支付等诸多领域，所以自1976年Diffie和Hellman提出公钥密码思想以来，就引起了人们的广泛重视。 目前大多数被普遍认可的公钥密码体制的安全性均基于某个数学困难问题。根据所依据的数学难题这些体制主要有三类：基于大整数分解问题的RSA型公钥密码、基于有限域上离散对数问题的E1Gamal型公钥密码和基于椭圆曲线离散对数问题(ECDLP：Elliptic Curve Discrete Logarithms Problem)的椭圆曲线公钥密码(ECC：Elliptic Curve Cryptography)。与其他公钥密码体制相比，ECC突出的优势在于：对于其所基于的数学难题并不存在亚指数时间算法，从而能够以更小的密钥尺寸满足相同的安全性要求。通常认为，为得到合理的安全性，RSA应当使用1024比特的模长，而对于ECC来说，只需使用160比特的模长。正是由于ECC密钥短的特点而受到国际上的广泛关注，已经对RSA、E1Gamal等公钥密码体制形成强劲的挑战。同时国际上对有关ECC的标准化也已完成，如美国国家标准与技术研究所(ANSI)公布的ANSI X9.62和ANSIX9.63、IEEE-P1363制定的公钥密码标准。可以说在未来的若干年内，ECC将日渐成熟，应用领域将逐步深入到信息安全的各个方面。 快速实现问题是目前ECC研究中的一个重要问题。ECC的实现可分为三个层次来讨论：第一层次为数乘运算，讨论如何将数乘转化为次数尽可能少的点加和倍点运算；第二层次为群运算，讨论如何将点加和倍点在一定的坐标系下转化为域运算；第三层次为域运算，主要包括域元素加法、乘法、平方和求逆，因求逆运算可转化为乘法和平方，因而主要的域运算是乘法和平方。综上所述，实现ECC的核心环节是数乘和域元素乘法与平方运算，因此，提高这三种运算的速度是提高ECC效率的关键。适用于建立ECC的有限域有三类：素域、基域和扩域，目前最常用的有限域是基域，因此对基域域运算进行深入研究具有较高的实用价值。基域元素乘法有两类实现方法，一为多项式基域元素乘法，二为正规基特别是优化正规基域元素乘法。大量研究表明，多项式基域元素乘法较适合于软件实现，而因正规基表示域元素时平方运算仅需一次循环移位即可完成，但此时乘法运算较为复杂，因此，努力提高正规基域元素乘法速度对于实现ECC具有较高的理论和实践价值。 近年来，国内外的密码学研究者对基域上实现ECC进行了广泛研究。这些研究结果表明，基域上的所有椭圆曲线均可同构于y2+xy=x3+a2x2+a6和y2+y=x3+a4x+a6.两式，后者为超奇异椭圆曲线，不适合密码学，只有前式表示的曲线适合于构建安全的密码算法；前式中，当a2取0或1及a6取1时所得曲线称为Koblitz曲线。利用正规基实现基于Koblitz曲线的数乘运算时，可首先利用Frobenius映射将整数k转换成TNAF表示式，然后利用该表示式计算数乘，由此带来的好处是无需倍点运算。因此，如何进一步减少整数k的TNAF表示式长度是提高数乘运算的关键。 本文对椭圆曲线公钥密码体制的实现问题进行了较为深入的研究，重点考察了正规基表示时的Lambda矩阵快速生成、基域元素乘法算法和基于Koblitz曲线的数乘算法。 首先，对椭圆曲线公钥密码体制的理论基础做了较为深入的讨论，对正规基域元素乘法中Lambda矩阵生成算法进行了深入剖析，给出了Type I型和Type II型Lambda矩阵的生成算法，并通过详细分析Type II型Lambda矩阵的生成过程，提出了一种快速生成算法，该算法将Lambda矩阵的生成速度提高约50％。 其次，深入研究了正规基域元素乘法运算，给出了优化正规基域元素乘法的一般计算公式，同时通过仔细分析Rosing算法和Ning-Yin算法，提出了一种优化正规基域元素乘法的改进算法和三种预计算方法，实验结果表明，该改进算法与Ning-Yin算法相比能提高约20％。 再次，深入研究了Koblitz椭圆曲线的性质，讨论了优化正规基表示域元素对数乘算法的影响，并讨论了数乘算法的NAF算法和TNAF算法，实现了一种TNAF改进算法，将数乘运算速度提高了约50％，从而从数乘层面进一步提高了ECC的实现速度。 最后，将这些算法应用于实现ECDSA数字签名体制，从实践角度证明了这些改进算法和实现的可行性，从而从整体上将数乘的计算速度提高约68％。本论文的研究成果对于各种椭圆曲线公钥密码体制的应用具有一定的理论参考价值和工程实践意义。

目录

文摘

英文文摘

声明

第1章前言

1.1信息安全技术研究意义

1.2信息安全技术研究现状与发展趋势

1.2.1信息安全技术研究现状

1.2.2信息安全技术面临的挑战

1.2.3信息安全技术发展趋势

1.3油田数据安全技术现状

1.3.1油田数据安全系统

1.3.2油田数据安全内容

1.3.3油田数据安全方案

1.4研究内容和方法

1.5研究成果和创新点

第2章密码学与密码体制

2.1密码学

2.2公钥密码体制

2.3数字签名体制

2.4椭圆曲线公钥密码体制

2.4.1椭圆曲线离散对数问题

2.4.2 ECDSA数字签名体制

2.4.3实现关键问题

第3章椭圆曲线群运算

3.1有限域

3.1.1素域

3.1.2基域

3.1.3扩或

3.2椭圆曲线

3.3椭圆曲线加法群

3.3.1椭圆曲线加法群的构造

3.3.2实数域群运算规则

3.3.3基域群运算规则

第4章优化正规基域元素乘法

4.1正规基域元素乘法

4.2 LAMBDA矩阵生成

4.2.1优化正规基

4.2.2 Type Ⅰ型Lambda矩阵生成

4.2.3 Type Ⅱ型Lambda矩阵生成

4.2.4 Type Ⅱ型Lambda矩阵生成改进算法

4.2.5基域中优化正规基存在情况

4.3优化正规基域元素乘法

4.3.1一般计算公式

4.3.2 Rosing算法

4.3.3 Ning-Yin算法

4.3.4改进算法

4.3.5预计算方法

第5章KOBLITZ曲线的数乘算法

5.1数乘运算

5.2 NAF算法

5.3 Koblitz曲线

5.4 Frobenius映射

5.5整数的TNAF表示

5.6算法改进

5.7TNAF表示时的数乘算法

第6章改进算法测试结果讨论及应用

6.1 Lambda矩阵生成改进算法测试与讨论

6.2乘法改进算法测试与讨论

6.3数乘改进算法测试与讨论

6.4 ECDSA的实现

结论

致谢

参考文献

附录A