RU2330382C1 - Preliminary key distribution circuit for cluster networks and its functioning method - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: EKSYD key distribution circuit for cluster networks includes the confidence centre comprising the processor and the memory and functioning at the stage of key blocks shaping and distribution. Each module of the cluster network also includes a processor, a memory and a receiver-transmitter. Also, according to the suggested key distribution circuit functioning method there is a number of operations including formation of the carrier incidence array of a predefined size, the incidence array of a predefined size, the EKSYD circuit incidence array as well as the key pool of the network and the key pool of each cluster.

EFFECT: enhancing the network security.

8 cl, 5 dwg

Description

The invention relates to devices for secret or secretive information transmission in modern communication networks, and more particularly to a key distribution system for secret communication.

The task of key distribution is the most important when solving a number of network security issues, namely, to ensure such services, security as confidentiality, authenticity and integrity of information during its transmission between network nodes. The main mechanism for providing the listed security services is cryptographic data conversion, which is carried out using secret keys.

In a symmetric cryptographic transformation, the same key is used in direct (for example, encryption) and inverse transformation (for example, decryption). In this case, cryptographic keys are distributed by the processor's executive circuit in such a way that each pair of network nodes has a common secret key (see, for example, US patent No. 5150411 [1]).

In another solution (for example, according to US patent No. 4876716 [2]), a description is given of a method for distributing keys generated by a random number generator between two systems over an insecure communication channel and calculating a common secret key by an executive processor circuit for transmitting information between these systems.

There is another approach to solving the key distribution problem, which consists in creating a specialized infrastructure, for example, public key infrastructure (see A.P. Alferov, A.Yu. Zubkov, A.S. Kuzmin, A.V. Cheremushkin. Fundamentals of cryptography. M .: "Helios Association of Russian Universities", 2002 [3]). However, the high cost of deploying such infrastructure and subsequent maintenance limits its use in modern ad hoc and mesh networks.

The problem to which the claimed invention is directed is to increase network security by applying a key pre-distribution scheme with a guaranteed high level of security during intercluster communication and an acceptable level of security during intra-cluster communication, as well as by developing a method for the effective functioning of such a scheme.

The problem was solved by developing an EKSYD key distribution scheme for servicing a network with a cluster organization, and this scheme uses a trusted center at the stage of formation and distribution of key blocks, which ensures guaranteed security during intercluster interaction and an acceptable level of security during intercluster interaction of nodes without participation a trusted center, and the trusted center has an executive processor circuit and memory, and each network node has an executive circuit him processor, memory and transceiver, while:

- the trusted center is configured to generate, by means of an executive circuit of the processor, a carrier incidence matrix of a given size in order to construct a resulting incidence matrix;

- the trusted center is configured to generate, by means of an executive circuit of the processor, nested incidence matrices of a given size in order to construct a resulting incidence matrix;

- the trusted center is configured to generate, by means of the processor executive circuit, the resulting incidence matrix by combining the aforementioned carrier and embedded matrices in accordance with the “nested” principle;

- the trusted center is configured to generate a key network pool using a pseudo-random number generator;

- the trusted center is configured to extract, through an executive circuit of the processor, the key pool of each cluster from said network key pool;

- the trusted center is configured to extract, by means of the processor circuit, the key block of a separate node from said key pool of the cluster into which this node is a member;

- the trusted center is configured to calculate, by means of an executive circuit of the processor and the pseudo-random number generator, a unique node identifier for each cluster;

- the trusted center is made with the possibility of secret transmission through the communication channels of the generated mentioned key blocks and their identifiers to the nodes of each cluster participating in intercluster and intracluster communication, which consists in exchanging data via open (insecure) communication channels, with one key block being transmitted to each node and identifier;

- the nodes are configured to calculate, by means of the processor circuit, a column of the resulting incidence matrix of an arbitrary node by its identifier;

- the nodes are configured to generate, by means of the processor circuit, a paired secret key based on the calculated column of the resulting incidence matrix of the receiver node and its own key block;

- the nodes are configured to encrypt / decrypt, as well as verifying the authenticity and integrity of the useful information using the aforementioned paired secret key by means of an executive circuit of the processor;

- nodes are configured to transmit / receive the generated message through a transceiver.

