RU2570700C1 - Method of designing system for "own-alien" recognition based on zero-knowledge protocol - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: disclosed method for "own-alien" recognition employs a protocol wherein a respondent first calculates its true and noisy status and then, after receiving from an interrogator question in the form of a random number, determines three answers to said question, and then transmits all calculated values to the interrogator which then verifies the legitimacy of the respondent by performing corresponding calculations and comparing results thereof with the noisy status of the respondent.

EFFECT: high mimic resistance owing to use of an authentication protocol based on zero-knowledge proof.

2 cl, 2 dwg

Description

The invention relates to radio engineering and can be used to determine the nationality of mobile objects and their identification.

Traditionally, the task of identifying "friend or foe" consists of two subtasks. The first task is to select an object and send it a “password”. The second task is based on operations related to obtaining “feedback” from the selected object. For single objects, the first subtask is solved quite trivially, by means of a radio query, laser guidance, etc. The second one is usually solved using radio communications and cipher codes.

In the source [1] (RF Patent No. 2386144 “Friend or Foe” recognition method; IPC G01S 13/78; Alexander Petrovich Varin (RU), Sergey Ivanovich Grigoryev (RU), Nikolai Vasilievich Kalinin (RU), Vladimir Nikolaevich Panov (RU ), Radko Nikolai Mikhailovich (RU). Publication date: 04/10/2010, bull. No. 10.) As a way to protect the transmitted data from unauthorized access (unauthorized access) and provide imitation protection, a specially encoded request signal and response signal are used. The principle of radio communication provides the interaction of means of identifying and identifiable objects using encryption and decryption devices. Thus, the imitability of the system is achieved.

There is a known method of recognition "friend or foe", implemented in the recognition system [2] (IPC G01S13. RF Patent No. 2189610. Moiseev V.F., Sivov V.A .; Publication date 09/20/2002). This system is characterized by insufficient imitation resistance. To ensure this property, an encryption block is used that has m inputs and m outputs. It is a switching device of m inputs to m outputs. The encryption block performs the operation of the permutation of the bits of the input block.

In this case, the value of the bits does not change, but only the order of their sequence in the output vector changes.

The imitostability of the friend-or-foe definition system can be enhanced by the method of constructing a system based on a protocol with zero disclosure, which are used in authentication protocols. Authentication Protocol - a cryptographic protocol during which one party verifies the identity of the other party involved in the protocol.

A special place among such protocols is occupied by authentication protocols of the "request-response" type, in which one side (applicant) proves its identity to the other side (verifier) by demonstrating knowledge of a certain secret. The applicant must respond to a request that varies in time, and the answer must depend on the value of his secret and on the request [3, p. 42-43] (Zapechnikov SV Cryptographic protocols and their application in financial and commercial activities. - M: Hot line-Telecom, 2007).

To ensure a high degree of imitability, a method for constructing an authentication system based on the use of an authentication protocol using evidence with zero disclosure is proposed.

In [3, p. 20-21] the most well-known computationally complex problems of number theory, on which the protocol for protecting data against unauthorized access is based, are presented. The proposed authentication algorithm, based on a zero-knowledge proof, relates to the Diffie-Hellman Recognition Problem (DDHP). It is known that the stability of Diffie-Hellman problems is based on the complexity of computing the discrete logarithm. Currently, this discrete logarithmization problem can be solved in a minimal amount of time only with the help of a subexponential algorithm, which is much longer than the enumeration time of possible commutation performed by the encryption block given in the source [2].

The main objective of the invention is to increase the imitability of a friend-or-foe determination system through the use of a request-response authentication protocol based on zero-knowledge proof.

The technical result achieved in the implementation of the claimed invention is to increase the resistance by using an authentication protocol based on evidence with zero disclosure.

To achieve a technical result in the method of constructing a recognition system "friend or foe" on the basis of a protocol with zero disclosure, it is proposed to perform the following data exchange algorithm.

First step. The numbers U, S, T are entered into the memory of the computing device of the responder. In this case, the number U acts as a long-term secret key. The numbers S and T are the basic basis by which the session keys S (i) and T (i) are calculated.

