KR100564599B1 - Inverse calculation circuit, inverse calculation method, and storage medium encoded with computer-readable computer program code - Google Patents

Abstract

The present invention is a computer-readable recording medium having recorded thereon an inverse calculation circuit, an inverse calculation method, and a program for executing the inversion calculation method. The inverse calculating circuit includes a random number generator for generating a first random number and a second random number; And receiving a plurality of first bits representing a first element of a finite body as a first input, and receiving a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the And an inverter for outputting a plurality of third bits representing the inverse of the first element in response to a second random number. The first random number is a random number for preventing DPA, and the second random number is a random number for preventing a time attack.

Montgomery inverse algorithm, inverse

Description

An inverse calculation circuit, an inverse calculation method, and storage medium encoded with computer-readable computer program code, which records an inverse calculation circuit, an inverse calculation method, and a program for executing the inverse calculation method.

The detailed description of each drawing is provided in order to provide a thorough understanding of the drawings cited in the detailed description of the invention.

1 shows a block diagram of an inverse calculating circuit according to an embodiment of the present invention.

FIG. 2 shows a circuit diagram of the inverter shown in FIG. 1.

The present invention relates to a cryptographic application circuit, and more particularly, to the inverse calculation circuit, the inverse calculation method, and the inverse calculation method, which are resistant to a timing attack and a differential power analysis (DPA) attack. A computer readable recording medium having recorded a program.

Cryptography was originally used in the military and diplomatic fields for the purpose of securing the secrets of the state. And financial institutions used cryptography for Electronic Funds Transfer. Therefore, since cryptography has been widely used in the economic and financial fields, it has been widely used, such as authentication of identity, key management of digital keys, digital signature, and identity verification.

Decryption can also be done by neglecting decryption keys, predictability of passwords, or monitoring of keyboard input on the network. Here, decryption is not a method in which the decryption agent decrypts plain text using only the ciphertext (so-called bruteforce attack), but knows all the information about the system such as the type of algorithm used for encryption of the plaintext and the operating system used. If you do not know only the key used for encryption, it refers to the act of finding the key and decrypting the ciphertext into plain text.

Decryption techniques include Ciphertext Only Attack, Known Plaintext Attack, Chosen Plaintext Attack, Adaptive Chosen Plaintext Attack, and Time Attack. timing attack) and DPA (also known as power analysis attack).

Time attack refers to a method of determining whether a value of a specific bit is 0 or 1 by using operation execution time information of an encryption algorithm, and thus decrypting a cipher. The differential power analysis attack analyzes the amount of power used by the encryption algorithm according to the input bit value, and accordingly, refers to a method of decrypting the password by finding the bit value of the secret key.

Elliptic curve cryptography, defined in the binary finite field (GF (2 ⁿ )), is divided into cryptography using affine coordinates and cryptography using projective coordinates.

The affine coordinate system expresses the coordinates on the elliptic curve as (x, y), and the projective coordinate system expresses the coordinates on the elliptic curve as (X, Y, Z). Therefore, the relationship between the point on the elliptic curve of the affine coordinate system and the point on the elliptic curve of the projective coordinate system is expressed by Equation 1.

Operations on elliptic curves include addition and doubling operations. The addition operation is used when the two points to add are different, and the doubling operation is used when the two points to add are the same.

The equation in the affine coordinate system defined in the binary finite field GF (2 ⁿ ) is shown in Equation 2.

