Today, the information security of each country is a key issue in ensuring national security, taking into account that modern information and communication technologies (ICT) are implemented in all spheres of life. Increasing number and power of cyberattacks on ICT forcing scientists around the world to seek new methods to secure information. Traditional cryptographic methods, which are mostly used to ensure data confidentiality, do not provide protection against all currently known attacks, in particular, they are vulnerable to attacks based on quantum algorithms. Ways to solve this problem are the protocols of quantum and post-quantum cryptography. Thereby this article describes hashbased digital signature systems. These systems are safe against quantum computer attacks. Quantum computers can break existing public-key crypto systems. Quantum computer solves the discrete logarithm problem both for finite fields and elliptic curves. As it is able to efficiently calculate discrete logarithms it can easily break Diffie-Hellman key exchange protocol. Hash-based digital signature systems have performance problems. The efficiency of the scheme is analyzed in the article. The Merkle digital signature algorithm using recursion was implemented. A performance analysis was conducted. To improve the efficiency in the implementation of this algorithm, the recursion was replaced by loops. An analysis of the resulting implementation was carried out. Modified implementation showed very good results.
Today, in digital era, data security is top of mind for many businesses and
governments to protect: financial records, medical histories, military strategy, confidential
information and more. Information technologies are presented in all spheres of human
life. But openness and publicity of network and Internet services, together with the
evolution of cyber-attacks, significant increase of ICT users and the amount of
information processed, stored and transmitted by ICT, jeopardize the information
confidentiality, which is usually provided by symmetric and symmetric cryptography, that
have certain shortcomings [
As it is known symmetric methods, in particular, are characterized by the problem of
secret keys distribution, and asymmetric methods are slow and require significant
computing resources [
In addition, the stability of all traditional cryptosystems depends on the
computational capabilities of intruder and is based on the hypothetical impossibility of solving
a certain class of mathematical problems in polynomial time [
Scientists and experts are actively working on the creation of quantum computers.
GOOGLE Corporation, NASA the association USRA (Universities Space Research
Association) and D-Wave teamed-up to develop quantum processors [
Quantum computers can break existing public-key crypto systems. Quantum
computer solves the discrete logarithm problem both for finite fields and elliptic curves.
Being able to efficiently calculate discrete logarithms it can break Diffie-Hellman key
exchange protocol [
Public-key cryptography is used in different products on different platforms and in various fields. Many commercial products use public-key cryptography, the number of which is actively growing. Public-key cryptography is also widely used in operating systems from Microsoft, Apple, Sun, and Novell. It is used in secure phones, Ethernet, network cards, smart cards, and it is widely used in cryptographic hardware. Public-key technology is used in protected Internet communications, such as S / MIME, SSL and S / WAN. It is used in government, banks, most corporations, different laboratories and educational organizations. Breaking existing public-key cryptosystems will cause complete chaos.
There are two major classes of methods to replace traditional cryptography – the first is quantum cryptography (based on the fundamental difference, the use of the unique capabilities of quantum mechanics), the second is post-quantum cryptography (for example, lattice-based cryptosystems, digital signature, syndrome-based cryptosystems and others).
Quantum cryptography can provide protection against interception of key
distribution, because, unlike classical cryptography, it is based on the laws of physics, and not
on the fact that successful interception would require huge computing power. Due to
the above properties of quantum systems, the attacker makes several errors in the
information transmitted by individual photons, which can be detected by legitimate
users. Note that the laws of quantum mechanics allow not only to detect perturbations
of states, but also link error rate in the measurements of legitimate users with the
amount of information that could be obtained by an attacker. Quantum key
distribution protocols main advantage is that they, in contrast to most classical schemes, have
theoretical and informational stability, independent of the computational and other
technical capabilities of the attacker [
On the other hand, post-quantum methods of information security are rapidly developing and great work is being done to create cryptosystems that are protected from quantum computer attacks. Such are hash-based digital signature systems. The security of these crypto systems is based on the resistance to collisions of hash functions. 3
Lamport–Diffie one-time signature scheme was offered, this scheme is a hashbased digital signature. In this scheme, key generation and signature generation are efficient, but the size of the signature is quite large.
For the signature key X, 2n random lines of the size n are generated.
X= (xn-1[0], xn-1[
Winternitz one-time Signature Scheme was proposed to reduce the size of the signature. In this scheme was chosen the argument w ∈ N, and is calculated r = [s/w]+[([log2 [s/w]] + 1 + w)/w]. R random numbers X1, X2, … Xr ∈{0,1}s was chosen, concatenation of which is X - private key. Are calculated Yi = h2w−1(Xi), the public key is Y = h(Y1||...||Yr). The message M is divided into s/w blocks b1, …, bs/w with the length w, if it is necessary, on the left are added zeroes. Later the checksum C =∑is=/w1 2w-bi is calculated. It is shown in the Fig 1. The binary representation of C is divided into [([log2 [s/w]] + 1 + w)/w] blocks, bs/w+1, ..., br with the length w.
Is calculated sigi = hbi(Xi) for i = 1, ..., r, the signature of the letter is sig = (sig1||...||sigr).
For signature verification are calculated b1, ..., br. For I = 1, ..., r is calculated signewi= h2w−1−bi(sigi) = h2w−1−bi(hbi (Xi)) = h2w−1(Xi) = Yi, if h(signew1, …, signewr)=Y, then the signature is correct.
The biggest problem of one-time signature schemes is the transfer of public key. It is necessary to make sure that the public key has not been changed, therefore it is necessary to use as little number of public keys as possible, and to make them shorter. 5
The Merkle crypto system was proposed to solve the problem of a one-time key pair. Merkle uses a binary tree to replace a large number of verification keys with one public key, the root of the binary tree. This cryptosystem uses a Lamport or Winternitz one-time signature scheme and a cryptographic hash function [17-20].
Key generation. The size of the tree must be H>=2 and using one public key 2H documents can be signed. Signature and verification keys are generated; Xi, Yi, 0<=i<=2H. Xi- is the signature key, Yi- is the verification key. Signature keys are hashed using the hash function h:{0,1}*{0,1}n in order to get the leaves of the tree.
The concatenation of two previous nodes is hashed in order to get the parent node,.
a[i,j] are the nodes of the tree;
a[
Message signature. A message of any size can be signed being transformed to size of n by means of hashing h (m) = hash,
An arbitrary one-time key Xany is used, and the signature is a concatenation of one-time signature, one-time verification key, index of a key and all fraternal nodes according to the selected arbitrary key with the index “any”.
Signature= (sig||any|| Yany||auth0,…,authH-1)
Signature verification. The one-time signature is checked using the selected verification key, if the verification is true, all the a[i, j] are calculated using "auth", index "any" and Yany. The signature is verified, if the root of the tree matches the public key. The algorithm of this system was implemented and recursion is used.
Recursion:
22.2.1.Sign is correct 22.3. Else
22.3.1. Sign is not correct
This example shows the implementation of the Merkle algorithm using recursion. The public key generation time for 8 elements is 0.0159 seconds, the encryption time is 0.01684, and the verification time is 0.0288883.
Recursion was changed to loops in order to improve the efficiency.
Implementation using loops: 1. Importing necessary libs 2. Define class 3. Defining “ loop_hashes(hashes) “ method 4. Set list “ arr ” 5. If hashes == “ ”, raise Exception 6. Foreach loop
6.1. sorting hashes and appending into arr 7. Length_of_block == length of arr 8. While loop, if length is odd, copy last element in list
8.1. append it into arr list 9. Set list “ another_arr ” 10. Set i = 0 11. While loop, Length_of_block > 1 11.1. Set to hash_f sha512() 11.2. Concatenate arr[i] and arr[i+1] 11.3. append it into “another_arr” list 11.4. append arr[i+1] to “auth_list” list 11.5. i = i + 2 11.6. if i equal to “Length_of_block” 11.6.1.set to “Length_of_block” “Length_of_block / 2” 11.6.2.i = 0 11.6.3.set “another_arr” to “arr” 11.6.4.empty “another_arr” 11.7. return “arr” 12. Set list “ hash_arr ” 13. Foreach loop
13.1. Generate Hex and put it into “ hash_arr ” list
14. Create message put it in “ st “ variable
15. Convert “ st “ value in binary
16. First_secret_key = hash_arr[0]
17. Second_secret_key = hash_arr[
18.1.1.Choose “ First_secret_key “ bit 18.2. Else
18.2.1.Choose “Second _secret_key “ bit
19. First_pub_key = hash(hash_arr[0])
20. Second_pub_key = hash (hash_arr[
21.1. Concatenate “ one-time signature ” with message’s hash
This example shows the implementation of the Merkle algorithm using loops. The “public key” generation time for 8 elements is 0.0061761 seconds, the encryption time is 0.0080878, and the confirmation time is 0.0181923. Here is the graph, which reflects the results: Thus, it could be seen, that the implementation changes gave rather good results. 6
In this work were described hash-based digital signature systems. These systems are safe against quantum computer attacks. Hash-based digital signature systems have performance problems. The efficiency of the scheme is analyzed in the article. The Merkle digital signature algorithm using recursion was implemented. A performance analysis was conducted. To improve the efficiency in the implementation of this algorithm, the recursion was replaced by loops. An analysis of the resulting implementation was carried out. Modified implementation showed very good results.
The project was conducted in the frame of the research grant PHDF-19-519.