Microsoft的25位CDKey里有什么

从win95起，microsoft的产品安装key从原来的10位数字改为25位字符，这一改动，代表着microsoft告别了简单的校验和，从此投入了椭圆曲线法的怀抱。从密码学的角度来看，这绝对是一个里程碑，因为当时椭圆曲线法仍在研究论证阶段，microsoft是第一个将之实用以商业产品的厂家。那么在这25个字符里到底有什么呢？
　 1.base24
　 这25个字符实际是114bits的数据用base24进行uucode后的结果，做为安装key，这个base必须绝对避免误认，所以microsoft选择了以下这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”在搜索引擎找相关的资料来看吧，这里只简单介绍microsoft的用法。
　 所谓椭圆曲线是指这样一类曲线方程：
　 y^2 + a1*xy + a3*y = x^3 + a2*x^2 + a4*x + a6
　 在密码学里用的是它的两个特例，而microsoft用的更是这两个特例中的特例：
　 y^2 = x^3 + a*x + b ( mod p )
　 当a、b、p选定后，就可以确定一个椭圆曲线，再选择一个生成点 g(gx，gy)，
于是，存在一个最小的整数q使得q*g=o，然后，再任意选择一个整数 kk(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，microsoft 必须公开椭圆曲线签名算法中的公开密钥，那么这个公开密钥放在哪里呢？答案是在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的生成算法，必须从microsoft 公开的密钥中求出对应的私有密钥，即只要求出q和k即可。从bink中公开的密钥来看，p 是一个384 bits的质数，看起来计算量好象至少要o(2^168)才行，但microsoft设计中一个缺陷（？）使实际工作量降低到只有o(2^28)就可以了。
　 为什么相差这么远？
　 回头看看3.c中的式子： sign = r - hash * k ( mod q )
　 通常情况下q可以是很大的值，因此sign应该也很大，但microsoft 为了减少用户输入的cdkey的数量，把sign的值限死在55 bits，因此，自然也限定了q最多也不能超过56 bits。依此类推，由于k在一台赛扬ii 800的机器上只用6个小时就解出某组密钥的q值，最多时在一台雷鸟1g上用了28个小时才算出另一组密钥的k值，其他平均大约都在十个小时左右就可以求出。

先贴上再说,有空在再来研究