Patent ID: 12192319

DETAILED DESCRIPTION OF THE EMBODIMENTS

FIG.1is a block diagram showing cryptography circuitry100according to an exemplary embodiment of the inventive concept. The cryptography circuitry100may be included in any device that performs a secure operation. For example, the cryptography circuitry100may be included in stationary computing systems such as desktop computers, servers, kiosks, and the like, portable computing systems such as laptop computers, smartphones, tablet PCs, and the like, wearable devices such as smart watches, smart glasses, smart bands, and the like, and personal authentication devices such as a credit card or a personal identification number (PIN), and the like. In some embodiments, the cryptography circuitry100may be included in a secure region protected from external attacks, and may be integrated into a single die and/or a single semiconductor package. As shown inFIG.1, the cryptography circuitry100may include a random number generator120, a processing circuit140, and a memory160.

The cryptography circuitry100may perform a cryptographic operation and/or a security operation. In some embodiments, the cryptography circuitry100may generate or utilize various cryptographic keys (e.g., a symmetric key, an asymmetric key) for encryption, decryption, signing, and/or signature verification. In some embodiments, the cryptography circuitry100may enable establishing a secure connection with another remote device over a communication link. In some embodiments, the cryptography circuitry100may enable the establishment of a trusted execution environment or security domain that stores data or performs various functions. Herein, public key-based encryption will be mainly referred to as an example of an encryption operation, but exemplary embodiments of the inventive concept are not limited thereto.

Multiple modular multiplications may be performed in cryptography. For example, in Rivest-Shamir-Adleman (RSA) encryption or elliptic curve cryptography (ECC), which is a public key-based encryption method, modular multiplications for 256-bit to 8192-bit values may be performed. Despite the inputs and outputs of modular multiplication with a relatively long length, RSA encryption and ECC are vulnerable to attacks using quantum computers. Accordingly, in order to combat attacks using quantum computers, post-quantum cryptography (PQC) has been proposed, and the U.S. National Institute of Standards and Technology (NIST) is in the process of standardizing PQC.

In PQC, modular multiplications may be performed on values having a relatively small length, and for example, modular multiplications for values of 32 bits or less may be performed. Accordingly, modular multiplication may be vulnerable to side-channel attacks, and modular multiplication that is resistant to side-channel attacks in PQC may be important. The random number generator120, the processing circuit140, and the memory160may perform modular multiplication of the first input a and the second input b, and may generate a result c of the modular multiplication. As will be described later, the random number generator120, the processing circuit140, and the memory160may consume equal power independently of the values of the first input a and the second input b to generate the result c of modular multiplication. Accordingly, modular multiplication and cryptographic operations including the same may be resistant to side-channel attacks. In addition, a generator for modular multiplication may be randomly selected, and accordingly, a modular multiplication and a cryptographic operation including the same may have more enhanced resistance to side-channel attacks. As a result, the cryptography circuitry100may provide PQC having an improved security level.

The random number generator120may generate a random number RN and may provide the random number RN to the processing circuit140. The random number generator120may generate a random number RN in an arbitrary manner. For example, the random number generator120may include a true random number generator and/or a pseudo random number generator, and may generate a random number RN having a length required by the processing circuit140. In some embodiments, the random number generator120may generate a random number RN in response to the request of the processing circuit140. Further, in some embodiments, the cryptography circuitry100may include a plurality of processing circuits, and the random number generator120may commonly provide a random number RN to two or more processing circuits. As will be described later, the random number RN may be used to generate a generator, or may be used to generate an input for modular multiplication (e.g., the second input b). Herein, the random number RN used to generate the generator may be referred to as a first random number, and the random number RN used to generate the input of modular multiplication may be referred to as a second random number. In some embodiments, the first random number and the second random number may be respectively generated by different random number generators.

The processing circuit140may receive a first input a and a second input b, and may generate a result c of a modular multiplication from the first input a and the second input b. For example, the processing circuit140may perform modular multiplication using the first input a and the second input b to generate the result c. The first input a and the second input b may be arbitrary multi-bit values that are required for an operation in cryptographic operation. For example, as will be described later with reference toFIG.10, the first input a may correspond to a value based on a secret key or a private key, and the second input b may correspond to a value based on a random number (i.e., a second random number). Further, the processing circuit140may receive a random number RN from the random number generator120and may access the memory160. The processing circuit140may generate a generator based on the random number RN, and may create at least one lookup table LUT based on the generator. An example of the operation of the processing circuit140will be described later with reference toFIG.2.

