KR102425475B1 - Method for modular multiplication - Google Patents

Abstract

In the modular multiplication method performed by the controller of the computing device according to some embodiments of the present disclosure, a first value and a second value input from a user are converted into a first expression and a second expression using a preset integer expression method to do; and performing modular multiplication on the first expression and the second expression to perform calculation, but storing and utilizing data related to the overlapped operation during the accumulation process in a storage unit.

Description

Modular multiplication method

The present disclosure relates to a modular multiplication method among operations for elliptic curve cryptography, and more particularly, to a fractional modular multiplication method for elliptic curve cryptography capable of fast modular multiplication in an 8-bit ATmega 128 processor environment.

Due to the rapid increase in various types of e-commerce, various encryption methods have been widely studied not only in the e-commerce system but also in the security system. Among them, the public key cryptography using the elliptic curve system (ECC: Elliptic Curve Cryptosystem, hereinafter referred to as ECC) is a public key encryption algorithm based on the difficulty of discrete algebra, following the RSA (Rivest Shamir Adleman) algorithm. Recently, it has been attracting attention as a core technology for e-commerce. The elliptic curve encryption system based on the difficulty of discrete algebra is a type of public key method along with the DSA algorithm and RSA based on prime factorization. The ECC was first proposed by N.Koblitz and V.S.Miller in 1985 as an alternative to the RSA encryption method, and is currently being widely adopted by security system and e-commerce solution companies.

In particular, the ECC does not create a new public key cryptographic algorithm on a finite field using an elliptic curve, but has a characteristic of implementing an existing public key algorithm using an elliptic curve. More precisely, the ECC provides a mathematical place to implement a cryptographic algorithm, not a specific cryptographic algorithm. It makes it possible to implement on an elliptic curve instead of on an elliptic curve. Cryptographic implementation on an elliptic curve is much stronger than implementation on an integer of the same key size due to mathematical complexity, so most of the cryptographic algorithms in the future are highly likely to be changed to ECC. This elliptic curve encryption system is a system based on a multiplication group of a finite field, and various encryption systems can be designed and have secure characteristics. In particular, various elliptic curves that can provide groups can be used. That is, it is easy to design various cryptographic systems. Also, even if all users use the same base body K, each user can choose a different curve. This means that all users can use the same hardware to perform operations, and the curve can be changed periodically for added security.

In addition, in order to investigate the theoretical safety of the public key encryption system, it is first to analyze how much it is required to solve the mathematical problem that is the basis of the system in order to attack the system. The public key cryptosystem RSA based on the real prime factor problem, the public key cryptosystem DSA based on the discrete logarithm problem, and the elliptic curve cryptosystem have all been precisely analyzed for many years, and such a system attack method is based on the mathematical problem underlying it. It is known to solve Therefore, it is now necessary to analyze what the "hard problem underlying" is. Specifically, it is known that the elliptic curve discrete logarithmic problem is relatively easy when it is a super-singular elliptic curve, which is a small class of elliptic curves. However, these vulnerabilities can be easily identified and therefore easily avoided. Sub-exponential time algorithms are generally known for prime factorization problems and discrete logarithmic problems in modular p. Although the sub-exponential time algorithm is still known as a difficult problem, it means that it is easier than a problem that allows only fully exponential time algorithms. The running time of this algorithm is for a constant c (avoiding the super-singular elliptic curve), however, there are no sub-exponential time algorithms in this group. That is, it is easy to design a secure encryption system.

While RSA and DSA use 1024-bit modularity, ECC shows that 160-bit modularity is sufficient. Moreover, as the key size increases, the ratio further increases. In order to perform the modular multiplication method to be applied to the ECC, there was a problem that the load for overlapping memory access in an environment with limited resources was relatively large.

Republic of Korea Patent Publication No. 10-2005-0101003 (published on October 20, 2005)

The present disclosure has been devised in response to the above-mentioned background technology, and it is possible to efficiently use registers in a resource-limited environment such as an 8-bit-based ATmega 128 processor to reduce the load on memory access redundancy, modular multiplication for elliptic curve cryptography to provide a way

The technical problems of the present disclosure are not limited to the technical problems mentioned above, and other technical problems not mentioned will be clearly understood by those skilled in the art from the following description.

In the modular multiplication method performed by the controller of the computing device for solving the above-described problem, a first value and a second value input from a user are converted into a first expression and a second expression using a preset integer expression method. converting; and performing modular multiplication on the first expression and the second expression to perform calculation, but storing and utilizing data related to the overlapped operation during the accumulation process in a storage unit.

에서 좌측항의 상기 X인 경우, 우측항의 표현이고, 상기 제 2 표현은, 상기 제 2 값이 상기 기 설정된 정수 표현법과 관련된 수학식

에서 좌측항의 상기 Y인 경우, 우측항의 표현이고, 상기

또는 상기

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고, 상기

는 2⁸ 일 수 있다.Alternatively, the first expression is an equation in which the first value is related to the preset integer expression method.

In the case of X of the left term, it is an expression of the right term, and the second expression is an equation in which the second value is related to the preset integer expression method.

In the case of Y of the left term, it is an expression of the right term, and

or above

is any value of 0 or more and less than 2 ⁸ , and

may be 2 ⁸ .

형태로 변환하는 단계 -상기 기 설정된 제 1 표현 방식에서, 상기

는

이고, 상기

는

임-; 상기 제 2 표현을 기 설정된 제 2 표현 방식인

형태로 변환하는 단계 -상기 기 설정된 제 2 표현 방식에서, 상기

는

이고, 상기

는

