win7 算号器之密码学 椭圆曲线算法.doc

win7 算号器之密码学 椭圆曲线算法最近发现，为了验证cdkey，ms必须公开椭圆曲线签名算法中的公开密钥，那么这个公开密钥放在哪里呢?答案是在pidgen.dll里的bink资源里(其他产品如office则被包在*.msi),在advapi32.dll里有crpygenkey函数进行key的生成.vc+中调用.1.base24这25个字符实际是114bits的数据用base24进行uucode后的结果，做为安装key，这个base必须绝对避免误认，所以ms选择了以下这24个字符做为uucode的base：bcdfghjkmpqrtvwxy 2346789所以，如果你的安装key有这24个字符以外的字符的话，你完全可以把它丢到垃圾筒里去了不用试就知道它根本通不过了。2.114 bits uudecode后得到的114位按intel高位在后的格式表示如下：flag：不明标志，目前所见的各类key中这一位总是为0。serial：用户序列号，转成十进制表示为aaaabbbbbb，对应显示为：零售版：*xx-aaa-bbbbbbx-*xx oem版：*xx-oem-0aaaabx-bbbbb以上31bits总称为data，是cdkey中的基本部分。hash：data经特定处理得到的结果，见后文。sign：hash值的椭圆曲线签名，见后文。3.椭圆曲线签名算法要说明椭圆曲线签名算法可不是一件容易的事，有兴趣的可以自己用椭圆曲线或是elliptic curve在搜索引擎找相关的资料来看吧，这里只简单介绍ms的用法。所谓椭圆曲线是指这样一类曲线方程：y2+a1*xy+a3*y=x3+a2*x2+a4*x+a6在密码学里用的是它的两个特例，而ms用的更是这两个特例中的特例：y2=x3+a*x+b(mod p)当a、b、p选定后，就可以确定一个椭圆曲线，再选择一个生成点g(gx,gy)，于是，存在一个最小的整数q使得q*g=o，然后，再任意选择一个整数k k(kx,ky)=k*g，这样椭圆曲线签名算法的key就全生成了：公开密钥为：a,b,p,g(gx,gy),k(kx,ky)私有密钥为：a,b,p,g(gx,gy),q,k要对data签名时：a.先任意选择一个整数r b.将data、rx、ry共100个字节求sha-1，取结果中的28位得到hash；c.求sign=r-hash*k(mod q)；d.把data、hash、sign三个数组合后uucode得到25位cdkey。验证cdkey时：a.把25位cdkey先uudecode再拆分后提到data、hash、sign；b.求点r(rx,ry)=sing*g+hash*k(mod p)；c.将data、rx、ry共100个字节求sha-1，取结果中的28位得到hash；d.如果hash=hash，则该cdkey为有效key。-补充点数学常识-法则详解：这不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但具体的运算法则显然与普通加法不同。根据这个法则，可以知道椭圆曲线无穷远点o与椭圆曲线上一点p的连线交于p，过p作y轴的平行线交于p，所以有无穷远点o+p=p。这样，无穷远点o的作用与普通加法中零的作用相当(0+2=2)，我们把无穷远点o称为零元。同时我们把p称为p的负元(简称，负p；记作，-p)。根据这个法则，可以得到如下结论：如果椭圆曲线上的三个点a、b、c，处于同一条直线上，那么他们的和等于零元，即a+b+c=ok个相同的点p相加，我们记作kp。如下图：p+p+p=2p+p=3p。下面，我们利用p、q点的坐标(x1,y1)，(x2,y2)，求出r=p+q的坐标(x4,y4)。例4.1：求椭圆曲线方程y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常点p(x1,y1)，q(x2,y2)的和r(x4,y4)的坐标。解：(1)先求点-r(x3,y3)因为p,q,-r三点共线，故设共线方程为y=kx+b,其中若pq(p,q两点不重合)则直线斜率k=(y1-y2)/(x1-x2)若p=q(p,q两点重合)则直线为椭圆曲线的切线，故由例3.1可知：k=(3x2+2a2x+a4-a1y)/(2y+a1x+a3)因此p,q,-r三点的坐标值就是方程组：y2+a1xy+a3y=x3+a2x2+a4x+a6-1y=(kx+b)-2的解。将2，代入1有(kx+b)2+a1x(kx+b)+a3(kx+b)=x3+a2x2+a4x+a6-3对3化为一般方程，根据三次方程根与系数关系(当三次项系数为1时；-x1x2x3等于常数项系数，x1x2+x2x3+x3x1等于一次项系数，-(x1+x2+x3)等于二次项系数。)所以-(x1+x2+x3)=a2-ka1-k2 x3=k2+ka1+a2+x1+x2；-求出点-r的横坐标因为k=(y1-y3)/(x1-x3)故y3=y1-k(x1-x3)；-求出点-r的纵坐标(2)利用-r求r显然有x4=x3=k2+ka1+a2+x1+x2；-求出点r的横坐标而y3 y4为x=x4时方程y2+a1xy+a3y=x3+a2x2+a4x+a6的解化为一般方程y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0,根据二次方程根与系数关系得：-(a1x+a3)=y3+y4故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3)；-求出点r的纵坐标即：x4=k2+ka1+a2+x1+x2；y4=k(x1-x4)-y1-a1x4-a3；提醒大家注意一点，以前提供的图像可能会给大家产生一种错觉，即椭圆曲线是关于x轴对称的。事实上，椭圆曲线并不一定关于x轴对称。如下图的y2-xy=x3+1五、密码学中的椭圆曲线现在基本上对椭圆曲线有了初步的认识。大家注意，前面的椭圆曲线是连续的，并不适合用于加密；所以，必须把椭圆曲线变成离散的点。让我们想一想，为什么椭圆曲线为什么连续?是因为椭圆曲线上点的坐标，是实数的(也就是说前面讲到的椭圆曲线是定义在实数域上的)，实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上(顾名思义，有限域是一种只有由有限个元素组成的域)。域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自己得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。下面，我们给出一个有限域fp，这个域只有有限个元素。fp中只有p(p为素数)个元素0,1,2p-2,p-1；fp的加法(a+b)法则是a+bc(mod p)；即，(a+c)p的余数和cp的余数相同。fp的乘法(ab)法则是abc(mod p)；fp的除法(ab)法则是a/bc(mod p)；即ab-1c(mod p)；(b-1也是一个0到p-1之间的整数，但满足bb-11(mod p)；具体求法可以参考初等数论，或我的另一篇文章)。fp的单位元是1，零元是0。同时，并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线，也是最为简单的一类。下面我们就把y2=x3+ax+b这条曲线定义在fp上：选择两个满足下列条件的小于p(p为素数)的非负整数a、b 4a3+27b20(mod p)则满足下列方程的所有点(x,y)，再加上无穷远点o，构成一条椭圆曲线。y2=x3+ax+b(mod p)其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为ep(a,b)。我们看一下y2=x3+x+1(mod 23)的图像是不是觉得不可思议?椭圆曲线，怎么变成了这般模样，成了一个一个离散的点?椭圆曲线在不同的数域中会呈现出不同的样子，但其本质仍是一条椭圆曲线。举一个不太恰当的例子，好比是水，在常温下，是液体；到了零下，水就变成冰，成了固体；而温度上升到一百度，水又变成了水蒸气。但其本质仍是h2o。fp上的椭圆曲线同样有加法，但已经不能给以几何意义的解释。不过，加法法则和实数域上的差不多，请读者自行对比。1.无穷远点o是零元，有o+o=o，o+p=p 2.p(x,y)的负元是(x,-y)，有p+(-p)=o3.p(x1,y1),q(x2,y2)的和r(x3,y3)有如下关系：x3k2-x1-x2(mod p)y3k(x1-x3)-y1(mod p)其中若p=q则k=(3x2+a)/2y1若pq，则k=(y2-y1)/(x2-x1)例5.1已知e23(1,1)上两点p(3,10)，q(9,7)，求1)-p，2)p+q，3)2p。解1) p的值为(3,-10)2)k=(7-10)/(9-3)=-1/2，2的乘法逆元为12因为2*121(mod 23)k-1*12(