新版算號器技術原理

[psac]

新版算號器技術原理--龍捲風轉發
我正在寫微軟序列號產生和驗證方面的論文,恰好新版算號器的出現,大家對新版算號器的高效和準確感到吃驚,為此,我和試著大家分析一

下新版算號器的技術原理!

1.產品ID(ProductID)
　　產品ID是由五組十進制數組成，如下：
AAAAA-BBB-CCCCCCC-DDEEE
　　如果你用「ProductID」搜索註冊表，你會發現一個與你安裝的軟體有關的產品ID。在Windows的控制台裡的系統裡，你可以找到Windows操作系統的產品ID。

每組數位所代表的意義如下表：
數位 | 意義
--------+-------------------------------------------------
AAAAA | 產品編號，例:55661為windows pro版 55660為HOME版
BBB | 初級產品序列號的最高有效三位數位
| (見下文)
CCCCCCC | 初級產品序列號的最低有效六位數位以及
| 校驗數位的和 (見下文)
DD | 用來驗證產品序列號的公開密匙索引.例:PRO版為22,VLK版為23
EEE | 隨機值(用於電話啟動時,產生不同的安裝ID)
在上面的CCCCCCC部分中，由一個校驗數位和六個數位組成。校驗數位是這樣計算得到的：將所有數位相加，包含一個檢驗數位，可以被七整除。

例:初級產品序列號的最低有效六位數位是728439
7 + 2 + 8 + 4 + 3 + 9 = 33
所以檢驗數位為2，因為
7 + 2 + 8 + 4 + 3 + 9 + 2 = 33 + 2 = 35
所得到的結果35可被七整除。所以產品ID中的CCCCCCC部分的結果為7284392。


2、產品序列號組成
這25位的序列號，是用來區分每份微軟產品的產品序列號。產品序列號由五組被「-」分隔開，由字母數位混合編製的字元串組成，每組字元串是由五個字元串組成。如下：

FFFFF-GGGGG-HHHHH-JJJJJ-KKKKK

每個字元是取自於以下24個字母及數位之中的一個：
B C E F G H J K M P Q R T V W X Y 2 3 4 6 7 8 9
採用這24個字元的原因是為了避免混淆相似的字母和數位，如I和1，O和0等，減少產生不必要的麻煩。
這25個字元的產品序列號是由長度為114bits用二進製表示的產品序列號用Base-24進行編碼得到的。114bits的二進制產品序列號按高位在後排列，各bit定義如下：

