基于离散轨迹的密钥交换方法

摘要

本发明公开了一种基于离散轨迹的密钥交换方法，主要解决现有密码学中缺少以离散的目标轨迹作为用户身份凭据的密钥交换方法。其实现方案为：建立系统和敌手模型；证明者分别通过基于位置密钥交换得到与验证者的共享密钥，主密钥为各共享密钥之和；证明者间进行密钥的分发，得到子密钥；设门限为t，当某用户沿着目标轨迹运行，同时拥有任意t个子密钥时，可恢复出与验证者协商的主密钥；验证者凭借主密钥与用户进行安全通信。本发明将密钥共享技术和基于位置的密钥交换结合，用户同时承担密钥共享者与分发者的角色，主密钥安全性强，能有效抵御多个敌手的共谋攻击。可用于在有敌手控制的网络环境中为通信实体之间建立共享的密钥。

权利要求

1.一种基于离散轨迹的密钥交换方法，其特征在于，包括有如下步骤：(1)建立系统模型：在移动通信的安全系统中，涉及到证明者、验证者和敌手三个角色，某一用户按照目标轨迹运行，轨迹上分布了n个等间隔的离散点，离散点即为指定位置，用户每到一个目标轨迹上的指定位置，就担任一次证明者的角色；在三维空间里，n个证明者分别称自己位于目标轨迹等间隔分布的P1,P2,…,Pn点上，对于每个证明者pi，其中1≤i≤n，采用四个验证者V1、V2、V3、V4，证明者均被封闭在由验证者所构成的四面体中；

(2)建立敌手模型：在上述系统模型中，存在敌手角色，所述敌手为共谋敌手，共谋敌手A＝{A1,A2,...,Ak}，能够控制整个网络环境，k个敌手之间相互合作，通过伪装、窃听、重放的方法来进行攻击，目的在于欺骗验证者使其认为此共谋敌手是按照目标的离散轨迹运行的，以计算得到验证者与用户之间最终的共享密钥；假设在离散轨迹上共谋敌手的数量小于门限t，即在指定位置Pi(1≤i≤n)点的共谋敌手的数量k

(3)系统准备工作：验证者拥有最小熵为(δ+β)y的反向熵源，y为信息串的长度，均可发送长字符串Xij，其中Xij∈{0,1}y，代表第i个点中的第j个字符串；验证者可以通过伪随机生成器PRG生成密钥K←{0,1}m，m为密钥的长度；当验证者发送的信息串高速经过共谋敌手时，共谋敌手能够提取信息串的任意函数，但是所提取函数的信息量必须小于或等于存储上限βy，其中βy是最小熵为(δ+β)y的总信息量的任意部分；

(4)验证者传递消息满足的条件：证明者和所有验证者之间均存在安全信道，验证者之间通过私有通道共享消息，其中传递的消息不能被验证者之外的其他实体所截获；所有验证者与证明者传送消息的速度都等于无线电波的速度，验证者收到消息与计算数据之间不存在时间延迟；

(5)主密钥生成阶段:

(5a)n个证明者分别通过基于位置密钥交换方案，在不同的时刻得到与验证者之间的共享密钥Si，也称为次密钥Si；最终用户与验证者的共享密钥S，也称为主密钥S，是所有参与者与验证者之间的共享密钥Si的和，即n个证明者通过基于位置密钥交换方案，得到与验证者之间的共享密钥Si，具体步骤如下：(5a1)验证者给位于P1的证明者发送消息：

设T为位于位置P1的证明者同时接收到4个验证者发送消息的时刻，Ti为消息从第i个验证者到达位置P1所需要的传输时间，1≤i≤4，验证者V1通过伪随机生成器PRG生成密钥K11，并在T-T1时刻广播消息(X14，K11)，验证者V2在T-T2时刻广播消息(X11，X15)，验证者V3在T-T3时刻广播消息X12，验证者V4在T-T4时刻广播消息X13；

(5a2)位于P1的证明者计算与验证者之间的共享密钥S1：

在T时刻，位于P1的证明者同时收到4个验证者广播的消息，根据收到的4个信息串(X14，K11)、(X11，X15)、X12、X13，利用公式Ki,j+1＝PRG(Xi,j,Ki,j)，1≤j≤5,i＝1，计算得到共享密钥K16，具体计算为：

K12＝PRG(X11，K11)，

K13＝PRG(X12，K12)，

K14＝PRG(X13，K13)，

K15＝PRG(X14，K14)，

K16＝PRG(X15，K15)，

即位于P1的证明者得到与验证者之间的共享密钥K16，记为S1；

(5a3)位于Pi点的证明者计算与验证者之间的共享密钥Si，2≤i≤n：反复执行步骤(5a1)-(5a2)，验证者在合适的时刻给位于P2,P3,…,Pn点的证明者发送消息，位于P2,P3,…,Pn点的证明者收到消息后，利用公式Ki,j+1＝PRG(Xi,j,Ki,j),1≤j≤5,2≤i≤n计算得到位于P2,P3,…,Pn点的证明者与验证者之间的共享密钥S2,S3,…,Sn；

(5b)验证者之间通过私有通道秘密地传输并安全地保存好主密钥S；

