Scientific and Technical Journal

ELECTROTECHNIC AND COMPUTER SYSTEMS

ISSN Print 2221-3937
ISSN Online 2221-3805
CAPACITY COMPLEXITY AND EMBEDDED ERROR DETECTION OF DEVICES FOR EXTENDED GALOIS FIELDS ELEMENTS PROCESSING
Abstract:

For extended Galois fields GF(dm) of about the same order (number of field elements) the amount of memory required to store elements codes (capacitive complexity) will be different for each field. Each digit of extended Galois field GF(dm) element code is represented by nb = élog2dù bits, by which you can encode dt = 2élog2dù> d of different code combinations. At the same time, dd = dt – d code combinations remain, which will never be encountered in the normal operation of processor and memory units and data channels. These unused (forbidden) code combinations can be used to control the work of these devices in the course of performing their basic functions, that is, to organize in-built testing, so called concurrent error detection (CED). Appearance of any forbidden combination in any Galois field element code digit will be the sign of error. In this paper, various extended Galois fields with approximately the same number of elements are compared by the capacitive complexity and concurrent error detection ability of the devices for such fields elements processing.

To date, the use of Galois GF(2m) binary fields has been standardized for the processing of digital signatures. In addition, there are standards that determine the use of the fields GF(pm) with the characteristic p > 3 (p is a prime number), although they do not deny the use of ternary fields with the characteristic p = 3. Fields with characteristic p ≈ 2768 are now being analyzed for use in post-quantum cryptography. For applied research of universal algorithmic computing systems models are needed that combine the achievements of the theory of abstract algorithms with the practice of designing and solving problems on real computers. The SH-model of the algorithm (software-hardware model) can be one. In the processes of synthesis, analysis and optimization of SH-models, it is proposed to use five complexity characteristics: hardware, time, capacitive, programmatic and structural ones, which are connected with each other and depend on each other.

Comparison of devices that process elements of extended Galois fields by the indicator of structural, hardware and time complexities was carried out in earlier works. Analysis of the capacity complexity and concurrent error detection ability of mentioned devices was not carried out.

Therefore, in the work in terms of capacitive complexity and concurrent error detection ability of devices that process Galois fields elements the next extended fields are considered: binary Galois field GF(2m), since they are now practically used; ternary fields GF(3m) - for use in the near future; other fields with high characteristics GF(pm) which are supposed to be involved in post-quantum cryptography.

It is shown in this paper that extended binary and prime Galois fields have the smallest length of elements codes (the smallest capacitive complexity), but the use of other extended Galois fields will not increase the length of the elements codes (capacitive complexity) by more than 30%. In order to increase the concurrent error detection ability of devices that process the extended Galois fields elements, it is recommended to use fields with characteristic d, which is the first prime number greater than power of 2, for example d = 3 or d = 5. Fields with characteristics d, which are either of power of 2 (d = 2), or are the first number smaller than the power of 2, but greater than 3, for example, d = 127, have the least concurrent error detection ability. From the standpoint of concurrent error detection cost, the field with a characteristic d = 3 (the extended ternary Galois GF(3m)) is the best. The redundancy of the extended Galois fields with characteristics d > 2 does not guarantee the detection of all errors that may occur when processing elements of such fields.

Authors:
Keywords
References
1. IEEE 1363-2000 (2000). Standard Specifications for Public-Key Cryptography [Text]. Copyright © 2000 IEEE. All rights reserved.

