-

Automation System for Configuration of Cryptographic Data Protection Unit Model

0 Lviv Polytechnic National University , St. Bandera Str. 12, Lviv, 79013 , Ukraine

1833

0000 0001

Elliptic curves are mathematical basis for digital signature processing. In this case, the processing of the elliptic curve points is based on the operations in the Galois fields GF(pm). Comparison of multipliers' hardware costs for Galois fields with different characteristics p is carried out in the work. The multipliers are intended for use as part of the cryptographic data protection system that is implemented on the FPGA. VHDL-descriptions of multipliers (cores) were created with the help of the developed core generator. It was found that hardware multipliers that process elements of the fields with characteristics 2, 3 and 7 ) and with approximately equal order and the representation of these elements in a polynomial basis have a lower hardware complexity than multipliers for Galois fields with other characteristics. Software complexity of multipliers for Galois fields GF(pm) with approximately equal order and the representation of these elements in a polynomial basis is also investigated. It was found that software multipliers that process elements of fields with characteristics 3, 5 and 7 have a higher time complexity (software complexity) than multipliers for Galois fields with other characteristics.

Galois field GF(dm) multiplier modified Guild cell LUT core generator

In the implementation of algorithms for performing arithmetic operations in finite fields [ 9 ] or Galois fields GF(pm) a large number of arithmetic and logical operations must be performed. The implementation of complex computational algorithms at the level of logic elements is a common practice [ 6 ].

Currently, in the practice of cryptographic data protection, logical fields GF(2m) and simple fields GF(p) are used. Fields with the characteristic p > 2 - GF(pm) are not used extensively. In this paper, hardware and software complexity of multipliers for Galois field elements GF(pm) with different field characteristics p but with approximately the same order is compared.

In carrying out this work, on the basis of multiplier model proposed in [1 and 5] its implementation was carried out and the results of the hardware complexity estimation (previously obtained theoretically) was obtained It was shown that the hardware complexity will be the smallest for the fields with the characteristic 2.

In [ 1, 2 ] a theoretical comparison of the hardware complexity of the multipliers of Galois fields GF(pm) with different characteristics p was made. It was seen that multipliers for fields with characteristic 3 and 7 implemented on modern FPGAs that have logical blocks with 6 inputs and 1 output have the least hardware complexity. In [ 1 ] comparisons of Galois multipliers based on Modified Guild Cells (MGC) were considered. The MGC was considered to be an black box (read only memory, ROM) or a set of multiplier and adder [ 1 ]. In [ 2 ] estimation of hardware costs of Galois field multipliers in case when the MGC is consist of logical elements was made. The Galois field multiplier time complexity was also performed, advantage of Galois fields with field characteristics greater than 2 was shown and a comparison of the structural complexity [ 3 ] of the Galois fields GF(pm) multipliers for different field characteristic p was made.

The most common methods of hacking computer systems are software brute force method, that is, a simple override of keys that can be implemented on supercomputers or quantum computers. Well known hacking methods were taken into account in determining the vulnerability of cryptographic data protection systems that use Galois fields with different field characteristics to hacking. In [ 5 ] a comparison of software implementations of the Galois multipliers was made. Software realizations of the multiplier for Galois field elements GF(2m) are well known.

A multiplier core generator was developed to generate a multiplier for Galois fields with different characteristics and field orders. [ 4 ] describes methods for constructing of core generators.

The purpose of this work is to compare FPGA hardware and software costs of multipliers for Galois field with different characteristics, but approximately the same order. The codes of Galois fields elements are represented in a polynomial basis. 2

Hardware Implementation of Cryptographic Protection Units in FPGA To estimate the hardware costs of multipliers for various Galois fields, an automated system (core generator) for configuration of data protection unit models was developed.

The purpose of the system is to form a VHDL-description of a necessary unit with necessary characteristics. To accomplish this task, the generator uses the base configurable unit model in the form of its VHDL-description (template) [ 4 ].

The generator determines which parts of the base model will be needed for a selected unit and performs adjustment of corresponding parameters of each selected element of the base model. A word processor was developed for VHDL-code generation from the base model of the configured unit.

Configuration options include the type of unit, field characteristic p, and field order m.



The list of cells that can be generated includes modified Guild cells for the field with characteristic p, carry generation cells F, as well as the actual multiplier.

The word processor generates VHDL-description in accordance with the template, taking into account the parameters of the unit. The VHDL-generator of the Galois field multipliers implements 2 variants of the multipliers: in the first variant the MGC is treated as an integer component (black box, read only memory, ROM) and in the second variant the MGC consists of a multiplier and an adder.

