无钥匙进入系统中HITAG2加密算法研究

张海峰，杨伟锋，胡正勇

(1.杭州电子科技大学电子信息学院，浙江 杭州 310018;2.浙江华城技术研究所，浙江 杭州 310013)

无钥匙进入系统中HITAG2加密算法研究

张海峰1，杨伟锋1，胡正勇2

(1.杭州电子科技大学电子信息学院，浙江 杭州 310018;2.浙江华城技术研究所，浙江 杭州 310013)

从数学的角度对无钥匙进入系统中的HITAG2加密算法进行了理论分析和推导.分析了HITAG2加密算法中的线性反馈移位寄存器和非线性滤波函数，由反馈函数和非线性滤波函数推导出在任意时刻加密器的各自状态.采用NXP公司自带HITAG2加密算法的PCF7952单片机进行数据加密，并在Mega168上编写HITAG2加密算法软件进行算法验证.通过研究提升了该算法的应用空间.

无钥匙进入系统；线性反馈移位寄存器；HITAG2；非线性滤波

0 引 言

HITAG2加密算法是应用在汽车无钥匙进入系统(Passive Keyless Entry，PKE)的一种保证汽车安全的主流算法.2003年，NXP公司推出的无钥匙进入系统中首次使用了HITAG2加密技术，但由于技术的保密性使得在实际应用中只能依靠NXP提供的带有硬件加密的芯片和软件加密库实现，限制了该技术的应用.文献[1-3]经过实际分析和试验，计算得到了HITAG2加密算法中的线性反馈函数和非线性滤波函数.本文采用数学分析的方法对HITAG2加密算法进行了理论计算和数学推导，并计算出任意时刻HITAG2加密器的状态值的数学表示形式.为验证HITAG2加密算法数学分析的正确性，设计了相应的无钥匙进入系统的硬件电路，采用NXP公司的PCF7952单片机进行数据加密，由HITAG2加密算法的数学计算得到的结果，设计编写相应的HITAG2软件实现代码进行验证.通过对HIAGT2加密算法的分析和验证，使得在以后的应用中可以不必再局限于使用现成的硬件加密芯片和软件库.

1 无钥匙进入系统的通信机制

无钥匙进入系统PKE由一个读卡器和若干的应答器组成.初次使用时，读卡器和应答器之间要先有一个相互认证的过程，认证的通信过程数据不加密.主要目的是使读卡器获得应答器的ID号，每个应答器有各自唯一的ID号，保证了通信中的防碰撞.认证完成后，读卡器就能识别该应答器，之后的通信过程都采用经HTIAG2加密的数据，以保证通信的安全.

2 HITAG2加密算法分析

2.1 HITAG2加密器组成

HITAG2加密器的结构如图1所示.当应答器和读卡器之间经过成功认证之后，两个设备之间的通信方式进入加密模式.在加密模式下，读卡器和应答器之间的通信数据都采用经HITAG2加密的数据，保证了通信的安全.HITAG2加密单元主要由一个48位的线性反馈移位寄存器(LFSR)和一个非线性滤波函数f组成，其结构如图1所示.在每个时钟周期下，线性反馈移位寄存器(LFSR)的20位输出通过非线性滤波函数的计算，生成一位密码，然后LFSR中的数据左移一位，同时LFSR的第48位由上一步生成的一位密码、设备ID号和密钥经过计算得到.

图1 HITAG2加密器的结构

线性反馈移位寄存器给定前一状态的输出，将该输出的线性函数再用作输入，是比较常用的序列生成器，其结构简单，生成的序列具有非常好的编码和密码性质，而且在软件和硬件上都很容易实现[4].设St-1=(st-1,st,…,st+n-2)，表示寄存器在t-1时刻的状态，则下一个状态为：

(1)

给定初始状态(s0,s1,…,sn-1)，则线性反馈移位寄存器生成的序列可以描述为：

(2)

即st+n+cn-1st+n-1+…+c0st=0,t=0,1,2,….

