加密強度可定制的新型文本加解密算法*

2017-09-18 00:28:58姜文超林德熙郭楚謀武繼剛孫傲冰

計算機與生活 2017年9期

姜文超，林德熙，郭楚謀，武繼剛，孫傲冰

1.廣東工業大學計算機學院，廣州 510006 2.廣東電子工業研究院，廣東東莞 523808

加密強度可定制的新型文本加解密算法*

姜文超1+，林德熙1，郭楚謀1，武繼剛1，孫傲冰2

1.廣東工業大學計算機學院，廣州 510006 2.廣東電子工業研究院，廣東東莞 523808

各類信息服務系統在生活中各領域的廣泛應用導致用戶需要管理和記憶越來越多的賬號和密碼，設計一種讓用戶能夠根據實際需求自定制的、加密強度可調節的賬戶和密碼管理方法成為急需解決的問題。提出了一種加密強度可定制與調節的加密策略，并設計、實現了一個加密算法實例。算法分為3個步驟：哈希映射、空白填補、字符加密。哈希映射用于制作密碼本，負責把明文根據密碼本放到密文緩沖區，或根據密碼本把明文從密文緩沖區讀取出來；空白填補把密文緩沖區空白部分填上隨機字符，進一步增加保密級別；字符加密允許用戶采用自己特定的加密算法對每個明文字符進行加密。理論分析和實驗測試均表明該加/解密算法靈活、便捷，同時可以有效保證用戶隱私數據的安全性，允許用戶根據實際需求自定制專屬自己的獨特的保密方法，并且證明在不知道密鑰的情況下無法使用蠻力窮舉法破解。

加密強度可定制；文本加密；哈希映射

1 引言

隨著各類信息系統的廣泛應用，人們擁有越來越多的賬號和密碼，但是人的記憶力是有限的，記住眾多的賬號和密碼會給用戶帶來很大困擾。通用的數據加密算法雖然可以保護用戶的隱私信息，但理論上仍然具有被破解的可能，倘若某一加密算法被破解，所有使用該方法的信息系統和用戶都將面臨突發的泄密災難。因此在數據保護需求強度越來越高的情況下，能否設計一種用戶可自定義的、加密強度可調的加密算法，使廣大非加解密領域和IT領域專家的普通用戶可以設計、開發具有自己個人特色的且每個用戶都互不相同的加密方法成為一種迫切需求。另外，目前各類信息系統的賬戶和密碼均采用數字和字符組合的方式，而沒有利用中文漢字數量大且方便記憶的獨特優勢。設計一種新型的、可自定義的、加密強度可定制的、結合中文復雜性的加密策略可以在保證用戶隱私數據安全的同時，使用戶容易記憶賬戶、密碼等高度隱私的數據信息。

本文提出了一種加密強度可自主定制與調節的加密策略，并實現了一個加/解密算法實例，讓用戶根據自己的需求和特色輕松設計專屬于自己的加密算法。對于任何一段數據，該方法分為3個步驟：哈希映射、空白填補、字符加密。哈希映射用于制作密碼本，負責把明文根據密碼本放到密文緩沖區，或根據密碼本把明文從密文緩沖區讀取出來；空白填補把密文緩沖區空白部分填上隨機字符，進一步增加保密級別；字符加密允許用戶采用自己特定的加密算法對每個明文字符進行加密。理論分析和實驗測試均表明本文加密算法可以有效保證用戶隱私數據的安全性，在不知道密鑰的情況下無法使用蠻力窮舉法破解。

2 算法設計

2.1 術語定義

本加密策略考慮到使廣大非加/解密領域和IT領域專家的普通用戶可以設計、開發具有自己個人特色的且每個用戶都互不相同的加密方法的原型，需要讓加密過程簡單、靈活，且加密強度可以調節，為描述其加/解密原理，定義基本術語如表1所示。

2.2 加密原理

如圖1所示，加密過程由校驗密碼模塊、哈希映射[1]模塊、填補空白模塊和加密字符模塊構成。校驗密碼模塊包括檢查密碼是否能作為密鑰和是否能對明文進行分解兩個功能。明文分解是把明文分解為多個子明文進行加密，在明文長度過大情況下，轉換為小于一定長度的明文作為輸入。其中，哈希映射需要申請一段內存空間作為緩沖區，哈希映射根據密鑰把明文字符亂序放在緩沖區。

