KR101817879B1 - Device and method for high-speed non-adjacent form conversion - Google Patents

Abstract

The present invention relates to a high-speed NAF conversion apparatus and a high-speed NAF conversion method. The high-speed NAF conversion apparatus according to the present invention is characterized in that a window having the set value as a length is divided into at least a part of the public key by a setting unit for setting a window value and a LSB (Least Significant Bit) Bit right shift (when the target bit to be encrypted in the public key is outside the window, the target bit is shifted to a right-shifted direction And a processing unit for setting the window to the second setting.

Description

TECHNICAL FIELD [0001] The present invention relates to a high-speed NAF conversion apparatus and a high-speed NAF conversion apparatus,

The present invention relates to a high-speed NAF conversion apparatus and a high-speed NAF conversion method.

The secret key cryptosystem in the prior art is highly likely to leak out to the encryption key by encrypting and decrypting using one encryption key. On the other hand, the public key cryptosystem uses a public key and a secret key to encrypt, thereby assuring stability of the key exchange and providing high security strength. Typical public key cryptosystems in the prior art are RSA (Rivest, Shamir, Adleman) and ECC (Elliptic Curve Cryptography).

는 소수이고,

는

이며,

이다(비밀키=

, 공개키=

). 만일, 공개키가 {7, 187}이고, 비밀키가 {23, 17, 11}일 때 메시지

이라면, 암호화된 메시지

는

가 되고,

를 복호화하면

이므로 처음 메시지

가 구해질 수 있다. 이 때,

과

을 구하고

을 계산하는 것은 아주 많은 연산을 요구할 수 있다.First, RSA is an algorithm based on the difficulty of subdivision decomposition. The public key and secret key can be obtained by multiplying two prime numbers and performing additional operations. In other words, RSA uses modular exponentiation in encryption and decryption as a core function. For example, in the case of RSA,

Is a prime number,

The

Lt;

(Secret key =

, Public key =

). If the public key is {7, 187} and the secret key is {23, 17, 11}

, The encrypted message

The

Lt; / RTI &

Decrypts

First message

Can be obtained. At this time,

and

And

Can require a great deal of computation.

 Since the computation has a great influence on the speed of the RSA, various studies have been conducted on the optimization of the modular multiplication and the optimization of the modular multiplication frequency.

상에 정의된 타원곡선

에서의 이산로그문제에 기초한다. ECC는 핵심 기능으로 유한체

상에 정의된 타원곡선

위의 점

를 양의 정수

만큼 더한

를 계산하는 연산인 스칼라 곱셈을 사용한다. 스칼라 곱셈은 타원곡선 상의 점에 대한 연산인 포인트 더블링(point doubling) 연산과 포인트 에디션(point addition) 연산으로 구성되어 있다.Next, ECC is a public key cryptosystem based on elliptic curve theory,

Elliptic curve defined on

Based on the discrete log problem in ECC is a core function,

Elliptic curve defined on

Above point

Positive integer

As much as

Which is a computation for computing the scalar multiplication. Scalar multiplication consists of a point doubling operation and a point addition operation, which is an operation on a point on an elliptic curve.

At this time, the speed of the ECC may be greatly affected by the scalar multiplication operation speed. Therefore, in order to improve the speed of the ECC, research for improving the scalar multiplication operation speed is required.

SUMMARY OF THE INVENTION The present invention has been conceived to solve the above problems, and it is an object of the present invention to provide a non-additive form (NAF) conversion process for reducing the number of modular multiplications in the modular exponentiation operation of RSA and the number of point editions in scalar multiplication operation of ECC So that the speed can be improved.

In order to achieve the above-mentioned object, a high-speed NAF conversion apparatus includes a setting unit for setting a value of a window and a window having the length of the set value as a length, based on a LSB (Least Significant Bit) of a public key, Bit right shifting (? -Bit right shift) so that the target bit is included if the target bit to be encrypted in the public key is outside the window And the processing unit for setting the window to the second setting.

According to another aspect of the present invention, there is provided a high-speed NAF conversion method comprising: setting a value of a window; setting a window having the set value as a length based on an LSB (Least Significant Bit) Bit key to the left of the window so that the target bit is included in the target key when the target bit to be encrypted in the public key is outside the window, and a step of setting the window to the second state by setting the ω-bit right shift (ω is a natural number).

According to an embodiment of the present invention, the speed of the NAF conversion process can be improved so as to reduce the number of modular multiplications in the modular exponentiation operation of the RSA and the number of point editions in the scalar multiplication operation of the ECC.

번의 비교 연산 과정을 수행함으로써,

번의 비트 비교 연산 과정을 수행하는

알고리즘의 연산 처리 속도를 최적화 할 수 있다(

은 양의 정수

의 이진수 변환에 따른 비트 수,

는 윈도우 크기).Further, according to an embodiment of the present invention,

By performing the comparison operation of the number of times,

Bit comparison operation

It is possible to optimize the processing speed of the algorithm (

Is a positive integer

The number of bits according to the binary conversion,

Window size).

(

은 양의 정수

의 이진수 변환에 따른 비트 수)이 증가하거나 홀수인 경우를 발생시키는 패턴이 많이 존재하는 경우에 NAF 변환 시간을 단축할 수 있다.Further, according to an embodiment of the present invention, in NAF conversion,

(

Is a positive integer

The number of bits in accordance with the binary conversion of the number of bits) increases or the number of patterns that generate an odd number is large, the NAF conversion time can be shortened.

FIGS. 1A to 1F are diagrams for explaining an algorithm used in RSA or ECC according to an embodiment of the present invention.
2 is a block diagram showing a high-speed NAF conversion apparatus according to an embodiment of the present invention.
3 is a view for explaining an implementation example using a high-speed NAF conversion apparatus according to an embodiment of the present invention.
4 is a view for explaining an implementation example using a high-speed NAF conversion apparatus according to an embodiment of the present invention.
5 is a diagram illustrating an algorithm for implementing a high-speed NAF conversion apparatus according to an embodiment of the present invention.
FIGS. 6 to 11 are diagrams for explaining performance evaluation of an algorithm for implementing a high-speed NAF conversion apparatus according to an embodiment of the present invention.
12 is a workflow diagram specifically illustrating a high-speed NAF conversion method according to an embodiment of the present invention.

Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings. However, the present invention is not limited to or limited by the embodiments. Like reference symbols in the drawings denote like elements.

에 대한 NAF(

) 변환 과정의 속도를 향상시킬 수 있다.The high-speed NAF conversion apparatus and the high-speed NAF conversion method described in this specification are based on a positive integer which is essentially used in the modular exponentiation operation of RSA and the scalar multiplication operation of ECC.

NAF for

) The speed of the conversion process can be improved.

To facilitate understanding of the description on the specification, an algorithm used in RSA or ECC will be described with reference to FIGS. 1A through 1F.

FIGS. 1A to 1F are diagrams for explaining an algorithm used in RSA or ECC according to an embodiment of the present invention.

형태의 계산에 있어서, 종래에는

를 십진수로 표현하였지만, 도 1a의 (가)에 도시된 바와 같은, 제1 알고리즘은

