密碼設計與檢核原理剖析

密碼設計與檢核原理剖析 密碼設計與檢核原理剖析

張東瀛

原載  
自動化科技  1996 年 12 月  p.62-67(上)
自動化科技  1997 年  1 月  p.54-59(下)

壹、前言

人類的社會，從組織型態看來，類似樹狀階層(hierarchical)結構。通常大群体中有小群体，小群体內又有小組合。一般人喜歡過群体生活，又希望保有相當的私密性。這種特性在城市居民的生活中特別顯著。基於區隔或保密的理由，多數人鍾愛透天厝，獨門獨戶，屋外又可建造圍牆，萬不得已，才住公寓。重門深鎖，外掛鐵窗，都是為了阻絕非法闖入或限制他人進出的防護措施。

個人電腦讓現代人具備第六個感知器，資訊傳播透過網路發展而無遠弗屆，活動範圍迅速擴大，其規模遠非傳統城市格局所能比擬。人類的知性生活因電腦而豐富，各行各業對電腦的依賴性也越來越高，因此電腦資訊的安全與維護便成為重要而嚴肅的課題。

一般人大都有使用自動櫃員機的經驗。提款卡插入後，機器會要求你輸入密碼，用以辨識身份。這種利用密碼檢核以過濾非法使用者的措施，常被用來作為系統安全防護的第一道關卡。類似的保護方式也可在 BBS 站，軟体安裝或使用時看到。

電腦系統內部，也有層層關卡，最常見的便是機密等級或使用權限的保護措施。假設你意外闖入某個電腦系統，發現一大堆看不懂的檔案，不必驚訝，因為這些檔案可能因為安全理由而上鎖，也就是經過檔案加密的手續。除非你持有密碼可將檔案還原或解密，否則仍是入寶山空手回的局面。

不論密碼檢核或檔案加密，都是專門技術，某些特殊的演算法更非三言兩語可以解釋清楚。密碼學即是研究此道的入門課程。密碼設定有許多種，常見的有單碼和複碼(以密碼機製造出來)，檔案加密的方法更是五花八門，令人嘆為觀止。本文僅針對基本的固定式密碼檢核及傳統檔案加密方法提出說明及程式設計實例。所附程式及演算法已用於商用軟体多年，並受國際著作權公約保護，僅供讀者參考。

貳、密碼檢核程式

   REM             ******************************************
   REM             *     CHarades.BAS Version 2.0           *
   REM             *     01-22-1986                         *
   REM             *     By Tony Chang                      *
   REM             *     06-22-1996                         *
   REM             *     Writing in Quick BASIC 4.5         *
   REM             *     Tony Knowledge Engineering Lab     *
   REM             ******************************************
   以上為版權宣告及程式設計相關資訊

   'EXIT Reminder  暫回DOS作業系統的檢知器。程式內因設有暫回DOS的功能
   因此利用&H4E位址來偵測是否已執行本程式。使用者按Esc時，將&H4E內函值設
   定為5，表示電腦已執行本程式
   COLOR 15， 1: DEF SEG = &H30: MS% = PEEK(&H4E): DEF SEG
   IF MS% = 5 THEN
      CLS : BEEP: PRINT
      PRINT "CHarades 2.0 already installed， type EXIT to return": END
   END IF
   程式開始執行時先檢查&H4E是否等於5，是的話，則提醒使用者打EXIT回本程式
   若否，則繼續下一步，定義變數
   A1$ = CHR$(68): A3$ = CHR$(97): A4$ = CHR$(109): A5$ = CHR$(101)
   A2$ = CHR$(114)
   這些變數用來定義密碼所需的字母，如果直接使用字串定義，很容易用PCTools
   等工具程式看出，所以先用字母的ASCII值來定義變數，再加以組合成密碼

   此一變數為音樂響鈴，可用PLAY指令發聲
   FATE1$ = "MB T180 O2 P2 P8 L8 GGG L2 E-"

   利用剛才定義的變數設定密碼PK1$，至於PK2$可作為備用鑰匙或第二個密碼，
   必要時也可再增加幾個KEY CODE，甚至建立密碼庫存放這些密碼
   I = 1: KEY OFF: CLS : LOCATE ， ， 0， 14
   PK1$ = A1$ + A2$ + A5$ + A3$ + A4$ + A5$ + A2$
   PK2$ = PK1$  '本例只用一個密碼

   從第line 14到line 18為密碼檢核常式，I值設定讓使用者可輸入三次，超過
   三次未輸入正確密碼則結束程式。非法使用者有時會先找出密碼為幾位數，再進
   行測試。此處使用DO ... LOOP 的目的即是讓非法使用者無法查覺密碼位數，以
   增加篩檢困難度。
