椭圆曲线加密算法的发展趋势

现代经济信息

椭圆曲线加密算法的发展趋势

周晚 贵州大学计算机科学与信息技术学院 贵州贵阳 550025

一、引言

根据加密算法与解密算法所使用的密钥是否相同，或是否能简单地由加/解密密钥求得解/加密密钥，可以将密码体制分成私钥密码体制(也叫单钥密码体制、对称密钥密码体制)和公钥密码体制(也叫作双钥密码体制、非对称密钥密码体制)。

对称密码体制中，在密钥管理和分配以及认证问题上，都有一定的缺陷。1976年美国斯坦福大学的博士生W.Diffie和他的导师M.Hellman教授发表了“密码学新方向”的论文，第一次提出公开密钥密码的概念。从此，密码学进入一个新的密码时代。

[1]

椭圆曲线并不是椭圆，只是它们与计算椭圆周长的方程相似。设F是一个域，如果F中一对数x， y满足方程

，此外，加上一个无穷远点O，就组成了椭圆曲线。

椭圆曲线可以定义在不同的有限域上，在实际应用中，通常在GF(p)和GF(2m)二者之中选择其一。一般情况下，二进制域上的椭圆曲线加密算法适合于硬件实现[2]素数域上的椭圆曲线加密算法适合于软件实现[3]，本文主要介绍后者。

椭圆曲线公钥密码体制有着其他公钥密码体制所无法比拟的优点，在相同的安全强度下，密钥尺寸比较小，选择余地比较大等，这使得椭圆曲线公钥密码可以适用于各种受限环境，因而深入研究椭圆曲线公钥密码具有很大的现实意义。

图2给出了椭圆曲线加密算法的加密和解密过程的运算层次，它主要分为：域运算层、椭圆曲线操作层和协议层。

二、公钥加密机制

公开密钥密码的基本思想是将传统的密码密钥一分为二，用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密，发送方和接收方每个拥有一对相互匹配的密钥中的一个(不是同一个)。 利用公钥算法，实现保密通信的过程如下：

（图1.公钥密码体制）

1.合法参与者容易生成一对密钥（公钥/私钥对）。

2.加密算法E和解密算法D都是高效的。这确保了密码的实用性。3.对于明文M有法都具备的基础条件。

4.攻击者如果知道密文以及公钥PK，要恢复明文计算上是困难的。

5.攻击者如果知道公钥PK，要确定私钥SK计算上是困难的。这是公开密钥的安全基础。

目前有以下三类系统被认为是安全和有效的：大整数因子分解系统(代表性的有RSA)、椭圆曲线离散对数系统(ECC)和离散对数系统(代表性的有DSA)。如下表所示：

。这是非对称加密与对称加密算

（图2. 椭圆曲线加密算法的运算层次）

协议层最接近于用户，主要完成协议的设计实现，为应用服务主要提供密钥交换和数字签名的功能；椭圆曲线操作层主要实现椭圆曲线上点的相关操作，其上的点乘运算影响着整个系统的效率；域运算层作为最基础、最核心的部分，影响决定着整个系统的性能和实现。椭圆曲线上的点乘运算是实现椭圆曲线密码体制的基本运算，同时也是最耗时的运算，它的运算效率直接决定着ECC的性能，所以也成为研究的热点和重点。

在椭圆曲线密码体制的软件实现中，最浪费时间的运算莫过于椭圆曲线的点乘运算。

所谓点乘，就是对给定椭圆曲线上的点P和正整数k，求k个P相加的结果，记作Q=kP=P+P+…+P。

在椭圆曲线点的点乘运算中，可以分为两种情况：一种是点固定的情况；一种是点未知的情况。可以对固定点的点乘算法进行一些预计算来提高算法的性能。[4]

三、椭圆加密算法

椭圆曲线密码(Elliptic Curve Cryptography， ECC)是1985年由N. Koblitz和V.Miller共同提出的。椭圆曲线密码属于公钥密码体制，它的安全性建立在椭圆曲线离散对数问题（ECDLP

）的困难性之上。

(1)模加运算

输入：模数p，a，b [0，p-1]输出：Step1.

186