(6)密钥分发阶段：n个证明者均进行密钥的分发过程，得到关于主密钥S的子密钥Mi，在此阶段中，证明者既承担了密钥共享者的角色，同时也起到了密钥分发者的角色，不需要再加入可信中心的干预；

(7)用户主密钥恢复阶段：当某一用户沿着目标轨迹运行后，担任了w次证明者的角色，t≤w≤n，所持有的子密钥数量达到门限t时，通过计算得到与验证者之间协商的主密钥S，实现了用户和验证者之间的密钥交换；

(8)验证者确认阶段：验证者将自己所保存的主密钥与用户恢复得到的主密钥进行比对，(8a)若相同，则证明此用户是沿着目标轨迹运行的，是安全合法的用户，验证者凭借此共享的主密钥与此用户进行安全通信；

(8b)若不同，则证明拥有此密钥的用户未按照目标轨迹运行，而是共谋敌手企图利用一个错误的随机数干扰系统的通信，证明者将拒绝与此用户通信。

2.根据权利要求1所述的基于离散轨迹的密钥交换方法，其特征在于，其中步骤(6)的密钥分发，具体步骤如下：(6a)位于P1,P2,…,Pn点的证明者均随机选取t-1个整数ai,1,ai,2,...,ai,t-1,1≤i≤n，构造一个t-1次多项式：Fi(x)＝Si+ai,1x+ai,2x2+…+ai,t-1xt-1，要求使得Si＝Fi(0)；

(6b)位于Pi的证明者计算Mi,j＝Fi(j),1≤j≤n,并把消息Mi,j安全秘密地发送给其他的证明者Pj；

(6c)位于Pi的证明者在收到所有其他的证明者发送的消息后，计算：Mi就是证明者Pi关于最终的主密钥S的子密钥。

3.根据权利要求1所述的基于离散轨迹的密钥交换方法，其特征在于，其中步骤(7)的主密钥恢复阶段，具体步骤如下：当某一用户沿着目标的离散轨迹运行后，同时拥有任意t个子密钥Mi时，根据拉格朗日插值公式，即可计算出最终的主密钥S，具体计算为：即若用户所拥有的子密钥Mi数目大于或等于t时，则可重构恢复最终的主密钥S；

若用户所拥有的子密钥Mi数目少于t时，则无法重构恢复最终的主密钥S。

说明书

基于离散轨迹的密钥交换方法

技术领域

[0001] 本发明属于移动通信技术领域，主要涉及密码学中基于位置的密钥交换和密钥共享技术，具体是一种基于离散轨迹的密钥交换方法，可用于在有敌手控制的网络中为实体之间建立共享的密钥。

背景技术

[0002] 目前，与人们生活息息相关的网络几乎都是公共网络，各个移动终端上的通信都是在这些公共网络上的公开信道里完成的。为了在这样的公开信道上安全地传输秘密信息，保障双方的安全通信，通常需要认证双方的身份，为实体之间建立共享的会话密钥。随着GPS(Global Positioning System)的广泛使用以及基于位置服务(Location-Based Service)的普及，“位置”成为了一个非常重要的属性。而轨迹可以看作是移动对象在空间中因位置变化留下的印迹。在大量用户位置和行为轨迹数据的背后，用户的身份就可以得到认证。

[0003] 移动用户因物理位置的改变而形成轨迹，轨迹即可代表用户的身份。移动对象的轨迹数据有着广阔的应用场景，在交通管制、移动电子商务、物流配送等领域，移动对象的轨迹均扮演着重要的角色。

[0004] 为了保障实体间安全的通信，如今，密钥交换协议的分析和设计已经成为密码学领域重点的研究问题。传统密码学中，密钥交换协议多是以预共享密钥、基于证书、基于身份等密码体制来实现的。在2009年欧密会上，Chandran等人提出了基于位置密码学的概念，其中典型应用有基于位置的密钥交换。与传统密码学不同，基于位置的密钥交换是将用户的物理位置作为唯一的身份凭证，对于不在指定位置的敌手，都不能得到最终协商的密钥。

[0005] 2013年第10届ISC会议中的《A Position-Based Key Management Scheme ForHeterogeneous Sensor Networks》一文提出了以传感器节点的位置作为一个独特的密钥用于验证传感器节点的身份，该文章是在《Position-based Cryptography》中所提出的位置密码学的基础上，极大地提高了无线网络中密钥管理过程下各个设备的性能，但该文章中的节点(验证者节点及传感器节点)仍然需要ID号，验证者需要有一个预共享密钥，且缺乏对多个验证者情况下抵抗敌手共谋攻击的考虑。

[0006] 综上，传统的密钥交换方法通常使用基于证书、预共享密钥等不同的密码体制来实现，无法抵抗敌手的共谋攻击；现有的基于位置的密钥交换协议，是将用户的物理位置作为此用户的唯一身份凭证，也只是适用于单一位置的，对于多个位置上的证明者无法将其联系起来，缺乏灵活性，无法抵抗多个位置情况下敌手的共谋攻击。

[0007] 经过一定范围内的充分检索，在密码学的现有技术中，尚未发现以离散轨迹作为用户身份凭据的密钥交换的技术方案存在，也未见过与本发明主题类似的报道。

