KR102462701B1 - Hash chain traversal algorithm and electronic device thereof - Google Patents

Abstract

A hash chain operation method is disclosed. The hash chain operation method of the present invention includes a first node exceeding a predetermined number based on a binary tree-based fractal hash chain operation method when the number of nodes constituting a target hash chain exceeds a predetermined number Generating a hash value of each of the second hash chain and the second node including a predetermined number of second nodes based on the step of generating the first hash chain and each hash value of the first node and the basic hash chain operation method It may be implemented in a method comprising steps.

Description

Hash chain operation method and electronic device including same { Hash chain traversal algorithm and electronic device thereof }

The present invention relates to a hash chain operation method and an electronic device including the same.

BACKGROUND ART With the development of electronic technology, various types of electronic devices are being developed and distributed. In particular, electronic devices that perform wireless communication used in various places have been continuously developed for several years. Accordingly, an encryption technology for enhancing security in the process of performing communication between electronic devices is being studied.

In cryptography, a hash function is a one-way function in which it is probabilistically difficult to obtain the input of the hash function from the output of the hash function. When such a hash function is continuously applied, the output values of each hash function continuously form a chain, which is called a hash chain.

However, if the hash chain is used repeatedly, processing throughput increases and the time according to the hash operation may increase excessively.

The present invention is in accordance with the above-mentioned necessity, and an object of the present invention is to provide a method for efficiently generating a hash chain.

In the hash chain operation method according to an embodiment of the present invention, when the number of nodes constituting the target hash chain exceeds a predetermined number, based on the binary tree-based fractal hash chain operation method, the predetermined number is exceeded. A first hash chain including a first node and a second hash chain including a predetermined number of second nodes based on a basic hash chain operation method and generating a hash value of each of the first nodes and the second hash chain and generating a hash value of each of the two nodes.

In addition, each of the first nodes includes a first leaf node and a first parent node, and the step of generating the hash value of each of the second hash chain and the second node includes a hash value of the first leaf node. A hash value of the second node is generated by using as a seed value.

In addition, the generating of the hash values of each of the second hash chain and the second node includes using the first hash value of the first leaf node as a seed value and the predetermined number of hash values of the second nodes. When generated, the predetermined number of hash values of the second nodes are generated by using the third hash value of the first leaf node as a seed value.

Meanwhile, the first generated hash value among the hash values of the first node may be a private key, and the last generated hash value among the hash values of the second node may be a public key.

In this case, the preset number may be 1024.

Meanwhile, the public key may be changed to a different hash value of the second node every preset period.

When the number of nodes constituting the communication unit, the storage unit, and the target hash chain exceeds a predetermined number, the electronic device according to an embodiment of the present invention exceeds the predetermined number based on the binary tree-based fractal hash chain operation method A first hash chain including a first node to generate a hash value of each of the first nodes, and a second hash chain including the preset number of second nodes based on a basic hash chain operation method and the second hash chain It includes a processor that generates a hash value of each of the two nodes.

As described above, according to various embodiments of the present invention, it is possible to efficiently generate a hash chain according to the number of hash values to be generated, thereby reducing processing throughput and calculation time.

1 is a view for explaining an electronic device according to an embodiment of the present invention.
2 is a view for explaining a hash chain operation method according to an embodiment of the present invention.
3 is a diagram for explaining operations of an electronic device and an external device according to an embodiment of the present invention.
4 is a flowchart for explaining a hash chain operation method according to an embodiment of the present invention.

Terms used in this specification will be briefly described, and the present disclosure will be described in detail.

Terms used in the embodiments of the present disclosure have been selected as currently widely used general terms as possible while considering the functions in the present disclosure, but this may vary depending on the intention or precedent of a person skilled in the art, the emergence of new technology, etc. . In addition, in specific cases, there are also terms arbitrarily selected by the applicant, and in this case, the meaning will be described in detail in the description of the corresponding disclosure. Therefore, the terms used in the present disclosure should be defined based on the meaning of the term and the contents of the present disclosure, rather than the simple name of the term.