14 PRINT : PRINT : PRINT : ' PLAY FATE1$
   IF I <= 3 THEN
      I$ = LTRIM$(STR$(I))
      ANS$ = "": LOCATE 8， 10， 1: PRINT "Password"
      DO: SANS$ = INPUT$(1): ANS$ = ANS$ + SANS$
      LOOP UNTIL ASC(SANS$) = 13
      I = I + 1: PRINT : ANS$ = LEFT$(ANS$， 7)
          IF I > 3 THEN
             GOTO 16
          ELSE
             GOTO 18
          END IF
   END IF
   CLS : LOCATE 10， 12: PRINT "Incorrect password， permission denied."
   LOCATE 22， 7
   PRINT "* * * By Tony Chang， Tainan， Taiwan， August 18， 1986 * * *"
   PRINT : END
16 IF NOT (ANS$ = PK1$ OR ANS$ = PK2$) THEN GOTO 14
18 IF NOT (ANS$ = PK1$ OR ANS$ = PK2$) THEN
      LOCATE 10， 10: PRINT "Incorrect password， try again please."
      SOUND 700， 1: GOTO 14

   以上的密碼檢核常式，原先是以MBASIC寫成，後來改用QBASIC編譯成OBJECT
   CODE 就可在不同的程式呼叫。

參、檔案加密與解密

檔案加密有很多方式，比較常見的是改變檔案內函值，也就是重新編碼。不論是 ASCII文字檔或是Binary檔(如*.EXE，*.COM，圖形檔或音效檔)都是由0-255等兩百五十六個ASCII碼組合而成，因此只要將這些ASCII碼按照一定的模式重新組合，就和原來的檔案大不相同，達到保護的目的。

編碼的方式有兩種，一種是規則式，例如將原碼加上或減去某值，甚至利用特定公式計算後變碼，也有依照一定程序將原碼重新排列。這種方式因為有一定的規則常會留下蜘絲馬跡，讓解碼者有機可趁，並非是很好的方法。另一種是不規則式，或是隨機式加密法。通常由兩個檔案組合而成，一個是要加密的來源檔，另一個則是用來當作密碼本的簽名檔。這兩個檔案可以是文字檔也可以是二進位檔。由於簽名檔可以千變萬化，檔案大小從數十BYTE到數十KBYTE不等，因此被破解的機率比較小。

以下分別以程式說明這兩種加密方式

肆、規則式檔案加密法

