一種基于KEELOQ的改進(jìn)加密算法及其在單片機(jī)中的實(shí)現(xiàn)技術(shù)

摘要：討論了Microchip公司的KEELOQ加解密算法的實(shí)現(xiàn)機(jī)制，通過(guò)引入隨隨機(jī)數(shù)，提出了一種新的改進(jìn)算法，并給出了其在單片機(jī)中的實(shí)現(xiàn)方案。該算法具有簡(jiǎn)單實(shí)用、所需硬件資源少、傳輸效率和安全性相對(duì)較高等優(yōu)點(diǎn)，適用于需要數(shù)據(jù)加密的小型無(wú)線數(shù)據(jù)傳輸系統(tǒng)，具有廣闊的應(yīng)用前景。 關(guān)鍵詞：加密算法 KEELOQ 單片機(jī) 跳碼技術(shù) 當(dāng)今的編解碼電路已經(jīng)朝著高度集成化和微電腦化發(fā)展。像普通的固定編解碼芯片和MC145026/145027、PT2262/2272等已被廣泛應(yīng)用于公用系統(tǒng)中，給生活帶來(lái)了方便。然而這些芯片不能保證系統(tǒng)的安全性。由于這些系統(tǒng)每次發(fā)送的數(shù)據(jù)流一模一樣，只是高低電平的組合，第三方面通過(guò)捕捉設(shè)備，一旦用戶信號(hào)出現(xiàn)，便可瞬間取得合法的身份識(shí)別碼;或使用編碼掃描設(shè)備，主動(dòng)攻擊解碼芯片。因此保證系統(tǒng)的安全性是一個(gè)很現(xiàn)實(shí)的問(wèn)題。在此背景下，基于加密算法的編解碼IC的安全機(jī)制得到了應(yīng)用。Microchip公司的KEELOQ技術(shù)是這種技術(shù)的代表。KEELOQ技術(shù)是一種多變化、抗截獲得、安全可靠性高的非線性跳碼加密解密技術(shù)。KEELOQ目前是通過(guò)硬件芯片IC(以Mirochip公司的HCS300為代表)實(shí)現(xiàn)，主要應(yīng)用于汽車陣盜系統(tǒng)和門(mén)禁系統(tǒng)，是無(wú)鑰進(jìn)入系統(tǒng)領(lǐng)域的首選芯片。但也由于硬件芯片本身的限制(其所能加密的數(shù)據(jù)必須預(yù)先寫(xiě)入EEPROM中)，使之很難用于其它(如數(shù)據(jù)加密)領(lǐng)域。 本文把這項(xiàng)封裝在芯片里的KEELOQ加密技術(shù)用軟件方式實(shí)現(xiàn)，并針對(duì)單片機(jī)的特性進(jìn)行了適當(dāng)改進(jìn)。這種在單片機(jī)中實(shí)現(xiàn)的改進(jìn)算法不僅包含了原來(lái) HCS300所具備的所有功能，而且在系統(tǒng)安全性、靈活性、可擴(kuò)展性、傳輸效率等方面均有較大改善，同時(shí)對(duì)改進(jìn)算法在數(shù)據(jù)加密領(lǐng)域作為全新的嘗試，以其特殊的密鑰管理方法獨(dú)立于對(duì)稱型加密(如DES)與不對(duì)稱型加密算法(即公開(kāi)密鑰體制，如RSA)，成為一種適用于無(wú)線傳輸領(lǐng)域小型系統(tǒng)的數(shù)據(jù)加密算法。