형태의 이진수로 표현할 수 있다. 제1 알고리즘의 항목(1)에서,

는 0으로 초기화되어 알고리즘이 종료될 때는

값이 될 수 있으며,

는

값을 저장하는 변수일 수 있다. 항목(2)에서 확인할 수 있듯이, 스퀘어 앤드 멀티플라이 기법은

를

부터 0까지 감소시키며

의 각 비트(bit)들을 왼쪽-오른쪽(Left-to-Right) 방식으로 1-비트씩 이동(Shift)하며 확인할 수 있다. 이 때, 스퀘어 앤드 멀티플라이 기법은

연산을 수행하면서(항목(2.1)),

의

번째 비트인

가 1인 경우에는 추가적으로

과

연산을 수행할 수 있다(항목(2.2)). 따라서, 스퀘어 앤드 멀티플라이 기법은

에서 1의 개수를 줄인다면 모듈러 곱셈 연산 횟수를 줄일 수 있다. 도 1a의 (나)는 스퀘어 앤드 멀티플라이 기법을 이용한 연산 예를 나타내는 도면이다.1A is a diagram for explaining a Square and Multiply technique. 1a is a first algorithm for the square-and-multiply scheme, which may be an algorithm used to reduce the amount of computation in modular exponentiation of RSA.

In the calculation of the form, conventionally

Is represented by a decimal number, but the first algorithm, as shown in Fig. 1A (a)

It can be expressed as a binary number of the form. In item (1) of the first algorithm,

Is initialized to 0 and the algorithm is terminated

Value,

The

It can be a variable that stores a value. As can be seen in item (2), the square-and-

To

To 0

Bit by 1 bit in the left-to-right manner. At this time, the square-and-

While performing the operation (item (2.1)),

of

Th bit

1 < / RTI >

and

(Item 2.2). ≪ / RTI > Thus, the square-and-

The number of modular multiplication operations can be reduced. (B) of FIG. 1A is a diagram showing an operation example using a square-and-multiply technique.

를 계산하는 스칼라 곱셈에서 가장 일반적으로 사용될 수 있다. 도 1b에 도시된, 바이너리 기법을 위한 제2 알고리즘의 항목(1)에 나타낸 바와 같이, 바이너리 기법은

의 각 비트들을 왼쪽-오른쪽(Left-to-Right) 또는 오른쪽-왼쪽(Right-to-Left) 방식으로 1-비트씩 이동하며 확인할 수 있다. 이 때, 바이너리 기법은 항목(2.1)과 같이 각 비트마다 한 번의 포인트 더블링(point doubling) 연산을 수행할 수 있다. 비트가 0이 아닌 경우, 바이너리 기법은 항목(2.2)와 같이 추가적인 포인트 에디션(point addition) 연산을 수행하도록 0이 아닌 비트의 수만큼 포인트 에디션 연산을 수행할 수 있다. 따라서, 바이너리 기법은

에서 1의 개수를 줄인다면 스칼라 곱셈 연산 속도를 향상시킬 수 있다. 1B is a diagram for explaining a binary technique. Binary technique is ECC

Can be most commonly used in scalar multiplication. As shown in item (1) of the second algorithm for the binary technique shown in FIG. 1B, the binary technique

Bit by bit in the left-to-right or right-to-left manner. At this time, the binary technique can perform a point doubling operation for each bit as shown in the item (2.1). If the bit is non-zero, the binary scheme may perform a point edition operation on the number of non-zero bits to perform an additional point addition operation, as in item (2.2). Thus, the binary technique

The number of scalar multiplication operations can be improved by decreasing the number of 1's.

일 때, 7P = 2(2(P)+P)+P 일 수 있고,

일 때, 6P = 2(2(P)+P) 일 수 있다.To illustrate an example of a binary technique,

(2 (P) + P) + P, < / RTI >

6P = 2 (2 (P) + P).

에서 0이 아닌 비트의 수가 많을수록 모듈러 곱셈 연산, 포인트 에디션 연산 횟수가 증가할 수 있다.

알고리즘은

의 각 비트에 부호가 있는 숫자를 사용할 수 있다.

알고리즘은 0이 아닌 숫자가 연속된 부분을 제거하여

보다 0이 아닌 숫자의 평균 밀도를 감소시킴으로써, RSA의 모듈러 멱승 연산에서는 모듈러 곱셈의 횟수를 줄이기 위해서 사용될 수 있다. 또한,

알고리즘은 ECC의 스칼라 곱셈에서는 포인트 에디션 연산의 수를 줄이기 위해서 사용될 수 있다. 일반적으로 길이가

인

를

와 같이 표현할 수 있다. 이 때,

일 수 있다.1C is a diagram for explaining the NAF technique. The square-and-multiply technique for optimizing modular exponentiation of RSA and the binary technique for scalar multiplication of ECC

The number of modular multiplication operations and the number of point edition operations may increase as the number of non-zero bits increases.

The algorithm

A number with a sign can be used for each bit of.

The algorithm removes consecutive non-zero digits

By reducing the average density of nonzero numbers, RSA modular exponentiation can be used to reduce the number of modular multiplications. Also,

The algorithm can be used to reduce the number of point edition operations in ECC scalar multiplication. In general,

sign

To

As shown in Fig. At this time,

Lt; / RTI >

을

로 변환하는

알고리즘일 수 있다. 제3 알고리즘은 양의 정수

와 윈도우 크기(window size)인

를 입력 받아

의 이진 표현인

에서 0이 아닌 정수인 비트 수가 줄어들도록 변환한

를 반환할 수 있다. NAF 기법은 제3 알고리즘의 항목(2)와 같이,

조건을 만족하면 와일(While)문을 반복하여 수행할 수 있고,

가 홀수일 때(즉, LSB(Least Significant Bit)가 1일 때)

의 값은