发明内容

[0008] 本发明的目的在于针对现有技术的不足，设计出一种可抵抗敌手共谋攻击的基于离散轨迹的密钥交换方法。

[0009] 本发明是一种基于离散轨迹的密钥交换方法，其特征在于，包括有如下步骤：

[0010] (1)建立系统模型：

[0011] 在移动通信的安全系统中，涉及到证明者、验证者和敌手三个角色，某一用户按照目标轨迹运行，轨迹上分布了n个等间隔的离散点，离散点即为指定位置，用户每到一个目标轨迹上的指定位置，就担任一次证明者的角色；在三维空间里，n个证明者分别称自己位于目标轨迹等间隔分布的P1,P2,…,Pn点上，对于每个证明者pi，其中1≤i≤n，采用四个验证者V1、V2、V3、V4，证明者均被封闭在由验证者所构成的四面体中；

[0012] (2)建立敌手模型：

[0013] 在上述系统模型中，存在敌手角色，所述敌手为共谋敌手，共谋敌手A＝{A1,A2,...,Ak}，能够控制整个网络环境，k个敌手之间相互合作，通过伪装、窃听、重放的方法来进行攻击，目的在于欺骗验证者使其认为此共谋敌手是按照目标的离散轨迹运行的，以计算得到验证者与用户之间最终的共享密钥；假设在离散轨迹上共谋敌手的数量小于门限t，即在指定位置Pi(1≤i≤n)点的共谋敌手的数量k

[0014] (3)系统准备工作：

[0015] 验证者拥有最小熵为(δ+β)y的反向熵源，y为信息串的长度，均可发送长字符串Xij，其中Xij∈{0,1}y，代表第i个点中的第j个字符串；验证者可以通过伪随机生成器PRG生成密钥K←{0,1}m，m为密钥的长度；当验证者发送的信息串高速经过共谋敌手时，共谋敌手能够提取信息串的任意函数，但是所提取函数的信息量必须小于或等于存储上限βy，其中βy是最小熵为(δ+β)y的总信息量的任意部分；

[0016] (4)验证者传递消息满足的条件：

[0017] 证明者和所有验证者之间均存在安全信道，验证者之间通过私有通道共享消息，其中传递的消息不能被验证者之外的其他实体所截获；所有验证者与证明者传送消息的速度都等于无线电波的速度，验证者收到消息与计算数据之间不存在时间延迟；

[0018] (5)主密钥生成阶段:

[0019] (5a)n个证明者分别通过基于位置密钥交换方案，在不同的时刻得到与验证者之间的共享密钥Si，也称为次密钥Si；最终用户与验证者的共享密钥S，也称为主密钥S，是所有参与者与验证者之间的共享密钥Si的和，即

[0020] (5b)验证者之间通过私有通道秘密地传输并安全地保存好主密钥S；

[0021] (6)密钥分发阶段：

[0022] n个证明者均进行密钥的分发过程，得到关于主密钥S的子密钥Mi，在此阶段中，证明者既承担了密钥共享者的角色，同时也起到了密钥分发者的角色，不需要再加入可信中心的干预；

[0023] (7)用户主密钥恢复阶段：

[0024] 当某一用户沿着目标轨迹运行后，担任了w次证明者的角色，t≤w≤n，所持有的子密钥数量达到门限t时，通过计算得到与验证者之间协商的主密钥S，实现了用户和验证者之间的密钥交换；

[0025] (8)验证者确认阶段：

[0026] 验证者将自己所保存的主密钥与用户恢复得到的主密钥进行比对，

[0027] (8a)若相同，则证明此用户是沿着目标轨迹运行的，是安全合法的用户，验证者凭借此共享的主密钥与此用户进行安全通信；

[0028] (8b)若不同，则证明拥有此密钥的用户未按照目标轨迹运行，而是共谋敌手企图利用一个错误的随机数干扰系统的通信，证明者将拒绝与此用户通信。

[0029] 在广阔的应用领域中，本发明的基于离散轨迹的密钥交换方法均可发挥巨大作用。例如，无人机安全接入网络时，首先需要对无人机进行安全验证，判断无人机是否按照目标轨迹运行，并且得到与可信的验证者协商的共享密钥。

[0030] 与现有技术相比，本发明具有如下优点：

[0031] (1)本发明是在基于位置的密钥交换的基础上进行设计，由单一位置扩展到目标轨迹上的n个离散位置，在有界存储模型上建立了系统模型，当验证者发送的信息高速通过敌手时，由于敌手能提取验证者所发送信息串的任意函数，但提取的信息量存在一个上限βy，因此，即使多个敌手共谋攻击，本发明的技术方案仍然是可证明安全的。

[0032] (2)本发明结合了无可信中心的密钥共享方案，且由于物理位置是用户唯一的身份凭证，所以，不在指定位置的非法成员是无法证明自己在此位置上，并伪装成合法成员，来获取子密钥的，因此，本发明可防止外部欺骗和内部欺骗两种欺骗方式。

[0033] (3)本发明保障了主密钥的随机性，主密钥是所有证明者们共同参与生成的，任何单独的证明者都不知道关于主密钥的信息，便不能独立地生成主密钥。同时，即使某一点上，敌手与证明者在角色上不可区分，但最终的主密钥对于此敌手仍然是完全随机的。因此，方案的安全性高。