1 KEELOQ技術(shù)簡(jiǎn)介及其硬件實(shí)現(xiàn) KEELOQ技術(shù)的核心思想是用64bit的EN_KEY[64:0](加密密鑰)去加密32bit的CSR[31:0](校驗(yàn)碼)得到32bit的 CRYP密文。加密機(jī)制為：首先定義一個(gè)非線性表，這個(gè)非線性表有5位輸入NLF_IN[4:0]，一位輸出NLF_OUT。它在CSR[31:0]中間隔均勻地取固定5位：I0、I1、I2、I3、I4，通過(guò)非線性產(chǎn)生一個(gè)輸出碼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密文也會(huì)有50%以上的數(shù)據(jù)位(16bit)發(fā)生變化。 Microchip公司以KEELOQ技術(shù)為基礎(chǔ)開(kāi)發(fā)了滾動(dòng)碼系統(tǒng)專用芯片，HCS300是其中較典型的一款。它是一塊8引腳的編碼IC芯片，里面集成了 KEELOQ算法和其他一些功能，帶有四個(gè)按鍵接口，實(shí)現(xiàn)15位的功能/命令碼。內(nèi)置192bits(12%26;#215;16bit words)EEPROM，用來(lái)存放EN_KEY(加密密鑰)、SN(序列號(hào))、SYNC(同步碼)、SEED(種子碼)等。序列號(hào)用來(lái)標(biāo)識(shí)不同的對(duì)象;加密密鑰用來(lái)對(duì)發(fā)送的數(shù)據(jù)進(jìn)行加密，增加破譯的難度，它不直接發(fā)送出去;同步計(jì)數(shù)器用來(lái)抗截獲，每次發(fā)送數(shù)據(jù)時(shí)，同步計(jì)數(shù)器的值都被更新，所以每次發(fā)送的數(shù)據(jù)都不一樣。種子碼用于安全學(xué)習(xí)時(shí)參與加密密鑰的生成。接收方必須先通過(guò)學(xué)習(xí)來(lái)獲得并存儲(chǔ)發(fā)送方的序列號(hào)、加解密密鑰和當(dāng)前同步計(jì)數(shù)器的值。學(xué)習(xí)相當(dāng)于身份確認(rèn)，只有經(jīng)過(guò)學(xué)習(xí)的用戶才能與主機(jī)通信。主機(jī)在接收到信號(hào)后，首先比對(duì)序列號(hào)，然后利用學(xué)習(xí)過(guò)程中得到并存儲(chǔ)的加密密鑰對(duì)接收的數(shù)據(jù)進(jìn)行解密;接著檢查同步計(jì)數(shù)器是否匹配，在確認(rèn)其匹配后，再去處理接收到的按鍵信令，并根據(jù)接收到的按鍵信令作出相應(yīng)的動(dòng)作反應(yīng)。HCS300的系統(tǒng)使每次發(fā)送的密文都不相同，有效防止了空中截獲法和數(shù)據(jù)重傳帶來(lái)的安全隱患。 HCS300系統(tǒng)的加密密鑰在學(xué)習(xí)過(guò)程中經(jīng)密鑰生成算法產(chǎn)生。學(xué)習(xí)分為一般學(xué)習(xí)和安全學(xué)習(xí)。一般模式下，解密解鑰由MKEY和SN生成加解密密鑰 EN_KEY，其解密密鑰隱含于發(fā)送信息(MKEY和SN)中。安全模式下，增加了種子碼SEED(當(dāng)四鍵一起按時(shí)發(fā)送)，它與MKEY和SN一起生成加解密密鑰EN_KEY，而SEED_KEY在平時(shí)并不發(fā)送，這樣增加了安全性。不過(guò)，在學(xué)習(xí)時(shí)SEED碼的發(fā)送是不經(jīng)過(guò)加密的。 2 KEELOQ技術(shù)的不足與改進(jìn)加密算法的提出 盡管KEELOQ技術(shù)有上述獨(dú)特的優(yōu)點(diǎn)，但是經(jīng)過(guò)深入分析不難發(fā)現(xiàn)KEELOQ算法及其硬件實(shí)現(xiàn)技術(shù)也存在一些不足： (1)安全性基于出廠密鑰和種碼SEED。在HCS300芯片中，加密密鑰EN_KEY是由出廠密鑰MKEY、序列號(hào)SN和種子碼SEED(安全模式)生成的。而SN和SEED在發(fā)送數(shù)據(jù)的過(guò)程中未經(jīng)加密，是可截獲的。理論上出廠密鑰一經(jīng)確定一般不會(huì)更改。所以，一旦出廠密鑰外泄，后果極其嚴(yán)重。 (2)擴(kuò)展功能弱、升級(jí)不方便。其算法由硬件芯片實(shí)現(xiàn)。其所能實(shí)現(xiàn)的功能由按鍵決定。其按鍵只有4個(gè)，最多也只有15種組合。發(fā)送方無(wú)法附加其余的信息(對(duì)于大多領(lǐng)域來(lái)說(shuō)，它要求能發(fā)送一些附加信息，如用戶的姓名、年齡、出生日期等)，功能擴(kuò)展幾乎不可能。另外，某一特定型號(hào)的芯片其序列號(hào)和同步計(jì)數(shù)器的長(zhǎng)度是固定的。當(dāng)系統(tǒng)建成后，開(kāi)發(fā)者如果想只通過(guò)軟件升級(jí)來(lái)擴(kuò)充系統(tǒng)的容量或提高系統(tǒng)的性能、用硬件實(shí)現(xiàn)技術(shù)基本不可能。 (3)對(duì)功能碼的檢錯(cuò)和糾錯(cuò)的功能較弱。在無(wú)線傳輸中，出現(xiàn)誤碼的概率比較大。功能碼代表所要實(shí)現(xiàn)的功能，如開(kāi)門(mén)、報(bào)警、開(kāi)閥等。如果發(fā)送的數(shù)據(jù)是 0010，而接收的數(shù)據(jù)為0100，其后果非常嚴(yán)重。 (4)傳輸效率較低。在發(fā)送的數(shù)據(jù)中，其有用信息(如序列號(hào)、功能碼)全部在固定碼中，加密碼只作為一種加密用的附加數(shù)據(jù)，這樣不但降低了安全性，而且傳輸效率不高。以HCS300為例，發(fā)送的66位數(shù)據(jù)中只有32位為有用信息，傳輸效率比較低。

(5)無(wú)法用于數(shù)據(jù)加密。由于其是由硬件芯片實(shí)現(xiàn)的，它所能加密的數(shù)據(jù)只限于序列號(hào)、同步碼等預(yù)先存在HCS300的EEPROM中的數(shù)據(jù)。它沒(méi)有數(shù)據(jù)入口，無(wú)法對(duì)數(shù)據(jù)流進(jìn)行加密。 (6)受硬件設(shè)計(jì)限制，靈活性差，成本較高，由于不擁有核心技術(shù)，容易受制于人。 基于上述分析，筆者結(jié)合單片機(jī)的特性，對(duì)KEELOQ算法提出如下改進(jìn)： (1)保留出廠密鑰，但引入隨機(jī)數(shù)，防止出廠密鑰和種碼的泄漏，用戶可隨時(shí)改變加密密鑰。 (2)改進(jìn)數(shù)據(jù)傳輸?shù)母袷剑淹酱a映射到各組待加密的數(shù)據(jù)中，提高傳輸效率。 (3)增加對(duì)功能碼或關(guān)鍵數(shù)據(jù)的檢錯(cuò)和糾錯(cuò)的功能。 (4)增加數(shù)據(jù)入口，改變對(duì)加密數(shù)據(jù)的長(zhǎng)度要求，使其適合批量的數(shù)據(jù)加密。 數(shù)據(jù)加密系統(tǒng)的兩個(gè)基本要素是加密算法和密鑰管理。密鑰是控制加密算法和解密算法的關(guān)鍵信息，其產(chǎn)生、傳輸、存儲(chǔ)等工作十分重要。目前數(shù)據(jù)加密技術(shù)可以分為二類，即對(duì)稱型加密、不對(duì)稱型加密。對(duì)稱型加密(如DES算法)使用單個(gè)密鑰對(duì)數(shù)據(jù)進(jìn)行加密或解密。不對(duì)稱型加密算法也稱公用密鑰算法(如RSA算法)，其特點(diǎn)是有二個(gè)密鑰(即公用密鑰和私有密鑰)，只有二者搭配使用才能完成加密和解密的全過(guò)程。便兩者都在密鑰的管理和分發(fā)上遇到一些困難。 KEELOQ密鑰管理機(jī)制的訂特別是對(duì)每個(gè)用戶都有自己獨(dú)特的加解密密鑰，在學(xué)習(xí)過(guò)程中發(fā)送到主機(jī)并保存。但密鑰信息隱含在每次發(fā)送的信息(SN和 MKEY)中(即使在安全模式下，種子碼SEED也是固定碼，可截獲)，并且依賴于生產(chǎn)廠家和出廠密鑰，不可更改。本改進(jìn)算法主要針對(duì)無(wú)線傳輸領(lǐng)域的小型系統(tǒng)，可以在學(xué)習(xí)過(guò)程中引入隨機(jī)參數(shù)RANDOM，與MKEY、SN一起生成EN_KEY。這個(gè)隨機(jī)數(shù)據(jù)RANDOM在同一次學(xué)習(xí)時(shí)相同，但每次學(xué)習(xí)時(shí)都會(huì)改變。這樣，加密密鑰就不依賴于生產(chǎn)廠家和出廠密鑰并且在用戶感到密鑰有可能泄漏時(shí)不隨時(shí)改變數(shù)據(jù)，增加了安全性。 3 改進(jìn)加密算法在單片機(jī)中的實(shí)現(xiàn) 整個(gè)系統(tǒng)分為用戶端(CLIENT)和主機(jī)端(SERVER)，系統(tǒng)框圖如圖1所示。在本系統(tǒng)中，考慮功耗、外圍功能等需要，選用飛利浦的LPC76X系列芯片。P87LPC764是20腳封裝的單片機(jī)，可以在寬范圍的性能要求下實(shí)現(xiàn)高集成度低成本的解決方案，4Kbits的ROM，32Byte用戶代碼區(qū)可用來(lái)存放序列碼及設(shè)置參數(shù)，內(nèi)帶看門(mén)狗定時(shí)器，處理器的指令執(zhí)行速度為標(biāo)準(zhǔn)80C51 MCU的兩倍。EEPROM發(fā)送部分選用AT2401(128%26;#215;8 bits)，接收部分選用AT2404(1024%26;#215;8bits)，8-DIP封裝，I2C總線接口，擦寫(xiě)次數(shù)>1百萬(wàn)次，保存時(shí)間>100年。 用戶必須經(jīng)過(guò)學(xué)習(xí)后才能與主機(jī)通信。在學(xué)習(xí)過(guò)程中，用戶把序旬號(hào)SN、出廠密鑰MKEY、加密密鑰EN_KEY送給主機(jī)，主機(jī)對(duì)每一個(gè)用戶要開(kāi)辟一片 EEPROM來(lái)存儲(chǔ)用戶信息。 在主機(jī)SERVER端，每個(gè)用戶CLIENT都需要有16bits的存儲(chǔ)空間。所以本系統(tǒng)共可接收511個(gè)用戶的信息。整個(gè)系統(tǒng)的設(shè)計(jì)充分考慮系統(tǒng)的升級(jí)和功能的擴(kuò)展。其中出廠密鑰、序列號(hào)、加密密鑰、隨機(jī)數(shù)均可按需要進(jìn)行擴(kuò)展或縮減。如果從安全角度考慮，可把序列號(hào)存放在微處理器的ROM中。 3.1 學(xué)習(xí)過(guò)程 所謂學(xué)習(xí)，就是使用戶在主機(jī)端中注冊(cè)登記的過(guò)程。引進(jìn)隨機(jī)數(shù)RANDOM，對(duì)每一次學(xué)習(xí)來(lái)說(shuō)，它所產(chǎn)生的隨機(jī)的數(shù)是不一樣的，它所發(fā)送的數(shù)據(jù)也是變化的、不可預(yù)知，提高了安全性。另外，RANDOM和序列號(hào)SN、出廠密鑰MKEY一起生成加解密密鑰EN_KEY，用戶可以隨時(shí)對(duì)加密密鑰EN_KEY進(jìn)行修改，這樣也提高了安全性。 進(jìn)入學(xué)習(xí)模式后，用戶端經(jīng)三次數(shù)據(jù)發(fā)送完成整個(gè)學(xué)習(xí)。過(guò)程如下： (1)用戶端產(chǎn)生隨機(jī)數(shù)RANDOM，與MKEY、SN經(jīng)加密后發(fā)送。主機(jī)接收到數(shù)據(jù)解密后，比對(duì)MKEY和SN，確認(rèn)用戶是本系統(tǒng)用戶(比對(duì)MKEY)并且是一個(gè)新用戶(SN不在EEPROM)時(shí)，開(kāi)辟空間，保存SN和RANDOM。 (2)用戶端和主機(jī)端分別利用密鑰生成算法生成，由MKEY+SN+RANDOM生成EN_KEY，并存入相應(yīng)的 存儲(chǔ)的空間。 (3)用戶端利用EN_KEY對(duì)SN、RANDOM、SYNC、MKEY進(jìn)行KEELOQ加密并發(fā)送。主機(jī)接收到數(shù)據(jù)后，比對(duì)MKEY、RANDOM、 SN正確后把SYNC存入相應(yīng)空間，請(qǐng)求第二次發(fā)送(只雙向通信中才有請(qǐng)求功能)。 (4)用戶端收到發(fā)送請(qǐng)求后(如果是單向通信，則等待后直接發(fā)送)再對(duì)SN、RANDOM、SYNC、MKEY加密后發(fā)送。因?yàn)镾YNC是每次改變的，所以這次數(shù)據(jù)位和上一次發(fā)送的數(shù)據(jù)位改變?cè)?0%以上。 (5)主機(jī)在接收到數(shù)據(jù)解密后，比對(duì)同步碼SYNC，如果用戶和主機(jī)的同步碼變化規(guī)律相同則學(xué)習(xí)成功。 三次發(fā)送即完成一次學(xué)習(xí)過(guò)程。第二次學(xué)習(xí)時(shí)隨機(jī)數(shù)重新產(chǎn)生，所以要求學(xué)習(xí)時(shí)三次數(shù)據(jù)發(fā)送是連續(xù)的，否則無(wú)效。以上各步中有任何一次數(shù)據(jù)比對(duì)挫敗則學(xué)習(xí)失敗。主機(jī)端在前二次接收到數(shù)據(jù)后等待24s仍未見(jiàn)用戶發(fā)送數(shù)據(jù)則學(xué)習(xí)失敗。學(xué)習(xí)挫敗后用戶重新學(xué)習(xí)。 隨機(jī)數(shù)利利用單片機(jī)的計(jì)數(shù)器產(chǎn)生，有兩種方法供選用：

(1)單次操作完畢后，單片機(jī)的計(jì)數(shù)器一直不停地計(jì)數(shù)，在外界對(duì)它進(jìn)行再次操作或者要發(fā)送數(shù)據(jù)時(shí)停止計(jì)數(shù)。因?yàn)橥饨绲牟僮骰虬l(fā)送的時(shí)間是不定的，所以計(jì)數(shù)寄存器里面的數(shù)是隨機(jī)的。 (2)可以對(duì)按鍵或操作時(shí)間進(jìn)行計(jì)時(shí)。用戶每次按鍵或操作的時(shí)間都是不定的，并且按鍵從抖動(dòng)到穩(wěn)定的時(shí)間也是不定的，對(duì)它進(jìn)行計(jì)時(shí)，如果把間隔的時(shí)間取得合適，即可得到近似隨機(jī)數(shù)。 3.2 發(fā)送過(guò)程 在數(shù)據(jù)發(fā)送前，必須先對(duì)數(shù)據(jù)進(jìn)行加密。數(shù)據(jù)加密的過(guò)程如下： (1)重新定制非線性表。原算法是用64位密鑰去加密32位的明碼數(shù)據(jù)，現(xiàn)在把它改為64位密鑰去加密64位的明碼數(shù)據(jù)，密文長(zhǎng)度也為64位，可按原規(guī)律擴(kuò)展非線性即可。 (2)對(duì)數(shù)據(jù)進(jìn)行分組。盡管應(yīng)用場(chǎng)合針對(duì)小型系統(tǒng)(數(shù)據(jù)傳輸量較小)，但還是必須對(duì)所要加密的數(shù)據(jù)進(jìn)行分組。在使用分組時(shí)，對(duì)明文尾部不滿一個(gè)整組的碎片采用填充隨機(jī)數(shù)的辦法將其擴(kuò)充為一個(gè)整組，然后進(jìn)行正常加密。即數(shù)據(jù)分組長(zhǎng)度、密鑰長(zhǎng)度和輸出密文長(zhǎng)度均為64位。 (3)把同步碼的變化反映到各組數(shù)據(jù)中。同步碼每次發(fā)送時(shí)均會(huì)改變，它是保證系統(tǒng)每次發(fā)送的密文都不一樣的根本。只需進(jìn)行分配、疊代、移位、異或等簡(jiǎn)單的變換即可完成反映的任務(wù)。 (4)封裝算法。算法經(jīng)封裝后可方便地被各種程序調(diào)用。算法的入口參數(shù)有三個(gè)：EN_KEY、Data、Mode。其中，EN_KEY為64位的加密密鑰;Data為64位被加密或被解密的數(shù)據(jù);Mode為工作方式，有加密或解密兩種。 HCS300芯片發(fā)送的數(shù)據(jù)主要由固定碼和加密碼組成。固定碼34bit，加密碼32bit。固定碼主要由28位序列號(hào)、4位功能碼(按鍵信息)和2位標(biāo)志組成。加密碼則由16位同步碼、28位序列號(hào)(可擴(kuò)展)、4位功能碼組成。經(jīng)改進(jìn)后可用于數(shù)據(jù)加密的格式如圖2所示。 在發(fā)送時(shí)還要加入檢錯(cuò)和糾錯(cuò)功能。檢錯(cuò)視系統(tǒng)的要求可選奇偶校驗(yàn)、CRC校驗(yàn)等。糾象牙可以用漢明碼。該碼的實(shí)現(xiàn)原理是在數(shù)據(jù)中加入幾個(gè)校驗(yàn)位，并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中;當(dāng)某位出錯(cuò)后，就會(huì)引起有關(guān)的幾個(gè)校驗(yàn)組的值發(fā)生變化。這不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出哪一位，為自動(dòng)糾錯(cuò)提供了依據(jù)。 3.3 接收過(guò)程 改進(jìn)算法的解密密鑰由學(xué)習(xí)時(shí)接收并存儲(chǔ)在EEPROM中。其加密和解密的密鑰是一樣的，解密是加密的逆過(guò)程。接收過(guò)程主要包括序列號(hào)搜索、比對(duì)、解密、同步碼的比對(duì)等過(guò)程。接收方的程序流程如圖3所示。 本文提出的基于KEELOQ技術(shù)的改進(jìn)加密算法及其在單片機(jī)中的實(shí)現(xiàn)技術(shù)，可以節(jié)約硬件成本，減少對(duì)硬件硬件的依賴，改善系統(tǒng)性能，擴(kuò)展了在數(shù)據(jù)加密領(lǐng)域的應(yīng)用，特別適合應(yīng)用于無(wú)線傳輸領(lǐng)域的小型系統(tǒng)的數(shù)據(jù)加密。隨著射頻技術(shù)、無(wú)線技術(shù)和藍(lán)牙技術(shù)的發(fā)展，射頻卡身份證的實(shí)施，其應(yīng)用領(lǐng)域可以擴(kuò)展到身份識(shí)別、安全管理、防盜報(bào)警、考勤、收費(fèi)、無(wú)線抄表、智能監(jiān)控、隨機(jī)檢測(cè)器、標(biāo)識(shí)信息等諸多領(lǐng)域。