The processing circuit140may have any structure that performs the above-described operation. For example, the processing circuit140may include at least one programmable component (e.g., a processor), such as a central processing unit (CPU), a digital signal processor (DSP), a graphics processing unit (GPU), a neural network processing unit (NPU), and the like, and may include reconfigurable components such as field programmable gate arrays (FPGAs), and the like, and may include a component that provides a fixed function, such as an intellectual property (IP) core. As used herein, IP cores may self-contained discrete units that provide a macro function to the system. Those skilled in the art will appreciate that the disclosed IP cores are physically implemented by electronic (or optical) circuits, such as logic circuits, discrete components, microprocessors, hard-wired circuits, memory elements, wiring connections, buses, communication links, and the like, which may be formed using semiconductor-based fabrication techniques or other manufacturing technologies.

The memory160may be accessed by the processing circuit140and may include at least one lookup table LUT. At least one lookup table LUT may be created and written to the memory160by the processing circuit140, and may be referenced by the processing circuit140to generate the result c of the modular multiplication from the first input a and the second input b. In some embodiments, while generating the result c of the modular multiplication, the memory160may be accessed by the processing circuit140a constant number of times independently of the values of the first input a and the second input b, and thus equal power consumption may be achieved.

The memory160may be any storage medium that stores at least one lookup table LUT. For example, the memory160may include a volatile memory such as dynamic random access memory (DRAM), static random access memory (SRAM), and the like, and may also include non-volatile memory such as flash memory, resistive random access memory (RRAM), and the like. Also, the memory160may include registers including a plurality of latches.

FIG.2is a flowchart showing a method for modular multiplication according to an exemplary embodiment of the inventive concept. As shown inFIG.2, the method ofFIG.2may include a plurality of operations S10to S60. In some embodiments, the method ofFIG.2may be performed by the processing circuit140ofFIG.1. For example, at least one processor may access a non-transitory computer-readable recording medium (e.g., a semiconductor memory device, an optical disk, a magnetic disk, etc.) storing a series of instructions, and may perform the method ofFIG.2by executing the series of instructions. Hereinafter,FIG.2will be described with reference toFIG.1.

Referring toFIG.2, a generator may be generated based on a random number RN in operation S10. For example, the random number generator120may generate a random number RN, and the processing circuit140may generate a generator based on the random number RN. Public key-based encryption may use modular multiplication in finite field or Galois field GF(p). The characteristic of the finite field GF(p) may be a prime number p, and GF(p) may be defined by [Equation 1] below.

GF⁡(p)={gi⁢⁢mod⁢⁢p;i=0,…⁢,p-2}⋃{0}[Equation⁢⁢1]

[Equation 1] may mean that the elements of the finite field GF(p) excluding zero must always have i expressed as “gimod p”. Accordingly, the generator g may depend on the prime number p. The processing circuit140may generate a generator g based on the random number RN, and even in modular multiplications where the input of modular multiplication, for example, the first input a corresponding to the secret key, is the same, the modular multiplications may consume different power and consequently reduce predictability. An example of operation S10will be described later with reference toFIG.3.

In operation S20, at least one lookup table LUT may be created. For example, the processing circuit140may create at least one lookup table LUT based on the generator g generated in operation S10. Modular multiplication of the first input a and the second input b may be expressed as [Equation 2] below.

c=a*b⁢⁢mod⁢⁢p=Exp⁡[Log⁡[a]+Log⁡[b]][Equation⁢⁢2]

In addition, in [Equation 2], the function Exp and the function Log may be defined as in [Equation 3] and [Equation 4] below.

Exp⁡[i]=gi⁢⁢mod⁢⁢p[Equation⁢⁢3]Log⁡[gi⁢⁢mod⁢⁢p]=i[Equation⁢⁢4]

In [Equation 3], the output of the function Exp may have a value of 1 to (p−1) (1≤Exp[i]≤p−1), and in [Equation 4], the output of the function Log may have a value of 0 to (p−2) (0≤Log[gimod p]≤p−2). For example, when the prime number p is 7 and the generator g is 3, the value of the modular multiplication “3*4 mod 7” of 3 and 4 may be 5. According to [Equation 4], Log[3] and Log[4] may be 1 and 4, respectively, and according to [Equation 2] and [Equation 3], Exp[1+4] is 5, which can be equal to 5 calculated earlier. Accordingly, the processing circuit140may create at least one lookup table LUT and the at least one lookup table LUT may include a lookup table (which may be referred to herein as the first lookup table) including pairs of input and output of the function Log and a lookup table (which may be referred to herein as a second lookup table) including pairs of input and output of the function Exp, and the processing circuit140may perform modular multiplication based on the created lookup tables.