g(x)=x48+x47+x44+x31+x30+x27+x24+x23+x17+x9+x8+x7+x4+x3+x1+1.

(3)

g(x)以多项式的表示形式，把这个多项式换算成布尔函数的表示形式：

L(x0…x47)∶=x0⊕x2⊕x3⊕x6⊕x7⊕x8⊕x16⊕x22⊕x23⊕x26⊕x30⊕x41⊕x43⊕x46⊕x47.

(4)

当已知初始序列S0(x0,…,x47)的状态值，就可以通过L(x0，…，x47)计算出t时刻的序列值St(x0,…,x47).

非线性滤波函数f由3个不同的函数结构fa，fb和fc组成，每个函数输出1位数据.在每次计算的过程中这个滤波函数中的fa和fb要使用多次，这2个函数都有4个输入变量，1个输出位，经过2次的fa使用和3次的fb计算共输出5 bit当作fc的输入变量，而fa，fb输入来源于线性反馈移位寄存器.fc接收来自fa和fb的5 bit变量，在每个时钟周期输出1位，经过32个时钟周期的输出就得到加密后的数据.对非线性滤波函数的定义如下：

(5)

其中，fa(i)=(0x2C79)，fb(i)=(0x6671)，fc(i)=(0x7907287B).

以fa(i)=(0x2C79)为例说明该函数的计算过程，fa的4个bit变量(x1,x2,x3,x4)组成一个16进制的变量i，fa(i)的输出结果就是选取0x2C79在第i位的值.

2.2HITAG2加密算法数学推导

加密器的48位线性反馈移位寄存器(LFSR)的初始值由32位的应答器ID号和48位密钥的低16位组合而成，中间状态随着每个时钟信号的到来都在改变，改变后的值由上一状态的值移位和新的位的注入组成，具体如图1所示.为了表示加密器每个时刻的状态值作如下定义：

48位密钥表示为k，且k=k0…k47∈(是有限域2上的一个n维向量空间)，32位应答器的ID号表示为id，id=id0…id31∈位随机码表示为nR，nR=nR0…nR32∈，读卡器的响应用aR表示，aR=aR0…aR31∈，应答器响应用aT表示，aT=aT0…aT31∈，输出密码流在i时刻的状态位为bi，bi=f(ai…ai+47)∀i∈N.由上面计算出的线性反馈移位寄存器的布尔函数表达式L(x0…x47)可以计算出在i时刻LFSR的中间状态值αi=ai…ai+47∈，结果如下：

ai∶=idi， ∀i∈[0,31]，

a32+i∶=ki， ∀i∈[0,15]，

a48+i∶=k16+i⊕nRi⊕bi， ∀i∈[0,31]，

a80+i∶=L(a32+i…a79+i)， ∀i∈N.

(6)

设{aR}i表示读卡器响应aR在第i位的值，{aT}i表示应答器响应aT在第i位的值，则{aR}i和{aT}i的计算表示为：

{aR}i∶=aRi⊕b32+i， ∀i∈[0,31]，

{aT}i∶=aTi⊕b64+i， ∀i∈[0,31].

(7)

通过对{aR}i和{aT}i的重新排列就是经过加密后的数据.具体就是每8 bit经过反转输出1个字节的数据，在实际的通信过程中本文使用了4个字节的数据.

3 HITAG2算法验证

为了验证算法的正确性，本文设计了相应的硬件电路，包括了基站和应答器之间的通信和各自的设计框图，如图2所示.

图2 硬件系统设计框图

整个系统由两部分组成，基站采用Mega168微控制器作为控制单元，对算法的验证由该控制器实现.对应的应答器(Tag)使用NXP公司的PCF7952单片机，该单片机是NXP公司推出的应用于PKE系统的一个芯片，内部自带计算单元，在硬件上实现了HITAG2算法，对数据进行加密.PKE的基本通信流程如图3所示.

图3 PKE基本通信流程

