WO2015156621A1 - Authentication apparatus and method - Google Patents

Abstract

Disclosed is an authentication apparatus using a public key encryption algorithm. An apparatus according to an embodiment generates a first instant public key through a random number generation process in response to an electronic signature generation request corresponding to a message. Further, the apparatus calculates and uses a first instant private key making a pair with the first instant public key, using the first instant public key.

Description

Authentication device and method

It relates to an authentication device and method, and more particularly to an improvement in the robustness against security attacks of a public key cryptographic algorithm based authentication device.

Signature techniques using public key cryptographic algorithms are used for device authentication and message electronic signatures. For example, the RSA (Rivest Shamir Adleman) algorithm is an Internet encryption and authentication method that encrypts and decrypts a public key and a private key as a set. The private key is stored on a device, and the public key is stored on an external device such as a certificate authority. Delivered and stored.

On the other hand, the private key is a target of security attack, such as a side channel attack because the signature can be forged when the private key is exposed / leaked based on the public key algorithm, such as RSA. Among subchannel attack methods, DPA (Differential Power Analysis) attack, which collects and statistically analyzes a large amount of data, is known to be very powerful.

On the other hand, PUF (Physically Unclonable Function) may provide an unpredictable digital value. Individual PUFs are given the correct manufacturing process, and even if manufactured in the same process, the digital values provided by the individual PUFs are different. PUF may be referred to as Physical One-Way Function practically impossible to be duplicated (POWF).

This non-replicable characteristic of the PUF may be used to generate an identifier of the device for security and / or authentication. For example, PUF may be used to provide a unique key to distinguish devices from one another.