Embodiments of the present disclosure may apply various transformations and may have various embodiments, and specific embodiments will be illustrated in the drawings and described in detail in the detailed description. However, this is not intended to limit the scope of the specific embodiments, and it should be understood to include all transformations, equivalents and substitutes included in the spirit and scope of the invention. In describing the embodiments, if it is determined that a detailed description of a related known technology may obscure the subject matter, the detailed description thereof will be omitted.

Terms such as first, second, etc. may be used to describe various elements, but the elements should not be limited by the terms. The terms are used only for the purpose of distinguishing one component from another.

The singular expression includes the plural expression unless the context clearly dictates otherwise. In the present application, terms such as "comprises" or "consisting of" are intended to designate that the features, numbers, steps, operations, components, parts, or combinations thereof described in the specification exist, and are intended to indicate that one or more other It is to be understood that this does not preclude the possibility of addition or presence of features or numbers, steps, operations, components, parts, or combinations thereof.

In the present disclosure, a "module" or "unit" performs at least one function or operation, and may be implemented as hardware or software, or a combination of hardware and software. In addition, a plurality of “modules” or a plurality of “units” are integrated into at least one module and implemented with at least one processor (not shown) except for “modules” or “units” that need to be implemented with specific hardware. can be

Hereinafter, with reference to the accompanying drawings, embodiments of the present disclosure will be described in detail so that those of ordinary skill in the art to which the present disclosure pertains can easily implement them. However, the present disclosure may be implemented in several different forms and is not limited to the embodiments described herein. And in order to clearly explain the present disclosure in the drawings, parts irrelevant to the description are omitted, and similar reference numerals are attached to similar parts throughout the specification.

1 is a block diagram illustrating an electronic device according to an embodiment of the present invention.

The electronic device 100 may include a communication unit 110 , a storage unit 120 , and a processor 130 .

The communication unit 110 transmits the hash value generated by the processor 130 to an external device. The communication unit 110 performs communication in a wired/wireless communication method, for example, beacon, near field communication (NFC), Bluetooh, IR (Infrared), WI-FI (Wireless Fidelity), Zigbee, WAN, Ethernet Communication may be performed through various communication methods such as (Ethernet), IEEE 1394, HDMI, USB, MHL, AES/EBU, optical, and coaxial.

The storage unit 120 stores various data necessary for the operation of the electronic device 100 . For example, the storage 120 may store a value for generating a hash value to be transmitted to an external device. Also, the storage unit 120 may store a hash value included in a root node of a binary tree-based fractal hash chain.

In particular, the storage unit 120 stores data necessary for the processor 130 to execute various processes. For example, the processor 130 may be implemented as an internal memory such as a ROM and a RAM included in the processor 130 , or may be implemented as a memory separate from the processor 130 . In this case, the storage unit 120 may be implemented in the form of a memory embedded in the electronic device 100 or may be implemented in the form of a memory detachable to the electronic device 100 according to the purpose of data storage. For example, data for driving the electronic device 100 is stored in a memory embedded in the electronic device 100 , and data for an extended function of the electronic device 100 is detachable from the electronic device 100 . It can be stored in any available memory. On the other hand, the memory embedded in the electronic device 100 is implemented in the form of a non-volatile memory, a volatile memory, a flash memory, a hard disk drive (HDD) or a solid state drive (SSD), etc., and is attached and detached to the display device 100 . In the case of a memory capable of this, it may be implemented in the form of a memory card (eg, a micro SD card, a USB memory, etc.), an external memory connectable to a USB port (eg, a USB memory), and the like.

The processor 130 controls the overall operation of the electronic device 100 .

According to an embodiment of the present invention, the processor 130 may be implemented as a digital signal processor (DSP), a microprocessor (microprocessor), or a time controller (TCON) for processing a digital signal. Without limitation, a central processing unit (CPU), a micro controller unit (MCU), a micro processing unit (MPU), a controller, an application processor (AP), or a communication processor ( communication processor (CP)), may include one or more of an ARM processor, or may be defined by a corresponding term In addition, the processor 130 may include a system on chip (SoC), large scale integration (LSI) in which a processing algorithm is embedded. ) or implemented in the form of a field programmable gate array (FPGA).

When the number of nodes constituting the target hash chain exceeds a preset number, the processor 130 according to an embodiment of the present invention is a first node exceeding a preset number based on a binary tree-based fractal hash chain operation method. It is possible to generate a hash value of each of the first hash chain and the first node including

