MS的cdkey的算法

NICDevil

Microsoft的25位CDKey里有什么？\r\nAuthor: Bug Fix\r\nDate: 2002-2-7 15:37:56\r\n\r\n\r\n    从Win98起，M$(编辑注：即Microsoft，下同) 的产品安装Key从原来的10位数字改为25位字符，这一改动，代表着M$告别了简单的校验和，从此投入了椭圆曲线法的怀抱。从密码学的角度来看，这绝对是一个里程碑，因为当时椭圆曲线法仍在研究论证阶段，M$是第一个将之实用以商业产品的厂家。 \r\n    那么在这25个字符里到底有什么呢？ \r\n\r\n    1.Base24 \r\n    这25个字符实际是114bits的数据用Base24进行UUCode后的结果，做为安装Key，这个Base必须绝对避免误认， \r\n所以M$选择了以下这24个字符做为UUCode的Base： \r\n    BCDFGHJKMPQRTVWXY2346789 \r\n    所以，如果你的安装Key 有这24个字符以外的字符的话，你完全可以把它丢到垃圾筒里去了━━不用试就知道它 \r\n根本通不过了。 \r\n\r\n    2.114 bits \r\n    UUDecode后得到的114位按Intel高位在后的格式表示如下： \r\n      [ X XXXXXXXX XXXXXXXX XXXXXXXXXXXXXXXXXX ] Total 114 Bits \r\n        | | | \\ 55 Bits Sign \r\n        | | \\ 28 Bits Hash \r\n        | \\ 30 Bits Serial \\ 31 Bits Data \r\n         \\ 1 Bits Flag / \r\n    Flag： 不明标志，目前所见的各类Key中这一位总是为0。 \r\n    Serial：用户序列号，转成十进制表示为AAAABBBBBB，对应显示为： \r\n            零售版：xxxxx-AAA-BBBBBBx-xxxxx \r\n            OEM版： xxxxx-OEM-0AAAABx-BBBBB \r\n    以上31bits总称为Data，是CDKey中的基本部分。 \r\n    Hash：Data经特定处理得到的结果，见后文。 \r\n    Sign：Hash值的椭圆曲线签名，见后文。 \r\n\r\n    3.椭圆曲线签名算法 \r\n    要说明椭圆曲线签名算法可不是一件容易的事，有兴趣的可以自己用“椭圆曲线”或是“elliptic curve”在搜索引擎 \r\n找相关的资料来看吧，这里只简单介绍M$的用法。 \r\n    所谓椭圆曲线是指这样一类曲线方程： \r\n    y^2 + a1*xy + a3*y = x^3 + a2*x^2 + a4*x + a6 \r\n    在密码学里用的是它的两个特例，而M$用的更是这两个特例中的特例： \r\n    y^2 = x^3 + a*x + b ( mod p ) \r\n    当a、b、p选定后，就可以确定一个椭圆曲线，再选择一个生成点 G(gx,gy)， \r\n于是，存在一个最小的整数q使得q*G=O，然后，再任意选择一个整数 k<q，求出点 \r\nK(kx,ky)=k*G，这样椭圆曲线签名算法的Key就全生成了： \r\n    公开密钥为：a,b,p,G(gx,gy),K(kx,ky) \r\n    私有密钥为：a,b,p,G(gx,gy),q,k \r\n    要对Data签名时： \r\n    A.先任意选择一个整数r<q，求点R(rx,ry)=r*G； \r\n    B.将Data、rx、ry共100个字节求SHA-1，取结果中的28位得到Hash； \r\n    C.求Sign = r - Hash * k ( mod q )； \r\n    D.把Data、Hash、Sign三个数组合后UUCode得到25位CDKey。 \r\n    验证CDKey时： \r\n    A.把25位CDKey先UUDecode再拆分后提到Data、Hash、Sign； \r\n    B.求点R( rx, ry ) = Sing * G + Hash * K ( mod p )； \r\n    C.将Data、rx、ry共100个字节求SHA-1，取结果中的28位得到Hash\'； \r\n    D.如果Hash = Hash\'，则该CDKey为有效Key。 \r\n\r\n    4.BINK \r\n    从前面的说明可以看出，为了验证CDKey，M$ 必须公开椭圆曲线签名算法中的公开密钥，那么这个公开密钥放在 \r\n哪里呢？答案是在pidgen.dll里的BINK资源里（其他产品如Office则被包在*.MSI），而且一共有两组，从目前已知的 \r\nKey组合来看，第一组密钥是用以零售版本的，第二组则用于OEM版本。两个产品的Key能否通用就在于对应的密钥 \r\n是否相同，比如中文版的Windows 2000的Pro/Srv/AdvSrv的第二组密钥也是相同的，即一个PWindows 2000 Pro的 \r\nOEM版的Key，可同时供 PWindows 2000 Srv/Adv的OEM版使用。 \r\n\r\n    5.破解及其难度 \r\n    要破解CDKey的生成算法，必须从M$ 公开的密钥中求出对应的私有密钥，即只要求出q和k即可。从BINK中公开的 \r\n密钥来看，p 是一个384 bits的质数，看起来计算量好象至少要O(2^16才行，但M$设计中一个缺陷（？）使实际 \r\n工作量降低到只有O(2^2就可以了。 \r\n    为什么相差这么远？ \r\n    回头看看3.C中的式子： Sign = r - Hash * k ( mod q ) \r\n    通常情况下q可以是很大的值，因此Sign应该也很大，但M$ 为了减少用户输入的CDKey的数量，把Sign的值限死在 \r\n55 bits，因此，自然也限定了q最多也不能超过56 bits。依此类推，由于k<q，所以k也不能超过56 bits，也就是说 \r\n我们面对的只是两个最多2^56的数据而已，用目前最普通的算法也只有O(2^2的工作量。 \r\n    作者曾经在一台赛扬II 800的机器上只用6个小时就解出某组密钥的q值，最多时在一台雷鸟1G上用了28个小时才 \r\n算出另一组密钥的k值， 其他平均大约都在十个小时左右就可以求出。 \r\n\r\n    6.实际例子 \r\n> mskshow CCC64-69Q48-Y3KWW-8V9GV-TVKRM \r\nKey CCC64-69Q48-Y3KWW-8V9GV-TVKRM is for P-WinXP_Pro, Sign is OK. \r\nFlag = 0, Serial = 005-080936, Hash = 5AA62EB, Sign = ED6AA259. \r\n  This key is for Windows XP Pro, Simplified chinese OEM/MSDN, serial is xxxxx-005-080936x-xxxxx \r\n\r\n> mskshow GJ27Y-XHH2X-GRR3G-Q3WVJ-H9P33 \r\nKey GJ27Y-XHH2X-GRR3G-Q3WVJ-H9P33 is for E-WinXP_Pro-2, Sign is OK. \r\nFlag = 0, Serial = OEM-006400-00001, Hash = 2177C11, Sign = 79B54F13. \r\n  This key is for Windows XP Pro, English Corporate Select Editions, serial is xxxxx-OEM-006400x-00001 \r\n\r\n> mskshow BCC64-69Q48-Y3KWW-8V9GV-TVKRM \r\nKey BCC64-69Q48-Y3KWW-8V9GV-TVKRM is for Unknow Product, Sign is not check \r\nFlag = 0, Serial = 005-080936, Hash = 5AA62EB, Sign = 564E8259. \r\n  This key is for some product I don\'t know, serial is xxxxx-005-080936x-xxxxx \r\n\r\n> mskshow ACC64-69Q48-Y3KWW-8V9GV-TVKRM \r\nInvaild key: ACC64-69Q48-Y3KWW-8V9GV-TVKRM. \r\n  This key is not a vaild M$ CD key.

wdh007

牛，版主怎么知道的？