KeeLoq算法深入剖析
1 KeeLoq算法介绍
1.1 KeeLoq运算规则
KeeLoq算法的核心思想就是用8byte密钥加密4byte明文，从而得到4byte密文或者用8byte密钥解密4byte密文，还原出原4byte明文。KeeLoq算法演算过程需要定义一个数据寄存器，用于存放4byte明文y31~0或者4byte密文y31~0，和一个密钥寄存器，用于存放8byte密钥k63~0。
KeeLoq数据加密过程模型图如图1所示，首先定义一个非线性表，这个非线性表有5bits输入码，1bit输出码。它在数据寄存器中间隔均匀地取5bits: y31、y26、y20、y9、y1，通过NLF（Nonlinear Logic Function）运算产生一个输出码。输出码再与数据寄存器中的y16与y0以及密钥寄存器中的k0进行异或运算后生成1bit加密数据码。每生成1bit加密数据码，密钥寄存器和数据寄存器分别进行移位，密钥寄存器作循环移位，加密数据码作为数据寄存器移位的输入，重复上述步骤528次后，得到4byte的输出密文。
NLF(x4,x3,x2,x1,x0)=x4x3x2^x4x3x1^x4x2x0^x4x1x0^x4x2^x4x0^x3x2^x3x0^x2x1^x1x0^x1^x0
图1 KeeLoq加密模型图
KeeLoq数据解密模型图如图2所示，其过程的运算方法与数据加密过程的运算方法基本一致，只是其中运算数据数据位发生变化。非线性表的5bits输入码改成从数据寄存器中间隔均匀地取固定5bits:y30、y25、y19、y8、y0。产生1bit输出码后输出码再与数据寄存器中的y31与y15以及密钥寄存器中的k15进行异或运算后生成1bit解密数据码。每输出1bit解密数据码后，密钥寄存器和数据寄存器分别进行移位，密钥寄存器作循环移位，解密数据码作为数据寄存器移位的输入，重复上述步骤528次后，还原出4byte的明文。
图2 KeeLoq解密模型图
1.2 KeeLoq实现机制
采用KeeLoq方法实现数据编码和解码，其通信过程需严格按照下述过程进行。首先，要求编码端和解码端都需要有非易失性存储空间以存储8byte密钥(用于编解码，可编程且不被发送不可泄露)、3byte序列号(用于区分不同的编码端)、2byte同步计数值(用于产生编码滚动效果，每完成一次数据传送后，其值自加1后更新)、1byte识别码（序列号的低1byte）和4byte种子码（安全模式下用来生成密钥）。
当用户有按键操作时，KeeLoq编码端将1byte功能键、1byte识别码、2byte同步计数值组合成4byte明文，按照图1的NLF运算规则加密成4byte密文，再加上4byte固定码（3byte序列号、1byte功能键），组合成一组8byte的编码数据发送。由于每次发送过程，同步计数值自加1，使得每次发送的4byte密文都是惟一的、不规则的、且不重复，故称之为滚动码，可以有效的防止密码捕捉和密码拷贝。由于8byte的编码组合达到2^64=1.84*10^19，因而可以有效的防止密码扫描。
解码端接收到8byte密文数据后，首先匹配编码端和解码段的3byte序列号一致后，按照图2的KeeLoq解码运算规则还原出4byte明文。再校验明文中的识别码以及功能键正确后，最后判断同步计数值是否合理增加。确认成功后根据功能键定义，控制相应执行机构动作。
2 KeeLoq算法不足与改进
2.1 KeeLoq算法的安全性与不足
KeeLoq算法的NLF运算规则，使得一个很小的输入变化量，也会造成很大的输出变化量，产生的编码滚动效果。密码分析者就无法通过输入微小的变化来观察分析输出的变化，从而破解出密钥，使得KeeLoq算法具有安全性高特点。
虽然KeeLoq算法发布于20世纪80年代，但直到2007年，Bogdanov才首次对KeeLoq算法进行攻击，他使用猜测-决定和滑动技术来完成攻击，攻击的时间复杂度为252，空间复杂度为16GB。在2008年，Courtois等人提出了4种滑动-代数攻击方法，其主要思想是利用KeeLoq算法连续64圈圈函数形成的置换和圈结构与随机置换圈结构的差异，先攻击密钥的前16bits，再攻击剩余的48bits。折合计算复杂性至少约为O(2^43)次加密。2010年，游建雄等人提出3 种不同采用面向字节的差分故障攻击方法，其中攻击效率最好的方法，恢复1 bit 密钥信息平均只需要0. 707617 个错误，恢复8byte的密钥只需要46个错误。
虽然KeeLoq算法发布后至今已经取得很多有效的攻击，大大降低了计算时间复杂度，，但是也增加了计算空间复杂度，并且需要一定数量的已知前提。导致在实际密码破解过程中难度系数高，故其安全性足以保证，在实际应用当中有着广泛应用。
2.2 KeeLoq算法的改进
KeeLoq加密算法是4byte的分组密码，密钥长度较短，仅为8byte。算法发布至今已有相关文献报导取得有效攻击，针对这一现状及上述算法不足之处，为了进一步提高 KeeLoq算法安全性，本文分别对编解码过程及密钥管理进行改进。
2.2.1 编解码过程的改进
首先，编解码过程借鉴了三重数据加密算法（3DES，Triple Data Encryption Algorithm），提出三重KeeLoq算法。即采用三个不同密钥分别对明文、第一次获得密文及第二次获得密文进行KeeLoq加密后，生成最终密文。解密过程则是，先用第三个密钥对最终密文解密得到第二次密文，用第二个密钥对第二次密文解密得到第一次密文，最后用第一个密钥对第一次密文解密得到原始明文。该过程是KeeLoq算法的一种更安全的变形，通过增加KeeLoq的密钥长度来提高针对KeeLoq攻击的时间复杂度和计算复杂度，以进一步提高其安全性。
2.2.2 KeeLoq密钥管理机制的改进
可以有一个人陪着你，也可以你一个人，总之那一刻，