In this case, a second hash chain including a preset number of second nodes and a hash value of each of the second nodes may be generated based on the basic hash chain operation method.

As an example, when the preset number is 1024 and the number of nodes constituting the target hash chain is 1535, the processor 130 performs the first hash chain including 1535-1024 = 511 first nodes and the first node, respectively. You can create a hash value of In this case, since the data structure including the plurality of first nodes is based on the binary tree-based fractal hash chain operation method, the data structure may be in the form of a binary tree having a depth value of 9. After that, since the preset number is 1024, a second hash chain including 1024 second nodes and a hash value of each of the second nodes may be generated based on the basic hash chain operation method.

When the number of nodes including the hash value exceeds the preset number, the processor 130 generates a hash value based on the binary tree-based fractal hash chain operation method, a hash based on the basic hash chain operation method This is because it is faster than generating values.

The processor 130 according to an embodiment of the present invention may generate a hash value of the second node by using the hash value of the first leaf node as a seed value. Also, the first node may include a first leaf node and a first parent node.

That is, it is possible to generate a hash value based on the basic hash chain operation method based on the result value of the leaf node based on the binary tree-based fractal hash chain operation method.

The processor 130 according to an embodiment of the present invention uses the hash value of the first leaf node as a seed value to generate the hash value of the second node by a preset number of the hash value of the second node, the first leaf A preset number of hash values of the second nodes may be generated by using the third hash value of the node as the seed value.

That is, after generating a preset number of hash values based on the basic hash chain operation method using a hash value (first hash value) included in any one of the first leaf nodes as a seed value, the first leaf node Other hash values based on the basic hash chain operation method may be generated by using the hash value (the third hash value) included in the remaining nodes as the seed value. This is because more than a preset number of hash values may be required.

The processor 130 according to an embodiment of the present invention identifies the first generated hash value among the hash values of the first node as the private key, and the last generated hash value among the hash values of the second node as the public key. have. For example, the secret key may be generated by the processor 130 , may be a value generated based on data transmitted from an external device or an external server, and may be a value obtained by reading the secret key value stored in the storage unit 120 . this could be

Specifically, the processor 130 may generate the hash values of the second node based on the binary tree-based fractal hash chain and the basic hash chain operation method based on the hash value identified by the secret key. In this case, the last generated hash value among the hash values of the second node may be identified as the public key.

In this case, the processor 130 may control the transmission unit 110 to transmit the hash value identified by the public key to the external device. In this case, the transmission method may be, for example, any one of a unicast method and a broadcast method, and the public key may be, for example, identification information or status information of an electronic device, as another example, the UUID of a beacon , MajorID, MinorID, etc. may be status information.

According to an embodiment of the present invention, the number of second nodes of the second hash chain generated by the processor 130 may be 1024. Here, each of the second nodes may include hash values.

According to the experimental example, when the number of hash values included in each node is less than 1024, the hash value generation speed based on the basic hash chain operation method is about twice that of the hash value generation speed based on the binary tree-based fractal hash chain operation method. You can see that it is fast. In the fractal hash chain operation method, after generating all the hash values of child nodes in one node, the parent node of the child node moves to the next node of the same depth, that is, the next stage node value needs to be updated. Because time is relatively large.

Therefore, according to an embodiment of the present invention, when the number of hash values to be generated exceeds 1024, the processor 130 generates 1024 hash values based on the basic hash chain operation method, and the remaining hash values to be generated Values can be generated based on a binary tree-based fractal hash chain operation method.

According to an embodiment of the present invention, the processor 130 may change the public key to a hash value of the second node different from the previous public key among the hash values of the second node every preset period.

As an example, the processor 130 may identify the last generated hash value among the hash values of the second node as a public key and transmit it to the external device for the first time. After a predetermined period from when the public key is first transmitted, the processor 130 may identify a hash value generated from the last to the first among the hash values of the second node as the public key and transmit it to the external device.

However, the present invention is not limited to this example, and the hash value of the second node different from the already transmitted hash value of the second node may be transmitted every preset period, and when all of the hash values of the second node are transmitted, the first The hash value of the node can also be transmitted. In addition, the hash value of the second node or the hash value of the first node may be transmitted regardless of the generated order.

