微软的CDKEY生成算法–椭圆曲线法

从Win95起,M$(编辑注:即[M$],下同) 的产品安装Key从原来的10位数字改
为25位字符,这一改动, 代表着M$告别了简单的校验和,从此投入了椭圆曲线
法的怀抱。从密码学的角度来看,这绝对是一个里程碑, 因为当时椭圆曲线法
仍在研究论证阶段,M$是第一个将之实用以商业产品的厂家。
那么在这25个字符里到底有什么呢?

1.Base24
这25个字符实际是114bits的数据用Base24进行UUCode后的结果,做为安装Key,
这个Base必须绝对避免误认, 所以M$选择了以下这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
在密码学里用的是它的两个特例,而M$用的更是这两个特例中的特例:
y^2 = x^3 + a*x + b ( mod p )
当a、b、p选定后,就可以确定一个椭圆曲线,再选择一个生成点 G(gx,gy),
于是,存在一个最小的整数q使得q*G=O,然后,再任意选择一个整数 k公开密钥
为:a,b,p,G(gx,gy),K(kx,ky)
私有密钥为:a,b,p,G(gx,gy),q,k
要对Data签名时:
A.先任意选择一个整数rB.将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,M$ 必须公开椭圆曲线签名算法中的
公开密钥,那么这个公开密钥放在 哪里呢?答案是在pidgen.dll里的BINK资源
里(其他产品如Office则被包在*.MSI),而且一共有两组,从目前已知的 Key
组合来看,第一组密钥是用以零售版本的,第二组则用于OEM版本。两个产品的Key
能否通用就在于对应的密钥 是否相同,比如中文版的[晕倒死] 2000的Pro/Srv/
AdvSrv的第二组密钥也是相同的,即一个P[晕倒死] 2000 Pro的 OEM版的Key,
可同时供 P[晕倒死] 2000 Srv/Adv的OEM版使用。

5.破解及其难度
要破解CDKey的生成算法,必须从M$ 公开的密钥中求出对应的私有密钥,即只要求
出q和k即可。从BINK中公开的 密钥来看,p 是一个384 bits的质数,看起来计算
量好象至少要O(2^168)才行,但M$设计中一个缺陷(?)使实际 工作量降低到只有
O(2^28)就可以了。
为什么相差这么远?
回头看看3.C中的式子: Sign = r – Hash * k ( mod q )
通常情况下q可以是很大的值,因此Sign应该也很大,但M$ 为了减少用户输入的
CDKey的数量,把Sign的值限死在 55 bits,因此,自然也限定了q最多也不能超过
56 bits。依此类推,由于k作者曾经在一台赛扬II 800的机器上只用6个小时就解出
某组密钥的q值,最多时在一台雷鸟1G上用了28个小时才 算出另一组密钥的k值,
其他平均大约都在十个小时左右就可以求出.

Your email is never shared.
Required fields are marked *