It is assumed that the main scope of the key distribution scheme described in this patent application is wireless mesh networks (see IF Akyildiz, X. Wang, W. Wang. Wireless mesh networks: a survey. Http: //www.sciencedirect. com / [4]). Each node in the mesh network functions as a router and is able to address relay incoming packets in a situation where the sending and receiving nodes are not nearest neighbors and, as a result, cannot establish a direct connection. Thus, the sender and receiver are connected through a chain of intermediate nodes. The term “multi-hop connection” is used in English literature to denote this type of interaction. Accordingly, the term “single-hop connection” is used to indicate the method of interaction of neighboring nodes when a direct connection is possible.

As a rule, the mesh network topology is not initially defined and is determined at the time of its deployment. Moreover, the topology can change over time - especially in cases where nodes have mobility. Mesh networks can be classified as self-organizing networks. Ideologically, mesh networks are close to ad hoc networks. The fundamental difference is the existence within the mesh network of a special control infrastructure consisting of nodes with advanced functionality (for example, equipped with several wireless interfaces and additional memory for data storage).

Clustering is a common way to organize modern communication networks. In some cases, the cluster approach is due to the binding of individual network segments to various stationary objects, such as rooms and buildings. The principle of clustering is in good agreement with the models for using mesh networks, which are described in detail in the documents of the IEEE 802.11s standard (see Residential and Office usage models, IEEE P802.11-04 / 662r16, Jan 2005 [5]). For example, a mesh network can be deployed on different floors of the building where the corporate office is located. Virtual clustering is also possible. The selected network segments can be mapped to virtual clusters. However, nodes from different clusters must be able to establish a secure mode of interaction in the same way as if they were in the same cluster.

The meshing models mentioned above suggest a security perimeter. For example, a corporate network cluster can be deployed in an office building on a separate floor. The room has several entrances and exits, each of which is equipped with an access control system.

The cluster approach can improve network security and reduce investment in security perimeter equipment. The cost of equipping several limited security perimeters for individual clusters can be significantly lower than the cost of equipping a network-wide security perimeter.

The attack may develop in the following scenario. Initially, an attacker penetrates the security perimeter. Then it captures the mesh node and leaves the security perimeter in the same or another way. The main goal of the attacker is to gain access to long-term secret keys that are stored in the local memory of the node. However, the attacker is not able to achieve the goal, being inside the perimeter - as a rule, the design of the node does not allow you to copy keys in a short period of time. Thus, in order to reduce the risk of detection, the attacker must ensure the operational implementation, capture and going beyond the security perimeter. Imagine a network in which, in order to compromise a private secret key of nodes located in two different clusters, it is necessary to capture a certain number of arbitrary nodes from these clusters. Moreover, the capture of nodes from one cluster does not allow to compromise the key. Obviously, a network with such properties has increased network security, since to compromise a key, it is necessary to penetrate the perimeters of each of the clusters.

With the cluster approach, it is useful to distinguish between intracluster and intercluster interaction of nodes. In intracluster interaction, two nodes from one cluster establish a secure interaction mode. In intercluster interaction, the sender and receiver are in different, not necessarily adjacent, clusters. A multi-hop connection is possible both in intercluster and intracluster interactions.

Consider possible attacks. Further, by "compromise" we mean the capture of a node by an attacker with the subsequent extraction of long-term secret keys from his local memory.

Guaranteed security means the following: the disclosure of long-term secret keys that are stored in the local memory of a node does not allow disclosing the paired secret key of the sender and recipient. Guaranteed security is ensured if the number of compromised nodes does not exceed a certain threshold value (compromise threshold), which is determined by the parameters of the current circuit.

1. Intracluster interaction. The purpose of the attack is to compromise the private secret key of the sender and recipient from one cluster S.

Possible attacks:

- Compromise one or more nodes DIRECTly from cluster S.

- To compromise one or more nodes from the cluster EXCELLENT from S.

- To compromise two groups of nodes: the first group belongs DIRECTLY to cluster S, and the second belongs to another cluster, DIFFERENT from S.

2. Intercluster interaction. The purpose of the attack is to compromise the private secret key of the sender and receiver from various S and T clusters.

Possible attacks:

- Compromise one or more nodes DIRECTly from cluster S or / and T.

- Compromise one or more nodes from the cluster EXCELLENT from S or / and T.

- To compromise two groups of nodes: the first group belongs DIRECTLY to clusters S or / and T, and the other belongs to other clusters DIFFERENT from S or / and T.

The claimed invention is based on a special "nesting" principle. According to this principle, the key pre-distribution scheme is built on the basis of another basic scheme, which is "embedded" in a special design. In the claimed invention, the KEDYS scheme described in RF patent application No. 2004103558 “Key distribution system and method of its operation” [6], as well as the ideas set forth in US patent application No. 20050177751 “Light-weight key distribution scheme in wireless network ”[7]. The choice of this scheme is significant, because its unique properties allow you to effectively implement a distributed key management method (see, for example, the method described by the author earlier in RF patent application No. 2006114900 [8]). The object of the application [8] is a distributed key management method based on a preliminary key distribution scheme, which includes the following operations:

- form a unique identifier of the mesh network node by the external registration center;

- write a unique identifier to the local memory of the mesh network node by an external registration center;

- form the incidence matrix of the KEDYS scheme by the trusted center;

- form the incidence matrix of the trivial scheme by the trusted center;

- generate long-term secret keys by a trusted center;

- write down by the trusted center the generated key block of the KEDYS scheme and the corresponding column of the incidence matrix into the local memory of the mesh network node;

- write the generated key block of the KEDYS scheme and the corresponding column of the incidence matrix into the local memory of the control node of the distributed key management center by the trusted center;

- write by the trusted center the generated key block of the trivial scheme and the broadcast key into the local memory of the control node of the distributed key management center;

- generate a trusted center starting value of the hash chain;

- calculate the final value of the hash chain by the trusted center;

- write the authenticator by the trusted center into the local memory of the mesh network node;

- write the trusted value of the hash chain to the local memory of the control node of the distributed key management center by the trusted center;

- check the identifier of the disconnected node against the database by the managing node of the distributed key management center and decide on disconnection;

- enter the identifier of the disconnected node into the database by the managing node of the distributed key management center;

- generate a session key by the managing node of the distributed key management center;

- calculate the incidence matrix of the KEDYS scheme by the control node of the distributed key management center;

- calculate the control node of the distributed key management center coverage;

- the session key is encrypted by the control node of the distributed key management center on paired keys of the trivial scheme or broadcast key;

- they send ciphertexts, which are the essence of the session key, encrypted on paired keys of a trivial scheme or broadcast key, to the managing node of the distributed key management center;

- accept the control node of the distributed key management center ciphertexts, which are the essence of the session key, encrypted on long-term keys from the coverage;

- the session key is encrypted by the control node of the distributed key management center on keys from the coverage that are included in its key block;

- form a broadcasting message for updating key blocks by a control node of a distributed key management center;

- send a broadcast message to the key node of the distributed key management center to update the key blocks;

- receive a broadcast message from the control node of the distributed key management center by the mesh network node;

- verify the authenticity of the broadcast message by the mesh network node;

- decrypt the broadcast message by the mesh-network node in order to obtain a session key;

- update the key block using a session key with a mesh network node;

- calculate by the sending node the column of the incidence matrix of the receiving node by its identifier;

- form a shared secret key by the sending node based on the incidence matrix column of the receiving node and the key block of the sending node;

- encrypt the sending information of the useful information on a shared secret key;

- form a sending node a message based on the received ciphertext;

- send the generated message to the address of the receiving node by the sending node;

- receive the generated message by the receiving node;

- calculate the receiver node column incidence matrix of the sending node by its identifier;

- form the recipient node a shared secret key based on the incidence matrix column of the sending node and the key block of the recipient node;

- decrypt the receiving node ciphertext from the message on a shared secret key.

The main advantages of the KEDYS circuit are as follows.

- The scheme is easily scalable and applicable in mesh networks with an arbitrary number of nodes.

- The computational complexity of building a circuit for a network with a given number of nodes is proportional to the size of the network. During the construction, binary logic operations are used, as well as arithmetic operations on integers of limited bit depth.

- The method of constructing a circuit is deterministic, i.e. construction time depends only on the number of nodes in the mesh network and the complexity of the method itself.

- The scheme belongs to the suboptimal class - the total number of long-term keys (hereinafter referred to as the key pool), as well as the number of keys stored in the local memory of an individual node (hereinafter referred to as the key unit), are much smaller than for other known schemes.

- The calculation of the pair key is carried out autonomously by the sender and receiver and does not require the execution of a special protocol.

- The scheme allows updating keys. The need to update the keys arises every time when some nodes of the mesh network are compromised. Updating is possible due to the existence of so-called coatings. Coverage - a subset of the keys that make up the key blocks of all nodes except for compromised ones. The coating is small in size. The coverage search procedure has a low computational complexity.

- The scheme allows distributed key management. A unique property of the scheme is the ability to select key blocks for the control center in such a way that they are able to form coalitions in order to search for coverage. The constructive method of acceptable labor input allows you to build a distributed key management center for a given number of nodes with the possibility of combining them in a coalition of a certain power.

However, it must be emphasized that instead of the KEDYS scheme, any other key pre-distribution scheme with similar properties can be selected.

For completeness, some further clarification is needed regarding key pre-distribution schemes (SPRCs) (see A. Chmora and A. Ourivski, “Lightweight Key Pre-distribution Scheme for Sensor Networks”, Tech. Rep., SAIT Communication & Network Lab, Security Team S / W SG CTL SRC, Jan 15, 2004. [9]).

In SPRC, a trusted center distributes classified information (key material) among a set of nodes U = {1, ..., N}. A piece of information u _i is transmitted to node i via a secret channel, for example, during network creation. The transferred key material allows us to establish a common secret key for a pair of nodes (the implementation of such an operation is described, for example, in the publications of R. Blom. An Optimal Class of Symmetric Key Generation Systems. - In: Advances in Cryptology - EUROCRYPT'84, LNCS 209, 1985, 335-338. [10]; C.J. Mitchell, FC Piper - Key Storage in Secure Networks. Discrete Applied Mathematics, vol. 21 (3), 1988, 215-228. [11]; L. Gong, DJ Wheeler .A Matrix Key Distribution Scheme. - Journal of Cryptology, vol. 2 (2), 1990, 51-59. [12]; M. Dyer, T. Fenner, A. Frieze, and A. Thomason - On Key Storage in Secure Networks. - Journal of Cryptology, vol. 8 (4), 1995, 189-199. [13]; C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung - Perfectly Secure Key Distribution for Dynamic Conferences. - In: Advances in Cryptology - CRYPTO'92, LNCS 740, 1993, 471-486. [14]; K. A. S. Quinn - Bounds for Key Distribution Patterns. - Journal of Cryptology, vol. 12 (4), 1999, 227-240. [15]). The use of pre-key distribution schemes in ad hoc networks, as well as sensor networks, is discussed in detail, for example, in the works of DR Stinson - On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption. - Designs, Codes and Cryptography, vol. 12 (3), 1997, 215-243. [16]; L. Eschenauer, V. Gligor - A Key Management Scheme for Distributed Sensor Networks. - Proceedings of the 9-th ACM conference CCS2002, 2002, 41-47. [17]; J. Lee, D. Stinson - On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks using Combinatorial Designs. - Technical rep. CACR 2005-40, Center for Applied Cryptographic Research, University of Waterloo, 2005. [18].

After the distribution of key material, the trusted center stops its work.

There are two simplest SPRK.

In the first scheme [10], the trusted center gives each node the same key k. Therefore, in fact, there is only one allowed group - the entire network, which includes all pairwise combinations of nodes, and the common key for each group is k.

This scheme has an obvious drawback: compromising at least one node compromises the entire network.

In the second scheme (trivial SPRK) [10] each pair of nodes has its own unique key. For a network of N nodes should trusted center to generate and distribute the N (N-1) / 2: N ^2/2 different keys - one for each pair. In this case, each node will receive N-1 keys. With increasing N, the amount of data that must be stored in each node increases and, starting with a certain value of N, becomes excessively large, which requires a significant amount of memory to store this data. On the other hand, such a scheme allows you to achieve the maximum level of security: to compromise the entire network, you need to capture (compromise) at least N-2 keys.

SPRK, which can be used in practical applications, are located between the two described schemes: by weakening security requirements, it is often possible to reduce memory requirements.

Let us give a general description of the construction based on the “nested” principle. The main task is to ensure guaranteed security of an individual cluster when nodes from other clusters are compromised.

For the convenience of presentation, we denote all nodes included in the cluster as a supernode. For simplicity, we assume that the secure interaction between the nodes of one cluster is ensured by a single secret key that all the nodes of this cluster have (it is obvious that the security of the cluster and the individual node are equivalent and the compromise of the node means the cluster is compromised; it will be shown below how to replace such a scheme with a scheme with a high threshold of compromise).

Correspondingly, secure interaction between super nodes is also possible if there is a private secret key between the sender and the recipient.

Any SPRK is a plan for distributing keys between nodes. The incidence binary matrix is a convenient way to represent such a plan. Each row of the matrix is associated with a long-term secret key, and each column is associated with a node. If the binary unit is located at the intersection of the i-th row and the 7th column, then the i-th key is included in the key block of the j-th node. This means that each column of the incidence matrix sets the plan for the formation of the key block of an individual node. The number of keys in the key pool is equal to the number of rows in the incidence matrix. Then the incidence matrix for the super node looks like the incidence matrix of the trivial SPRK, in addition, each super node has its own secret key (for intra-cluster interaction).

Consider an example for five clusters. The incidence matrix is as follows.

Obviously, the matrix F consists of two matrices - the identity matrix at the top and the matrix of the trivial SPRK at the bottom. Thus, the identity matrix determines the key distribution plan for intra-cluster interaction, and the trivial SPRC matrix determines the inter-cluster interaction. The interaction of the two supernodes means that a regular node from the first supernode acting as a sender interacts with a regular node from a second supernode acting as a recipient. We call the matrix F the carrier.

Recall that the incidence matrix of a trivial SPRK has strictly two units in each row, since each pair of nodes has a unique secret key.

Since each supernode is a set of nodes, it is not difficult to imagine the incidence matrix for supernets as a detailed incident structure in which each binary unit is replaced by a separate incidence matrix of lower dimension. We call such matrices nested. The number of columns of the embedded matrix is equal to the number of nodes in the corresponding cluster, and the number of rows is determined by the size of the key pool of the corresponding SPRK.

Then the matrix F from (1) is representable in the following form.

и

есть соответственно левая и правая части матрицы

Причем D_ST - это вложенная матрица инцидентности СПРК, которая обеспечивает взаимодействие узлов из кластеров S и Т. Матрицы 0 - вложенные нулевые матрицы подходящей размерности.In the resulting matrix G, the matrix C _S is the embedded incidence matrix of the SPRK for the Sth cluster. Matrices

and

there are respectively the left and right parts of the matrix

Moreover, D _ST is a nested incidence matrix of SPRK, which ensures the interaction of nodes from clusters S and T. Matrices 0 are nested zero matrices of suitable dimension.

The “nesting” principle allows constructing schemes for an arbitrary number of clusters without limiting the number of nodes in a separate cluster. Moreover, different clusters do not have to be equally powerful (have the same number of nodes).

Let us evaluate the security of a circuit built according to the “nested” principle. The security of intercluster and intracluster interaction depends on which SPRK matrices C _S correspond. and D _ST . If С _S is the incidence matrix of k _S - stable (with a compromise threshold k _S ) SPRK, then guaranteed security of interaction between nodes within the Sth cluster is provided, provided that no more than k _S nodes are compromised in this cluster. In addition, the compromise of an arbitrary number of nodes in other clusters is allowed. Similarly, if D _ST is the incidence matrix of w _ST - stable SPRK, then guaranteed security of interaction between nodes from clusters S and T is provided, provided that no more than w _ST nodes are totally compromised in these two clusters. It is also allowed to compromise an arbitrary number of nodes in other clusters.

Security during the compromise of nodes outside an individual cluster or a pair of clusters is ensured by the matrix structure (1). Whereas security inside the clusters is ensured by the structure of matrices С _S and D _ST .

We estimate the amount of memory that is needed to store the key block and pool. Suppose that there are C clusters of size n _i , i = 1, ..., C. In cluster S, k _S is deployed - a stable SPRK with a key block of b _S keys and a key pool of ν _S keys. For a pair of clusters S and T, w _ST is deployed - a stable SPRK with a key block of b _ST keys and a key pool of ν _ST keys. Note that b _ST = b _TS and ν _ST = ν _TS .

Then the key block of the node from cluster S contains

keys.

The cluster key pool, or the total number of different keys included in the key blocks of cluster S nodes, contains

keys.

The network key pool, or the total number of different keys in the circuit, contains

keys.

SPRK with good security and an acceptable amount of memory for storing keys can be built using the KEDYS scheme. In other words, the KEDYS scheme is embedded in a design constructed according to the “nested” principle.

This design is called EKSYD, from the Extended Key Distribution Scheme. The name is pronounced "[ik'si: d]", the English word "exceed" is similarly pronounced.

It is obvious that EKSYD is superior to KEDYS in terms of security, but payback is an increase in the number of keys in the key block and pool. Rate this growth. Suppose you are given a network of N nodes. Then the KEDYS schema key pool contains

keys

and the key block is B (N) = V (N) / 2 keys.

For simplicity, we assume that the network is divided into C clusters and all clusters are equally powerful. Security within a single cluster is provided by the KEDYS scheme. In addition, security during intercluster interaction is also provided by the corresponding KEDYS scheme. Then the key block contains

keys, the cluster key pool is V _S = 2B _S keys, and the network key pool

keys. It follows from the above formulas that the size of the key block increases linearly with the number of clusters, while the size of the key pool of the network increases quadratically, as in the trivial scheme.

Figure 1 shows the change in the growth in the number of keys in the key block with an increase in the number of clusters (along the X axis) for a network of N = 65536 nodes.

Analysis of the size of the key block shows that in the EKSYD scheme with C clusters with N / C nodes in each, the size of the key block is approximately C / 2 times larger than in the KEDYS scheme for a network of N nodes. In the EXYD scheme, the key pool of the network is approximately C times larger than the key block. However, the size of the key pool of the network is important only at the time of formation and distribution of key blocks, it is set once at the stage of network deployment. The size of the key pool of the cluster is more important, since it affects the size of the control structure within the cluster (as a result of applying the KEDYS scheme). But the size of the cluster key pool in the EKSYD scheme is two times larger than the size of the key block. A similar relation holds for the KEDYS circuit.

If we proceed from the criterion of the amount of memory for storing keys, then for networks with a small number of nodes, namely when

EXYD circuit loses trivial SPRK.

It should be noted that with an increase in the number of clusters from C = 1 to C = N, it is possible to build a SPRC family with the KEDYS scheme for C = 1 and the trivial SPRC for C = N. Thus, it can be argued that the EKSYD scheme is a generalization of the KEDYS scheme. Following the “nesting” principle, it is possible to construct a scheme with arbitrary parameters: from a 1-stable scheme with a minimum key block size at C = 1, to an (N-2) -stable scheme with a key block of N-1 keys at C = N.

The basis of the claimed invention is the task of increasing network security through the use of a preliminary key distribution scheme with a guaranteed high level of security during intercluster communication and an acceptable level of security during intracluster communication. In addition, guaranteed security is always ensured when nodes from clusters other than those to which the sender and the receiver belong are compromised.

The problem is solved by creating an EKSYD key distribution scheme for servicing a network with a cluster organization, while the scheme includes a trusted center that contains the processor executive circuit (hereinafter referred to as the “processor”) and a memory unit (hereinafter referred to as the “memory”) and operates on the stage of formation and distribution of key blocks, and each network node with a cluster organization also contains an executive processor circuit (processor), a memory block (memory) and a transceiver, while:

- the trusted center is configured to form, by means of a processor, an incidence matrix of a given size to construct the resulting incidence matrix;

- the trusted center is configured to generate, by means of a processor, nested incidence matrices of a given size to construct the resulting incidence matrix;

- the trusted center is configured to generate, by means of a processor, the resulting incidence matrix by combining the aforementioned carrier and embedded matrices in accordance with the “nested” principle;

- the trusted center is configured to generate a key network pool using a pseudo-random number generator;

- the trusted center is configured to allocate, through the processor, the key pool of each cluster from said network key pool;

- the trusted center is configured to extract, by the processor, the key block of a separate node from said key pool of the cluster into which this node is a member;

- the trusted center is configured to calculate, by the processor and the pseudo-random number generator, a unique node identifier for each cluster;

- the trusted center is configured to secretly transmit, through communication channels, formed key blocks and their identifiers to the nodes of each cluster participating in intercluster and intracluster communication, which consists in exchanging data via open (i.e., unprotected) communication channels, with each node transmit one key block and identifier;

- the nodes are configured to calculate, by the processor, a column of the resulting incidence matrix of an arbitrary node by its identifier;

- the nodes are configured to generate, by means of a processor, a paired secret key based on the calculated column of the resulting incidence matrix of the recipient node and its own key block;

- nodes are made with the possibility of encryption / decryption, as well as verification of the authenticity and integrity of useful information using the aforementioned paired secret key through the processor;

- nodes are configured to transmit / receive the generated message through a transceiver.

Thus, the trusted center is responsible for the formation and distribution of key blocks at the stage of network deployment. The interaction of nodes is carried out without the participation of a trusted center.

Preliminarily perform:

- analysis of the security of intracluster and intercluster interaction when the network is divided into clusters and the selection of the optimal compromise threshold for each of the clusters;

- selection of the parameters of the EKSYD scheme taking into account the number of nodes in the network, the number of clusters, the power of each cluster, a given compromise threshold for each cluster, as well as the presence of a control structure within the cluster;

- assessment of the amount of local memory of the node for storing the key block, the amount of memory of the trusted center for storing the key pool of the network.

For the operation of the EKSYD scheme, it is necessary that the trusted center be configured to create the resulting incidence matrix.

For the operation of the EKSYD scheme, it is essential that the trusted center be configured to create a carrier matrix of a given size.

For the operation of the EKSYD scheme, it is essential that the trusted center be configured to create nested matrices of a given size.

For the operation of the EKSYD scheme, it is essential that the trusted center be configured to secretly transmit key blocks to the nodes of each cluster at the stage of network deployment.

For the operation of the EKSYD scheme, it is essential that the nodes are configured to generate a paired secret key based on the calculated column of the resulting incidence matrix of the receiving node and its own key block of the sending node.

The problem is also solved by creating a method of functioning of the EKSYD circuit, consisting of the following operations:

- form, by means of the processor of the trusted center, the incidence matrix of a given size;

- form, by means of the processor of the trusted center, nested incidence matrices of a given size;

- form, by means of the processor of the trusted center, the resulting incidence matrix of the EKSYD scheme by combining the aforementioned carrier and embedded matrices in accordance with the “nested” principle;

- form, by means of a pseudo-random number generator of the trusted center, the key pool of the network;

- allocate, through the processor of the trusted center, the key pool of each cluster from the said key pool of the network;

- isolate, by means of the processor of the trusted center, the key block of a separate node from the said key pool of the cluster into which this node is a member;

- calculate, by the processor and the pseudo-random number generator of the trusted center, a unique node identifier for each cluster;

- secretly transmit, through the communication channels of the trusted center, the mentioned key blocks and their identifiers to the nodes of each cluster;

- calculate, by the node processor, a column of the resulting incidence matrix of an arbitrary node by its identifier;

- form, by means of the node processor, a paired secret key based on said calculated column of the resulting incidence matrix of the receiving node and the key block of the sending node;

- encrypt / decrypt, and also verify the authenticity and integrity of the useful information on the aforementioned secret key pair, through the node processor;

- transmit / receive the generated message by the transceiver node.

To implement the method of functioning of the EKSYD scheme, it is important that the carrier matrix for the network of N nodes and C clusters is formed by the processor of the trusted center, as follows:

- form, by means of the processor of the trusted center, a unit matrix in which the number of rows and columns is equal to the number of clusters C;

и в каждой строке имеется ровно по две двоичных единицы, а каждом столбце ровно по (N-1) двоичных единиц;- form, through the processor of the trusted center, the incidence matrix of the trivial SPRC, in which the number of columns is equal to the number of clusters C, and the number of rows is

and each row has exactly two binary units, and each column has exactly (N-1) binary units;

- form, by means of the processor of the trusted center, the supporting matrix by combining the aforementioned unit matrix and the incidence matrix of the trivial SPRK.

To implement the method of functioning of the EKSYD circuit, it is essential that the embedded matrices of a given size are formed by the processor of the trusted center in accordance with the design of the KEDYS circuit.

To implement the way the EKSYD scheme operates, it is essential that the column number be associated with a unique node identifier during the network deployment phase.

For the operation of the EKSYD scheme, it is essential that the pair secret key is generated by the node processor as follows:

- the node processor computes the intersection of the key blocks of the sending and receiving nodes (shared keys) by applying the AND operation (logical AND) to the columns of the resulting incidence matrix for the sending and receiving nodes - binary units at the corresponding positions of the result column indicate keys from the intersection;

- calculate the pair secret key by the processor of the sending node by applying a unidirectional hash function to the said set of keys from the intersection (common for the key blocks of the sending node and the receiving node);

- calculate the pair secret key by the processor of the recipient node by applying a one-way hash function to the said set of keys from the intersection (common to the key blocks of the sending node and the receiving node).

To implement the method of functioning of the EKSYD scheme, it is essential that the use of a unidirectional hash function is reduced to the following operations:

- concatenate the keys from the intersection, which are common to two different key blocks belonging respectively to the sending and receiving nodes;

- establish the concatenation order (i.e., the sequence of the keys), which must match both the sender and the recipient;

- calculate the values of the unidirectional hash function from the concatenation of these keys.

Thus, the technical result of the claimed invention is the creation of an EKSYD scheme that scales for a network with an arbitrary number of nodes and clusters of arbitrary power, does not require a large amount of memory for storing a key block, and guarantees low computational complexity, both when constructing the resulting incidence matrix, and when calculating a pair key during node interaction, provides guaranteed security during intercluster interaction and an acceptable level of security for internal utcluster interaction. In addition, guaranteed security is always ensured when nodes from clusters other than those to which the sender and the receiver belong are compromised.

To provide a deeper understanding of the operation of the EKSYD circuit, the following is a detailed description of its operation and drawings.

Figure 1 is a graph of changes in the growth in the number of keys in a key block with an increase in the number of clusters for a network of N = 65536 nodes (according to the EKSYD and KEDYS scheme).

Figure 2 is a graph of the dependence of the growth in the number of keys in the key block (in thousand) with the increase in the number of clusters for a network of N = 65536 nodes (according to the EKSYD scheme and the trivial SPRK).

Figure 3 is a block diagram of an EKSYD SPRK according to the invention.

4 is a sequence diagram of a method for forming an EKSYD SPRK according to the invention.

5 is a sequence diagram of a method for the interaction of nodes in an EKSYD SPRK according to the invention.

The EKSYD scheme is intended for deployment in a network with a cluster structure and consists of a trusted center 2, communication channels 3. In this case, the trusted center 2 contains a processor 4, a memory 5 and a generator 6 of pseudo-random (or random) numbers, and each network node 7 contains a processor 8, a memory 9, and a transceiver 10 (see FIG. 3).

At the stage of network deployment (see Fig. 4), the incidence incidence matrix of a given size (step 1) is formed by the processor 4 of the trusted center 2 (step 1), then the incidence matrices of the specified size are formed by the processor of the trusted center 2 (step 2), after which the processor 4 trusted center 2 form the resulting incidence matrix based on the matrices obtained in steps 1 and 2 (step 3). Generate a key pool of the network by means of a generator 6 of pseudorandom numbers of the trusted center 2 (step 4). Using the processor 4 of the trusted center 2, the key pool of each cluster is allocated from the key pool of the network (step 5). Using the processor 4 of the trusted center 2, the key block of an individual node is isolated from the key pool of the cluster into which this node is a member (step 6). A unique identifier for each node of each cluster is calculated by means of processor 4 and generator 6 of pseudo random numbers of the trusted center (step 7). Secretly transmit to the nodes of each cluster through the communication channels 3 of the trusted center 2 key blocks and identifiers (step 8).

During intercluster and intracluster interaction (see Figure 5), a column of the resulting incidence matrix of an arbitrary node selected as the receiving node is calculated by processor 8 of node 7 (step 1). A pair secret key is generated by the processor 8 of the node 7 based on the column of the resulting incidence matrix of the receiver node and the key block of the sending node, which is stored in memory 9, calculated in step 1 (step 2). The data is encrypted / decrypted, and its authenticity and integrity are checked with the help of a secret pair key using processor 8 of node 7 (step 3). The generated message is transmitted / received by the transceiver 10 (step 4).

Next, we consider the construction of the claimed EKSYD scheme using a specific example.

узлам.For an example we will select a network with five clusters and 25 nodes. We will proceed from the assumption that all clusters have different power. Namely, n ₁ = 3, n ₂ = 4, n ₃ = 5, n ₄ = 6, n ₅ = 7 and

nodes.

We write the matrix G explicitly.

At the beginning, matrices C _{i are formed} . Using the incidence matrix of the KEDYS scheme for four nodes [2], we obtain the matrices

.

.

Moreover, the matrix C _{1 is} obtained from C _{2 by} discarding the last two columns, and then the rows containing only one unit or not containing a single unit.

Using the incidence matrix of the KEDYS scheme for eight nodes

construct the next set of matrices

Moreover, the matrix C _{3 is} constructed from the matrix C by discarding the last three columns, and then the rows containing only one unit, or not containing a single unit. Matrices C ₄ and C _{5 are} constructed in a similar way.

We construct matrices D _ST . The matrix D ₁₂ is the first seven columns of the matrix C and D ₁₃ = C. Then

To construct the remaining matrices, we use the incidence matrix of the KEDYS scheme for sixteen nodes

Matrices D ₁₄ and D ₂₃ are the first nine columns of D, D ₁₅ , and D ₂₄ are the first ten columns of D, D ₂₅ , and D ₃₄ are the first eleven columns of D, and the matrix D ₃₅ is the first twelve columns of D. As a result, we obtain

In the interaction of nodes from the “four” and “five” clusters, the same group key is used that is common to all nodes (this assumption is for illustrative purposes only). Then

.

.

The full incidence matrix is presented below (6). The following notation is used: • = 1 and o = 0.

We emphasize once again that this example is given to illustrate the “nested” principle of construction and the properties of the EKSYD circuit. The size of the key block varies depending on the number of nodes in the cluster and its security (determined by the SPRK used). The minimum key block size is thirty-four keys (nodes from the "five" cluster), the maximum key block consists of thirty-nine keys (nodes from the "three" cluster). In a trivial SPRK with similar parameters, each node would have a key block of twenty-four keys. Thus, the statement is true that for networks with a small number of nodes, the EKSYD scheme loses a trivial SPRK by the size of the key block. However, the situation is changing for networks with a large number of nodes, as follows from the figure below, which shows the dependence of the growth in the number of keys in the key block (in thousands) with the increase in the number of clusters (along the X axis) for a network of N = 65536 nodes ( see Figure 2).

Although the above embodiments of the invention have been set forth for purposes of illustration, it is clear to those skilled in the art that various modifications, additions and substitutions are possible without departing from the scope and meaning of the present invention disclosed in the description, drawings and claims.

Claims (12)

1. The EKSYD key distribution scheme for servicing a network with a cluster organization, including a trusted center that contains a processor and memory, and functioning at the stage of formation and distribution of key blocks, each network node with a cluster organization also contains a processor, memory and transceiver, wherein: the trusted center is configured to generate, by a processor, a carrier incidence matrix of a given size to construct the resulting incidence matrix; the trusted center is configured to generate, by the processor, the nested incidence matrices of a given size to construct the resulting incidence matrix; the trusted center is configured to form a resultant incidence matrix by the processor by combining the aforementioned carrier and nested matrices in accordance with the “nested” principle; the trusted center is configured to generate a key network pool using a pseudo random number generator; the trusted center is configured to extract, by the processor, the key pool of each cluster from said network key pool; the trusted center is configured to extract, by the processor, the key block of a separate node from said key pool of the cluster into which this node is a member; the trusted center is configured to calculate, by a processor and a pseudo-random number generator, a unique node identifier for each cluster; the trusted center is configured to secretly transmit through the communication channels the generated key blocks and their identifiers to the nodes of each cluster participating in intercluster and intracluster communication, which consists in exchanging data via open communication channels, with one key block and identifier being transmitted to each node; the nodes are configured to calculate, by the processor, a column of the resulting incidence matrix of an arbitrary node by its identifier; the nodes are configured to generate, by the processor, a paired secret key based on the calculated column of the resulting incidence matrix of the recipient node and its own key block; the nodes are configured to encrypt / decrypt, as well as verify the authenticity and integrity of useful information using the aforementioned pair of secret keys by means of a processor; the nodes are configured to transmit / receive the generated message through a transceiver. 2. The key distribution scheme according to claim 1, characterized in that the trusted center is configured to create a resulting incidence matrix. 3. The key distribution scheme according to claim 1, characterized in that the trusted center is configured to create a carrier matrix of a given size. 4. The key distribution scheme according to claim 1, characterized in that the trusted center is configured to create nested matrices of a given size. 5. The key distribution scheme according to claim 1, characterized in that the nodes are configured to generate a paired secret key based on the calculated column of the resulting incidence matrix of the receiving node and its own key block of the sending node. 6. The way the key distribution scheme operates, consisting of the following operations: form by the processor of the trusted center the incidence matrix of a given size; form by the processor of the trusted center nested incidence matrices of a given size; form by the processor of the trusted center the resulting incidence matrix of the EKSYD scheme by combining the aforementioned carrier and embedded matrices in accordance with the “nested” principle; form the key pool of the network by means of a pseudo-random number generator of the trusted center; allocating, by a trusted center processor, a key pool of each cluster from said network key pool; by means of a trusted center processor, allocating a key block of an individual node from said key pool of the cluster into which this node is a member; calculating a unique node identifier for each cluster by means of a processor and a pseudo-random number generator of a trusted center; secretly transmit via the communication channels of the trusted center the mentioned key blocks and their identifiers to the nodes of each cluster; calculating by the node processor the column of the resulting incidence matrix of an arbitrary node by its identifier; forms a pair secret key by means of the node processor based on said calculated column of the resulting incidence matrix of the receiving node and the key block of the sending node; encrypt / decrypt, and also verify the authenticity and integrity of the useful information on said pair of secret keys, through the node processor; transmit / receive the generated message by the transceiver node. 7. The method according to claim 6, characterized in that they form a carrier matrix for the network of N nodes and C clusters as follows: form a unit matrix in which the number of rows and columns is equal to the number of clusters C; form the incidence matrix of the trivial SPRK (pre-distribution key scheme), in which the number of columns is equal to the number of clusters C and the number of rows is

and each row has exactly two binary units, and each column has exactly (N-1) binary units; form the carrier matrix by combining the aforementioned unit matrix and the incidence matrix of the trivial SPRK. 8. The method according to claim 6, characterized in that the embedded matrix is formed in accordance with the design of the KEDYS circuit. 9. The method according to claim 6, characterized in that the column number is associated with a unique identifier of the node at the stage of network deployment. 10. The method according to claim 6, characterized in that the paired secret key is calculated as follows: calculate the intersection of the key blocks of the sending node and the receiving node (shared keys) by applying the AND operation (logical AND) to the columns of the resulting incidence matrix for the sending node and the receiving node - binary units at the corresponding positions of the result column indicate the keys from the intersection ; the sender and receiver calculate the pair secret key by applying a one-way hash function to the said set of keys from the intersection common to the key blocks of the sending node and the receiving node. 11. The method according to claim 10, characterized in that a unidirectional hash function is used as follows: perform concatenation of keys from the intersection, which are common to two different key blocks belonging respectively to the sending and receiving nodes; establish the concatenation order, which must match both the sender and the recipient; compute the value of the one-way hash function from concatenating these keys. 12. The method according to claim 6, characterized in that the key blocks are transmitted to network nodes via a secret channel, and exactly one key block is transmitted to each node.

Images