Add operation and doubling operations on the elliptic curve defined on the finite field (GF (2 ^n)), as shown in equation (2) is a finite field operation of the (GF (2 ⁿ⁾⁾ (i.e., add, square, multiplication and inverse Calculation). Table 1 shows the number and types of operations required for addition and doubling operations in each elliptic curve.

Type of operation  Number of operations Point addition 1I + 2M + 1S Point doubling 1I + 2M + 1S

Where I denotes the inverse calculation of the finite field ^{(GF (2 n)),} M denotes a multiplication in the finite field ^{(GF (2 n)),} S denotes the power of the finite field (GF (2 ^n)). Finite field (GF (2 ⁿ⁾⁾ addition is may be implemented by an exclusive-OR (bitwise XOR) between the bit and the finite field (GF (2 ⁿ⁾⁾ as finite field (GF (2 ⁿ⁾ to implement the addition of the Since the computation speed of the addition of) is negligible, the addition of the finite field GF (2 ⁿ ) is excluded from Table 1.

Finite field calculate inverses of (GF (2 ⁿ⁾⁾ is a finite field is a calculation takes up a large share of the elliptic curve cryptography, compared to the product of the multiplier and the finite field (GF (2 ⁿ⁾⁾ of the (GF (2 ⁿ⁾⁾ . Therefore, in elliptic curve cryptography, calculations of projective coordinate systems are sometimes used that do not require inverse calculation.

However, if the addition and doubling operations in the elliptic curve using the affine coordinate system are vulnerable to side channel attack, the safety of the elliptic curve cryptography is reduced.

Therefore, the technical problem to be achieved by the present invention is to provide a reverse circuit calculation circuit resistant to time attack and differential power analysis attack.

The reverse source calculation circuit for achieving the technical problem comprises a random number generator for generating a first random number and a second random number; And receiving a plurality of first bits representing a first element of a finite body as a first input, and receiving a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the And an inverter for outputting a plurality of third bits representing the inverse of the first element in response to a second random number.

The first random number is a random number for preventing DPA, and the second random number is a random number for preventing a time attack.

Inverter calculation method for achieving the technical problem comprises the steps of generating a first random number and a second random number; And receiving a plurality of first bits representing a first element of a finite body as a first input and receiving a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the And outputting a plurality of third bits representing the inverse of the first element in response to a second random number.

The computer-readable recording medium for achieving the technical problem is a step of generating a first random number and a second random number; And receiving a plurality of first bits representing a first element of a finite body as a first input, and receiving a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the A program for executing the step of outputting a plurality of third bits representing the inverse of the first element in response to a second random number is recorded.

Preferably, the first random number is generated later than the second random number. The first random number is composed of 2 bits, the second random number has a value larger than 2n and smaller than 3n, and n is an order of finite field.

When the plurality of first bits and the plurality of third bits are composed of n bits, the plurality of second bits may be configured of (n + 1) bits.

In order to fully understand the present invention, the operational advantages of the present invention, and the objects achieved by the practice of the present invention, reference should be made to the accompanying drawings which illustrate preferred embodiments of the present invention and the contents described in the accompanying drawings.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Like reference numerals in the drawings denote like elements.

Montgomery inverse algorithm in the finite body (GF (2 ⁿ )) presented by E. Savas, CK Koc, entitled "Architectures for unified field inversion with application in elliptic curve cryptography" at The 9th IEEE Internal Conference on Electronics, Circuit and System. Montgomery inverse algorithm is as follows.

Input : a (x) and p (x), where deg (a (x)) <deg (p (x))

Output : r (x) and k, where r = a (x) ^-1 x ^k (mod p (x))

and deg (a (x)) ≤ k ≤ deg (p (x)) + deg (a (x)) + 1

1: u (x): = p (x), v (x): = a (x), r (x): = 0, and s (x): = 1

2: k: = 0

3: while (v (x)! = 0)

4: if u (0) = 0 then u (x): = u (x) / x, s (x): = xs (x)

5: else if v (0) = 0 then v (x): = v (x) / x, r (x): = xr (x)

6: else if deg (u (x))> deg (v (x)) then

u (x): = (u (x) + v (x)) / x

r (x): = r (x) + s (x)

s (x): = xs (x)

7: else v (x): = (v (x) + u (x)) / x

s (x): = s (x) + r (x)

r (x): = xr (x)

8: k: = k + 1

9: if deg (r (x)) = deg (p (x)) then r (x): = r (x) + p (x)

10: return r (x) and k

Where a (x) is an element of finite body (GF (2 ⁿ )) and a (n-1) order polynomial. Also, p (x) is an n th order polynomial for modular operation. r (x) is the inverse of a (x) and is the (n-1) order polynomial. Here, the order of a (x) deg (a (x)) is smaller than the order of p (x) deg (p (x)). The Montgomery inverse algorithm calculates a (x) ^-1 x ^k for element a (x) of the finite field GF (2 ⁿ ). The condition of k is as follows.

deg (a (x) ≤ k ≤ deg (p (x)) + deg (a (x)) + 1,

That is, when n is the order of the finite body GF (2 ⁿ ), k ≦ 2n.

In the Montgomery inverse algorithm, the computation time and k for inverse calculation depend on the element a (x) of the finite field GF (2 ⁿ ). However, when repeatedly inputting elements a (x) of the same finite body (GF (2 ⁿ )) as an inverse calculation circuit implementing the Montgomery inverse algorithm, the calculation time for calculating the inverse of the element a (x) is determined. same. Thus, the inverse calculating circuit is vulnerable to time attack.

Therefore, the Montgomery algorithm (hereinafter referred to as 'the first Montgomery inverse algorithm') that improves the conventional Montgomery inverse algorithm to be resistant to time attack is as follows.

1.Input a (x) and p (x), where deg (a (x)) <deg (p (x))

U (x) ← p (x), v (x) ← a (x), r (x) ← 0, and s (x) ← 1

3.m ← random value, 2n ≤m ≤ 3n

While (k <m)

4.1 if (v (x) ≠ 0)

4.1.1 if (u ₀ ≠ 0) u (x) ← u (x) / x, s (x) ← xs (x)

4.1.2 else if (v ₀ ≠ 0) v (x) ← v (x) / x, r (x) ← xr (x)

4.1.3 else if (deg (u (x))> deg (v (x))) then

u (x) ← (u (x) + v (x)) / x

r (x) ← r (x) + s (x)

s (x) ← xs (x)

4.1.4 else v (x) ← (v (x) + u (x)) / x

s (x) ← s (x) + r (x)

r (x) ← xr (x)

4.2 else

4.2.1 if (r _n = 1) r (x) ← r (x) + p (x)

4.2.2 r (x) ← xr (x)

4.3 k ← k + 1

5.if (deg (r (x)) = deg (p (x))) r (x) ← r (x) + p (x)

6.OUTPUT r (x), k

The first Montgomery inverse algorithm (or hardware implementing the first Montgomery inverse algorithm) introduced a random number (m) in the Montgomery inverse algorithm. The range of random numbers (m) is any number between 2n and 3n. N is the order of the finite body (GF (2 ⁿ )).

The Montgomery inverse algorithm calculates inverses only for (v (x)! = 0). Further, the first Montgomery inverse algorithm performs step 4.1 when (v (x) ≠ 0), but performs step 4.2 when v (x) is zero.

Therefore, step 4.2 performs inverse calculation until the random number m defined in step 4 is obtained, so that the first Montgomery inverse algorithm uses elements of the same input (e.g., finite field GF ( ²ⁿ ) to obtain inverse sources). ), The time for calculating the inverse for the input is also different. Thus, the first Montgomery inverse algorithm is resistant to time attack.

In this Montgomery inverse algorithm, ^k of a (x) ^-1 x ^k is smaller than 2n, and ^m of a (x) ^-1 x ^m in the first Montgomery inverse algorithm is larger than 2n and smaller than 3n.

The relationship between a (x) ^-1 x ^k and a (x) ^-1 x ^m has the following relationship since step 4.2 is performed when step 4.1 is completed in the first Montgomery inverse algorithm.

a (x) ^-1 x ^m = a (x) ^-1 x ^k x ^(mk)

Thus, the first Montgomery inverse algorithm always performs step 4.1 before v (x) = 0. Thus, the first Montgomery inverse algorithm is vulnerable to DPA.

Therefore, the algorithm according to the embodiment of the present invention which improves the first Montgomery inverse algorithm to be resistant to time attack and DPA (hereinafter, referred to as a 'second Montgomery inverse algorithm') is as follows.

1.Input a (x) and p (x), where deg (a (x)) <deg (p (x))

U (x) ← p (x), v (x) ← a (x), r (x) ← 0, and s (x) ← 1

3.m ← random value, 2n ≤m ≤ 3n

While (k <m or v (x) ≠ 0)

4.1 R ← random value, 0 ≤ R ≤ 3

4.2 if (v (x) ≠ 0 and R ≠ 0)

4.2.1 if (u ₀ ≠ 0) u (x) ← u (x) / x, s (x) ← xs (x)

4.2.2 else if (v ₀ ≠ 0) v (x) ← v (x) / x, r (x) ← xr (x)

4.2.3 else if (deg (u (x))> deg (v (x))) then

u (x) ← (u (x) + v (x)) / x

r (x) ← r (x) + s (x)

s (x) ← xs (x)

4.2.4 else v (x) ← (v (x) + u (x)) / x

s (x) ← s (x) + r (x)

r (x) ← xr (x)

4.3 else

4.3.1 if (r _n = 1) r (x) ← r (x) + p (x)

4.3.2 r (x) ← xr (x)

4.3.3 if (s _n = 1) s (x) ← s (x) + p (x)

4.3.4 s (x) ← xs (x)

4.4 k ← k + 1

5.if (deg (r (x)) = deg (p (x))) r (x) ← r (x) + p (x)

6.OUTPUT r (x), k

In the second Montgomery inverse algorithm according to the present invention, a random number R is introduced. The random number R has a random value between 0 and 3 in every iteration. If v (x) is not zero and R is not zero, step 4.2 is performed. That is, if v (x) is not zero and R is zero, step 4.3 is performed. Thus, the second Montgomery inverse algorithm according to the present invention does not perform the same operation on the same input.

Since the random number R has a random value between 0 and 3, and step 4.3 is performed only when v (x) is not 0 and R is 0, step 4.3 is performed with a probability of 1/4. If only one random number R is selected from 0 and 1, steps 4.2 and 4.3 are performed with a probability of 1/2 respectively.

The inverse calculating circuit according to the present invention implements a second Montgomery inverse algorithm, which is described in detail with reference to FIGS. 1 and 2.

1 shows a block diagram of an inverse calculating circuit according to an embodiment of the present invention. Referring to FIG. 1, the inverse calculating circuit 100 includes an inverter 200 and a random number generator 400.

The random number generator 400 generates a first random number R and a second random number m. The first random number R is a random number for preventing DPA. Since the range of the first random number R generated by the random number generator according to the present invention is from 0 to 3, the value of the first random number R may be represented by 2 bits. However, the range of the first random number R according to the present invention is not limited to 0 to 3.

The second random number m is a random number for preventing a time attack. The second random number m has a value larger than 2n and smaller than 3n. Where n represents the order of the finite body (GF (2 ⁿ )).

The inverter 200 receives a (x) and p (x), and outputs r (x) in response to the first random number R and the second random number m. Where a (x) represents the element of the finite body (GF (2 ⁿ )) for which the inverse is to be obtained. a (x) is a (n-1) order polynomial and is represented by n bits.

p (x) is an nth order polynomial for modular operation, represented by (n + 1) bits. r (x) is the inverse of a (x), which is a (n-1) order polynomial, represented by n bits.

FIG. 2 shows a circuit diagram of the inverter shown in FIG. 1. The structure and operation of the inverter are described in detail with reference to FIG. 1, the second Montgomery inverse algorithm, and FIG. 2.

Each register 201, 203, 205, and 207 stores u (x), v (x), s (x), and r (x).

Each of the right shift registers 209, 211, and 213 receives input data, shifts the data one bit to the right, and stores zeros in each most significant bit (MSB). For example, when the data output from the register 201 is 00011, the right shift register 209 receives 00011 and outputs 00001.

However, the right shift register 215 receives the input data, shifts the data one bit to the right, and stores 1 in the MSB. Therefore, when the data output from the register 233 is 11000, the right shift register 215 receives 11000 and outputs 11100.

Each of the left shift registers 217, 219, 221, and 223 receives input data, shifts the data one bit to the left, and stores zero in each least significant bit (LSB).

The exclusive OR gates 225, 227, 231, and 229 perform an exclusive OR operation bitwise on two input data. For example, the exclusive OR gate 225 exclusively ORs the data output from the register 201 and the data output from the register 203 in units of bits.

The register 233 is a register for storing the order of the finite field GF (2 ⁿ ), and is set to 1000 ... 0 at the beginning of the operation. If u (x) is a finite body (GF (2 ⁿ )) and degU (x) is (degU _n , degU _n-1 , ..., degU ₁ , degU ₀ ), then degU _n = 1, degU _n-1 = degU ₁ = degU ₀ = 0. The AND circuit 235 receives the data output from the register 203 and the data output from the register 233, and logically multiplies them bit by bit.

The control logic unit 300 includes the LSB (u ₀ ) of the register 201, the LSB (v ₀ ) of the register 203, the MSB (r _n ) of the register 207, and the output signal of the AND product circuit 235. Generate control signals based on Each of the control signals is input to registers 201, 203, 205, and 207 corresponding to muxes 237, 239, 241, and 243. Each register 201, 203, 205, and 207 updates the stored data in response to a corresponding control signal.

2 is an implementation of the second Montgomery inverse algorithm, the circuit corresponding to each step is as follows.

Step 4.2.1 is implemented with registers 209 and mux 237, and registers 217 and mux 241. Step 4.2.2 is implemented with registers 213 and mux 239, and registers 219 and mux 243.

In step 4.2.3 u (x) ← (u (x) + v (x)) / x is implemented with an exclusive OR gate (XOR1; 225), right shift register (RSHT2; 211) and mux (MUX1; 237). R (x) ← r (x) + s (x) are implemented with an exclusive OR gate (XOR2; 227), and a mux (MUX4; 243), and s (x) ← x · s (x) is left It is implemented with a shift register 217 and a mux (MUX3) 241.

In step 4.2.4 v (x) ← (v (x) + u (x)) / x is implemented with an exclusive OR gate (XOR1; 225), right shift register 211 and mux (MUX2; 239), s (x) ← s (x) + r (x) are implemented with exclusive OR gates (XOR2; 227) and mux (MUX3; 241), and r (x) ← xr (x) is the left shift register ( 219) and MUX4; 243.

Steps 4.3.1 and 4.3.2 are implemented with XOR3 231, left shift register 219, left shift register 221 and mux 243.

Steps 4.3.3 and 4.3.4 are implemented with a left shift register 217, a left shift register 223 and a mux 241.

In step 4.2.3, deg (u (x))> deg (v (x)) is implemented by the register 233 and the AND circuit 235 as follows.

At the start of the operation, the data stored in register 233 is 100 ... 0. U (x) ← (u (x) + v (x)) / x in step 4.2.1 or step 4.2.3 is performed, and the order of u (x) each time data stored in the register 201 is updated Decreases. Each time the order is reduced, the register 233 receives and stores data output from the register 215. At this time, when the order of u (x) is greater than the order of v (x), the data stored in the OR circuit 235 is 000 ,,, 0.

For example, assuming that the data initially stored in the register 233 in the finite field GF (2 ⁴ ) is (10000) and v (x) is (00111), the order of v (x) is secondary.

If step 4.2.1 is performed and the data stored in the register 201 is updated, the order of u (x) is cubic. At this time, the data of the register 233 becomes (11000). If the AND is performed by the AND circuit 235, the result is (00000). In this case u (x) is substantially cubic and v (x) is quadratic.

If step 4.2.1 is performed again, u (x) becomes secondary and 11100 is stored in register 233. At this time, the logical product circuit 235 is stored (00100). The control logic unit 300 performs step 4.2.4 using the stored information. The inverse calculating circuit according to the present invention can be used in an encryption device such as a smart card.

Although the present invention has been described with reference to one embodiment shown in the drawings, this is merely exemplary, and those skilled in the art will understand that various modifications and equivalent other embodiments are possible therefrom. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

As described above, the computer-readable recording medium that records the inverse calculating circuit, the inverse calculating method, and the program for executing the method according to the present invention is resistant to time attack and differential power analysis attack.

Claims (11)

In the inverse calculation circuit, A random number generator for generating a first random number and a second random number; And Receive a plurality of first bits representing a first element of a finite body as a first input, and receive a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the first And an inverter for outputting a plurality of third bits representing the inverse of the first element in response to the random number. The inverse calculation circuit of claim 1, wherein the first random number is generated later than the second random number. The inverse calculating circuit according to claim 1, wherein the first random number is composed of two bits. 2. The inverse calculating circuit according to claim 1, wherein the second random number has a value larger than 2n and smaller than 3n, and n is an order of a finite body. The inverse calculating circuit of claim 1, wherein when the plurality of first bits and the plurality of third bits comprise n bits, the plurality of second bits comprise (n + 1) bits. In the inverse calculation method, Generating a first random number and a second random number; And Receive a plurality of first bits representing a first element of a finite body as a first input, and receive a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the first And outputting a plurality of third bits representing the inverse of the first element in response to the random number. In a computer-readable recording medium, Generating a first random number and a second random number; And Receive a plurality of first bits representing a first element of a finite body as a first input, and receive a plurality of second bits representing a second element of a finite body as a second input, wherein the first random number and the first 2. A computer readable recording medium having recorded thereon a program for executing a step of outputting a plurality of third bits representing the inverse of the first element in response to a random number. 8. The computer-readable recording medium of claim 7, wherein the first random number is generated later than the second random number. 8. The computer-readable recording medium of claim 7, wherein the first random number consists of two bits. 8. The computer-readable recording medium of claim 7, wherein the second random number has a value greater than 2n and less than 3n, and n is a finite order. 8. The computer-readable device of claim 7, wherein when the plurality of first bits and the plurality of third bits comprise n bits, the plurality of second bits comprise (n + 1) bits. 9. Recording media.

Images