50 CLS
   A6$ = CHR$(110): A12$ = CHR$(111): A15$ = CHR$(121): A16$ = CHR$(84)
   LOCATE 1， 1:
   PRINT "CHarades 1.0 Copyright " + A16$ + A12$ + A6$ + A15$ + " Lab 1992"
   IF A16$ <> "T" OR A6$ <> "n" OR A12$ <> "o" OR A15$ <> "y" THEN 50
   以上是防止版權宣告遭他人篡改的措施

   其次是設計以方向鍵操作的功能選單，使用者可以選擇「加密」「解密」「結束」
   等功能，選項以紅底黃字顯示，項目少時，用方向鍵比較便捷，選單多時才用滑鼠操作
   CLEAR : DIM M$(4): ECG$ = "MF L16O2ECG>CEG>CL32O2CDEFGAB>CDEFGAB>C"
   M$(1) = " 1: Charades "
   M$(2) = " 2: Reduction "
   M$(3) = " 3: Exit to DOS "
   FOR Y = 1 TO 3: LOCATE 2 * Y + 6， 30: PRINT M$(Y): NEXT Y
   LOCATE ， ， 0
   Y = 1: MVE = NO: X = 1: Q$ = ""
   WHILE Q$ <> CHR$(13)
   LOCATE 2 * Y + 6， 30: COLOR 14， 4: PRINT M$(Y): COLOR 15， 1
   Q$ = INKEY$: WHILE Q$ = "": Q$ = INKEY$: WEND
   IF LEN(Q$) = 2 AND ASC(RIGHT$(Q$， 1)) = 72 THEN
      MVE = YES: X = Y - 1:
          IF X = 0 THEN
             X = 3
          END IF
   END IF
   IF LEN(Q$) = 2 AND ASC(RIGHT$(Q$， 1)) = 80 THEN
      MVE = YES: X = Y + 1:
          IF X = 4 THEN
             X = 1
          END IF
   END IF
   'Call DOS shell
   這一段是利用SHELL指令設計暫回DOS功能，有時候忘記檔案放在那個目錄，或是臨時想
   到DOS作業，便可按Esc跳出。&H4E用來存放程式辨識值
   IF ASC(RIGHT$(Q$， 1)) = 27 THEN
      CLS : DEF SEG = &H30: H4E% = PEEK(&H4E): POKE &H4E， 5: SHELL
      DEF SEG = &H30: POKE &H4E， H4E%: DEF SEG : GOTO 50
   END IF
   IF Q$ >= "1" AND Q$ <= "3" THEN X = VAL(Q$): MVE = YES
   IF MVE = YES THEN LOCATE 2 * Y + 6， 30: PRINT M$(Y): Y = X: MVE = NO
   WEND
   A$ = STRING$(1， " ")'定字串長度
   IF Y = 1 THEN 110
   IF Y = 2 THEN 370
   IF Y = 3 THEN PLAY ECG$: CLS
   END

   這一段是加密常式，先輸入要進行加密和加密後的檔名
110 CLS : BEEP
    LOCATE 7， 20: PRINT "ASCII (Binary) file -> Charade file"
    LOCATE 9， 20: INPUT "Source file name "; SFN1$: IF SFN1$ = "" THEN 110
    LOCATE 11， 20: INPUT "Charade file name "; CFN1$: IF CFN1$ = "" THEN 110

    再用 SUB 600 讓使用者選擇 1-99999 五位數作密碼，CD%是密碼值除以256後的餘數
    GOSUB 600

    打開檔案，將ASCII碼逐一讀入，經過編碼運算後存入新檔
    OPEN SFN1$ FOR BINARY AS #1
    OPEN CFN1$ FOR BINARY AS #2
    L = LOF(1)
    FOR I = 1 TO L
    GET #1， I， A$
    H% = ASC(A$)
    AC% = H% + CD%: IF AC% > 255 THEN AC% = AC% - 256
    將ASCII值和密碼餘數值相加，若大於255則減去256
    IF AC% >= 249 THEN 260 '超過249則商大於10，無法存個位數
    A% = INT((AC%) / 25) '計算商
    C% = AC% - A% * 25 '計算餘數
    IF C% = 7 OR C% = 18 THEN
    LOCATE 15， 30: PRINT "Proceeding   : "; I '顯示進行加密的進度
    END IF
    AC% = C% * 10 + A% '以餘數當十位數，以商當個位數，計算新數值
260 PUT #2， I， AC% '將演算結果存進加密檔
    NEXT I
    LOCATE 15， 30
    BEEP: LOCATE 20， 20: INPUT ; "Hit RETURN to continue."， ANS2$: GOTO 50

    這一段是解密常式，將加密演算法反向操作，把ASCII數值還原，再存入解密檔