The generator of VHDL-descriptions of multipliers consists of the following parts (Fig. 1):     module for inverter F creation; module for multiplier MUL and adder SUM creation; module for element MGC creation; module for creating and filling the matrix with F elements and the links between them; module for creating and filling the matrix with MGC elements and the links between them.

Creation boolean functions for element F Minimization of this functions Creation of element F Creation matrix of elements F Creation boolean functions for element SUM Minimization of this functions Creation of element SUM Creation matrix of elements MGC Filling matrix of elements and connections Creation boolean functions for element MUL Minimization of this functions Creation of element MUL Creation boolean functions for element MGC Minimization of this functions Creation of element MGC

The program modules which are responsible for creating the F and MGC elements for both cases use the common part of the program to minimize logical functions.

Intermediate results of the VHDL-descriptions generator are stored in files. This allows the user to see what changes occur with the function at each stage.

In Fig. 2 the internal structure of the MGC is presented in case of its implementation a) as a "black box" and b) as modular multiplier and adder, on the example of the multiplier for Galois Field GF(34).

In Fig. 3 the internal structure of generated multiplier for Galois Field GF(34) is presented. The inverter F performs operation B=(-A)modp. m Fig. 2. Implementation of MGC for Galois fields GF(3 ): a) as "black box" (BB); b) as “Multiplier plus Adder” (MA).

MGC_3 l(1:0) B(7:6) A(1:0) l(1:0) B(5:4) A(1:0) l(1:0) B(3:2) A(1:0) l(1:0) B(1:0) A(1:0) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) S(1:0)

S(1:0)

S(1:0) A(7:0) B(7:0) P(7:0) l(1:0)

R(7:0) l(1:0) B(7:6) A(5:4)

B(5:4) A(5:4)

B(3:2) A(5:4)

B(1:0) A(5:4) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) l(1:0) B(7:6) A(3:2)

B(5:4) A(3:2)

B(3:2) A(3:2)

B(1:0) A(3:2) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) S(1:0)

S(1:0)

S(1:0) l(1:0) B(7:6) A(7:6)

B(5:4) A(7:6)

B(3:2) A(7:6)

B(1:0) A(7:6) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) S(1:0)

U16

MGC_3 :(01A f :(01B ) U29 )

S(1:0)

S(1:0) P(7:6)

P(5:4)

P(3:2)

P(1:0) S(1:0) S(1:0)

U12 MGC_3

U15 MGC_3

U17

MGC_3 :(10A f :(10B ) U30 ) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) S(1:0)

S(1:0)

U2 MGC_3

U5 MGC_3

U24 MGC_3

U27

MGC_3 4 Fig. 3. Diagram of Galois Field GF(3 ) multiplier MUL (U1 – U16 – multiplier, U17 – U31 modulo convolution unit, divider) S(1:0) S(1:0)

U8 MGC_3

U11 MGC_3

U14 MGC_3

U18 MGC_3

U21

MGC_3 :(1A f :(01B )0 U31 ) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0) S(1:0)

S(1:0)

U10 MGC_3

S(1:0)

U4 MGC_3

U7 MGC_3

U13 MGC_3

U19 MGC_3

U22 MGC_3

U3 MGC_3

U6 MGC_3

U9 MGC_3

U20 MGC_3

U23

MGC_3 P(7:6)

P(5:4)

P(3:2)

P(1:0) P(7:6)

P(5:4)

P(3:2)

P(1:0) C(1:0) B(1:0) A(1:0)

C(1:0) B(1:0) A(1:0)

U25

MGC_3 S(1:0)

S(1:0)

U26

MGC_3 R(7:6)

R(5:4)

S(1:0) R(3:2)

S(1:0) R(1:0)

U28 MGC_3

In the first case, two logical functions S(1) and S(0) which depend on 6 variables (C(1:0), B(1:0), A(1:0)) are formed. The function S(1:0) forms the result of S = (A * B + C)mod3. In the second variant there are 4 logical functions, each of which depends on 4 variables, two of which form the result of multiplication F = A * Bmod3, and two others - result of adding S = (F + C) mod3.

The projects in this work were created and simulated in the Active-HDL 9.1 environment. The implementation was performed in the Xilinx ISE environment for

Spartan 6 FPGA.

The value of hardware costs and time delays for the implementation of the multipliers for GF(215), GF(39), GF(56), GF(75), GF(134) fields, which all have schemes similar to Fig. 3, are shown in Fig. 4 and Table 1.