[0034] (4)本发明考虑到了用户沿着目标轨迹运行的误差问题，即使丢失了n-t个子密钥，仍认为此用户是按照目标轨迹运行的，即可以恢复出最终与验证者之间协商的主密钥。因此，本发明具有较高的灵活性。

附图说明

[0035] 图1是本发明中的实现总流程图；

[0036] 图2是本发明的系统模型图；

[0037] 图3是本发明中的独立的证明者与验证者协商共享密钥示意图；

[0038] 图4是本发明中的以Pi点为例的密钥分发示意图；

[0039] 图5是本发明中的验证者确认用户身份流程图。

具体实施方式

[0040] 下面结合附图，对本发明作详细的描述。

[0041] 实施例1

[0042] 在日常生活中的公开网络中，为保障实体间安全的通信，密钥交换协议现已成为密码学领域中重点研究的问题。现有研究的密钥交换方案多是以预共享密钥、基于证书、基于身份等密码体制来实现的，无法抵抗敌手的共谋攻击。而随着移动通信和移动定位技术的迅猛发展，基于位置的服务得到了人们的广泛应用，移动用户的运行轨迹中蕴含着大量的信息。现有的基于位置的密钥交换协议，它是将用户的物理位置作为此用户的唯一身份凭证，也只是适用于单一位置的，无法抵抗多个位置情况下敌手的共谋攻击。移动对象轨迹的应用已越来越广泛，为保障移动对象的安全通信，基于轨迹的安全研究至关重要。本发明将轨迹作为用户的身份凭据，设计一个全新的密钥交换方法，达到轨迹上多个离散位置情况下，抵抗敌手共谋攻击的安全性，是具有重要的应用价值的。

[0043] 为了达到轨迹上多个离散位置情况下，抵抗敌手共谋攻击的安全性，本发明提供了一种基于离散轨迹的密钥交换方法，参见图1，包括有如下步骤：

[0044] (1)建立系统模型：

[0045] 在移动通信的安全系统中，涉及到证明者、验证者和敌手三个角色。本发明的系统模型参见图2，某一用户按照目标轨迹运行，轨迹上分布了n个等间隔的离散点，离散点即为指定位置，用户每到一个目标轨迹上的指定位置，就担任一次证明者的角色。在三维空间里，n个证明者分别称自己位于目标轨迹等间隔分布的P1,P2,…,Pn点上，这n个点即为指定位置；对于每个证明者pi，其中1≤i≤n，采用四个验证者V1、V2、V3、V4，证明者均被封闭在由验证者所构成的四面体中；证明者称自己位于目标离散轨迹的P1,P2,…,Pn点上，但其身份的真实性需要验证者的验证。图2中，仅画出了一个验证者，用于验证者角色的示意，如果4个验证者对一个用户在目标轨迹上的各指定位置均验证成功，则此用户就可得到与验证者之间的共享密钥，实现其安全的通信，重要的是在此过程中，本发明的方案能够成功的抵御地敌手的共谋攻击。

[0046] (2)建立敌手模型：

[0047] 在上述系统模型中，参见图2，存在敌手角色，敌手为共谋敌手，共谋敌手A＝{A1,A2,...,Ak}，能够控制整个网络环境，k个敌手之间相互合作，通过伪装攻击、窃听攻击、重放攻击的方法来进行攻击，目的在于欺骗验证者使其认为此共谋敌手是按照目标的离散轨迹运行的，以计算得到验证者与证明者间最终的共享密钥。敌手可能存在于目标轨迹上的指定位置，也可能不在目标轨迹上，在本发明中假设不存在在离散轨迹上共谋敌手的数量超过或等于门限t的情况，即在指定位置Pi(1≤i≤n)点的共谋敌手的数量k

[0048] (3)系统准备工作：

[0049] 验证者拥有最小熵为(δ+β)y的反向熵源，y为信息串的长度，均可发送长字符串Xij，其中Xij∈{0,1}y，代表第i个点中的第j个字符串；验证者可以通过伪随机生成器PRG生成密钥K←{0,1}m，m为密钥的长度。当验证者发送的信息串高速经过共谋敌手时，共谋敌手能够提取信息串的任意函数，但是所提取函数的信息量必须小于或等于存储上限βy，其中βy是最小熵为(δ+β)y的总信息量的任意部分。

[0050] (4)验证者传递消息满足的条件：

[0051] 证明者和所有验证者之间均存在安全信道，验证者之间通过私有通道共享消息，该私有通道是指该通道只被用于特定的实体之间的通信，其中传递的消息不能被验证者之外的其他实体所截获，用于消息的安全传递。所有验证者与证明者传送消息的速度都等于无线电波的速度，验证者收到消息与计算数据之间不存在时间延迟。

[0052] (5)主密钥生成阶段：

[0053] (5a)n个证明者分别通过基于位置密钥交换方案，在不同的时刻得到与验证者之间的共享密钥Si，也称为次密钥Si；最终用户与验证者的共享密钥S，也称为主密钥S，是所有参与者与验证者之间的共享密钥Si的和，即