임-; 표현 방식이 변환된 상기 제 1 표현 및 상기 제 2 표현을 이용하여 곱셈을 수행하여 산출 값을 생성하는 단계; 및 상기 산출 값에 대한 기 설정된 감산 연산을 수행하여 최종 산출 값을 생성하는 단계;를 포함할 수 있다.Alternatively, the step of calculating by performing modular multiplication on the first expression and the second expression may include converting the first expression into a preset first expression method.

Converting to a form - In the preset first expression method, the

Is

and said

Is

lim-; The second expression is a preset second expression method

Converting to a form - In the preset second expression method, the

Is

and said

Is

lim-; generating an output value by performing multiplication by using the first expression and the second expression in which the expression method is converted; and generating a final calculated value by performing a preset subtraction operation on the calculated value.

에서, 상기

를

로 치환하고, 상기

를

로 치환하고, 상기

를

으로 치환하는 단계; 를 더 포함하고, 상기

는

이고, 상기

는

이고, 상기

는

이고, 상기

는

이고, 상기

은

이고, 상기

, 상기

및 상기

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값일 수 있다.Alternatively, the generating an output value by performing multiplication by using the first expression and the second expression in which the expression mode is converted may include using the first expression and the second expression in which the expression mode is converted. The result of multiplication by

in, said

cast

Substituted with,

cast

Substituted with,

cast

Substituting with; further comprising,

Is

and said

Is

and said

Is

and said

Is

and said

silver

and said

, remind

and said

may be any one of 0 or more and less than 2 ⁸ values.

Alternatively, the preset subtraction operation is performed using a preset modular prime to express the 256-bit calculated value as a 192-bit multiplication result, and the final calculated value is

로 표현될 수 있다.formula

can be expressed as

의 연산 결과 값을 상기 저장부에 저장하여 활용할 수 있다.Alternatively, in the final calculated value, the

may be used by storing the operation result value in the storage unit.

A computing device for solving the above-described problems includes: a controller including one or more processors; a storage unit for storing data, wherein the control unit converts the first value and the second value input by the user into a first expression and a second expression using a preset integer expression method, and the first expression and a modular multiplication of the second expression is performed to perform an operation, but data related to a redundant operation during an accumulation process may be stored and utilized in the storage unit.

A computer program stored in a computer-readable storage medium for solving the above-described problems, the computer program comprising instructions for causing a control unit of a computing device to perform the following steps, wherein the steps are: converting the first value and the second value into the first expression and the second expression using a preset integer expression method; and performing modular multiplication on the first expression and the second expression to perform calculation, but storing and utilizing data related to the overlapped operation during the accumulation process in a storage unit.

According to the present disclosure, by using a range shifted representation different from the conventional one, a new redundant operation is generated, and by using this, the effect of performing the operation twice in one calculation can be increased, thereby increasing the memory access and register usage efficiency. In particular, the speed of modular multiplication operation can be improved by storing data related to overlapping operations during the accumulation process in a register to minimize load and storage of memory and implement in assembly language.

The effects obtainable in the present disclosure are not limited to the above-mentioned effects, and other effects not mentioned will be clearly understood by those of ordinary skill in the art to which the present disclosure belongs from the description below. .

Various aspects are now described with reference to the drawings, wherein like reference numbers are used to refer to like elements collectively. In the following examples, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of one or more aspects. It will be evident, however, that such aspect(s) may be practiced without these specific details.
1 is a block diagram of a computing device in accordance with some embodiments of the present disclosure.
2 is a diagram for explaining an example of a modular multiplication method performed in a computing device according to some embodiments of the present disclosure.
3 to 5 are diagrams illustrating an algorithm for explaining an example of a modular multiplication method performed in a computing device according to some embodiments of the present disclosure.
6 is a diagram comparing a modular multiplication method performed in a computing device according to some embodiments of the present disclosure, another multiplication method, and another modular multiplication method.
7 is a general schematic diagram of an example computing environment in which embodiments of the present disclosure may be implemented.

Various embodiments and/or aspects are now disclosed with reference to the drawings. In the following description, for purposes of explanation, numerous specific details are set forth to provide a thorough understanding of one or more aspects. However, it will also be appreciated by one of ordinary skill in the art that such aspect(s) may be practiced without these specific details. The following description and accompanying drawings set forth in detail certain illustrative aspects of one or more aspects. These aspects are illustrative, however, and some of the various methods in principles of various aspects may be employed, and the descriptions set forth are intended to include all such aspects and their equivalents. Specifically, as used herein, “embodiment”, “example”, “aspect”, “exemplary”, etc. is not to be construed as an advantage or advantage of any aspect or design described over other aspects or designs. It may not be.

Hereinafter, the same or similar components are assigned the same reference numerals regardless of reference numerals, and redundant description thereof will be omitted. In addition, in describing the embodiments disclosed in the present specification, if it is determined that detailed descriptions of related known technologies may obscure the gist of the embodiments disclosed in the present specification, the detailed description thereof will be omitted. In addition, the accompanying drawings are only for easy understanding of the embodiments disclosed in the present specification, and the technical ideas disclosed in the present specification are not limited by the accompanying drawings.

Unless otherwise defined, all terms (including technical and scientific terms) used herein may be used with the meaning commonly understood by those of ordinary skill in the art to which this disclosure belongs. In addition, terms defined in a commonly used dictionary are not to be interpreted ideally or excessively unless clearly defined in particular.

In addition, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless otherwise specified or clear from context, “X employs A or B” is intended to mean one of the natural implicit substitutions. That is, X employs A; X employs B; Or, when X employs both A and B, "X employs A or B" can be applied to either of these cases. Also, as used herein, the term “and/or” should be understood to refer to and include all possible combinations of one or more of the listed related items.

Also, the terms "comprises" and/or "comprising" mean that the feature and/or element is present, but excludes the presence or addition of one or more other features, elements and/or groups thereof. should be understood as not Also, unless otherwise specified or unless it is clear from context to refer to a singular form, the singular in the specification and claims should generally be construed to mean “one or more”.

