椭圆曲线加密算法的C语言设计和实现.doc

《椭圆曲线加密算法的C语言设计和实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、椭圆曲线加密算法的C语言设计和实现椭圆曲线加密算法于1985年提出，由于自身优点，它一出现便受到关注，现在密码学界普遍认为它将替代RSA加密算法成为通用的公钥加密算法。那么我们今天就来看看椭圆曲线加密算法是如何通过C语言来设计实现的。一、椭圆曲线加密算法的C语言设计1、椭圆曲线加密系统的基本结构椭圆曲线的加解密流程如图1所示：椭圆曲线进行加密通信的过程如下：首先选定一个适合加密的椭圆曲线Ep(a，b)，并取椭圆曲线上的一点作为基点G。选择一个私有密钥k，并生成公开密钥K=kG。加密时，将明文编码到

2、Ep(a，b)上的一点M，并产生一个随机整数r(r

3、件，由加拿大人汤姆St.丹尼斯编写，用标准C语言写了几乎所有标准的密码算法模块，并且在几乎所有的操作系统下都可执行。LibTomMath库对高精度大整数的表示是该库最大的一个特点。在LibTomMath库中的高精度大整数表示如下：在32位机上unsignedlong为32bit，用mp_digit表示这个类型：typedefunsigned_longmp_digit；实际使用了32位的28位，少用4位，因此用16进制表示一个mp_digit为0XXXXXXX，其中X为16进制数字，将这个32位bi

4、t串称为一个mp_digit单元，若干个mp_digit单元构成一个大整数，结构定义一个大整数mpint如下：typeclefstruct{inlused，alloc，sign；mp_digit*dp;)mp_int；其中：dp是存放大整数的地址，将大整数（二进比特串）分段（mp_digit单元）存放在从该地址起的内存里，缺省时分配dp为MP_PREC=64个mp_digit单元，即alloc=64；used为实际使用的mp_digit单元；sign=0表示非负数，为1表示负数。对于分配了allo

5、c个mp_digit的大整数mpjnL，因为实际可以使用的比特数是28*alloc，因此可以表示的整数范围是[-228*alloc，228*alloc]。对于64位机情况类似。3、椭圆曲线的参数选取在基于椭圆曲线的加密和解密实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在SECI及IEEEP1363ECC工作草案中，所定义的二进制域上椭圆曲线用到六个参量T=(p，a，b，G，n，h)op，a，b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的整数部分

6、，这几个参量取值的选择直接影响加密的安全性。参量值一般要求满足以下几个条件：a）p当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求；b）p≠nxh；c）pt≠l(modn)，l≤t<20；d）a3+27b2≠O(modp)；e）n为素数；f）h≤4。本文选用大素数域上的椭圆曲线E(p)：y2=x3+ax+b作为我们的加密曲线。（1）参数a、b的选取采用构造法产生椭圆曲线CM(ComplexMultiplication)法，即先确定有限域Fp和其上的椭圆fHj线的阶，然后再构

7、造满足要求的椭圆曲线，即求出椭圆曲线方程E(p)：y2=x3+ax+b中的a，b。（2）基点的确定首先在椭圆曲线上随机选择一个有效点，然后根据选择的点得到阶是n的有效基点。这里有效基点的阶最好是曲线阶的点，至少是曲线阶的最大素因子，这样可以保证一定的安全。（3）私钥的确定随机选取1到P-1之间的素数作为私钥d。（4）公钥的确定由d乘我们所确定的基点得到公钥K，即K=dG。4、椭圆曲线的点加和标量乘对于一般的椭圆曲线方程yz+alxy+a3y=X3+a2xz+a,x+a6，设点P(xi，yl)，Q(

8、X2，yz)的和R(X3，y3)的坐标为x3=k2+kal+a2+xl+x2；y3=k(XI-X4)-y1-alx4-a3，其中当P≠Q时（点加运算）k=（y1-y2）／（x1-x2）；当P=Q时（倍点运算）k=(3×2+2a2x+a4-aly)/(2y+a1x+a3)；对于椭圆曲线方程y2-X3+aX+b，上述的公式变为X3=θ2_X1_X2;y3=θ(X1-X3)-y1，其中当P≠Q时（点加运算）θ=（y1-y2）／（x1-x2）；当P=Q时（倍点运算）θ=（3×12一a）／2