基于共有信息构建与节点选择的对称密钥生成与交换方法

1.本发明属于通信网络安全领域，特别涉及一种密钥生成与交换技术。


背景技术：

2.近年来，随着网络应用的不断发展，网络安全攻击的数量和破坏力也在不断提高。加密技术因其对网络数据机密性和完整性的有效保护能力，在网络安全保障中发挥了重要的作用。其中，对称加密算法因系统开销低、加密数据量大而广泛用于数据传输保护过程。为了保障密钥的安全性，dh(diffie-hellman，迪菲-赫尔曼)密钥交换协议被广泛应用于对称密钥的生成与交换过程。在该协议中，因通信双方依靠共享大素数生成密钥，导致中间人在窃取了一方发送的大素数后，可冒充另一方继续进行密钥协商；同时，中间人可向另一方发送新的大素数，和另一方生成新的密钥。
3.当前为解决dh密钥交换协议面临的中间人攻击问题，主要有两类防御方法：一种是对通信用户进行认证的方法，另一种是保护密钥生成过程的方法。但是这两类方法都存在一定的缺陷，通过证书认证和身份认证抵抗中间人攻击的方法需要借助第三方的帮助，这就要求第三方完全可信，但在现实中较难保障。利用转换编码器、二进制生成器、数字签名和上下文感知对密钥生成过程进行保护的方法会导致计算复杂度和密钥生成时间等方面代价的提高。


技术实现要素：