[0054] (5b)验证者之间通过私有通道秘密地传输并安全地保存好主密钥S。

[0055] 由于此密钥Si(i＝1,2,…,n)是由密钥交换协议得到的，是完全随机的，所以，最终的主密钥S也是随机的。最终的主密钥就是所有参与者的次密钥的和，即主密钥S是所有证明者们共同参与生成的，任何单独的证明者都不知道关于主密钥的信息，便不能独立地生成主密钥。

[0056] 另一方面，若某一敌手Am，1≤m≤k，刚好位于目标轨迹上的指定位置Px，1≤x≤n，则此敌手可以得到一个与验证者的共享密钥Sx，对于指定位置Px，即敌手与证明者均可得到一个与验证者的共享密钥Sx，因此，此处敌手与证明者在角色上不可区分，但最终的主密钥S对于此敌手Am仍然是完全随机的，由此保障了主密钥S的安全性和可靠性。

[0057] (6)密钥分发阶段：

[0058] n个证明者均进行密钥的分发过程，得到关于主密钥S的子密钥Mi，参照图4。在此阶段中，证明者既承担了密钥共享者的角色，同时也起到了密钥分发者的角色，不需要再加入可信中心的干预。因此，本发明的密钥共享安全性高。

[0059] (7)用户主密钥恢复阶段：

[0060] 当某一用户沿着目标轨迹运行后，担任了w次证明者的角色，t≤w≤n，所持有的子密钥数量达到门限t时，通过计算得到与验证者之间协商的主密钥S，实现了用户和验证者之间的密钥交换；即拥有达到门限值t个子密钥的用户，就被视为是沿着目标轨迹运行的，可得到与验证者之间协商的主密钥S，即可成功地恢复主密钥。

[0061] (8)验证者确认阶段：

[0062] 参照图5，验证者将自己所保存的主密钥与用户恢复得到的主密钥进行比对，[0063] (8a)若相同，则证明此用户是沿着目标轨迹运行的，是安全合法的用户，验证者凭借此共享的主密钥与此用户进行安全通信；

[0064] (8b)若不同，则证明拥有此密钥的用户未按照目标轨迹运行，而是共谋敌手企图利用一个错误的随机数干扰系统的通信，证明者将拒绝与此用户通信。

[0065] 由于密钥交换具有认证性、保密性、一致性的安全目标，如何在存在敌手共谋攻击的环境下实现密钥交换方案的安全目标，保证方案的可证明安全，是本发明设计基于离散轨迹的密钥交换方案的基础。

[0066] 本发明是在基于位置的密钥交换的基础上，建立了安全的系统模型和敌手模型。由于敌手能提取验证者所发送信息串的任意函数，但提取的信息量存在一个上限βy，因此，基于位置的密钥交换协议可抵抗指定位置上敌手的共谋攻击。在主密钥生成阶段中，n个证明者分别通过基于位置的密钥交换方案，得到与验证者之间的共享密钥，每个指定位置上都可抵抗敌手的共谋攻击，即不在指定位置上的敌手无法得到验证者与证明者之间的共享密钥。

[0067] 同时，在本方案的敌手模型中，假设在目标轨迹上的共谋敌手的数量小于门限t，即使敌手共谋攻击，但敌手所掌握的子密钥的数量也是小于t的，敌手想成功地攻破Shamir的(t,n)门限方案，这在计算上是不可行的，即敌手无法恢复出共享的主密钥S。

[0068] 因此，本发明的技术方案不仅可以抵抗单一位置上的共谋敌手的攻击，还将多个位置上的证明者联系起来，抵抗了目标轨迹多个离散位置情况下敌手的共谋攻击。

[0069] 实施例2

[0070] 基于离散轨迹的密钥交换方法同实施例1，其中步骤(5a)中n个证明者通过基于位置密钥交换方案，得到与验证者之间的共享密钥Si，包括如下步骤：

[0071] (5a1)验证者给位于位置P1的证明者发送消息：

[0072] 参照图3，设T为位于位置P1的证明者同时接收到4个验证者发送消息的时刻，因为四个验证者和位于位置P1的证明者的距离随机，为了使消息同时到达位于位置P1，即位于位置P1的证明者同时收到各验证者所发送的消息，设Ti为消息从第i个验证者到达位置P1所需要的传输时间，1≤i≤4，则T-Ti时刻就是验证者Vi给位于P1的证明者发送消息的时刻。

[0073] 本例中，验证者V1通过伪随机生成器PRG生成密钥K11，并在T-T1时刻广播消息(X14，K11)，验证者V2在T-T2时刻广播消息(X11，X15)，验证者V3在T-T3时刻广播消息X12，验证者V4在T-T4时刻广播消息X13。其中Xij∈{0,1}y，代表第i个点中的第j个字符串，例如X13代表第1个点中的第3个字符串。

[0074] 在本发明中，密钥K11由验证者V1生成并发送给证明者，实际上验证者V1，V2，V3，V4在功能上相同，密钥K11也可以由其他验证者生成并发送。

[0075] (5a2)位于P1的证明者计算与验证者之间的共享密钥S1：

