椭圆加密算法（ECC）是一种公钥加密体制，最初由Koblitz和Miller两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。
 
 
 
 
 
 优点
 
 编辑
 

  与经典的RSA，DSA等公钥
 密码体制相比，椭圆密码体制有以下优点：
 
 
 
 
 
 
 
 
 安全性高
 
 

  有研究表示160位的椭圆密钥与1024位的RSA密钥安全性相同。
 
 
 
 
 
 
 
 
 处理速度快
 
 

  在
 私钥的加密解密速度上，ecc算法比RSA、DSA速度更快。
 
 
 存储空间占用小。
 
 
 带宽要求低.
 
 
 
 
 
 
 
 
 分类
 
 编辑
 

  公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、
 离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
 

 参考百度百科：http://baike.baidu.com/link?url=lmC0XPAo8zgsKMzCp7iHOfj6LzPZvX6UF0QowaNSjEX-h9DvihI5RddFhb-5uNn8pK-svlSUe6KpIkEgPy-zRq
 
 
 
 
 
 
 
 

 

 
 
2002年，美国SUN公司将其开发的椭圆加密技术赠送给开放源代码工程
 
公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。 
 
椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程： 
 
y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) 
 
所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。 
 
椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式 
 
mP=P+P+…+P=Q (2) 
 
中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这 个困难问题设计而来。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller在1985年分别独立提出的。 
 
椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高的一种体制。解椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，其时间复杂度为，是完全指数阶的。其中n为等式(2)中m的二进制表示的位数。当n=234, 约为2117，需要1.6x1023 MIPS 年的时间。而我们熟知的RSA所利用的是大整数分解的困难问题，目前对于一般情况下的因数分解的最好算法的时间复杂度是子指数阶的，当n=2048时，需 要2x1020MIPS年的时间。也就是说当RSA的密钥使用2048位时，ECC的密钥使用234位所获得的安全强度还高出许多。它们之间的密钥长度却 相差达9倍，当ECC的密钥更大时它们之间差距将更大。更ECC密钥短的优点是非常明显的，随加密强度的提高，密钥长度变化不大。 
 
德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司实现了椭圆曲线密码体制，我国也有一些密码学者做了这方面的工作。许多标准化组 织已经或正在制定关于椭圆曲线的标准，同时也有许多的厂商已经或正在开发基于椭圆曲线的产品。对于椭圆曲线密码的研究也是方兴未艾，从 ASIACRYPTO’98上专门开辟了ECC的栏目可见一斑。 
 
在椭圆曲线密码体制的标准化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它们所开发的椭圆曲线标准的文档有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等。
 
2003年5月12日中国颁布的无线局域网国家标准 GB15629.11 中，包含了全新的 WAPI(WLAN Authentication and Privacy Infrastructure)安全机制，能为用户的WLAN系统提供全面 的安全保护。这种安全机制由 WAI和WPI两部分组成，分别实现对用户身份的鉴别和对传输的数据加密。WAI采用公开密钥密码体制，利用证书来对 WLAN系统中的用户和AP进行认证。证书里面包含有证书颁发者(ASU)的公钥和签名以及证书持有者的公钥和签名，这里的签名采用的就是椭圆曲线ECC 算法。
 
加拿大Certicom公司是国际上最著名的ECC密码技术公司,已授权300多家企业使用ECC密码技术，包括Cisco 系统有限公司、摩托罗拉、Palm等企业。Microsoft将Certicom公司的VPN嵌入微软视窗移动2003系统中。
以下资料摘自：http://www.hids.com.cn/data.asp
 
公钥密码系统的加密算法ECC与RSA的对比 
 第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：基于大整数因子分解问题（IFP）的RSA算法和基于椭圆曲线上离散对数计算问题 （ECDLP）的ECC算法。RSA算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全强度相对较低。目前用国际上公认的对于 RSA算法最有效的攻击方法--一般数域筛(NFS)方法去破译和攻击RSA算法，它的破译或求解难度是亚指数级的。ECC算法的数学理论非常深奥和复 杂，在工程应用中比较难于实现，但它的单位安全强度相对较高。用国际上公认的对于ECC算法最有效的攻击方法--Pollard rho方法去破译和攻击ECC算法，它的破译或求解难度基本上是指数级的。正是由于RSA算法和ECC算法这一明显不同，使得ECC算法的单位安全强度高 于RSA算法，也就是说，要达到同样的安全强度，ECC算法所需的密钥长度远比RSA算法低（见表1和图1）。这就有效地解决了为了提高安全强度必须增加 密钥长度所带来的工程实现难度的问题。（见表2）
 
 
 

