雅技資訊日誌: 利用字母及數字對身分證做分段加密(轉置)方法

這是我去年的一個Case，不過目前已經 failed，原因是這個演算法沒有學術根據，無法用數學方法驗證他的安全性。即然案子已經 failed，所以就將個方法公開。

這個演算概念是個人創造出來的，如果看倌要引用這個方法，麻煩註明出處及作者，至少讓我享受一下「虛榮」，如果要應用在商業上，請先徵得作者同意!

需求：

客戶要求開發一組API，可以將台灣的身分證統一編號(以下用 ID表示)進行轉換，而轉換出來的 ID 仍要符合身分證統一編號的編碼及驗算規則，fe()是編碼函數，fd()是解碼函數，fe(IDa )=IDb；fd(IDb)=IDa，簡單的說，就是將 IDa 丟到函數 fe()中，產出的結果 IDb 還是一組合法的身分證編號，將 IDb 丟到 fd() 中則可以反解回 IDa。

看倌或計會有一個疑問，要這麼費功夫嗎? 用一個字母及數字轉換的對照表不就解決了。是的，一開始我也這麼想，可是這樣太容易反解了，大約只要精心安排4組身分證號就可以破解，所以才會搞出這麼一個演算法：

假設 IDa 是由 A1 + [12] + N1 + C1 組成

A1：是指身分證字母部分
[12]：是指男或女，不是1，就是2
N1：是指七碼的數字
C1：是指最後一碼的檢查碼

目的：

許多系統再造(或改寫)都要驗證其功能是否正確、完全，一般的測試資料輸入後，只能人工判斷是否無誤，並無法進行比對，而且要產生合理的測試資料曠日費時。

如果可以從現有系統產生真實案件，就可以比對新、舊系統對資料的處理是否一致，但又擔必真實案件中的個資被廠商非法使用，所以最簡單的方式就是對身分證進行轉碼(因為它是鍵值，不能遮蔽)，以及將其他欄位(如姓名、地址)進行遮蔽，然後轉作測試資料用。

轉換要素：

K1：數字的轉碼對照表，最少一組，最多五二組，每一組都包含 0-9 的對照，而且不能有二組內容是相同的。

K2：字母的轉碼對照表，最少一組，最多10的7次方組。

為了易於說明，K1、 K2都用10組表示，底下是我設計的範例：

K1=[ 3018524967, 9207143658, 5860379214, 1492635870, 6974180325, 2580749631, 4752968103, 3641875092, 8596302147, 7085291436 ]

K2=[ BZGCLEKXDYNQAUWSRJTOFIPHVM , GXQEADKUJVLCWOMRBIFYHPNZST , BOFCRMJWSHUZVIPTLYEQNKADXG , WIJURQNKXAEGVDLCTBYSFPZHMO, HEBXFGSDLNJKWUYRZAVIOPMQTC, ZDYLAUEMQXNGKIFRTPCOBWJHVS, MUBZWHCXGSEYLVITDKOFRQANJP, LOFHMJWQCUVRBAIESNTPGYXZDK, IZKQCSVYGDJWAOFTRMLXNBUPHE,
GRXMDQAWTCBKNVPYELOFSZHUJI ]

加密演算：

由 A1 決定數字轉換要採用哪一組，如果要採用52組的方式，則由 A1 與 [12] 共用決定，所以因應不同字母，數字的轉換對照表就不一樣，利用不同的對照表對 N1 進行轉換得到 N2。

即 fe(N1, K1, A1) => N2

再利用 N2 進行加權找出要使用的字母對照表，用來轉換字母，例如：

直接 MOD(N2,10)=Pt2 //用 N2 除於10 取餘數
或者 N2逐數字乘於 1,2,3,5,8,13,21 再取10的餘數
MOD([N2]*[1,2,3,5,8,13,21], 10)=Pt2
(各種加權方式可以自行發揮)
fe(A1, K2, Pt2) => A2

等決定好 A2, N2 後，[12]不做轉換，直接加入，然後重新計算檢查碼，即：

fc(A2, [12],N2) => C2
故得新的 ID 為
IDb=A2 + [12] + N2 + C2 組成

解密演算：

加密後的 IDb=A2 + [12] + N2 + C2

解密時，反過來計算，利用 N2 的加權找出要使用的字母對照表，用來轉換字母，例如：

直接 MOD(N2,10)=Pt2 用 N2 除於10 取餘數
或者 N2逐數字乘於 1,2,3,5,8,13,21 再取10的餘數
MOD([N2]*[1,2,3,5,8,13,21], 10)=Pt2 這個Pt2的值應該要和加密演算得到的 Pt2一致!

fd(A2, K2, Pt2) => A1
得到 A1 後，就可以得知轉換數字的對照表是用哪一組了，即：
fd(N2, K1, A1) => N1

等解出 A1, N2 後，[12]不做轉換，直接放回去，然後重新計算檢查碼，即：

fc(A1, [12],N1) => C1
故得解碼後得至
IDa=A1 + [12] + N1 + C1即為原身分證號

缺點：

這個演算法有個缺點，就是如果原 ID 的檢查碼是錯的，加密再解密，會造成檢查碼不一致! 目前我還沒有想到如何克服這個問題!

先天的缺陷：

台灣身分證原本就是有限集合(5億2千萬組)，利用窮舉破解，一定解得開，而且不會花太多時間，所以這種方法是不能跟DES 或 AES 相比的。

優點：

由於 K1, K2 是由開發人員自己建置，所以不同的開發人員對同一組ID加密後的結果可能都不一樣，要破解也比使用單獨一組對照表(前面提到的)來得困難。如果覺得加密一次很好解，也可以進行多次加密，即 fe(fe(fe(IDa, K1,K2),K3,K4),K5,K6)。

延申演算：

看倌或許發現，要解出數字對照表其實很簡單，例如用 A123456789， A198765435 大概就可以看出端倪，我們可以將整個ID做分段，例如 A123456789，把 A234 和 5678 分成兩組來決定對照表，這樣就更不容猜出，甚至可以使用更極端的做法，由 8 決定 A 的對照表，再由 A 的結果決定 2 的對照表，依此類推，最後由 7 的結果決定 8 的對照表。解碼時，由 7 的結果解出 8 ，再依序由 8 解 A，A 解 2，...，這樣做，就不限只使用K1，K2，可以使用更多組對照表。破解的困難度也會增加

嘆氣：

這個演算法沒有辦法讓客戶接受，因為我無法用數學或統計方法證明它是安全的，其實單獨身分證編號本身就沒有安不安全問題，因為坊間一堆的產生器，甚至有人寫好批次產生，要身分證號碼，一點也不難，這不是演算法的原罪!