[0076] 在T时刻，位于P1的证明者同时收到4个验证者广播的消息，根据收到的4个信息串(X14，K11)、(X11，X15)、X12、X13，利用公式Ki,j+1＝PRG(Xi,j,Ki,j)，1≤j≤5，i＝1，计算得到共享密钥K16，具体计算为：

[0077] K12＝PRG(X11，K11)，

[0078] K13＝PRG(X12，K12)，

[0079] K14＝PRG(X13，K13)，

[0080] K15＝PRG(X14，K14)，

[0081] K16＝PRG(X15，K15)，

[0082] 即位于P1的证明者得到与验证者之间的共享密钥K16，记为S1。

[0083] 其中密钥K11是验证者V1通过伪随机生成器PRG生成的，K12～K16均是证明者根据验证者发送的消息串计算得到的共享密钥，S1则是最终的主密钥的一部分。

[0084] (5a3)位于Pi点的证明者计算与验证者之间的共享密钥Si，2≤i≤n：

[0085] 反复执行步骤(5a1)-(5a2)，验证者在合适的时刻给位于P2,P3,…,Pn点的证明者发送消息，位于P2,P3,…,Pn点的证明者收到消息后，利用公式

[0086] Ki,j+1＝PRG(Xi,j,Ki,j),1≤j≤5,2≤i≤n

[0087] 计算得到位于P2,P3,…,Pn点的证明者与验证者之间的共享密钥S2，S3，…，Sn，则S2，S3，…，Sn均是最终的主密钥的组成部分。

[0088] 由于运行轨迹是基于离散轨迹的密钥交换方案的凭据，因此，如何将现有的基于位置的密钥交换方案中的独立点扩展到轨迹，确保每个位置密钥的可靠性，是本发明设计基于离散轨迹的密钥交换方案的关键。

[0089] 本发明中位于Pi点的证明者分别通过基于位置的密钥交换，得到的共享密钥Si，Si是完全随机的，由此保障了主密钥的随机性，各证明者独立地生成次密钥，都不知道关于主密钥的信息，不能独立地生成主密钥，因此，本发明的技术方案安全性高。

[0090] 实施例3

[0091] 基于离散轨迹的密钥交换方法同实施例1-2，其中步骤(6)的密钥分发，参照图4，具体步骤如下：

[0092] (6a)位于P1,P2,…,Pn点的证明者均随机选取t-1个整数ai,1,ai,2,...,ai,t-1,1≤i≤n，构造一个t-1次多项式：Fi(x)＝Si+ai,1x+ai,2x2+…+ai,t-1xt-1，要求使得Si＝Fi(0)；

[0093] (6b)位于Pi的证明者计算Mi,j＝Fi(j),1≤j≤n,并把消息Mi,j安全秘密地发送给其他的证明者Pj；

[0094] (6c)位于Pi的证明者在收到所有其他的证明者发送的消息后，计算：

[0095]

[0096] Mi就是证明者Pi关于最终的主密钥S的子密钥。

[0097] 由于密钥共享的方案的丰富性与复杂性，因此，如何选择适合的密钥共享方案，保障用户既能承担密钥共享者的角色，同时也要起到密钥分发者的角色，是本发明设计基于离散轨迹的密钥交换方案的保障。

[0098] 本发明结合了无可信中心的密钥共享方案，证明者既承担了密钥共享者的角色，同时也起到了密钥分发者的角色，不需要再加入可信中心的干预；且由于物理位置是用户唯一的身份凭证，所以，不在指定位置的非法成员是无法证明自己在此物理位置上，并把自己伪装成合法成员，来获取子密钥的。因此，本发明的技术方案可防止外部欺骗和内部欺骗两种欺骗方式。

[0099] 实施例4

[0100] 基于离散轨迹的密钥交换方法同实施例1-3，其中步骤(7)的主密钥恢复阶段，具体步骤如下：

[0101] 当某一用户沿着目标的离散轨迹运行后，同时拥有任意t个子密钥Mi时，根据拉格朗日插值公式，即可计算出最终的主密钥S，具体计算为：

[0102]

[0103] 即若用户所拥有的子密钥Mi数目大于或等于t时，则可重构恢复最终的主密钥S；

[0104] 若用户所拥有的子密钥Mi数目少于t时，则无法重构恢复最终的主密钥S。

[0105] 随着轨迹数据的增多，即需要验证的离散点数的增多，对每一个监测点进行验证的难度则会增大，因此，采样取点的方法，即密钥共享机制被引入。假设目标轨迹上总监测点的个数为n，监测点即目标轨迹上的离散点，n个证明者进行无可信中心的密钥共享过程，即共同参与进行主密钥的生成，密钥的分发及主密钥的恢复。

[0106] 下面给出一个完整的例子，对本发明进行更详细的阐述。

[0107] 实施例5

[0108] 基于离散轨迹的密钥交换方法同实施例1-4，下面结合附图，对本发明再作描述。

[0109] 系统概述

[0110] 参照图2，在移动通信系统中，针对安全通信中的密钥交换方案，一共有三个参与角色，分别为证明者(prover)，验证者(verifier)，敌手(adversary)。用户沿着目标轨迹运行，每到一个目标轨迹上的指定位置，就担任一次证明者的角色。本发明中将目标轨迹划分为一系列等间隔的离散点P1,P2,…,Pn。

