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

1、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

2、有这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.椭圆曲线签名算法要说明椭圆曲线签名

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就全生成了：公开密

4、钥为：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位得到

5、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，处于同一

6、条直线上，那么他们的和等于零元，即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=(3

7、x2+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)故

8、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；提醒大家注意一点，以前提供的图像可能会给大家产生一种错觉，即椭

9、圆曲线是关于x轴对称的。事实上，椭圆曲线并不一定关于x轴对称。如下图的y2-xy=x3+1五、密码学中的椭圆曲线现在基本上对椭圆曲线有了初步的认识。大家注意，前面的椭圆曲线是连续的，并不适合用于加密；所以，必须把椭圆曲线变成离散的点。让我们想一想，为什么椭圆曲线为什么连续?是因为椭圆曲线上点的坐标，是实数的(也就是说前面讲到的椭圆曲线是定义在实数域上的)，实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上(顾名思义，有限域是一种只有由有限个元素组成的域)。域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自

10、己得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。下面，我们给出一个有限域Fp，这个域只有有限个元素。Fp中只有p(p为素数)个元素0,1,2p-2,p-1；Fp的加法(a+b)法则是a+bc(mod p)；即，(a+c)÷p的余数和c÷p的余数相同。Fp的乘法(a×b)法则是a×bc(mod p)；Fp的除法(a÷b)法则是a/bc(mod p)；即a×b-1c(mod p)；(b-1也是一个0到p-1之间的整数，但满足b×b-11(mod p)；具体求法可以参考初等数论，或我的另一篇文章)。Fp的单位

11、元是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)的图像是不是觉得不可思议?椭圆曲线，怎么变成了这般模样，成了一个一个离散的点?椭圆曲线在不同的数域中会呈现出不同

12、的样子，但其本质仍是一条椭圆曲线。举一个不太恰当的例子，好比是水，在常温下，是液体；到了零下，水就变成冰，成了固体；而温度上升到一百度，水又变成了水蒸气。但其本质仍是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(mo