Microsoft的25位CDKey裡有什麼 從Win98起,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,然後,再任意選擇一個整數 k<q,求出點
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<q,求點R(rx,ry)=r*G;
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<q,所以k也不能超過56 bits,也就是說我們面對的只是兩個最多2^56的資料而已,用目前最普通的算法也只有O(2^28)的工作量。
以目前的電腦運算速度,在一台賽揚II 800的機器上只用6個小時就可以解出某組密鑰的q值,最多時在一台雷鳥1G上用了28個小時才算出另一組密鑰的k值,其他平均大約都在十個小時左右就可以求出。
|