In operation S30, at least one lookup table LUT may be written to the memory160. For example, the processing circuit140may write at least one lookup table LUT created in operation S20to the memory160. Accordingly, preparation for performing modular multiplication on a given prime number p and generator g may be completed. At least one lookup table LUT stored in the memory160may be used for at least one modular multiplication, and the update timing of the at least one lookup table LUT may be determined in various ways. For example, the processing circuit140may perform operations S10to S30per one modular multiplication, perform operations S10to S30in units of a predefined number of modular multiplications, and perform operations S10to S30in a single cryptographic operation unit including modular multiplications. Further, the processing circuit140may perform operations S10to S30when power is supplied to the cryptography circuitry100or a predefined event such as an idle state occurs.

In operation S40, a first input a and a second input b may be received. For example, as described above with reference toFIG.1, the cryptographic operation may include a plurality of modular multiplications, and the processing circuit140may receive a first input a and a second input b for modular multiplication of the first input a and the second input b.

In operation S50, the memory160may be accessed. For example, the processing circuit140may access the memory160based on the first input a and the second input b received in operation S40. The processing circuit140may access the memory160a predetermined number of times independently of values of the first input a and the second input b. Accordingly, the power consumed during modular multiplication may be equal despite variations in the first input a and the second input b. Examples of at least one lookup table LUT stored in the memory160will be described later with reference toFIGS.6,7A, and7B, and an example of operation S50will be described later with reference toFIG.8.

In operation S60, the result c of the modular multiplication may be generated. For example, the processing circuit140may generate a result c of the modular multiplication based on values obtained from at least one lookup table LUT by accessing the memory160in operation S50.

FIG.3is a flowchart showing a method for modular multiplication according to an exemplary embodiment of the inventive concept. Specifically, the flowchart ofFIG.3shows an example of operation S10ofFIG.2. As described above with reference toFIG.2, a generator may be generated based on a random number RN in operation S10′ ofFIG.3. As shown inFIG.3, operation S10′ may include operations S12and S14, andFIG.3will be described below with reference toFIG.1.

Referring toFIG.3, in operation S12, a plurality of candidate generators may be obtained based on a modulus. For example, as described above with reference toFIG.2, the cryptographic operation may include modular multiplication with a prime number p as a modulus, and there may be a plurality of candidate generators that are smaller than the prime number p and satisfy [Equation 1]. For example, each of the plurality of candidate generators may correspond to generator g such that a finite field GF(p) is a union of {gimod p; i=0, . . . , p−2} and {0}. The processing circuit140may acquire a plurality of candidate generators depending on the prime number p in various ways. For example, the processing circuit140may sequentially calculate a plurality of candidate generators based on the prime number p, and as will be described later with reference toFIGS.4and8, obtain a plurality of generators by accessing a memory (e.g., memory160inFIG.1) in which a plurality of candidate generators are stored. Examples of a plurality of candidate generators will be described later with reference toFIGS.5A to5C.

In operation S14, one candidate generator may be selected based on the random number RN. For example, the processing circuit140may select one of a plurality of candidate generators obtained in operation S12based on a random number RN, and use the selected candidate generator g to create at least one lookup table LUT. Accordingly, the generator g may be selected at random, and the predictability of a side-channel attack is significantly reduced. In some embodiments, the processing circuit140may calculate a generator g from the modulus and the random number RN based on a predefined function, differently from that shown inFIG.3. The generator g may be changed based on a random number RN.

FIG.4is a block diagram illustrating a memory400according to an exemplary embodiment of the inventive concept. Specifically, the block diagram ofFIG.4is an example of the memory160ofFIG.1and shows data stored in the memory400.

