登录
注册
一种基于零知识证明的RFID鉴别协议
作者：华强电子世界
来源：RFID世界网
日期：2007-03-01 10:18:28
摘要：身份鉴别是双向的，即RFID卡与终端要相互鉴别对方身份。目前，在RFID系统存在的安全问题(如保护消费者隐私权)中，攻击者所采用的主要攻击方式是对RFID卡信息的非法窃取，而不是伪造RFID卡，因此本文将研究重点放在RFID卡对终端的鉴别问题上。
1引 言
RFID技术是当前研究的一个热点，其采用无线信号进行无接触的双向信息传输，一方面具有极大的方便性和灵活性，另一方面增加了信息被窃取的风险。无线信道与具有保密性的有线信道不同，无线信道的一个特征是其公开性，任何人只要拥有相应频段的接收设备，就可以对无线信道进行监听，因此和有线信道相比，无线信道更容易被窃听而且不容易被发现。对于EPC(电子产品代码)Class0／O+标准中没有任何加密措施和鉴别机制的情况，已经引发了广泛的关于保护消费者隐私权的激烈讨论。而对于远作用距离的有源RFID系统，则具有更大的安全隐患。因此研究如何在RFID系统实现高效的身份鉴别是非常有必要的。
鉴别又叫认证，是用来证明某人或某事是否真实、可靠或者有效的过程，他通过验证称谓者的一个或多个参数的真实性或者有效性来达验证其是否名副其实的目的[1]。鉴别在现实生活中的形式多种多样，如对人的鉴别，一般通过口令或者人的生理特征(声音、指纹、视网膜等)进行鉴别。本文主要讨论RFID系统的鉴别，其鉴别的过程是基于零知识证明技术的。
身份鉴别是双向的，即RFID卡与终端要相互鉴别对方身份。目前，在RFID系统存在的安全问题(如保护消费者隐私权)中，攻击者所采用的主要攻击方式是对RFID卡信息的非法窃取，而不是伪造RFID卡，因此本文将研究重点放在RFID卡对终端的鉴别问题上。
2 目前常用的两种鉴别体制的缺陷
鉴别分为2种：对称鉴别和非对称鉴别。对称鉴别是指主机和称谓者预先共享了某个秘密信息，或者主机知道称谓者某个秘密信息的映象，主机通过验证称谓者是否知道这个秘密来达到鉴别的目的；非对称鉴别是指主机不知道称谓者用于证明其身份的某个秘密(包括秘密的映象)，而仅通过与称谓者的秘密对应的公开密钥来鉴别其真伪[2]。
2．1对称鉴别体制
在智能卡中应用较多的是对称鉴别体制，采用的是DES对称加密算法。在通之前，卡要对终端进行验证，对称鉴别速度较快，对智能卡的性能、资源要求较低，但是其在使用之前一般需要有一个集中的卡的发行过程，以便于密钥的分发，因此只能适合于比较单一的领域(或单一的人群)使用，如移动电话卡、银行卡等。对于更广泛的电子商务、物流管理来讲，非对称鉴别更适合，目前已经出现了一系列的基于智能卡的加密接口规范。
2．2非对称鉴别体制
非对称鉴别体制与对称鉴别体制相比具有更大的灵活性，他并未完全包括某一特定的密码算法，却经常以RSA算法为基础进行加工[3]。RSA算法是密码学理论上的一个重大突破，他成功地解决了密钥分发的问题，但在实际应用中却存在以下困难：
(1)RSA算法的保密强度是建立在特定的数学问题求解的困难性上的，他可以表示成简单的数学公式，然而随着数学的发展，许多现在看来难以解决的问题可能在不久的将来会得到解决，而诸如DES之类的对称密码算法则难以表示成一个确定的数学形式，其保密强度因此相应地要高。
(2)RSA算法中密钥的生成较对称密码体制而言要复杂得多，特是大素数p和q的生成比较复杂。倘若一个电子标签应用系统中只采用一对p和q，一旦他们被泄密，则整个密码系统失效；而若每个电子标签采用不同的p和q，则p和q的生成任务极其繁重。
(3)受电子标签资源的限制，在电子标签中实现RSA算法非常困难，主要是实现RSA算法中的大数乘方取模比较困难，即使能实现，其速度往往比较慢，而对于电子标签而言，其操作或交易都是在非常短的时间内完成的，如门禁系统、车辆管控系统等。因此RSA算法有时不符合某些电子标签及其应用的要求，除非电子标签有对大数乘方取模操作的硬件支持，但这又带来了电子标签的成本较高，用户难以接受的问题。
(4)对于RFID系统而言，无源电子标签本身没有电源，只能从射频信号中提取能量，因此其功率必然受到一定的限制，难以完成像RSA这样复杂的算法；而对于有源的电子标签，依靠自身电池提供能量，可以完成此算法，但会严重影响其使用寿命。
3 新型的零知识鉴别协议
在实际生活中，A要向B证明他知道某秘密的常用方法是把他知道的秘密告诉B，但这样一来B就知道了这个秘密。如何在不告诉B这个秘密的情况下使B相信A知道这个秘密，就是零知识证明要解决的问题。有了零知识证明，A就可以不公布秘密，却能使任何人相信他知道这个秘密。零知识证明可以使研究人员向世人证明他知道一个特殊定理的证明方法但又不泄漏证明，这种方法在商业上也有许多用途。零知识证明的研究受到各国研究人员的重视，在国际上一直很活跃，基本的零知识证明算法基于同构图和汉密尔顿回路"[4]。
所谓的零知识鉴别协议是指一个证明者P是一个具有无限计算能力的图灵机，向一个仅具有多项式计算能力的图灵机(验证者)V证明他宣称的一个结论是正确的，在此过程中，验证者V除了相信P的宣称以外，得不到其他额外的信息，允许P，V违背协议[5]。
严格地讲，假设P，V是两个概率图灵机，P有无限的计算能力，V的计算能力是多项式的，若一个证明协议满足以下3点，就称此协议为一个零知识证明协议[6]：
完备性 如果P的声称是真的，则V以绝对优势的概率接受P的结论；
有效性 如果P的声称是假的，则V以绝对优势的概率拒绝P的结论；
零知识性 无论V采取任何手段，当P的声称是真的，并且不违背协议时，V除了接受P的结论以外，得不到其他额外的信息。
这一概念产生之后，关于他的理论和实际应用方面的研究立刻全面展开。零知识证明系统已逐渐形成一个体系，他象单向函数、单向陷门函数以及伪随机数发生器一样，成为构造安全密码系统的基本方法之一。零知识交互式证明系统在身份验证、数字签名和抗选择密文攻击等方面获得了广泛的应用，使用零知识交互式证明的身份验证模式比使用RSA的执行速度要快得多[7]。
Feige-Fiat-Shamir算法是第一个基于零知识证明的算法，他出现于上个世纪80年代。2000年，Nyang和Song提出了一个应用于智能卡的基于零知识证明和身份认证协议，从此关于零知识证明的应用研究广泛展开。
目前有一种有效的零知识鉴别协议可应用于RFID统，该协议是以离散对数为基础的，离散对数是现代密码学常用的重要的单向函数，其特点之一是只需较小的通信量和计算量。
假设P是一个素数，Zp是整数环模p，定义Kp是p-1最大的除数，他的素因子至少为v=[log2p]。
我们将考虑语言集L，他的元素是串a=(I；β，p)，而β是串Znp=Zp／{O}，βkp 1(mod p),I∈Znp是I·βs
1(mod p)，对于所有的s∈Zp-1，有L={(I；β，p)│p是一个素数，β，I∈Z*p；βkp 1(mod p)；I·βs
1(mod p)}。
我们称I为公开数，s为秘密数。假设H为Z*p(·)的子集，有kp，那么公开数是H的元素，注意到任何β∈H，β≠1，有至少为v=[10g2p]的阶。
我们约定│p│表示p的二进制长度，a∈RA表示元素a是用一致性分配从集合A中随机选取的。
协议(P，V)：输入x=(I；β，p)，V校验p是一个素数，然后计算kp，校验I∈H，βkp 1(mod p)。如果任何一个条件失败了，那么V停止和退出。
步骤一 P发送给V：z=βr(mod p)，而r∈RZp-1；
步骤二 V发送给P：q，而q∈RZ│p│；
步骤三 P认证q∈Z│p│；如果校验成功，发送给V：y (r+qs)(mod(p一1))，而s是βs·I (mod p)；
步骤四 V认证y∈Zp-1，Z βy·Iq(mod p)。如果这一验失败，那么协议停止。
步骤五 上面的步骤独立的重复t次，V接受，其中t=t(│p│)几乎恒定。
该协议是语言集L中的成员证明。当x∈L时，那么认证方将(几乎)总是接受，而当x不是L的成员时，那么认证方将(几乎)总是拒绝。
4算法的完备性、有效性和零知识性 完备性 当x∈L时，βr·Iq βr·βφ·Iq Z(βs，I)q Z·(Mod p)，对于步骤4中的校验，V总是接受；
有效性 当x L时，若I H或βk，≠1(mod p)，V总是拒绝；若I∈H，βkp 1(mod p)，甚至是功能无限强的，不诚实证明方都不能回答步骤3的几个序列q，所以当没有s使得βs
1(mod p)时，连续t次后，V接受的概率可以忽略不计。
零知识性 从直观上讲，证明方不向认证方显示任何新知识，因为认证方可以自己模拟协议通信。认证方可以猜测他自己的问题q，自己得到证明方将发给他的Z和y。就是说，他可以用实际协议中同样的分配，产生满足步骤4中条件的串(Z，q，y)。这一模拟的关键是，给定的q和y，都容易获得适当的Z。当然，模拟的证明将不向认证方保证x∈L。
因此，该协议符合零知识鉴别的条件。
5性能分析
V是限于│n│的多项式，因此│v│=O(log│n│)。对于通信和计算复杂度，我们只考虑群元素G，H为模数，群操作可以按模操作的方式表达的情况。我们假设H=*m，输入的长度是θ(│m│)，协议的性能将按│m│的方式测量。在协议的每一循环中，步骤1和步骤3通信│m│比特，步骤2通信│v│比特。对于t的重复，我们有t(2│m│+│v│)比特。由于当t△logs│m│时，│v│=O(log
│m│)，通信的比特数是│m│logε│m│。
6 结语
RFID技术中应用身份鉴别机制是一种必然趋势，本文提出将基于零知识证明的鉴别协议应用在RFID技术上，此协议具有较低的运算复杂度、较小的通信量和较高的安全性，并且密钥不易被窃听，随着研究的不断深入和人们对于信息安全和个人隐私的重视，一定会有广阔的应用前景。
RFID技术是当前研究的一个热点，其采用无线信号进行无接触的双向信息传输，一方面具有极大的方便性和灵活性，另一方面增加了信息被窃取的风险。无线信道与具有保密性的有线信道不同，无线信道的一个特征是其公开性，任何人只要拥有相应频段的接收设备，就可以对无线信道进行监听，因此和有线信道相比，无线信道更容易被窃听而且不容易被发现。对于EPC(电子产品代码)Class0／O+标准中没有任何加密措施和鉴别机制的情况，已经引发了广泛的关于保护消费者隐私权的激烈讨论。而对于远作用距离的有源RFID系统，则具有更大的安全隐患。因此研究如何在RFID系统实现高效的身份鉴别是非常有必要的。
鉴别又叫认证，是用来证明某人或某事是否真实、可靠或者有效的过程，他通过验证称谓者的一个或多个参数的真实性或者有效性来达验证其是否名副其实的目的[1]。鉴别在现实生活中的形式多种多样，如对人的鉴别，一般通过口令或者人的生理特征(声音、指纹、视网膜等)进行鉴别。本文主要讨论RFID系统的鉴别，其鉴别的过程是基于零知识证明技术的。
身份鉴别是双向的，即RFID卡与终端要相互鉴别对方身份。目前，在RFID系统存在的安全问题(如保护消费者隐私权)中，攻击者所采用的主要攻击方式是对RFID卡信息的非法窃取，而不是伪造RFID卡，因此本文将研究重点放在RFID卡对终端的鉴别问题上。
2 目前常用的两种鉴别体制的缺陷
鉴别分为2种：对称鉴别和非对称鉴别。对称鉴别是指主机和称谓者预先共享了某个秘密信息，或者主机知道称谓者某个秘密信息的映象，主机通过验证称谓者是否知道这个秘密来达到鉴别的目的；非对称鉴别是指主机不知道称谓者用于证明其身份的某个秘密(包括秘密的映象)，而仅通过与称谓者的秘密对应的公开密钥来鉴别其真伪[2]。
2．1对称鉴别体制
在智能卡中应用较多的是对称鉴别体制，采用的是DES对称加密算法。在通之前，卡要对终端进行验证，对称鉴别速度较快，对智能卡的性能、资源要求较低，但是其在使用之前一般需要有一个集中的卡的发行过程，以便于密钥的分发，因此只能适合于比较单一的领域(或单一的人群)使用，如移动电话卡、银行卡等。对于更广泛的电子商务、物流管理来讲，非对称鉴别更适合，目前已经出现了一系列的基于智能卡的加密接口规范。
2．2非对称鉴别体制
非对称鉴别体制与对称鉴别体制相比具有更大的灵活性，他并未完全包括某一特定的密码算法，却经常以RSA算法为基础进行加工[3]。RSA算法是密码学理论上的一个重大突破，他成功地解决了密钥分发的问题，但在实际应用中却存在以下困难：
(1)RSA算法的保密强度是建立在特定的数学问题求解的困难性上的，他可以表示成简单的数学公式，然而随着数学的发展，许多现在看来难以解决的问题可能在不久的将来会得到解决，而诸如DES之类的对称密码算法则难以表示成一个确定的数学形式，其保密强度因此相应地要高。
(2)RSA算法中密钥的生成较对称密码体制而言要复杂得多，特是大素数p和q的生成比较复杂。倘若一个电子标签应用系统中只采用一对p和q，一旦他们被泄密，则整个密码系统失效；而若每个电子标签采用不同的p和q，则p和q的生成任务极其繁重。
(3)受电子标签资源的限制，在电子标签中实现RSA算法非常困难，主要是实现RSA算法中的大数乘方取模比较困难，即使能实现，其速度往往比较慢，而对于电子标签而言，其操作或交易都是在非常短的时间内完成的，如门禁系统、车辆管控系统等。因此RSA算法有时不符合某些电子标签及其应用的要求，除非电子标签有对大数乘方取模操作的硬件支持，但这又带来了电子标签的成本较高，用户难以接受的问题。
(4)对于RFID系统而言，无源电子标签本身没有电源，只能从射频信号中提取能量，因此其功率必然受到一定的限制，难以完成像RSA这样复杂的算法；而对于有源的电子标签，依靠自身电池提供能量，可以完成此算法，但会严重影响其使用寿命。
3 新型的零知识鉴别协议
在实际生活中，A要向B证明他知道某秘密的常用方法是把他知道的秘密告诉B，但这样一来B就知道了这个秘密。如何在不告诉B这个秘密的情况下使B相信A知道这个秘密，就是零知识证明要解决的问题。有了零知识证明，A就可以不公布秘密，却能使任何人相信他知道这个秘密。零知识证明可以使研究人员向世人证明他知道一个特殊定理的证明方法但又不泄漏证明，这种方法在商业上也有许多用途。零知识证明的研究受到各国研究人员的重视，在国际上一直很活跃，基本的零知识证明算法基于同构图和汉密尔顿回路"[4]。
所谓的零知识鉴别协议是指一个证明者P是一个具有无限计算能力的图灵机，向一个仅具有多项式计算能力的图灵机(验证者)V证明他宣称的一个结论是正确的，在此过程中，验证者V除了相信P的宣称以外，得不到其他额外的信息，允许P，V违背协议[5]。
严格地讲，假设P，V是两个概率图灵机，P有无限的计算能力，V的计算能力是多项式的，若一个证明协议满足以下3点，就称此协议为一个零知识证明协议[6]：
完备性 如果P的声称是真的，则V以绝对优势的概率接受P的结论；
有效性 如果P的声称是假的，则V以绝对优势的概率拒绝P的结论；
零知识性 无论V采取任何手段，当P的声称是真的，并且不违背协议时，V除了接受P的结论以外，得不到其他额外的信息。
这一概念产生之后，关于他的理论和实际应用方面的研究立刻全面展开。零知识证明系统已逐渐形成一个体系，他象单向函数、单向陷门函数以及伪随机数发生器一样，成为构造安全密码系统的基本方法之一。零知识交互式证明系统在身份验证、数字签名和抗选择密文攻击等方面获得了广泛的应用，使用零知识交互式证明的身份验证模式比使用RSA的执行速度要快得多[7]。
Feige-Fiat-Shamir算法是第一个基于零知识证明的算法，他出现于上个世纪80年代。2000年，Nyang和Song提出了一个应用于智能卡的基于零知识证明和身份认证协议，从此关于零知识证明的应用研究广泛展开。
目前有一种有效的零知识鉴别协议可应用于RFID统，该协议是以离散对数为基础的，离散对数是现代密码学常用的重要的单向函数，其特点之一是只需较小的通信量和计算量。
假设P是一个素数，Zp是整数环模p，定义Kp是p-1最大的除数，他的素因子至少为v=[log2p]。
我们将考虑语言集L，他的元素是串a=(I；β，p)，而β是串Znp=Zp／{O}，βkp 1(mod p),I∈Znp是I·βs
1(mod p)，对于所有的s∈Zp-1，有L={(I；β，p)│p是一个素数，β，I∈Z*p；βkp 1(mod p)；I·βs
1(mod p)}。
我们称I为公开数，s为秘密数。假设H为Z*p(·)的子集，有kp，那么公开数是H的元素，注意到任何β∈H，β≠1，有至少为v=[10g2p]的阶。
我们约定│p│表示p的二进制长度，a∈RA表示元素a是用一致性分配从集合A中随机选取的。
协议(P，V)：输入x=(I；β，p)，V校验p是一个素数，然后计算kp，校验I∈H，βkp 1(mod p)。如果任何一个条件失败了，那么V停止和退出。
步骤一 P发送给V：z=βr(mod p)，而r∈RZp-1；
步骤二 V发送给P：q，而q∈RZ│p│；
步骤三 P认证q∈Z│p│；如果校验成功，发送给V：y (r+qs)(mod(p一1))，而s是βs·I (mod p)；
步骤四 V认证y∈Zp-1，Z βy·Iq(mod p)。如果这一验失败，那么协议停止。
步骤五 上面的步骤独立的重复t次，V接受，其中t=t(│p│)几乎恒定。
该协议是语言集L中的成员证明。当x∈L时，那么认证方将(几乎)总是接受，而当x不是L的成员时，那么认证方将(几乎)总是拒绝。
4算法的完备性、有效性和零知识性 完备性 当x∈L时，βr·Iq βr·βφ·Iq Z(βs，I)q Z·(Mod p)，对于步骤4中的校验，V总是接受；
有效性 当x L时，若I H或βk，≠1(mod p)，V总是拒绝；若I∈H，βkp 1(mod p)，甚至是功能无限强的，不诚实证明方都不能回答步骤3的几个序列q，所以当没有s使得βs
1(mod p)时，连续t次后，V接受的概率可以忽略不计。
零知识性 从直观上讲，证明方不向认证方显示任何新知识，因为认证方可以自己模拟协议通信。认证方可以猜测他自己的问题q，自己得到证明方将发给他的Z和y。就是说，他可以用实际协议中同样的分配，产生满足步骤4中条件的串(Z，q，y)。这一模拟的关键是，给定的q和y，都容易获得适当的Z。当然，模拟的证明将不向认证方保证x∈L。
因此，该协议符合零知识鉴别的条件。
5性能分析
V是限于│n│的多项式，因此│v│=O(log│n│)。对于通信和计算复杂度，我们只考虑群元素G，H为模数，群操作可以按模操作的方式表达的情况。我们假设H=*m，输入的长度是θ(│m│)，协议的性能将按│m│的方式测量。在协议的每一循环中，步骤1和步骤3通信│m│比特，步骤2通信│v│比特。对于t的重复，我们有t(2│m│+│v│)比特。由于当t△logs│m│时，│v│=O(log
│m│)，通信的比特数是│m│logε│m│。
6 结语
RFID技术中应用身份鉴别机制是一种必然趋势，本文提出将基于零知识证明的鉴别协议应用在RFID技术上，此协议具有较低的运算复杂度、较小的通信量和较高的安全性，并且密钥不易被窃听，随着研究的不断深入和人们对于信息安全和个人隐私的重视，一定会有广阔的应用前景。