가 되도록 할 수 있다(항목(2.1). 이 때, NAF 기법은 앞서 구한

가

보다 크거나 같으면

값은

가 되도록 하고, 그렇지 않을 경우에는 앞에서 구한 값을 사용할 수 있다(항목(2.1.1). 또한, NAF 기법은

에

를 빼줄 수 있다(항목(2.1.2)). 항목(2.2)에 나타낸 바와 같이,

가 짝수일 경우(즉, LSB가 0일 경우)

값은 0이 될 수 있다. 항목(2.3)에서, NAF 기법은

에서

는

값을 2로 나누는 수행을 할 수 있고, 이 과정이 오른쪽으로 1-비트 이동하는 동작일 수 있다. 예를 들어, 십진수 7을 이진수로 나타내면

이고, 7을 2로 나누면 실제로는 3.5이지만, 제3 알고리즘에서 변수

가 정수(Integer)로 선언되어있기 때문에

값은 소수점을 제외한 3이 되고, 이를 이진수로 나타내면

이 될 수 있다. 따라서, NAF 기법은 가장 오른쪽 비트를 없애고 모든 비트가 오른쪽으로 한 칸씩 이동하도록 할 수 있다. NAF 기법은

의 길이가

이므로,

번의 비트 비교 연산 과정을 수행할 수 있다. 도 1c의 (나)는 NAF 기법을 이용한 연산 예를 나타내는 도면이다.As shown in (a) of Figure 1c, the third algorithm

of

To convert

Algorithm. The third algorithm is a positive integer

And the window size

Take input

Binary representation of

The number of bits that are non-zero integers in

. ≪ / RTI > The NAF scheme, like item (2) of the third algorithm,

If the condition is satisfied, it is possible to perform the while statement repeatedly,

(That is, when the LSB (Least Significant Bit) is 1)

The value of

(Section 2.1). At this time, the NAF technique is a

end

If greater than or equal to

The value is

(See Section 2.1.1). In addition, the NAF technique may be used

on

Can be subtracted (item 2.1.2). As shown in item (2.2)

Is an even number (i.e., when the LSB is 0)

The value can be zero. In item (2.3), the NAF technique

in

The

You can do this by dividing the value by 2, and this can be a one-bit move to the right. For example, if you represent a decimal number 7 as a binary number

Dividing 7 by 2 is actually 3.5, but in the third algorithm,

Is declared as an Integer

The value is 3, except for the decimal point, and expressed as a binary number

. Thus, the NAF technique can eliminate the rightmost bit and cause all bits to move to the right by one space. The NAF technique

The length of

Because of,

The bit comparison operation process can be performed. (B) of FIG. 1C is a diagram showing an operation example using the NAF technique.

알고리즘을 사용하여 모듈러 멱승 연산을 수행하는 알고리즘일 수 있다. 항목(2.3)과 같이,

가 -1인 경우를 처리하는 과정을 추가한다는 점과

를 사용한다는 점을 제외하면 스퀘어 앤드 멀티플라이 기법과 동일할 수 있다. 제4 알고리즘은

에서

의 곱셈에 대한 역원인

가 미리 계산될 수 있다. 레코딩 바이너리 기법의 상세 동작 과정은 도 1d의 (가)에서의 제4 알고리즘에 나타낸 바와 같고, 도 1d의 (나)는 레코딩 바이너리 기법을 이용한 연산 예를 나타내는 도면이다. FIG. 1D is a diagram for explaining a recording binary technique. The recording binary technique

Algorithm to perform a modular exponentiation operation. As in item 2.3,

The process of processing the case of -1 is added

Can be the same as the square-and-multiple technique. The fourth algorithm

in

The reverse cause of the multiplication of

Can be calculated in advance. The detailed operation procedure of the recording binary technique is as shown in the fourth algorithm in FIG. 1D, and FIG. 1D is a diagram showing an operation example using the recording binary technique.

알고리즘을 사용하여 스칼라 곱셈을 수행하는 알고리즘일 수 있다. 또한, 윈도우 NAF 기법은 바이너리 기법에

알고리즘을 활용하여 포인트 에디션 연산을 줄일 수 있다. 윈도우 NAF 기법은,

에 해당하는 타원곡선 상의 점들을 미리 계산하여 저장할 수 있다. 따라서 윈도우 NAF 기법은

의 크기에 따라 미리 계산한(pre-computation) 값들을 저장할 메모리가 요구될 수 있다. 윈도우 NAF 기법의 상세 동작 과정은 도 1e의 제5 알고리즘에 나타낸 바와 같다. 윈도우 NAF 기법을 이용한 연산 예로서,

일 때,

이고, 7P = 2(2(2(P)))-P 일 수 있다. 또한, 윈도우 NAF 기법을 이용한 연산 예로서,

일 때,

이고, 6P = 2(2(2(P))-P) 일 수 있다.1E is a view for explaining a window NAF (Window NAF) technique. Windows NAF technique

Algorithm to perform a scalar multiplication. In addition, the window NAF technique uses binary techniques

Algorithms can be used to reduce point edition operations. The Windows NAF technique,

The points on the elliptic curve corresponding to Eq. Therefore,

A memory may be required to store pre-computation values depending on the size of the memory. The detailed operation procedure of the window NAF scheme is as shown in the fifth algorithm of FIG. As an operation example using the window NAF technique,

when,

, And 7P = 2 (2 (2 (P))) - P. As an operation example using the window NAF technique,

when,

, And 6P = 2 (2 (2 (P)) - P).

에 대한

와 타원곡선 상의 점

을 미리 계산하여 결과를 저장하기 때문에

에 따라 미리 계산한(pre- computation) 값들을 저장할 메모리가 요구될 수 있다. 그리고 슬라이딩 윈도우 기법은

부터 윈도우 NAF 기법에 비해 미리 계산한 값(pre-computation)이 많은 단점이 있지만, 일반적으로 사용하는

크기인

인 경우에 포인트 에디션 연산 횟수가 줄어든다는 장점이 있을 수 있다. 또한, 슬라이딩 윈도우 기법은 0,1로만 표현되는 일반적인 이진 표현을 사용할 수 있지만 이 경우는 타원곡선 상의 점

을 미리 계산하기 때문에 메모리 요구가 훨씬 증가할 수 있다. 따라서, 슬라이딩 윈도우 기법은

를

로 변환하여 사용함으로써, 효율을 증가시킬 수 있다. 슬라이딩 윈도우 기법의 상세 동작 과정은 도 1f의 제6 알고리즘에 나타낸 바와 같다.1F is a view for explaining a sliding window technique. The sliding window technique

For

And points on the elliptic curve

And stores the result

A memory may be required to store the pre-computation values according to the pre-computation values. And the sliding window technique

Although there are many disadvantages in pre-computation compared to the window NAF technique,

The size

The number of point edition operations may be reduced. In addition, although the sliding window technique can use a general binary representation expressed only as 0,1, in this case, the point on the elliptic curve

The memory requirements can be much increased. Thus, the sliding window technique

To

It is possible to increase the efficiency. The detailed operation process of the sliding window technique is as shown in the sixth algorithm of FIG. 1F.

2 is a block diagram showing a high-speed NAF conversion apparatus according to an embodiment of the present invention.

The high-speed NAF converting apparatus 200 (hereinafter, NAF converting apparatus) of the present invention may include a setting unit 210 and a processing unit 220. [ In addition, according to the embodiment, the NAF conversion apparatus 200 can be configured by adding the changing unit 230, the calculating unit 240, and the determining unit 250. [

The setting unit 210 sets the value of the window. That is, the setting unit 210 can set a value of a window that is a positive integer. For example, the setting unit 210 may set at least one value of two or more integers to the window value.

The processing unit 220 first sets a window having the length of the set value to at least a part of the public key based on the LSB (Least Significant Bit) of the public key. That is, as the first setting, the processing unit 220 can set the window to a part of the public key by the value set by the setting unit 210. [ For example, when the value of the window is set to 3, the processing unit 220 may set the first bit of the public key to 3 bits from the LSB.

If the target bit to be encrypted in the public key is outside the window, the processing unit 220 may perform a ω-bit right shift ? is a natural number), and sets the window to the second setting. That is, the processing unit 220 may set the window to the second value by moving the target bit by ω-bit, which is the value of the window, in order to include the target bit in the window. For example, when the value of the window is set to 3, the processing unit 220 may set the target bit to be included by shifting the window by 3 bits.

In order to facilitate understanding of the explanation, the NAF conversion apparatus 200 in FIG. 2 will be described with reference to FIGS. 3 and 4. FIG.

3 is a view for explaining an implementation example using a high-speed NAF conversion apparatus according to an embodiment of the present invention.

에 대해

으로 설정되면,

알고리즘에서

가 홀수인 경우(즉, LSB가 1인 경우)의 윈도우를, 제1 세팅할 수 있다(회색 음영 부분, 311).As shown in FIG. 3, the processing unit 220

About

Lt; / RTI >

In the algorithm

(I.e., when the LSB is 1) can be set to the first setting (grayscale portion, 311).

The changing unit 230 may change all bits in the public key included in the first set window to '0'. That is, the changing unit 230 may change all of the first set bits to '0'. In the example of FIG. 3A, the changing unit 230 may change all the bits included in the window (i.e., the gray shaded portion) to '0' (312).

에 대하여

을 산출할 수 있다. The operation unit 240 may calculate a conversion value for the bits in the public key included in the first set window. In the example of FIG. 3A, when the rightmost 3-bit is 011, the arithmetic unit 240 determines that the item (2.1) in the third algorithm

about

Can be calculated.

로 선정된다면, 변경부(230)는 환산값

가

인지를 확인할 수 있다. 도 3의 (a)의 일례에서, 변경부(230)는

값이 제3 알고리즘에서의 항목(2.1.1)의

를 만족시키지 않으므로,

를 수행할 수 있다. 이때, 변경부(230)는

가 3이므로

을 수행하여 가장 오른쪽의 3-비트가 000이 되도록 할 수 있다(312).At this time, the changing unit 230 may check whether the calculated conversion value exceeds the predetermined reference value, and add or subtract a predetermined number to convert the conversion value to '0'. For example,

The changing unit 230 sets the converted value < RTI ID = 0.0 >

end

. In the example of FIG. 3 (a), the changing unit 230

Value of the item (2.1.1) in the third algorithm

Lt; / RTI >

Can be performed. At this time, the changing unit 230

Is 3

To make the rightmost 3-bit be 000 (312).

값을 2로 나누어 오른쪽으로 1-비트 이동시킬 수 있다(313). 즉, 도 3의 (a)에 도시된 바와 같이, 가장 오른쪽 3-비트를 표시하는 회색 음영은 이동될 수 있다.At this time, the processing unit 220 determines the value of 1 as '1', 1-bit right shifts the window, and shifts the 1-bit right shift The movement can be repeated to make the second setting. In an example of FIG. 3A, the processing unit 220 performs item 2.3 of the third algorithm

The value can be shifted one bit to the right by dividing by two (313). That is, as shown in Fig. 3 (a), the gray shade indicating the rightmost 3-bit can be moved.

알고리즘을 통해, 도 3과 같은 동작을 수행한 후 오른쪽으로 1-비트 이동시키는 과정에서, 현재

번째 비트를 본다고 가정할 때

번째 비트부터

번째 비트는 모두 0으로 바뀌는 것을 알 수 있다.Here, the NAF conversion device 200

In the course of performing the operation as shown in FIG. 3 and then shifting one bit to the right through the algorithm,

Assuming you see the ith bit

From the ith bit

0 < / RTI >

값을 1 증가시킴으로써, LSB를 가리키는 화살표를 이동시킬 수 있다. In addition, the processing unit 220 may move the LSB of the public key in conjunction with the 1-bit right shift of the window. As shown in FIG. 3 (a), the processing unit 220

By increasing the value by 1, the arrow pointing to the LSB can be moved.

In addition, the processing unit 220 may remove the bit of the bit value '0' that deviates from the window after the 1-bit right shift. That is, the processing unit 220 may remove the bits previously designated as LSBs (steps 311, 312) so that they actually disappear. For example, in FIG. 3 (a), as shown in step 313, the processing unit 220 may remove the bit value of a portion deviated from the window (a part that is not a gray shade).

에 대하여

으로 할 수 있다. 이때, 변경부(230)는

값이 항목(2.1.1)의

를 만족시키므로,

값이

인 -3이 되고, 항목(2.1.2)의

를 수행할 수 있다. 변경부(230)는

가 -3이므로

을 수행하면 가장 오른쪽의 3-비트가 000이 되도록 할 수 있는데(322), 이때 전환(carry)이 발생할 수 있다. 본 명세서에서, 전환이 발생하는 것은 0 또는 1(0 or 1)이 1 또는 0(1 or 0)으로 바뀌는 것으로 표현하지만, 이에 한정되지는 않는다.3 (b), first, as described in step 311, the processing unit 220 , The window can be set to the first setting (grayscale portion, 321). Next, when the rightmost 3-bit is 101, the changing unit 230 sets the item (2.1) in the third algorithm

about

. At this time, the changing unit 230

The value of the item (2.1.1)

Lt; / RTI >

The value is

(-3), and the item

Can be performed. The changing unit 230

Is -3

The rightmost 3-bit can be made 000 (322), at which time a carry may occur. In this specification, the occurrence of the conversion is expressed as a change of 0 or 1 (0 or 1) to 1 or 0 (1 or 0), but is not limited thereto.

값을 2로 나누어 오른쪽으로 1-비트 이동시킬 수 있다(323). 또한, 처리부(220)는

값을 1증가시킴으로써, LSB를 가리키는 화살표를 이동시킬 수 있다.Next, the processing unit 220 performs an item (2.3) of the third algorithm

The value may be divided by 2 and shifted one bit to the right (323). In addition, the processing unit 220

By increasing the value by 1, the arrow pointing to the LSB can be moved.

알고리즘에 슬라이딩 윈도우 개념을 적용하고,

알고리즘에서

의 값이 반드시

보다 작은 양의 홀수가 된다는 특성을 활용할 수 있다. 예를 들어,

인 경우, NAF 변환 장치(200)는 001 및 011인 1 및 3만이

의 값이 될 수 있다는 특성을 활용할 수 있다. 또한, NAF 변환 장치(200)는 010, 100 및 110과 같은 짝수의 경우, LSB가 1이 될 때까지 오른쪽으로 이동하여 001 및 011의 형태가 되고, 101 및 111의 경우에는 전환(carry)가 발생하여 1000이 된 다음 LSB가 1이 될 때까지 오른쪽으로 이동하여 001의 형태가 될 수 있다는 특성을 활용할 수 있다. 따라서, NAF 변환 장치(200)는

의 값이 반드시

보다 작은 양의 홀수가 되는 특성을 활용할 수 있다. According to the embodiment, the NAF conversion device 200

We apply the sliding window concept to the algorithm,

In the algorithm

The value of

It is possible to utilize the characteristic of being a smaller amount of odd number. E.g,

, The NAF converting apparatus 200 can obtain only 1 and 3 of 001 and 011

Can be a value of. In the case of an even number such as 010, 100, and 110, the NAF converter 200 shifts to the right until the LSB becomes 1 and becomes a form of 001 and 011. In the case of 101 and 111, And then moves to the right until the LSB becomes 1 and can take the form of 001. Therefore, the NAF conversion device 200

The value of

It is possible to utilize the characteristic that becomes a smaller amount of odd number.

4 is a view for explaining an implementation example using a high-speed NAF conversion apparatus according to an embodiment of the present invention.

에 대해

으로 설정되면,

알고리즘에서

가 홀수인 경우(즉, LSB가 1인 경우)의 윈도우를, 제1 세팅할 수 있다(회색 음영 부분, 411, 421).As shown in FIG. 4, the processing unit 220

About

Lt; / RTI >

In the algorithm

(Gray shaded portion, 411, 421) can be set in the case of the odd number (that is, when the LSB is 1).

을 기준으로, 환산값이 기준값을 넘는지를 판단할 수 있다.The determination unit 250 may determine whether the calculated conversion value exceeds a predetermined reference value. That is, the determination unit 250 can determine the conversion value calculated by the calculation unit 240 based on the reference value. For example, the determination unit 250 determines that the reference value

It is possible to judge whether the converted value exceeds the reference value.

보다 환산값이 작은 경우, 제1 세팅된 윈도우 크기(ω)만큼을, ω 비트만큼 오른쪽 이동시킬 수 있다. 도 4의 (a)에 도시된 바와 같이, 처리부(220)는

인 경우 오른쪽으로

-비트 이동시킬 수 있다(413). 단계(413)에서, ω-비트 이동한 후, NAF 변환 장치(200)는 윈도우가 이동한 비트의 값을 체크할 수 있다. 즉, 처리부(220)는 윈도우 크기가 3으로 제1 세팅된 경우, 윈도우 크기가 3인 윈도우를 3-비트만큼 오른쪽 이동시킬 수 있다. 3-비트 이동한 후, NAF 변환 장치(200)는 윈도우에 포함된 비트에 대하여, 0 또는 1 중 하나를 비트값으로 체크할 수 있다. 이 과정에서, 처리부(220)는

알고리즘의 연산 과정을 생략할 수 있다.At this time, if the result of the determination is negative, the processing unit 220 can move the window to the? -Bit right and adjust the setting position of the window to the target bit. That is, the processing unit 220 determines that the reference value

If the converted value is smaller, the first set window size? Can be shifted to the right by? Bits. As shown in Fig. 4 (a), the processing unit 220

To the right

- Bit can be moved (413). In step 413, after shifting the? -Bit, the NAF transformer 200 may check the value of the bit where the window has moved. That is, when the window size is set to '3', the processing unit 220 can move the window having the window size of 3 to the right by 3 bits. After the 3-bit shift, the NAF transformer 200 can check one of 0 or 1 as a bit value for the bits included in the window. In this process, the processing unit 220

The computation process of the algorithm can be omitted.

대신

를 수행할 수 있다(422). 또한, 처리부(220)는 비트값을 전환한 후, 도 4의 (b)에 도시된 바와 같이, 윈도우 크기가 ω인 윈도우를 ω 비트만큼 오른쪽 이동시킬 수 있다(423). 단계(423)에서, ω-비트 이동한 후, NAF 변환 장치(200)는 윈도우가 이동한 비트의 값을 체크할 수 있다. 예를 들면, 처리부(220)는 제1 세팅된 윈도우 크기가 3인 윈도우를 3-비트만큼 오른쪽 이동시킬 수 있다. 3-비트 이동한 후, NAF 변환 장치(200)는 윈도우에 포함된 비트에 대하여, 0 또는 1 중 하나를 비트값으로 체크할 수 있다.As a result of the determination, if the processing unit 220 carries out the bit value of the target bit and moves the window to the right by the? -Bit, the processing unit 220 may adjust the setting position of the window to the target bit . That is, as the processing unit 220 generates a caryy,

instead

(422). After switching the bit value, the processing unit 220 may move the window having the window size of? To the right by? Bits as shown in FIG. 4B (423). In step 423, after shifting the? -Bit, the NAF transformer 200 may check the value of the bit where the window has moved. For example, the processing unit 220 can move the window with the first set window size of 3 to the right by three bits. After the 3-bit shift, the NAF transformer 200 can check one of 0 or 1 as a bit value for the bits included in the window.

-비트 이동을 하여

번째 비트로 이동함으로써, LSB를 가리키는 화살표를 이동시킬 수 있다.In addition, the processing unit 220 can adjust the LSB of the public key to the target bit in conjunction with the ω-bit right shift of the window. That is, as shown in FIGS. 4A and 4B, the processing unit 220 is moved to the right

- By bit shifting

Th bit, it is possible to move the arrow pointing to the LSB.

번의 비교 연산 과정을 수행함으로써,

번의 비트 비교 연산 과정을 수행하는

알고리즘의 연산 처리 속도를 최적화 할 수 있다.The NAF conversion device 200,

By performing the comparison operation of the number of times,

Bit comparison operation

The processing speed of the algorithm can be optimized.

(

은 양의 정수

의 이진수 변환에 따른 비트 수)이 증가하거나 홀수인 경우를 발생시키는 패턴이 많이 존재하는 경우에 NAF 변환 시간을 단축할 수 있다(

은 양의 정수

의 이진수 변환에 따른 비트 수,

는 윈도우 크기).Further, the NAF conversion device 200, upon NAF conversion,

(

Is a positive integer

The number of bits in accordance with the binary conversion of the number of bits) is increased or an odd number is generated, the NAF conversion time can be shortened

Is a positive integer

The number of bits according to the binary conversion,

Window size).

5 is a diagram illustrating an algorithm for implementing a high-speed NAF conversion apparatus according to an embodiment of the present invention.

알고리즘)으로서 수도 코드(pseudo code)로 표현될 수 있다. NAF 변환 장치(200)는 제7 알고리즘의 항목(2)에서의 While문의 수행 조건을

으로 설정하지 않을 수 있다. 그 이유는,

의 값이 반드시

보다 작은 양의 홀수가 되므로 NAF 변환 장치(200)는 와일(While)문의 중단 여부를 항목(2.3.1)에서만 판단하도록 할 수 있다. 항목(2.1)의 와일(While)문은 연속된 0을 빠르게 처리하기 위한 코드일 수 있다. 와일(While)문을 빠져 나와 항목(2.2)에 왔을 때는

는 반드시 홀수인 정수가 될 수 있다.As shown in Fig. 5, the NAF conversion apparatus 200 includes a seventh algorithm (

Algorithm) as a pseudo code. The NAF transforming apparatus 200 calculates the condition of execution of the While statement in the item (2) of the seventh algorithm

. ≪ / RTI > The reason is that,

The value of

The NAF conversion apparatus 200 can determine whether or not the while query is terminated only in the item (2.3.1). The While statement of item (2.1) can be a code to quickly process consecutive zeros. When you come out of the While door and come to the item (2.2)

Can be an integer that is an odd number.

-비트에 대한 1-비트씩 이동(shift) 하는 과정'을 생략할 수 있다. 즉, NAF 변환 장치(200)는

를

만큼 증가시키고 를

만큼 오른쪽으로 이동할 수 있다. Item (2.3.2) in the seventh algorithm is a code representation of the operation process of FIG. 4 (a). At this time, the NAF conversion apparatus 200 determines whether the item (2.1.2) of the third algorithm and the item

- the process of shifting bits by one bit 'can be omitted. That is, the NAF conversion apparatus 200

To

≪ / RTI & To

To the right.

를 수행할 수 있다. NAF 변환 장치(200)는 나머지 부분에 대하여 항목(2.3.2)와 같이 수행할 수 있다.Item (2.4) in the seventh algorithm is a code representation of the operation process of (b) in FIG. In this case, since NAF conversion apparatus 200 generates a carry in the algorithm

Can be performed. The NAF conversion apparatus 200 can perform the operation as shown in item (2.3.2) for the remaining part.

FIGS. 6 to 11 are diagrams for explaining performance evaluation of an algorithm for implementing a high-speed NAF conversion apparatus according to an embodiment of the present invention.

알고리즘(제7 알고리즘)의 성능 평가를 도시한 도면이다.

알고리즘에 대한 성능 평가는 입력 값

와

에 대해

를 계산하는 데에 걸리는 사이클 카운터(Cycle Counter)를

알고리즘과 비교하는 방식으로 평가할 수 있다.

알고리즘과

알고리즘은

의 길이

이 늘어나면 전체 사이클 카운터가 증가할 수 있다. 두 알고리즘은 오른쪽 이동(right shift)하는 과정에서 홀수인 경우가 증가할수록 사이클 카운터가 증가할 수 있다.

(Seventh algorithm) according to an embodiment of the present invention.

The performance evaluation of the algorithm is based on the input value

Wow

About

The cycle counter (Cycle Counter)

And can be evaluated in a manner of comparing with an algorithm.

Algorithm and

The algorithm

Length

The total cycle counter can be increased. Both algorithms can increase the cycle counter as the odd number increases in the right shift process.

의 길이가 8이고

가 2일 때,

은 홀수인 경우가 1번 발생하지만

와

은 홀수인 경우가 4번 발생하기 때문에 사이클 카운터가 더 클 수 있다.

이 홀수인 경우가 4번이 되는 이유는 도 6에 도시된 바와 같이,

일 때 발생하는 전환(Carry)에 의해

-비트 앞에 1이 발생하기 때문일 수 있다.For example,

Is 8 in length

Is 2,

The odd number occurs once

Wow

Since the odd number occurs four times, the cycle counter may be larger.

The reason why the odd number is 4 is that, as shown in Fig. 6,

By the conversion that occurs when

- It may be because 1 occurs before the bit.

의 길이

에 대한 사이클 카운터 비교를 할 수 있다. 그뿐만 아니라, 본원의 성능 평가에서는 홀수의 경우가 발생하는 횟수에 대한 비교도 포함할 수 있다. 즉, 본원의 성능 평가에서는 0과 1로 조합되는 0,1,01,001,011,101 등과 같은 패턴들의 반복 횟수에 대해서

크기가 2인 경우와 3인 경우를 저성능 8-비트 마이크로프로세서 아트메가128(ATmega128)에서 구현하고 사이클 카운터를 측정하여 성능 평가를 수행할 수 있다.Therefore, in the performance evaluation of the present invention

Length

Can be compared to the cycle counter. In addition, the performance evaluation of the present invention may include a comparison of the number of occurrences of the odd number. That is, in the performance evaluation of the present invention, the number of repetitions of patterns such as 0,1,01,001,011,101,

It is possible to implement 2 and 3 cases in the low performance 8-bit microprocessor Artmega 128 (ATmega128) and measure the cycle counter to perform the performance evaluation.

의 이진수 비트수는 RSA에서 1024-비트 이상, ECC에서 160-비트 이상이 사용되며, 이러한 비트들은 0과 1에 의한 다양한 패턴들의 반복이라고 볼 수 있다. 따라서, 도 7에 도시된 바와 같이, 3-비트 이하에서 발생 가능한 다양한 반복 패턴에 따른

알고리즘 대비

알고리즘의 평균 및 편차 이득을 요약하여 도시한다.

알고리즘에 비해

알고리즘의 평균 사이클 카운터가 약 20% 정도 감소하고 편차 또한 30% 이상 감소한 것을 확인할 수 있다. 특히,

알고리즘은

알고리즘에 비해 편차에서 우수한 성능을 나타낼 수 있다. 이는,

알고리즘이

의 길이

이 늘어나더라도 사이클 카운터 증가량이

알고리즘 보다 작아서 다양한 입력 패턴에 대해 일정한 성능을 나타낼 수 있음을 의미할 수 있다.

The number of binary bits in RSA is more than 1024-bit, and the number of bits in RSC is more than 160-bit in ECC. These bits can be regarded as repetition of various patterns by 0 and 1. Therefore, as shown in FIG. 7, in accordance with various repetitive patterns that can be generated in 3-bit or less

Algorithm contrast

The mean and variance gains of the algorithm are summarized.

Compared to the algorithm

The average cycle counter of the algorithm is reduced by about 20% and the deviation is also decreased by 30% or more. Especially,

The algorithm

It can exhibit excellent performance in deviation from the algorithm. this is,

The algorithm

Length

The cycle counter increment is

It can be said that it is possible to show a constant performance for various input patterns because it is smaller than the algorithm.

알고리즘은

알고리즘에 비해 각각 평균 이득이 18.6%와 19.4%, 편차 이득이 31.3%와 31.8% 성능 향상을 나타낼 수 있다. 또한, 도 10 및 도 11에 도시된 바와 같이,

알고리즘은

알고리즘에 비해 각각 평균 이득이 11.8%와 14.3%, 편차 이득이 26.7%와 29.9% 성능 향상을 나타낼 수 있다. 8 and 9 show results of a detailed analysis of the cycle counter of the two algorithms according to the number of repetitions in the 1 and 01 bit patterns, which are the main repetitive patterns affecting the performance of the two algorithms. As shown in Figs. 8 and 9,

The algorithm

The average gain is 18.6% and 19.4%, the deviation gain is 31.3%, and the performance improvement is 31.8%, respectively. Further, as shown in Figs. 10 and 11,

The algorithm

The average gain is 11.8% and 14.3%, and the deviation gain is 26.7% and 29.9%, respectively, compared with the algorithm.

-비트 이동(shift) 횟수가 동일하기 때문일 수 있다. 예를 들어,

일 때, 0101은 전환(carry)이 발생해 1000로 변환된 후 3 오른쪽 이동(right shift)을 한 다음 0001을 처리하기 때문에 한 번의

-비트 이동(shift)이 발생할 수 있다. 010101도 전환(carry)이 발생해 011000으로 변환된 후 오른쪽으로 3-비트 이동(shift)을 한 다음 011을 처리하기 때문에 이동(shift)이 한 번 발생할 수 있다. 반면에, 01010101은 전환(carry)이 발생하여 01011000으로 변환된 후 오른쪽으로 3-비트 이동(shift)을 한 다음 01011이 되고, 다시 01000으로 변환된 후 오른쪽으로 3-비트 이동(shift)을 하여 01을 처리하기 때문에 이동(shift)이 두 번 발생할 수 있다. 따라서, 01의 연속 횟수가 2번일 때와 3번일 때의 사이클 카운터는 동일하지만 4번일 때는 사이클 카운터가 증가하게 될 수 있다.As shown in FIG. 11, the reason why the clock counter does not increase as the number of repetitions increases from 2 to 3 (or from 5 to 6)

- It may be because the number of bit shifts is the same. E.g,

, 0101 generates a carry, converts it to 1000, performs 3 right shifts, and then processes 0001,

- Bit shift may occur. 010101 may also shift once because a carry occurs and is converted to 011000 and then shifted to the right by three bits and then processed by 011. On the other hand, a 01010101 shifts to 01011000 after a carry occurs, shifts 3-bit to the right, and then shifts to 01011. After shifting to 01000, it shifts to 3 bits to the right 01, the shift may occur twice. Therefore, the cycle counter of 01 and 2 is 3 and the cycle counter is the same, but when it is 4, the cycle counter may be increased.

12 is a workflow diagram specifically illustrating a high-speed NAF conversion method according to an embodiment of the present invention.

First, the high-speed NAF conversion method according to this embodiment can be performed by the NAF conversion device 200 described above.

First, the NAF transformer 200 sets a window value (1210). That is, step 1210 may be a process of setting a value of a window that is a positive integer. For example, the NAF conversion device 200 can set at least one value of two or more integers to the value of the window.

Next, the NAF transformer 200 sets a window having the length of the set value to at least a part of the public key, based on the LSB (Least Significant Bit) of the public key (1220). That is, step 1220 may set the window to a portion of the public key by the value set in step 1210, as the first setting. For example, when the value of the window is set to 3, the NAF transformer 200 can set the first bit to 3 bits from the LSB of the public key.

Next, when the target bit to be encrypted in the public key is located outside the window, the NAF transformer 200 transforms the window into? -Bit right shift (? -Bit right shift ) (The above? Is a natural number), and sets the window to the second setting (1230). That is, the NAF transformer 200 may set the window to the second value by moving the target bit by ω-bit, which is the value of the window, in order to include the target bit in the window. For example, when the value of the window is set to 3, the NAF transformer 200 can set the target bit to be included by shifting the window by 3 bits.

According to the embodiment, the NAF transformer 200 may change all the bits in the public key included in the first set window to '0'. That is, the NAF converter 200 can change all of the first set bits to '0'.

에 대하여

을 산출할 수 있다. According to the embodiment, the NAF transformer 200 may calculate a conversion value for the bits in the public key included in the first set window. For example, if the rightmost 3-bit is 011, the NAF transformer 200 determines that the item (2.1) in the third algorithm

about

Can be calculated.

로 선정된다면, NAF 변환 장치(200)는 환산값

가

인지를 확인할 수 있다. NAF 변환 장치(200)는

값이 제3 알고리즘에서의 항목(2.1.1)의

를 만족시키지 않으므로,

를 수행할 수 있다. 이때, NAF 변환 장치(200)는

가 3이므로

을 수행하여 가장 오른쪽의 3-비트가 000이 되도록 할 수 있다.The step of changing to '0' may be a process of checking whether the calculated conversion value exceeds a predetermined reference value, and adding or subtracting a predetermined number to convert the conversion value to '0'. For example,

The NAF conversion device 200 converts the converted value < RTI ID = 0.0 >

end

. The NAF conversion device 200

Value of the item (2.1.1) in the third algorithm

Lt; / RTI >

Can be performed. At this time, the NAF conversion device 200

Is 3

So that the rightmost 3-bit can be made 000.

값을 2로 나누어 오른쪽으로 1-비트 이동시킬 수 있다.At this time, the step 1230 determines the value of '1' and 1-bit right shifts the window, and the 1-bit right shift is performed until the target bit is included in the window. And repeating the movement to repeat the second setting. For example, the NAF transformer 200 performs an item 2.3 of the third algorithm

You can divide the value by two and move it one bit to the right.

In addition, the step 1230 may be a process of removing the bit of the bit value '0' deviating from the window after the 1-bit right shift. In other words, the NAF transformer 200 can remove the bits previously designated as LSBs so that they actually disappear. For example, the NAF conversion apparatus 200 can remove the bit value of the portion deviated from the window.

값을 1 증가시킴으로써, LSB를 이동할 수 있다.In addition, step 1230 may be a step of moving the LSB of the public key in conjunction with the 1-bit right shift of the window. For example, the NAF conversion device 200

By increasing the value by 1, the LSB can be moved.

을 기준으로, 환산값이 기준값을 넘는지를 판단할 수 있다.According to the embodiment, the NAF conversion apparatus 200 can determine whether the calculated conversion value exceeds a predetermined reference value. That is, with respect to the conversion value calculated at the step of calculating the conversion value, the NAF conversion device 200 can determine the conversion value based on the reference value. For example, the NAF conversion device 200 may convert the reference value

It is possible to judge whether the converted value exceeds the reference value.

보다 환산값이 작은 경우, 제1 세팅된 윈도우 크기(ω)만큼을 ω 비트만큼 오른쪽 이동시킬 수 있다. NAF 변환 장치(200)는 인 경우 오른쪽으로

-비트 이동시킬 수 있다. ω-비트 이동한 후, NAF 변환 장치(200)는 윈도우가 이동한 비트의 값을 체크할 수 있게 된다. 예를 들면, NAF 변환 장치(200)는 윈도우 크기가 3으로 제1 세팅된 경우, 윈도우 크기가 3인 윈도우를 3-비트만큼 오른쪽 이동시킬 수 있다. 3-비트 이동한 후, NAF 변환 장치(200)는 윈도우에 포함된 비트에 대하여, 0 또는 1 중 하나를 비트값으로 체크할 수 있다. 이 과정에서, NAF 변환 장치(200)는

알고리즘의 연산 과정을 생략할 수 있다.According to the embodiment, the NAF transformer 200 may move the window to the right by the? -Bit to adjust the setting position of the window to the target bit if the result of the determination is NO. That is, the NAF conversion apparatus 200 converts the reference value

If the converted value is smaller, the first set window size? Can be shifted to the right by? Bits. The NAF conversion device 200 To the right

- Bit can be moved. After the? -bit shift, the NAF transformer 200 can check the value of the bit where the window has moved. For example, when the window size is set to 3 in the first setting, the NAF conversion apparatus 200 can move the window having the window size of 3 to the right by 3 bits. After the 3-bit shift, the NAF transformer 200 can check one of 0 or 1 as a bit value for the bits included in the window. In this process, the NAF conversion device 200

The computation process of the algorithm can be omitted.

대신

를 수행할 수 있다. 또한, NAF 변환 장치(200)는 비트값을 전환한 후, 윈도우 크기가 ω인 윈도우를 ω 비트만큼 오른쪽 이동시킬 수 있다. ω-비트 이동한 후, NAF 변환 장치(200)는 윈도우가 이동한 비트의 값을 체크할 수 있다. 예를 들면, NAF 변환 장치(200)는 제1 세팅된 윈도우 크기가 3인 윈도우를 3-비트만큼 오른쪽 이동시킬 수 있다. 3-비트 이동한 후, NAF 변환 장치(200)는 윈도우에 포함된 비트에 대하여, 0 또는 1 중 하나를 비트값으로 체크할 수 있다.According to the embodiment, the NAF transformer 200 may carry the bit value of the target bit when it is determined that the target bit is exceeded, move the window to the right by the? -Bit, The target bit can be adjusted. That is, as the NAF conversion apparatus 200 generates a caryy,

instead

Can be performed. Also, after switching the bit value, the NAF conversion apparatus 200 can move the window having the window size? To the right by? Bits. After the? -bit shift, the NAF transformer 200 can check the value of the bit where the window has moved. For example, the NAF conversion apparatus 200 can move the window with the first set window size of 3 to the right by 3 bits. After the 3-bit shift, the NAF transformer 200 can check one of 0 or 1 as a bit value for the bits included in the window.

-비트 이동을 하여 번째 비트로 이동함으로써, LSB를 가리키는 화살표를 이동시킬 수 있다.According to the embodiment, the NAF transformer 200 can adjust the LSB of the public key to the target bit in conjunction with? -Bit right shift of the window. For example, the NAF conversion device 200 is shifted to the right

- By bit shifting Th bit, it is possible to move the arrow pointing to the LSB.

번의 비교 연산 과정을 수행함으로써,

번의 비트 비교 연산 과정을 수행하는

알고리즘의 연산 처리 속도를 최적화 할 수 있다(

은 양의 정수

의 이진수 변환에 따른 비트 수,

는 윈도우 크기).This NAF conversion method

By performing the comparison operation of the number of times,

Bit comparison operation

It is possible to optimize the processing speed of the algorithm (

Is a positive integer

The number of bits according to the binary conversion,

Window size).

(

은 양의 정수

의 이진수 변환에 따른 비트 수)이 증가하거나 홀수인 경우를 발생시키는 패턴이 많이 존재하는 경우에 NAF 변환 시간을 단축할 수 있다.In the NAF conversion method,

(

Is a positive integer

The number of bits in accordance with the binary conversion of the number of bits) increases or the number of patterns that generate an odd number is large, the NAF conversion time can be shortened.

The method according to an embodiment of the present invention may be implemented in the form of a program command that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions to be recorded on the medium may be those specially designed and configured for the embodiments or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of program instructions include machine language code such as those produced by a compiler, as well as high-level language code that can be executed by a computer using an interpreter or the like. The hardware devices described above may be configured to operate as one or more software modules to perform the operations of the embodiments, and vice versa.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments. For example, it is to be understood that the techniques described may be performed in a different order than the described methods, and / or that components of the described systems, structures, devices, circuits, Lt; / RTI > or equivalents, even if it is replaced or replaced.

Therefore, other implementations, other embodiments, and equivalents to the claims are also within the scope of the following claims.

200: High-speed NAF converter
210: setting unit 220:
230: changing section 240:
250:

Claims (16)

A setting unit for setting a value of a window;
Setting a window having the set value as a length on at least a part of the public key based on a least significant bit (LSB) of a public key, and setting, as a target bit to be encrypted in the public key, Bit right shift (the "?&Quot; is a natural number) so that the target bit is included in the window,
And a high-speed NAF converter. The method according to claim 1,
And changing the bits in the public key included in the first set window to ' 0 '
Further comprising:
Wherein,
Bit right shifting until the target bit is included in the window, and the second bit is shifted to the right by 1-bit right shifting (1-bit right shift) Setting
High speed NAF converter. 3. The method of claim 2,
Wherein,
After the 1-bit right shift, the bit of the bit value '0' which is deviated from the window is removed
High speed NAF converter. 3. The method of claim 2,
Wherein,
The LSB of the public key is moved in conjunction with the 1-bit right shift of the window
High speed NAF converter. 3. The method of claim 2,
Calculating a converted value of an integer with respect to bits included in the first set window among the bits constituting the public key,
Further comprising:
The changing unit may change,
And the number of bits included in the first set window is made to be '0' by checking whether the calculated conversion value of the integer exceeds the predetermined reference value, adding or subtracting a predetermined number,
High speed NAF converter. The method according to claim 1,
An operation unit for calculating an integer conversion value of bits included in the first set window among bits constituting the public key; And
A determination unit for determining whether the calculated conversion value of the integer exceeds a predetermined reference value,
Further comprising:
Wherein,
As a result of the determination,
Moves the window to the right by the? -Bit, and adjusts the setting position of the window to the target bit
High speed NAF converter. The method according to claim 6,
As a result of the determination,
Wherein,
1 if the bit value of the target bit is 0, or 0 if the bit value of the target bit is 1, and moves the window to the right by the? -Bit so as to set the setting position of the window to the target Bit-adjusted
High speed NAF converter. 8. The method according to claim 6 or 7,
Wherein,
The LSB of the public key is adjusted to the target bit in conjunction with the ω-bit right shift of the window
High speed NAF converter. Setting a value of a window;
Setting a window having the set value as a length based on a LSB (Least Significant Bit) of a public key to at least a part of the public key; And
If the target bit to be encrypted in the public key is outside the window,
Setting the window to a second state by making ω-bit right shift (ω is a natural number) the window so that the target bit is included;
/ RTI > 10. The method of claim 9,
Changing all bits in the public key included in the first set window to ' 0 '
Further comprising:
Wherein the second setting comprises:
Determining? As '1'; And
Bit right shift until the target bit is included in the window, and repeating the 1-bit right shift until the target bit is included in the window,
/ RTI > 11. The method of claim 10,
Wherein the second setting comprises:
Removing the bit of the bit value '0' deviating from the window after the 1-bit right shift,
Further comprising the steps of: 11. The method of claim 10,
Wherein the second setting comprises:
Moving the LSB of the public key in conjunction with the 1-bit right shift of the window
Further comprising the steps of: 11. The method of claim 10,
In the NAF conversion method,
Calculating an integer conversion value of bits included in the first set window among the bits constituting the public key,
Further comprising:
The step of changing to '0'
Checking whether the calculated conversion value of the integer exceeds the predetermined reference value, adding or subtracting a predetermined number to make all the bits included in the first set window '0'
/ RTI > 10. The method of claim 9,
Calculating an integer conversion value of bits included in the first set window among the bits constituting the public key;
Determining whether the calculated conversion value of the integer exceeds a predetermined reference value; And
As a result of the determination,
Shifting the window to the right ω-bit and adjusting the setting position of the window to the target bit
Further comprising the steps of: 15. The method of claim 14,
As a result of the determination,
If the bit value of the target bit is 0, the bit is changed to 1 or if the bit value of the target bit is 1, the bit is changed to 0 and carry; And
Shifting the window to the right ω-bit and adjusting the setting position of the window to the target bit
Further comprising the steps of: 16. The method according to claim 14 or 15,
Adjusting the LSB of the public key to the target bit in conjunction with? -Bit right shift of the window
Further comprising the steps of:

Images