And, the term "at least one of A or B" should be interpreted to mean "when including only A", "when including only B", and "when combined with the configuration of A and B".

When a component is referred to as being “connected” or “connected” to another component, it may be directly connected or connected to the other component, but it is understood that other components may exist in between. it should be On the other hand, when it is mentioned that a certain element is "directly connected" or "directly connected" to another element, it should be understood that no other element is present in the middle.

The suffixes "module" and "part" for the components used in the following description are given or used in consideration of ease of writing the specification, and do not have a meaning or role distinct from each other by themselves.

Objects and effects of the present disclosure, and technical configurations for achieving them will become clear with reference to the embodiments described below in detail in conjunction with the accompanying drawings. In describing the present disclosure, if it is determined that a detailed description of a well-known function or configuration may unnecessarily obscure the subject matter of the present disclosure, the detailed description thereof will be omitted. And the terms to be described later are terms defined in consideration of functions in the present disclosure, which may vary according to the intention or custom of the user or operator.

However, the present disclosure is not limited to the embodiments disclosed below and may be implemented in various different forms. Only the present embodiments are provided so that the present disclosure is complete, and to fully inform those of ordinary skill in the art to which the present disclosure belongs, the scope of the disclosure, and the present disclosure is only defined by the scope of the claims . Therefore, the definition should be made based on the content throughout this specification.

The modular multiplication method according to some embodiments of the present disclosure may refer to a method of performing modular multiplication using a preset integer expression method.

1 is a block diagram of a computing device in accordance with some embodiments of the present disclosure.

Referring to FIG. 1 , a computing device 100 according to some embodiments of the present disclosure may include a control unit 110 , a storage unit 120 , and a communication unit 130 . However, since the above-described components are not essential in implementing the computing device 100 , the computing device 100 may have more or fewer components than those listed above.

Computing apparatus 100 may include any type of computer system or computer device, such as, for example, microprocessors, mainframe computers, digital processors, portable devices and device controllers, and the like. However, the present invention is not limited thereto.

The controller 110 of the computing device 100 may typically process the overall operation of the computing device 100 . In addition, the control unit 110 processes signals, data, information, etc. input or output through the above-described components or by driving an application program stored in the storage unit 120 to provide or process appropriate information or functions to the user. can For example, the controller 110 may generate a final calculated value by performing modular multiplication on the input values. In addition, the control unit 110 is on the storage unit 120 such as a central processing unit (CPU), a general purpose graphics processing unit (GPGPU), a tensor processing unit (TPU), etc. It may be any type of processor that executes instructions stored in , and may include one or more processors. For example, the controller 110 may be an 8-bit-based ATmega 128 processor. However, the present invention is not limited thereto.

Also, the controller 110 may control at least some of the components of the computing device 100 in order to drive an application program stored in the storage 120 . Furthermore, the controller 110 may operate at least two or more of the components included in the computing device 100 in combination to drive the application program.

According to the software implementation, embodiments such as the procedures and functions described in this specification may be implemented as separate software modules. Each of the software modules may perform one or more functions and operations described herein. The software code may be implemented as a software application written in a suitable programming language. The software code may be stored in the storage unit 120 of the computing device 100 and executed by the controller 110 of the computing device 100 .

Meanwhile, the controller 110 of the computing device 100 according to some embodiments of the present disclosure may perform operations related to the modular multiplication method.

Specifically, the controller 110 of the computing device 100 according to some embodiments of the present disclosure converts the first value and the second value input by the user into the first expression and the second expression using a preset integer expression method. can do.

Here, each of the first value and the second value may be an arbitrary integer. Specifically, each of the first value and the second value may be any one of integers that can be expressed within a preset bit. The preset bit may be set to any one of a plurality of bits (eg, 64 bits, 128 bits, 192 bits, 256 bits, etc.) according to the performance of the computing device 100 or a user's setting. For example, the first value and the second value may be any one integer from 0 to 2 ¹⁹² integers that can be expressed within 192 bits. However, the present invention is not limited thereto.

Meanwhile, the preset integer expression method may mean converting an expression of values (eg, first and second values) input by a user into a preset range. Specifically, the preset expression means converting the first value and the second value into the first expression and the second expression in the range of 2 ^-96 to 2 ⁹⁶ ( ^2-96 or more and 2 ⁹⁶ or less) in units of 8-bit words. can do. That is, the controller 110 sets the first value and the second value input by the user in units of 8-bit words in the range of 2 ^-96 to 2 ⁹⁶ ( ^2-96 or more and 2 ⁹⁶ or less) using a preset expression method. expression and a second expression. Specifically, the first value is as in Equation 1 below.

는 제 1 값이고,

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고,

는 2⁸ 일 수 있다. 여기서, 제 1 표현은 수학식 1의

에서 우측항의 표현일 수 있다.

is the first value,

is any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ . Here, the first expression of Equation 1

It may be an expression of the right term in .

In addition, the second value is the same as in Equation 2 below.

는 제 2 값이고,

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고,

는 2⁸ 일 수 있다. 여기서, 제 2 표현은 수학식 2의

에서 우측항의 표현일 수 있다.

is the second value,

is any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ . Here, the second expression of Equation 2

It may be an expression of the right term in .

In addition, a result of multiplying the first value and the second value is expressed by Equation 3 below.

는 제 1 값과 제 2 값의 곱셈 결과 값이고,

는 제 1 값이고,

는 제 2 값이고,

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고,

는 2⁸ 일 수 있다.

is the result of multiplying the first value and the second value,

is the first value,

is the second value,

is any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ .

Meanwhile, the control unit 110 performs modular multiplication on the first expression and the second expression to perform calculation, but data related to the overlapped operation during the accumulation process may be stored and utilized in the storage unit. Here, the controller 110 may perform modular multiplication on the first expression and the second expression using a method similar to the subtractive Karatsuba operation. However, the present invention is not limited thereto.

의 형태이고,

는

이고,

는

일 수 있다. 여기서,

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고,

는 2⁸ 일 수 있다. 즉, 제어부(110)는 제 1 표현을

의 형태로 변환할 수 있다.Specifically, when performing an operation by performing modular multiplication on the first expression and the second expression, the controller 110 may convert the first expression into a preset first expression method. Specifically, the preset first expression method is

is in the form of

Is

ego,

Is

can be here,

is any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ . That is, the control unit 110 generates the first expression

can be converted to the form of

의 형태이고,

는

이고,

는

일 수 있다. 여기서,

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값이고,

는 2⁸ 일 수 있다. 즉, 제어부(110)는 제 2 표현을

의 형태로 변환할 수 있다.Also, the controller 110 may convert the second expression into a preset second expression method. Specifically, the preset second expression method is

is in the form of

Is

ego,

Is

can be here,

is any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ . That is, the control unit 110 generates the second expression.

can be converted to the form of

Then, the controller 110 may generate a calculated value by performing multiplication by using the first expression and the second expression in which the expression method is converted.

일 수 있다. 여기서,

는

이고,

는

이고,

는

이고,

는

이고,

는 2⁸ 일 수 있다. 여기서,

및

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값일 수 있다. 즉, 제어부(110)는 표현 방식이 변환된 제 1 표현 및 제 2 표현을 이용하여 곱셈을 수행하여

을 생성할 수 있다. Here, the calculated value, that is, the calculated result value obtained by performing multiplication using the first expression and the second expression in which the expression method is converted, is

can be here,

Is

ego,

Is

ego,

Is

ego,

Is

ego,

may be 2 ⁸ . here,

and

may be any one of 0 or more and less than 2 ⁸ values. That is, the controller 110 performs multiplication by using the first expression and the second expression in which the expression method is converted.

can create

에서,

를

로 치환하고,

를

로 치환하고,

를

으로 치환할 수 있다. 여기서,

는

이고,

는

이고,

는

이고,

는

이고,

은

이고,

,

및

는 0 이상 2⁸ 미만인 값 중 어느 하나의 값일 수 있고,

는 2⁸ 일 수 있다.Here, the control unit 110 is the calculated result value

at,

cast

replace with

cast

replace with

cast

can be replaced with here,

Is

ego,

Is

ego,

Is

ego,

Is

ego,

silver

ego,

,

and

may be any value of 0 or more and less than 2 ⁸ ,

may be 2 ⁸ .

Also, the controller 110 may generate a final calculated value by performing a preset subtraction operation on the calculated value. Here, the preset subtraction operation may be performed using a preset modular prime to express a 256-bit calculated value as a 192-bit multiplication result. That is, the controller 110 may generate a final calculated value by performing a subtraction operation using a preset modular prime on the calculated value.

일 수 있고,

는 2¹⁹²-2⁶⁴-1의 연산 결과 값을 의미할 수 있다.Here, the preset modular prime is NIST P-192, that is,

can be,

may mean an operation result value of 2 ¹⁹² -2 ⁶⁴ -1.

로 표현될 수 있다. 그리고, 제어부(110)는

의 연산 결과 값을 저장부(120)에 저장하여 활용할 수 있다. 즉, 제어부(110)는 최종 산출 값

에서

의 연산 결과 값을 저장부(120)에 저장하여 활용할 수 있다. 이에 대한 자세한 설명은 도 2를 통해 후술한다.In addition, the final calculated value is

can be expressed as And, the control unit 110

The operation result value of ? may be stored in the storage unit 120 to be utilized. That is, the controller 110 controls the final calculated value.

at

The operation result value of ? may be stored in the storage unit 120 to be utilized. A detailed description thereof will be described later with reference to FIG. 2 .

2 is a diagram for explaining an example of a modular multiplication method performed in a computing device according to some embodiments of the present disclosure. Specifically, FIG. 2A is a diagram illustrating a calculated value generated by performing multiplication on a first expression and a second expression in a computing device according to some embodiments of the present disclosure. Referring to FIG. 2A , the controller 110 of the computing device 100 according to some embodiments of the present disclosure converts a first value and a second value using a preset integer expression method to a first expression and a second expression. Multiplication of the expression 2 is performed using the Karatsuba operation, and the calculated value can be expressed as W ^-24 ~ W ²⁴ (W is 2 ⁸ ).

And, FIG. 2(b) is a diagram illustrating a final calculated value by performing a subtraction operation on the calculated value of FIG. 2(a) in a computing device according to some embodiments of the present disclosure. Referring to FIG. 2( b ), the control unit 110 of the computing device 100 according to some embodiments of the present disclosure provides values in the range of W ^-24 to W ^-12 in FIG. 2( a ) and FIG. 2( a ). ), a preset subtraction operation may be performed on a value in the range of W ¹² to W ²⁴ and a final calculated value may be generated. Here, the final calculated value exists in the range of W ^-12 to W ¹² (W is 2 ⁸ ) of the preset integer expression method, and overlapping partial operations may occur. Accordingly, the control unit 110 may store and utilize the operation result value of the partial operation overlapping in the final calculated value in the storage unit 120 . Specifically, the storage unit 120 may record information on a portion that is repeatedly calculated (accumulated) during the operation process. The control unit 110 may determine which part is stored in a register included in the storage unit 120 by using the information stored in the storage unit 120 during the operation of the first value and the second value. In addition, when it is necessary to additionally perform an operation on the corresponding part during the accumulation process, the controller 110 may call a value stored in the register to perform the accumulation. That is, the control unit 110 converts the first value and the second value into the first expression and the second expression using a preset integer expression method, performs modular multiplication, and calculates data related to overlapping partial operations during the accumulation process. can be stored in registers.