Referring toFIG.4, the memory400may include a first lookup table LUT1and a second lookup table LUT2, and may include a plurality of candidate generators420. For example, as shown inFIG.4, the first lookup table LUT1may be stored in an area corresponding to the first address ADR1, and the second lookup table LUT2may be stored in an area corresponding to the second address ADR2, and the plurality of candidate generators420may be stored in an area corresponding to the third address ADR3. In some embodiments, different from that shown inFIG.4, at least some of the first lookup table LUT1, the second lookup table LUT2, and the plurality of candidate generators420may be stored in a memory other than the memory400. For example, the first lookup table LUT1and the second lookup table LUT2may be stored in a volatile memory device such as DRAM, SRAM, or the like, and moreover, the plurality of candidate generators420may be stored in a nonvolatile memory device such as a flash memory or ROM.

The first lookup table LUT1may include, as entries, pairs of inputs and outputs of the function Log defined in [Equation 4]. That is, in [Equation 4] defined by the generator g and the prime number p, the first lookup table LUT1may include pairs of an input corresponding to “gimod p” and an output corresponding to i. The input of the function Log, that is, “gimod p”, may have one of (p−1) different values, and accordingly, the first lookup table LUT1may include (p−1) entries. The processing circuit140may obtain outputs of a function Log corresponding to the first input a and the second input b of the modular multiplication from the first look-up table LUT1. An example of the first lookup table LUT1will be described later with reference toFIG.6.

The second lookup table LUT2may include, as entries, pairs of inputs and outputs of the function Exp defined in [Equation 3]. That is, in [Equation 3] defined by the generator g and the prime number p, the second lookup table LUT2may include pairs of an input corresponding to i and an output corresponding to “gimod p”. As defined in [Equation 1], the input of the function Exp, that is, i, may have one of (p−1) different values, and accordingly, the second lookup table LUT2may include (p−1) entries. In some embodiments, the second lookup table LUT2may include a number of entries different from (p−1). The processing circuit140may obtain an output of a function Exp corresponding to values calculated from values obtained from the first lookup table LUT1and from the second lookup table LUT2, and generate a value obtained from the second lookup table LUT2as a result c of modular multiplication. Examples of the second lookup table LUT2will be described later with reference toFIGS.7A and7B.

The memory400may store a plurality of candidate generators. For example, in a cryptographic operation, the modulus of modular multiplication may be predefined as a prime number p, and a plurality of candidate generators depending on the prime number p may also be calculated in advance based on [Equation 1]. Among the algorithms being discussed in PQC, CRYSTALS-KYBER may define the value of the prime number p as 3329 (p=3329), and Falcon may define the value of the prime number p as 12289 (p=12289), and CRYSTALS-Dilithium may define a prime value of p as 8380417 (p=8380417).

FIGS.5A to5Care diagrams illustrating examples of a plurality of candidate generators according to an exemplary embodiment of the inventive concept. Specifically,FIGS.5A to5Cshow a plurality of candidate generators divided for purposes of illustration in CRYSTALS-KYBER, which defines the prime number p, that is, 3329.

As shown inFIGS.5A to5C, there may be a total of 1536 candidate generators for the finite field GF(p) based on the prime number p of 3329. 1536 candidate generators may be smaller than the prime number p. The (p−1) remainders obtained by dividing each of the (p−1) numbers from the zero power to the (p−2) power of the candidate generator by the prime number p may correspond one-to-one to a set including numbers from 1 to (p−1). As described above with reference toFIG.3, the processing circuit140may select one of 1536 candidate generators based on a random number RN, and such a randomly selected generator may be used to create at least one lookup table LUT for modular multiplication, for example, the first lookup table LUT1and the second lookup table LUT2ofFIG.4.

FIG.6is a diagram illustrating a lookup table according to an exemplary embodiment of the inventive concept. Specifically,FIG.6shows an example of the first lookup table LUT1stored in the memory400ofFIG.4. As described above with reference toFIG.4, the first lookup table LUT1′ ofFIG.6may include input and output pairs of the function Log defined in [Equation 4] as entries.

Referring toFIG.6, the first lookup table LUT1′ may include an output Log[y] of a function Log corresponding toy sequentially increasing from 1 to (p−1). For example, as shown inFIG.6, the first lookup table LUT1′ may include a pair of y, which is 1, and an output xi of a function Log corresponding to y, and include a pair of y, which is (p−1) and an output xp-1of the function Log corresponding to y. y (or a value converted from y) of the first lookup table LUT1′ may correspond to an address of the memory400ofFIG.4, and the output of the function Log corresponding to y may correspond to data stored in the area accessed by the corresponding address.