With the graphics of Fig. 4, it can be seen that multiplier for GF(215) has the smallest hardware cost. Multipliers for field GF(215) has also the smallest time delays. It should also be noted that the multipliers for GF(39), GF(75) have hardware and performance rates, which are somewhat higher than logical fields multipliers.

Software Implementation of Cryptographic Data Protection Units

Software Complexity.

The hacking of cryptographic cipher on the basis of elliptic curves is mostly realized by the method of "brute force". To assess the stability of the cipher to breakdown, it is necessary to analyze the software complexity of arithmetic operations in the Galois fields. The most complicated arithmetic operation in the Galois fields GF(pm) is multiplication. For analysis, it was assumed that the multiplication operation is performed on a matrix multiplier. Matrix multiplier consists of modified Guild cells. The modified Guild cell can be considered either as a holistic element or as a set of multipliers and adder both by the modulus of the characteristic p of the field. The software complexity of multipliers in different Galois fields will be determined by the number of logical operations that must be performed to calculate 1 bit of the result.

Field MGS MGC Number Number of Number of Number max as number of GF LUTs in slices in of inputs delay, elements, multipliers multipliers and ns

% outputs GF(215) BB 435 101,3% 218 82 61 22 GF(215) MA 435 101,3% 205 86 61 26 GF(39) BB 153 96,5% 312 138 74 31 GF(39) MA 153 96,5% 298 106 74 47 GF(56) BB 66 89,6% 1946 600 75 49 GF(56) MA 66 89,6% 439 171 75 42 GF(75) BB 45 95,4% 2534 963 63 37 GF(75) MA 45 95,4% 258 103 63 31 GF(134) BB 28 100% 7395 3031 68 42 GF(134) MA 28 100% 2949 1018 68 86 The Table 1 shows that the smallest hardware costs of the multiplier will be in the GF(215) field. Fields with characteristic 3 and 7 have higher hardware costs, respectively, of 45.36 and 25.85% for MGC as a multiplier and adder

Table 2 shows the number of logical operations that need to be performed to simulate one modified Guild cell for fields with different characteristics. For analysis, fields with approximately the same number of elements are taken. The values given in Table 2 are based on the results of the synthesis of the corresponding MGS created by the core generator of cryptographic data protection units.

To estimate the number of operations that need to be performed when modeling a MGC, its model is used in the form of a multiplier plus adder (consists of two ROMs, Fig. 2, b – the first mode of estimation). An option when the MGC is holistic element is not considered, since its software implementation needs in general more operations, as can be seen from Table 2.

Each of MGC’s two elements can be imagined as a ROM, so the hardware complexity OMCG(p) of the MGC is the volume of this two ROMs: OMCG(p) = 2V(p)=2*2ni*no, where ni  2log 2 p is ROM input bits number and no  log 2p is ROM output bits number.

2log p 2log 2p1 Then O ( p )  2 * 2  2  log p  2  log p.

MCG 2 2

The number NMGC of MGC in the Galois fields GF(pm) multiplier is NMGC(m) = m(2m-1). The full hardware complexity of the multiplier of the Galois field GF(pm) elements can be calculated as 2log 2p1 OMUL ( m, p )  OMCG ( p )N MGC ( m ) 2  log 2pm(2m - 1) . value shows total number of bits which have to be calculated during multiplication.

Table 3 shows the hardware complexity of GF(pm) multipliers.

This

OSW ( m, p )  NC  NV , where NC is number of processor cores; NV is the number of vectors that the processor core can handle [ 7 ]. This value shows how many Galois Field elements each core can handle at a time. The element code length must be equal or less then vector length VL  log 2p and NC  NV  m .

The number of vectors NV and their length VL in modern processors are given in Table 4 [ 8 ]. Results of software complexity estimation are shown in Table 3. This mode of software complexity estimation gives incorrect results especially in case of

Galois fields with big characteristics (Fig. 5).

NV 8 4 3 3 2 16 16 16 16 16

Software complexity 1244 325 29240 19320 91584

The software complexity of multiplication can also be estimated on the basis of arithmetic operations that can be performed in each MGC (the second mode of estimation). In one MGC, you must perform a multiplication, division, addition and re-division operation. This method can be implemented by the MGC for the Galois field. Each MGC will perform 4 arithmetic operations, which have their weight - the ratio of its execution time to execution time of logical operation. Take the weight of multiplication and division operation as 8, the weight of addition as 4. Thus, for the simulation of the work of the MGC, it is necessary to perform 4 arithmetic operations, which are equivalent to 28 logical operations. Estimation results are in Table 5 and in Fig. 6. 3.4