That is, the controller 110 may calculate the overlapping partial operation only once and store the redundant operation data in the register, and use the redundant operation data stored in the register for the remaining overlapping partial operations. Accordingly, the control unit 110 may reduce the load and storage of the memory included in the storage unit 120 to improve the speed of the modular multiplication operation.

Meanwhile, the controller 110 of the computing device 100 according to some embodiments of the present disclosure may perform modular multiplication by performing a preset algorithm. A detailed description thereof will be described later with reference to FIGS. 3 to 5 .

의 계산을 삽입하여

에 대한 96비트와 96비트 곱셈 1레벨 Karatsuba 곱셈을 수행하는 알고리즘 2에 관한 도면이다. 그리고, 도 5는 본 개시의 몇몇 실시예에 따른 컴퓨팅 장치에서 수행되는 192비트와 192비트 곱셈 2레벨 Karatsuba 곱셈과 NIST P-192를 이용한 감산 연산을 나타내는 알고리즘 3에 관한 것이다.3 to 5 are diagrams illustrating an algorithm for explaining an example of a modular multiplication method performed in a computing device according to some embodiments of the present disclosure. Specifically, FIG. 3 is a diagram of Algorithm 1 showing a basic implementation of 96-bit and 96-bit multiplication 1-level Karatsuba multiplication performed in a computing device according to some embodiments of the present disclosure. And, FIG. 4 is an algorithm 1 of FIG. 3 in a computing device according to some embodiments of the present disclosure.

by inserting the calculation of

96-bit and 96-bit multiplication for , Algorithm 2 for performing 1-level Karatsuba multiplication. And, FIG. 5 relates to Algorithm 3 showing a two-level Karatsuba multiplication and a subtraction operation using NIST P-192 for 192-bit and 192-bit multiplication performed in a computing device according to some embodiments of the present disclosure.

3 to 5 , the control unit 110 of the computing device 100 according to some embodiments of the present disclosure performs algorithms 1 to 3 to set first and second values input by the user to preset values. It is converted into the first expression and the second expression using the integer expression method, and is calculated by performing modular multiplication on the first expression and the second expression, but data related to the overlapping operation during the accumulation process can be stored and utilized in the storage unit. have. Here, the detailed description of the computing device 100 may be replaced with the content described with reference to FIGS. 1 and 2 .

일 수 있다. 다만, 이에 한정되지 않는다. 또한, 저장부(120)는 기 설정된 비트 내에서 표현할 수 있는 정수가 저장되어 있을 수 있다. Referring back to FIG. 1 , the storage unit 120 includes a register or memory, and may store any type of information generated or determined by the control unit 110 and any type of information received by the communication unit 130 . . For example, the storage unit 120 may store data generated in connection with a duplicate operation during the accumulation process in the control unit 110 . Specifically, the register of the storage unit 120 may store data related to overlapping partial operations during the accumulation process. Accordingly, when performing the redundant operation, the controller 110 may utilize data related to the redundant operation stored in the storage unit 120 . That is, the controller 110 may increase the memory access and register usage efficiency of the storage unit 120 by utilizing data related to overlapping partial operations during the accumulation process stored in the register of the storage unit 120 . In addition, data for the overlapping portion may be recorded in the storage unit 120 . Here, the overlapping part is

can be However, the present invention is not limited thereto. Also, the storage unit 120 may store an integer that can be expressed within a preset bit.

Here, the storage unit 120 is a flash memory type (flash memory type), a hard disk type (hard disk type), a multimedia card micro type (multimedia card micro type), card type memory (eg, SD or XD memory, etc.) ), Random Access Memory (RAM), Static Random Access Memory (SRAM), Read-Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Programmable Read-Only Memory (PROM), Magnetic It may include at least one type of storage medium among a memory, a magnetic disk, and an optical disk. However, the present invention is not limited thereto.

Meanwhile, the communication unit 130 may include one or more modules that enable communication between the computing device 100 and the user terminal and between the computing device 100 and external servers. Also, the communication unit 130 may include one or more modules for connecting the computing device 100 to one or more networks.

Here, the communication unit 130 is a network connecting the communication between the computing device 100 and the user terminal and between the computing device 100 and external servers is any wired or wireless network that can transmit and receive data and signals in any form. A communication network may be included in the network represented in this disclosure.

As described above in FIG. 1 , the modular multiplication method performed by the controller of the computing device according to some embodiments of the present disclosure stores and utilizes data related to the redundant operation in the storage unit, thereby reducing the operation time compared to the prior art. can be effective A detailed description thereof will be described later with reference to FIG. 6 .

6 is a diagram comparing a modular multiplication method performed in a computing device according to some embodiments of the present disclosure, another multiplication method, and another modular multiplication method.

Referring to FIG. 6 , as a result of the multiplication 10 performed by the Operand scanning method in the computing device, cycle counts are 7760. Here, the cycle count may mean an execution time. Accordingly, the computing device may determine that the lower the cycle count, the smaller the execution time and thus the more efficient.

Here, the multiplication 10 performed by the operand scanning method in the computing device may be a method of performing multiplication by configuring an inner loop and an outer loop. Specifically, in a computing device, the outer loop may be loaded and held in a working register while the operand X _i is executing the inner loop. In addition, in the computing device, multiplication and operand Y _i are loaded one by one in the inner loop, and partial multiplication may be calculated by multiplying X _i . Then, when the inner loop is completed in the computing device, the next operand Y _i+1 may be loaded and the inner loop may be repeated again.

Meanwhile, as a result of performing the multiplication 20 performed by the product scanning method in the computing device, cycle counts were found to be 5614.