To calculate the session keys S (i) and T (i), the invention proposes to use the pseudo-random function (PSF) given in [4] (Kalmykov I.A., Dagaev O.I., Naumenko D.O., Weltz O .V. Systematic approach to the use of pseudorandom functions in information protection systems // Bulletin of the Southern Federal University. Technical Sciences, Taganrog: TRTU, 2013 No. 12 (149), pp. 228-234). This PSF, which takes the input sequence (x ₁ , ..., x _n ) and the key (g, s ₁ , ..., s _n ), ensures the equality

where g is the primitive element of the multiplicative group.

At the same time, the simulated resistance of this PSF is based on the proof of the complexity of solving the λ-DDH problem. Then we have

where q is the number generating the multiplicative group; g is the primitive element of this group; i is the number of the ongoing session.

Second phase. Using the obtained data U, S (i) and T (i), the computing device of the responder calculates the true status of the object according to

The calculated true status value is recorded in the memory block of the responder.

The third stage. Then, in the computing device, using the obtained data U, S (i) and T (i), they are noisy

where ΔU, ΔS, ΔT are the noise values of U, S (i) and T (i), respectively.

After that, the computing device of the responder calculates the noisy status according to

The calculated value of the noisy status is recorded in the memory unit of the responder.

The fourth stage. When an object appears in the visibility range, the interrogator generates a “query number” d and sends it to the responder.

The fifth stage. Having received the "query number" d, the responder calculates the responses

where φ (q) is the Euler function of q.

The sixth stage. After completing the calculations, the responder transmits to the interrogator a signal that contains:

- calculated true status C (i);

- the calculated noisy status C * (i);

- answers to the question posed r ₁ , r ₂ , r ₃ .

Seventh stage. The interrogator, having received this signal, calculates the result according to

If the calculated value Y (i) matches the value of the noisy status of the object, i.e. Y (i) = С * (i), then a decision is made that his status is “his”.

If the calculated value of Y (i) does not match the value of the noisy status of the object, i.e. Y (i) ≠ С * (i), then a decision is made that the status of the object is “alien”.

The proposed method for constructing a friend-or-foe identification system based on a protocol with zero disclosure is carried out using a friend-or-foe identification system.

The structure of the friend or foe identification system is shown in FIG. 1. and FIG. 2. In FIG. 1 shows a part of an identification system that is located on a transponder. The system includes the first memory unit 1, the first switching unit 2, the second memory unit 3, the third memory unit 4, the fourth memory unit 5, the first adder 6 modulo q, the second adder 7 modulo q, the third adder 8 modulo q, first computing device 9, second switching unit 10, transponder input 11, first register 12, second computing device 13, third computing device 14, third computing device 15, second register 16, third register 17, fourth register 18, fifth register 19, sixth register 20, control input 21.

The output of the first memory unit 1 is connected to the input of the first switching unit 2. The first, second, and third outputs of the first switching unit 2 are connected, respectively, to the first, second, and third inputs of the first computing device 9. The fourth output of the first switching unit 2 is connected to the first input of the first the adder 6 modulo q, to the second input of which the output of the second memory unit 3 is connected. The fifth output of the first switching unit 2 is connected to the first input of the second adder 7 modulo q, the second input of which is connected to the output of the third memory lock 4. The sixth output of the first switching unit 2 is connected to the first input of the third adder 8 modulo q, the second input of which is connected to the output of the fourth memory unit 5. The output of the first adder 6 modulo q is connected to the first input of the first computing device 9, and to the second input of the second computing device 13, the first input of which is connected to the output of the first register 12. The output of the second adder 7 modulo q is connected to the second input of the first computing device 9, as well as to the second input of the third calculation device 14, the first input of which is connected to the output of the first register 12. The output of the third adder 8 modulo q is connected to the third input of the first computing device 9, as well as to the second input of the fourth computing device 15, the first input of which is connected to the output of the first register 12. The output of the first computing device 9 is connected to the input of the second switching unit 10, the first output of which is connected to the input of the second register 16, the second output is connected to the input of the third register 17.

The input of the first register 12 is connected to the input of the responder 11, which receives the "question d" from the interrogator. The output of the second computing device 13 is connected to the input of the fourth register 18. The output of the third computing device 14 is connected to the input of the fifth register 19. The output of the fourth computing device 15 is connected to the input of the sixth register 20. The control inputs of the first and second switching units 2 and 10 are connected to the control input 21. The outputs of the registers 16-20 are the output of the identification system "friend or foe", located on the defendant. From the outputs of the registers 16-20, the calculated values of the true status C (i), the noisy status C * (i), the answers to the question posed r ₁ , r ₂ , r ₃ are received at the input of the transmitter, which transmits them to the receiver of the interrogator.

In FIG. 2 shows a part of the identification system, which is located on the interrogator. The structure of this part of the system includes the fifth memory block 22, the output of the interrogator 23, the input of the interrogator 24, the seventh register 25, the fifth computing device 26, the output of the identification system 27.

The fifth memory block 22, designed to store questions d, is connected to the output of the interrogator 23. From this output 23, question d is transmitted to the receiver of the transponder via the transmitter located on the interrogator, the output of which goes to the input 11 of the identification system located on the transponder.

The input of the interrogator 24, through which the calculated values of the true status C (i), the noisy status C * (i), the answers to the question r ₁ and r ₂ , r ₃ received from the responder are transmitted, is connected to the input of the seventh register 25, the output of which connected to the input of the fifth computing device 26, the output of which is connected to the output of the identification system 27.

The recognition system "friend or foe" works as follows. The value of U, S, and T is written to the first memory block 1. The signal y = 1 is received at the control inputs of the first and second switching blocks 2 and 10 from the control input 21. As a result of this, the values of U, S, and T are supplied respectively to the first, second, and third outputs of the first switching unit 2, and then to the first, second, and third inputs of the first computing device 9, which implements the calculation of the true status C (i) according to expression (4 ) The calculated value of the true status C (i) is fed to the input of the second switching unit 10, which, under the action of the control unit y = 1, transfers it to the second register 16. To calculate the noisy value C * (i), to the control inputs of the first and second switching units 2 and 10 from input 21 receives a control signal y = 0. As a result of this, the values of U, S, and T are supplied to the fourth, fifth, and sixth outputs of the first switching unit 2, and then to the first inputs of the first, second, and third adders 6-8 modulo q, respectively. The second inputs of these adders modulo q from the outputs of the second, third, fourth memory blocks 3, 4, 5 receive the values ΔU, ΔS and ΔT, respectively. Adders 6-8 modulo q implement the calculation of the noisy values of U *, S * and T * according to the expressions (5-7). The noisy values of U *, S *, and T * arrive at the first, second, and third inputs of the first computing device 9, respectively, which implements expression (8). The calculated value of the noisy status C * (i) is fed to the input of the second switching unit 10, which, under the action of the control signal y = 0, transfers this value to the second output of the block, and then to the input of the third register 17.

When an object appears in the visibility range, the interrogator selects the “query number” d using the fifth memory block 22. Then this number is output to the interrogator 23, and then, using the transmitter located on the interrogator, it is transmitted to the responder’s receiver, the output of which is input 11 identification systems located on the defendant.

When the question d is received at the input of the transponder 11 of the system, this number is written into the first register 12, and from its output to the first inputs of the second, third and fourth computing devices 13, 14, 15. A noisy value U *, S is received at the second inputs of these devices * and T * from the outputs of the first, second and third adders 6, 7, 8 modulo q, respectively. These computing devices implement expressions (9-11). The calculated values of r ₁ , r ₂ , r ₃ from the outputs of the second, third and fourth computing devices 13, 14, 15 are fed to the inputs of the fourth, fifth and sixth registers 18, 19, 20, respectively.

From the outputs of the registers 16-20, the calculated values of the true status C (i), the noisy status C * (i), the answers to the question posed r ₁ , r ₂ , r ₃ are received at the input of the transmitter, which transmits them to the receiver of the interrogator.

The received data is fed to the input of the interrogator 24, and then recorded in the seventh register 25. From the output of the seventh register, the values of the true status C (i), the noisy status C * (i), the answers to the question r ₁ , r ₂ , r ₃ are submitted to the input of the fifth computing device 26, which implements the calculation of equality (12). If the calculated value Y (i) matches the value of the noisy status of the object, i.e. Y (i) = С * (i), then the output of the identification system 27 receives a signal “1”, which corresponds to the status “own”.

If the calculated value of Y (i) does not match the value of the noisy status of the object, i.e. Y (i) ≠ С * (i), then the output of the identification system 27 receives a signal “0”, which corresponds to the status of “alien”.

Consider an example protocol implementation. Let q = 11 as the number. For this multiplicative group, choose g = 2. As elements of the secret, choose U = 3, S = 4, T = 6. Then according to (4) we obtain that the value of the true status

C = q ³ q ⁴ q ⁶ modq = 2 ¹³ mod11 = 2 ³ mod11 = 8

This value is recorded in the first register 16. When the control signal y = 0 arrives, “U, S, T values are noisy”. Let ΔU = 2, ΔS = 5, ΔТ = 4 be taken from the outputs of memory blocks 3-6. Then the outputs of the adders 6-8 modulo q remove the values

The resulting noisy U *, S * and T * are fed to the inputs of the first computing device 9, which implements (8). Then

This value C * comes through the second switching unit 10, and then is recorded in the second register 17.

Let the question d = 6 be removed from the fifth memory block 22 of the identification system, which is located on the interrogator. This number from the output of the interrogator 23 is supplied to the transmitter of the interrogator and transmitted to the object. This number is received by the receiver of the responder and fed to input 11 and recorded in the first register 12. Computing devices 13, 14, 15 determine the "answer" to the question d = 6

The calculated values are recorded respectively in registers 18-20. Then, the calculated values (C, C *, r ₁ , r ₂ , r ₃ ,) from the registers 16-20 arrive at the transmitter of the responder and are transmitted to the interrogator.

The interrogator receiver receives these values and transfers them to input 24. Then these values are recorded in register 25 and fed to the input of the fifth computing device 26. The latter implements expression (12). Then the value is obtained

Since the noisy value C * coincided with the calculated value Y, the output of the identification system 27 receives a signal “1”, which corresponds to the status “own”.

Claims (2)

1. A method of constructing a friend-or-foe identification system based on a zero-disclosure protocol, characterized in that the authentication protocol, based on a zero-disclosure proof, uses the true status values C (i) calculated by the respondent
C (i) = g ^U g ^{S (i)} g ^{T (i)} modq,
where U is the long-term secret key;
S and T - the basis of session keys

and

q is the number generating the multiplicative group;
g is the primitive element of this group;
i - number of the ongoing session calculated, as well as the value of the noisy status

where U * (i) = U + ΔUmodq;
S * (i) = S (i) + ΔSmodq;
T * (1) = T (i) + ΔTmodq;
ΔU, ΔS, ΔT are the noisy values of the values of U, S (i) and T (i), respectively, while receiving the "request number" d from the interrogator, in the protocol the responder calculates the answers to the question d
r ₁ = U * -dUmodφ (q),
r ₂ = S (i) * - dS (i) modφ (q),
r ₃ = T (i) * - dT (i) modφ (q),
where φ (q) is the Euler function of q, according to the protocol, the responder transmits to the interrogator the calculated values of the true status C (i), the noisy status C * (i), the responses r ₁ , r ₂ , r ₃ , after which the interrogator uses these values verifies their correctness by applying the expression

if the calculated value Y (i) coincides with the value of the noisy status of the object, i.e. Y (i) = С * (i), then the interrogator makes a decision that the status of the defendant is “his”, otherwise, a decision is made that the status is “alien”. 2. The friend-or-foe recognition system, built on the basis of a zero-disclosure protocol, consists of two parts located on the responder and the interrogator, while in the part located on the responder, the output of the first memory unit is connected to the input of the first switching unit, the first , the second and third outputs of which are connected, respectively, to the first, second and third inputs of the first computing device, the fourth output of the first switching unit is connected to the first input of the first adder modulo q, where q is the number generating the multiplier a positive group, to the second input of which the output of the second memory unit is connected, the fifth output of the first switching unit is connected to the first input of the second adder modulo q, the second input of which is connected to the output of the third memory unit, the sixth output of the first switching unit is connected to the first input of the third adder module q, the second input of which is connected to the output of the fourth memory block, while the output of the first adder modulo q is connected to the first input of the first computing device, and also to the second input of the second a device, the first input of which is connected to the output of the first register, the output of the second adder modulo q is connected to the second input of the first computing device, as well as to the second input of the third computing device, the first input of which is connected to the output of the first register, the output of the third adder modulo q connected to the third input of the first computing device, as well as to the second input of the fourth computing device, the first input of which is connected to the output of the first register, the output of the first calculation The device is connected to the input of the second switching unit, the first output of which is connected to the input of the second register, and the second output is connected to the input of the third register, the input of the first register is connected to the input of the transponder, the output of the second computing device is connected to the input of the fourth register, the output of the third computing device is connected with the input of the fifth register, the output of the fourth computing device is connected to the input of the sixth register, the control inputs of the first and second switching units are connected to the control to the main input, the outputs of the second, third, fourth, fifth and sixth registers are the output of the friend-or-foe identification system located on the transponder, while in the part located on the interrogator, the fifth memory unit is connected to the interrogator output, the interrogator input is connected to the input the seventh register, the output of which is connected to the input of the fifth computing device, the output of which is connected to the output of the identification system located on the interrogator, and when the object appears in the visibility range, the interrogator selects “interrogator number "d, using the fifth memory block, then this number goes to the requestor's output and is sent to the input of the responder.

Images