2 is a view for explaining a hash chain operation method according to an embodiment of the present invention.

The target hash chain 200 operation method according to an embodiment of the present invention includes a hash chain 210 generated based on a binary tree-based fractal hash chain operation method and a hash included in leaf nodes of the hash chain 210. Based on the value, it includes a method of generating the hash chains 220 and 230 according to the basic hash chain operation method. In this case, each node of the target hash chain 200 includes a hash value.

For example, when the preset number of nodes is n+1, the number of nodes included in the basic hash chain may be n+1. According to the basic hash chain operation method, a hash value included in the node 222 may be generated through a hash operation by using the hash value included in the node 221 as a seed. If the above-described hash operation is repeatedly applied n times, the n+1th hash value included in the node 223 may be generated.

In this case, the hash value included in the node 221 may be generated by performing a hash operation on the hash value included in any one of the leaf nodes 211 of the binary tree-based fractal hash chain.

In addition, when all of the hash values of each of the predetermined number of nodes 220 are generated, the hash values included in each of the nodes 230 are calculated based on the hash values included in the node 212, as described above. It can be generated based on the hash chain operation method.

Specifically, the basic hash chains 220 and 230 generate hash values in the above-described order. As an example, a hash value of the node 221 , a hash value of the node 222 , ... , a hash value of the node 223 may be generated.

Thereafter, the hash values included in each node may be consumed in the reverse order. As an example, the hash value of the node 223 , the hash value of the node 222 , ... , may be consumed in the order of the hash value of the node 221 . For example, the electronic device 100 transmits a hash value included in each node to an external device, and the hash value included in the node may be consumed. This is because reusing an encryption key that has already been used is vulnerable to security.

Meanwhile, according to FIG. 2, two basic hash chains 220 and 230 having a preset number of nodes and hash values of nodes have been exemplified, but the number of basic hash chains is not limited thereto, and the processor 130 is a basic hash chain. A chain can be created at least as many as the number of leaf nodes in the fractal hash chain 210 .

According to the binary tree-based fractal hash chain operation method according to an embodiment of the present invention, a hash value of each leaf node may be generated.

In this case, the number of nodes included in the hash chain 210 may be the number remaining after subtracting the number of nodes included in the basic hash chains 220 and 230 from the number of nodes constituting the target hash chain. That is, it may be the number remaining after subtracting the number of preset nodes.

According to an example, a hash value of a child node may be generated based on a hash value of a parent node of the hash chain 210 . When one parent node generates both hash values of two child nodes, a pebbles move can be performed.

A pebble refers to a memory cell, and a pebble move refers to a process of moving a hash value included in another memory cell from a current memory cell to another memory cell in order to generate or consume it.

On the other hand, the order in which the nodes and hash values included in the target hash chain 200 are generated is, for example, the hash included in the leaf node based on the hash value included in the root node of the binary tree-based fractal hash chain 210 . After generating the value, the nodes of the basic hash chain 220 and 230 may be generated based on the hash value included in the leaf node.

After that, the order of consuming the hash value included in the target hash chain is after consuming the hash value included in the nodes of the basic hash chain (220, 230), the hash value of the binary tree-based fractal hash chain (210) can be consumed

3 is a diagram for explaining operations of an electronic device and an external device according to an embodiment of the present invention.

According to an embodiment of the present invention, the processor 130 of the electronic device 100 performs a hash operation based on the private key, and then sets the hash values of the basic hash chains 220 and 230 as the public key to the external device. The communication unit 110 may be controlled to transmit to 300 . According to another example, a hash value of the binary tree-based fractal hash chain 210 may be used as a public key.

In this case, the external device 300 may perform various wireless communication operations, such as authentication, network access, and data communication, based on the public key transmitted from the electronic device 100 .

According to an embodiment of the present invention, the public key to be transmitted by the electronic device 100 may be changed to a different hash value for each preset period. This is because if the public key having the same hash value is continuously transmitted, a malicious user can receive the public key and reuse it for other purposes. Accordingly, the electronic device 100 transmits any one of the plurality of hash values generated by the processor 130 to the external device 300, and transmits another hash value different from the transmitted hash value after a preset period elapses to the external device ( 300) may be sequentially transmitted. Accordingly, security can be strengthened.