FIGS.7A and7Bare diagrams illustrating examples of a lookup table according to exemplary embodiments of the inventive concept. Specifically,FIGS.7A and7Billustrate examples of the second lookup table LUT2stored in the memory400ofFIG.4, respectively. As described above with reference toFIG.4, the second lookup table LUT2′ ofFIG.7Aand the second lookup table LUT2″ ofFIG.7Bmay include pairs of inputs and outputs of the function Exp defined in [Equation 3] as entries.

Referring toFIG.7A, the second lookup table LUT2′ may include an output Exp[x] of a function Exp corresponding to x sequentially increasing from 0 to (2p−4). As mentioned above, the output of the function Log defined by [Equation 4] may have a value of 0 to (p−2) (0≤Log[gimod p]≤p−2), and accordingly, the value of the input “Log[a]+Log[b]” of the function Exp in [Equation 1] may have a value of 0 to (2p−4) (0≤Log[a]+Log[b]≤2p−4). Accordingly, the second lookup table LUT2′ may include (2p−3) entries. For example, as shown inFIG.7A, the second lookup table LUT2″ may include a pair of x, which is zero, and output 1 of the function Exp corresponding to x, and a pair of x, which is (2p−4), and output “gp-3mod p” of the function Exp corresponding to x. x (or a value converted from x) of the second lookup table LUT2′ may correspond to an address of the memory400ofFIG.4, and the output of the function Exp corresponding to x may correspond to data stored in the area accessed by the corresponding address. As shown inFIG.7A, the outputs of the function Exp corresponding to x in (p−1) to (2p−4) may match the outputs of the function Exp corresponding x in zero to (p−3). Accordingly, the second lookup table LUT2ofFIG.4may have a reduced size like the second lookup table LUT2″ ofFIG.7B.

Referring toFIG.7B, the second lookup table LUT2″ may include an output Exp[x] of a function Exp, corresponding to x sequentially increasing from 1 to (p−1). For example, as shown inFIG.7B, the second lookup table LUT2″ may include a pair of x, which is zero, and an output 1 of the function Exp corresponding to x, and a pair of x, which is (p−2), and an output “gp-2mod p” of the function Exp corresponding to x. x (or a value converted from x) of the second lookup table LUT2″ may correspond to an address of the memory400ofFIG.4, and the output of the function Exp corresponding to x may correspond to data stored in the area accessed by the corresponding address. As shown inFIG.7B, an example of an operation of referring to the second lookup table LUT2″ including (p−1) entries will be described later with reference toFIG.9.

FIG.8is a message diagram showing a method for modular multiplication according to an exemplary embodiment of the inventive concept. Specifically, the message diagram ofFIG.8shows an example of operation S50ofFIG.2. As described above with reference toFIG.2, in operation S50′ ofFIG.8, the processing circuit840may access the memory860. As shown inFIG.8, operation S50′ may include a plurality of operations S51to S59. As shown inFIG.8, the memory860may include a first lookup table LUT1and a second lookup table LUT2. For convenience of illustration, it is shown inFIG.8that the processing circuit840communicates with the first lookup table LUT1and the second lookup table LUT2included in the memory860, respectively. The processing circuit840may access the memory860ofFIG.8.

Referring toFIG.8, in operation S51, the processing circuit840may generate an address ADR based on a first input a. For example, as shown inFIG.8, the processing circuit840may generate an address ADR from the first input a based on a predefined function f. The generated address ADR may be an address of an area in which an entry corresponding to the first input a is stored in the first lookup table LUT1. In some embodiments, as described above with reference toFIG.4, the memory860may sequentially store entries of the first lookup table LUT1(e.g., in the order shown inFIG.6) from the area corresponding to the first address ADR1, and the function f may generate the address ADR by summing up the first address ADR1and the address offset corresponding to the first input a.

In operation S52, the processing circuit840may provide the address ADR to the memory860, and the memory860may receive the address ADR. In some embodiments, the processing circuit840may provide a read command to the memory860along with the address ADR. In operation S53, the memory860may provide the value included in the first lookup table LUT1to the processing circuit840. For example, the memory860may store the output Log[a] of the function Log corresponding to the first input a in the area of the first lookup table LUT1corresponding to the address ADR, and as shown inFIG.8, provide Log[a] to the processing circuit840in response to the address ADR. Herein, as in operation S52and operation S53, the entire operation in which the processing circuit840provides an address to the memory860and the memory860provides data in response to the address may be referred to as a single access to the memory860.