Table 1 Basic definitions表1 基本術語定義

填補空白模塊負責在緩沖區空白位置填補隨機字符。字符加密模塊對每個字符運用用戶特定的加密算法進行加密，保證攻擊者無法猜測明文信息。只要緩沖區足夠大，填補空白使明文和填補組成的密文無法知道給定一段字符是輸入填補還是明文。

加密過程實例偽代碼描述如下。

1.encryption(str,key)

2.input str,key//明文，密碼

3.get temp_length//獲得緩沖區長度

4.if(IsNullorEmptyorWhitechar(str))//明文判斷不空

5.return str

6.hstr=md5(key)+end_string//后綴

7.get per//獲得緩沖區使用率

clearstr=distribution(str,temp_length*per)//分割明文函數，輸入字符串和分割字符串長度temp_length*per，可以把字符串str分割為長度不大于temp_length*per的多個字符串

8.foreach(temp in clearstr)//分割的明文分別進行加密

9.ciphertext+=encryption_string(temp,temp_length,hstr,key)

10.return ciphertext

加密子明文需先申請緩沖區，長度temp_length，明文后面加上后綴，對明文每個字符，使用哈希映射得到其在緩沖區的位置，如果哈希映射得到位置沖突，則使用沖突函數得到一個沒有沖突的位置。之后通過fill_gaps填補空白，輸入緩沖區temp和密鑰，對temp填補空白，填補空白之后對temp每個字符加密。其偽代碼描述如下。

1.encryption_string(str,temp_length,hstr,key)

2.temp=char[temp_length]//申請緩沖區

3.str=str+hstr//明文后綴

4.for i=0 to str.length

5.position=hash(i,key);//哈希映射

6.temp[position]=str[i]

7.fill_gaps(temp,key)//填補空白

8.for i=0 to temp_length

9.temp[i]=encryption_character(temp[i],key,i)

10.return temp

2.3 解密原理

如圖2所示，解密過程包括校驗密鑰、哈希映射、字符解密3個模塊。當存在多個密文需要進行解密且費時較長時需要驗證密鑰，一旦密鑰錯誤，校驗密鑰模塊可以停止解密以節約時間，可對原密鑰進行特定加密過程，比如MD5[2]，然后用加密算法使用經過MD5加密后的密鑰。首先用經過驗證的密鑰對密文解密，然后比較要驗證密鑰的MD5和明文是否相同來驗證密鑰。

Fig.1 Encryption圖1 加密過程

解密過程中的哈希映射和加密過程類似，除了沖突處理conflict之外，用于判斷當前位置在緩沖區是否已經存在字符，如果不存在字符，那么解密沖突。這和加密過程相反，加密過程是存在字符時發生沖突。使用哈希映射得到密文字符在明文中的位置，哈希映射和密鑰以及明文的字符所在位置有關，和明文本身無關，用相同的密鑰可以得到處于相同明文位置的字符在緩沖區唯一位置。

字符解密模塊包括加密哈希映射得到的結果和截取密文，也可以對隨機字符解密。截取密文根據后綴截取，字符解密后可以得到明文加上后綴、隨機字符后的字符串，對字符串截取后綴后即可得到明文。

解密過程實例偽代碼描述如下。

1.decryption(str,key)

2.get temp_length

3.if(IsNullorEmptyorWhitechar(str))

4.return str

5.hstr=md5(key)+end_string

6.ciphertext=distribution(str,temp_length)//分割密文

7.foreach(temp in ciphertext)

8.clearstr+=decryption_string(temp,temp_length,hstr,key)//對分割的密文解密

9.return clearstr

1.decryption_string(str,temp_length,hstr,key)

2.tempclearstr=char[temp_length]//申請緩沖區

3.tempciphertext=char[temp_length]

4.for i=0 to temp_length

5.tempciphertext[i]=decryption_character(str[i],key,i)//解密字符

6.position=hash(i,key)//哈希路徑

7. count=0

8.while(!IsNull(temp[position]))//沖突處理

9. position=conflict(count,position,key,temp_length)

10.tempclearstr[i]=tempciphertext[position[i]]

11.return subhstr(tempclearstr,hstr)//去后綴

3 算法實現

根據加/解密原理，一個加密算法需要分別對加密過程和解密過程用到的校驗密碼、哈希映射、填補空白、字符加密子模塊分別加以實現。

