密码学是信息安全的基础,人们利用密码学来保证通信的安全。而密码协议作为密码学用来保证通信安全的主要方式,越来越受到人们的重视。密码协议[1]是一种分布式的算法,是指两个或两个以上实体为达到一个特定的安全目标,执行的一系列有明确动作规定的步骤。一般而言,密码学中所有的密码系统,例如密钥分配系统、数字签名认证系统、秘密共享系统,均可称为密码协议。密码协议为网络提供安全服务,是网络安全的基本保障。近年来,随着Internet的飞速发展,网络上越来越多的数据传输和交易都需要密码协议的保障和支持。本论文主要包含两部分内容,首先设计了一套针对车载自组网络的密码安全协议,该协议在效率方面要强于现有的安全协议,并且可以满足安全上的需求。同时,在安全多方计算方面,设计了一系列安全字符串匹配协议,该协议在效率方面要强于现有的协议,并且对多项式时间的攻击者是安全的。这两个方面的研究在现实生活中有很重要的意义。一、安全有效的车载自组网络协议不管在工业界还是学术界,车载自组网络(Vehicular Ad Hoc Network简称VANET)都已经引起了大家越来越多的关注。它是智能交通系统[2]的重要组成部分。在典型的车载自组网络中,每一个车辆都会拥有一个车载部件(On-Board Unit简称OBU),在路边会建立一些基站(Road-Side Unit简称RSU),并且还会建立一个可信的认证中心(Trusted Authority简称TA)和一些其他的应用服务器。OBU和RSU之间通过无线网络使用专用短程通信协议(Dedicated Short Range Communications Protocol简称DSRC)[3]来进行通信。RSU和可信认证中心(TA)以及应用服务器则通过安全的固定有线网络进行连接。基于这些,每一个车辆都可以周期性的广播包括诸如它的速度、位置、路况和其他交通信息在内的一些安全信息[4]。通过接收这些信息,其他车辆的司机就可以对一些突发情况进行预先的处理和防范。经过多次的转发,这些信息或许被RSU所接收,或许因超过了其生存周期而被丢弃。RSU也可以将一些交通信息通知路况控制中心,这样控制中心可以调节交通指示灯来避免可能发生的交通阻塞。车载自组网络也可以提供一个公共的通信平台来实现多个成员之间的通信。与其他的通信网络一样,安全性是必须要考虑的问题。比如说消息的完整性必须得到保证,同时消息的发送者必须经过认证。否则的话攻击者就可以替换某些安全信息甚至模仿一些车辆发送一些垃圾信息,危害严重的甚至可能造成交通事故或者危害到人身安全。另外,用户的隐私包括用户的身份、位置和一些特殊车辆的运行路线等等也要得到保护。因此,车载自组网络需要一个匿名而且安全的通信协议。而国际上现有的车载自组网络安全协议,有的安全性无法满足需求,有的则使用基于椭圆曲线密码算法的双线性对来实现,效率不够理想。因此,我们设计了一个基于HMAC (Hash-based Message Authentication Code,基于杂凑函数的消息认证码)的安全有效的通信协议。我们提出了一系列满足车载自组网络安全性要求的协议,主要包括以下三个协议：1.车辆和RSU之间的通信协议：本文使用速度较快的HMAC计算和对称加密代替效率较低的椭圆曲线密码算法(ECC)来实现车辆和RSU之间的安全通信,这提高了通信的效率并且可以满足安全上的需求。通过模拟验证,该协议更加有效,系统的延迟更低。经过模拟,该协议的平均延迟比以前的协议的延迟低千倍。而且经过证明,该协议可以满足车载自组网络的安全性需求。该协议需要预先在RSU和车辆之间生成一个共享密钥,这一条件很容易实现,并且现有的很多协议都满足这一条件。2.群成员之间的安全通信协议：本文使用HMAC计算和对称加密来实现群成员之间的安全通信,而在以前的协议中如DRS协议[5]则使用复杂的椭圆曲线密码算法(ECC)来实现。在车载自组网络中,群通信是多个成员之间通信的一个公共的通信平台。一群车辆在RSU的协助下形成群,在群形成以后,群中的车辆无需RSU的协助就可以进行安全通信。该协议提高了通信的效率并且可以满足车载自组网络的安全性需求。通过模拟验证,该协议更加有效,协议的延迟更低。该协议的平均延迟是0.312毫秒,而以前的协议的平均延迟是12.3毫秒,该协议的平均延迟远远低于先前系统的平均延迟。而且经过证明,该协议可以满足车载自组网络的安全性需求。3.陌生车辆之间的一对一安全通信协议：本文提出了在陌生车辆之间进行一对一安全通信的协议,而在以前的研究中没有类似的协议提出,本文弥补了这一缺陷。该协议主要应用于一个车辆想要跟附近的另一个陌生的车辆进行通信的情况。该协议也是使用有效率的HMAC计算和对称加密来实现的,通过模拟验证,该协议的平均延迟是0.312毫秒,而以前的协议要实现该功能的平均延迟是大概9秒。而且经过证明,该协议完全可以满足车载自组网络的安全性需求。二、安全字符串匹配本文这部分研究内容是关于安全两方字符串匹配问题：Alice有一个长度为n的字符串t∈{0,1}n, Bob有一个长度为m的字符串p∈[0,1}m。我们的协议的目标是Bob获得它的字符串p在t中出现的位置。当然可以根据需要把它扩展到任意的Q阶的字母字符串。尤其是对于t,p∈{A,T,C,G}这样的DNA序列。字符串匹配算法,也叫字符串查找算法,是字符串算法中比较重要的一类算法。这些算法可以用在文档处理中,例如Unix操作系统中的grep命令,也可以用在一些文本信息检索程序中,例如Medline、Lexis或者Nexis,也可能用在图书馆的目录检索系统中,当然在网络浏览器和爬虫软件中也可以用到。在分子生物学中,有很多的存储DNA、RNA或者其他字符串的数据库中也可以用到这些。除了基本的字符串匹配问题,还存在由该问题衍变而来的一些问题,比如匹配的字符串可能包含通配符。这个问题已经被研究者广泛研究,而且可以在线性的时间复杂度[7]内解决。字符串匹配还有可能是近似的,比如要求匹配的字符串的汉明重量小于某个上限丁。最近的一个解决该问题的算法是Amir [6]等人提出的,他们的时间复杂度是O(n (?))。另外还可能要求匹配的字符串的编辑距离(Edit Distance)[8]小于某个上限。随着社会的进步和科技发展的需要,越来越多的系统都需要一个安全的字符串匹配算法。比如在分子生物学中,每个人的DNA、RNA或者其他字符串数据库中的信息都是非常重要的个人隐私,在查询和匹配过程中,人们不希望自己的信息被泄露出去,因此一个既能保证安全性,又能保护个人隐私不被泄露的安全字符串匹配协议就成了人们的普遍需求。在安全字符串匹配协议中,要求通信的双方既要保证正确性,即匹配过程是完全正确的,又要保证安全性,即通信双方都不希望自己的信息被泄露出去。本文提出的关于安全字符串匹配问题的安全协议主要有如下三个协议组成：1.基本安全字符串匹配协议：使用后缀树来实现了一个基本的安全字符串匹配问题的有效协议,该协议的轮复杂度是O(1),其通信复杂度和计算复杂度在理论上都是线性的。Alice有一个长度为n的字符串t∈{0,1}n, Bob有一个长度为m的字符串p∈{0,1}m。我们的协议的目标是Bob获得它的字符串p在t出现的位置,t和p都不包含通配符,而且该协议要求的是精确匹配。该协议的计算复杂度和通信复杂度在理论上均是O(m+n),但是由于后缀树在理论上计算复杂度的时候只能考虑最差情况,而在实际中,通过模拟,该协议远远好于先前的协议,尤其是当字符串t的长度n远远大于字符串p的长度m的时候,而这恰好符合现实中的需求。该协议针对多项式时间的攻击者是安全的,而且可以达到基于模拟的完全的安全性(full simulation security)[9],也就是在匹配的过程中除了最后的匹配结果以外双方不会得到任何其他信息。2.带通配符的安全字符串匹配协议：本文使用Boneh-Goh-Nissim算法实现了含有通配符的安全字符串匹配协议,由于Boneh-Goh-Nissim算法对任意次加法和一次乘法是同态的,所以大大降低了复杂度。在该协议中,字符串p中是可以包含通配符的,我们将该安全字符串匹配协议的复杂度从O(mn)[10]和O(n log m)[11]降低到了O(m+n)。同时该协议需要一个安全的第三方来处理密钥生成的过程。该协议针对多项式时间的攻击者也是基于模拟完全安全的(full simulation security)。3.近似安全字符串匹配协议：我们使用Boneh-Goh-Nissim算法实现了近似字符串匹配协议,也就是要求匹配的两个字符串的汉明重量只要小于某个上限丁,就说他们匹配。同样利用Boneh-Goh-Nissim算法的同态特性,大大降低了复杂度。将近似安全字符串匹配协议的复杂度从O(mn)[10]和O(nlogm)[11]降低到了O(nτ),这里τ是近似字符串匹配协议中汉明重量的上限值。该协议也需要一个安全的第三方来处理密钥生成的过程。该协议针对多项式时间的攻击者也是基于模拟完全安全的(fullsimulation security)。