4.为解决上述技术问题，本发明提出一种基于共有信息构建与节点选择的对称密钥生成与交换方法。
5.本发明采用的技术方案为：一种基于共有信息构建与节点选择的对称密钥生成与交换方法，包括：任意两个节点从通信周期中得到有效消息，由有效消息生成共有信息，对其进行一致性验证后，再用共有信息生成大素数，并通过dh密钥交换协议生成对称密钥；生成对称密钥的过程为：
6.a1、通信双方通过对通信过程中的消息取哈希的方式进行完整消息匹配或部分消息匹配，得到有效消息；
7.a2、通信双方按照有效消息中的控制字段和内容字段从有效消息中分别进行数据抽样，得到控制矩阵u和内容矩阵v，将两个矩阵融合后得到共有信息矩阵；
8.a3、利用共有信息矩阵是实对称矩阵，对其进行特征值求解和特征向量分解后，用特征向量对双方的共有信息进行一致性验证；
9.a4、对共有信息矩阵的特征值素数化，得到因素基，对因素基按照因素基更新算法进行多次迭代后得到计算大素数g和p需要的素因子，随后计算出满足要求的大素数g和p；
10.a5、最后通信双方根据从共有信息中得到的大素数进行dh密钥交换协议进行协商生成对称密钥，并用消息验证码确保消息密钥协商在通信过程中不被篡改，以实现对称密钥的生成；消息验证码根据共有信息矩阵取哈希的数据生成；
11.还包括：在通信需求、计算能力和存储能力的约束下，选择网络中部分节点作为共有信息节点进行密钥生成；具体包括以下步骤：
12.b1、对于网络中的节点，计算基于共有信息生成密钥的存储和计算开销；
13.b2、根据步骤b1的计算结果，得出相比于使用传统dh密钥交换协议的存储和计算开销加重率；
14.b3、基于密钥的破解时间分析，得出相对于使用传统dh密钥交换协议，基于共有信息生成密钥的安全性提升率；
15.b4、在节点通信频率、计算和存储能力的约束下，建立最大化系统安全性提升率和最小化系统开销加重率的优化模型；
16.b5、通过遗传算法求解该优化模型得到共有信息节点的选择策略。
17.本发明的有益效果：本发明的方法，通过历史通信消息生成共有信息，再通过dh密钥交换协议生成对称密钥，既扩展了历史通信消息的作用，又提高使用dh密钥交换协议生成对称密钥协商时的安全性。同时，本发明通过选择部分节点作为共有信息节点生成密钥，可以适用于不同规模的网络，实现该网络的安全性和开销均衡，具有良好的泛化能力与广泛的应用前景。
附图说明
18.图1为基于共有信息的对称密钥生成机制的架构图；
19.图2为有效消息匹配机制；
20.图3为节点选择优化模型示意图；
21.图4为cipss算法的数据传输流程图。
具体实施方式
22.为便于本领域技术人员理解本发明的技术内容，下面结合附图对本发明内容进一步阐释。
23.针对dh密钥交换协议的中间人攻击问题，本发明首先设计了基于共有信息的对称密钥生成机制，通信双方先从通信周期中得到有效消息，由有效消息生成共有信息，对其进行一致性验证后，再用共有信息生成大素数，并通过dh密钥交换协议生成对称密钥。然后为了实现在网络中共有信息节点体系的高效构建和维护，本发明设计了基于遗传算法的共有信息节点的选择机制，在通信需求、计算能力和存储能力的约束下，选择网络中部分节点作为共有信息节点进行密钥生成，实现开销和安全性均衡的系统构建。下面对技术方案做具体的描述：
24.1、基于共有信息的对称密钥生成机制
25.本发明是利用通信过程中积累的消息内容进行计算，通信双方对于从发送消息中得到有效消息，不能通过对乱序、丢失的数据帧进行重传、重组等方式来实现，同时也不能切入、改变通信的机制和过程。因此，需要在全局数据帧不可靠的基础上，实现局部数据帧的一致性，并基于这种一致性，生成双方的共有信息。通信双方主机h1和主机h2为通信节点对，在h1和h2的通信频率达到一定的门限值f0(f0≥0)后，h1和h2可称为频繁通信节点对。此时，h1和h2可选择与对方协商、启动构建双方对于通信过程认识的共有信息。在构建时，用户
双方需使用的系统公开参数为九元组《t0，nm，n
p
，c，d，rc，rd，》，其中t0表示起始时间，nm(nm∈n
*
)表示每轮的消息积累数量，c(c≥3，c∈n
*
)表示控制矩阵列数，d(d∈n
*
)表示内容矩阵列数，rd(rd∈n
*
)和rc(rc∈n
*
)为随机数，表示本次基于共有信息生成密钥时dh密钥交换协议中需要使用的大素数p的位数，本次基于共有信息生成密钥时dh密钥交换协议中需要使用的本原根g的位数，本原根g也为素数且g＜p。
26.h1和h2的实时通信频率f仍处于不断的变化中，假设积累nm条消息需要的时间为tm，利用历史消息进行共有信息生成和对称密钥生成的时间为tc，nm的值可由nm＝d(f，tc)进行设定。其中函数d(f，tc)的设计原则是：a)当f较小时，应减小nm，使消息积累时间tm缩小，保证h1和h2能及时更新密钥；b)当f较大时，应增大nm，使tm＜tc，保证h1和h2有充足的时间更新密钥。因此，nm应随f与tc进行动态调整。同时，基于共有信息生成密钥的安全性与有效消息数量相关，为保证生成密钥的安全性，则当f较小时，nm有最小值nm≥n0＝d(f，tc)。如果h1和h2协商通过使用本方案进行对称密钥生成，则在给定时刻t0起，h1和h2将其与对方通信的消息分别存储于各自的缓存c1与c2中。当h1或h2中任一方缓存的消息达到预定数量nm时，该方将会向另一方发起有效消息匹配请求，双方经过有效消息匹配机制得到用于生成共有信息的有效消息集合me。然后，h1和h2利用共有信息生成算法得到共有信息矩阵k，并且对k进行一致性验证。随后，h1和h2利用矩阵k的特征值和大素数生成算法得到相同的大素数p和本原根g。最后，h1和h2执行dh密钥交换协议，协商出对称密钥。h1和h2利用共有信息生成的对称密钥将被用于后续通信数据的加解密中，保证通信过程中数据的安全性。基于共有信息的对称密钥生成机制的系统架构图如图1所示，下面将从有效消息匹配机制、共有信息生成算法、一致性验证和大素数生成与密钥协商机制这四个方面进行介绍。
27.假设密钥更新的周期为t
key
(t
key
由网络管理员给定)，利用本发明生成一个新的密钥的时间包含：积累nm条消息需要的时间tm和利用历史消息进行共有信息生成和对称密钥生成的时间tc两部分，当时(即新生成的密钥所能被使用的时间不足密钥更新周期的三分之一时)，认为f较小；当时(即新生成的密钥所能被使用的时间超过密钥更新周期的三分之二时)，认为f较大。
28.(1)有效消息匹配机制
29.有效消息匹配机制如图2所示，包括通信模式协商、通信消息积累和有效消息匹配三个阶段。在通信模式协商阶段，h1和h2协商开始新一轮通信周期及相关信息，通信发起方h1或h2会向另一方发送通信周期开始请求，该方收到后应答该请求。随后进入通信消息积累阶段，h1和h2进行正常的通信交互过程，当其中一方的消息缓存数量达到nm时，该节点将发出有效消息匹配请求。
30.如在图2中，当h2发出第nm条消息后，随后进入有效消息匹配阶段。h2先向h1发送完整消息匹配请求，h1收到该请求后，进行一次完整消息匹配；若匹配成功，则向h2发送应答消息；否则匹配失败即h1和h2分别积累的通信消息集合和和存在不一致，则h1和h2可按照双方约定的规则分别对上一轮的消息集合s1和s2取其中的子集和并基于和进行匹配，即进行部分消息匹配。此时，n
p
(n
p
∈n
*
)表示取其中部分消息进行匹配测试的最大次数，即取s1和s2的子集数量最大为n
p
。理论上消息集合s1和s2的非空真子集有个，即n
p
最大可以取为但是在
实际应用中，考虑到每进行一次部分消息匹配需要消耗一定的计算和通信资源，为了保障开销在一定限度内，n
p
一般不设置为指数级别的大小，本发明中设置n
p
＝2nm，在其他网络中n
p
可以根据通信场景需求进行调整。若在n
p
次进行部分消息匹配后，双方仍未匹配成功，则舍弃本轮通信周期中的消息，重新开始新一轮的通信周期。在h1或h2进行有效消息匹配成功后，得到n条有效消息的集合并向对方发送一次匹配成功应答，进行共有信息的计算过程。
31.在进行完整消息匹配与部分消息匹配时，h1和h2会对按时间先后顺序进行排列的消息取哈希，当双方的哈希结果一致时，有效消息匹配成功。h1和h2在进行部分消息匹配时，分别对集合和取哈希，其中k∈[1，nm]，当时，则部分消息匹配成功。其中，集合和中的消息m
1，j
和m
2，j
(j∈[1，nm])需要用函数s(x)对s1和s2中的消息进行取样，s(x)函数的设计原则是保证在预期的n
p
次哈希结果对照中，每次采样的消息尽量少重叠和单一消息出现在两次哈希对照中的概率尽量小。本发明中，s(x)为步进函数s(x)＝ai+1，其中a＝2，3，4等，此时a的取值与本轮通信周期中设定的nm、n
p
相关。在实际应用中，s(x)根据通信场景需求进行调整或重新设计。具体而言，nm和n
p
共同决定了a的取值范围，步进函数中1≤ai+1≤nm，i≥0且i∈z，初始时i＝0，后续在每一次采样时i以每次增加1的步长逐渐递增，由于当a＝1时表示可以取到所有的这nm条消息，因此在进行部分消息匹配时，需设定a≥2，且a的取值将随着采样次数的增加而增加，假设每次a以大小为y的步长进行增加，则在第n
p
次采样时，a＝2+y*n
p-1≤nm。下面进行举例说明，当积累的消息数量nm＝10，最大匹配次数n
p
＝2，每次采样时a以大小为1的步长进行增加即y＝1时，可以得到a的取值为a＝2，3，则第一次采样时a＝2，h1可以得到此时采样的消息集合为第二次采样时a＝3，h1可以得到此时采样的消息集合为
[0032]
y的取值由a的取值决定，由于a表示每一次采样过程中，相邻两次抽到的消息的标号间隔，因此a最大为n
m-1，因此y≤n
m-1。
[0033]
(2)共有信息生成算法
[0034]
h1和h2在计算共有信息时，首先从有效消息的控制字段与内容字段中分别进行数据抽样以得到控制矩阵u与内容矩阵v，然后利用u和v计算出共有信息矩阵k。
[0035]
在构造矩阵u和v时，分别对与中的信息进行数据抽样后能得到u和v的一个行向量和进而从n条有效消息中得到矩阵u和v。对中的数据进行抽样时，首先将包含字段的字节按顺序拼接成一个字段，其中含有个字节，然后根据控制矩阵列数c，随机数rc和进行数据抽样，抽样规则为：当消息字段中的字节数量少于抽样数量时，将消息字段中的字节均作为抽样字节数据，其余部分补零，即
[0036][0037]
而当消息字段中的字节数量可支持进行随机抽样时，中的个字节进行分成c组，从每一组数据中进行抽样，每一组的数据量为分成c组，从每一组数据中进行抽样，每一组的数据量为为向下取整运算，并通
过抽样随机数和ξi进行数据抽样得到uy。的初始值为rc，根据ξi可对进行调整，使其能均匀地从数据报文中进行数据抽样，有
[0038][0039]
从而得到其中且j≤c
×
ξi。而对中的数据进行抽样时，用内容矩阵列数d、随机数rd和含有的字节数量分别对c、rc、和进行替换，从而得到向量中的每个数据以构造出n行c列的矩阵u与n行d列的矩阵v，
[0040][0041]
然后，由u和v得到矩阵w，
[0042][0043]
矩阵w的意义是将内容信息投影到控制信息对应的空间中，使h1和h2以理解控制信息字段的方式理解内容信息字段。但矩阵w并非方阵，无法直接求特征值，可令矩阵w与其转置矩阵相乘得到为方阵的共有信息矩阵k，
[0044][0045]
对矩阵k进行特征值与特征向量求解后，可得到特征值组成的集λ＝{λ1，λ2，
…
，λc}和对应的特征向量构成的矩阵λ和γ分别用于大素数的生成过程和对共有信息进行一致性验证。
[0046]
(3)一致性验证
[0047]
由公式(5)可知，矩阵k为实对称矩阵，则不同特征值对应的特征向量之间相互正交。本发明利用矩阵k的特征向量对h1和h2分别计算出的矩阵k进行一致性验证，由于特征向量不参与大素数的计算过程，且无法由特征向量反推出特征值，则在通信网络中传输特征向量不会影响密钥协商过程的安全性。
[0048]
对共有信息的一致性验证过程包括特征向量乘法验证与特征向量哈希验证。若h1先向h2发送共有信息的一致性验证信息，h1先从γ矩阵中随机选取个特征向量组成的验证矩阵n
*
表示非零自然数，是h1从γ中随机选取的特征向量，并将剩下c-n个特征向量按对应特征值大小进行排序构成矩阵γ1，对γ1取哈希后可得到hash(γ1)，η1和hash(γ1)构成共有信息的一致性验证信息。h2在收到h1发送的验证信息后，首先用γ对η1进行矩阵相乘验证，由γ与η1相乘可得到矩阵ρ，
[0049][0050]
由不同特征值对应的特征向量之间有相互正交的关系，则ρ中只有n个不为零的
值，且每一列只有一个不为零的值。当ρ
i，j
≠0(i，j∈[1，c]，且)，则有且.且.且.表示正整数，h2通过ρ中不为零的值ρ
i，j
对η1进行验证，且得到组成η的n个特征向量，这n个特征向量由n个不为零的值ρ
i，j
得到。随后，h2得到由c-n个特征向量构成的矩阵γ1′
，对γ1′
取哈希可得到hash(γ1′
)，对比hash(γ1)与hash(γ1′
)可验证剩下的c-n个特征向量是否相同。满足以上条件则h2可确定双方生成的共有信息相同，同时防止第三方篡改共有信息的验证信息。h2从γ1中抽取的n
′
(n
′
∈[1，c-n])个特征向量组成的验证矩阵η2，利用γ矩阵中的c-n
′
个特征向量组成新的矩阵γ2并取哈希后得到hash(γ2)，得到h2发给h1的共有信息一致性验证信息；随后，h1按上述方法对h2生成的共有信息进行验证。
[0051]
(4)大素数生成与密钥协商机制
[0052]
h1和h2将利用矩阵k的特征值和大素数生成算法得到相同的大素数p和本原根g。由于特征值集合λ中的元素不全为素数，在基于集合λ构造小素数集合时，首先令距离每个于特征值集合λ中的元素不全为素数，在基于集合λ构造小素数集合时，首先令距离每个最近的奇数代替λi；然后用miller-rabin素数检测算法对λi进行素性检测，当λi不为素数时，令λi＝λi+2，重复此过程至λi为素数；最后对小素数集合中的λi按大小排序后，得到初始因素基b0＝{b1，b2，
…
，bc}(bi＝λi)。
[0053]
设第i(i∈n)轮更新的因数基为bi，b0为初始因数基，且bi中的各个素数为b
i，j
(1≤j≤c，j∈n
*
)，更新b
i，j
的公式为
[0054][0055]
其中，α为幂乘因子，h1和h2可通过调整α，对因数基的更新速度进行调整，本发明中α＝1；δ(δ∈n
*
)为素数距离，表示由多个素因子进行幂乘后得到的奇数与素数b
i+1，j
的之间的距离，δ的初值为零。若对公式计算出b
i+1，j
用miller-rabin算法检测出b
i+1，j
不是素数，则令δ＝δ+1，得到新的b
i+1，j
，再对其进行素性检测，直至b
i+1，j
为素数，该过程即增量素数生成算法；在计算出素数b
i+1，j
后，得到因数基b
i+1
。
[0056]
在对bi进行更新之前，会先通过对b
i+1
中最大的素数b
i+1，c
的位数f(b
i+1，c
)与素数p的位数进行比较，以判断因素基bi是否为最后一轮因数基。使用表示估计数x的位数，当x＝b
i，j
时，表示估计素数b
i，j
的位数，其中为向上取整操作。设有整数a0和a1，乘积a2＝a0a1，则log2a2＝log2a1+log2a0，且a2的位数f(a2)满足f(a0)+f(a1)-1≤f(a2)≤f(a0)+f(a1)将此式代入式(7)可以得到
[0057][0058]
若时，下一轮计算出的素数位数小于大素数p的位数表明bi不为b
l
，则需要更新计算出因数基b
i+1
，并保留bi中的最大素数b
i，c
，将其加入集合φ；否则，大素数，将其加入集合φ；否则，大素数表明b
l
＝bi，则终止更新因数基。b
l
表示最后一轮因素基。
[0059]
由公式(8)可知，b
i+1，j
的位数取决于参与计算b
i+1，j
过程的素因子，且b
i+1，j
与b
i，j
之间的位数差距巨大。b0中包含的素数b
0，j
之间的位数差异会影响因数基更新后b
i，j
之间位数的差异；若b0中b
0，1
到b
0，c
之间的位数差距不大时，则在一轮因数基更新后，b
1，1
到b
1，c
之间位数差异也不大；但b
i，j
与b
i+1，j
之间位数差异很大，即f(b
i，j
)≈f(b
i，j+1
)且f(b
i+1，j
)≈(c-1)
×
f(b
i，j
)。因此，在对更新因数基时，其更新结束条件为判断第i+1轮因素基b
i+1
中最大的素数b
i+1，c
的位数f(b
i+1，c
)是否大于同时，b
l
中的b
l，j
不会全参与p的计算过程，则可通过减少b
l，j
的计算个数提高因数基更新速度，由且θ
l
为参与p计算过程的b
l，j
个数，可得到需要b
l
中的θ
l
个素数组成的集合为
[0060]
由于素数分布的不均匀性，在更新素数b
i，j
的过程中，用miller-rabin算法进行素数判定次数是随机的，但更新b
i+1，j
的平均时间消耗随素数b
i+1，j
的位数的增加而提高；因此，更新因素基b需要一定的时间消耗，且无法直接由初始因数基b0计算出后续的素数，防止第三方快速破解密钥协商过程中的素数。
[0061]
因素基更新完成后，最后一轮因数基b
l
中的素数与其他因数基bi(0≤i＜l)中的最大素数b
i，c
组成的集合φ＝{b
0，c
，b
1，c
，
…
，b
l-1，c
}可得到计算p的直接因数基b
φ
，φ为b
φ
的子集。由于
[0062][0063]
则有参与素数计算时，会使计算得到的奇数位数大于，因此只需要计算θ
l
个素数即可。从集合φ中得到b
φ
中需要b
i，c
的数量的数量表示自然数。首先由表示自然数。首先由δl-θi×
f(b
i，c
)≤f(b
i，c
)，可从b
l-1
中可得到θ
l-1
个值为b
l-1，c
的素因子，随后令δl＝δl-θi×
f(b
i，c
)，重复该过程得集合)，重复该过程得集合然后由公式
[0064][0065]
计算出素数p。其中，由于的位数f(pd)不一定和相等，因此令其与2
β
相乘可得到位数为的奇数p
′d，其中由计算出β；随后，由增量素数生成算法得到素数p。
[0066]
由于可按上述方法中p换成g并将换成即可求得g。
[0067]
通信双方用大素数g和p执行dh密钥交换协议时，首先双方生成r1与r2，用户h1计算出的公开数并利用对共有信息矩阵k哈希生成消息验证码mac1→2，然后将x1与mac1→2发送给用户h2；用户h2收到并验证mac1→2后，计算出公开数同时计算出消息验证码mac2→1，并将mac2→1和x2一起发送给用户h1；用户h2和用户h1用共有信息矩阵k验证mac值为真后，分别由和计算出对称密钥，完成密钥协商。
[0068]
2、基于遗传算法的共有信息节点选择机制
[0069]
为了实现网络中共有信息节点体系的高效构建与维护，本发明进一步提出了基于遗传算法的共有信息节点选择机制。考虑到网络中不同节点的通信需求、计算能力和存储能力存在较大差异，让任意两个节点间都构建共有信息生成密钥会带来较大的开销。因此，该机制首先对基于共有信息生成密钥的存储和计算开销进行了分析，分别得出相比于使用传统dh密钥交换协议的存储和计算开销加重率。然后，该机制基于密钥的破解时间分析，得
出了相对于使用传统dh密钥交换协议，基于共有信息生成密钥的安全性提升率。其次，在节点通信频率、计算和存储能力的约束下，建立了最大化系统安全性提升率和最小化系统开销加重率的最优化模型，并通过遗传算法求解该模型得到共有信息节点的选择策略。
[0070]
为了兼顾动态性不同的网络，本发明将每隔一段时间t对共有信息节点进行调整以实现节点间共有信息的维护和更新。具体而言，对于一些较为稳定的网络，网络的拓扑结构和节点间的通信行为几乎不变，则t就可以设置为无穷大。而在有些较为不稳定的网络中，比如一些动态变化的无线网络，网络的拓扑结构和节点间的通信行为变化较快，则需设置t为比较小的值。由于当网络不稳定时，对每个周期r(r∈n
*
)内的开销和安全性进行简单的叠加是没有意义的，本发明后面将以第r个周期内的网络情况进行具体分析。假设网络是由n个节点组成的无向图，每个顶点代表网络中的一个节点。该网络可以表示为g＝(v，e)，其中v表示网络中的节点集合，e表示这些节点之间的物理链路集合，这n个节点组成集合其中v表示网络中的节点集合，e表示这些节点之间的物理链路集合，这n个节点组成集合在共有信息节点体系中的节点由两种类型的节点组成：共有信息节点和普通节点。其中，共有信息节点基于共有信息生成密钥，普通节点使用传统dh密钥交换协议生成密钥。假设节点hi的存储能力为节点hi和节点hj间的通信频率为f
i，j
(r)，若f
i，j
(r)＞0，则ψ
i，j
(r)＝1，表示节点hi和节点hj在第r个周期内存在通信行为，否则ψ
i，j
(r)＝0。下面将从存储开销分析、计算开销分析、安全性增益分析、共有信息节点选择的优化模型和基于遗传算法的模型求解算法这五个方面进行具体介绍。
[0071]
t具体的取值由网络的拓扑结构和节点间的通信行为变化的快慢决定，需要具体情况具体讨论。比如，在一个动态变化的车联网中，快速移动的车辆需要向路侧单元传递车辆信息，但由于车辆的移动性，每隔5分钟很多车辆离它最近的路侧单元就会发生变化，这时候在该车联网中拓扑结构和节点间的通信行为将发生变化，此时应设置t小于5分种，但不应设置的过小，t需大于基于遗传算法的共有信息节点选择机制的运行时间，以保证所选择的共有信息节点能够更大限度地根据当前网络的状态保护网络中数据的传输。
[0072]
(1)存储开销分析
[0073]
在基于共有信息生成密钥的过程中，存储开销主要包含在生成共有信息的过程中，矩阵u和v会占用较大的存储空间，为n(c+d)字节，其中n为有效消息的数量，c和d分别为控制矩阵和内容矩阵的列数；以及在素数生成过程中，最后一轮更新的因数基会占用较大的空间，这与每个素因子的位数f(bi)相关，更新的素因子平均位数为)相关，更新的素因子平均位数为其中，l0为初始因素基的平均长度，z为因数基更新轮数，分析矩阵k的计算过程，可得c为初始因素基中素数的个数，τ为消息中每个字节的平均值，n表示有效消息的数量，则消息数量对素数生成过程的存储资源消耗影响很小。因此可知在共有信息节点体系中，节点hi和节点hj花费的存储开销为
[0074][0075]
式(11)中的ξ1表示最后一轮因素基占用的存储空间和更新的素因子平均位数为ξ1倍的正比关系。
[0076]
传统dh密钥交换协议中的存储开销主要包含以下几个方面：
[0077]
(a)公开参数存储开销：传统dh密钥交换协议需要提前共享一些公开参数，比如素数p和本原根g。这些参数需要在协议开始前进行共享，并在协议的执行过程中被使用。因
此，存储这些公开参数的开销是传统dh密钥交换协议开销的一部分。
[0078]
(b)私有密钥存储开销：在传统dh密钥交换协议中，每个参与者都需要生成一个私有密钥，该私钥通常是一个随机生成的大素数，足够大的数可以保障不容易被猜测或通过暴力破解算法计算出来。这些私有密钥需要在协议执行过程中被使用，因此需要进行存储。
[0079]
(c)中间值存储开销：在传统dh密钥交换协议中，每个参与者都需要计算一个中间值，并将其发送给另一个参与者。这些中间值需要在协议执行过程中被存储。
[0080]
(d)密钥存储开销：在传统dh密钥交换协议完成后，参与者需要存储计算出的密钥，这些密钥将在后续的通信中被使用。
[0081]
上述四个方面的存储开销都和大素数的位数相关，且由于大素数的位数与dh密钥交换协议的安全性息息相关，通常会使用位数较长的大素数来保障安全，因此传统dh密钥交换协议的存储开销主要和大素数的位数有关。可以得到节点hi和节点hj使用传统dh密钥交换协议生成密钥的存储开销为
[0082][0083]
式(12)中的ξ2表示节点存储开销和大素数的位数为ξ2倍的正比关系。由式(11)和式(12)可以得到在第r个周期内节点hi和节点hj之间基于共有信息产生密钥相比于使用传统dh密钥交换协议的存储开销加重率为
[0084][0085]
(2)计算开销分析
[0086]
基于共有信息生成密钥中的计算开销主要体现在共有信息生成过程和密钥生成两个过程中，而后者的主要计算开销来源于大素数生成过程和密钥协商过程，但密钥协商过程的计算开销相对于大素数生成过程很少。因此基于共有信息生成密钥的计算开销主要为计算共有信息与计算大素数的过程中消耗的时间。
[0087]
在共有信息生成阶段，共有信息节点hi和节点hj主要的计算开销包含矩阵运算和共有信息矩阵的特征值分解；其中前者的计算开销与有效消息数量n和内容矩阵列数d相关，后者的计算开销与控制矩阵列数c相关但变化不大，因此共有信息生成阶段的计算开销主要和n和d相关，n和d越大所需要耗费的时间越多。因此，可以得到节点hi和节点hj进行共有信息生成阶段的计算开销为
[0088][0089]
式(14)中的ρ1表示节点hi进行共有信息生成阶段的计算开销和有效消息数量n和内容矩阵列数d的和为ρ1倍的正比关系。
[0090]
在大素数生成阶段中，大素数的搜索次数是一个随机的数值，且位数越高时，其搜索次数越长，因数基中的素数能够更好地辅助进行所求大素数的计算。由于不同的控制矩阵列数c决定了特征值的个数，而当c不同时，因数基b更新的轮数z也不同。在因数基更新完成后计算大素数的直接素因子，随后求出pd以及寻找距离p最近的素数，这一过程消耗的时间与素数位数相关。因此，可以得到节点hi和节点hj进行大素数生成阶段的计算开销为
[0091]
[0092]
式(15)中的ρ2和ρ3表示节点hi进行大素数生成阶段的计算开销和大素数的位数为指数关系。根据式(14)和式(15)可以得到在第周期r内，节点hi和节点hj使用共有信息生成密钥所需的计算开销为
[0093][0094]
传统dh密钥交换协议中的计算开销主要包含大素数生成、中间值计算和密钥计算这三部分。其中大素数生成需要由随机数发生器给出符合密钥位数要求的随机数，再通过素数生成算法和素数判定算法得到素数，这个过程和本发明中所使用的素数生成算法的计算开销相差不大，并且中间值计算和密钥计算相比于大素数生成所带来的计算开销太小，可以忽略不计。因此可以得到节点hi和节点hj使用传统dh密钥交换协议进行数据保护的计算开销为：
[0095][0096]
由式(16)和式(17)可以得到在第r个周期内节点hi和节点hj之间使用共有信息产生密钥相比于使用传统dh密钥交换协议带来的计算开销加重率为
[0097][0098]
(3)安全性增益分析
[0099]
在基于共有信息生成密钥的过程中，密钥安全性的保障由dh密钥协商机制和共享大素数的生成过程两部分提供，其中dh密钥协商协议的安全性是一个离散对数问题，由密钥交换信息中的大素数位数决定；而共享大素数生成过程的安全性由共有信息提供保证。若有敌手试图通过破解共享大素数获得节点hi和节点hj的通信密钥，需从有效消息中获得共有信息矩阵，才能通过共有信息的一致性验证过程和密钥协商时的消息验证码过程，对双方的密钥协商过程成功进行攻击；因此，敌手主要从有效消息中破解共有信息进而破解密钥。
[0100]
假设敌手能获得节点hi和节点hj之间的有效消息，并且明确从矩阵u和v得到矩阵k与计算共享大素数的过程，但未得到从有效消息生成矩阵u和v的方法，分析敌手对本方案进行破解需要的时间开销。敌手在破解时，通过不断地尝试从每条有效消息中得到长度为c的向量和长度为d的向量，进而生成矩阵u和v。其中，敌手破解的次数主要有效消息数量n和内容矩阵列数d相关，由此得到当基于共有信息生成密钥时，敌手破解节点hi和节点hj间密钥的破解时间为
[0101][0102]
式(19)中的ψ1表示敌手破解节点hi和节点hj间密钥的时间与有效消息的数量n和内容矩阵的列数d的和为ψ1倍的线性关系。
[0103]
传统dh密钥交换协议与密钥传输机制和密钥相关，其中密钥传输机制在数学难题原理上保证了安全性；对于密钥本身的安全性，dh密钥交换协议中是由共享大素数决定，共享大素数的产生首先需要随机数发生器给出符合密钥位数要求的随机数，再通过素数生成算法和素数判定算法得到素数。因此传统的密钥交换协议中密钥本身的安全性主要由素数位数决定。由此得到当使用传统dh密钥交换协议时，敌手破解节点hi和节点hj间密钥的破解
时间为
[0104][0105]
式(20)中的ψ2表示当使用传统dh密钥交换协议时，敌手破解节点hi和节点hj间密钥的时间与大素数的位数为ψ2倍的线性关系。
[0106]
由式(19)和式(20)可以得到在第r个周期内节点hi和节点hj之间相比于使用传统dh密钥交换协议，在密钥破解时间方面使用共有信息产生密钥带来的安全性提升率为
[0107][0108]
(4)共有信息节点选择的优化模型
[0109]
为了实现最大化共有信息节点系统安全性的同时，最小化系统开销，本发明建立了共有信息节点系统安全性和开销均衡的优化模型。在第r个周期内，只有通信节点双方都是共有信息节点时，节点间才可以基于共有信息生成密钥，否则都使用传统dh密钥交换协议进行密钥生成。因此在共有信息节点体系中主要存在三种通信行为：共有信息节点和共有信息节点间的通信，共有信息节点和普通节点间的通信，以及普通节点和普通节点间的通信。令li(r)表示节点hi在第r个周期内是否被选为共有信息节点，若hi被选择为共有信息节点，则有li(r)＝1，否则li(r)＝0。可以得到网络中共有信息的节点个数为网络内的n个节点中有a个共有信息节点和b个普通节点和b个普通节点组成，h＝hc∪h
t
且n＝a+b。当共有信息节点和共有信息节点的通信频率f
i，j
(r)满足f
i，j
(r)≥f
min
时，令ζ
i，j
(r)＝1表示节点和节点之间的通信频率满足共有信息构建的最低频率要求，否则ζ
i，j
(r)＝0。
[0110]
由式(13)和式(18)可以得到共有信息节点体系构建的系统存储开销加重率η
sto
(r)和系统计算开销加重率η
com
(r)分别为
[0111][0112][0113]
式(22)和式(23)中的ψ
i，j
(r)表示节点hi和节点hj在第r个内是否存在通信行为，若f
i，j
(r)＞0，则ψ
i，j
(r)＝1，表示节点hi和节点hj在第r个周期内存在通信行为，否则ψ
i，j
(r)＝0。相比于使用传统dh密钥交换协议生成密钥，使用共有信息生成密钥保障用户间的每一次通信，可以提供更强的安全性保障能力，则由式(21)可以共有信息节点体系的系统安全性提升率η
sec
(r)为
[0114][0115]
由式(22)、式(23)和式(24)可得到系统安全性和开销均衡的优化模型为：
[0116][0117]
s.t.c1：li(r)＝{0，1}
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(25b)
[0118]
c2：f
i，j
(r)≥f
min
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(25c)
[0119][0120][0121]
式(25a)中，权重因子κ1和κ2分别表示安全性和开销在共有信息节点系统构建的重要程度且κ1+κ2＝1，0＜κ1＜1，0＜κ2＜1。权重因子μ1和μ2分别表示存储开销和计算开销的重要程度，且μ1+μ2＝1，0＜μ1＜1，0＜μ2＜1；式(25b)表示在第r个周期内，若节点hi被选择为共有信息节点，则有li(r)＝1，否则li(r)＝0；式(25c)表示两节点hi和hj间构建共有信息的通信频率限制；式(25d)表示在第r个周期内节点hi为计算共有信息所花费的存储开销必须小于该节点的存储能力限制；式(25e)表示在第个r周期内节点hi为计算共有信息所花费的计算开销必须小于一个阈值。最优化模型架构图如图3所示，通过该最优化模型可以实现存储开销、计算开销和安全性、网络规模均衡的系统构建。在不超过节点存储能力和计算开销的约束下，通过选择部分节点作为共有信息节点生成密钥提升网络的安全性的同时，还可以适应不同规模大小的网络，实现当网络中节点个数较多时也不会为网络带来较多的负担。
[0122]
(5)基于遗传算法的模型求解算法
[0123]
本发明中优化问题模型是关于整数离散变量li的求解，是一个0-1整数规划问题，属于np-hard问题中的一类。在该问题中，由于整数是不连续的，因此不能进行微分，导致无法使用微积分工具得到最优性条件。同时，由于离散无法满足凸性，通常只能求得近似解和局部最优解。不过，在该规划中，由于解空间是闭合的，因此目标函数b(r)(li)的最优解必然存在。本发明将使用遗传算法求解该0-1整数线性规划问题，遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向，能够高效地进行全局搜索。通过对种群进行重复的选择、交叉和变异操作，使每一代的染色体具有更好的适应性，最终得到最优解。
[0124]
设计了一个针对单目标优化的基于遗传算法的共有信息节点选择策略求解算法(cipss，common information point selection strategy)。首先定义相关参数，在网络中有许多设备，每个设备当做一个节点，且都有一个编号，用1，2，...，n依次表示，每个节点的是否被选择记录在数组vari(1≤i≤n)中，该数组表示一个解，其长度为节点的个数，即最优化问题中决策变量的个数，每一位的取值为0或1，0表示该节点没有没选中，1表示该节点被选中。表示遗传算法过程中的一个父代，num
p
为设置的种群数量，即在该父代中有num
p
个种群，一个种群表示一个可行解。初始父代也即遗传算法的初始输入为pop0，随着迭代次数的增加，每一次迭代得到的父代分别记为pop1，pop2，...，pop
maxit
，maxit为遗传算法中设置的最大迭代次数，当算法迭代次数达到该限额时，停止算法并输出结果。cr表示交叉率，mf表示缩放因子。cipss算法的流程图如图2所示，步骤如下：
[0125]
step1：初始化：根据定义的编码方式，在该算法中采用二进制编码，根据决策变量的个数(即节点个数n)确定染色体的长度，设置染色体上每个基因的取值范围为0或1；根据定义的种群大小num
p
，生成相应数量的个体，作为初始父代；对于每个个体，随机生成染色
体初始值，以确保初始父代的多样性；对于每个染色体上的基因，根据其取值范围生成一个随机数，并将其作为该基因的初值；重复以上步骤，直到生成足够数量的个体。
[0126]
step2：适应度评价：在优化算法中，适应度函数是用来评价解决方案的好坏的函数。由于本发明中最优化问题的目标函数值是非负的，因此采用目标函数值作为适应度值，其中函数值越大，适应度越高。这种方法可以确保优化算法能够找到最优解决方案，从而提高算法的效率和准确性，适应度函数为f(r)＝b(r)。
[0127]
step3：编码：由于本章的优化模型中决策变量取值只可能是0或1，因此采用2进制编码方式，每一个0或1称为一个基因位，染色体上每一位代表决策变量的真实值，具体二进制编码过程需要先对每个变量进行二进制取值，然后将每个变量的二进制串按顺序连接起来，形成一个整体的二进制串，即问题的解的二进制编码，二进制编码方式计算简单易于实现，且解码时也易于实现。
[0128]
step4：选择操作：采用一对一生存者竞争模式选择，使用一种简单的净值机制来选择父代个体，这种选择机制的主要思想是将种群中的每个个体与另一个随机选择的个体进行竞争，比较它们的适应度值，适应度值高的个体获胜并作为父代个体，采用一对一生存者竞争模式简单易懂，可以有效地引导种群朝着更优解的方向演化，同时可以有效避免出现轮盘赌选择机制中的局部最优问题。
[0129]
step5：交叉操作：交叉操作在遗传算法中起着核心作用，它随机选择两个个体并通过交换染色体的片段进行组合，将父串的优秀特征遗传给子串，以产生新的优秀个体，通过这种操作能够帮助搜索算法在多个优良的解之间进行探索，让遗传算法的搜索能力有一个飞跃式的提升。改进的差分算法的交叉算子主要有二项式交叉和指数交叉，本发明采用二项式交叉。二项式交叉算子首先会随机产生一个维标识j
rand
，用来确保最后得到的试验个体中至少有一维来自于变异个体，以免与当前个体相同，使得种群更加多样；然后，对当前个体的每一维随机产生一个0到1之间的实数，如果随机产生的实数小于交叉率cr，则试验个体的该维来自于变异个体；否则，试验个体的该维来自于当前个体。设父代的一个个体vari的某个基因位上的值为var
i，j
，则新个体var
′
i，j
的值计算如下：
[0130][0131]
step6：变异重组操作：变异重组操作用于改变群体中个体串中的某些基因位上的基因值，以提高个体的适应度。当遗传算法接近最优解邻域时，使用变异算子的局部搜索能力可以帮助加速向最优解收敛。这种方法可以提高算法的效率和准确性，从而在优化问题中取得更好的结果。假设从当前父代中随机选择了三个互不相同的向量记为x
y1
、x
y2
和x
y3
；然后，对x
y2
和x
y3
做差运算，得到差分向量；最后，通过缩放因子mf对差分向量进行缩放，并和基向量x
y1
做和运算，得到一个新的变异个体vi，具体公式如下：
[0132][0133]
式(27)中，mf是缩放因子，用来描述扰动量对变异向量的影响，一般取值为0到1之间的随机数；g代表种群的演进代数；表示基向量的索引。
[0134]
本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的
任何修改、等同替换、改进等，均应包含在本发明的权利要求范围之内。