Here, the multiplication 20 performed by the product scanning method in the computing device may be a method of deriving a final multiplication result by performing partial multiplication for each column among parts accumulated in a work register and accumulating partial multiplication values.

Meanwhile, as a result of the multiplication 30 performed by the hybrid scanning method in the computing device, cycle counts were 4133.

Here, the multiplication 30 performed by the hybrid scanning method in the computing device may be a method combining the operand scanning method 10 and the product scanning method 20 . Specifically, the multiplication 30 performed by the hybrid scanning method in the computing device consists of an inner loop and an outer loop, the inner loop uses the operand scanning method 10 , and the outer loop uses the product scanning method 20 . This may be a method of deriving the final multiplication result. The hybrid scanning method (30) described above is described in the paper "Gura N, Patel A, Wander A, Eberle H, Shantz SC (2004) Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye M, Quisquater JJ (eds) Cryptographic hardware and embedded systems (lecture notes in computer science), vol 3156. Springer, Berlin, pp 119-132".

On the other hand, as a result of the multiplication 40 performed by the Operand caching method in the computing device, cycle counts were shown as 3470.

Here, the multiplication 40 performed by the Operand caching method in the computing device divides the calculation into several rows based on the product scanning method 20, and divides the divided row into 4 parts to perform multiplication. can be The above-described Operand caching method (40) is described in the paper "Hutter M, Wenger E (2011) Fast multi-precision multiplication for publickey cryptography on embedded microprocessors. In: Preneel B, Takagi T (eds) Cryptographic hardware and embedded systems(lecture notes in) computer science), vol 6917. Springer, Berlin, pp 459-474".

On the other hand, as a result of the multiplication 50 performed by the consecutive operand caching method in the computing device, cycle counts were shown as 3437.

Here, the multiplication 50 performed by the consecutive operand caching method in the computing device may refer to a method of rescheduling rows to share operands when the row is changed based on the operand caching method 40 . The multiplication 50 performed by the consecutive operand caching method in the computing device can overcome the disadvantage of having to reload the operands because there is no shared operand between the rows whenever the row is changed in the operand caching method 40 in the operand caching method 40 . The above-mentioned consecutive operand caching method (50) is described in the paper "Seo H, Kim H (2012) Multi-precision multiplication for public-key cryptography on embedded microprocessors. In: MotiYung DHL (ed) Information security applications, vol 7690. Lecture notes in computer science. Springer, Berlin, pp 55-67".

Meanwhile, as a result of the multiplication 60 performed by the subtractive Karatsuba method in the computing device, cycle counts were found to be 2987.

Here, the multiplication 60 performed by the subtractive Karatsuba method may refer to a method of performing multiplication using the Karatsuba method in an 8-bit-based computer platform. The aforementioned Subtractive Karatsuba method (60) is specifically discussed in the paper “Hutter M, Schwabe P (2015) Multiprecision multiplication on AVR revisited. J Cryptogr Eng 5(3):201-214”.

On the other hand, as a result of the modular multiplication 70 performed by the consecutive operand caching method in the computing device, cycle counts are shown as 4042.

Here, the modular multiplication 70 performed by the consecutive operand caching method may refer to a method of additionally performing a subtraction operation after performing the multiplication 50 by the consecutive operand caching method in the computing device.

Meanwhile, as a result of the modular multiplication 80 performed by the subtractive Karatsuba method in the computing device, cycle counts were found to be 3597.

Here, the modular multiplication 80 performed by the subtractive Karatsuba method may refer to a method of additionally performing a subtraction operation after performing the multiplication 60 by the subtractive Karatsuba method in the computing device.

Modular multiplication (70) performed by the above-described consecutive operand caching method and modular multiplication (80) performed by the subtractive Karatsuba method is described in the paper "Liu Z, Seo H, Großschδdl J, Kim H (2016) Efcient implementation of NIST-compliant elliptic. curve cryptography for 8-bit AVR-based sensor nodes. IEEE Trans Inf Forensics Secur 11(7):1385-1397”.

Meanwhile, as a result of the modular multiplication 90 performed by the modular multiplication method performed in the computing device according to some embodiments of the present disclosure, cycle counts are shown as 2958.

6, it can be seen that the cycle count is measured lower in the modular multiplication method 90 performed in the computing device according to some embodiments of the present disclosure than the conventional multiplication method and modular multiplication methods 10 to 80. can Accordingly, the modular multiplication method 90 performed in the computing device according to some embodiments of the present disclosure requires less execution time than the conventional multiplication method and the modular multiplication method 10 to 80 , and thus is more efficient.

7 is a general schematic diagram of an example computing environment in which embodiments of the present disclosure may be implemented.

Although the present disclosure has been described above as being generally capable of being implemented by a computing device, those skilled in the art will appreciate that the present disclosure is a combination of hardware and software and/or in combination with computer-executable instructions and/or other program modules that may be executed on one or more computers. It will be appreciated that it can be implemented as a combination.

Generally, program modules include routines, programs, components, data structures, etc. that perform particular tasks or implement particular abstract data types. In addition, those skilled in the art will appreciate that the methods of the present disclosure can be applied to single-processor or multiprocessor computer systems, minicomputers, mainframe computers as well as personal computers, handheld computing devices, microprocessor-based or programmable consumer electronics, and the like. It will be appreciated that each of these may be implemented in other computer system configurations, including those capable of operating in connection with one or more associated devices.

The described embodiments of the present disclosure may also be practiced in distributed computing environments where certain tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