[0111] 本发明中用户是以证明者的身份参与到密钥交换过程的。当验证者与位于位置Pi(1≤i≤n)的证明者进行基于位置的密钥交换协议后，证明者与验证者之间会协商共享密钥。设门限为t(t≤n)，当某一用户同时拥有h(t≤h≤n)个子密钥时，即可恢复出最终的共享密钥S。否则，则认为用户不是按着目标轨迹运行的，无法得到最终的共享密钥S。验证者可根据共享密钥，对用户的身份进行确认，然后凭借此共享密钥与用户进行安全的通信。

[0112] 参照图1，本发明的具体实施步骤如下：

[0113] 1、建立系统模型：

[0114] 在d(1≤d≤3)维空间里，为完成基于离散轨迹的密钥交换协议，用户雇佣验证者V＝{V1,V2,…,Vg}(g≥d+1)，用户和所有验证者之间存在安全信道。验证者之间通过私有通道共享信息，该私有通道是指该通道只被用于特定的实体之间通信，即只用于验证者之间的通信，其中传递的消息不能被其他实体所截获，用于消息的安全传递。

[0115] 以三维空间为例，n个证明者分别称其位于离散轨迹上的P1,P2,…,Pn点，且P1,P2,…,Pn等间隔分布。对于每个证明者Pi，其中1≤i≤n，采用四个验证者V1、V2、V3、V4，证明者均被封闭在由验证者所构成的四面体中，证明者身份的真实性需要验证者的确认。

[0116] 2、建立敌手模型：

[0117] 存在共谋敌手A＝{A1,A2,...,Ak}，能够控制整个网络环境，通过伪装攻击、窃听攻击、重放攻击的方法来进行攻击，欺骗验证者使其认为此共谋敌手是按照目标轨迹运行的，以计算得到最终的共享密钥。假设在本发明中不存在在离散轨迹上敌手的数量超过或等于门限t的情况，即在Pi(1≤i≤n)点的共谋敌手的数量k

[0118] 若k≥t，则说明敌手的数量大于或等于门限t，结合实际，由于目标轨迹对于敌手是未知的，而敌手想要在目标轨迹上，且保证数量超过门限t，敌手需要花费巨大的代价。因此，本发明不考虑此种情况。

[0119] 3、系统准备工作：

[0120] 验证者拥有最小熵为(δ+β)y的反向熵源，均可发送长字符串Xij，其中Xij∈{0,1}y，代表第i个点中的第j个字符串，y为信息串的长度，1≤i≤n，1≤j≤5。验证者可以通过伪随机生成器PRG生成密钥K←{0,1}m，m为密钥的长度。当验证者发送的信息串高速经过敌手时，敌手能够提取信息串的任意函数，但是所提取函数的信息量必须小于或等于存储上限βy，其中βy是最小熵为(δ+β)y的总信息量的任意部分。

[0121] 所有验证者与证明者传送消息的速度都等于无线电波的速度，验证者收到消息与计算数据之间不存在时间延迟。

[0122] 4、独立离散点上的共享密钥生成阶段：

[0123] 以位于点P1的证明者为例，与验证者之间生成共享密钥：

[0124] 4a)参照图3，设T为位于位置P1的证明者同时接收到4个验证者发送消息的时刻，为了使消息同时到达位于位置P1，设Ti为消息从第i个验证者到达位置P1所需要的传输时间，1≤i≤4，则T-Ti时刻就是验证者Vi给位于P1的证明者发送消息的时刻。

[0125] 验证者V1通过伪随机生成器PRG生成密钥K11，并在T-T1时刻广播消息(X14，K11)，验证者V2在T-T2时刻广播消息(X11，X15)，验证者V3在T-T3时刻广播消息X12，验证者V4在T-t4时刻广播小心X13。

[0126] 4b)在时刻T，位于P1的证明者同时收到4个验证者广播的消息，根据收到的4个信息串(X14，K11)、(X11，X15)、X12、X13，利用公式Ki,j+1＝PRG(Xi,j,Ki,j)，1≤j≤5，i＝1，计算得到K16，具体计算为：

[0127] K12＝PRG(X11，K11)，

[0128] K13＝PRG(X12，K12)，

[0129] K14＝PRG(X13，K13)，

[0130] K15＝PRG(X14，K14)，

[0131] K16＝PRG(X15，K15)，

[0132] 即位于P1的证明者得到与验证者之间的共享密钥K16，记为S1。

[0133] 5、主密钥生成阶段：

[0134] 5a)类似于步骤4，位于P2,P3,…,Pn点的证明者可利用公式：

[0135] Ki,j+1＝PRG(Xi,j,Ki,j),1≤j≤5,2≤i≤n

[0136] 分别在不同的时刻计算得到他们与验证者之间的共享密钥S2，S3，…，Sn。

[0137] 5b)最终的主密钥

[0138] 5c)验证者之间通过私有通道秘密地传输并安全地保存好主密钥S。

[0139] 6、密钥分发阶段：

[0140] 参照图4，该部分的具体实现如下：

