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