2.DSTU 4145-2002 (2002), InformationTechnology. Cryptographic Techniques. Digital Signatures Based on Elliptic Curves. Generation and Verification [Informatsiyni tekhnolohiyi. Kryptohrafichnyy zakhyst informatsiyi. Tsyfrovyy pidpys, shcho gruntuyet'sya na eliptychnykh kryvykh. Formuvannya ta pereviryannya], Derzhavnyy komitet Ukrayiny z pytan' tekhnichnoho rehulyuvannya ta spozhyvchoyi polityky, Kiyv, Ukraine, 2003 (In Ukrainian).

3. DSTU ISO/IEC 15946-1:2015 Information technology - Security techniques -Cryptographic techniques based on elliptic curves -Part 1: General [DSTU ISO/IEC 15946-1:2015Informatsiini tekhnolohii. Metody zakhystu.Kryptohrafichni metody, shcho gruntuiutsia naeliptychnykh kryvykh. Chastyna 1. Zahalnipolozhennia], Kiyv, Ukraine, 2016 (In Ukrainian).

4.De Feo, L. (2011), Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. PQCrypto. – 24 p.

5.Cherkaskyi, M. V. (2001), SH-model ofthe algorithm [SH-model alhorytmu] // Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, Lviv, Ukraine, vol. 433, pp. 127–134 (In Ukrainian).

6.Cherkaskyi, M. V., Khusein KhalidMurad (2004). Universal SH-model [Universalna SH-model] // Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, vol. 523, pp. 150–154 (In Ukrainian).

7.Hlukhov, V. S., Hlukhova, O. V. (2013),Structural Complexity of Galois Field Elements Multipliers Evaluation Results [Rezul'taty otsinky strukturnoyi skladnosti pomnozhuvachiv elementiv poliv Halua], Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, Lviv, Ukraine, vol. 773, pp. 27–32 (In Ukrainian).

8.Hlukhov, V. S., Trishch, H. M. (2014),Evaluation of structural complexity of multisection multiplier for Galois field elements [Otsinka strukturnoyi skladnosti bahatosektsiynykh pomnozhuvachiv elementiv poliv Halua], Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, Lviv, Ukraine, vol. 806, pp. 27–33 (In Ukrainian).

9.Hlukhova, O. V., Lozynskyi, A. Ya.,Yaremkevych, R. I., Ihnatovych, A. O. (2015), 99
ISSN 2221-3805. Електротехнічні та комп’ютерні системи. 2018. № 29 (105)
Захист iнформацiї у комп'ютерних системах
Analytical evaluation of Galois field elements multipliers structural complexity [Analitychna otsinka strukturnoi skladnosti pomnozhuvachiv elementiv poliv Halua], Materialy V Vseukrainskoi shkoly-seminaru molodykh vchenykh i studentiv. Suchasni kompiuterni informatsiini tekhnolohii. ACIT’2015, 22-23 may 2015 year. Ternopil. Ukraine. TNEU. Pp. 166–167 (In Ukrainian).

10.Elias, R., Rakhma, M., Hlukhov, V.(2017), Structural complexity of multipliers for Calois fields elements in normal and polynomial bases [Strukturna skladnist pomnozhuvachiv elementiv poliv Halua u normalnomu ta polinomialnomu bazysakh]. Elektrotehnicheskie i kompyuternyie sistemy, Odessa, Ukraine, № 25 (101), pp. 324–331 (In Ukrainian).

11.Sholohon, O. Z. (2014), StructuralComplexity of Galois Field GF(2m) Elements Multipliers in Polynomial Basis Calculation [Obchyslennya strukturnoyi skladnosti pomnozhuvachiv u polinomial'nomubazysi elementiv poliv Halua GF(2m)], Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, Lviv, Ukraine, vol. 806, pp. 284–289 (In Ukrainian).

12.Sholohon, Yu. Z. (2014), Based onElementary Transducers Structural Complexity of Galois Field Multipliers Evaluation [Otsinyuvannya strukturnoyi skladnosti pomnozhuvachiv poliv Halua na osnovi elementarnykh peretvoryuvachiv], Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika” “Komp"yuterni systemy ta merezhi”, Lviv, Ukraine, vol. 806, pp. 290–295 (In Ukrainian).

13.Hlukhov, V. S. (2007), Comparison ofpolynomial and normal bases of Galois fields elements presentation [Porivnyannya polinomial"noho ta normal"noho bazysiv predstavlennya elementiv poliv Halua, Visnyk Natsionalnoho universytetu «Lvivska politekhnika» “Komp’yuterni systemy proektuvannya. Teoriya i praktyka”, Lviv, Ukraine, vol. 591, pp. 22–27 (In Ukrainian).

14.Hlukhov, V. S. (2008), Estimation ofhardware costs for implementation of multilevel computer system [Otsinka aparatnykh vytrat na realizatsiiu bahatorivnevoi kompiuternoi systemy] // Visnyk Natsionalnoho universytetu «Lvivska politekhnika» “Kompiuterni nauky ta informatsiini tekhnolohii” Lviv, Ukraine, vol. 629, pp. 13–20 (In Ukrainian).

15.Zholubak, I. M., Hlukhov, V. S. (2016),Definition of the extended Galois field GF(dm) with multiplier minimal hardware complexity [Vyznachennia rozshyrenoho polia Halua GF(dm) z naimenshoiu aparatnoiu skladnistiu pomnozhuvacha], Visnyk Natsionalnoho universytetu «Lvivska politekhnika» “Informatsiini systemy ta merezhi”, vol. 854. Lviv, Ukraine, Pp. 63–69 (In Ukrainian).

16.Hlukhov, V., Elias, R., Rahma, M. (2016),The time complexity of based on modified Guild cells and oriented on cryptographic transformations in cyberphysical systems multipliers [Chasova skladnist oriientovanykh na vykonannia kryptohrafichnykh peretvoren v skladi kiberfizychnykh system pomnozhuvachiv na osnovi modyfikovanykh komirok Hilda]. Materialy druhoho naukovoho seminaru Kiber-fizychni systemy: dosiahnennia ta vyklyky, Lviv, Natsionalnyi universytet «Lvivska politekhnika», 21-22 chervnia 2016 r, pp. 36–42 (In Ukrainian).

17.Elias, R., Rahma, M., Hlukhov, V. (2016),Multipliers for Galois fields time complexity [Chasova skladnist' pomnozhuvachiv dlya poliv Halua], Elektrotehnicheskie i kompyuternyie sistemy, Odessa, Ukraine, № 22 (98), pp. 323–327 (In Ukrainian).

18.Rahma, M. K., Hlukhov, V. S. (2016),Time complexity of multipliers for Galois fields. INTERNATIONAL YOUTH SCIENCE FORUM ”LITTERIS ET ARTIBUS”, 24-26 NOVEMBER 2016, LVIV, UKRAINE. Proceedings, pp. 52–53.
Published:
Last download:
20 Sept 2019

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2014-2018. Any use of information from the site is possible only under the condition that the source link! ]