In operation S54, the processing circuit840may generate the address ADR based on the second input b. For example, similar to operation S51, the processing circuit840may generate an address ADR from the second input b based on a predefined function f. The generated address ADR may be an address of an area in which an entry corresponding to the second input b is stored in the first lookup table LUT1.

In operation S55, the processing circuit840may provide the address ADR to the memory860, and the memory860may receive the address ADR. In some embodiments, the processing circuit840may provide a read command to the memory860along with the address ADR. In operation S56, the memory860may provide the value included in the first lookup table LUT1to the processing circuit840. For example, the memory860may store the output Log[b] of the function Log corresponding to the second input b in the area of the first lookup table LUT1corresponding to the address ADR, and provide Log[b] to the processing circuit840in response to the address ADR, as shown inFIG.8.

In some embodiments, operations S54to S56may be performed in parallel with operations S51to S53. For example, the memory860may include a plurality of ports and may provide parallel accesses simultaneously. Accordingly, the processing circuit840accesses the memory860in parallel through the two ports to simultaneously acquire the output Log[a] of the function Log corresponding to the first input a and the output Log[b] of the Log corresponding to the second input b.

In operation S57, the processing circuit840may generate the address ADR based on the outputs Log[a] and Log[b] of the function Log. For example, as shown inFIG.8, the processing circuit840may sum up Log[a] received in operation S53and Log[b] received in operation S56, and generate an address ADR from the sum of Log[a] and Log[b] based on a predefined function h. The generated address ADR may be an address of an area in which an entry corresponding to the sum of Log[a] and Log[b] is stored in the second lookup table LUT2. In some embodiments, as described above with reference toFIG.4, the memory860may sequentially store entries of the second lookup table LUT2(e.g., in the order shown inFIG.7A or7B) from the area corresponding to the second address ADR2, and the function h may generate the address ADR by summing the second address ADR2and an address offset corresponding to the sum of Log[a] and Log[b].

In some embodiments, when the second lookup table LUT2includes (2p−3) entries as described above with reference toFIG.7A, the processing circuit840may generate an address ADR corresponding to one of the (2p−3) entries. In addition, in some embodiments, when the second lookup table LUT2includes (p−1) entries as described above with reference toFIG.7B, the processing circuit840may generate an address ADR corresponding to one of the (p−1) entries. When the second lookup table LUT2includes (p−1) entries, an example of operation S57will be described later with reference toFIG.9.

In operation S58, the processing circuit840may provide the address ADR to the memory860, and the memory860may receive the address ADR. In some embodiments, the processing circuit840may provide a read command to the memory860along with the address ADR. In operation S59, the memory860may provide the value included in the second lookup table LUT2to the processing circuit840. For example, the memory860may store an output Exp[Log[a]+Log[b]] of the function Exp corresponding to the sum of Log[a] and Log[b] in the area of the second lookup table LUT2corresponding to the address ADR and provide Exp[Log[a]+Log[b]] to the processing circuit840in response to the address ADR, as shown inFIG.8.

FIG.9is a flowchart showing a method for modular multiplication according to an exemplary embodiment of the inventive concept. Specifically, the flowchart ofFIG.9shows an example of operation S57ofFIG.8. As described above with reference toFIG.8, the address ADR may be generated based on the outputs Log[a] and Log[b] of the function Log in operation S57′ ofFIG.9. As shown inFIG.9, operation S57′ may include operation S57_2, operation S57_4, and operation S57_6. In the example ofFIG.9, the processing circuit820ofFIG.8may refer to the second lookup table LUT2″ ofFIG.7B, andFIG.9will be described with reference toFIGS.7B and8.

Referring toFIG.9, (p−1) and the sum of Log[a] and Log[b] may be compared in operation S57_2. As described above with reference toFIG.7A, the outputs of the function Exp corresponding to inputs from (p−1) to (2p−4) may match the outputs of the function Exp corresponding to inputs from zero to (p−3). Accordingly, the processing circuit840may compare the sum of Log[a] and Log[b] with (p−1). As shown inFIG.9, when the sum of Log[a] and Log[b] is greater than or equal to (p−1) (operation S57_2, YES), operation S57_4may be performed subsequently, and when the sum of Log[a] and Log[b] is less than (p−1) (operation S57_2, NO), operation S57_6may be subsequently performed.