[0141] 6a)位于P1,P2,…,Pn的证明者均随机选取t-1个整数ai,1,ai,2,...,ai,t-1,1≤i≤n，构造一个t-1次多项式：Fi(x)＝Si+ai,1x+ai,2x2+…+ai,t-1xt-1，要求使得Si＝Fi(0)。

[0142] 6b)位于Pi的证明者计算Mi,j＝Fi(j),1≤j≤n,并把消息Mi,j安全秘密地发送给其他的证明者Pj。

[0143] 6c)位于Pi的证明者在收到所有其他的证明者发送的消息后，计算

[0144]

[0145] Mi就是证明者Pi关于最终的主密钥S的子密钥。

[0146] 7、主密钥恢复阶段：

[0147] 当某一用户沿着目标轨迹运行，同时拥有任意t个子密钥Mi时，根据拉格朗日插值公式，即可计算出最终的主密钥S，具体计算为：

[0148]

[0149] 即拥有到达门限值t个子密钥的用户被视为是沿着目标轨迹运行的，可得到与验证者之间协商的主密钥S。

[0150] 8、验证者确认阶段：

[0151] 参照图5，验证者将步骤5中自己所计算得到并安全保存的主密钥与用户计算得到的主密钥进行比对:

[0152] 8a)若相同，则证明此用户是沿着目标轨迹运行的，是合法安全的用户，之后可凭借此共享的主密钥进行安全通信；

[0153] 8b)若不同，则证明拥有此密钥的用户未按照目标轨迹运行，而是共谋敌手企图利用一个错误的随机数干扰系统的通信，验证者之后将拒绝与此用户进行通信。

[0154] 本发明方案中，验证者凭借自己的主密钥对用户的身份进行了再次的确认，充分保障了系统通信的安全性。

[0155] 下面给出一个证明实例，证明本发明方案的安全性。

[0156] 实施例6

[0157] 基于离散轨迹的密钥交换方法同实施例1-5，本发明是一个(t,n)门限密钥共享方案，满足(t,n)门限密钥共享方案的要求。

[0158] 密码学中的(t,n)门限密钥共享方案必须满足如下规则：

[0159] t个或t个以上的参与者联合可以恢复所共享的主密钥；而t-1个或更少的参与者的合作不能恢复该主密钥，甚至不能得到关于该密钥的任何信息。

[0160] 所以需要证明，在本发明方案中，t个或者更多的证明者可以用他们的子密钥来恢复主密钥S，而少于t个证明者无法获得主密钥的任何信息。

[0161] 证明如下：

[0162] 在本发明基于离散轨迹的密钥交换方案中，每一个证明者P1,P2,……,Pn均随机选取t-1个整数ai,1,ai,2,...,ai,t-1,1≤i≤n,构造一个t-1次多项式：Fi(x)，使得证明者与验证者之间的共享密钥Si满足Si＝Fi(0)。

[0163] 令F(x)满足 可以看到，F(x)也是t-1次多项式，并且主密钥满足S＝F(0)。因此，只需要说明每个证明者的子密钥Mi满足Mi＝F(i)即可。

[0164] 在本发明中，证明者的子密钥Mi满足 而Mj,i＝Fj(i)，可得到：

[0165]

[0166] 从而证明了：

[0167] 在本发明中，t个或者更多的证明者可以用他们得到的子密钥来恢复主密钥S。

[0168] 而少于t个证明者想成功地攻破Shamir的(t,n)门限方案，这在计算上是不可行的；由于最终的主密钥是所有参与者的次密钥的和，即主密钥S是所有证明者们共同参与生成的，任何单独的证明者都不知道关于主密钥的信息，所以少于t个证明者无法恢复最终的主密钥S。

[0169] 由此可知，本发明是一个(t,n)门限密钥共享方案，满足(t,n)门限密钥共享方案的要求。

[0170] 证明完毕。

[0171] 本发明考虑到随着轨迹数据的增多，对每一个监测点进行验证的难度则会增大，因此，门限的思想，即密钥共享的机制被引入。同时，考虑到了用户沿着目标轨迹运行的误差问题，即使丢失了n-t个子密钥，仍认为此用户是按照目标轨迹运行的，即可以恢复出最终与验证者之间协商的主密钥。因此，本发明还具有较高的灵活性。

[0172] 简而言之，本发明公开的一种基于离散轨迹的密钥交换方法，主要解决现有密码学技术中缺少以离散的目标轨迹作为用户身份凭据的密钥交换方法。其实现方案为：建立系统模型和敌手模型；证明者分别通过基于位置密钥交换得到与验证者的共享密钥，主密钥为各个共享密钥之和；证明者之间进行密钥的分发，得到子密钥；设门限为t，当某用户沿着目标轨迹运行，同时拥有任意t个子密钥时，则可恢复出与验证者协商的主密钥；验证者可凭借主密钥与用户进行安全通信。本发明将(t，n)门限密钥共享技术和基于位置的密钥交换技术结合，由单一位置扩展到目标轨迹上的n个离散位置，用户同时承担了密钥共享者与分发者的角色，主密钥安全性强，能有效抵御多个敌手的共谋攻击，为安全通信提供了一种新的密钥交换方法，可用于在有敌手控制的网络环境中为通信的实体之间建立共享的密钥。