椭圆曲线加密算法（ECC）学习笔记
四月 10th, 2008
1985年，Miller和Koblitz分别独立提出了该想法。
Koblitz的论文见http://links.jstor.org/sici?sici=0025-5718%28198701%2948%3A177%3C203%3AECC%3E2.0.CO%3B2-E
椭圆曲线方程的图像并不是椭圆，取这个名字是因为它的形式和求椭圆弧线长度时用到的积分很像。
ECC因其密钥短加密速度快逐渐成为RSA的热门接替者。根据NSA的数据ECC用313位密钥的获得的安全性和RSA用4096位密钥相当，并且有着更快的性能。
可用于加密的椭圆曲线主要是模p的椭圆曲线，这种曲线上的点有这样一种性质，任意给出椭圆E上的两点P,Q可以很容易的计算出第三点R，反之则很难，并且R也在E上，如果把这种运算定义为加法运算则意味着E上的加法运算时封闭的。
如E：y^2≡x^3+4x+4(mod 5)
该E上的点是有限的，无论x取什么值，模5后都只能等于0，1，2，3，4中之一。代入x解对应的二次剩余方程即可求出对应的y。
但并非对于所有的x取值都有相应的y，当x≡3(mod 5)时，y^2≡43≡3(mod 5)无解。而x≡1(mod 5)时，y^2≡9≡4(mod 5)，解得y=2或3，所以(1,2),(1,3)为椭圆上的点。
椭圆曲线上的明文嵌入。
E：y^2≡x^3+bx+c(mod p)为椭圆曲线。
为了加密明文m（已表示为数字），把m作为x代入椭圆方程，但是因为只有1/2的机率，x^3+bx+c是模p二次剩余，有对应的y。这样的加密成功率是不能接受的，所以m需进行一定的处理，才能使m作为E上一点的X坐标值被嵌入椭圆。
Koblitz的方法是
取k，使（m+1)k<p
x=mk+j(0<=j<k)
对于j的不同取值计算x^3+bx+c是否为模p二次剩余，如果是则以点(x,y)嵌入椭圆曲线成功，如果所有的取值都非模p二次剩余则嵌入失败，但这种可能性只有（1/2)^k。
恢复数据只需要做m=[x/k]，即使m等于x/k的整数部分。
ElGamal加密系统的椭圆曲线实现。
如果A要发消息给B
B选择一条椭圆曲线E(mod p)，并取其上的一点P，和一个随机数a，计算出Q=aP，把（E,P,Q)作为公钥发送给A，保留a为私钥。
A得到B的公钥后，把消息m表示为E上的一点x（可以用Koblitz方法），并取一随机数k，计算y1=kP，y2=x+kQ，把（y1，y2）发送给B。
B通过x=y2-ay1=x+kQ-akP=x+kaP-akP,解密消息。
整个系统的秘密在于P和Q的关系。因为y1和y2是分别通过P和Q计算出来了所以它们之间的关系是P和Q之间的关系的延续，k只是作为这种关系的掩盖，并在解密过程中被消去。
椭圆曲线算法的作用在于确保在不知道a的情况下没有可能通过P和Q计算出他们之间的关系。
在这个领域我可能的研究方向：
1）并非所有的椭圆曲线都适合用于加密，选取一条安全的椭圆曲线确保安全性的第一步，这方面有很多工作可以做。
2）椭圆曲线上的明文嵌入，Koblitz的方法虽然简洁明了，但效率不高，有改进的空间。
3）标量乘法效率优化。
参考的书：
Wade Trappe, Introduction to Cryptography with Coding Theory (SE),第三章 Basic Number Theroy和第十六章 Elliptic curves
