《ECC核心算法改进与硬件实现方案》由会员分享，可在线阅读，更多相关《ECC核心算法改进与硬件实现方案（14页珍藏版）》请在金锄头文库上搜索。
1、摘要作为一种公钥加密算法，椭阅曲线加密算法由于具有处理速度快、低功耗、抗攻 击能力强、节省存储空间和带宽等优势，得到了广泛应用。尤其是我W于2010年公布 针对ECC的SM2公钥密码算法以来，国内很多研究所、高校、公司都开始了 SM2商 用化的研宂工作，因此，对于ECC算法和硬件实现的研宂意义重大。木文主要改进了椭圆曲线加密算法，并对点乘进行了高效硬件实现，实现了 256 位模p素数域上的ECC运算，适用于硬件条件受限的应用场合。第一，分析了 ECC 各层次算法，选择了适合于本设计目标的实现方案；第二，优化了 BLWL类型基2的 Montgomery模乘算法，利用流水线方式提高了模乘运算效率；
2、第三，为了避免点乘过 程中的模逆运算，选择在Jacobian射影坐标系下完成倍点运算，在Jacobian和仿射混 合坐标系下完成点加运算，并优化了点加和倍点过程，用两个模乘器实现，提高运算 效率；第四，选择NAF方法进行点乘，并优化了电路实现，给出了整个点乘过程，完 成了 ECC协处理器的设计。在整个设计过程中，主耍有3个创新点：对Montgomery模乘算法的优化以及采用 流水线方式进行实现；对点加和倍点过程的优化以及双模乘器方式实现；对NAF方法 的实现以及整体点乘的硬件实现。选择SM2推荐的256位素数域椭圆曲线参数，给出了 ASIC和FPGA W种硬件实 现方案，并模拟了基本的ElGa
3、mal方案，验证了点乘结果的正确性。综合结果表明， 本设计在速度和面积上达到了很好的折中，实现了设计目标。1素数域运算和点运算分析椭阏曲线加密算法的运算层次如错误!未找到引用源。所示，包括：协议层、群运 算层、曲线运算层和域运算层。协议层以点乘运算为基础，点乘运算通过多次调用点 加和倍点运算来实现，点加和倍点运算通过调用模加减、模乘、模平方、模逆等域运 算来实现。上层运算的性能很大程度上取决于下层运算的性能，因此，对于有限域上 元素的模加减、模乘、模平方、模逆运算的有效实现非常重要。木文关注于底三层的 实现。点乘是椭圆曲线数字签名、身份认证和加密体制的核心运算。优化点乘运算的方 式一般有三种：
4、一是对底层的优化，通过对域运算的分析改进，提高计算效率；二是 对点运算的优化，提高点操作效率；三是对顶层的优化，通过对标量的表示方式的 转化改进点乘算法，从而减少点乘运算中调用点加的次数。素数域模加减运算相比较 其他复杂运算来说可以忽略不计，而模平方运算可以通过模乘来实现，从而节省面积。 因此，本章首先对底层运算模乘和模逆进行了分析研究，其次确定了椭圆曲线点加和 倍点方案，最后是对顶层运算点乘的分析，从而得到高效点乘方案。1.1素数域模乘当今的加解密认证系统中，快速模乘得到了广泛使用。模乘是整个ECC算法硬件 实现的重点，其效率很大程度上决定了系统运行的速度。因此，如何减少模乘运算时 间，提高
5、模乘频率，是非常重要的。1.1.1传统的素数域模乘素数域尽上的乘法什/7可以通过先将fZ和6作整数乘法，再以P为模做约减运算 来实现。Karatsuba-Ofman方法的核心思想是将2/位的tz和分块，使得2/位的整数 乘转化为/位或更短位的整数乘、加法和减法来完成。对于二进制域乘法来说，其中的 加减运算均可以通过异或操作來实现，使得该算法可以得到很好的应用；对于素数域 适当大小的整数，该算法也是很有用的；但是对于素数域大整数乘法来说，硬件实现 整数乘法器和较长的进位传播链成为其实现的瓶颈ll2j。Montgomery模乘被认为是S前 最高效和最主流的一种模乘算法，它同时完成了乘法和约减功能，
6、将在1.1.2节进行详 细介绍。对大数乘法计算完成之后，进行模约减的方法主耍有三种：经典的模约减、 Barrett 模约减、Montgomery 模约减。对于非特殊形式的模P，约减运算是整个模乘运算中非常费时的部分。Barrett约减 方法用低成本的运算代替了高成本的除法，但是需要一种高成本的与模和关的计算， 适合于对一个模的多次约减运算13，14。当前，最流行有效的约减方式是Montgomery模 约减方法，它利用简单的移位代替了复杂的除法运算，因此相较于其他方式，Montgomery方法更快速。而对于某一指定的模p,具有更加简便的方式。美国FIPS 186-2标准U5j推荐的模 P256=
7、2256-2224+2192+296-l的快速约减，由于它可以表示成少量的2的幂的和或差，因此， 可以通过少量的256位整数相加减来实现快速约减。参考NIST素数快速约减过程，由于SM2算法中推荐的素数在基232下位值为0, U,因此约减过程可以大大简化，推导过程见附荥。这里直接给出了其快速约减算 法1-1。需要注意的是，在第2步的加减法是模加减，因此可能还需要儿次取模运算才 能得到最终的输出cmod/7。算法 1-1 模 p256=2256-2224-296+264-l 的快速约减输入：?=(?15, Ci4, Ci3, Ci2, Cn, Cjo, c9, c8, c7, Q, C5, c4
8、, c3, C2, Cl, c。)为 232 进制整数，?e0, p2)o 输出：c mod 1定义256位整数：S=(c7, C6, c5, Q, c3, C2, Cl, Co)，5*2(。8，C，Cjo, C9, Cg, 0, *13，Cj2)53=(c9, 0, 0, 0, Cl 5, 0, Cg, c8),4=(10, 0, 0, Cs, C4, 0, C10, C9)，5=(15 14, C13, C2, C9 0, C12, Cn),*V6=(lb 15, C!4, Cl3, C12, 0, Cn, C10),57=(c12,0,0,0,0,0,0,0),58=(C13, 0,0,
9、 0, 0, 0, 0, c13)，恥=(14, 0, 0, 0, 0, 0, c14, c14)，分10=(。5, 0, t、5, C14, C13, 0, C15, ?15)5n=(0, 0, 0, 0, 0, c8, 0, 0),12=(0, 0,0, 0, 0, c9, 0, 0),513=(0, 0, 0, 0, 0, C13, 0, 0),5|4=(0, 0, 0, 0, 0, 6*14, 0, 0)。2 返 I口I(.y 1 +5,2+53+.V4+55+5,6+2.S，7+258+259+2kV|()一511 5 12S13514 m()d /?)。Montgomery 模乘M
10、ontgomery模乘的基木思想是用简单的加法和移位操作代替复杂的除法运算，同 时完成乘法和取模，不仅提高了运算效率，而且非常适合硬件实现16，17。设6/，0, p-1，要计算mod p。p的二进制表示长度力m，字长为w位， 选Montgomery域上的模数/?，使得J=L gcd(/?, p)= 1,表示/?和/?的最大公因子为1。 为获得更高效率，通常选择为字长的倍数，一般令A和6的Montgomery乘积、定义为：可以将Montgomery模乘过程分为三步：将素数域上的元素6Z和/?转换成Montgomery域上的元素A和B，从而将正常数和Montgomery数进行对应的映射。转换过程
11、为计算A和的Montgomery乘积，即将Montgomery数反变换为正常数，得到结果可见，Montgomery乘法的结果是c的Montgomery数，即该算法在Montgomery 域上是封闭的。对于单次模乘运算，需要调用4次Montgomery算法，这是不合算的。 然jflj，由于Montgomery乘法是封闭的，对于ECC算法中的点运算，需要进行上万次 模乘的情况，只需要在初始吋进行一次数据变换，中间的计算都在Montgomery域中进 行，结束时再进行一次反变换即可，这样Montgomery算法的效率就体现了出来。同时, Montgomery算法还可以用来加速模幂的计算。而且素数域模
12、加减运算也可以在 Montgomery域中完成，模加减计算与普通素数域运算相同，如公式错误!未找到引用源。 所示。这里给出了基本的Montgomery模乘算法1819。1.2素数域模逆在素数域的各种运算中，模逆最复杂、最耗资源、运算时间较长。模逆运算效率 的高低将直接影响整个点乘运算的效率。素数域久上的非零元素6Z的逆记力简记为即若在什上存在惟一 一个非零元素X,使得(nwdp)，则称元素;C为6Z的逆cf输入：素数/?，元素el，p-l。输出：a mod po u=a，v=p，X|=l X2=0o 2当关1且vtM时，重复执行2.1当是偶数时，重复执行“=w/2 o若A是偶数，则七以；否则，
13、i=(x1+/?)/2。2.2当v是偶数时，重复执行 v=v/2o。常见的计算的算 法冇三种：小费马定理、扩展的整数Euclidean算法和Montgomery求逆算法。小费马定理的原理是：设p是质数，6/是与p互质的一个整数，则有=办即三，(modp)。因此，某个域元素t/在模p下的逆，可以通过求模幂(mod 妁来实现，不需要再额外加入新的模块。但是这样实现的模逆运算将非常费时。Montgomery求逆的基本思想与模乘类似，对丁特别选择的/?=2用低成本的tz/T1 modp运算代替复杂的tzmodp运算，计算效率比小费马定理提高了很多。然而，其计 算结果仍然是一个Montgomery数，如
14、果采用这种算法，求逆之后还需要额外的步骤将 Montgomery数转换为正常数，硬件实现起来比较麻烦。Euclidean算法的内容为：令和Z?为正整数，则扩展的Euclidean算注可以用于寻 找两个整数x和y，使得从而求得T1。算法1-2给出丫扩展的二进 制Euclidean求逆方法。算法1-2 扩展的三进制Euclidean求逆方法若是偶数，则X2=X2/2;否则，2=0的9)/2。若 mSv，则 w=(w-v)/2。2.3.1 若 X|X2，贝1J若1和2奇偶性相同，则XJ=(X|-X2)/2。若和A奇偶性不同，则A =(4 -x2+p)/2。2.3.2 若 X|&2，贝1J若|和x2奇
15、偶性相同，则A=(X|-x2)/2+p。若和奇偶性不同，则a =(4 -x2+p)/2。2.4 若 wv，则 v=(v-w)/2。2.4.1 若 2义1，则若和奇偶性相同，则x2=(x2_xi )/2。若A和奇偶性不同，则x2=(x2-x1+p)/2。2.4.2 若 x2Sxi，则若Xi和a奇偶性相同，则X2=(xm)/2+/?。若A和幻奇偶性不同，则X2=(X2-X +p)/2。3若w=l，则返回若v=l，则返回x2。算法计算过程中保持下列关系式不变：ax+py=bh ov2+p，2=v，其中，i和J，2不被计 算。当或v=l时算法终止。当i尸1时，cixpy=,因此modp;当v=l时， axpy2=,因此modp。该算法用简单的模加减、移位、奇偶判断和比较运算代 替了原来的除法运算，效率更高，也更适合于硬件实现。对于奇偶判断，只需要确定 该数的最低位是1还是0即可；对于比较运算，可以通过相减并判断结果的最高位是 否溢出来确定两数大小。将该算法的初始条件i=l修改为x=b,便町得到计算bla=bax mod 的除法算法。算法在中间步骤中完成了取模，使得最后计算结果在l，p-l范围 内，其计算时间最多为相同位数的乘法算法的两倍。对于m位的输入，计算时间为2m。1.3点加和倍点算法椭
