Windows XP 算號原理
Windows XP 算號原理
從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”在搜索引擎找相關的資料來看吧，這裏只簡單介紹MS的用法。
所謂橢圓曲線是指這樣一類曲線方程：
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。依此類推，由於k 作者曾經在一台賽揚II 800的機器上只用6個小時就解出某組密鑰的q值，最多時在一台雷鳥1G上用了28個小時才算出另一組密鑰的k值， 其他平均大約都在十個小時左右就可以求出。
注：關於什麽-640-和-005-，其實沒什麽意思，例如當我裝xp打入序號爲FCKGW-RHQQ2-YXRKT-8TG6W-2B7Q8，我的産品號就是55274-640-0000356-23174，而我打入3H87P-VHQGD-M74M6-8MHMH-3JRB3時，我的産品號就變成了55274-643-6941852-23174，這證明了什麽?其實産品號的頭五個key，是****windows的版本，而接著的十個key，就是****你裝windows時輸入的序號，最後的五個key是****光碟的cd-code罷了.............所以，産品號不是-005-的 都未必不能啟動簡體中文專業版的..................
從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”在搜索引擎找相關的資料來看吧，這裏只簡單介紹MS的用法。
所謂橢圓曲線是指這樣一類曲線方程：
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。依此類推，由於k 作者曾經在一台賽揚II 800的機器上只用6個小時就解出某組密鑰的q值，最多時在一台雷鳥1G上用了28個小時才算出另一組密鑰的k值， 其他平均大約都在十個小時左右就可以求出。
注：關於什麽-640-和-005-，其實沒什麽意思，例如當我裝xp打入序號爲FCKGW-RHQQ2-YXRKT-8TG6W-2B7Q8，我的産品號就是55274-640-0000356-23174，而我打入3H87P-VHQGD-M74M6-8MHMH-3JRB3時，我的産品號就變成了55274-643-6941852-23174，這證明了什麽?其實産品號的頭五個key，是****windows的版本，而接著的十個key，就是****你裝windows時輸入的序號，最後的五個key是****光碟的cd-code罷了.............所以，産品號不是-005-的 都未必不能啟動簡體中文專業版的..................