NAND FLASH ECC校验原理与实现



 
ECC简介
　　由于NAND Flash的工艺不能保证NAND的Memory Array在其生命周期中保持性能的可靠，因此，在NAND的生产中及使用过程中会产生坏块。为了检测数据的可靠性，在应用NAND Flash的系统中一般都会采用一定的坏区管理策略，而管理坏区的前提是能比较可靠的进行坏区检测。
　　如果操作时序和电路稳定性不存在问题的话，NAND Flash出错的时候一般不会造成整个Block或是Page不能读取或是全部出错，而是整个Page（例如512Bytes）中只有一个或几个bit出错。
　　对数据的校验常用的有奇偶校验、CRC校验等，而在NAND Flash处理中，一般使用一种比较专用的校验——ECC。ECC能纠正单比特错误和检测双比特错误，而且计算速度很快，但对1比特以上的错误无法纠正，对2比特以上的错误不保证能检测。
 
ECC原理
　　ECC一般每256字节原始数据生成3字节ECC校验数据，这三字节共24比特分成两部分：6比特的列校验和16比特的行校验，多余的两个比特置1，如下图所示：
 

 
　　
　　ECC的列校验和生成规则如下图所示：
 

 

 

　　用数学表达式表示为：
　　　　P4=D7(+)D6(+)D5(+)D4　　P4`=D3(+)D2(+)D1(+)D0
　　　　P2=D7(+)D6(+)D3(+)D2　　P2`=D5(+)D4(+)D1(+)D0
　　　　P1=D7(+)D5(+)D3(+)D1　　P1`=D6(+)D4(+)D2(+)D0
　　这里(+)表示“位异或”操作
　　
　　ECC的行校验和生成规则如下图所示：
 

 
　　用数学表达式表示为：
　　　　P8 = bit7(+)bit6(+)bit5(+)bit4(+)bit3(+)bit2(+)bit1(+)bit0(+)P8
　　　　……………………………………………………………………………………
　　这里(+)同样表示“位异或”操作
　
　　当往NAND Flash的page中写入数据的时候，每256字节我们生成一个ECC校验和，称之为原ECC校验和，保存到PAGE的OOB（out-of-band）数据区中。
　　当从NAND Flash中读取数据的时候，每256字节我们生成一个ECC校验和，称之为新ECC校验和。
　　校验的时候，根据上述ECC生成原理不难推断：将从OOB区中读出的原ECC校验和新ECC校验和按位异或，若结果为0，则表示不存在错（或是出现了ECC无法检测的错误）；若3个字节异或结果中存在11个比特位为1，表示存在一个比特错误，且可纠正；若3个字节异或结果中只存在1个比特位为1，表示OOB区出错；其他情况均表示出现了无法纠正的错误。
 
ECC算法的实现
　　static const u_char nand_ecc_precalc_table[] =
　　{
　　　　0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00,
　　　　0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
　　　　0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
　　　　0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
　　　　0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
　　　　0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
　　　　0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
　　　　0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
　　　　0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
　　　　0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
　　　　0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
　　　　0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
　　　　0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
　　　　0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
　　　　0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
　　　　0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00
　　};
 
　　//　Creates non-inverted ECC code from line parity
　　static void nand_trans_result(u_char reg2, u_char reg3,u_char *ecc_code)
　　{
　　　　u_char a, b, i, tmp1, tmp2;
 
　　　　/* Initialize variables */
　　　　a = b = 0x80;
　　　　tmp1 = tmp2 = 0;
 
　　　　/* Calculate first ECC byte */
　　　　for (i = 0; i < 4; i++)
　　　　{
　　　　　　if (reg3 & a)　　　 /* LP15,13,11,9 --> ecc_code[0] */
　　　　　　　　tmp1 |= b;
　　　　　　b >>= 1;
　　　　　　if (reg2 & a)　　　 /* LP14,12,10,8 --> ecc_code[0] */
　　　　　　　　tmp1 |= b;
　　　　　　b >>= 1;
　　　　　　a >>= 1;
　　　　}
 
　　　　/* Calculate second ECC byte */
　　　　b = 0x80;
　　　　for (i = 0; i < 4; i++)
　　　　{
　　　　　　if (reg3 & a)　　　 /* LP7,5,3,1 --> ecc_code[1] */
　　　　　　　　tmp2 |= b;
　　　　　　b >>= 1;
　　　　　　if (reg2 & a)　　　 /* LP6,4,2,0 --> ecc_code[1] */
　　　　　　　　tmp2 |= b;
　　　　　　b >>= 1;
　　　　　　a >>= 1;
　　　　}
 
　　　　/* Store two of the ECC bytes */
　　　　ecc_code[0] = tmp1;
　　　　ecc_code[1] = tmp2;
　　}
 
　　//　Calculate 3 byte ECC code for 256 byte block
　　void nand_calculate_ecc (const u_char *dat, u_char *ecc_code)
　　{
　　　　u_char idx, reg1, reg2, reg3;
　　　　int j;
 
　　　　/* Initialize variables */
　　　　reg1 = reg2 = reg3 = 0;
　　　　ecc_code[0] = ecc_code[1] = ecc_code[2] = 0;
 
　　　　/* Build up column parity */
　　　　for(j = 0; j < 256; j++)
　　　　{
 
　　　　　　/* Get CP0 - CP5 from table */
　　　　　　idx = nand_ecc_precalc_table[dat[j]];
　　　　　　reg1 ^= (idx & 0x3f);
 
　　　　　　/* All bit XOR = 1 ? */
　　　　　　if (idx & 0x40) {
　　　　　　　　reg3 ^= (u_char) j;
　　　　　　　　reg2 ^= ~((u_char) j);
　　　　　　}
　　　　}
 
　　　　/* Create non-inverted ECC code from line parity */
　　　　nand_trans_result(reg2, reg3, ecc_code);
 
　　　　/* Calculate final ECC code */
　　　　ecc_code[0] = ~ecc_code[0];
　　　　ecc_code[1] = ~ecc_code[1];
　　　　ecc_code[2] = ((~reg1) << 2) | 0x03;
　　}
 
　　//　Detect and correct a 1 bit error for 256 byte block
　　int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc)
　　{
　　　　u_char a, b, c, d1, d2, d3, add, bit, i;
 
　　　　/* Do error detection */
　　　　d1 = calc_ecc[0] ^ read_ecc[0];
　　　　d2 = calc_ecc[1] ^ read_ecc[1];
　　　　d3 = calc_ecc[2] ^ read_ecc[2];
 
　　　　if ((d1 | d2 | d3) == 0)
　　　　{
　　　　　　/* No errors */
　　　　　　return 0;
　　　　}
　　　　else
　　　　{
　　　　　　a = (d1 ^ (d1 >> 1)) & 0x55;
　　　　　　b = (d2 ^ (d2 >> 1)) & 0x55;
　　　　　　c = (d3 ^ (d3 >> 1)) & 0x54;
 
　　　　　　/* Found and will correct single bit error in the data */
　　　　　　if ((a == 0x55) && (b == 0x55) && (c == 0x54))
　　　　　　{
　　　　　　　　c = 0x80;
　　　　　　　　add = 0;
　　　　　　　　a = 0x80;
　　　　　　　　for (i=0; i<4; i++)
　　　　　　　　{
　　　　　　　　　　if (d1 & c)
　　　　　　　　　　　　add |= a;
　　　　　　　　　　c >>= 2;
　　　　　　　　　　a >>= 1;
　　　　　　　　}
　　　　　　　　c = 0x80;
　　　　　　　　for (i=0; i<4; i++)
　　　　　　　　{
　　　　　　　　　　if (d2 & c)
　　　　　　　　　　　　add |= a;
　　　　　　　　　　c >>= 2;
　　　　　　　　　　a >>= 1;
　　　　　　　　}
　　　　　　　　bit = 0;
　　　　　　　　b = 0x04;
　　　　　　　　c = 0x80;
　　　　　　　　for (i=0; i<3; i++)
　　　　　　　　{
　　　　　　　　　　if (d3 & c)
　　　　　　　　　　　　bit |= b;
　　　　　　　　　　c >>= 2;
　　　　　　　　　　b >>= 1;
　　　　　　　　}
　　　　　　　　b = 0x01;
　　　　　　　　a = dat[add];
　　　　　　　　a ^= (b << bit);
　　　　　　　　dat[add] = a;
　　　　　　　　return 1;
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　i = 0;
　　　　　　　　while (d1)
　　　　　　　　{
　　　　　　　　　　if (d1 & 0x01)
　　　　　　　　　　　　++i;
　　　　　　　　　　d1 >>= 1;
　　　　　　　　}
　　　　　　　　while (d2)
　　　　　　　　{
　　　　　　　　　　if (d2 & 0x01)
　　　　　　　　　　　　++i;
　　　　　　　　　　d2 >>= 1;
　　　　　　　　}
　　　　　　　　while (d3)
　　　　　　　　{
　　　　　　　　　　if (d3 & 0x01)
　　　　　　　　　　　　++i;
　　　　　　　　　　d3 >>= 1;
　　　　　　　　}
　　　　　　　　if (i == 1)
　　　　　　　　{
　　　　　　　　　　/* ECC Code Error Correction */
　　　　　　　　　　read_ecc[0] = calc_ecc[0];
　　　　　　　　　　read_ecc[1] = calc_ecc[1];
　　　　　　　　　　read_ecc[2] = calc_ecc[2];
　　　　　　　　　　return 2;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　/* Uncorrectable Error */
　　　　　　　　　　return -1;
　　　　　　　　}
　　　　　　}
　　　　}
 
　　　　/* Should never happen */
　　　　return -1;
　　}