3.1 校驗密碼

校驗密碼包括密碼長度檢驗[3]、重復字符檢驗兩個模塊。因為在加密過程需要一個正確的密碼，如果一個長度過短并且有很多重復字符的密碼，使用哈希映射將會容易產生沖突，導致性能差。經過哈希映射處理后，和明文相比，密文熵沒有足夠大，密碼長度如果和緩沖區長度相同，每個緩沖區數據都能分配一個密碼作為密鑰的關鍵字key，但是用戶極少能輸入這么長的密碼。如果檢驗到用戶密碼過短，可以讓用戶重新輸入或組合用戶的密碼得到密鑰。重復的字符檢驗存在多個相同字符，在哈希映射得不到比較散列的位置，因為由密鑰字符決定明文在緩沖區位置，相同的字符會得到相同的位置，因而造成沖突，之后調用沖突處理conflict會降低加密性能。位置分布不夠分散導致密文熵不夠大，影響加密強度。因此緩沖區temp長度temp_length與密鑰長度存在一定關系temp_length=f(k_length)，獲得最好的比例，temp_length越長加密效果越好，需要空間越大，調用沖突處理次數越大，而temp_length越小，分割越多，加密性能越差。例如：密鑰長度為l，如果沖突處理使用步長為l的conflict，就會讓哈希映射失去作用。可以尋找到一個新的起點，排列出m，滿足m==M，從而避免步長為l的沖突發生。

為滿足密鑰長度和加密的要求，首先判斷密碼長度，然后選擇去除重復字符。在用戶輸入過短的情況下，可以把用戶的輸入進行MD5，得到比較長的密鑰，但這種情況限于用戶輸入為英文和數字的情況，并沒有使用中文加密。而選擇使用何種哈希映射也可以依靠密碼來調整，如密碼只有英文和數字，沒有中文，則選擇對英文和數字有優化的哈希映射。同時，根據密鑰可以決定緩沖區長度，但緩沖區長度選擇和哈希算法有關，如果使用密鑰單字符作為哈希映射關鍵字,選擇緩沖區長度應為密鑰的10倍，保證每10個明文字符所用的密鑰字符是相同的。如果選擇緩沖區長度100倍，則每100個明文字符所用的密鑰字符是相同的。因此選擇多個字符作為關鍵字，明文字符所用的關鍵字相同的數量會比選擇密鑰單字符作為哈希映射關鍵字少，密鑰作為哈希關鍵字中重復數越少，加密效果會越好。

加密校驗密鑰的算法實例如下。

1.input key//輸入密碼

2.if(IsNullorEmptyorWhitechar(key))//判斷輸入字符串是否空字符串、無效字符串、空格字符串

3.fail

4.else

5.key=remove_same_character(key)//刪除字符串的相同字符

6.if(key.length＜MinLength)//判斷密碼是否小于作為密鑰最小長度

7. fail

8.else

9.true

解密過程校驗密鑰可利用已有的MD5算法，把MD5后的密文放到本算法中加密，得到密鑰key，如果保存在本地的密鑰密文解密后和輸入密鑰MD5后一樣，那么密鑰正確。

解密校驗密鑰的一個算法實例如下。

1.input key,keystr//key是輸入密鑰，keystr是保存在本地的密鑰密文

2.str=md5(key)//MD5是已有的MD5加密算法，能對輸入的字符串輸入一段定長的密文

3.str1=decryption(keystr,key)//decryption是本加密算法的解密函數，需要輸入明文和密鑰，輸入密文

4.if(str==str1)

5. right

6.else

7.fail

3.2 哈希映射

哈希映射包括分割明文或密文模塊、哈希路徑判斷、沖突處理3個功能。哈希映射的設計目標是讓每個明文字符對應到緩沖區中不同位置，如圖3所示。其中，明文每個字符的位置和明文本身無關，只和密鑰k、字符在明文中的位置i有關。

Fig.3 Hash mapping圖3 哈希映射過程

具體哈希映射、路徑 p和沖突處理方法有多種選擇，可以根據用戶實際需要和加密強度需求自主選擇和調節加密強度。其實現偽代碼描述如下。

1.hash(i,key)

2.position=p(i,key)//哈希路徑

3.while(!IsNull(temp[position]))//沖突處理，加密判斷位置不為空，解密過程判斷位置為空

