首页
社区
课程
招聘
从XP的序列号谈椭圆曲线签名算法
2004-6-4 08:50 12082

从XP的序列号谈椭圆曲线签名算法

2004-6-4 08:50
12082
  从Win95起,MS(注:即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”在搜索引擎找相关的资料来看吧,这里只简单介绍了M$的用法。 
所谓椭圆曲线是指这样一类曲线方程:
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。依此类推,密钥的q值,密钥的k值, 在现在的主流机器上大约都在十个小时左右就可以求出。 

PS:自从微软2003SERVER的源码被泄密后,网上就出现了真正意义上M$2003的KEY生成器。有意思的自己找出Q和K值,自己也写一个吧^_^

[培训]《安卓高级研修班(网课)》月薪三万计划

收藏
点赞4
打赏
分享
最新回复 (5)
雪    币: 253
活跃值: (27)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
呱叽呱叽 1 2004-6-4 09:03
2
0
虽然看过,不过还是顶一下:)
雪    币: 196
活跃值: (58)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
xyzliuin 2004-6-4 09:43
3
0
雪    币: 3241
活跃值: (339)
能力值: (RANK:20 )
在线值:
发帖
回帖
粉丝
blowfish 2004-6-4 12:14
4
0
转贴的就注明一下,不然别人会说闲话的。。。
雪    币: 225
活跃值: (115)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
风云剑 2004-6-4 16:35
5
0
PS:自从微软2003SERVER的源码被泄密后,网上就出现了真正意义上M$2003的KEY生成器。有意思的自己找出Q和K值,自己也写一个吧^_^

2003的源代码在哪儿?
雪    币: 203
活跃值: (71)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
lllaaa 2004-6-6 09:09
6
0
最初由 风云剑 发布
PS:自从微软2003SERVER的源码被泄密后,网上就出现了真正意义上M$2003的KEY生成器。有意思的自己找出Q和K值,自己也写一个吧^_^

2003的源代码在哪儿?


跟泄漏源代码一点关系也没有的。:D
游客
登录 | 注册 方可回帖
返回