ecc核心算法改进与硬件实现方案

《ecc核心算法改进与硬件实现方案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要作为一种公钥加密算法，椭阅曲线加密算法由于具有处理速度快、低功耗、抗攻击能力强、节省存储空间和带宽等优势，得到了广泛应用。尤其是我W于2010年公布针对ECC的SM2公钥密码算法以来，国内很多研究所、高校、公司都开始了SM2商用化的研宂工作，因此，对于ECC算法和硬件实现的研宂意义重大。木文主要改进了椭圆曲线加密算法，并对点乘进行了高效硬件实现，实现了256位模p素数域上的ECC运算，适用于硬件条件受限的应用场合。第一，分析了ECC各层次算法，选择了适合于本设计目标的实现方案；第二，优化了BLWL类型基

2、2的Montgomery模乘算法，利用流水线方式提高了模乘运算效率；第三，为了避免点乘过程屮的模逆运算，选择在Jacobian射影坐标系下完成倍点运算，在Jacobian和仿射混合坐标系下完成点加运算，并优化了点加和倍点过程，用两个模乘器实现，提高运算效率；第四，选择NAF方法进行点乘，并优化了电路实现，给出了整个点乘过程，完成了ECC协处理器的设计。在整个设计过程中，主耍有3个创新点：对Montgomery模乘算法的优化以及采用流水线方式进行实现；对点加和倍点过程的优化以及双模乘器方式实现；对NAF方法的

3、实现以及整体点乘的硬件实现。选择SM2推荐的256位素数域椭圆曲线参数，给出了ASIC和FPGAW种硬件实现方案，并模拟了基本的ElGamal方案，验证了点乘结果的正确性。综合结果表明，本设计在速度和面积上达到了很好的折屮，实现了设计目标。1素数域运算和点运算分析椭阏曲线加密算法的运算层次如错误!未找到引用源。所示，包括：协议层、群运算层、曲线运算层和域运算层。协议层以点乘运算为基础，点乘运算通过多次调用点加和倍点运算来实现，点加和倍点运算通过调用模加减、模乘、模平方、模逆等域运算来实现。上层运算的性能很大

4、程度上取决于下层运算的性能，因此，对于有限域上元素的模加减、模乘、模平方、模逆运算的有效实现非常重要。木文关注于底三层的实现。点乘是椭圆曲线数字签名、身份认证和加密体制的核心运算。优化点乘运算的方式一般有三种：一是对底层的优化，通过对域运算的分析改进，提高计算效率；二是对点运算的优化，提高点操作效率；三是对顶层的优化，通过对标量々的表示方式的转化改进点乘算法，从而减少点乘运算中调用点加的次数。素数域模加减运算相比较其他复杂运算来说可以忽略不计，而模平方运算可以通过模乘来实现，从而节省面积。因此，本章首先对底

5、层运算模乘和模逆进行了分析研究，其次确定了椭圆曲线点加和倍点方案，最后是对顶层运算点乘的分析，从而得到高效点乘方案。1.1素数域模乘当今的加解密认证系统中，快速模乘得到了广泛使用。模乘是整个ECC算法硬件实现的重点，其效率很大程度上决定了系统运行的速度。因此，如何减少模乘运算时间，提高模乘频率，是非常重要的。1.1.1传统的素数域模乘素数域尽上的乘法什/7可以通过先将fZ和6作整数乘法，再以P为模做约减运算来实现。Karatsuba-Ofman方法的核心思想是将2/位的tz和分块，使得2/位的整数乘转化为/

6、位或更短位的整数乘、加法和减法来完成。对于二进制域乘法来说，其中的加减运算均可以通过异或操作來实现，使得该算法可以得到很好的应用；对于素数域适当大小的整数，该算法也是很有用的；但是对于素数域大整数乘法来说，硬件实现整数乘法器和较长的进位传播链成为其实现的瓶颈ll2j。Montgomery模乘被认为是S前最高效和最主流的一种模乘算法，它同时完成了乘法和约减功能，将在1.1.2节进行详细介绍。对大数乘法计算完成之后，进行模约减的方法主耍有三种：经典的模约减、Barrett模约减、Montgomery模约减。对于

7、非特殊形式的模P，约减运算是整个模乘运算中非常费时的部分。Barrett约减方法用低成本的运算代替了高成本的除法，但是需要一种高成本的与模和关的计算，适合于对一个模的多次约减运算［13，14］。当前，最流行有效的约减方式是Montgomery模约减方法，它利用简单的移位代替了复杂的除法运算，因此相较于其他方式，Montgomery方法更快速。而对于某一指定的模p,具有更加简便的方式。美国FIPS186-2标准U5j推荐的模P256=2256-2224+2192+296-l的快速约减，由于它可以表示成少量的2

8、的幂的和或差，因此，可以通过少量的256位整数相加减来实现快速约减。参考NIST素数快速约减过程，由于SM2算法中推荐的素数在基232下位值为｛0,±U,因此约减过程可以大大简化，推导过程见附荥。这里直接给出了其快速约减算法1-1。需要注意的是，在第2步的加减法是模加减，因此可能还需要儿次取模运算才能得到最终的输出cmod/7。算法1-1模p256=2256-2224-296+264-l的快速约减输入：