技术特征：
1.一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，包括：任意两个节点从通信周期中得到有效消息，由有效消息生成共有信息，对其进行一致性验证后，再用共有信息生成大素数，并通过dh密钥交换协议生成对称密钥；生成对称密钥的过程为：a1、通信双方通过对通信过程中的消息取哈希的方式进行完整消息匹配或部分消息匹配，得到有效消息；a2、通信双方按照有效消息中的控制字段和内容字段从有效消息中分别进行数据抽样，得到控制矩阵u和内容矩阵v，将两个矩阵融合后得到共有信息矩阵；a3、利用共有信息矩阵是实对称矩阵，对其进行特征值求解和特征向量分解后，用特征向量对双方的共有信息进行一致性验证；a4、对共有信息矩阵的特征值素数化，得到因素基，对因素基按照因素基更新算法进行多次迭代后得到计算大素数g和p需要的素因子，随后计算出满足要求的大素数g和p；a5、最后通信双方根据从共有信息中得到的大素数进行dh密钥交换协议进行协商生成对称密钥，并用消息验证码确保消息密钥协商在通信过程中不被篡改，以实现对称密钥的生成；消息验证码根据共有信息矩阵取哈希的数据生成；还包括：在通信需求、计算能力和存储能力的约束下，选择网络中部分节点作为共有信息节点进行密钥生成；共有信息节点的选择过程包括以下步骤：b1、对于网络中的节点，计算基于共有信息生成密钥的存储和计算开销；b2、根据步骤b1的计算结果，得出相比于使用传统dh密钥交换协议的存储和计算开销加重率；b3、基于密钥的破解时间分析，得出相对于使用传统dh密钥交换协议，基于共有信息生成密钥的安全性提升率；b4、在节点通信频率、计算和存储能力的约束下，建立最大化系统安全性提升率和最小化系统开销加重率的优化模型；b5、通过遗传算法求解该优化模型得到共有信息节点的选择策略。2.根据权利要求1所述的一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，步骤a1具体为：记通信双方中其中一方为h1，另一方为h2；记h1积累的通信消息集合为s1，h2积累的通信消息集合为s2；若h2的消息缓存数量达到n
m
时，h2向h1发送完整消息匹配请求，h1收到完整消息匹配请求后，进行一次完整消息匹配；h1和h2分别对各自按时间先后顺序进行排列的消息集合s1和s2取哈希，当双方的哈希结果一致时，则完整消息匹配成功，h1向h2发送应答消息；否则完整消息匹配失败，进行部分消息匹配；部分消息匹配过程为：分别对s1和s2各自的子集进行匹配，若两个子集的哈希结果一致，则部分消息匹配成功；否则舍弃本轮通信周期中的消息，重新开始新一轮的通信周期；将完整消息匹配或部分消息匹配成功的消息作为有效消息。3.根据权利要求2所述的一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，在部分消息匹配过程中，s1和s2各自的子集采用步进函数进行取样得到；步
进函数表达式为：s(x)＝ai+11≤ai+1≤n
m
，a为大于或等于2且小于或等于n
m
的正整数，每一次采样a以大小为y的步长进行增加，i≥0，每一次采样时i以每次增加1的步长逐渐递增。4.根据权利要求3所述的一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，步骤a2具体过程为：记控制字段为内容字段为首先将含字段的字节按顺序拼接成一个字段，其中含有个字节，控制矩阵列数为c；将含字段的字节按顺序拼接成一个字段，其中含有个字节，控制矩阵列数为d；对中的数据进行抽样时，若则将个字节均作为抽样字节数据，其余部分补零；若时，则将中的内容分成c组，从每一组数据中进行抽样，每一组的数据量为为向下取整运算，通过抽样随机数r
c
和进行数据抽样得到u
y
；从而构造出n行c列的矩阵u：对中的数据进行抽样时，若则将个字节均作为抽样字节数据，其余部分补零；若时，则将中的内容分成d组，从每一组数据中进行抽样，每一组的数据量为通过抽样随机数r
d
和进行数据抽样得到v
y
；从而构造出n行d列的矩阵v，由u和v得到矩阵w，令矩阵w与其转置矩阵相乘，得到的方阵即为共有信息矩阵k：5.根据权利要求4所述的一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，步骤a3具体包括：对共有信息矩阵k进行特征值与特征向量求解，得到特征值组成的集λ和对应的特征向量构成的矩阵γ；若h1先向h2发送共有信息的一致性验证信息，h1先从矩阵γ中随机选取n个特征向量组成的验证矩阵1≤n≤c
′
，是h1从γ中随机选取的特征向量，并将剩下c-n个特征向量按对应特征值大小进行排序构成矩阵γ1，对γ1取哈希后得到hash(γ1)，η1和hash(γ1)构成共有信息的一致性验证信息；h2在收到h1发送的验证信息后，首先用γ对η1进行矩阵相乘验证，由γ与η1相乘可得到
矩阵ρ：由不同特征值对应的特征向量之间有相互正交的关系，则ρ中只有n个不为零的值，且每一列只有一个不为零的值；当ρ
i，j
≠0，i，j∈[1，c]，则有且h2通过ρ中不为零的值ρ
i，j
对η1进行验证，且得到组成η的n个特征向量；随后，h2得到由c-n个特征向量构成的矩阵γ1′
，对γ1′
取哈希得到hash(γ1′
)，对比hash(γ1)与hash(γ1′
)验证剩下的c-n个特征向量是否相同；满足以上条件则h2确定双方生成的共有信息相同。6.根据权利要求5所述的一种基于共有信息构建与节点选择的对称密钥生成与交换方法，其特征在于，步骤b4所述最大化系统安全性提升率和最小化系统开销加重率的优化模型表达式为：s.t.c1：l
i
(r)＝{0，1}c2：f
i，j
(r)≥f
minmin
其中，κ1和κ2分别表示安全性和开销在共有信息节点系统构建的重要程度，且κ1+κ2＝1，0＜κ1＜1，0＜κ2＜1；μ1和μ2分别表示存储开销和计算开销的重要程度，且μ1+μ2＝1，0＜μ1＜1，0＜μ2＜1；为存储开销加重率，为计算开销加重率，为安全性提升率；h
c
表示共有信息节点，f
i，j
(r)表示两节点h
i
和h
j
间构建共有信息的通信频率，f
min
表示两节点h
i
和h
j
间构建共有信息的最小通信频率，表示在第r个周期内节点h
i
为计算共有信息所花费的存储开销；两个节点之间的通信频率满足共有信息构建的最低频率要求时，ζ
i，j
(r)＝1，否则ζ
i，j
(r)＝0；表示在第r个周期内节点为计算共有信息所花费的存储开销，表示节点的存储能力；为在第个r周期内节点为计算共有信息所花费的计算开销，t0为设定的阈值。

技术总结
本发明公开一种基于共有信息构建与节点选择的对称密钥生成与交换方法，应用于通信网络安全领域，针对在通信网络中用DH密钥交换技术生成对称密钥时存在的中间人攻击问题，本发明的通信双方利用通信消息构建关于双方通信过程的共有信息，并以共有信息为基础进行密钥协商，安全且快速的生成对称密钥，然后选择网络中的部分节点作为共有信息节点进行共有信息构建和对称密钥协商，实现安全性和开销均衡的系统构建。的系统构建。的系统构建。


技术研发人员：韦云凯 王艺霖 冷甦鹏 杨鲲 刘强 朱佑存
受保护的技术使用者：电子科技大学长三角研究院（衢州）
技术研发日：2023.06.08
技术公布日：2023/8/6