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