370 CLS : BEEP: LOCATE 7， 20: PRINT "Charade file -> ASCII (Binary) file"
    LOCATE 9， 20: INPUT "Charade file name "; CFN2$: IF CFN2$ = "" THEN 370
    LOCATE 11， 20: INPUT "Target file name "; TFN2$: IF TFN2$ = "" THEN 370
    GOSUB 600
    OPEN CFN2$ FOR BINARY AS #1
    OPEN TFN2$ FOR BINARY AS #2
    L = LOF(1) - 1
    FOR I = 1 TO L
    GET #1， I， A$
    AC% = ASC(A$)
    IF AC% >= 249 THEN 500
    C% = INT(AC% / 10): D% = AC% - C% * 10 'C% 為十位數， D%為個位數
    AC% = D% * 25 + C% 'D%為原來的商，C%為原來的餘數
    IF D% = 2 OR D% = 7 THEN LOCATE 15， 30: PRINT "Proceeding   : "; I
500 H% = AC% - CD%: IF H% < 0 THEN H% = H% + 256
    B$ = CHR$(H%)
    PUT #2， I， B$
    NEXT I
    LOCATE 15， 30: PRINT "Proceeding   : "; I 顯示進行解密的進度
    BEEP: LOCATE 20， 20: INPUT ; "Hit RETURN to continue."， ANS2$: GOTO 50
    END

    SUB 600 用以計算密碼的餘數值，由於ASCII值為0-255，故除以256再取餘數值，
    密碼設計為五位數只是障眼法，目的是取一個隨機的ASCII值來運算
600 BEEP: LOCATE 13， 20: PRINT "Code Number (XXXXX) : ": CD$ = INPUT$(5)
    CD& = VAL(CD$): IF CD& > 99999 OR CD& < 1 THEN PLAY ECG$: GOTO 600
    CD% = CD& - (INT(CD& / 256)) * 256
    RETURN

    這種加密方式由於一次處理一個BYTE，速度較慢，而且密碼為定值，被解開的機率較大。

伍、隨機式檔案加密法

隨機檔案加密法是利用兩個不同檔案，將其對應位址ASCII碼相加後，應用簡單的演算法取得新值成為加密檔。第一個檔案為資料來源檔，是要加密的檔案，第二個檔案為簽名檔，是當作密碼鑰匙用的檔案。由於簽名檔可以是任何形式的檔案，因此要解開密碼的機率相當低。

範例程式以長字串方式讀入ASCII碼，再存入陣列，得以加快加密速度，由於需用動態定長字串陣列，因此需要較多記憶体來執行。字串陣列大小設定為20K BYTE。陣列太小時若要將大檔案加密，耗時甚久，陣列設定太大，會造成Out of Stack。

50 CLS : A6$ = CHR$(110): A12$ = CHR$(111): A15$ = CHR$(121): A16$ = CHR$(84)
   LOCATE 1， 1
   PRINT "CHarades 2.0 Copyright " + A16$ + A12$ + A6$ + A15$ + " Lab 1992"
   IF A16$ <> "T" OR A6$ <> "n" OR A12$ <> "o" OR A15$ <> "y" THEN 50
   CLEAR : DIM M$(4): ECG$ = "MF L16O2ECG>CEG>CL32O2CDEFGAB>CDEFGAB>C"
   M$(1) = " 1: Charades "
   M$(2) = " 2: Reduction "
   M$(3) = " 3: Exit to DOS "
   FOR Y = 1 TO 3: LOCATE 2 * Y + 6， 30: PRINT M$(Y): NEXT Y
   LOCATE ， ， 0
   Y = 1: MVE = NO: X = 1: Q$ = ""
   WHILE Q$ <> CHR$(13)
   LOCATE 2 * Y + 6， 30: COLOR 14， 4: PRINT M$(Y): COLOR 15， 1
   Q$ = INKEY$: WHILE Q$ = "": Q$ = INKEY$: WEND
   IF LEN(Q$) = 2 AND ASC(RIGHT$(Q$， 1)) = 72 THEN
      MVE = YES: X = Y - 1:
          IF X = 0 THEN
             X = 3
          END IF
   END IF
   IF LEN(Q$) = 2 AND ASC(RIGHT$(Q$， 1)) = 80 THEN
      MVE = YES: X = Y + 1:
          IF X = 4 THEN
             X = 1
          END IF
   END IF
   'Call DOS shell
   IF ASC(RIGHT$(Q$， 1)) = 27 THEN
      CLS : DEF SEG = &H30: H4E% = PEEK(&H4E): POKE &H4E， 5: SHELL
      DEF SEG = &H30: POKE &H4E，
   END IF
   IF Q$ >= "1" AND Q$ <= "3" THEN X = VAL(Q$): MVE = YES
   IF Q$ >= "1" AND Q$ <= "3" THEN X = VAL(Q$): MVE = YES
   IF Q$ >= "1" AND Q$ <= "3" THEN X = VAL(Q$): MVE = YES
   IF MVE = YES THEN LOCATE 2 * Y + 6， 30: PRINT M$(Y): Y = X: MVE = NO
   WEND
   IF Y = 1 THEN 110
   IF Y = 2 THEN 370
   IF Y = 3 THEN PLAY ECG$: CLS : END

   以上程式說明，請參考規則式加密法部份

