胡歌回应霍建华林心如:XP序列号与椭圆曲线签名算法

从Win95起，即Microsoft的产品安装Key从原来的10位数字改为25位字符，这一改动，代表着MS告别了简单的校验和，从此投入了椭圆曲线法的怀抱。从密码学的角度来看，这绝对是一个里程碑，    因为当时椭圆曲线法仍在研究论证阶段，MS是第一个将之实用以商业产品的厂家。那么在这25个字符里到底有什么呢？    
   　　1.Base24    
   　　这25个字符实际是114bits的数据用Base24进行UUCode后的结果，做为安装Key，这个Base必须绝对避免误认，所以MS选择了以下这24个字符做为UUCode的Base：BCDFGHJKMPQRTVWXY2346789    
   所以，如果你的安装Key     有这24个字符以外的字符的话，你完全可以把它丢到垃圾筒里去了━━不用试就知道它根本通不过了。    
   　　2.114     bits    
   　　UUDecode后得到的114位按Intel高位在后的格式表示如下：    
   　　[     X     XXXXXXXX     XXXXXXXX     XXXXXXXXXXXXXXXXXX     ]     Total     114     Bits    
   　　|     |     |     \\     55     Bits     Sign    
   　　|     |     \\     28     Bits     Hash    
   　　|     \\     30     Bits     Serial     \\     31     Bits     Data    
   　　\\     1     Bits     Flag     /    
   　　Flag：     不明标志，目前所见的各类Key中这一位总是为0。    
   　　Serial：用户序列号，转成十进制表示为AAAABBBBBB，对应显示为：    
   　　零售版：xxxxx-AAA-BBBBBBx-xxxxx    
   　　OEM版：     xxxxx-OEM-0AAAABx-BBBBB    
   　　以上31bits总称为Data，是CDKey中的基本部分。    
   　　Hash：Data经特定处理得到的结果，见后文。    
   　　Sign：Hash值的椭圆曲线签名，见后文。    
   　　3.椭圆曲线签名算法    
   　　要说明椭圆曲线签名算法可不是一件容易的事，有兴趣的可以自己用“椭圆曲线”或是“elliptic     curve”在搜索引擎找相关的资料来看吧，这里只简单介绍MS的用法。    
   　　所谓椭圆曲线是指这样一类曲线方程：    
   　　y^2     +     a1*xy     +     a3*y     =     x^3     +     a2*x^2     +     a4*x     +     a6    
   　　在密码学里用的是它的两个特例，而MS用的更是这两个特例中的特例：    
   　　y^2     =     x^3     +     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。    
    
   　　4.BINK    
   　　从前面的说明可以看出，为了验证CDKey，MS    必须公开椭圆曲线签名算法中的公开密钥，那么这个公开密钥放在哪里呢？答案是在pidgen.dll里的BINK资源里（其他产品如Office则被包在*.MSI），而且一共有两组，从目前已知的Key组合来看，第一组密钥是用以零售版本的，第二组则用于OEM版本。两个产品的Key能否通用就在于对应的密钥是否相同，比如中文版的Windows    2000的Pro/Srv/AdvSrv的第二组密钥也是相同的，即一个PWindows     2000    Pro的OEM版的Key，可同时供     PWindows     2000     Srv/Adv的OEM版使用。    
   　　5.破解及其难度    
   　　要破解CDKey的生成算法，必须从MS    公开的密钥中求出对应的私有密钥，即只要求出q和k即可。从BINK中公开的密钥来看，p     是一个384    bits的质数，看起来计算量好象至少要O(2^168)才行，但MS设计中一个缺陷（？）使实际工作量降低到只有O(2^28)就可以了。    
   　　为什么相差这么远？    
   　　回头看看3.C中的式子：     Sign     =     r     -     Hash     *     k     (     mod     q     )    
   　　通常情况下q可以是很大的值，因此Sign应该也很大，但MS    为了减少用户输入的CDKey的数量，把Sign的值限死在55     bits，因此，自然也限定了q最多也不能超过56    bits。依此类推，由于k     　　作者曾经在一台赛扬II    800的机器上只用6个小时就解出某组密钥的q值，最多时在一台雷鸟1G上用了28个小时才算出另一组密钥的k值，    其他平均大约都在十个小时左右就可以求出。    
    
  注：关于什么-640-和-005-，其实没什么意思，例如当我装xp打入序号为FCKGW-RHQQ2-YXRKT-8TG6W-2B7Q8，我的产品号就是55274-640-0000356-23174，而我打入3H87P-VHQGD-M74M6-8MHMH-3JRB3时，我的产品号就变成了55274-643-6941852-23174，这证明了什么?其实产品号的头五个key，是代表windows的版本，而接着的十个key，就是代表你装windows时输入的序号，最后的五个key是代表光盘的cd-code罢了.............所以，产品号不是-005-的都未必不能激活简体中文专业版的..................