The subject of the article is the process of data encryption for building systems of distributed secure data storage. The aim of the work is to develop a method of data encryption based on Redundant Residue Number System (RRNS) and evaluate its cryptographic strength. The tasks include analyzing the existing method of data encryption using RRNS and investigating its cryptographic strength; constructing a structural diagram of the encryption process based on RRNS and shuffling method based on the M-sequence key; justifying the use of the conditions mentioned in the work to reduce the bit width of the used modules. The methods used in the research are: RRNS-based digital information protection method; methods of data transformation and processing in RRNS; methods for evaluating the cryptographic strength of encryption algorithms. The following results were obtained: an algorithm for data encryption based on RRNS was proposed. The existing method of data encryption based on RRNS is investigated and an improved method of data encryption based on RRNS and the shuffling method based on the M-sequence key is proposed. A formula was derived to estimate cryptographic strength in RRNS-based data encryption, allowing calculation of module number and bit width for protection comparable to AES 128 against brute-force attacks. Suggested was a minimum message length to decrease required module bit width for specified protection levels. Cryptographic strength comparisons were made between classical RRNS encryption and proposed RRNS with shuffling method using M-sequence key. Findings: Novelty lies in proposing RRNS-based data encryption employing an additional key for M-sequence key-based shuffling, ensuring heightened cryptographic security. A structural diagram for RRNS data encryption was devised, alongside a formula for estimating cryptographic strength in the proposed RRNS method. The conducted research showed that the proposed method with a module bit rate of 8-16 bits provides 11-15 times higher cryptographic strength compared to the classical method of encryption in RRNS, and with a module bit rate of 8-16 bits, and with a module bit rate of 96-128 bits, on average, it is 3 times higher which makes it suitable for building secure distributed data storage systems.1
To backup data, distributed systems can be used that make it difficult for intruders to access data. Distributed data storage systems allow splitting data into fragments which can be located on physically remote devices or cloud services that complicate physical access to information. In the case when an attacker gets access to part of the data or one of the data storage devices, the use of encryption, in particular, the block type of encryption and maintaining sequential blocks on different devices allows for additional data protection and makes it impossible to decrypt it.
There are a number of methods for splitting data into fragments; one of them is the use of
the Residue Number System. According to RRNS, data is split into fragments due to the
predetermined modules, which reduces the bit-width of the number and increases the speed of
performing arithmetic operations, especially when processing long-length messages, for
example, during hardware implementation of cryptographic algorithms [
Despite a large number of existing data protection methods and algorithms, the number of
cyber threats to intelligent and computer networks is increasing [
Data encryption methods are developed with the aim of detecting modifications along with
ensuring security to prevent an intruder from getting access to data or modifying it when
transmitting [
Common data protection methods include the use of long symmetric and asymmetric keys
[
In turn, the use of non-positional number systems, an example of which is the RRNS [10], makes it difficult for an attacker to decode data, and the use of simple algorithms allows the implementation of multilevel encryption methods [11], which, in combination with other common solutions, significantly improves data protection [12]. In [13], a special system of modules for building correction codes based on the RRNS was considered. Their use is one of the ways to increase the reliability and security of data storage systems [14] and distributed storage of residue files allows increasing trust in cloud storage providers [15].
The purpose of the research is to develop a data encryption method based on the RRNS and estimate its cryptographic strength.
Data conversion in RRNS is carried out according to the following formula: xi = Xmodpi , (1) where (x1, x2 ,..., xi ,...xn ) is the sequence of residues; X – data given in the positional number system; pi - relatively prime modules.
The received residues xi are written into files and stored in the network or distributed data storage. Data conversion from the RRNS into the positional number system is carried [14]: n X = ∑ xi ⋅ bi modP ,
i=1 where P is the total range of the system and determined by the following formula: n P = ∏ pi ;
i=1 bi are the base numbers of the RRNS, which are determined according to formula: (2) bi = P ⋅ mi ≡ 1modpi ,
pi where mi – is a set of coefficients that ensure the conversion orthogonally and satisfy the condition 0<mi<pi.
To detect errors in the RRNS, an extended system of modules (p1, p2, …, pi, …, pk, …, pn) is used, where k is the number of modules of the working range.
To detect errors, the following concept of the working range is introduced: k H = ∏ pi .
i=1
If an error occurs in the residue of one of the modules (x1, x2, …, xi*, …, pn) the value X* obtained as a result of the inverse transform will be outside the working range, i.e. H<X*.
Data encryption algorithm in the RRNS consists of the following steps: 1. Choosing the size of the encryption block. 2. Selecting the number of relatively prime modules. 3. Selecting the value of relatively prime modules. 4. Converting the data block into decimal format. 5. Converting the data block into the RRNS according to formula (1). 6. Coding residues into the optimal volume format. 7. Recording the residues xi into n files to store them on distributed media.
The data encryption key in the RRNS is presented by the values of modules pi and their number n.
It should be noted that conducting theoretical research, we are not restricted to any conditions when selecting modules, but they must be taken into account during implementation. The first condition is that the smallest addressable memory cell is a byte.
Accordingly, the values of modules should be selected so that the working range meets the following condition:
H ≥ 28*с + 1 , where H – is the working range; с – is an integer that determines the amount of stored data.
It is also necessary to take into account that relatively prime numbers are used as modules in RRNS, the values of which affect the size of the working range [16].
For example, when с=2, the value of the working range must satisfy the condition H≥65537. To fulfill this condition, one of the options is a set of modules: {41, 43, 47}, with the value H=82861, and another one is as follows: {3, 5, 7, 11, 13, 17}, H= 255255.
As it is seen, both values satisfy the condition, however, in the second case, the number of modules is 2 times larger and, accordingly, the number of memory cells for storing the residues is also required to be 2 times larger.
Due to this comparison, it is possible to derive the condition for selecting the optimal set of modules, namely, the dependence on the number and bit-size of modules.
We cannot unlimitedly increase the number of modules, because it complicates the operations of writing and reading data from memory, and the speed of performing arithmetic operations with modules of the same bit-size takes the same amount of time [17].
When comparing sets of modules {41, 43, 47} and {3, 5, 7, 11, 13, 17} which have the same bit-size, i.e., 1 byte and 2 bytes of the working range, the 1st set of modules is 2 times more effective, since its residues are 3 bytes when calculating and the 2nd set of residues is 6 bytes.
When attempting unauthorized data decryption (2), the intruder needs to determine the number n and the value of modules pi, which have been used to encrypt data in RRNS.
Thus, the problem of estimating the cryptographic strength of data encryption based on the RRNS is still relevant.
According to the asymptotic distribution of prime numbers, their amount in the interval from 0 to some q is approximately determined by the following formula: π(q) = q . (3)
lnq −1,07 When using s-bit numbers, the range q can be represented as q=2s, and formula 3 is as: π(s) = 2s . (4)
(s ⋅ ln2) −1,07
When selecting a system of n modules, the approximate number of options can be determined by the following formula: π(s) L(n,s) = ∏ π(s) . (5)
π(s)−n
For small values of s, this notation is more accurate. However, under the condition of using modules with the bit-size s≥16, formula 5 can be represented as follows:
Accordingly, the total complexity of direct and inverse transforms based on the RRNS is determined due to the following formula [17]:
In order to estimate the cryptographic strength of the ciphertext transmitted to the remote storage device, it is proposed to take into account not only the overall complexity of the cryptanalysis algorithm based on the RRNS, but also the size of the files of residues, since when intercepting a message, an intruder does not know the bit-size of the selected modules. Therefore, to decipher the message, it is necessary to sort through all the prime numbers that can be used as modules during encryption.
According to the asymptotic distribution of prime numbers (formula 4), the amount of prime numbers in the file of residues is determined by the following formula: f 1 S(f) = f ⋅ ∑ (9)
i=3 i where f is the bit-size of the files with residues.
Since the development of a system with a redundancy of more than 100% is not advisable, therefore the sum of the sizes of all files with residues should not exceed twice the size of the initial file, and the size of the fragment itself is calculated according the following formula: Q(n, f, s) 2135 2145 2140 2150 2129 2139 2150 2160 2170 2180 2130 2140 According to Table 4, it can be concluded that consideration of the minimum length of the files of residues of 1 KB when determining the complexity of the message decryption allows reducing the bit-size of modules by 8 bits while ensuring the required level of protection.
sequences method based on
pseudorandom
In order to increase the level of the encryption algorithm cryptographic strength based on the RRNS, this paper proposes an improvement of the encryption method by changing the position of the residues xi using pseudorandom sequences PRS (S.key).
As a PRS, we select an M-sequence that provides a high bit generation rate and the required key length [19, 20].
Figure 1 shows an encryption scheme based on the RRNS, where pi is a set of modules, Cipher is an encryption block, and Decipher is a decryption block.
It is proposed to write the calculated residue to the file of residues without change when the signal is '0'. In the case when the value of the sequence is equal to '1', then the residues are recorded into the following file of residues, and the last residue is recorded into the first file (Fig. 2).
The residues are shifted according to the value of the PRS, which is notated as '0' and '1'.
During decryption, the inverse sequence of operations is performed, i.e., first, the contents of the files of residues (F_1 - F_4) are written into the corresponding residue arrays to which the shift key operation is subsequently applied.
Considering that the RRNS is a non-positional number system, the shift of the residues by one position makes it difficult to restore data. If the set of modules used to develop the system is unknown, an attacker will not be able to obtain the source file even after gaining access to all residue files.
To recover the correct sequence of residues, an attacker needs to sort through each of the possible residues in all the residue files. It is possible to obtain the correct residue file if the sequence for all files is correctly selected. The number of residues depends on the number of modules bits, and the complexity of sorting possible candidates taking into account the shift, is determined by the following formula: s 8 f O(n, f, s, i) = ∑ n!8⋅i . (11)
i=1
As it has been proposed earlier to use a minimum size of the residue file of at least 1 KB, then by substituting the corresponding values into (11) and taking into account the data in Table 3, the complexity of sorting residues in the residue file can be determined (Table 5).
As it can be seen in Table 5, the complexity of sorting residues Q(n, f, s, i) taking into account the shift, is quite high, and its consideration makes it possible to increase the cryptographic strength of the developed system and reduce the bit-size of the modules.
Thus, taking into account the complexity of finding residues (formula 6), the cryptographic strength of the system (Table 2), the complexity of sorting the residues (Table 5) and messages whose residues will be at least 1 KB, it is possible to determine the complexity of breaking into the system when using a different number of modules with a bit-size of less than 16 bits (Table 6).
n 3 4 5 6 7 8
Q(n, f, s, i) 2229 2371 2533 2711 2904 21109
The results of the dependence of the system cryptographic strength on the bit-size of the residues with two information and one check modules are shown in Table 7.
As it can be seen from the above calculations (Table 7), when the bit-size of the modulus increases by 8, the bit-size of the computational complexity of the cryptanalysis algorithm Q(n, f, s, i) does not increase linearly, but it significantly decreases when the bit-size of modules increases up to 24 bits and higher.
A comparison of the dependence of the calculation complexity of the decryption algorithm O(n, k) (Table 1) and the developed data encryption method Q(n, f, s, i) (Table 6) on the bitsize of modules when n=3 is shown in Figure 3.
The proposed method provides 11-15 times higher cryptographic strength with 8-16 bit modules than the classical method, and on average 3 times higher with 96-128 bit modules.
It should be noted that this complexity of breaking into the system will arise only if the attacker does not know the bit-size and the modules themselves.
However, when the system works for a long time, all official information usually becomes public knowledge.
In this case, an attacker can examine each digit position separately, checking whether the condition 0≤X≤M is fulfilled, and formula 11 is as follows: s 8 f
O(n,f,s,i) = ∑i=1 n!⋅ 8 ⋅ i (12)
Taking into account the previously mentioned conditions and formula 12, the complexity of sorting through the fragments in the residue file with the modules known to an attacker is shown in Table 8.
0 8 16 24 32 40 48 56 64 72 80 88 96 1041121201281S36
As it is shown in Table 8, in the case when an attacker knows the set of modules pi, which has been used to split the input data array into arrays of residues, the sorting complexity significantly reduces and largely depends on the length of the file and the key length.
Since it has been assumed that for calculations the residue files should be at least 1 KB, and the use of 1-byte modules is not advisable due to the increase in the time of the read/write operations, a 512-bit key is sufficient for data encryption.
Among the results of this study, the following issues need to be discussed.
Firstly, when developing secure RRNS on the basis of redundant RRNS, the problem of justifying the number of check modules arises. According to the 2022 Backblaze Storage Cloud report [21], the percentage of failure of data storage devices (DSD) depends to a small extent on the size of the device itself and to a large extent it depends on the time of operation, but even for the devices that have been working continuously for more than 8 years, the percentage does not exceed 3.73% for small DSD (up to 10 TB), and for disks with a size of 1216 TB, on average it is 1.07%. This proves the high reliability of modern DSD and allows the detection and correction of only a single error when calculating the number of RRNS check modules.
Secondly, we propose to use the bit-size of the residues not less than 1 KB. Table 3 shows the dependence of additional cryptographic strength on the size of the residue file.
Finally, a PRS of maximum length (M-sequence) is used as an additional key, because it provides a high bit generation rate and the required key length. However, other types of PRS can also be implemented.
The method for data encryption based on redundant RRNS and the residue shift by the Msequence key is proposed and investigated in this paper.
The formula for estimating the cryptographic strength of data encryption based on the RRNS is created, which makes it possible to determine the number and bit-size of modules that provide a level of protection similar to the AES 128 algorithm in brute-force attacks.
It is proposed to reduce the minimum length of the message, which makes it possible to reduce the bit-size of modules necessary to achieve the specified level of protection.
A comparison of the cryptographic strength of the classical method of encryption in the RRNS and the proposed method based on the redundant RRNS and the residue shift by key is carried out.
The proposed method provides 11-15 times higher cryptographic strength using 8-16 bit modules than the classical method, and 3 times higher on average when using 96-128 bit modules.
In our opinion, the most promising areas of future research are the following ones: • • •
Studying the impact of other types of attacks on the proposed encryption method. Investigating the cryptographic strength of the algorithm when increasing the number of the RRNS modules.
Studying the prospects of using the proposed approach to encryption of medical images. [9] E. Ochoa-Jiménez, L. Rivera-Zamarripa, N. Cruz-Cortés and F. Rodríguez-Henríquez.
Implementation of RSA Signatures on GPU and CPU Architectures. in IEEE Access, vol. 8, (2020) 9928-9941. doi: 10.1109/ACCESS.2019.2963826. [10] Ananda Mohan, P.V. Residue Number Systems: Theory and Applications. Birkhäuser,
Cham, Switzerland, 2016. [11] E. Y. Baagyere, P. A. -N. Agbedemnab, Z. Qin, M. I. Daabo and Z. Qin. A Multi-Layered Data Encryption and Decryption Scheme Based on Genetic Algorithm and Residual Numbers. In IEEE Access, vol. 8, (2020) 100438-100447. doi: 10.1109/ACCESS.2020.2997838. [12] P. A. -N. Agbedemnab, E. Y. Baagyere and M. I. Daabo. A New Image Encryption and Decryption Technique using Genetic Algorithm and Residual Numbers. 2019 IEEE AFRICON, Accra, Ghana, (2019) 1-9. doi: 10.1109/AFRICON46755.2019.9133919. [13] V. Yatskiv, A. Sachenko, N. Yatskiv, P. Bykovyy and A. Segin. Compression and Transfer of Images in Wireless Sensor Networks Using the Transformation of Residue Number System. 2019 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), Metz, France, (2019) 1111-1114. doi: 10.1109/IDAACS.2019.8924372.. [14] V. Yatskiv, S. Kulyna, P. Bykovyy, T. Maksymyuk and A. Sachenko. Method of Reliable Data Storage Based on Redundant Residue Number System. 2020 IEEE 5th International Symposium on Smart and Wireless Systems within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS-SWS), Dortmund, Germany, (2020) 1-4. doi: 10.1109/IDAACS-SWS50031.2020.9297052. [15] A. Kar et al. Secuirity in cloud storage: An enhanced technique of data storage in cloud using RNS. 2016 IEEE 7th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON), New York, NY, USA, (2016) 1-4. doi: 10.1109/UEMCON.2016.7777905. [16] E. Vassalos, & D. Bakalis. Residue-to-Binary Converter for the New RNS Moduli {22n−2, 2n−1, 2n+1}. 2019 Panhellenic Conference on Electronics & Telecommunications (PACET), Volos, Greece, (2019) 1-4. doi: 10.1109/PACET48583.2019.8956249. [17] S. Kulyna. Evaluation of the reverse transformation methods complexity of the residual number system for secure data storage. Scientific Journal of TNTU, Tern.: TNTU, vol. 107, iss 3, (2022) 21-28. doi: 10.33108/visnyk_tntu2022.03.021. [18] O. G. Abood, S. K. Guirguis. A survey on cryptography algorithms. International Journal of Scientific and Research Publications, vol. 8, iss 7, (2018) 410-415. doi: 10.29322/IJSRP.8.7.2018.p7978. [19] M. Shirvanimoghaddam. On the Hamming Weight Distribution of Subsequences of Pseudorandom Sequences. 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia, (2021) 1671-1675. doi: 10.1109/ISIT45174.2021.9517946. [20] García, J. Espinosa, G. Cotrina, A. Peinado, A. Ortiz. Security and efficiency of linear feedback shift registers in GF (2n) using n–bit grouped operations. Mathematics, vol. 10, iss 6, (2022) 996. doi: 10.3390/math10060996. [21] Backblaze Drive Stats for 2022, 2022. URL: https://www.backblaze.com/company/about.html.