加密常式: 輸入相關檔名，打開檔案，視檔案相對長度決定一次讀入字串和陣列大小
110 CLS
    LOCATE 7， 20: PRINT "Input file name for Charades Process"
    LOCATE 9， 20: INPUT "Source file: "， SFN1$: IF SFN1$ = "" THEN 110
    LOCATE 11， 20: INPUT "Signature file: "， CFN1$: IF CFN1$ = "" THEN 110
    LOCATE 13， 20: INPUT "Charades file: "， TFN1$: IF TFN1$ = "" THEN 110
    OPEN SFN1$ FOR BINARY AS #1
    OPEN CFN1$ FOR BINARY AS #2
    OPEN TFN1$ FOR BINARY AS #3
    L1 = LOF(1)
    L2 = LOF(2)

    若檔名輸入有誤，則重新輸入
    IF L1=0 OR L2=0 THEN
       BEEP: LOCATE 20，20
       INPUT ; "File Error! Hit RETURN to continue."， ANS2$
       GOTO 110
    END IF

    IF L1 > L2 THEN IL = L2 ELSE IL = L1
    以來源檔及簽名檔中較小的檔案長度作為字串陣列設定值IL
    IF IL > 20480 THEN IL = 20480   'IL最大值為20K BYTE
    設定動態定長字串陣列
    '$DYNAMIC
    DIM RD$(2)
    定義字串變數長度
    RD$(1) = SPACE$(IL)
    RD$(2) = SPACE$(IL)
    若來源檔大於一次處理長度則分段進行加密，否則一次完成
    IF L1 > IL THEN GOSUB RECHA ELSE GOSUB NONRECHA
    ERASE RD$  '將動態陣列移除
    CLOSE : BEEP:
    LOCATE 20， 20: INPUT ; "Hit RETURN to continue."， ANS2$: GOTO 50

一次完成加密常式
NONRECHA:
    GET #1， ， RD$(1)
    GET #2， ， RD$(2)
    FOR I = 1 TO IL
    DSOR$ = MID$(RD$(1)， I， 1)
    DCHA$ = MID$(RD$(2)， I， 1)
    SOR% = ASC(DSOR$)
    CHA% = ASC(DCHA$)
    TAG% = SOR% + CHA%: IF TAG% > 255 THEN TAG% = TAG% - 256
    必要時可在此處加上其他演算法變碼
    DSOR$ = CHR$(TAG%)
    PUT #3， ， DSOR$
    NEXT I
    RETURN

分次完成加密常式
RECHA:
    LAST = 0
    JT = INT(L1 / IL) + 1
    FOR J = 1 TO JT
    GET #1， ， RD$(1)
    GET #2， 1， RD$(2)
    FOR I = 1 TO IL
    DSOR$ = MID$(RD$(1)， I， 1)
    DCHA$ = MID$(RD$(2)， I， 1)
    SOR% = ASC(DSOR$)
    CHA% = ASC(DCHA$)
    TAG% = SOR% + CHA%: IF TAG% > 255 THEN TAG% = TAG% - 256
    必要時可在此處加上其他演算法變碼
    LAST = IL * (J - 1) + I
    DSOR$ = CHR$(TAG%)
    PUT #3， LAST， DSOR$
    IF LAST = L1 THEN EXIT FOR
    NEXT I
    LOCATE 15， 30: PRINT "Proceeding   : "; LAST
    NEXT J
    RETURN