[ 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：產品ID的縮寫，轉成十進製表示為AAAABBBBBB，對應顯示為：
零售版：xxxxx-AAA-BBBBBBx-xxxxx
OEM版： xxxxx-OEM-0AAAABx-BBBBB
以上31bits總稱為Data，是產品序列號中的基本部分。
Hash：Data經特定處理得到的結果，見後文。
Sign：Hash值的橢圓曲線簽名，見後文。

3、橢圓曲線簽名算法
所謂的橢圓曲線是指這樣一類曲線方程：
Y2 + a1XY + a3Y = X3 + a2X2 + a4X + a6
在密碼學裡用的是它的兩個特例，而微軟公司用的更是特例中的特例：
Y2　= X3 + aX +b (mod p)
當a、b、p選定後，就可以確定一個橢圓曲線，再選擇一個產生點G(gx,gy)，於是，存在一個最小的整數q使得q×G=0，然後，再任意選擇一個整數k＜q，求出點K(kx,ky)=k×G，這樣橢圓曲線簽名算法的Key就全產生了：
公開密鑰為：a,b,p, G(gx,gy), K(kx,ky)
私有密鑰為：q,k

要對Data簽名時：
(1).先任意選擇一個整數r＜q，求點R(rx,ry)=r×G；
(2).將Data、rx、ry進行SHA-1(4)運算，取結果中的28位得到Hash；
(3).求Sign = r–Hash×k (mod q)；
(4).把Data、Hash、Sign三個數組合編碼後得到25位的產品序列號。

驗證產品序列號時：
(1).把25位產品序列號譯碼後，拆分為Data、Hash、Sign；
(2).求點R(rx,ry)＝Sign×G + Hash×K（mod p）;
(3). 將Data、rx、ry進行SHA-1運算，取結果中的28位得到Hash』；
(4).如果Hash＝Hash』，則該產品序列號為有效的。

4. 公開密鑰
從前文可以看出，為了驗證產品序列號，微軟公司必須公開橢圓曲線簽名算法中的公開密鑰。我們可以從Windows XP安裝光碟中的檔案pidgen.dll的BINK資源裡找到（其他產品如Office則被包在*.msi裡）。而且一共有兩組。從目前已知的Key組合來看，第一組公開密鑰是用以零售版本的，第二組公開密鑰則用於OEM版本。兩個產品的Key能否通用就在於對應的公開密鑰是否相同，譬如中文版的Windows 2000的Pro/Srv/AdvSrv的第二組密鑰也是相同的，即一個中文Windows 2000 Pro的OEM版的Key，可同時供 中文Windows 2000 Srv/Adv的OEM版使用。
　　
5.破解及其難度
要破解產品序列號產生算法，必須從微軟公司公開的密鑰中求出對應的私有密鑰，即只要求出q和k即可。從BINK中公開的密鑰來看，p 是一個384 bits的質數，看起來計算量好像至少要O(2168)才行，但微軟公司設計中存在一個嚴重缺陷，使實際工作量降低到只O(228)就可以了。為什麼相差這麼遠？回頭看看2.(3)中的式子：Sign = r - Hash * k ( mod q )通常情況下q可以是很大的值，因此Sign應該也很大，但微軟公司為了減少用戶輸入的產品序列號的數量，把Sign的值限死在55 bits，因此，自然也限定了q最多也不能超過56 bits。依此類推，由於k<q，所以k也不能超過56 bits，也就是說我們面對的只是兩個最多256的資料而已。把q和k求出來了，就可以根據上面所述的算法，編寫出微軟公司所有採用該技術產品的算號器！


結論:

我估計所有微軟公司產品的序列號產生算法是一樣的.只是公有密鑰和私有密鑰不同而已,只要我們求出私有密鑰q和k,要產生序列號,就容易得多了.新版算號器的作者就是把各個版本的私有密鑰q和k求出來了.

新版算號器的工作流程:
在新版算號器中輸入初級產品ID的範圍,就可以隨機確定產品ID.初級產品ID中的前三位,根據算號啟動成功經驗和統計正版序列號的結果,每個版本都有特定數位.例在PRO版中010,011啟動成功機率很高,在HOME版中005,006啟動機率很高.後7位中有一位是效驗位,其它6位隨機指定即可,所以只需輸入6位.接著程序會自動產生一個隨機數,也就是算法中的r.最後根據上面的算法,得出產品序列號.使用不同的隨機數,對同一個產品ID運算,所得到的序列號是不相同的!學過數學的朋友可以看出,這個算法的複雜度並不高,用現在的電腦,很快就可以算出來,這就是新版算號器速度驚人,準確率高的根本原因!

完美算號器!
關於算號啟動的問題,大家一直爭論不已,最主要就是XP的啟動問題,XP在裝了SP後是不可以啟動的了,原因就是微軟加了序列號檢測機制,也就是在啟動過程中,序列號本身也要發送到微軟的啟動服務器進行驗證.我估計驗證機制可能採用了這兩種方法的其中一個:第一:微軟有個序列號出廠資料庫.對於要啟動的系統所用的序列號沒有出廠記錄,就說明該序列號是由算號器產生的,不給予啟動.我估計這個方法可能性不大!第二:對序列號本身存在一個檢測機制!也就是說,算號器算出來的序列號,只有符合某一定規律的,才能夠啟動,而這個機制只有微軟公司掌握,破解了這個機制就有可能製作出可以算出真正正版的序列號的算號器,換一句話就是可以製作出裝了SPX都可以啟動的最完美的算號器!!!破解這個檢測機制的最大希望就是上面所說的r!採用特定的產品ID只有配合特定的r算出來的序列號,才是正版的序列號!要破解這個檢測機制,方法就是收集大量的正版序列號,分析出產品ID和r的關係,就可以製作出最完美的算號器!所以我估計最完美的算號器,將在不久的將來面世!我希望這個完美算號器在我們龍捲風誕生!!

其實算號器的編寫並不難的,只要求出各個版本的私有密鑰q和k(這需要一點時間),利用上面的算法就可以製作出NIN1的算號器,這需要一定的數學知識和一定的編程功力!而我不怎麼會編程.各位龍捲風的朋友一起努力製作出最完美的NIN1算號器吧!不要老是讓老外走在我們前面.
本人很奇怪,關於算號原理的文章,網上一早就有了,但是剛出來的算號器,效率奇低,不知道它是採用什麼算法的.而新版算號器直到最近一段時間才放出來.對本文有興趣及一定見解的朋友請回帖留下你的聯繫方式,歡迎大家一起探討.本人水平有限,如有錯漏之外,敬請指出及原諒!

Dr Arab

[hwj_c]

看不太懂耶！程度太低了！

雖然我的數學能力不好，但我看的出這代表很快就會有"終極完美版"的
序號產生器問世，貧苦的孩子們！咱們有福囉~~~~~

[psac]

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值，其他平均大約都在十個小時左右就可以求出。