When the sum of Log[a] and Log[b] is greater than or equal to (p−1) (operation S57_2, YES), the address ADR may be generated from Log[a], Log[b] and p based on the function h in operation S57_4. For example, as shown inFIG.9, the processing circuit840may use a value obtained by subtracting (p−1) from the sum of Log[a] and Log[b] as an input of the function h. On the other hand, when the sum of Log[a] and Log[b] is less than (p−1) (operation S57_2, NO), the address ADR may be generated from the sum of Log[a] and Log[b] based on the function h in operation S57_6. Accordingly, the second lookup table LUT2″ ofFIG.7Bmay have a reduced size.

FIG.10shows an example of a cryptographic operation according to an exemplary embodiment of the inventive concept. Specifically,FIG.10shows an example of a polynomial multiplication. For example, as described above, CRYSTALS-KYBER may require modular multiplications using a prime number p of 3329 as a modulus. Although a third-order polynomial is illustrated inFIG.10, exemplary embodiments of the inventive concept are not limited thereto. Hereinafter,FIG.10will be described with reference toFIG.1.

Referring toFIG.10, multiplication of coefficients of a polynomial may be performed by multiplication of the polynomials. For example, as shown inFIG.10, a third polynomial P3may be generated by multiplying the first polynomial P1by the second polynomial P2. The coefficients a0, a1, a2, and a3of the first polynomial P1may correspond to the secret key, and the coefficients b0, b1, b2, and b3of the second polynomial P2may correspond to a random number (i.e., a second random number).

The third polynomial P3may be a third-order polynomial, such as the first polynomial P1and the second polynomial P2. For this, a term having a power of 4 or more, that is, a term including x4, x5, or x6, may be divided by x4. Accordingly, the coefficients c0, c1, c2, and c3of the third polynomial P3may be calculated, as shown inFIG.10, from the coefficients a0, a1, a2, and a3of the first polynomial P1and the coefficients b0, b1, b2, and b3of the second polynomial P2. Specifically, as shown in the table ofFIG.10, in order to calculate the coefficients c0, c1, c2, and c3of the third polynomial P3, a total of 16 modular multiplications may be required.

As shown inFIG.10, each of the coefficients a0, a1, a2, and a3of the first polynomial P1may be used for four modular multiplications, and each of the coefficients b0, b1, b2, and b3of the second polynomial P2may also be used for four modular multiplications. Side-channel attacks may attempt hacking based on power consumption and/or electromagnetic fields generated by a plurality of modular multiplications, and accordingly, there is a risk of exposure of the coefficients a0, a1, a2, and a3of the first polynomial P1corresponding to the secret key. However, as described above with reference to the drawings, due to the memory being constantly accessed independently of the values of the inputs, in the 16 modular multiplications ofFIG.10, power consumption and electromagnetic fields may be equal. In addition, because the generator is randomly selected, different power consumption and/or electromagnetic fields may be generated even if the modular multiplication is repeated. Accordingly, the predictability of the coefficients a0, a1, a2, and a3of the first polynomial P1is significantly reduced, and the secret key is safely protected from side-channel attacks.

As described above with reference toFIG.2, the update timing of at least one lookup table LUT may be determined in various ways. In some embodiments, the processing circuit140may generate a generator before performing each of the 16 modular multiplications illustrated inFIG.10, and may create at least one lookup table LUT. Further, in some embodiments, the processing circuit140may generate a generator before performing the multiplication of the first polynomial P1by the second polynomial P2, and may commonly use at least one lookup table LUT generated based on the same generator in 16 modular multiplications for multiplication of the first polynomial P1by the second polynomial P2.

FIG.11is a block diagram showing devices according to an exemplary embodiment of the inventive concept. Specifically, the block diagram ofFIG.11shows a first device10and a second device20communicating with each other through a communication link CL in a secure environment. The first device10and the second device20may be any device (e.g., a computing device) capable of performing the cryptographic operation described above with reference to the drawings. The communication link CL may be any appropriate communication channel that allows communication between or among one or more computing systems and/or devices, such as, for example, the first device10and the second device20. The communication link CL may be wired, wireless, or any combination thereof.

