Currently, elliptic curves are the mathematical basis for digital signature processing. Elliptic curve points processing is based on the performance of operations in Galois field GF(2m) in normal or polynomial bases. Characteristics of multipliers for these bases are different. In this paper, the time complexity of software multipliers for binary Galois fields GF(2m) and fields GF(dn) was investigated. Fields with approximately the same number of elements were investigated. Elements of these fields were represented in a polynomial basis. It is established that the Galois field GF(3т) provides the greatest time complexity of software multiplication, and the prime Galois field GF(P) has the least time complexity. It is also shown that the use of polynomial basis allows, in contrast to the normal basis, to realize larger part of multiplier on FPGA chip.
[1] DSTU 4145-2002. Informatsiyni tekhnolohiyi. Kryptohrafichnyy zakhyst informatsiyi. Tsyfrovyy pidpys, shcho gruntuyet'sya na eliptychnykh kryvykh. Formuvannya ta pereviryannya [Information Technology. Cryptographic Techniques. Digital Signatures Based on Elliptic Curves. Generation and Verification]. Derzhavnyy komitet Ukrayiny z pytan' tekhnichnoho rehulyuvannya ta spozhyvchoyi polityky, Kiyv, Ukraine, 2003 (In Ukrainian).
[2] Hlukhov V. S. Porivnyannya polinomial"noho ta normal"noho bazysiv predstavlennya elementiv poliv Halua. [Comparison of polynomial and normal bases of Galois fields elements presentation.]. Visnyk Nacional"noho universytetu "L"vivs"ka politexnika" "Komp'yuterni systemy proektuvannya. Teoriya i praktyka". Vol. 591, Lviv, Ukraine, 2007, pp. 22-27.
[3] H. H. Guild. Fully iterative fast array for binary multiplication and addition. Electronics Letters, Vol. 5, Issue 12, 12 June1969, рр. 263 (In English).
https://doi.org/10.1049/el:19690201
[4] V. S. Hlukhov, R. M. Elias, A. O. Mel'nyk. Osoblyvosti realizatsiyi na PLIS sektsiynykh pomnozhuvachiv elementiv poliv Halua GF(2m) z nadvelykym stepenem [Features of the FPGAbased Galois Field GF(2m) Elements Sectional Multipliers with Extra Large Exponent]. Komp'yuterno-intehrovani tekhnolohiyi: osvita, nauka, vyrobnytstvo - naukovyy zhurnal, Luts'kyy natsional'nyy tekhnichnyy universytet. Luts'k, Ukraine, 2013, Vol. 12, pp. 103-106 (In Ukrainian).
[5] Hlukhov V.S., Hlukhova O.V. Rezul'taty otsinky strukturnoyi skladnosti pomnozhuvachiv elementiv poliv Halua [Structural Complexity of Galois Field Elements Multipliers Evaluation Results]. Visnyk Natsional'noho universytetu "L'vivs'ka politekhnika" "Komp'yuterni systemy ta merezhi". Lviv, Ukraine, 2013, Vol. 773, pp. 27-32 (In Ukrainian).
[6] Hlukhov V. S., Trishch H. M. Otsinka strukturnoyi skladnosti bahatosektsiynykh pomnozhuvachiv elementiv poliv Halua [Evaluation of structural complexity of multisection multiplier for Galois field elements]. Visnyk Natsional'noho universytetu "L'vivs'ka politekhnika" "Komp"yuterni systemy ta merezhi". Lviv, Ukraine, 2014, Vol. 806, pp. 27-33 (In Ukrainian).
[7] Sholohon O. Z. Obchyslennya strukturnoyi skladnosti pomnozhuvachiv u polinomial'nomu bazysi elementiv poliv Halua GF(2m) [Structural Complexity of Galois Field GF(2m) Elements Multipliers in Polynomial Basis Calculation]. Visnyk Natsional'noho universytetu "L'vivs'ka politekhnika" "Komp'yuterni systemy ta merezhi". Lviv, Ukraine, 2014, Vol. 806, pp. 284-289 (In Ukrainian).
[8] Sholohon Yu. Z. Otsinyuvannya strukturnoyi skladnosti pomnozhuvachiv poliv Halua na osnovi elementarnykh peretvoryuvachiv [Based on Elementary Transducers Structural Complexity of Galois Field Multipliers Evaluation]. Visnyk Natsional'noho universytetu "L'vivs'ka politekhnika" "Komp'yuterni systemy ta merezhi". Lviv, Ukraine, 2014, Vol. 806, pp. 290-295 (In Ukrainian).
[9] Hlukhova O. V., Lozynskyi A. Ya., Yaremkevych R. I., Ihnatovych A. O. Analitychna otsinka strukturnoi skladnosti pomnozhuvachiv elementiv poliv Halua. [Analytical evaluation of Galois field elements multipliers structural complexity]. Materialy V Vseukrainskoi shkoly-seminaru molodykh vchenykh i studentiv. Suchasni kompiuterni informatsiini tekhnolohii. ACIT'2015. 22-23 may 2015 year. Ternopil. Ukraine. TNEU, 2015. - рp. 166-167 (In Ukrainian).
[10] Hlukhov V. S., Elias R. Umenshenie strukturnoy slozhnosti mnogosektsionnyih umnozhiteley elementov poley Galua [Galois Fields Elements Multisection Multipliers Structural Complexity Reduction]. Elektrotehnicheskie i kompyuternyie sistemyi. - 2015. - No. 19 (95). - pp. 222-226 (In Russian).
https://doi.org/10.15276/eltecs.19.95.2015.49
[11] M. Zholubak, A. T. Kostyk, V. S. Hlukhov. Osoblyvosti opratsyuvannya elementiv triykovykh poliv Halua na suchasniy elementniy bazieskye y komp'yuternыe systemы [Features of processing Binary Galois fields elements on modern hardware base]. Visnyk Natsional'noho universytetu "L'vivs'ka
politekhnika" "Komp'yuterni systemy ta merezhi". Lviv, Ukraine, 2015, Vol. 830, pp. 27-33 (In Ukrainian).
[12] Elias R., Rahma M., Hlukhov V. Multipliers for Galois fields time complexity. Elektrotehnicheskie i kompyuternyie sistemyi. - 2016. - No. 22 (98) - pp. 323-327 (In Ukrainian).
https://doi.org/10.15276/eltecs.22.98.2016.55
[13] Zholubak I. M., Hlukhov V. S. Vyznachennia rozshyrenoho polia Halua GF(dm) z naimenshoiu aparatnoiu skladnistiu pomnozhuvacha [Definition of the extended Galois field GF(dm ) with multiplier minimal hardware complexity]. Visnyk Natsionalnoho universytetu «Lvivska politekhnika» "Informatsiini systemy ta merezhi"/ - Lviv, Ukraine, 2016. Vol. 854. - рp. 63-69 (In Ukrainian).
[14] Password cracking. https://en.wikipedia.org/wiki/Password_ cracking
[15] IEEE 1363-2000. Standard Specifications for Public-Key Cryptography. Copyright © 2000 IEEE. All rights reserved.
[16] Maple User Manual. Copyright © Maplesoft, a division of Waterloo Maple Inc. 2017
[17] V. S. Hlukhov, R. Elias, M. Rahma. Structural Complexity of Multipliers for Galouan Fields Elements in Normal and Polynomial Bases. Electrotechnic and Computer Systems. - Odessa, 2017. Astroprint. - No. 25(101). - рр. 324-331.
https://doi.org/10.15276/eltecs.25.101.2017.39