|
|
|||||||
| 論壇說明 | 標記討論區已讀 |
|
歡迎您來到『史萊姆論壇』 ^___^ 您目前正以訪客的身份瀏覽本論壇，訪客所擁有的權限將受到限制，您可以瀏覽本論壇大部份的版區與文章，但您將無法參與任何討論或是使用私人訊息與其他會員交流。若您希望擁有完整的使用權限，請註冊成為我們的一份子，註冊的程序十分簡單、快速，而且最重要的是－－註冊是完全免費的！ 請點擊這裡：『註冊成為我們的一份子！』 |
|
|
主題工具 | 顯示模式 |
2003-12-11, 07:46 PM
|
#1 |
|
榮譽會員
 
|
DSA算法的理論，實現，以及在破解中的套用
DSA算法的理論，實現，以及在破解中的套用
[第一部分： 理論篇] 0. 前言 我眼中的最有代表性的公匙密碼算法 ECC，RSA，DSA。 其中前兩種已經被國內眾多 Cracker界前輩高人詳細的解釋並實現，使我等初學者獲益匪淺，其中尤為具代表性 的兩篇如： ●ECC加密算法入門介紹 [作者：zmworm/CCG] ●RSA與大數運算 [作者：afanty] 更是使我受益良多。 唯獨DSA算法 由於各種原因鮮有相關文章 國內的共享軟體也很少有使用這種加密算 法進行註冊驗證的， 其實DSA算法有許多它自己獨特的地方 它比ECC算法更加便於理 解和實現， 比RSA產生密匙的速度快很多，且安全性與RSA不相上下 但是DSA的一個 重要特點是兩個素數(P,Q)公開，這樣，當使用別人的p和q時，即使不知道私鑰，你 也能驗證它們是否是隨機產生的，還是作了手腳。RSA算法卻作不到。 我用了一個禮拜時間四處搜集資料 其中包括套用密碼學一書中DSA算法章節 DSATool 中的說明文件 看學學院中DSA算法的簡單介紹 等諸多權威信息， 經過自己的整理， 翻譯，理解寫出本文，文中少有複雜的數論知識，重在套用和實踐，旨在起到一個拋 磚引玉的作用 希望這套算法被更多人接受，理解，並得到廣泛的套用。不足之處在所 難免 希望各位高人能不吝賜教加以指點 ：） // 為免譯文不準確 部分段落引用英文原文 英文好的朋友可以自行參考 1. General stuff / 一般資料 In 1991 the Digital Signature Algorithm(DSA) has become the Digital Signature Standard(DSS). DSA is a public-key signature scheme that uses a pair of transformations to generate and verify a digital value called signature. DSA has been developed by the US National Security Agency(NSA) and can -not- be used for encryption or key distribution. DSA is some variant of the ElGamal signature algorithm and, as defined in the standard, uses the Secure Hash Algorithm(SHA/SHA-1) as one-way hash function. // Digital Signature Algorithm (DSA)是Schnorr和ElGamal簽名算法的變種，被美國 NIST(美國國家標準局)作為數字簽名標準(DigitalSignature Standard)。同樣屬於 公匙密碼體系，並使用Secure Hash Algorithm(SHA/SHA-1)作為中間單向計算算法 2. Parameters / 參數 P = A prime number in range 512 to 1024 bits which must be a multiple of 64 P = 一個範圍在512至1024之間的素數 且必須為64的倍數 Q = A 160 bit prime factor of P-1 Q = P - 1的160bits的素因子 G = H^((P-1)/Q) mod P. H is any number < P-1 such that H^((P-1)/Q) mod P > 1 G = h^((p-1)/q) mod P，H 必須 < p - 1, h^((p-1)/q) mod p > 1 X = A number < Q X = 小於Q的一個數 Y = G^X mod P Parameters P, Q, G and Y are public where Y is the public key. X is the private key and must be kept secret! To obtain X from Y one needs to solve the Discrete Logarithm Problem which is virtually impossible for -properly- generated parameters of reasonable size. // 以上參數其中P, Q, G 以及 Y 為公匙， X為私匙必須保密！任何第三方用戶想要從 Y解密成X 都必須解決整數有限域離散對數難題 3. Signing a message (M) / 簽名部分 To sign M, carry through the following steps: // 若需要對M進行數字簽名 則需要進行下列運算： - Generate a -random- number K < Q. NEVER use same K twice or more to sign other messages! - 產生一個隨機數 K (K < Q),，永遠不要將同樣的K用於進行其他的簽名運算！ - Compute R = (G^K mod P) mod Q - 計算 R = (G^K mod P) mod Q - Compute S = (K^-1*(SHA(M) + X*R)) mod Q - 計算 S = (K^-1*(SHA(M) + X*R)) mod Q The number pair (R,S) is the signature of M. // R以及S 為這次對M的數字簽名結果 4. Verifying a signature (R,S) of M / 驗證部分 - Compute W = S^-1 mod Q - 計算 W = S^-1 mod Q - Compute U1 = (SHA(M) * W) mod Q - 計算 U1 = (SHA(M) * W) mod Q - Compute U2 = (R*W) mod Q - 計算 U2 = (R*W) mod Q - Compute V = ((G^U1 * Y^U2) mod P) mod Q - 計算 V = ((G^U1 * Y^U2) mod P) mod Q If V == R the signature is verified. // 若v = r，則認為簽名有效。 5. DSA的安全性 DSA主要依賴於整數有限域離散對數難題。素數 P 必須足夠大，且p-1至少包含一個大 素數因子以抵抗Pohlig & Hellman算法的攻擊。M 一般都應採用信息的HASH值(官方推 薦為SHA算法)。DSA的安全性主要依賴於p和g，若選取不當則簽名容易偽造，應保證g對 於p-1的大素數因子不可約。 個人觀點DSA的安全性要次於ECC 與RSA不相上下。但是有 一點， 就是DSA算法的驗證程序 R，S 是以明文形式出現的， 這點很容易被利用，在 第二篇中各位會體會到這一點。 6. Cracker眼中的DSA DSA算法鮮有被用於國產共享軟體的註冊驗證部分 即使在國外的共享軟體中也遠不如 RSA，Blowfish等算法套用廣泛。 DSA算法在破解時 關鍵的參數就是X 根據 Y = G^X mod P 只要知道 P，G，Y，Q 且能 分解出 X 就可以偽造R，S寫出KeyGen了。 [第二部分： 簽名篇] 介紹完理論之後 我們來實踐瞭解一下： 目標： pDriLl's Crypto KeygenMe #4 主要工具： C32Asm(感謝pll621/CCG 送給我Keyfile); Ollydbg1.09d; BigInt Calc Pro 1.2(感謝Stkman/CCG 送給我Keyfile) 等等.... 先脫殼：用CoolDumper找到OEP是407952 然後使用 ImportREC1.6f 修復IAT表。 用Ollydbg載入程序 下斷點 BPX GetDigItem 斷下後走到不遠處： 004012A6 . LEA EBX,DWORD PTR SS:[EBP-104] 004012AC . MOV DWORD PTR DS:[EBX],EAX 004012AE . POP EBX 004012AF . CMP DWORD PTR SS:[EBP-1D0],0 // 該不會連名字都不輸入吧 004012B6 . JNZ SHORT Dumped4W.004012DE 004012B8 . PUSH 0 004012BA . LEA EAX,DWORD PTR SS:[EBP-3C] 004012C0 . PUSH EAX 004012C1 . LEA EAX,DWORD PTR SS:[EBP-20] 004012C7 . PUSH EAX 004012C8 . LEA EAX,DWORD PTR SS:[EBP+8] 004012CE . MOV EAX,DWORD PTR DS:[EAX] 004012D0 . PUSH EAX 004012D1 . LEA EAX,DWORD PTR DS:[4017BD] 004012D7 . PUSH EAX 004012D8 .-JMP DWORD PTR DS:[40E9A4] ; user32.MessageBoxA 004012DE LEA EAX,DWORD PTR SS:[EBP-22C] 004012E4 . PUSH EAX 004012E5 . CALL Dumped4W.00401900 // 過了這個CALL， DB EAX 就看到： 0012F878 01 23 45 67 89 AB CD EF FE DC BA 98 76 54 32 10 #Eg壂惋?簶vT2 See... MD5的常量， 不知道為什麼 我一見到MD5就興奮 對這個算法很有感情 ：） MD5特點 － 單向不可逆 所以在這裡不多說了 主要介紹DSA。 004012EA . ADD ESP,4 004012ED . MOV CL,BYTE PTR DS:[40E9C6] // 取Key的第7位 004012F3 . MOV BYTE PTR DS:[40E940],CL 004012F9 . MOV DL,BYTE PTR DS:[40E9CD] // 取Key的第14位 004012FF . MOV BYTE PTR DS:[40E941],DL 00401305 . MOV AL,BYTE PTR DS:[40E9D4] // 取Key的第21位 //所以 Key 最少為21位， 重新輸入註冊信息， Name:LingDi Key:123456789012345678901 0040130A . MOV BYTE PTR DS:[40E942],AL 0040130F . MOV DWORD PTR SS:[EBP-48],Dumped4W.0040E>; ASCII "12FHCF-YEAH!!" 00401316 . MOV ECX,DWORD PTR SS:[EBP-104] 0040131C . PUSH ECX 0040131D . PUSH Dumped4W.0040D1C0 ; ASCII "%d" 00401322 . MOV EDX,DWORD PTR SS:[EBP-48] 00401325 . PUSH EDX 00401326 . CALL Dumped4W.00407900 // 將Key的位數連線到剛才取出的3個Key值後. 0040132B . ADD ESP,0C 0040132E . MOV DWORD PTR SS:[EBP-48],Dumped4W.0040E>; ASCII "FHCF-YEAH!!" 00401335 . PUSH Dumped4W.0040D1B4 ; ASCII "EGBE-YEAH!!" 0040133A . PUSH Dumped4W.0040D1B0 ; ASCII "%s" 0040133F . MOV EAX,DWORD PTR SS:[EBP-48] 00401342 . PUSH EAX 00401343 . CALL Dumped4W.00407900 // 連接 EGBE-YEAH!! // DB 40e940看到如下結果 0040E940 37 34 31 32 37 45 47 42 45 2D 59 45 41 48 21 21 74127EGBE-YEAH!! 0040E950 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 00401348 . ADD ESP,0C 0040134B . MOV CL,BYTE PTR DS:[40E945] 00401351 . ADD CL,1 00401354 . MOV BYTE PTR DS:[40E945],CL 0040135A . MOV DL,BYTE PTR DS:[40E946] 00401360 . ADD DL,1 00401363 . MOV BYTE PTR DS:[40E946],DL 00401369 . MOV AL,BYTE PTR DS:[40E947] 0040136E . ADD AL,1 00401370 . MOV BYTE PTR DS:[40E947],AL 00401375 . MOV CL,BYTE PTR DS:[40E948] 0040137B . ADD CL,1 0040137E . MOV BYTE PTR DS:[40E948],CL // 00401354 至 0040137E 只不過是分別取 EGBE的ASCII值 並加1 // 結果為 FHCF， 好像是個組織名 不過沒在0DayFTP上看到過這個組織的Relase 00401384 . MOV BYTE PTR DS:[40E950],0 0040138B . PUSH 10 0040138D . PUSH Dumped4W.0040E940 00401392 . LEA EDX,DWORD PTR SS:[EBP-22C] 00401398 . PUSH EDX // 啦啦啦∼ 又看到MD5的四個常量了 你猜接下來要幹嗎？ 00401399 . CALL Dumped4W.00401930 0040139E . ADD ESP,0C 004013A1 . LEA EAX,DWORD PTR SS:[EBP-22C] 004013A7 . PUSH EAX 004013A8 . LEA ECX,DWORD PTR SS:[EBP-F0] 004013AE . PUSH ECX 004013AF . CALL Dumped4W.004019E0 004013B4 . ADD ESP,8 004013B7 . MOV EDX,DWORD PTR SS:[EBP-1CC] 004013BD . PUSH EDX 004013BE . LEA EAX,DWORD PTR SS:[EBP-F0] 004013C4 . PUSH EAX // EAX中儲存"74127FHCF-YEAH!!"的MD5 Hash結果：AA6E429C590F8579E5D51EBAAE66643A 0012F9B4 AA 6E 42 9C 59 0F 85 79 E5 D5 1E BA AE 66 64 3A 猲B淵危逭 寒fd: 004013C5 . PUSH 10 004013C7 . CALL Dumped4W.004065C0 004013CC . ADD ESP,0C 004013CF . PUSH Dumped4W.0040D194 ; ASCII "Bn6EN1dDFrupNxw1Wk4WO5==" 004013D4 . MOV ECX,DWORD PTR SS:[EBP-FC] 004013DA . PUSH ECX 004013DB . CALL Dumped4W.00405E80 01CE2CA0 04 00 00 00 AC 2C CE 01 00 00 00 00 B9 63 E1 A4 ...??....筩幛 01CE2CB0 55 C3 71 93 BA 6B 31 74 75 43 E8 67 00 00 00 00 U胵摵k1tuC鑗.... 004013E0 . ADD ESP,8 004013E3 . MOV EDX,DWORD PTR SS:[EBP-1CC] 004013E9 . PUSH EDX 004013EA . MOV EAX,DWORD PTR SS:[EBP-FC] 004013F0 . PUSH EAX 004013F1 . CALL Dumped4W.004039C0 // 這個CALL用來比較Hash結果是否等於 67E8437574316BBA9371C355A4E163B9 004013F6 . ADD ESP,8 004013F9 . TEST EAX,EAX 004013FB . JE SHORT Dumped4W.00401423 開始我怎麼也弄不明白 Bn6EN1dDFrupNxw1Wk4WO5== 這個字串串是幹什麼用的，後來在學習一段 Delphi來源碼的時候才想起來 Base64 這個東西。上面一段程式碼的作用就是 對比 "74127FHCF-YEAH!!" 的MD5 Hash結果：AA6E429C590F8579E5D51EBAAE66643A 是否等於 "Bn6EN1dDFrupNxw1Wk4WO5==" 即 67E8437574316BBA9371C355A4E163B9， 不相等則提示 Hmmm.. you don't even pass the first threshold!! 我們來考慮一下如何過這第一關， 過關條件是： "Key的第7位 + Key的第14位 + Key的第21位 + Key的位數 + FHCF-YEAH!!" 這段字串串的MD5結果必須 等於67E8437574316BBA9371C355A4E163B9 這就要靠猜了 稍微有點Cracker頭腦的人 都會猜到註冊碼是 xxxxxx-xxxxxx-xxxxxx-xxxxxx 這種格式的 不然 就必須編程窮舉了。 相當於窮舉5位密碼的MD5值，窮舉的速度也不慢 如果條件設定得當，理論上3分鐘左右應該 就可以得到結果 我是屬於沒有Cracker頭腦的人 所以這種格式並不是我想到的 ：（ 驗證一下： MD5("---27FHCF-YEAH!!") = 67E8437574316BBA9371C355A4E163B9 驗證通過。 重新輸入註冊信息，進入下一階段： Name: LingDi Key: 123456-890123-567890-234567 00401448 . MOV EDI,Dumped4W.0040E9C0 ; ASCII "123456-890123-567890-234567" 0040144D . OR ECX,FFFFFFFF 00401450 . XOR EAX,EAX 00401452 . REPNE SCAS BYTE PTR ES:[EDI] 00401454 . NOT ECX 00401456 . ADD ECX,-1 00401459 . CMP DWORD PTR SS:[EBP-100],ECX 0040145F . JGE SHORT Dumped4W.004014D5 00401461 . CMP DWORD PTR SS:[EBP-100],6 00401468 . JNZ SHORT Dumped4W.00401479 0040146A . MOV EDX,DWORD PTR SS:[EBP-100] 00401470 . ADD EDX,1 00401473 . MOV DWORD PTR SS:[EBP-100],EDX 00401479 > CMP DWORD PTR SS:[EBP-100],0D 00401480 . JNZ SHORT Dumped4W.00401491 00401482 . MOV EAX,DWORD PTR SS:[EBP-100] 00401488 . ADD EAX,1 0040148B . MOV DWORD PTR SS:[EBP-100],EAX 00401491 > CMP DWORD PTR SS:[EBP-100],14 00401498 . JNZ SHORT Dumped4W.004014A9 0040149A . MOV ECX,DWORD PTR SS:[EBP-100] 004014A0 . ADD ECX,1 004014A3 . MOV DWORD PTR SS:[EBP-100],ECX 004014A9 > MOV EDX,DWORD PTR SS:[EBP-108] 004014AF . MOV EAX,DWORD PTR SS:[EBP-100] 004014B5 . MOV CL,BYTE PTR DS:[EAX+40E9C0] 004014BB . MOV BYTE PTR DS:[EDX+40E940],CL 004014C1 . MOV EDX,DWORD PTR SS:[EBP-108] 004014C7 . ADD EDX,1 004014CA . MOV DWORD PTR SS:[EBP-108],EDX 004014D0 .^JMP Dumped4W.00401439 //看結果就知道 以上是個循環 目地是去除Key中的 "-" 結果： 0040E940 31 32 33 34 35 36 38 39 30 31 32 33 35 36 37 38 1234568901235678 0040E950 39 30 32 33 34 35 36 37 00 00 00 00 00 00 00 00 90234567........ 004014F0 > MOV EDI,Dumped4W.0040E940 ; ASCII "123456890123567890234567" 004014F5 . OR ECX,FFFFFFFF 004014F8 . XOR EAX,EAX 004014FA . REPNE SCAS BYTE PTR ES:[EDI] 004014FC . NOT ECX 004014FE . ADD ECX,-1 00401501 . CMP DWORD PTR SS:[EBP-100],ECX 00401507 . JGE SHORT Dumped4W.0040157C 00401509 . MOV ECX,DWORD PTR SS:[EBP-100] 0040150F . MOVSX EDX,BYTE PTR DS:[ECX+40E940] 00401516 . CMP EDX,41 00401519 . JL SHORT Dumped4W.0040152D 0040151B . MOV EAX,DWORD PTR SS:[EBP-100] 00401521 . MOVSX ECX,BYTE PTR DS:[EAX+40E940] 00401528 . CMP ECX,46 0040152B . JLE SHORT Dumped4W.00401577 0040152D > MOV EDX,DWORD PTR SS:[EBP-100] 00401533 . MOVSX EAX,BYTE PTR DS:[EDX+40E940] 0040153A . CMP EAX,30 0040153D . JL SHORT Dumped4W.00401551 0040153F . MOV ECX,DWORD PTR SS:[EBP-100] 00401545 . MOVSX EDX,BYTE PTR DS:[ECX+40E940] 0040154C . CMP EDX,39 0040154F . JLE SHORT Dumped4W.00401577 00401551 > PUSH 0 00401553 . LEA EAX,DWORD PTR SS:[EBP-3C] 00401559 . PUSH EAX 0040155A . LEA EAX,DWORD PTR SS:[EBP-1C4] 00401560 . PUSH EAX 00401561 . LEA EAX,DWORD PTR SS:[EBP+8] 00401567 . MOV EAX,DWORD PTR DS:[EAX] 00401569 . PUSH EAX 0040156A . LEA EAX,DWORD PTR DS:[4017BD] 00401570 . PUSH EAX 00401571 .-JMP DWORD PTR DS:[40E9A4] ; user32.MessageBoxA // 得到了 Key 的有效範圍： 0~9 A~F 004015C1 . LEA ECX,DWORD PTR SS:[EBP-A4] 004015C7 . PUSH ECX 004015C8 . CALL Dumped4W.00402490 // 跟進這個CALL 會看到SHA算法的5個常量 // 00402490 /$ MOV EAX,DWORD PTR SS:[ESP+4] // 00402494 |. XOR ECX,ECX // 00402496 |. MOV DWORD PTR DS:[EAX],67452301 // 0040249C |. MOV DWORD PTR DS:[EAX+4],EFCDAB89 // 004024A3 |. MOV DWORD PTR DS:[EAX+8],98BADCFE // 004024AA |. MOV DWORD PTR DS:[EAX+C],10325476 // 004024B1 |. MOV DWORD PTR DS:[EAX+10],C3D2E1F0 // 004024B8 |. MOV DWORD PTR DS:[EAX+14],ECX // 004024BB |. MOV DWORD PTR DS:[EAX+18],ECX // 004024BE \. RETN 004015CD . ADD ESP,4 004015D0 . MOV EDX,DWORD PTR SS:[EBP-1D0] 004015D6 . PUSH EDX 004015D7 . PUSH Dumped4W.0040E8C0 ; ASCII "LingDi" 004015DC . LEA EAX,DWORD PTR SS:[EBP-A4] // 期待已久的用戶名入棧 004015E2 . PUSH EAX 004015E3 . CALL Dumped4W.004024C0 004015E8 . ADD ESP,0C 004015EB . LEA ECX,DWORD PTR SS:[EBP-A4] 004015F1 . PUSH ECX // SHA計算所需要的常量。 0012FA00 01 23 45 67 89 AB CD EF FE DC BA 98 76 54 32 10 #Eg壂惋?簶vT2 0012FA10 F0 E1 D2 C3 30 00 00 00 00 00 00 00 4C 69 6E 67 疳頤0.......Ling 004015F2 . LEA EDX,DWORD PTR SS:[EBP-120] 004015F8 . PUSH EDX 004015F9 . CALL Dumped4W.00402760 // SHA(UserName) 0012F984 9E 80 31 BA 2C 32 5B 7D E8 FA 59 34 69 BD 24 81 瀫1?2[}楮Y4i? 0012F994 E5 0A 63 0C 00 00 01 01 18 00 00 00 1B 00 00 00 ?c......... Hash結果： 9E8031BA2C325B7DE8FA593469BD2481E50A630C // 這裡有必要說一下， 我試了計算SHA160(Name)的值 並沒有得到這個結果， 根據DSA 的官方資料，這裡推薦為 SHA-0/SHA-1 所以我猜測上面使用的HASH算法是SHA-0，但由於我 手頭沒有計算SHA-0的工具，所以暫時無法驗證，本文的重點是DSA，所以這裡我們得到HASH 的結果就行了，計劃下一篇文章寫寫SHA算法，不過那是以後的事情了。 ：） 004015FE . ADD ESP,8 00401601 . MOV EAX,DWORD PTR SS:[EBP-1D4] 00401607 . MOV DWORD PTR DS:[EAX+220],40 00401611 . PUSH Dumped4W.0040D170 ; ASCII "rizMjllW3niYFDZJlEEI7vyix++QkBK7=" 00401616 . MOV ECX,DWORD PTR SS:[EBP-40] 00401619 . PUSH ECX 0040161A . CALL Dumped4W.00405E80 092F9320 06 00 00 00 2C 93 2F 09 00 00 00 00 BB 12 90 90 ...,?.....?悵 092F9330 EF C7 A2 FC EE 08 41 94 49 36 14 98 78 DE 56 59 鍇Ⅻ?A擨6榵轛Y 092F9340 8E CC 2C AE 00 00 00 00 00 00 00 00 00 00 00 00 幪,?........... // P = AE2CCC8E5956DE7898143649944108EEFCA2C7EF909012BB 0040161F . ADD ESP,8 00401622 . PUSH Dumped4W.0040D164 ; ASCII "p911BFFR=" 00401627 . MOV EDX,DWORD PTR SS:[EBP-44] 0040162A . PUSH EDX 0040162B . CALL Dumped4W.00405E80 092F9170 02 00 00 00 7C 91 2F 09 00 00 00 00 51 51 04 75 ...|?.....QQu 092F9180 DD A7 00 00 00 00 00 00 00 00 00 00 00 00 00 00 荮.............. // Q = A7DD75045151 00401630 . ADD ESP,8 00401633 . PUSH Dumped4W.0040D140 ; ASCII "jfwz34Lt7/VqvRrhYb4X+8H0A9XfEzEG=" 00401638 . MOV EAX,DWORD PTR SS:[EBP-F8] 0040163E . PUSH EAX 0040163F . CALL Dumped4W.00405E80 092FAE50 06 00 00 00 5C AE 2F 09 00 00 00 00 06 31 13 DF ...\?.....1 092FAE60 D5 03 F4 C1 FB 17 BE 61 E1 1A BD 6A F5 EF ED 82 ?裊?綼?絡躪韨 092FAE70 DF 33 FC 8D 00 00 00 00 00 00 00 00 00 00 00 00 ?鼚............ // G =8DFC33DF82EDEFF56ABD1AE161BE17FBC1F403D5DF133106 00401644 . ADD ESP,8 00401647 . PUSH Dumped4W.0040D11C ; ASCII "qg1kJK2T1pVDWjoJ+q/VNYYg03Ij7q85=" 0040164C . MOV ECX,DWORD PTR SS:[EBP-FC] 00401652 . PUSH ECX 00401653 . CALL Dumped4W.00405E80 092FACA0 06 00 00 00 AC AC 2F 09 00 00 00 00 39 AF EE 23 ...j/.....9# 092FACB0 72 D3 20 86 35 D5 AF FA 09 3A 5A 43 95 D6 93 AD r??寨?:ZC曋摥 092FACC0 24 64 0D AA 00 00 00 00 00 00 00 00 00 00 00 00 $d.?........... // Y = AA0D6424AD93D695435A3A09FAAFD5358620D37223EEAF39 00401658 . ADD ESP,8 0040165B . MOV EDX,DWORD PTR SS:[EBP-1CC] 00401661 . PUSH EDX 00401662 . LEA EAX,DWORD PTR SS:[EBP-120] 00401668 . PUSH EAX // 用戶名的Hash結果 0012F984 9E 80 31 BA 2C 32 5B 7D E8 FA 59 34 69 BD 24 81 瀫1?2[}楮Y4i? 0012F994 E5 0A 63 0C 00 00 01 01 18 00 00 00 1B 00 00 00 ?c......... // 至此 我們得到了DSA的四個公匙： P = AE2CCC8E5956DE7898143649944108EEFCA2C7EF909012BB G = 8DFC33DF82EDEFF56ABD1AE161BE17FBC1F403D5DF133106 Y = AA0D6424AD93D695435A3A09FAAFD5358620D37223EEAF39 Q = A7DD75045151 接下來輪到 BigInt Calc1.2 出場了，它可以很方便的使用陳述式輔助計算，方便速度快 最重要的是CCG成員編寫的 當然要大力推薦一下咯，具體用法參考說明文件，我就不多說了 根據 Y = G^X mod P 得到：X = 40A6C8A2464A891E99DDBFCFC967BAFD4BAFA67B3ECEDC43 根據 R = (G^K mod P) mod Q ，設K等於1，計算(G mod P) mod Q 得到： R = 4A2B8273F9AF 根據 S = (K^-1*(SHA(M) + X*R)) mod Q，設K等於1，計算((SHA(M) + X*R)) mod Q， 已知： SHA(M) = 9E8031BA2C325B7DE8FA593469BD2481E50A630C 即： S = (9E8031BA2C325B7DE8FA593469BD2481E50A630C + 12BB32F497704DE84B07A0E581B75D 3F00EAAFA1FB124DAD4E5F1BBEBCCD)) mod A7DD75045151 最終得到： S = 2FE47548E4AC 簽名算法分析完成， 給出兩組有效KEY，注意大小寫，另外任何一個有效的Name所對應的Key 都不是唯一的 原因在於 K 的值， 比如： Name：LingDi SN： 4A2B82-73F9AF-2FE475-48E4AC / 57410B-49E869-63014B-326892 Name：娃娃 SN： 4A2B82-73F9AF-2F3777-6CD9C8 通過上面的分析以及計算 想必各位已經瞭解了DSA算法的簽名程序 接下來我們仍然結合這個 KeygenMe來瞭解DSA算法的驗證程序。 [第三部分： 驗證篇] 仍然是剛才的KeygenMe， 上一篇只介紹了DSA算法的簽名實現步驟，下面讓我們通過偵錯器來看看 這個KeygenMe是如何驗證有效Key的，通過實踐來瞭解DSA算法的驗證程序以及計算方法。 我們以輸入有效Key Name：LingDi SN： 4A2B82-73F9AF-2FE475-48E4AC 為例 來分析運算程序： 00401669 . PUSH 14 0040166B . CALL Dumped4W.004065C0 00401670 . ADD ESP,0C 00401673 . MOV ECX,DWORD PTR SS:[EBP-E0] 00401679 . PUSH ECX 0040167A . MOV EDX,DWORD PTR SS:[EBP-E0] 00401680 . PUSH EDX 00401681 . MOV EAX,DWORD PTR SS:[EBP-E0] 00401687 . PUSH EAX // EAX = S 009B82B0 02 00 00 00 BC 82 9B 00 00 00 00 00 AC E4 48 75 ...紓?....鯨u 009B82C0 E4 2F 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ?.............. 00401688 . MOV ECX,DWORD PTR SS:[EBP-44] 0040168B . PUSH ECX // ECX = Q 009B9940 02 00 00 00 4C 99 9B 00 00 00 00 00 51 51 04 75 ...L櫅.....QQu 009B9950 DD A7 00 00 00 00 00 00 00 00 00 00 00 00 00 00 荮.............. 0040168C . MOV EDX,DWORD PTR SS:[EBP-E0] 00401692 . PUSH EDX 00401693 . CALL Dumped4W.00405530 // 以上程式碼計算 W = S^-1 mod Q 00401698 . ADD ESP,14 0040169B . MOV EAX,DWORD PTR SS:[EBP-124] 004016A1 . PUSH EAX 004016A2 . MOV ECX,DWORD PTR SS:[EBP-44] 004016A5 . PUSH ECX 004016A6 . MOV EDX,DWORD PTR SS:[EBP-44] 004016A9 . PUSH EDX 004016AA . MOV EAX,DWORD PTR SS:[EBP-E0] 004016B0 . PUSH EAX // EAX = W 004016B1 . MOV ECX,DWORD PTR SS:[EBP-E0] 004016B7 . PUSH ECX // ECX = Q 004016B8 . MOV EDX,DWORD PTR SS:[EBP-1CC] 004016BE . PUSH EDX // EDX ＝ SHA(M) 009D5090 05 00 00 00 9C 50 9D 00 00 00 00 00 0C 63 0A E5 ...滵?.....c. 009D50A0 81 24 BD 69 34 59 FA E8 7D 5B 32 2C BA 31 80 9E ?絠4Yf}[2,? 004016BF . CALL Dumped4W.00404E50 009D2090 02 00 00 00 9C 20 9D 00 00 00 00 00 6D E0 ED C4 ...??....m囗 009D20A0 83 61 00 00 00 00 00 00 00 00 00 00 00 00 00 00 惠.............. // 上面是用來計算 U1 = (SHA(M) * W) mod Q 004016C4 . ADD ESP,18 004016C7 . MOV EAX,DWORD PTR SS:[EBP-1C8] 004016CD . PUSH EAX 004016CE . MOV ECX,DWORD PTR SS:[EBP-44] 004016D1 . PUSH ECX 004016D2 . MOV EDX,DWORD PTR SS:[EBP-44] 004016D5 . PUSH EDX 004016D6 . MOV EAX,DWORD PTR SS:[EBP-E0] 004016DC . PUSH EAX // EAX = W 009D3090 02 00 00 00 9C 30 9D 00 00 00 00 00 9E 1F FE D8 ...??....?? 009D30A0 C9 8F 00 00 00 00 00 00 00 00 00 00 00 00 00 00 蓮.............. 004016DD . MOV ECX,DWORD PTR SS:[EBP-E0] 004016E3 . PUSH ECX // ECX = Q 004016E4 . MOV EDX,DWORD PTR SS:[EBP-DC] 004016EA . PUSH EDX // EDX = R 009D4090 02 00 00 00 9C 40 9D 00 00 00 00 00 AF F9 73 82 ...淍?....零 009D40A0 2B 4A 00 00 00 00 00 00 00 00 00 00 00 00 00 00 +J.............. 004016EB . CALL Dumped4W.00404E50 009D1090 02 00 00 00 9C 10 9D 00 00 00 00 00 14 B3 2F B6 ...??....? 009D10A0 54 6C 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Tl.............. // 上面的程式碼用來計算 U2 = (R*W) mod Q 004016F0 . ADD ESP,18 004016F3 . MOV EAX,DWORD PTR SS:[EBP-F4] 004016F9 . PUSH EAX 004016FA . MOV ECX,DWORD PTR SS:[EBP-40] 004016FD . PUSH ECX 004016FE . MOV EDX,DWORD PTR SS:[EBP-1C8] 00401704 . PUSH EDX 00401705 . MOV EAX,DWORD PTR SS:[EBP-FC] 0040170B . PUSH EAX // EAX = Y 009D6680 06 00 00 00 8C 66 9D 00 00 00 00 00 39 AF EE 23 ...巨集?....9# 009D6690 72 D3 20 86 35 D5 AF FA 09 3A 5A 43 95 D6 93 AD r??寨?:ZC曋摥 009D66A0 24 64 0D AA 00 00 00 00 00 00 00 00 00 00 00 00 $d.?........... 0040170C . MOV ECX,DWORD PTR SS:[EBP-124] 00401712 . PUSH ECX // ECX = U1 00401713 . MOV EDX,DWORD PTR SS:[EBP-F8] 00401719 . PUSH EDX // EDX = G 009D6830 06 00 00 00 3C 68 9D 00 00 00 00 00 06 31 13 DF ...<h?....1 009D6840 D5 03 F4 C1 FB 17 BE 61 E1 1A BD 6A F5 EF ED 82 ?裊?綼?絡躪韨 009D6850 DF 33 FC 8D 00 00 00 00 00 00 00 00 00 00 00 00 ?鼚............ 0040171A . CALL Dumped4W.00405490 // 計算 Vt = (G^U1 * Y^U2) mod P 0040171F . ADD ESP,18 00401722 . MOV EAX,DWORD PTR SS:[EBP-44] 00401725 . PUSH EAX // EAX = Q ; /Arg3 00401726 . MOV ECX,DWORD PTR SS:[EBP-44] ; | 00401729 . PUSH ECX ; |Arg2 0040172A . MOV EDX,DWORD PTR SS:[EBP-F4] ; | 00401730 . PUSH EDX // EDX = Vt ; |Arg1 00401731 . CALL Dumped4W.004044B0 ; \Dumped4W.004044B0 // 計算 V = Vt mod Q 00401736 . ADD ESP,0C 00401739 . MOV EAX,DWORD PTR SS:[EBP-DC] 0040173F . PUSH EAX // EAX = V 009D4090 02 00 00 00 9C 40 9D 00 00 00 00 00 AF F9 73 82 ...淍?....零 009D40A0 2B 4A 00 00 00 00 00 00 00 00 00 00 00 00 00 00 +J.............. 00401740 . MOV ECX,DWORD PTR SS:[EBP-F4] 00401746 . PUSH ECX // ECX = R 009D0090 02 00 00 00 9C 00 9D 00 00 00 00 00 AF F9 73 82 ...??....零 009D00A0 2B 4A 00 00 00 00 00 00 00 00 00 00 00 00 00 00 +J.............. 00401747 . CALL Dumped4W.004039C0 // 對比 V 是否等於 R 0040174C . ADD ESP,8 0040174F . TEST EAX,EAX 00401751 . JE SHORT Dumped4W.0040177B // 得到了 V， 則與R對比， 相等則驗證通過，不相等自然失敗咯∼ 至此，驗證部分的工作程序想必各位都瞭解了吧，這個KeygenMe就此退役了 真的非常 感謝pDriLi編寫了這個這麼出色的KeygenMe，結構清晰，程式碼緊湊 真是一個非常好的 例子。 ：） [第四部分： 套用篇] 實踐過後自然要知道怎麼用， 我這篇文章的目地就是希望這種算法能得到廣泛的使用 實際上DSA算法在IC卡 以及許多銀行卡中已經被得到了套用， 但是由於美國的密碼算法 出口限制 這種算法並沒有被個人廣泛使用 IMPORTANT FINAL NOTE: Please never forget that even the most secure cryptographic algorithm is worthless if you make mistakes in the implementation. So, if you don't know -exactly- what you're doing, better use some 3rd party sourcecodes made by people you trust and -never- change the recommended standard(s). // 上面一段是DSATools的作者 tE!/TMG 說的， 譯文： 請永遠不要忘記， 任何一種安全的加密算法若你在執行的時候出現了一些差錯 都可能導致 密文輕易被攻破， 所以若你並不確定你的程序要做什麼和在做什麼，或許使用一個第三方編寫 的來源碼或插件是個不錯的主意。 RSA算法依靠的是N夠大，使得你不能分解，無法得到 D，同RSA一樣 DSA算法若公匙過於簡單， 很容易讓人得到X， DSA中的X 價值相當於RSA中的D， 根據上面的實例各位不難看出， 得到了X 剩下事情就是寫KeyGen了。 DSA算法在 C/C++ ，Delphi， BC中都有第三方控件 有興趣的朋友可以自行搜尋一下 通過 來源碼 或許可以更好的理解DSA的程序和原理， 我在這裡就不貼出了， DSA有比RSA更快的 速度以及更多優秀的特性， 希望能得到大家妥善的套用。 [第五部分： 寫在後面的話] 必須要說明的是 我不是數論高材生 所以寫出來的東西也許只能得到皮毛， 無法深究內 在精華， 若文中有什麼錯誤 請各位高手不吝賜教，感激不盡 我將文中提到的KeygenMe，DSATools2 以及這篇文章的RTF版本等相關文件打包上傳在： http://wawa.winzheng.com/Release/DSA.cab 感興趣的朋友可以下回去看看。 計劃過幾天寫一個DSATools 實現X的分解 以及相關運算， 最近事情很多 要寫NFOMaker 還有忙活CCG的官方主頁... ... ThX Fly To： －＝ KanXue Stkman Ivanopulo SunBird pll621 Hoto 時空幻影 nzinzi ＝－ －＝ Hying DingBoy 小樓 Ajj heXer Amenesia ..... 所有說明 過我的朋友 僅以次文獻給CCG組織 希望它能蒸蒸日上！ 娃娃(LingDi) 屬於中國破解組織CCG CHiNA CrACKiNG GrOUp -= iPB =- -= BCG =- 2003年 8月 12日 |
|
送花文章: 3,
|
平板模式