Computers typically include a variety of computer-readable media. Any medium accessible by a computer can be a computer readable medium, and such computer readable media includes volatile and nonvolatile media, transitory and non-transitory media, removable and non-transitory media. including removable media. By way of example, and not limitation, computer-readable media may include computer-readable storage media and computer-readable transmission media. Computer-readable storage media includes volatile and non-volatile media, temporary and non-transitory media, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. includes media. A computer-readable storage medium may be RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital video disk (DVD) or other optical disk storage device, magnetic cassette, magnetic tape, magnetic disk storage device, or other magnetic storage device. device, or any other medium that can be accessed by a computer and used to store the desired information.

Computer readable transmission media typically embodies computer readable instructions, data structures, program modules or other data, etc. in a modulated data signal such as a carrier wave or other transport mechanism, and Includes any information delivery medium. The term modulated data signal means a signal in which one or more of the characteristics of the signal is set or changed so as to encode information in the signal. By way of example, and not limitation, computer-readable transmission media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media. Combinations of any of the above are also intended to be included within the scope of computer-readable transmission media.

An exemplary environment 1100 implementing various aspects of the disclosure is shown including a computer 1102 , the computer 1102 including a processing unit 1104 , a system memory 1106 , and a system bus 1108 . do. A system bus 1108 couples system components, including but not limited to system memory 1106 , to the processing device 1104 . The processing device 1104 may be any of a variety of commercially available processors. Dual processor and other multiprocessor architectures may also be used as processing unit 1104 .

The system bus 1108 may be any of several types of bus structures that may be further interconnected to a memory bus, a peripheral bus, and a local bus using any of a variety of commercial bus architectures. System memory 1106 includes read only memory (ROM) 1110 and random access memory (RAM) 1112 . A basic input/output system (BIOS) is stored in non-volatile memory 1110, such as ROM, EPROM, EEPROM, etc., which BIOS is the basic input/output system (BIOS) that helps transfer information between components within computer 1102, such as during startup. contains routines. RAM 1112 may also include high-speed RAM, such as static RAM, for caching data.

The computer 1102 may also be configured with an internal hard disk drive (HDD) 1114 (eg, EIDE, SATA) - this internal hard disk drive 1114 may also be configured for external use within a suitable chassis (not shown). Yes-, magnetic floppy disk drive (FDD) 1116 (eg, for reading from or writing to removable diskette 1118), and optical disk drive 1120 (eg, CD-ROM) for reading from, or writing to, disk 1122, or other high capacity optical media such as DVD. The hard disk drive 1114 , the magnetic disk drive 1116 , and the optical disk drive 1120 are connected to the system bus 1108 by the hard disk drive interface 1124 , the magnetic disk drive interface 1126 , and the optical drive interface 1128 , respectively. ) can be connected to The interface 1124 for implementing an external drive includes at least one or both of Universal Serial Bus (USB) and IEEE 1394 interface technologies.

These drives and their associated computer readable media provide non-volatile storage of data, data structures, computer executable instructions, and the like. For computer 1102, drives and media correspond to storing any data in a suitable digital format. Although the description of computer readable media above refers to HDDs, removable magnetic disks, and removable optical media such as CDs or DVDs, those skilled in the art will use zip drives, magnetic cassettes, flash memory cards, cartridges, etc. It will be appreciated that other tangible computer-readable media such as etc. may also be used in the exemplary operating environment and any such media may include computer-executable instructions for performing the methods of the present disclosure.

A number of program modules may be stored in the drive and RAM 1112 , including an operating system 1130 , one or more application programs 1132 , other program modules 1134 , and program data 1136 . All or portions of the operating system, applications, modules, and/or data may also be cached in RAM 1112 . It will be appreciated that the present disclosure may be implemented in various commercially available operating systems or combinations of operating systems.

A user may enter commands and information into the computer 1102 via one or more wired/wireless input devices, for example, a pointing device such as a keyboard 1138 and a mouse 1140 . Other input devices (not shown) may include a microphone, IR remote control, joystick, game pad, stylus pen, touch screen, and the like. Although these and other input devices are often connected to the processing unit 1104 through an input device interface 1142 that is connected to the system bus 1108, parallel ports, IEEE 1394 serial ports, game ports, USB ports, IR interfaces, It may be connected by other interfaces, etc.

A monitor 1144 or other type of display device is also coupled to the system bus 1108 via an interface, such as a video adapter 1146 . In addition to the monitor 1144, the computer typically includes other peripheral output devices (not shown), such as speakers, printers, and the like.

Computer 1102 may operate in a networked environment using logical connections to one or more remote computers, such as remote computer(s) 1148 via wired and/or wireless communications. Remote computer(s) 1148 may be workstations, computing device computers, routers, personal computers, portable computers, microprocessor-based entertainment devices, peer devices, or other common network nodes, and are typically connected to computer 1102 . Although it includes many or all of the components described for it, only memory storage device 1150 is shown for simplicity. The logical connections shown include wired/wireless connections to a local area network (LAN) 1152 and/or a larger network, eg, a wide area network (WAN) 1154 . Such LAN and WAN networking environments are common in offices and companies, and facilitate enterprise-wide computer networks, such as intranets, all of which can be connected to a worldwide computer network, for example, the Internet.

When used in a LAN networking environment, the computer 1102 is connected to the local network 1152 through a wired and/or wireless communication network interface or adapter 1156 . Adapter 1156 may facilitate wired or wireless communication to LAN 1152 , which also includes a wireless access point installed therein for communicating with wireless adapter 1156 . When used in a WAN networking environment, the computer 1102 may include a modem 1158, be connected to a communication computing device on the WAN 1154, or establish communications over the WAN 1154, such as over the Internet. have other means. A modem 1158 , which may be internal or external and a wired or wireless device, is coupled to the system bus 1108 via a serial port interface 1142 . In a networked environment, program modules described for computer 1102 or portions thereof may be stored in remote memory/storage device 1150 . It will be appreciated that the network connections shown are exemplary and other means of establishing a communication link between the computers may be used.