The Third Method of Software Complexity Estimation.

An estimation of software complexity of the multiplier on the basis of logical operations used for multiplication, division, addition is described below (the third estimation method). To estimate the complexity of the multiplier it is necessary to calculate the complexity of the MGC. It performs Nbpm= log 2p bit-parallel multiplication operations, Nbprm= log 2p bit-parallel operations of reduction in modulus after multiplication (long division), Na=1 serial addition operation and Nbpra=1 bit-parallel operations of reduction in modulus after addition (short division). If we take that bit-parallel and serial operation have the same execution time then the complexity of the MGC can be estimated as total quantity Nbps of such operations Nbps = Nbpm + Nbprm + Na + Nbpra = = 2log 2 p  2  2( log 2 p  1 ) . The scheme of the multiplier and divider is shown in Fig. 3. In general, for the implementation of the MGC, it is necessary to perform Nlo = 4  2( log 2 p  1 )  8( log 2 p  1 ) logical operations, since we take that each multiplier and divider performs approximately 4 logical operations, for the implementation of a field with a characteristic of no more than W (where W is width of processor data bus), and NLO  8( log 2p  1 )log 2p / W  for a field with any other characteristic. MGC number is NMGC=m(2m-1). The formula for estimating the number of logical operations that is used to multiply 2 elements of a field: NLOM  8( log 2p  1 )log 2pm( 2m  1 ) / W  . Estimation results are in Table 6 and in Fig. 6. The obtained results show that the modeling of the multiplier of the Galois field elements is better by the method of logical operations.

The software complexity of multiplier for a field with a small characteristics is the largest. That is, it will be harder to crack them.

At the same time, the analysis of hardware implementation of multipliers shows that the hardware complexity of multipliers for fields with characteristics 2, 3 and 7 is the smallest.

Thus, the use of hardware multipliers in Galois fields with characteristics 2, 3, and 7 provides the best hardware parameters and complicates the task of modeling their work by hackers.

Conclusion An automated system for configuring VHDL-descriptions of cryptographic data protection units has been developed. With its help, a family of multipliers of the Galois field elements was generated for the Galois fields with field characteristics 2, 3, 5 7, 13 and a hardware cost analysis for their implementation on the FPGA of was performed. An analysis of the results of multiplier implementation has shown that the least hardware costs will be in multipliers of the Galois fields with the field characteristic 2. It is also shown that extended fields with approximately the same number of elements and small characteristics have low hardware and high software complexity. 6

Zholubak ,

Hlukhov . Determination of the extended Galois field GF(dm) with the smallest hardware complexity of the multiplier // Bulletin of the National Polytechnic University “Information systems and network” ”. - Lviv : - 2016 . - № 835. - P. 50 - 58 .

Zholubak ,

Hlukhov . Hardware costs of Galois multipliers GF(dm) with a large characteristic // Bulletin of the National Polytechnic University “Computer sciences and information technology” ”. - Lviv : - 2017 .

3. Cherkasky

М.

, Tkachuk

. І. Characteristics of the complexity of multiplication devices // Radioelectronic and computer systems . - 2012. - № 5. P. 142 - 147 .

4. Melnik

А.

, Melnik

. Personal supercomputers . Monograph. Lviv: Lviv Polytechnic Publishing House , 2013 . 516 p.

Zholubak ,

Hlukhov . Implementation of high-order Galois multipliers in FPGA // Bulletin of the National Polytechnic University “Computer systems and network”. - Lviv : - 2017 . - № 881. - З. 41 - 47 .

6. Palagin

The structure of FPGA-based cyclic-code converters / Alexander Palagin , Vladimir Opanasenko, Sergey Krivoi // Optical Memory & Neural Networks (Information Optics) . Springer. - 2013 , Vol. 22 , N. 4 . - PP. 207 - 216 .

7. Pawliczek

, Dzwinel

, Yuen

D.A.

( 2015 ) Visual Exploration of Data with Multithread MIC Computer Architectures . In: Rutkowski L., Korytkowski

, Scherer

, Tadeusiewicz

, Zadeh

, Zurada

. (eds) Artificial Intelligence and Soft Computing. ICAISC 2015. Lecture Notes in Computer Science , vol 9120 . Springer, Cham

Stephen

Vassyl

Dimitrov , Kimmo Järvinen, "Another Look at Inversions over Binary Fields" in Computer Arithmetic (ARITH), 2013 21st

IEEE

Symposium , Austin, TX, USA, 2013 .