二元域椭圆加密算法(ECC)C 语言实现dajiangwangmail.com2013-09-22二二元元域域椭椭圆圆曲曲线线加加密密算算法法 ( (E EC CC C) )C C 语语言言实实现现d da aj ji ia an ng gw wa an n g gm ma ai il l. .c co om m2 20 01 13 3- -9 9- -2 22 2二元域椭圆加密算法(ECC)C 语言实现dajiangwangmail.com2013-09-221. 前言.1 2. BN 定义. 2 3. BN 算法. 5 3.1. 单宽度整数乘法.5 3.2. 单宽度整数除法.6 3.3. 中间计算结果函数.7 3.4. 计算大数位数的函数.9 3.5. 大数转换函数.10 3.6. 大数赋值函数.11 3.7. 大数比较函数.12 3.8. 大数移位函数.13 3.9. 大数加减函数.14 3.10. 大数乘法函数.15 3.11. 大数除法函数.16 3.12. 大数取模函数.17 3.13. 大数乘法取模函数.17 3.14. 大数求倒数取模函数.18 3.15. 大数其他函数.19 4. HASH 函数.21 5. ECC 算法.25 5.1. ECC 算法头文件.25 5.2. ECC 算法实现.26 6. 附录.45 7. 参考资料.48二元域椭圆加密算法(ECC)C 语言实现dajiangwangmail.com2013-09-2211. 前前言言二元域的椭圆加密算法在工作中会遇到， 由于该算法涉及到许多数学理论， 要理解算法 不是太容易。 ECC 在 PC 机上有很多实现，比如 openssl、tomcrypto 以及 gcrypto 等；以上的算法由 于要考虑运行效率，使用了很多加速算法，导致阅读时不易理解。 为了理解该算法的关键部分， 本文依照 RSA 提供的大数算法， 对 TinyBECC 的源码进行 整理修改， 实现了 ECC 加密算法的 ECDSA。 该代码可以在 Windows 下使用 Microsoft VC 6.0 进行编译，也可以在 Fedora Linux 下的使用 gcc 进行编译。为了验证算法的正确性，可以通 过 openssl 进行对比测试。 作为一个示例性的程序，性能较差，只能用来了解 ECC 算法的原理。二元域椭圆加密算法(ECC)C 语言实现dajiangwangmail.com2013-09-2222. BN 定定义义ECC 使用大数进行运算，在计算机表示大数时，一般采用多个字节来存储。在 C 语言 中使用整数数组来存储大数。以下代码假设计算机的整数宽度为 32Bit, 存储时先存储低端 数据，后存储高端数据。以下代码是从 RSA 提供的 RSA 算法实现参考中(BN.h 和 BN.c)复 制出来的，然后进行了一些修改。以下代码定义一些宏、数据类型以及函数原型。图 1. 大数头文件 bn.h (第 1 部分)#ifndef _BN_H #define _BN_Htypedef unsigned charuint8_t; typedef unsigned shortuint16_t; typedef unsigned intuint32_t; typedef signed charint8_t; typedef shortint16_t; typedef intint32_t;#define NN_HALF_DIGIT_BITS16 #define NN_DIGIT_BITS32 #define MAX_NN_HALF_DIGIT0xffff #define MAX_NN_DIGIT0xffffffff #define NN_DIGIT_LEN(NN_DIGIT_BITS / 8) typedef uint16_tNN_HALF_DIGIT; typedef uint32_tNN_DIGIT;#define LOW_HALF(x)(x) uint32_t NN_Bits(NN_DIGIT *a, uint32_t digits);/* Encode BIG NUMBER b into octet string a */ void NN_Encode(uint8_t *a, uint32_t len, NN_DIGIT *b, uint32_t digits);/* Decode octet string a to BIG NUMBER b */ void NN_Decode(NN_DIGIT *a, uint32_t digits, uint8_t *b, uint32_t len);void NN_Assign(NN_DIGIT *a, NN_DIGIT *b, uint32_t digits);void NN_AssignZero(NN_DIGIT *a, uint32_t digits);void NN_Assign2Exp(NN_DIGIT *a, uint32_t b, uint32_t digits);#define NN_ASSIGN_DIGIT(a, b, digits)NN_AssignZero (