4 is a flowchart for explaining a hash chain operation method according to an embodiment of the present invention.

According to the target hash chain operation method according to an embodiment of the present invention, when the number of nodes constituting the target hash chain exceeds a predetermined number, the predetermined number is exceeded based on the binary tree-based fractal hash chain operation method A first hash chain including a first node and a hash value of each of the first nodes may be generated (S410).

Thereafter, a second hash chain including a preset number of second nodes and a hash value of each of the second nodes may be generated based on the basic hash chain operation method ( S420 ).

As described above, by generating a first node for a number exceeding a preset number to operate a binary tree-based fractal hash chain, and generating a preset number of second nodes to operate the basic hash chain, the hash value is calculated By efficiently generating it, processing throughput and computation speed can be increased.

Meanwhile, at least some of the above-described methods according to various embodiments of the present disclosure may be implemented in the form of an application that can be installed in an existing electronic device.

In addition, at least some of the above-described methods according to various embodiments of the present disclosure may be implemented only by software upgrade or hardware upgrade of an existing electronic device.

In addition, at least some of the above-described various embodiments of the present invention may be performed through an embedded server provided in the electronic device or an external server of the electronic device.

Meanwhile, at least some of the various embodiments described above may be implemented in a recording medium readable by a computer or a similar device using software, hardware, or a combination thereof. . In some cases, at least some of the embodiments described in this specification may be implemented by the processor itself. According to the software implementation, at least some components of the 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.

Meanwhile, computer instructions for performing the processing operation of the electronic device according to various embodiments of the present disclosure described above may be stored in a non-transitory computer-readable medium. When the computer instructions stored in the non-transitory computer-readable medium are executed by the processor of the specific device, the specific device performs the processing operation in the electronic device according to the various embodiments described above.

The non-transitory computer-readable medium refers to a medium that stores data semi-permanently, rather than a medium that stores data for a short moment, such as a register, cache, memory, etc., and can be read by a device. Specific examples of the non-transitory computer-readable medium may include a CD, DVD, hard disk, Blu-ray disk, USB, memory card, ROM, and the like.

In the above, preferred embodiments of the present disclosure have been illustrated and described, but the present disclosure is not limited to the specific embodiments described above, and is commonly used in the technical field pertaining to the present disclosure without departing from the gist of the present disclosure as claimed in the claims. Various modifications may be made by those having the knowledge of

100: electronic device 200: target hash chain 300: external device

Claims (7)

In the hash chain operation method,
When the number of nodes constituting the target hash chain exceeds a preset number, the first node exceeding the preset number based on the binary tree-based fractal hash chain operation method and the hash value of each of the first nodes are included generating a first hash chain to and
Based on the basic hash chain operation method, generating a second hash chain including the predetermined number of second nodes and a hash value of each of the second nodes based on the basic hash chain operation method; including, a hash chain operation method. According to claim 1,
Each of the first nodes includes a first leaf node and a first parent node,
The step of generating a hash value of each of the second hash chain and the second node comprises:
and generating a hash value of the second node by using the hash value of the first leaf node as a seed value. 3. The method of claim 2,
The step of generating a hash value of each of the second hash chain and the second node comprises:
When the predetermined number of hash values of the second nodes are generated using the first hash value of the first leaf node as the seed value, the preset number of the hash values of the first leaf node is used as the seed value. generating a hash value of the number of said second nodes. 4. The method of claim 3,
The hash chain operation method, wherein the first generated hash value among the hash values of the first node is a private key, and the last generated hash value among the hash values of the second node is a public key. 5. The method of claim 4,
The preset number is 1024, the hash chain operation method. 5. The method of claim 4,
A hash chain operation method for changing the public key to a hash value of a different second node every preset period. In an electronic device,
communication department;
storage; and
When the number of nodes constituting the target hash chain exceeds a preset number, a first node exceeding the preset number based on a binary tree-based fractal hash chain operation method and a hash value of each of the first nodes create a first hash chain,
A processor for generating a second hash chain including the predetermined number of second nodes and a hash value of each of the second nodes based on a basic hash chain operation method; including, an electronic device.

Images