The first device10may include a memory11, at least one processor13, an authentication logic15, a cryptography logic17, and a communication logic19. Although not shown inFIG.11, similar to the first device10, the second device20may include a memory, at least one processor, an authentication logic, a cryptography logic, and a communication logic. Each of the components of the first device10(e.g., the authentication logic15, the cryptography logic17, and the communication logic19, etc.) in a secure environment may be implemented as hardware, software, firmware, or a combination thereof. In some embodiments, each of the components of the first device10(e.g., the authentication logic15, the cryptography logic17, and the communication logic19, etc.) may form at least one processor13or may be part of another hardware component. Further, in some embodiments, each of the components of the first device10(e.g., the authentication logic15, the cryptography logic17, and the communication logic19, etc.) may be implemented as a circuit or electrical devices (e.g., authentication circuitry, cryptography circuitry, and communication circuitry). In addition, two or more components of the first device10(e.g., the authentication logic15, the cryptography logic17, and the communication logic19, etc.) may be integrated into one component.

The at least one processor13may be implemented as a single or multiple core processor, a digital signal processor, a microcontroller, or another type of processor. The memory11may store various data and/or software used during the operation of the first device10. For example, the memory11may be accessed by at least one processor13and may store an operating system (OS), an application, a program library, and/or software. In some embodiments, the memory11may include a secure area, and a secret key may be stored in the secure area. In addition, in some embodiments, the memory11may store at least one lookup table referenced during modular multiplication in the secure area.

The authentication logic15may perform various operations for authentication. For example, the authentication logic15may execute a hash function to generate a hash value of a message transmitted and received over the communication link CL. Further, the authentication logic15may generate a signature to be transmitted to the second device20or verify a signature received from the second device20, based on the secret key and/or hash value. In some embodiments, the authentication logic15may perform modular multiplication upon generation and/or verification of a signature, and as described above with reference to the drawings, due to the modular multiplication that is resistant to side-channel attacks, the generation and/or verification of a signature may be safely performed.

The cryptography logic17may perform cryptographic and/or secure operations. In some embodiments, the cryptography logic17may be embedded in the first device10as a cryptographic engine, an independent secure co-processor, an accelerator included in at least one processor13, or the like. Further, in some embodiments, the cryptography logic17may, despite its name, be embedded in the first device10as standalone software or firmware. In some embodiments, the cryptography logic17may perform modular multiplication when performing key generation, encryption and/or decryption, and as described above with reference to the drawings, key generation, encryption, and/or decryption may be safely performed due to the modular multiplication resistant to side-channel attacks.

The communication logic19may transmit a message and signature to the second device20through a communication link CL. A message transmitted through the communication link CL may not be encrypted or may be encrypted by the cryptography logic17. Further, the communication logic19may provide a message and/or a signature received from the second device20through the communication link CL to the authentication logic15and/or the cryptography logic17.

FIGS.12A to12Care block diagrams illustrating examples of a device for performing a cryptographic operation according to exemplary embodiments of the inventive concept. As described above with reference to the drawings, modular multiplication that is resistant to side-channel attacks may be performed, and accordingly, a cryptographic operation with a higher level of security may be provided.

Referring toFIG.12A, the identification device30amay include a communication interface31. The identification device30amay transmit a response RES including identification information of the identification device30ato the outside in response to a request REQ received from the outside. For example, the identification device30amay be a smart card, an RFID, or the like, and the identification information included in the response RES may be used to identify the user of the identification device30a. The identification information included in the response RES may be encrypted by cryptography circuitry included in the communication interface31.

Referring toFIG.12B, a storage device30bmay include an encryption engine32and a storage33. The storage device30bmay store the data DATA received from the outside or transmit the stored data DATA to the outside. The storage device30bmay encrypt data DATA received from the outside for security of stored data, and store encrypted data ENC encrypted by the encryption engine32in the storage33. In addition, the encryption engine32may decrypt the encrypted data ENC read from the storage33and transmit the decrypted data DATA to the outside. For example, the storage device30bmay be a portable storage device or a storage device of a storage server.

Referring toFIG.12C, a communication device30cmay include a public key generator34and a modem35. The communication device30cmay communicate with another communication device by receiving the signal RX from the other communication device or transmitting the signal TX to the other communication device. The public key generator34may generate a public key P_KEY based on the secret key, and the modem35may transmit the encrypted signal TX or decrypt the signal RX, based on the public key P_KEY. That is, the communication device30cmay perform secure communication with another communication device, and for example, the communication device30cmay be a portable wireless communication device.

While the inventive concept has been particularly shown and described with reference to embodiments thereof, it will be understood that various changes in form and details may be made therein without departing from the spirit and scope of the following claims.