Korean Patent Registration No. 10-1139630 (hereinafter '630 patent) has been presented a method for implementing the PUF. The '630 patent proposes a method in which a process variation of a semiconductor is used to probabilistically determine whether an inter-layer contact or a via is formed between conductive layers of the semiconductor. It became.

According to embodiments, an authentication apparatus and an authentication method that are robust against side channel attacks are presented. For example, an authentication apparatus and method are disclosed that make a DPA attack impossible and meaningless while using a public key based algorithm. According to embodiments, the public-private key pair is a fixed value and is not used repeatedly, but instead can be instantaneously generated and used when authentication is required.

According to one side, an authentication apparatus including at least one processor and performing an authentication procedure according to RSA, which is an encryption algorithm using a public key, such as an asymmetric key encryption algorithm, is provided. The device has a predetermined private key p, q. According to an embodiment, the apparatus may further include: a generator configured to generate a first instant public key in response to a digital signature corresponding to the algorithm; A calculator configured to calculate a first instant private key paired with the first instant public key in the algorithm by using the fixed private key and the first instant public key; And a processing unit for generating an electronic signature by the algorithm using the first instant private key. The generation unit, the calculation unit, and the processing unit may be implemented at least temporarily by the at least one processor. According to an embodiment, the apparatus may further include a communication unit configured to transmit a message to be transmitted to the counterpart device together with the electronic signature and the first instant public key.

According to an embodiment, the device generates and holds the fixed private key through a public key key generation algorithm. The fixed private key is used to calculate the first instant private key using the first instant public key and to generate a fixed public key that is passed to another device in the issuing process prior to use and used together for later signature verification. do. By way of example, but not limitation, the authentication device may further include a PUF that provides a hardware fingerprint using a randomly occurring process variation. According to an embodiment, the value of this PUF may be used directly or indirectly as the fixed private key value. In this case, there is no need to store the fixed private key directly in a memory, thereby protecting the fixed private key from physical attack. This is also strongly guaranteed that the public key-private key pair cannot be arbitrarily created by another device since it is strongly guaranteed that the fixed private key exists only in the device. In another embodiment, the value of the PUF may be used directly or indirectly to generate instant public keys. For example, it may be used as a seed value or a source value in the random number generation process. In this case, by using the PUF as a source value of the random number generation algorithm, the random number generation results generated for each device are independent of each other and have a different value. Additional effects can be expected to make them different.

Meanwhile, in response to receiving the retransmission request from the counterpart device, it may correspond to the following. In case of retransmission request due to a simple communication error, the created message can be retransmitted. However, in other cases, for example, if there is a suspicious signature or attack, the first instant public key is discarded, and a new second instant public key different from this is generated and the digital signature is generated and transmitted again.

According to an embodiment, when it is determined in the calculation result that the first instant private key paired with the first instant public key does not exist, the generation unit may generate a second instant public that is different from the first instant public key. Create a key. The calculator then calculates a second instant private key paired with the second instant public key in the algorithm. On the other hand, instead of performing the random number generation process to generate the second instant public key, the generation unit may determine and provide the number of the second instant public key by adding the integer 2 to the first instant public key. The integer "2" added to the first instant public key is exemplary and may be changed to another value. If the encryption algorithm is a RSA-CRT (Chinese Remainder Theorem) algorithm, the first instant private key calculated by the calculator includes a first dP value and a first dQ value. In this RSA-CRT embodiment, if it is determined that none of the first dP value and the first dQ value according to the calculation result is present, the generation unit generates a second instant different from the first instant public key. Generate a public key. The calculator calculates a second dP value and a second dQ value paired with the second instant public key in the algorithm.

According to another aspect, an authentication device including at least one processor and verifying an electronic signature transmitted by an external device according to a public key based encryption algorithm is provided, such as a certification authority (CA). The apparatus may include a processing unit for verifying the electronic signature using the fixed public key of the external device, and the first instant public key generated by the external device and transmitted together with the electronic signature. have.

According to an embodiment, the apparatus may further include a determining unit that determines that the first instant public key is invalid if the first instant public key is not three or more odd numbers. The processor and the determiner may be implemented at least temporarily by the at least one processor.

According to another aspect, an authentication device including at least one processor, comprising: a determination unit for determining whether a first instant public key received from an external device is a valid value; And a processing unit that encodes data to be transmitted using the fixed public key of the external device and the first instant public key held when the first instant public key is a valid value. The determining unit and the processing unit may be implemented at least temporarily by the at least one processor. For example, but not limited to, the first instant public key may be generated through a random number generation process in the counterpart device.

According to an embodiment, if the first instant public key is not an odd number of three or more, the determination unit may determine that the first instant public key is invalid. According to another aspect, an authentication apparatus including at least one processor and performing an authentication procedure according to a public key based encryption algorithm is provided. The apparatus may include: a generation unit generating a first instant public key through a random number generation process in response to the authentication procedure being performed; A calculator configured to calculate a first instant private key paired with the first instant public key in the algorithm using the first instant public key; And receiving a message encoded using the fixed public key previously held in the counterpart device and the first instant public key from the counterpart device receiving the first instant public key, by using the first instant private key. It may include a processing unit for decoding the message. The generation unit, the calculation unit, and the processing unit may be implemented at least temporarily by the at least one processor.

According to an embodiment, the authentication device may further include a PUF that provides a hardware fingerprint by using a randomly generated process variation. In this case, the random number generation process includes a random number generation algorithm using the hardware fingerprint value as a source value.

According to an embodiment, when it is determined in the calculation result that the first instant private key paired with the first instant public key does not exist, the generation unit may generate a second instant different from the first instant public key. Generate a public key. The calculator may calculate a second instant private key paired with the second instant public key in the algorithm.

According to yet another aspect, there is provided a non-one embodiment computer program stored on a computer-readable recording medium. The program may include the following set of instructions that, when executed on a computing device including a processor, cause the processor to operate. Instruction sets include: an instruction set for causing the processor to generate a first instant public key through a random number generation process in response to a digital signature generation request corresponding to the message; An instruction set for causing the processor to calculate a first instant private key paired with the first instant public key using the first instant public key; And an instruction set for causing the processor to generate an electronic signature by a public key-algorithm using the first instant private key.

According to yet another aspect, there is provided a non-one embodiment computer program stored on a computer-readable recording medium. The program may include the following set of instructions that, when executed on a computing device including a processor, cause the processor to operate. Instruction sets include: an instruction set for causing the processor to determine whether a first instant public key received with a message and an electronic signature from a counterpart device is valid; And a set of instructions for causing the processor to verify the electronic signature using the fixed public key of the external device stored in the computing device and the received first instant public key when the first instant public key is valid. It may include.

1 is a block diagram illustrating an authentication device for providing an instant public key and an instant private key, according to an exemplary embodiment.

2 is a block diagram illustrating an authentication apparatus for receiving and using an instant public key generated by a counterpart according to an embodiment.

3 is a flowchart illustrating an electronic signature verification process according to an embodiment.

4 is a flowchart illustrating an encoding and decoding process according to an embodiment.

5 is a flowchart illustrating processing in the case where an instant private key does not exist, according to an embodiment.

6 is a flowchart illustrating a process in a case where a private key does not exist when an RSA-CRT algorithm is applied according to an embodiment.

Hereinafter, embodiments will be described in detail with reference to the accompanying drawings. However, the scope of rights is not limited or limited by these embodiments. Like reference numerals in the drawings denote like elements.

The terminology used in the description below has been selected to be general and universal in the art to which it relates, although other terms may vary depending on the development and / or change in technology, conventions, and preferences of those skilled in the art. Therefore, the terms used in the following description should not be understood as limiting the technical spirit, and should be understood as exemplary terms for describing the embodiments.

In addition, in certain cases, there is a term arbitrarily selected by the applicant, and in this case, the meaning thereof will be described in detail in the corresponding description. Therefore, the terms used in the following description should be understood based on the meanings of the terms and the contents throughout the specification, rather than simply the names of the terms.

1 is a block diagram illustrating an authentication device for providing an instant public key and an instant private key, according to an exemplary embodiment. Device 100 may be at least a portion of a computing terminal that includes at least one processor. The computing terminal may be, but is not limited to, a smartphone, tablet, laptop, general purpose computer, server, dedicated terminal for encrypted communication, and the like. The device 100 performs an authentication procedure according to a public key based encryption algorithm, such as an asymmetric key encryption algorithm such as RSA.

According to an embodiment, the generating unit 110 of the apparatus 100 generates a first instant public-key "E" in response to the case where an electronic signature corresponding to the RSA algorithm is required. The generation of the first instant public key E may be performed through a random number generating process. On the other hand, the generated E must be an odd number of three or more. This is because even if they are prime or very large, they must be pseudo-prime. The generation unit 110 may check whether the generated E is odd and whether the value is not 1.

Meanwhile, according to an exemplary embodiment, the device 100 may include a PUF (not shown) that provides a hardware finger-print using a randomly generated semiconductor process variation. There are many examples of implementing PUF using semiconductor process variation. For example, a PUF may be implemented using a random formation-forming failure result of vias or inter-layer contacts disposed between conductive layers of a semiconductor. The specification of the '630 patent is incorporated herein by reference.

Meanwhile, in this exemplary situation, the hardware fingerprint provided by the PUF may be used for the fixed private key generation algorithm. The device has a fixed private key (p, q) which is basically 301, and a hardware fingerprint may be used as a candidate value of the fixed private key (p, q) when generating it. In this case, only the difference between the hardware fingerprint value and the actually generated fixed private key (p, q) value needs to be recorded in the memory. The value recorded is 32-bit enough, so it is impossible to infer the original static private key (p, q) using this value alone. It is also possible to quickly reproduce the fixed private key value from the hardware fingerprint value when needed.

  Meanwhile, in this exemplary situation, the hardware fingerprint provided by the PUF may be used for the random number generation algorithm. For example, a hardware fingerprint may be used as a seed value or seed key required by a random number algorithm operating in software and / or hardware.

When the first instant public key E is generated by the above Equation 1, the calculation unit 120 uses the first instant public key E according to an algorithm according to the calculation method defined in the RSA method, which is an RSA pair of E again. In other words, the first instant private-key "D" paired with E is calculated.

In this way, the instantaneous generation and calculation of the private key-public key, which is the subject of the key issuance process, has the following advantages. In the RSA scheme, the private key has {D, p, q} and the public key provided to the counterpart device has {E, N}. Where N is the product of p and q, and D and E are D × E = 1 mod (p-1) (q-1). Unlike E or N, which is passed to other devices or certification authorities, private keys {D, p, q} that exist only in (and must exist) inside the authentication device are subject to a security attack. Once D is known by a third party, direct digital signature forgery is possible. And if the third party knows the value of p and / or q without knowing D, then this RSA encryption is no longer valuable because it can be used in conjunction with an externally disclosed E to calculate D.

As mentioned earlier, side-channel attacks, such as differential power analysis (DPA), analyze the power consumption waveforms of a device, unlike actual power analysis (SPA) attacks that only observe one current consumption waveform. After collecting a large number of keyed waveforms, we try to obtain this D, p or q by statistical analysis. SPA attacks may be unsuccessful in noisy environments or in shielding power consumption, making them difficult to observe, but still DPA attacks threaten the algorithm's safety. This is because in the process of statistical analysis through multiple waveforms, other outliers such as noise may be canceled out and significant patterns may be found.

In the conventional RSA cryptographic algorithm, the authentication device has a fixed private key {D, p, q}, and the authentication authority as the other party has a fixed public key {E, N}. Therefore, the risk was that an attacker could collect multiple waveforms required for DPA by repeatedly requesting the device for digital signatures.

However, according to the above embodiment, at least D and E of the private key and the public key are not fixed values but dynamically changing values. In other words, when it is necessary to perform an encryption algorithm such as an electronic signature, instantaneously, D and E are generated. The generated D and E are used only once (one time), so even if the digital signature is collected by the attacker, it is statistically insignificant. Embodiments generate and use E and D, which are not fixed and dynamically changed, to prevent side channel attacks such as DPA attacks.

Moreover, as described above, even though the hardware fingerprint of the PUF used to randomly generate the first instant public key E is identical in design, it is impossible to physically duplicate the value. In addition, it is almost impossible to observe and analyze PUF values or structures externally. Therefore, according to this embodiment, it is also possible to prevent attacking the algorithm itself which generates a random E by using the PUF value as a seed.

As such, the first instant public key E is generated and the first instant private key D, which is a pair of Es, is calculated. In some cases, the D that satisfies Equation 2 may not exist.

If D does not exist, a valid " instant D-pair of instant E " cannot be made, so the generation unit 110 generates a second instant public key E 'different from the first instant public key E. Using the second instant public key E ', the calculator 120 calculates the second instant private key D' according to Equation 2. If D 'is present, E' and D 'are used; otherwise, this process can be repeated.

Here, the process of generating the second instant public key E 'by the generation unit 110 may be a process of generating a random number again, similarly to the process of creating the first instant public key E. FIG. However, other embodiments that are simpler than this process are possible. For example, instead of performing the random number generation process again, the generation unit 110 subtracts the number of integers (that is, the odd numbers immediately above E) from the first instant public key E that was generated but the corresponding D did not exist. 2 may be determined and provided as an instant public key E '. Herein, the integer "2" added to E to generate E 'is exemplary, and may be changed to another value. Regenerating E depending on the presence of D will be described again with reference to FIG. 5.

Meanwhile, the encryption algorithm may be an algorithm using a Chinese Remainder Theorem (CRT). In this case, the instant private key to be calculated with E is not D, but {dP calculated according to Equations 3 and 4 below. , dQ}.

In this RSA-CRT embodiment, if it is determined that none of the valid dP values and the valid dQ values corresponding to E is present according to the calculation of the calculation unit 120, E may be generated again. In this case, the random number generation process may be performed again, but E 'may be simply determined by adding 2 to E, and the dP' and dQ 'values corresponding to E' may be calculated. Details will be described again with reference to FIG. 6.

If a valid instant public key (E) and instant private key (D or {dP, dQ}) are determined through the above process, an RSA encryption algorithm may be performed. If the message M is signed to generate the electronic signature S, the processor 130 may perform the following process.

GenSign () is a digital signature generation function and is defined according to the RSA algorithm. The communication unit 140 transmits the generated digital signature S together with the message M to the counterpart device (such as a certification authority), but also transmits the instant public key E generated above as well. The counterpart device will then verify the digital signature S using this instant public key E together with the fixed public key N of the device 100 already having it. The above process will be described again with reference to FIG. 3.

On the other hand, when the other device encodes and sends a message using the instant public key E transmitted as described above, the device 100 may decode the message using the instant private key D (or dP, dQ) that it has together with p and q. Can be. This process is described below with reference to FIG.

Thus, although the risk of a security attack has been significantly lowered according to embodiments, there may be some other attack attempts that can be expected, and these other attacks may be implemented by the following embodiments. If an attacker can request a retransmission of a key several times in a very short time. In the case of a communication error, the apparatus 100 only retransmits an already generated generation without regenerating a signature by reusing an instant private key. If it is not a communication error, the generated instant public key may be discarded and a new instant public key may be generated. Whether or not a communication error can be confirmed by whether the communication Ack for the transmission message is received. Attack prevention alternatives that can be performed by the counterpart device will be described in more detail with reference to FIG. 2.

2 is a block diagram illustrating an authentication apparatus for receiving and using an instant public key generated by a counterpart according to an embodiment. The device 200 may be, for example, a Certification Authority (CA). In addition, the apparatus 200 may be at least a portion of a computing terminal including at least one processor, and the determination unit 210 and the processing unit 220, which will be described later, may be implemented at least temporarily by the processor.

The apparatus 200 according to an embodiment may include a fixed public key N of the external device, and a first instant generated by the external device as described in FIG. 1 and transmitted together with the message M and the digital signature S. FIG. By using the public key E, it may include a processing unit 220 for verifying the digital signature S.

When the message needs to be encoded and sent to the counterpart device, the processor 220 encodes the data M to be transmitted using the fixed public key N of the counterpart device held therein and the first instant public key E previously received. If M 'is normally encoded and transmitted to the counterpart device, the counterpart device will decode M' into M using its fixed private keys p, q and instant private keys D (or dP and dQ).

Meanwhile, according to an exemplary embodiment, the apparatus 200 may further include a determination unit 210 that determines whether the instant public key E sent from the counterpart device is valid. An attacker can anticipate an attack that generates and delivers a digital signature with both E and D set to 1. In this case, the digital signature generation and verification operation is not actually performed. Because E and D are used as exponential values in RSA operations, a value of 1 means that "1" square of the message for encoding-decoding is the same as no operation. At this point, from the CA's point of view, the signature verification result may be valid. Therefore, in order to prevent such a situation, the determination unit 210 checks whether the instant public key E received from the counterpart device is an odd number of three or more. So if E is even or E is 1, it can be determined to be invalid E.

Furthermore, when the E is repeatedly used more than a specified number of reuse times, the determination unit 210 according to another exemplary embodiment may recognize this as an abnormal situation and treat the instant public key E as invalid.

3 is a flowchart illustrating an electronic signature verification process according to an embodiment. As described above, the difference from the conventional RSA is that the device does not have a fixed private key D, and the counterpart certification authority does not have a fixed public key E of this device. Therefore, according to the embodiment, when authentication is required as described above with reference to FIGS. 1 and 2, an instant public key E and an instant private key D calculated therefrom are generated and utilized.

In the illustrated embodiment, the device has only p and q in the reservoir 301. And the certification authority has only N of the device's static public keys. If authentication is required, step 310 is performed. Step 310 is a process of generating a random instant public key E through a random number generation process, the generated E is an odd number of three or more. Generation and validation of the instant E are as described with reference to FIG. 1.

Then, in step 320, D, an RSA pair of instant public key E, is calculated. By the way defined in the RSA, one skilled in the art can easily understand this calculation of D. In step 330, an electronic signature S for message M to be transmitted is generated. In step 340, the instant public key E together with the message M and the digital signature S is transmitted to the certificate authority. Then, the certification authority will use the previously received E together with N, which is previously performed, in step 350 of performing the digital signature verification algorithm. Prior to performing step 350, the certification authority may go through a process of verifying whether the received E is valid, which has been described in detail with reference to FIG.

4 is a flowchart illustrating an encoding and decoding process according to an embodiment. The process by which the certification authority encodes the message M and sends it to the device is shown. The certification authority encodes the data M to be transmitted using the fixed public key N of the counterpart device previously held in step 410 and the instant public key E previously received. The encoded message M 'is transmitted to the device in step 420, and the device uses M's M' with its fixed private keys p, q and instant private keys D (or dP and dQ) in step 430. Can be decoded.

5 is a flowchart illustrating processing in the case where an instant private key does not exist, according to an embodiment. In step 510, the generation unit of the device generates the instant publisher E through a random number generation process. In operation 520, the calculation unit of the device calculates an instant private key D which is an RSA pair of E according to Equation 2 using E. FIG. If the valid D exists in step 530, the authentication process using the instant D and the instant E is performed as described with reference to Figs.

However, if the D does not exist in the determination of step 530, the generation unit of the device generates a second instant public key E 'different from the instant instant public key E. This process may be through a random number generation process again, but in the example shown in FIG. In step 540, the integer 2 is added to the instant public key E, which was previously generated but cannot be used because D does not exist. This process is repeated until there is a valid E-D pair.

6 is a flowchart illustrating a process in a case where a private key does not exist when an RSA-CRT algorithm is applied according to an embodiment. First, when the signature is generated in the previous embodiment without using the CRT and when the signature is generated when using the CRT, the following table is shown.

In Table 1, M '' adds padding and the like to the hash value of message M according to the RSA signature format. As Table 1 shows, using CRT complicates the expression, but the processing data length of "modular exponentiation", which takes up a large part of the calculation amount in RSA operation, is 1/2. Can be 4 to 8 times faster.

After the random instant public key E is generated, if CRT is used (step 610), then dP is calculated in step 620 and it is determined whether this dP exists (630). E cannot be used if this dP does not exist regardless of the presence of dQ. Therefore, in step 631, the process of designating the number of E plus 2 again as E and calculating dP is repeated until this dP exists. Of course, as described above, since the step 631 is an optional embodiment, it is also possible to regenerate a completely new E through a random number generation process.

If dP is present, the same process is repeated for dQ. The calculation of dQ 640 and the determination of the presence 650 and the regeneration 651 of E according to the absence of dQ are the same as the description of steps 620, 630 and 631. And if there are both valid dP and dQ, an encryption algorithm using CRT will be performed in step 660.

Effects and performance issues according to the above embodiments will be briefly described. In the case of random number generation using the PUF hardware fingerprint as a source value, the external attack is impossible. Even if the pair of E and D is always regenerated, if the value of E is too small (e.g. less than 16-bit), the same pair of E-Ds may be used by chance, but this can be prevented by increasing E slightly. If the size of E increases, the amount of computation required for digital signature verification increases, but it is not a burden considering the hardware resources of the certification authority performing such computation. Thus, the magnitude of the E value can be set to a sufficiently large value, such as 128-bit or more, without sacrificing performance.

On the other hand, the performance degradation caused by the continuous regeneration of the E-D pair according to the embodiments is not significant. The time complexity of the operation generating the ED pair is proportional to the length n of the key (time complexity O (n)), and the signature generation operation is proportional to the square or cube of length n of the key, depending on the implementation (time complexity O ( n ² ) or O (n ³ )). However, since the minimum key length of recently used RSA is 1024, 2048-bit or more, the operation time for generating an ED pair is equivalent to one-thousandth of the signature generation time. Small enough to be. Therefore, according to the embodiments, subchannel attacks such as DPA are prevented at the source without detrimental hardware or performance degradation.

In the above, although the embodiments have been described by way of limitation, various modifications and variations are possible to those skilled in the art from the above description. For example, the described techniques may be performed in a different order than the described method, and / or components of the described systems, structures, devices, circuits, etc. may be combined or combined in a different form than the described method, or other components. Or even if replaced or substituted by equivalents, an appropriate result can be achieved.

Therefore, other implementations, other embodiments, and equivalents to the claims are within the scope of the claims that follow.

Claims (20)

An authentication device comprising at least one processor and performing an authentication procedure in accordance with public-key cryptosystems, wherein the authentication device is at least temporarily implemented by the at least one processor: A generator configured to generate a first instant public key in response to a digital signature corresponding to the algorithm required; A calculator configured to calculate a first instant private key paired with the first instant public key in the algorithm using the first instant public key; And A processing unit for generating an electronic signature by the algorithm using the first instant private key Authentication device comprising a. The method of claim 1, A communication unit for transmitting a message to be transmitted to the opposite device together with the digital signature and the first instant public key Authentication device further comprising. The method of claim 2, In response to receiving the retransmission request from the counterpart device, if the communication Ack is received and it is determined that there was no communication error, the authentication unit generates a second instant public key different from the first instant public key. . The method of claim 1, And the generation unit generates the first instant public key through a random number generation process. The method of claim 4, wherein The authentication device further includes a physically unclonable function (PUF) for providing a hardware fingerprint by using a randomly generated process deviation, The random number generation process includes a random number generation algorithm using the hardware fingerprint as a source value. The method of claim 4, wherein If it is determined in the calculation result that the first instant private key paired with the first instant public key does not exist: The generation unit generates a second instant public key that is different from the first instant public key; And the calculating unit calculates a second instant private key paired with the second instant public key in the algorithm. The method of claim 6, And the generation unit determines the second instant public key by providing a number obtained by adding an integer 2 to the first instant public key instead of performing the random number generation process to generate the second instant public key. The method of claim 6, When the encryption algorithm is a RSA-CRT (Chinese Remainder Theorem) algorithm, the first instant private key calculated by the calculation unit includes a first dP value and a first dQ value, If it is determined in the calculation result that none of the first dP value and the first dQ value is present: The generation unit generates a second instant public key that is different from the first instant public key; And the calculating unit calculates a second dP value and a second dQ value paired with the second instant public key in the algorithm. An authentication device comprising at least one processor and verifying an electronic signature sent by a counterpart device according to a public key based encryption algorithm, the authentication device being at least temporarily implemented by the at least one processor: A processing unit for verifying the electronic signature using the fixed public key of the external device held and the first instant public key generated by the external device and sent together with the electronic signature in an instant. Authentication device comprising a. The method of claim 9, A determination unit that determines that the first instant public key is invalid if the first instant public key is not three or more odd numbers Authentication device further comprising. The method of claim 9, Determination unit for determining that the first instant public key is invalid if the first instant public key is generated repeatedly Authentication device further comprising. An authentication device comprising at least one processor, the authentication device being at least temporarily implemented by the at least one processor: A determination unit that determines whether the first instant public key received from the external device is a valid value; And If the first instant public key is a valid value, the processor is configured to encode data to be transmitted using the fixed public key of the external device and the first instant public key. Authentication device comprising a. The method of claim 12, And the first instant public key is generated through a random number generation process in the counterpart device. The method of claim 12, And the determination unit determines that the first instant public key is not valid unless the first instant public key is an odd number of three or more. The method of claim 12, And the determination unit determines that the first instant public key is invalid when the first instant public key is repeatedly used more than a predetermined number of reuse times. An authentication device comprising at least one processor and performing an authentication procedure according to a public key based encryption algorithm, wherein the authentication device is at least temporarily implemented by the at least one processor: A generator configured to generate a first instant public key through a random number generation process in response to the authentication procedure being performed; A calculator configured to calculate a first instant private key paired with the first instant public key in the algorithm using the first instant public key; And When a message encoded using the first public key and the fixed public key held in advance in the external device is received from the external device receiving the first instant public key, the first instant private key is used. Processing section for decoding the message Authentication device comprising a. The method of claim 16, The authentication device further includes a physically unclonable function (PUF) for providing a hardware fingerprint by using a randomly generated process deviation, The random number generation process includes a random number generation algorithm using the hardware fingerprint as a source value. The method of claim 1, If it is determined in the calculation result that the first instant private key paired with the first instant public key does not exist: The generation unit generates a second instant public key that is different from the first instant public key; And the calculating unit calculates a second instant private key paired with the second instant public key in the algorithm. In a non-one embodiment computer program stored on a computer-readable recording medium, the program, when executed on a computing device including a processor, includes: An instruction set for generating a first instant public key through a random number generation process in response to a digital signature generation request corresponding to the message; An instruction set for calculating, using the first instant public key, a first instant private key paired with the first instant public key; And Instruction set for generating an electronic signature by a public key algorithm using the first instant private key Program stored on a computer-readable recording medium comprising a. In a non-one embodiment computer program stored on a computer-readable recording medium, the program, when executed on a computing device including a processor, includes: A set of instructions for determining whether a first instant public key received with a message and an electronic signature from an external device is valid; And A set of instructions for verifying the electronic signature using the fixed public key of the external device stored in the computing device and the received first instant public key when the first instant public key is valid Program stored on a computer-readable recording medium comprising a.

Images