解密常式: 輸入相關檔名，打開檔案，視檔案相對長度決定一次讀入字串和陣列大小
370 CLS
    LOCATE 7， 20: PRINT "Input file name for Reduction Process"
    LOCATE 9， 20: INPUT "Charades file: "， SFN1$: IF SFN1$ = "" THEN 370
    LOCATE 11， 20: INPUT "Signature file: "， CFN1$: IF CFN1$ = "" THEN 370
    LOCATE 13， 20: INPUT "Reduction file: "， TFN1$: IF TFN1$ = "" THEN 370
    OPEN SFN1$ FOR BINARY AS #1
    OPEN CFN1$ FOR BINARY AS #2
    OPEN TFN1$ FOR BINARY AS #3
    L1 = LOF(1)
    L2 = LOF(2)
    若檔名輸入有誤，則重新輸入
    IF L1=0 OR L2=0 THEN
       BEEP: LOCATE 20，20
       INPUT ; "File Error! Hit RETURN to continue."， ANS2$
       GOTO 370
    END IF
    IF L1 > L2 THEN IL = L2 ELSE IL = L1
    IF IL > 20480 THEN IL = 20480
    DIM RD$(2)
    RD$(1) = SPACE$(IL)
    RD$(2) = SPACE$(IL)
    IF L1 > IL THEN GOSUB REDUC ELSE GOSUB NONREDUC
    CLOSE : BEEP:
    LOCATE 20， 20: INPUT ; "Hit RETURN to continue."， ANS2$: GOTO 50

一次完成解密常式
NONREDUC:
    GET #1， ， RD$(1)
    GET #2， ， RD$(2)
    FOR I = 1 TO IL
    DSOR$ = MID$(RD$(1)， I， 1)
    DCHA$ = MID$(RD$(2)， I， 1)
    SOR% = ASC(DSOR$)
    CHA% = ASC(DCHA$)
    TAG% = SOR% - CHA%: IF TAG% < 0 THEN TAG% = TAG% + 256
    DSOR$ = CHR$(TAG%)
    PUT #3， ， DSOR$
    NEXT I
    RETURN

分次完成解密常式
REDUC:
    LAST = 0
    JT = INT(L1 / IL) + 1
    FOR J = 1 TO JT
    GET #1， ， RD$(1)
    GET #2， 1， RD$(2)
    FOR I = 1 TO IL
    DSOR$ = MID$(RD$(1)， I， 1)
    DCHA$ = MID$(RD$(2)， I， 1)
    SOR% = ASC(DSOR$)
    CHA% = ASC(DCHA$)
    TAG% = SOR% - CHA%: IF TAG% < 0 THEN TAG% = TAG% + 256
    LAST = IL * (J - 1) + I
    DSOR$ = CHR$(TAG%)
    PUT #3， LAST， DSOR$
    IF LAST = L1 THEN EXIT FOR
    NEXT I
    LOCATE 15， 30: PRINT "Proceeding   : "; LAST
    NEXT J
    RETURN

陸、結語

以簽名檔作為隨機加密的密碼檔，也可用來作為檔案製作認證文件，如果通訊雙方各用兩個共軛簽名檔重覆加密，更可確認雙方身分。例如收訊者和送訊者先交換簽名檔送訊者再以自己和對方的簽名檔進行二次加密後，經由網路送給對方，受訊者收到檔案再用這兩個簽名檔進行二次解密，便可將檔案還原。由於簽名檔可針對不同檔案隨時更改內容，即使第三者截獲加密檔也很難解密。本文提到的隨機加密程式，經過編譯後處理 20K BYTE 檔案僅需數秒，實用性頗高。

簽名檔可用一般文字檔或二進位檔，最好使用字元比較有變化的檔案作簽名檔。色彩單調的圖形檔或比較鬆散的檔案(可得高壓縮率的未壓縮檔)，通常不適合作為簽名檔。一般而言，使用經過壓縮的檔案進行加密或當作簽名檔，都可得到較好的加密效果。

[ 中文作品 | 回主畫面 | 已發表論文 ]