Computer 1102 may be associated with any wireless device or object that is deployed and operates in wireless communication, for example, printers, scanners, desktop and/or portable computers, portable data assistants (PDAs), communication satellites, wireless detectable tags. It operates to communicate with any device or place, and phone. This includes at least Wi-Fi and Bluetooth wireless technologies. Accordingly, the communication may be a predefined structure as in a conventional network or may simply be an ad hoc communication between at least two devices.

Wi-Fi (Wireless Fidelity) makes it possible to connect to the Internet, etc. without a wire. Wi-Fi is a wireless technology such as cell phones that allows these devices, eg, computers, to transmit and receive data indoors and outdoors, ie anywhere within range of a base station. Wi-Fi networks use a radio technology called IEEE 802.11 (a, b, g, etc) to provide secure, reliable, and high-speed wireless connections. Wi-Fi can be used to connect computers to each other, to the Internet, and to wired networks (using IEEE 802.3 or Ethernet). Wi-Fi networks may operate in unlicensed 2.4 and 5 GHz radio bands, for example, at 11 Mbps (802.11a) or 54 Mbps (802.11b) data rates, or in products that include both bands (dual band). .

One of ordinary skill in the art of this disclosure will understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, instructions, information, signals, bits, symbols, and chips that may be referenced in the above description are voltages, currents, electromagnetic waves, magnetic fields or particles, optical field particles or particles, or any combination thereof.

A person of ordinary skill in the art of the present disclosure will recognize that the various illustrative logical blocks, modules, processors, means, circuits and algorithm steps described in connection with the embodiments disclosed herein include electronic hardware, (convenience For this purpose, it will be understood that it may be implemented by various forms of program or design code (referred to herein as software) or a combination of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. A person skilled in the art of the present disclosure may implement the described functionality in various ways for each specific application, but such implementation decisions should not be interpreted as a departure from the scope of the present disclosure.

The various embodiments presented herein may be implemented as methods, apparatus, or articles of manufacture using standard programming and/or engineering techniques. The term article of manufacture includes a computer program, carrier, or media accessible from any computer-readable storage device. For example, computer-readable storage media include magnetic storage devices (eg, hard disks, floppy disks, magnetic strips, etc.), optical disks (eg, CDs, DVDs, etc.), smart cards, and flash drives. memory devices (eg, EEPROMs, cards, sticks, key drives, etc.). Also, various storage media presented herein include one or more devices and/or other machine-readable media for storing information.

It is understood that the specific order or hierarchy of steps in the presented processes is an example of exemplary approaches. Based on design priorities, it is to be understood that the specific order or hierarchy of steps in the processes may be rearranged within the scope of the present disclosure. The appended method claims present elements of the various steps in a sample order, but are not meant to be limited to the specific order or hierarchy presented.

The description of the presented embodiments is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the scope of the present disclosure. Thus, the present disclosure is not intended to be limited to the embodiments presented herein, but is to be construed in the widest scope consistent with the principles and novel features presented herein.

Claims (8)

In the modular multiplication method performed by the control unit of the computing device,
converting the first and second values input by the user into the first expression and the second expression using a preset integer expression method; and
performing an operation by performing modular multiplication on the first expression and the second expression, but storing and utilizing data related to redundant operations during an accumulation process in a storage unit;
containing,
Modular multiplication method.
The method of claim 1,
The first expression is
The first value is an equation related to the preset integer expression method

In the case of X of the left term, it is the expression of the right term,
The second expression is
The second value is an equation related to the preset integer expression method

In the case of Y of the left term, it is the expression of the right term,
remind

or above

is any value of 0 or more and less than 2 ⁸ , and

is 2 ⁸ people,
Modular multiplication method.
3. The method of claim 2,
The step of calculating by performing modular multiplication on the first expression and the second expression comprises:
The first expression is a preset first expression method

Converting to a form - In the preset first expression method, the

Is

and said

Is

lim-;
The second expression is a preset second expression method

Converting to a form - In the preset second expression method, the

Is

and said

Is

lim-;
generating an output value by performing multiplication by using the first expression and the second expression in which the expression method is converted; and
generating a final calculated value by performing a preset subtraction operation on the calculated value;
containing,
Modular multiplication method.
4. The method of claim 3,
The step of generating a calculated value by performing multiplication using the first expression and the second expression in which the expression method is converted,
It is a calculated result value obtained by performing multiplication using the first expression and the second expression in which the expression method is converted.

in, said

cast

Substituted with,

cast

Substituted with,

cast

Substituting with;
further comprising,
remind

Is

and said

Is

and said

Is

and said

Is

and said

silver

and said

, remind

and said

is any one of the values between 0 and 2 and less than ⁸ ,
Modular multiplication method.
5. The method of claim 4,
The preset subtraction operation is
It is performed using a preset modular prime to express the calculated value of 256 bits as a result of multiplication of 192 bits,
The final calculated value is,
formula

expressed as,
Modular multiplication method.
6. The method of claim 5,
In the final calculated value, the

to store and utilize the operation result value of
Modular multiplication method.
a control unit including one or more processors;
a storage unit for storing data;
including,
The control unit is
Converting the first value and the second value input by the user into the first expression and the second expression using a preset integer expression method, and
The first expression and the second expression are calculated by performing modular multiplication, but data related to the overlapped operation during the accumulation process is stored and utilized in the storage unit,
computing device.
A computer program stored in a computer-readable storage medium, the computer program comprising instructions for causing a control unit of a computing device to perform the following steps, the steps comprising:
converting the first and second values input by the user into the first expression and the second expression using a preset integer expression method; and
performing an operation by performing modular multiplication on the first expression and the second expression, but storing and utilizing data related to redundant operations during an accumulation process in a storage unit;
containing,
A computer program stored on a computer-readable storage medium.

Images