首先约定一个双方都知道的48bit密钥key，这里令key为0x4F4E4D494B52，这个密钥分别存储在基站和和钥匙各自的内部Flash中，之后就可以开始数据的通信，第一步是认证过程，基站按下学习按键后，发送数据(0xFFFFFFF0)给Tag应答器，应答器唤醒之后通过UHF发送自身的ID号给基站，基站接收到应答器的ID号之后存储.认证学习之后双方的通信过程就采用加密的方式进行，认证学习只进行一次.

在认证学习之后，当按下识别按键后就开始HITAG2算法验证，学习中基站已经知道了应答器的ID号，通过基站发送应答器的ID号来唤醒该应答器，然后发送32位随机码给应答器.应答器接收到ID号后唤醒自身的CPU工作，CPU单元存储32位随机码，然后将32位随机码、自身的32位ID号和48位密钥key送入计算单元进行加密，然后通过433MHz的天线将加密后的数据发送给基站.由于基站中也存有随机码、ID号和密钥key，将这3组数据送入编写的HITAG2算法函数，计算出加密后的数据，然后将计算出的数据和从应答器接收到的数据进行比较，如相同则表示算法正确.

表1列出了在PC机上通过该算法计算的不同密钥、ID和随机码的计算结果.

表1 PC机运行结果

从表1的数据可以看出，在通信过程中，密钥、ID、随机码这3个要素中只要有1个不同，经过加密计算得到的结果就有很大差别.实际应用中，每把钥匙都有自己的固定ID，密钥事先约定，每次的通信过程中发送的随机码都不相同，所以，通过截获一定数量的数据样本发现数据规律，从而破解数据是不可能的，这说明了通信是安全的.

4 结束语

本文对HITAG2加密算法进行了数学分析和实际验证.基站和钥匙的双向通信机制和复杂的HITAG2加密算法保证了通信的安全.但HITAG2算法的设计结构也有一定的缺陷，如移位寄存器的位数相对较少，滤波函数的的深度(层级)较低，因此在这些方面的扩展研究将进一步加强本文算法的安全级别.

[1]ROYD,DATTAP,MUKHOPADHYAYS.AlgebraiccryptanalysisofstreamciphersusingdecompositionofBooleanfunction[J].JournalofAppliedMathematicsandComputing, 2015, 49(1/2): 397-417.

[2]VERDULTR,GARCIAFD,BALASCHJ.Gonein360seconds:HijackingwithHitag2[C]//Presentedaspartofthe21stUSENIXSecuritySymposium(USENIXSecurity12), 2012: 237-252.

[3]HAZAYC,LPEZ-ALTA,WEEH,etal.Leakage-ResilientCryptographyfromMinimalAssumptions[J].JournalofCryptology, 2016, 29(3): 514-551.

[4]阚海斌，彭杰王启春.安全的布尔函数构造[M].北京：科学出版社，2014：2-3.

[5]赵竞.Mifare非接触式IC卡安全性分析[D].杭州：杭州电子科技大学，2012.

[6]全祯业.PEPS系统的安全与可靠性研究[D].贵阳：贵州大学，2015.

HITAG2 Encryption Algorithm Based on the Keyless Entry System

ZHANG Haifeng1, YANG Weifeng1, HU Zhengyong2

(1.SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China; 2.ZhejiangHuachengTechnologyResearchInstitute,HangzhouZhejiang310012,China)

This paper analyzed and deduced the HITAG2 encryption algorithms which are commonly used in keyless entry system, and analyzed two important components of HITAG2 encryption algorithm: linear feedback shift register and nonlinear filtering functions. The respective status of encryptor at any time was derived. In order to verify the correctness of this HITAG2 encryption algorithm, it designed the corresponding hardware circuit, using a controller with HITAG2 encryption algorithm PCF7952(manufactured by NXP) encrypted those data, and writing a software which run in the Mega128 microcontroller.

passive keyless entry; linear feedback shift register; HITAG2; nonlinear filtering function

10.13954/j.cnki.hdu.2017.01.005

2016-07-05

张海峰(1961-)，男，浙江台州人，副教授，数字控制技术.

TP309.7

A

1001-9146(2017)01-0020-05