4.position=conflict(count,position,key,temp_length)

5.return position

哈希映射的關鍵是產生哈希路徑，只要滿足輸入一個關鍵字，得到一個在緩沖區長度temp_length以內的數值即可滿足算法的哈希路徑要求。當key和value唯一對應時產生的哈希路徑效率最高。如果可以保證有大量不同的key得到不同的value，只有少量不同的key可能得到相同的value的哈希路徑即可使用，此時可以調用沖突處理函數來得到另一個確定的位置。

哈希路徑輸入關鍵字可以使用單個密鑰字符、多個密鑰字符、密鑰字符和明文字符所在明文位置的混合等多種方式。使用單個關鍵字可以把關鍵字的unicode作為返回的value參數進行計算，比如式（1）采用除留余數法。除留余數法是將key對一個常數取模。

其中，a、b、c為常數；%為取模，取模操作確保最后的value不會超過緩沖區的大小。

哈希路徑產生過程都依賴密鑰，可能得到一個不適合的熵值，會增加沖突處理次數，進而降低算法性能。為解決這個問題，如式（2）所示，關鍵字key可以使用密鑰中的字符和value與明文的第i個字符的比值得到，從而使每個關鍵字都不相同，存在一個哈希路徑使value也都不同。

根據key得到value可以用傳統的Hash函數，比如Robert Sedgwicks（RS）[4]、Justin Sobel（JS）[5]等。但是這些哈希映射不能很好地適應本算法，因為最終得到的值需要對緩沖區長度取模，這樣散列映射空間很小，沖突次數增多。

為解決該問題，本文采用密鑰排序法，能夠利用密鑰中的字符和i來得到明文第i個字符所在緩沖區位置。密鑰排序法按照密鑰字符規律先對密鑰可能的字符進行排序，如英文的次序和漢字拼音次序。去掉密鑰中相同的字符，計算密鑰剩下字符，并更新密鑰長度。把緩沖區分割為temp_length/k_length個區，每個區按照字符順序，每個區長度相同，多余的緩沖區字符可以放在每個區之間。明文的第i1個字符對應密鑰第i2個字符，反之可以按照密鑰第i2個字符所在順序位置得到明文的第i1個字符首位置。密鑰第i2個字符作為i1/k_length個字符的關鍵字，明文的第i1個字符位置可以是a+b，b∈B。B是可以在分割后的緩沖區內沒有重復數的數組。例如：密鑰只有英文，那么將存在的英文字符排序，刪除重復的字符，分割緩沖區為temp_length/k_length。如果明文的第i1個字符剛好對應的密鑰第i2個字符是B，那么尋找B所在的位置a，則明文的i1字符首位置就是a，判斷當前i2和i1的比，獲取的當前明文是所在區域第i3個進入明文，根據沖突處理放到相對的位置。

假如密鑰ABCGFKJ

明文是123456789

那么首先對密鑰進行分析，按照ASCII對密鑰字符進行排序。可以看到A排在第1位，B排在第2位,C排在第3位，因為沒有DE，F排在第4位，G排在第5位，J排在第6位，K排在第7位。通過函數 place(key)，根據key得到所在區域，如圖4所示。

Fig.4 Zone of secret key characters圖4 每個密鑰字符區域

把緩沖區分為7部分，稱為區域，如圖5所示。這里設每個區域大小都一樣，不能被整數劃分的緩沖區空間放在最后。

Fig.5 Zone of each character圖5 每個字符區域大小

把每個明文字符根據所在位置選擇密鑰的字符，得到位置，如圖6所示。

Fig.6 Placement of plain text圖6 把明文放到區域

密鑰排序法簡單，對于英文和數字加密效果不夠理想，但是中文漢字數量大，可以充分發揮其算法優勢。另外，對于漢字密鑰，可以依照拼音或筆畫等對漢字進行排序，得到密鑰每個字符對應排序后所在位置，明文的第i個字符和密鑰的第i1個字符相對應，分配到密鑰第i1個字符所在區域。漢字密鑰產生前必須有一套規則來對漢字排序，需要漢字庫的支持。漢字庫最簡單的有按照拼音和比劃排序。普通字典也可以在排序前先加密，防止攻擊者依靠漢字庫來猜明文所在區域。

