扫一扫
分享文章到微信
扫一扫
关注官方公众号
至顶头条
从Windows95起,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高位在后的格式表示如下:
|
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的用法。
所谓椭圆曲线是指这样一类曲线方程:
|
在密码学里用的是它的两个特例,而Microsoft用的更是这两个特例中的特例:
|
当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中的式子:
|
通常情况下q可以是很大的值,因此sign应该也很大,但Microsoft 为了减少用户输入的cdkey的数量,把sign的值限死在55 bits,因此,自然也限定了q最多也不能超过56 bits。依此类推,由于k在一台赛扬ii 800的机器上只用6个小时就解出某组密钥的q值,最多时在一台雷鸟1g上用了28个小时才算出另一组密钥的k值,其他平均大约都在十个小时左右就可以求出。
如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。
现场直击|2021世界人工智能大会
直击5G创新地带,就在2021MWC上海
5G已至 转型当时——服务提供商如何把握转型的绝佳时机
寻找自己的Flag
华为开发者大会2020(Cloud)- 科技行者