??? 摘?要:? 討論了Microchip公司的KEELOQ加解密" title="加解密">加解密算法的實現機制，通過引入隨機數" title="隨機數">隨機數，提出了一種新的改進算法，并給出了其在單片機中的實現方法。該算法具有簡單實用、所需硬件資源少、傳輸效率和安全性相對較高等優點，適用于需要數據加密" title="數據加密">數據加密的小型無線數據傳輸系統，具有廣闊的應用前景。
??? 關鍵詞：? 加密算法? KEELOQ? 單片機? 跳碼技術
?
??? 當今的編解碼" title="編解碼">編解碼電路已經朝著高度集成化和微電腦化發展。像普通的固定編解碼芯片如MCl45026/145027、PT2262/2272等已被廣泛應用于公用系統中，給生活帶來了方便。然而這些芯片不能保證系統的安全性。由于這些系統每次發送的數據流一模一樣，只是高低電平的組合，第三方通過捕捉設備，一旦用戶信號出現，便可瞬間取得合法的身份識別碼；或使用編碼掃描設備，主動攻擊解碼芯片。因此保證系統的安全性是一個很現實的問題[1]。在此背景下，基于加密算法的編解碼IC的安全機制得到了應用。Microchip公司的KEELOQ技術是這種技術的代表[2,3,4]。KEELOQ技術是一種多變化、抗截獲、安全可靠性高的非線性跳碼加密解密技術。KEELOQ目前是通過硬件芯片IC（以Mirochip公司的HCS300為代表）實現，主要應用于汽車防盜系統和門禁系統，是無鑰進入系統領域的首選芯片。但也由于硬件芯片本身的限制（其所能加密的數據必須預先寫入EEPROM中），使之很難用于其它（如數據加密）領域。
??? 本文把這項封裝在芯片里的KEELOQ加密技術用軟件方式實現，并針對單片機的特性進行了適當改進。這種在單片機中實現的改進算法不僅包含了原來HCS300所具備的所有功能，而且在系統安全性、靈活性、可擴展性、傳輸效率等方面均有較大改善，同時對改進算法在數據加密領域作了全新的嘗試，以其特殊的密鑰管理方法獨立于對稱型加密(如DES)與不對稱型加密算法(即公開密鑰體制，如RSA)[1]，成為一種適用于無線傳輸領域小型系統的數據加密算法。
1 KEELOQ技術簡介及其硬件實現
??? KEELOQ技術的核心思想[2,3,4]是用64bit的EN_KEY[64:0]（加密密鑰）去加密32bit的CSR[31:0]（校驗碼）得到32bit的CRYP密文。加密機制為：首先定義一個非線性表，這個非線性表有5位輸入NLF_IN[4:0]，一位輸出NLF_OUT。它在CSR[31:0]中間隔均勻地取固定5位：I0、I1、I2、I3、I4，通過非線性產生一個輸出碼NLF_OUT；這一位輸出碼NLF_OUT再與EN_KEY中的15位、CSR中的2位進行異或運算后輸出第一位輸出碼CRYP[0]；每輸出一位后，EN_KEY、CSR分別進行移位，EN_KEY作循環移位，CRYP[0]作為CSR移位的輸入；重復上述步驟直到輸出32位CRYP[0:31]。依此法，即使32bit的校驗碼CSR中只有一位發生變化，用KEELOQ加密算法得到的CRYP密文也會有50%以上的數據位(16bit)發生變化。
??? Microchip公司以KEELOQ技術為基礎開發了滾動碼系列專用芯片，HCS300是其中較典型的一款。它是一塊8引腳的編碼IC芯片，里面集成了KEELOQ算法和其他一些功能，帶有四個按鍵接口，實現15位的功能/命令碼。內置192bits(12×16bit words) EEPROM，用來存放EN_KEY（加密密鑰）、SN（序列號）、SYNC（同步碼）、SEED（種子碼）等。序列號用來標識不同的對象；加密密鑰用來對發送的數據進行加密，增加破譯的難度，它不直接發送出去；同步計數器用來抗截獲，每次發送數據時，同步計數器的值都被更新，所以每次發送的數據都不一樣。種子碼用于安全學習時參與加密密鑰的生成。接收方必須先通過學習來獲得并存儲發送方的序列號、加解密密鑰和當前同步計數器的值。學習相當于身份確認，只有經過學習的用戶才能與主機通信。主機在接收到信號后，首先比對序列號，然后利用學習過程中得到并存儲的加密密鑰對接收的數據進行解密；接著檢查同步計數器是否匹配，在確認其匹配后，再去處理接收到的按鍵信令，并根據接收到的按鍵信令作出相應的動作反應。HCS300系統使每次發送的密文都不相同，有效防止了空中截獲法和數據重傳帶來的安全隱患。
??? HCS300系統的加密密鑰在學習過程中經密鑰生成算法產生。學習分為一般學習和安全學習。一般模式下，解密密鑰由MKEY和SN生成加解密密鑰EN_KEY，其解密密鑰隱含于發送信息（MKEY和SN）中。安全模式下，增加了種子碼SEED(當四鍵一起按時發送)，它與MKEY和SN一起生成加解密密鑰EN_KEY，而SEED_KEY在平時并不發送，這樣增加了安全性。不過，在學習時SEED碼的發送是不經過加密的。
2? KEELOQ技術的不足與改進加密算法的提出
??? 盡管KEELOQ技術有上述獨特的優點，但是經過深入分析不難發現KEELOQ算法及其硬件實現技術也存在一些不足：
??? (1)安全性基于出廠密鑰和種子碼SEED。在HCS300芯片中，加密密鑰EN_KEY是由出廠密鑰MKEY、序列號SN和種子碼SEED（安全模式）生成的。而SN和SEED在發送數據的過程中未經加密，是可截獲的。理論上出廠密鑰一經確定一般不會更改。所以，一旦出廠密鑰外泄，后果極其嚴重。
??? (2)擴展功能弱、升級不方便。其算法由硬件芯片實現。其所能實現的功能由按鍵決定。其按鍵只有4個，最多也只有15種組合。發送方無法附加其余的信息（對于大多領域來說，它要求能發送一些附加信息，如用戶的姓名、年齡、出生日期等），功能擴展幾乎不可能。另外，某一特定型號的芯片其序列號和同步計數器的長度是固定的。當系統建成后，開發者如果想只通過軟件升級來擴充系統的容量或提高系統的性能、用硬件實現技術基本不可能。
??? (3)對功能碼" title="功能碼">功能碼的檢錯和糾錯的功能較弱。在無線傳輸中，出現誤碼的概率比較大。功能碼代表所要實現的功能，如開門、報警、開閥等。如果發送的數據是0010，而接收的數據為0100，其后果非常嚴重[4]。
??? (4)傳輸效率較低。在發送的數據中，其有用信息(如序列號、功能碼)全部在固定碼中，加密碼只作為一種加密用的附加數據，這樣不但降低了安全性，而且傳輸效率不高。以HCS300為例，發送的66位數據中只有32位為有用信息，傳輸效率比較低。
??? (5)無法用于數據加密。由于其是由硬件芯片實現的，它所能加密的數據只限于序列號、同步碼等預先存在HCS300的EEPROM中的數據。它沒有數據入口，無法對數據流進行加密。
??? (6)受硬件設計限制，靈活性差，成本較高，由于不擁有核心技術，容易受制于人[4]。
??? 基于上述分析，筆者結合單片機的特性，對KEELOQ算法提出如下改進：
??? (1)保留出廠密鑰，但引入隨機數，防止出廠密鑰和種子碼的泄漏，用戶可隨時改變加密密鑰。
??? (2)改進數據傳輸的格式，把同步碼映射到各組待加密的數據中，提高傳輸效率。
??? (3)增加對功能碼或關鍵數據的檢錯和糾錯的功能。
??? (4)增加數據入口，改變對加密數據的長度要求，使其適合批量的數據加密。
??? 數據加密系統的兩個基本要素是加密算法和密鑰管理。密鑰是控制加密算法和解密算法的關鍵信息，其產生、傳輸、存儲等工作十分重要。目前數據加密技術可以分為二類，即對稱型加密、不對稱型加密[5]。對稱型加密（如DES算法）使用單個密鑰對數據進行加密或解密。不對稱型加密算法也稱公用密鑰算法（如RSA算法），其特點是有二個密鑰（即公用密鑰和私有密鑰），只有二者搭配使用才能完成加密和解密的全過程。但兩者都在密鑰的管理和分發上遇到一些困難。KEELOQ密鑰管理機制的主要特點是對每個用戶都有自己獨特的加解密密鑰，在學習過程中發送到主機并保存。但密鑰信息隱含在每次發送的信息(SN和MKEY)中（即使在安全模式下，種子碼SEED也是固定碼，可截獲），并且依賴于生產廠家和出廠密鑰，不可更改。本改進算法主要針對無線傳輸領域的小型系統，可以在學習過程中引入隨機參數RANDOM，與MKEY、SN一起生成EN_KEY。這個隨機數RANDOM在同一次學習時相同，但每次學習時都會改變。這樣，加密密鑰就不依賴于生產廠家和出廠密鑰并且在用戶感到密鑰有可能泄漏時可隨時改變數據，增加了安全性。
3? 改進加密算法在單片機中的實現
??? 整個系統分為用戶端（CLIENT）和主機端（SERVER），系統框圖如圖1所示。在本系統中，考慮功耗、外圍功能等需要，選用飛利浦的LPC76X系列芯片[6]。P87LPC764 是20 腳封裝的單片機，可以在寬范圍的性能要求下實現高集成度低成本的解決方案，4Kbits的ROM，128bits的RAM，32Byte用戶代碼區可用來存放序列碼及設置參數，內帶看門狗定時器，處理器的指令執行速度為標準80C51 MCU的兩倍。EEPROM發送部分選用AT2401(128×8 bits)，接收部分選用AT2404（1024×8 bits），8-DIP封裝，I2C總線接口，擦寫次數>1百萬次，保存時間>100年。
?
??? 用戶必須經過學習后才能與主機通信。在學習過程中，用戶把序列號SN、出廠密鑰MKEY、加密密鑰EN_KEY送給主機，主機對每一個用戶要開辟一片EEPROM來存儲用戶信息。其具體分布如表1所示。
?
??? 在主機SERVER端，每個用戶CLIENT都需要有16bits的存儲空間。所以本系統共可接收511個用戶的信息。整個系統的設計充分考慮系統的升級和功能的擴展。其中出廠密鑰、序列號、加密密鑰、隨機數均可按需要進行擴展或縮減。如果從安全角度考慮，可把序列號存放在微處理器的ROM中。
3.1? 學習過程
??? 所謂學習，就是使用戶在主機端中注冊登記的過程。引進隨機數RANDOM，對每一次學習來說，它所產生的隨機數是不一樣的，它所發送的數據也是變化的、不可預知的，提高了安全性。另外，RANDOM和序列號SN、出廠密鑰MKEY一起生成加解密密鑰EN_KEY，使得EN_KEY不再依賴于出廠密鑰MKEY,用戶可以隨時對加解密密鑰EN_KEY進行修改，這樣也提高了安全性。
??? 進入學習模式后，用戶端經三次數據發送完成整個學習。過程如下：
??? (1)用戶端產生隨機數RANDOM，與MKEY、SN經加密后發送。主機接收到數據解密后，比對MKEY和SN，確認用戶是本系統用戶（比對MKEY）并且是一個新用戶（SN不在EEPROM中）時，開辟空間，保存SN和RANDOM。
??? (2)用戶端和主機端分別利用密鑰生成算法生成，由MKEY+SN+RANDOM生成EN_KEY，并存入相應的存儲空間。
??? (3)用戶端利用EN_KEY對SN、RANDOM、SYNC、MKEY進行KEELOQ加密并發送。主機接收到數據后，比對MKEY、RANDOM、SN正確后把SYNC存入相應空間，請求第二次發送（只雙向通信中才有請求功能）。
??? (4)用戶端收到發送請求后（如果是單向通信，則等待后直接發送）再對SN、RANDOM、SYNC、MKEY加密后發送。因為SYNC是每次改變的，所以這次數據位和上一次發送的數據位改變在50%以上。
??? (5)主機在接收到數據解密后，比對同步碼SYNC，如果用戶和主機的同步碼變化規律相同則學習成功。
??? 三次發送即完成一次學習過程。第二次學習時隨機數重新產生，所以要求學習時三次數據發送是連續的，否則無效。以上各步中有任何一次數據比對失敗則學習失敗。主機端在前二次接收到數據后等待24s仍未見用戶發送數據則學習失敗。學習失敗后用戶需重新學習。
??? 隨機數則利用單片機的計數器產生，有兩種方法供選用：
??? (1)單次操作完畢后，單片機的計數器一直不停地計數，在外界對它進行再次操作或者要發送數據時停止計數。因為外界的操作或發送的時間是不定的，所以計數寄存器里面的數是隨機的。
??? (2)可以對按鍵或操作時間進行計時。用戶每次按鍵或操作的時間都是不定的，并且按鍵從抖動到穩定的時間也是不定的，對它進行計時，如果把間隔的時間取得合適，即可得到近似隨機數。
3.2? 發送過程
??? 在數據發送前，必須先對數據進行加密。數據加密的過程如下：
??? (1)重新定制非線性表。原算法是用64位密鑰去加密32位的明碼數據，現在把它改為64位密鑰去加密64位的明碼數據，密文長度也為64位，可按原規律擴展非線性表即可。
??? (2)對數據進行分組。盡管應用場合針對小型系統（數據傳輸量較?。?，但還是必須對所要加密的數據進行分組。在使用分組時，對明文尾部不滿一個整組的碎片采用填充隨機數的辦法將其擴充為一個整組，然后進行正常加密。即數據分組長度、密鑰長度和輸出密文長度均為64位。
??? (3)把同步碼的變化反映到各組數據中。同步碼每次發送時均會改變，它是保證系統每次發送的密文都不一樣的根本。只需進行分配、疊代、移位、異或等簡單的變換即可完成反映的任務。
??? (4)封裝算法。算法經封裝后可方便地被各種程序調用。算法的入口參數有三個：EN_KEY、Data、Mode。其中EN_KEY為64位的加密密鑰；Data為64位被加密或被解密的數據；Mode為工作方式，有加密或解密兩種。
??? HCS300芯片發送的數據主要由固定碼和加密碼組成。固定碼34bit，加密碼32bit。固定碼主要由28位序列號、4位功能碼（按鍵信息）和2位標志組成。加密碼則由16位同步碼、28位序列號(可擴展)、4位功能碼組成。經改進后可用于數據加密的格式如圖2所示。
?
圖2 數據發送格式
?
??? 在發送時還要加入檢錯和糾錯功能。檢錯視系統的要求可選奇偶校驗、CRC校驗等。糾錯可以用漢明碼。該碼的實現原理是在數據中加入幾個校驗位，并把數據的每個二進制位分配在幾個奇偶校驗組中；當某位出錯后，就會引起有關的幾個校驗組的值發生變化。這不但可以發現錯誤，還能指出哪一位，為自動糾錯提供了依據。
3.3? 接收過程
??? 改進算法的解密密鑰由學習時接收并存儲在EEPROM中。其加密和解密的密鑰是一樣的，解密是加密的逆過程。接收過程主要包括序列號搜索、比對、解密、同步碼的比對等過程。接收方的程序流程如圖3所示。
?
?
??? 本文提出的基于KEELOQ技術的改進加密算法及其在單片機中的實現技術，可以節約硬件成本，減少對硬件的依賴，改善系統性能，擴展了在數據加密領域的應用，特別適合應用于無線傳輸領域的小型系統的數據加密。隨著射頻技術、無線技術和藍牙技術的發展，射頻卡身份證的實施，其應用領域可以擴展到身份識別、安全管理、防盜報警、考勤、收費、無線抄表、智能監控、隨機檢測器、標識信息等諸多領域。
參考文獻
1 賈 晶. 信息系統的安全與保密．北京：清華大學出版社，1999
2 岳云天, 郁 濱. 一種基于加密算法的編解碼IC的安全機制. 電子技術, 2002；29（7）
3 KEELOQ Code Hooping Encode.? Microchip Technology Inc,?2000
4 李福平, 金偉正, 鄧德祥.? KEELOQ技術的軟件實現. 電子技術應用,2002;28(6)
5 Bruce Schneier著, 吳世忠譯. 密碼學-協議、算法與C源程序．北京：機械工業出版社，2000
6 胡漢才. 單片機原理及其接口技術. 北京： 清華大學出版社，1996