椭圆曲线加密算法(ECC)

TsinghuaCarelife假如平行线在很远很远的地方相交了？即平行线相交于无穷远点P∞：无穷远点与平常点◦与无穷远点相区别把原来平面上的点叫做平常点由此出现了射影坐标系射影平面坐标系是对普通平面直角坐标系的扩展：◦增加无穷远点P∞构造方法：◦对普通平面直角坐标系上的点A的坐标（x,y）做如下改造：令x=X/Z，y=Y/Z（Z≠0）；则A点可以表示为（X:Y:Z）。变成了有三个参量的坐标点，这就对平面上的点建立了一个射影平面坐标体系。一条椭圆曲线是在射影平面上满足方程：𝑦2𝑧+𝑎1𝑥𝑦𝑧+𝑎3𝑦𝑧2=𝑥3+𝑎2𝑥2𝑧+𝑎4𝑥𝑧2+𝑎6𝑧3−−Weierstrass方程的所有点的集合，且曲线上的每个点都是非奇异的椭圆曲线上有一个无穷远点O∞（0:1:0）（满足Weierstrass方程）椭圆曲线的形状不是椭圆的：设x=X/Z，y=Y/Z代入Weierstrass方程得到：𝑦2+𝑎1𝑥𝑦+𝑎3𝑦=𝑥3+𝑎2𝑥2+𝑎4𝑥+𝑎6◦上述方程加上无穷远点O∞构成了平面上的椭圆曲线椭圆曲线上的切线斜率◦𝑘=(3𝑥2+2𝑎2𝑥+𝑎4−𝑎1𝑦)/(2𝑦+𝑎1𝑥+𝑎3)运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点𝑅’，过𝑅’做y轴的平行线交于R。规定:◦𝑷+𝑸=𝑹前面所述的椭圆曲线是连续的，并不适合用于加密；必须把椭圆曲线变成离散的点有限域Fp上：◦有限域Fp中只有p（p为素数）个元素0,1,2……p-2,p-1；◦加法(a+b)法则：a+b≡c(modp)◦乘法(a×b)法则是：a×b≡c(modp)◦除法(a÷b)法则：a/b≡c(modp)◦单位元是1，零元是0将椭圆曲线定义到有限域Fp上就变成了离散的椭圆曲线将𝑦2=𝑥3+𝑎𝑥2+𝑏这条曲线定义在Fp上：◦选择两个满足下列条件的小于p(p为素数)的非负整数a、b4𝑎3+27𝑏2≠0𝑚𝑜𝑑𝑝◦则满足下列方程的所有点(x,y)，再加上无穷远点O∞构成一条椭圆曲线:𝑦2=𝑥3+𝑎𝑥2+𝑏(𝑚𝑜𝑑𝑝)◦其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)𝑦2=𝑥3+𝑥2+1𝑚𝑜𝑑23的图像：对于椭圆曲线上的某个点P，存在一个最小的数n，使得𝑛𝑃=𝑂∞，那么n就是P点的阶。加密/解密签名&生成软件序列号公开密钥算法总是要基于一个数学上的难题。◦RSA：给定两个素数p、q很容易相乘得到n，而对n进行因式分解却相对困难。那椭圆曲线上有什么难题呢？◦考虑K=kG，其中K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数。◦给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。◦点G：基点（basepoint）◦k（kn，n为基点G的阶）：私有密钥（privatekey）◦K：公有密钥（publickey)①用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。②用户A选择一个私有密钥k，并生成公开密钥𝐾=𝑘𝐺。③用户A将Ep(a,b)和点K，G传给用户B。④用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（rn）。⑤用户B计算点𝐶1=𝑀+𝑟𝐾；𝐶2=𝑟𝐺。⑥用户B将C1、C2传给用户A。⑦用户A接到信息后，计算𝐶1−𝑘𝐶2，结果就是点M。𝐶1−𝑘𝐶2=𝑀+𝑟𝐾−𝑘(𝑟𝐺)=𝑀+𝑟𝐾−𝑟(𝑟𝐺)=𝑀⑧再对点M进行解码就可以得到明文。上图是ECC加密/解密的图示，从中可以看到如果有一个偷窥者H，他只能看到Ep(a,b)、K、G、C1、C2而通过K、G求k或通过C2、G求r都是相对困难的。因此，H无法得到A、B间传送的明文信息。描述一条Fp上的椭圆曲线，常用到六个参量：T=(p,a,b,G,n,h)p、a、b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的整数部分参量值一般要求满足以下几个条件：◦p越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求◦𝑝≠𝑛×ℎ◦𝑝𝑡≠1(𝑚𝑜𝑑𝑛)，1≤𝑡20◦4𝑎3+27𝑏2≠0(𝑚𝑜𝑑𝑝)◦𝑛为素数◦ℎ≤4签名过程：①选择一条椭圆曲线Ep(a,b)，和基点G；②选择私有密钥k（kn，n为G的阶），利用基点G计算公开密钥𝐾=𝑘𝐺；③产生一个随机整数r（rn），计算点𝑅=𝑟𝐺；④计算SHA值，即𝐻𝑎𝑠ℎ=𝑆𝐻𝐴(𝑢𝑠𝑒𝑟𝑛𝑎𝑚𝑒,𝑥,𝑦)；⑤计算𝑠𝑛≡𝑟−𝐻𝑎𝑠ℎ∗𝑘(𝑚𝑜𝑑𝑛)；⑥将sn和Hash作为用户名username的序列号验证过程（软件中存有椭圆曲线Ep(a,b)，和基点G，公开密钥K）：①从用户输入的序列号中，提取sn以及Hash；②计算点𝑅≡𝑠𝑛∗𝐺+𝐻𝑎𝑠ℎ∗𝐾(𝑚𝑜𝑑𝑝)，如果sn、Hash正确，其值等于软件作者签名过程中点R(x,y)的坐标，因为𝑠𝑛≡𝑟−𝐻𝑎𝑠ℎ∗𝑘(𝑚𝑜𝑑𝑛)所以𝑠𝑛∗𝐺+𝐻𝑎𝑠ℎ∗𝐾=(𝑟−𝐻𝑎𝑠ℎ∗𝑘)∗𝐺+𝐻𝑎𝑠ℎ∗𝐾=𝑟𝐺–𝐻𝑎𝑠ℎ∗𝑘𝐺+𝐻𝑎𝑠ℎ∗𝐾=𝑟𝐺–𝐻𝑎𝑠ℎ∗𝐾+𝐻𝑎𝑠ℎ∗𝐾=𝑟𝐺=𝑅③计算𝐻=𝑆𝐻𝐴(𝑢𝑠𝑒𝑟𝑛𝑎𝑚𝑒,𝑥,𝑦)；④如果H=Hash则注册成功。如果H≠Hash，则注册失败。简单对比一下两个过程：◦作者签名用到了：椭圆曲线Ep(a,b)，基点G，私有密钥k，及随机数r。◦软件验证用到了：椭圆曲线Ep(a,b)，基点G，公开密钥K。Microsoft的产品安装Key为25位字符，这25位字符是如何得出来的呢？下面将一一叙述…Base24：这25个字符实际是114bits的数据用Base24进行UUCode后的结果，做为安装Key，这个Base必须绝对避免误认，所以Microsoft选择了以下这24个字符做为UUCode的Base：BCDFGHJKMPQRTVWXY2346789上页所述的114位数据按Intel高位在后的格式表示如下：◦Flag：不明标志，目前所见的各类Key中这一位总是为0。◦Serial：用户序列号，转成十进制表示为AAAABBBBBB，对应显示为：零售版：xxxxx-AAA-BBBBBBx-xxxxxOEM版：xxxxx-OEM-0AAAABx-BBBBB以上31bits总称为Data，是CDKey中的基本部分。◦Hash：Data经特定处理得到的结果,既ECC中的hash◦Sign：Hash值的椭圆曲线签名，既ECC中的snMicrosoft用了如下形式的椭圆曲线：𝑦2=𝑥3+𝑎𝑥2+𝑏然后按照上述的签名过程生成Sign,Hash：◦任选整数rq，求点𝑅(𝑟𝑥,𝑟𝑦)=𝑟∗𝐺；◦对Data,rx,ry共100个字节求SHA-1，取结果中的28位得Hash；◦求𝑆𝑖𝑔𝑛=𝑟−𝐻𝑎𝑠ℎ∗𝑘(𝑚𝑜𝑑𝑞)；◦把Flag,Data,Hash,Sign四个数组合后UUCode得25位CDKey。验证CDKey时：◦把25位CDKey先UUDecode再拆分后得到Data、Hash、Sign；◦求点𝑅(𝑟𝑥,𝑟𝑦)=𝑆𝑖𝑔𝑛∗𝐺+𝐻𝑎𝑠ℎ∗𝐾(𝑚𝑜𝑑𝑝)；◦将Data,rx,ry共100个字节求SHA-1，取结果中的28位得Hash*；◦如果𝐻𝑎𝑠ℎ=𝐻𝑎𝑠ℎ∗，则该CDKey为有效Key。微软的序列号能不能被轻易破解呢？◦答案是肯定的–注册机！要破解CDKey的生成算法，只要求出k即可。微软公钥中，p是一个384bits的质数，求k的计算量为𝑂(2192)，但是…回顾𝑆𝑖𝑔𝑛=𝑟−𝐻𝑎𝑠ℎ∗𝑘(𝑚𝑜𝑑𝑝)，这里尽管p是个很大的数，但是Sign被限制死了在55bits，也就是q最大不超过56bits，而𝑘𝑞，所以计算k的计算量只要𝑂(228)≈𝑂(108.5)！优点◦安全性能更高160位ECC与1024位RSA、DSA有相同的安全强度◦处理速度更快在私钥的处理速度上，ECC远比RSA、DSA快得多◦带宽要求更低◦存储空间更小ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多缺点◦设计困难，实现复杂◦在序列号方面的安全性并没有想象中的完善