沖突處理[6]是指當輸入相同關鍵字時就出現了沖突，相同關鍵字哈希路徑得到相同位置，而在加密過程把明文M放到已有明文的位置會丟失明文，不使用沖突處理可以作為摘要加密。沖突處理需要訪問內存尋找一個沒有沖突的位置，時間較長，如果加密一個字符需要訪問沖突處理次數很多，那么效率很低。當前可用沖突處理可以是簡單使用密鑰來獲得一個數，然后判斷這個數對應位置是否沖突，如果沖突則繼續步驟。而奇數環法則是申請緩沖區長度為奇數，采用步長為偶數的沖突處理方法。加密過程的沖突處理是判斷當前位置已經被占用，則調用沖突處理尋找其他位置。解密過程的沖突處理是判斷當前位置如果沒有經過加密的字符，即空區域，則調用沖突處理進行下一個加密字符的搜索。沖突處理函數由原位置position和步長step組成。

conflict(i,position)=(position+k_i)%temp_length

解密過程的沖突處理不能出現某些位置一直訪問不到，如果只出現很少量小于temp_length/(1-per)的位置，那么明文可以全部放進緩沖區。如果用戶需要得到一個無沖突的方法，沖突處理可以使用奇數環法。

3.3 填補空白

填補空白把緩沖區空白部分填補隨機字符，可以進一步打亂明文的持續。在填補空白之前，需要在明文后面添加后綴，用以區分明文和填補的垃圾信息，如圖7所示。

Fig.7 Filling blanks圖7 填補空白

后綴是區分明文和垃圾的字符串，在解密過程，通過哈希映射得到結果，從結果的末尾開始尋找后綴所在的位置，去除后綴及之后的垃圾數據，可以得到明文，故后綴的設置需要和填補的垃圾位置不存在沖突。后綴可以是固定的字符串，和密鑰無關，也可以是和密鑰有關的字符串，根據密鑰的摘要采用MD5來得到后綴。

在加密過程中，可以通過哈希映射把垃圾填補在明文里面。先申請一個和緩沖區相同大小的空間Mtemp，利用哈希映射在Mtemp添加上temp_length-M_length個垃圾字符，然后把明文按照順序放到Mtemp，如果位置被占用，則向下尋找沒有字符的位置放入明文。解密過程則使用哈希映射找出填補垃圾所在的位置，然后去除垃圾字符得到明文。

填補空白的一個實例描述如下。

1.input temp,key

2.for i=0 to temp_length

3.if(IsNull(temp[i])

4.temp[i]=ran_char

3.4 加密字符

加密字符可以根據用戶需要選擇使用目前的任何一種加密算法[7-8]。通過加密字符，攻擊者要得到原有的信息，通過排列只能得到一個和自己隨機組合得到的一樣的結果。比如將字符的unicode加上一個隨機數，或對每個字符進行異或，或使用DES（data encryption standard）[9]加密算法對每個字符進行加密。例如：在只有英文大寫字符的情況，Z+1=A。對每個字符異或一個數和加上一個數相同，這個數可以是根據密鑰得到的，但是如果能保證源代碼不被攻擊者得到，加上一個固定數也是可以的。

異或操作可以讓原有的數據類型發生變化，即：原本是英文，加密后超過英文的范圍；原本是數字，加密后超過數字范圍。另外，異或操作會導致轉換字符編碼出現問題，解密后得不到原文，異或操作的使用是對于不進行字符編碼的加密。

字符加密算法描述如下。

1.for i=1 to temp_length

2.encryption_character(n,temp_i)

3.end for

1.encryption_character(str,key,i)

2.get type(str)up,down//獲得字符的類型Unicode最大值up，最小down

3.return range(str,key[i%key.length],up,down)//range區間加法

4 實例測試

明文M：這是；

后綴h：明文；

密鑰：用戶。

整個加密過程如圖8所示。

4.1 哈希映射對明文亂序

哈希映射包括哈希路徑和沖突處理。哈希路徑使用密鑰相關，其中：

（1）p(K0,M0)=2

（2）p(K1,M1)=5

Fig.8 Example of Hash mapping圖8 哈希映射實例

沖突處理conflict函數的作用是在原有位置加1得到新的位置。如果采用沖突處理得到的位置和原哈希路徑得到位置相同，那么可能存在某些位置沒有被訪問到[10]，這時需要更改沖突處理的方法，修改步長讓沖突處理可以訪問所有位置。

1.begin temp_position≠'