The computing development in the post-quantum cryptography era puts forward new requirements for cryptographic mechanisms for providing basic security services. The advent of a full-scale quantum computer casts doubt on the cryptographic strength of cryptosystems based on symmetric cryptography and public-key cryptography. One of the promising areas in the opinion of US NIST experts is the use of crypto-code constructions (crypto-code schemes or code-theoretic schemes) by McEliece or Niederreiter. The construction allows one integrated mechanism to provide the basic requirements for cryptosystems - cryptographic stability, speed of cryptoconversion and besides - reliability based on the use of noise-resistant coding. However, their use is difficult due to the large volume of power of the alphabet, and the possibility of hacking based on Sidelnikov's attack. The paper proposes to use non-cyclic noiseresistant codes on elliptic curves in a modified McEliece cryptosystem that are not susceptible to Sidelnikov's attack. The main criteria for constructing a modified crypto code based on the McEliece scheme on elongated elliptic codes are investigated. It is proposed to reduce the energy intensity in the proposed crypto-code design by reducing the power of the Galois field while ensuring the level of cryptographic stability of the modified cryptosystem as a whole with its software implementation. To reduce the field power, it is proposed to use modified elliptic codes, which allows to reduce the field power by 2 times. A comparative assessment of the performance of cryptosystems is carried out. The results of statistical stability studies based on the NIST STS 822 package confirm the cryptographic strength of the proposed cryptosystem on modified elongated elliptic codes. It is proposed to use the method of evaluating the cryptographic strength of various cryptosystems based on the entropy approach.
The rapid growth of the volume of data being
processed and the development of computing
technology has put forward new requirements for
reliability and data security. Studies on the
influence of quantum computing using quantum
superposition and quantum entanglement to
transmit and process data have shown that
quantum computers that use special algorithms
(for example, Shor’s algorithm) will be able to
factorize numbers in polynomial time [
The advent of a full-scale quantum computer casts doubt on the cryptographic strength of cryptosystems based on symmetric cryptography and public-key cryptography. One of the promising areas in the opinion of US NIST experts is the use of crypto-code constructions (crypto-code schemes or code-theoretic schemes) by McEliece or Niederreiter. The construction allows one integrated mechanism to provide the basic requirements for cryptosystems – cryptographic stability, speed of cryptoconversion Pand besides – reliability based on the use of noise-resistant coding.
The analysis showed that for the provision of
basic security services, crypto-code constructions
are usually used based on the McEliece and
Niederreiter schemes. To ensure the level of
cryptographic strength in post-quantum
cryptography, it is necessary to use the power of
the alphabet in a field of 210-213 degrees, which
is a significant drawback of their practical
application [
The second drawback is the hacking attack on
the McEliece scheme based on linear-fractional
transformations and the property of triply
transitivity of the automorphism groups of the
generalized Reed-Solomon code, proposed in the
work of professor Sidelnikov from Moscow State
University. The essence of which is to find the
elements of the generating matrix and remove the
action of masking matrices [
The orthogonality of the matrices, which is generative and test, allows us to consider the effectiveness of the attack on the Niederreiter scheme. A promising way to eliminate the identified patterns Sidelnikov proposes to use cascade or algebraic geometry codes – codes built based on the algebra of the theory of noiseresistant coding and geometric parameters of the curve, in particular elliptic curves.
The algebraic-geometric code uses the mathematical apparatus of noise-resistant coding and the parameters of the spatial curve. This allows us to provide resistance to Sidelnikov’s attack and proper (n, k, d) parameters of the errorcorrecting code, which, under equal conditions of length n, provides bigger values of the d and k parameters (allows to transmit more characters in open text and correct more errors )
The paper proposes to use non-cyclic noiseresistant codes on elliptic curves in a modified McEliece cryptosystem that are not susceptible to Sidelnikov’s attack. The main criteria for constructing a modified crypto code based on the McEliece scheme on elongated elliptic codes are investigated. It is proposed to reduce the energy intensity in the proposed crypto-code design by reducing the power of the Galois field while ensuring the level of cryptographic stability of the modified cryptosystem as a whole with its software implementation. To reduce the field power, it is proposed to use modified elliptic codes, which allows to reduce the field power by 2 times. A comparative assessment of the performance of cryptosystems is carried out. The results of statistical stability studies based on the NIST STS 822 package confirm the cryptographic strength of the proposed cryptosystem on modified elongated elliptic codes.
The main advantage of symmetric and asymmetric Crypto-Code Systems (CCS) is the high speed of information conversion and the integrated provision of reliability and information concealment (confidentiality) that satisfies the basic security requirements.
For security reasons, the perspective direction is the use of asymmetric cryptosystems based on CCS McEliece integrated (with one mechanism) providing reliability values at the level of 29 – 212 and cryptostability 230 – 235 group operations when constructed over the field GF(210).
Figure 1 shows the classification of cryptocode structures and the provision of basic security services. The main advantage of which is the provision of cryptographic stability, efficiency and reliability in the transmission of information in the postquantum period.
Table 1 shows the results of comparative studies of the effectiveness of cryptographic information security methods at a fixed level of stability.
cryptographic Security Key length cryptogra Additional transfonrmatio model [bits t,r[abnpisthsiti/cisoencs features
symmetric ciphers
symmetric ciphers
Practical 128, 256, 106 – 109 security 512 Practical 128, 256, 107 – 1010 security 512
SePcruoroifty 0((2,125∙215∙18060)6),6 106 – 108 imrnecolErinaregribat,ooislriirntiyng
In Table 1, there are presented values: average
(the complexity of cryptanalysis is the
bestknown algorithm of at least 2128 operations);
high (the complexity of cryptanalysis is the
bestknown algorithm of at least 2256 operations);
super-high (the complexity of cryptanalysis is the
best-known algorithm of at least 2512 operations)
[
Hence, as it follows from the above results of the comparative analysis (Table 1), asymmetric cryptographic algorithms using TCS allow the cryptographic protection of information to be realized on the technology of public keys. And thus they provide the speed of crypto-code transformation of information with the speed of encryption of block-symmetric ciphers (BSС). In addition, the practical use of ACCS information security allows to ensure the security and reliability of data, based on the integration of channel coding and encryption mechanisms in a comprehensive manner.
In [
In [
In [
In the following papers [
In computer networks with decisive feedback,
the authors ensure the use of the McEliece
cryptocode design in the G.709 optical transport network
(OTN) infrastructure to provide integrated
requirements for both reliability and security [
Thus, the analysis showed that crypto-code constructions belong to the section of quantumresistant cryptography and can be used instead of asymmetric cryptosystems soon. In this regard, their improvement is of wide interest among the scientific community.
However, all the codes proposed by the
authors are cyclical and prone to Sidelnikov's
attacks [
Protocol Formation of key data Protocol
Secret key a1, , an
Session key
|IV1|, е Private key G, X, P, D
Public key
Gx = X × G × P × D i cX*= i × GX + e
Encryption
X-1, P-1, D-1 cX* c` = cX* × D-1 + P-1 c` = i` × G + e` i = i × X-1 Decryption i B
Property Shortened MEC Extended MEC (n, k, d) code n = 2 q + q +1− x , n= 2 q +q+1− x+ x1 parameters , constructed by k ≥ α – x, d ≥ n – k ≥ α – x + x1, displaying the α, α=3×degF, d ≥ n – α, view φ:X→Pk-1 k + d ≥n α = 3 × degF (n, k, d) code n = 2 q + q +1− x parameters , n= 2 q +q+1− x+ x1 , constructed by k ≥ n – α, d ≥ α, k ≥ n – α, d ≥ α, displaying the α = 3×degF, k + d α = 3 × degF view φ:X→Pr-1 ≥ n
The proposed McEliece MCCS can reduce the power of the alphabet, which al-lows them to be implemented in practice, while ensuring the required level of crypto-graphic strength due to the introduction of additional initialization vectors: IV1 – defines shortening characters from a code word (cryptograms), IV2 – defines elongation characters (plain text) of a codeword (cryptogram), see also Fig. 3. Let us con-sider the results of a study of the basic properties of the proposed crypto-code systems.
To estimate time and speed parameters it is common to use the unit of measurement CPB (cycles per byte) – the number of processor cycles, which should be spent to process 1 byte of incoming information.
Notes:* duration of 1000 operations in processor cycles: reading a character – 27 cycles, com-paring strings – 54 cycles, string concatenation - 297 cycles.
** for the calculation, a processor with a clock frequency of 2 GHz was used, taking into account the load by the operating system, is taken 5%
Algorithm complexity is calculated from
expression [
Per = UtlCPU_clock/Rate, where Utl – utilization of the CPU core (%) and Rate – algorithm bandwidth (bytes/sec).
In Table 4 there are shown dependency research results of code length sequence of algebrogeometric code in McEliece TCS from the number of processor cycles due to executing elementary operations in the program realization of crypto-code systems.
Table 5
sscCyorsydtpeetmo- lsehCeenonqcdgueet (bRABaalgyntotederwi/thisdmethc), (anuC%ttPii)oUliz i(cAmtCoylgBm,oPpr)Pilteehxr McEliec 100 46 125 790 56 61,5 e ACCS 1000 120 639 896 56 62,0 100 51 694 662 56 61,7
In order to estimate the parameters of asymmetric code-theoretic schemes using elliptic codes, let us introduce the following notation: • lI – length of the information sequence (block) arriving at the input of the crypto-code structure (in bits); • lK – the length of the public key (in bits); • lK+ – the length of the private key (in bits); • ls – the length of the code (in bits); • OK - the complexity of the formation of the code (number of group operations); • OSK – the difficulty of decoding the cryptogram (the number of group operations); • OK+ – the complexity of solving the analysis problem (the number of group operations).
For the construction of graphs, conditional abbreviations (prefixes) were used: • uk – MACCS with truncated MEС; • ud – MACCS with elongated MEC. In calculating the parameters of cryptosystems, the Galois fields were used: • for McEliece TCS – GF(210); • for MACCS with truncated / elongated MEC – GF(26).
In the next step, we perform a comparative analysis of the parameters of the McEliece asymmetric code-theoretic scheme (MACS) using EC, with the parameters of the modified MACCS McEliece on MEC. To estimate the length of the infor-mation sequence (in bits) arriving at the input of the MACCS with the algebraic (n, k, d)code over GF(2m) (where m − the power of the extended Galois field), we use the expressions: • lI = k × m, for AСCS on the EC; • lI = 1/2k × m, for MCCS on truncated MEC; • lI = k × m, for MACCS on elongated MEC.
In Tab. 6 and in Figure 4 we show the cryptogram formation complexity from the power of the field, where code rate (R) stands for the relative speed of coding R=k/n, the encoder assigns to each message of k digits a longer message of n digits called a codeword.
From the provided data it can be seen that the cryptogram formation complexity for the chosen power of the GF 26 on the truncated and elongated codes is much lower (by 5 times and more) than in the original realization of MACCS to the EC. Respectively, the speed of the formation of the cryptogram will significantly increase.
• In order to estimate the length of the cryptogram (in bits), we use the expressions: • ls = n × m, for ACCS on the EC; • l_s=(2√q+q+1-1/2k)×m, for MCCS on truncated MEC; • l_s=(2√q+q+1-1/2k+1/2k)×m, for MCCS on elongated MEC. 20 881 of cryptogram formation, shows a significant increase in the decoding rate when using truncated and elongated MEC.
The length of the public key (in bits) is determined by the sum of the elements of the matrix and is given by the expressions: for MCCS on truncated MEC; lK = k × n × m , for ACCS on the EC:; = 21 × (2√ + + 1 − 1/2 ) × , = 21 × (2√ + + 1 − 21 + 21 ) × for MCCS on elongated MEC.
The length of the private key (in bits) is determined by the sum of the elements of the matrices X, P, D (in bits) and is given by the expressions: lK+ = n2× 2k× mf,or ACCS on the EC; = 21 [log2(2√ + + 1)], for MCCS on truncated MEC; = (
21 − 21 )[log2(2√ + + 1)], for MCCS on elongated MEC.
In Tab. 8 and Figure 5 there are shown the dependency of the breaking complexity based on the permutation decoding on the field strength. Dependence of Breaking Complexity in Various , • • • • • •
0.75 0.5(ud) 0.75(ud) 0.5(uk) 0.75(uk) 1.056 1.38 2.237 3.017 2.868 4.867 4.843 6.613 = ( + 1) × (2√ + + 1 − 21 + 21 ), for non-systematic: = ( + 1) × (2√ + + 1 − 21 + 21 ).
The complexity of decoding of a pattern is defined by expressions: • for ACCS on EC:
OSK = 2×n2+k2+4t2 + (t2 + t – 2)2/4, • for MCCS on truncated MEC: = 2(2√ + + 1 − 21 )2 − 2 2 + 4 2 + 1 ( + −2)2.
4 • for MCCS on elongated MEC: 1 = 2(2√ + + 1 − 2 + 1/2 ) − 2 ( + − 2)2 + 4 2 + where
The complexity of the task of the analysis (decoding) solution is set by expressions: • for ACCS on EC:
OK+ =
× n × r, Ncov CCnt −nt k =
n(n −1)...(n − t −1) (n − k )(n − k −1)...(n − k − t −1)
t=[(d–1)/2]
The potential strength of the cryptosystem is defined by size ρ×t, and noise stability of system – (1 – ρ) × t. • For MCCS on truncated codes: •
= × (2√ + + 1 − 21 ) × .
For MCCS on elongated codes: = × (2√ + + 1 − 21 + 1/2 ) × .
In Tab. 9 and Figure 7 it is presented dependence of complexity of breaking and complexity of coding for various speeds of the EC (MEC).
The results of studies of the dependence of the software implementation depend-ing on the field power and the parameters of algebra-geometric codes are also pre-sented, as can be seen from Table 11, the use of modified crypto-code constructions provides a 5-fold reduction in energy costs for the software implementation, that allows for their practical implementation
One of the main components of the evaluation of the stability of cryptographic algorithms is the estimation of its statistical security. It is believed that the algorithm is statistically secure if the sequence it generates by its properties is not inferior to a random sequence - such sequences are called “pseudorandom”. For the experi-mental estimation of how close the crypto-algorithms approximate the generators of the “random” sequences, statistical tests are used. The NIST STS benchmark pack-age for testing random or pseudorandom number generators is one of the approach-es to realizing the task of evaluating the statistical security of cryptographic primi-tives.
The use of this package makes it possible to
conclude with a high degree of probability as to
how much sequence that is generated by the
investigated primitive is statistically secure. A set
of NIST STS tests was proposed during the
contest for a new national standard for US block
coding in 2000 and developed by the staff of the
National Institute of Standard and Technologies
[
In accordance with the methodology, the decision to pass statistical testing is taken by the event that fulfills the following rules: 1. The rule #1. All q tests were executed, (q =(1,189) ̅), and if the value of the coefficient rj is inside the confidence interval [0.96, 1.00]; 2. The rule #2. All q tests were executed, (q = q =(1,189) ̅), and if for all tests by the Pearson 2 criterion the condition is met P(2)>0.0001.
For carrying out experimental research about the properties of the developed code cryptosystems the program is developed to realize the offered means of protec-tion of the information.
The following parameters have been selected during the tests: • length of the test sequence n = 106 bits; • number of tested sequences m = 100. Thus, the volume of the test sample was N = 106x100 = 108 bits; • significance level = 0.01; • number of tests q = 189.
Authors have obtained the results of statistical testing and statistical portraits of the developed means of information protection. The final values and results of the best world crypto-algorithms are summarized in Table 12.
As it can be seen from the presented data in Table 12 the proposed crypto-code systems on the modified codes are not inferior to the statistical characteristics of the randomness of the code sequence formation to the world standards of providing basic services: confidentiality, integrity and accessibility, while ensuring the required level of reliability of data transmission.
Consequently, the practical application of the developed information protection means allows to obtain good statistical properties of the generated sequences and to effectively ensure the security and reliability of the data being processed and transmitted.
The proposed express analysis makes it possible, without significant computational and energy costs, at the intuitive level, to compare not only the resistance of various crypto-algorithms (cryptosystems), but their software implementation. The algorithm of the entropy method for assessing crypto-resistance is shown in Figure 9.
Table 13 gives the results of the study into the stability and software effectiveness of the implementation of block and stream ciphers of varying complexity. We applied DES, 3DES, GOST 28147-2015, Kalina-256, AES-256 as block ciphers. To imple-ment a stream cipher, we used pseudo-random sequence generators of two different types: based on the rule “60” of cellular automata in its classical form, without modifications, and the cryptographically resistant generator SecureRandom from Java cryptolibraries, which is marketed as suitable for cryptographic applications. conclusions about the max-imally possible degree of dispersion as a characteristic of the architecture.
Computation of entropy of the original
message with a specified length Мi – original message, Рi– probability of the emergence of the i-th symbol in Мi, Li – number of the i-th symbols in Мi, Нi – entropy of the i-th symbol, H(M) – entropy M Computation of entropy of the encrypted
message with a specified length C – encrypted message, sPyi'm–bporloibnaCbi,lity of the emergence of the i-th Start
Input Мi Computation of probabilities (Pi) of the emergence of each symbol in Мi
Pi = Li / length(Мi) Computation of entropy of each symbol (Hi)
Hi = Pi log(Pi) Computation of entropy М (H(М))
H(М) = −Мi
Encryption М i : M ⎯K⎯ii →C Computation of ent'ropy C (H(C))
H(C) =−iL=1 Hi' Computation of difference in the entropies of the original text and the ouput ciphertext
HCypher = HC − HM
End Computation of probabilities (P') of the emergence of each symbol iin С
Pi' = L'i / length(Ci)
L'i – number of the i-th symbols in C, Computation of en(Htroi')py of each symbol Hcipi'h–eretnetxrto,py of the i-th symbol in a Hi' = Pi' log(Pi')
H(C) – entropy C
Entrop yEonftrtohpe Pegreceonfta y of the encrypt Differe entropy, minepessuatg meeesdsag nce adcditpehhdeebry
In Table 13, we calculated the entropy of the input and the encrypted text, differ-ence, as well as the percentage of entropy added to the entropy of plaintext by the cipher itself. An analysis of Table 1 allows us to assess the contribution of the cipher in the total entropy of the encrypted message. As they all were tested under identical conditions, it is possible to judge their relative performance.
The AES-like ciphers (SPN-system, substitution-permutation schemes) are worth mentioning. Both such ciphers, Kalina and AES, made the greatest contribution, larger than 103 %, to the entropy of the plaintext. According to the given results, both ciphers have the best diffusing effect. Approximately the same results were demonstrated by the symmetric block cipher (SBC) GOST 28147-2015: 72.89 % against 73.04 % for DES/3DES. This probably confirms
To compare the results, we conducted experiments using stream ciphers based on two different generators with a pseudorandom key sequence. Encryption was per-formed by the rule of addition for modulo two. In the first case, this is a generator based on cellular automata (the rule “60”). This is not a crypto-resistant generator whose sequence does not pass testing for NIST STS 822, while the second one is positioned as the crypto-resistant generator SecureRandom in the Java crypto-library. In both cases, the obtained values for entropy are much smaller than those for classic SBC, which does not allow us to argue about quality encryption with their help. Thus, the presented results suggest that a simple entropy method allows rapid assessment of the quality of ciphers used without referring to expert estimations. Such an express technique is available to anyone with a minimal knowledge of the information theory.
Moreover, in this way, one can evaluate different implementations of ciphers that will make it possible to select the best (optimal) software implementation that matches the terms and requirements of the user. For example, in our computer ex-periments, we used two implementations of the DES algorithm. One of them, given in Table 13 at number 3, demonstrated a 73.04 % increase in entropy after encrypting compared to the original text, another algorithm − 64.4 %. It is obvious that for practical purposes it makes sense to choose the first implementation, since it appears that its scattering characteristics are better. Thus, the expressanalysis allows assessment of the quality of implementation of classic (and other) cryptoalgorithms in order to select an optimal crypto library out of many commercially available libraries.
We shall consider the results obtained in terms of maximum cryptographic infor-mation protection. An indicator of such protection is the entropy of the encrypted binary file, given in Table 14.
y of Entropy y of the of the cryptogra input encrypted phic messa message protection ge , Pc
resistant generator SecureRan 0.4692 0.747287 0.7472877 dom from 76 753 53
cryptolibraries DES 3DES 0.4692 76
AES-256 Perfect cipher
It is known that the maximum possible
cryptographic protection is provided by the
socalled "perfect cipher" by Shannon, which as a
result of encryption produces a random number
[
In Figure 10 there are shown the results of studies of the average entropy of crypto-grams of different BSS of meaningful plaintext with a length of M = 108 bits, with an interval of N = 5 × 106 bits.
Analysis of Figure 10 practically confirms the possibility of using the express method for the selection of software security mechanisms based on cryptoalgorithms.
As a result of the conducted research, it can be concluded that
1. Evaluation by NIST specialists of the computing capabilities of quantum com-puters requires a review of the use of traditional encryption algorithms to provide basic security services based on symmetric and asymmetric cryptography. The growth and synergy of modern threats put forward new requirements for systems for protecting confidential information. At the same time, the use of crypto-code constructions allows us to provide not only the required level of cryptographic stability, but also the reliability of the transmitted information. However, their use in communication devices is associated with significant energy and computation-al costs, which does not allow their practical use. Besides, the proposed Sidelnikov attack does not allow the use of many well-known codes; to counter it, it is pro-posed to use algebraic geometries based on the parameters of elliptic curves.
2. The overall structure of asymmetric crypto-code systems based on the McEliece TCS enabling integrated (with a single device) provision of the required indicators of reliability, efficiency and data security was analyzed. A major shortcoming of ACCS based on the McEliece TCS is a big volume of key data, that constricts their use in different communication system areas (today cryptographic strength on the level of the provable strength model is provided while building ACCS in the Galois field GF(213)). The use of modified (shortened) elliptic (algebraic) codes helps to reduce the volume of key data while maintaining the requirements for cryptographic strength of ACCS. Estimation of the data conversion performance is comparable to the speed of direct and inverse cryptographic conversion of modern BSC, this ensures the cryptographic strength at the level of asymmetric cryptosystems (cryptographic strength is based on the theoretical complexity problem – random code decoding).
3. The use of modified crypto-code constructions in modified (shortened, elongated) elliptic codes allows to reduce the level of the alphabet with the required level of cryptographic strength. For this, additional session keys are used (initial initializa-tion, which specify the symbols of correlation and/or extension), as well as valid codewords on the receiving side. The alphabetical index of the cryptosystem without reducing the cryptographic strength of the system as a whole ensures their practical application and use in the protocols of Internet resources and infor-mation and communication systems in the conditions of post-quantum cryptog-raphy.