[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2020101325A1 - 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법 - Google Patents

순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법 Download PDF

Info

Publication number
WO2020101325A1
WO2020101325A1 PCT/KR2019/015346 KR2019015346W WO2020101325A1 WO 2020101325 A1 WO2020101325 A1 WO 2020101325A1 KR 2019015346 W KR2019015346 W KR 2019015346W WO 2020101325 A1 WO2020101325 A1 WO 2020101325A1
Authority
WO
WIPO (PCT)
Prior art keywords
key
permutation
encryption
signature
message
Prior art date
Application number
PCT/KR2019/015346
Other languages
English (en)
French (fr)
Inventor
안세환
Original Assignee
(주)블루팝콘
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by (주)블루팝콘 filed Critical (주)블루팝콘
Priority to CN201980088769.4A priority Critical patent/CN113330712A/zh
Priority to US17/293,613 priority patent/US20220069984A1/en
Priority to EP19884666.9A priority patent/EP3883178A4/en
Priority to AU2019381522A priority patent/AU2019381522A1/en
Priority claimed from KR1020190144235A external-priority patent/KR102304831B1/ko
Publication of WO2020101325A1 publication Critical patent/WO2020101325A1/ko

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Definitions

  • the present invention relates to an encryption method and system using cryptographic technologies based on permutation group, and more specifically, a password generating object (hereinafter referred to as a “sender”) and a decryption object (hereinafter referred to as a “receiver”) send a message, It is different from the message space that composes the original message, and the secret permutations group that changes to a new space through movement or expansion, etc.
  • a password generating object hereinafter referred to as a “sender”
  • a decryption object hereinafter referred to as a “receiver”
  • Quantum-based algorithms include the Shor and Grover algorithms mentioned above. According to Grover's algorithm that affects symmetric key encryption, most symmetric key encryption methods double the encryption key to achieve the same level of security as before, but when a quantum computer with a Shor algorithm is developed, the public key currently used Encryption is no longer available.
  • Table 2 below compares and shows how the security level changes in the quantum computing environment with respect to the cryptography currently used.
  • the present invention proposes a post-quantum encryption technique and system that operates efficiently in a current computing environment and securely protects data even in a quantum computing environment.
  • the proposed quantum resistance (post quantum) encryption method should be improved over the existing public key method in terms of performance, security, and usability as it has to replace the public key encryption method that is no longer secure due to the quantum computing environment. In addition, it should be suitable for the current computing environment.
  • the operation of composing a symmetric key and an asymmetric key, respectively, in the form of permutations at the same time based on permutation groups Using the method and multi-dimensional expansion with the key array transformation method, the key space is extended without using complex mathematical operations, and complexity is increased and processing is performed in the substitution-permutation-network (SPN) of the symmetric key encryption technique without performing complex mathematical operations. It is possible to perform a fast encryption process by performing calculations such as substitution and conversion of values.
  • SPN substitution-permutation-network
  • the conventional method uses a method of performing a mathematical operation of a fixed key function using a key value generated once as shown in FIG. 1, but in the present invention, a multi-dimensional space selected by a receiver as shown in FIG. 3 whenever the sender transmits a message
  • a multi-dimensional space selected by a receiver as shown in FIG. 3 whenever the sender transmits a message
  • the present invention includes an encryption performance object for encrypting a message and a decryption performance object for decrypting the encrypted message, and the encryption performance object and decryption performance object are disclosed among symmetric keys and asymmetric keys that are permutations based on permutation groups. Encrypting the message by synthesizing the keys at the same time, and when decrypting it again, the permutation group based encryption technology is applied, which is characterized by decrypting the original text using the private key of the permutation type symmetric key and asymmetric key based on the permutation group. Disclosed is an encryption system.
  • the object to be encrypted and the object to be decrypted are an encrypter (ENC) that encrypts a message using an encryption key (K e ), and a message is decrypted using a decryption key (K d ). It includes a decoder (DEC) and an encryption key generator (MKG).
  • EEC encrypter
  • DEC decoder
  • MKG encryption key generator
  • the encrypter is an input queue for processing message input, a GA operator for generating a cipher text through permutation using a disposable public key, and an output queue for processing the output of the generated cipher text. It includes.
  • the GA operator receives the symmetric key (Q AB ) and the public key (G B ) of the decrypted object from the cryptographic key generator (MKG) and generates cryptographic text through permutation.
  • Q AB is the symmetric key of the encryption and decryption objects
  • G B is decryption.
  • the public key of the execution object, M is a message space, and C is a ciphertext space.
  • the decryptor processes an input queue processing an input of a ciphertext, a GA operator for restoring an original message through permutation using a disposable private key, and an output of the restored original message Contains output queue.
  • the GA operator receives the symmetric key (Q AB ) and the private key (H B ) of the decrypted object from the encryption key generator (MKG) and restores the original message through permutation. .
  • Q AB is a symmetric key between an encryption object and a decryption object
  • H B is a decryption object.
  • the private key of, M is a message space
  • C is a ciphertext space.
  • the cryptographic key generator is a random number generator (PRNG) that generates a disposable pseudo-random number through a key derivation function (KDF) using a plurality of parameters, and the key derivation function (KDF) ) To generate a disposable pseudorandom number sequence (PRP) and provide it to the key generation module.
  • PRNG random number generator
  • KDF key derivation function
  • KDF key derivation function
  • PRP disposable pseudorandom number sequence
  • the key generation module is a master key vector (MSK_) which is a vector function representing a secret permutation group of an object to be decrypted.
  • MSK_ master key vector
  • MSK_ master kiss color module
  • MPK symmetric key module
  • PK public key module
  • SK key module
  • the master key vector (MSK_ ) Module, master kiss color module (MSK_ ) And the symmetric key module (MPK) use a plurality of unique personal identification information as parameters to generate different key values according to the same value or mutually agreed method through the key induction function (KDF).
  • KDF key induction function
  • the present invention comprises the steps of generating a master key using an identification factor by an encryption key generator, and generating a symmetric key, a private key, and a public key pair required for encryption and decryption in the encryption key generator, and an object to perform encryption.
  • Disclosed is an encryption and decryption method.
  • the identification factor includes at least one of a user identification factor including personal information of the user, a terminal device identification factor including user terminal information, and a secret function generation factor.
  • the ciphertext is generated by operating the GA operator using the generated symmetric key and the public key of the decrypted object.
  • the ciphertext (C) is generated as shown in the following formula by permutation (M ⁇ K ⁇ C) by substituting the encryption key (K e ) in the encryption function (E).
  • the restoration of the ciphertext is characterized in that it is generated as follows by permutation (C ⁇ K ⁇ M) by substituting the decryption key (K d ) in the decryption function (D). ,
  • the present invention includes a signature performing object that generates a signature when creating a cipher text, and a verification performing object that is configured to verify the signature to decrypt the cipher text into an original message, and is symmetrical in the form of permutation based on a permutation group. It provides a signature verification system using permutation group based encryption technology characterized by generating and verifying a signature using a key and an asymmetric key.
  • the signature performing object and the verification performing object include a signer that generates a signature through permutation, a verifier that verifies the signature through permutation, and a cryptographic key generator (MKG). Includes.
  • the signer is an input queue for processing message input, a GA operator for generating a signature statement through permutation using a one-time private key, and an output for processing the output of the generated signature statement Includes cues.
  • the GA operator of the signer receives the symmetric key (Q AB ) and the private key (H A ) of the object to be signed from the cryptographic key generator (MKG) and signs the signature through permutation.
  • the verifier receives an input queue for processing a signature, and a GA operator for generating an accepted original message by verifying the signature through permutation using a single-use public key, It contains an output queue that processes the output of the accepted original message.
  • the GA operator of the verifier receives the symmetric key (Q AB ) and the public key (G A ) of the signature performing object from the cryptographic key generator (MKG) and receives the signature through permutation. Verify and confirm acceptance or rejection.
  • the cryptographic key generator is a random number generator (PRNG) that generates a disposable pseudo-random number through a key derivation function (KDF) using a plurality of parameters, and the key derivation function (KDF) ) To generate a disposable pseudorandom number sequence (PRP) and provide it to the key generation module.
  • PRNG random number generator
  • KDF key derivation function
  • KDF key derivation function
  • PRP disposable pseudorandom number sequence
  • the key generation module is a master key vector (MSK_) which is a vector function representing a secret permutation group of an object to be signed. ) Module, and a master kiss color module (MSK_) that determines a secret permutation to be used when decrypting ),
  • the symmetric key module (MPK) that generates a symmetric key shared between the signature execution object and the validation execution object, and the public and private keys, which are a pair of asymmetric keys of the decryption execution object used when encrypting and decrypting messages. It includes a generated public key module (PK) and a private key module (SK).
  • the master key vector (MSK_ ) Module master kiss color module (MSK_ )
  • the symmetric key module (MPK) generate key values through a key derivation function (KDF) using one or more identification information that can distinguish objects from each other as parameters.
  • KDF key derivation function
  • the present invention comprises the steps of generating a master key using an identification factor by an encryption key generator, and generating a symmetric key, a private key, and a public key pair required for encryption and decryption in the encryption key generator, and an object to be signed.
  • Generating a signature by receiving the generated symmetric key and the signature key and the private key of the object to be verified; and the object to be verified receives the symmetric key and the verification key, the disposable public key of the object to be signed to perform the signature.
  • a method for signing and verifying a cipher text including verifying the generated signature text and accepting or rejecting the original text message according to the verification result.
  • the identification factor includes at least one of a user identification factor including personal information of the user, a terminal device identification factor including user terminal information, and a secret function generation factor.
  • the signature statement (M S ) is generated as shown in the following formula by permutation (M ⁇ K ⁇ S) by substituting the signature key (K S ) in the signature function (S).
  • the verification of the signature is characterized in that it is generated as follows by the permutation operation (S ⁇ K ⁇ S) by substituting the verification key (K V ) in the verification function (V). ,
  • GQQ is the left multiplication of the permutation functions G and Q
  • message M (m 1 m n )
  • key K (k 1 k n )
  • the method proposed in the present invention makes it possible to replace the mathematical-based public key cryptographic system that can no longer be used as an insecure problem under a quantum computing environment to prevent confusion caused by data security problems in the coming quantum computing era. .
  • the recipient's private key and symmetric key are disposable keys that are generated only once when there is a transmission / reception connection, even if an unauthorized participant steals related information, the same key cannot be generated, and thus the decrypted ciphertext is decrypted. It is impossible to get angry, and it is safe for hacking attacks such as man-in-the-middle attacks.
  • the signature algorithm it is possible to determine whether or not a malicious attacker has taken and manipulated the generated ciphertext, and also provides a non-repudiation function that does not deny the message sent by the attacker. .
  • 1 is a conceptual diagram showing an example cipher (K, E, C) space of the RSA cryptosystem.
  • FIG. 2 is a conceptual diagram showing an example of a group action.
  • FIG. 3 is a conceptual diagram showing an example cipher (K, E, C) space of the invention system.
  • FIG. 4 is a conceptual diagram of a cryptographic communication system.
  • 5 is a structural diagram of a system for encryption / decryption.
  • FIG. 6 is a structural diagram of an encryptor.
  • FIG. 7 is a structural diagram of a decoder.
  • 8 is a conceptual diagram of an encryption key generator.
  • 9 is a conceptual diagram showing an example of a cryptographic operation.
  • 10 is a flow chart of encryption / decryption procedures.
  • 11 is a conceptual diagram showing an example of setting the encryption / decryption step 1;
  • FIG. 12 is a conceptual diagram showing an example of encryption / decryption step 2 key generation.
  • 13 is a conceptual diagram showing encryption step 3 cryptogram generation.
  • 14 is a conceptual diagram showing decryption step 3 message generation.
  • 15 is a structural diagram of a system for signature / verification.
  • 16 is a structural diagram of a signer.
  • 17 is a structural diagram of a verifier.
  • 19 is a conceptual diagram showing an example of a signature / verification step 1 setting.
  • 20 is a conceptual diagram showing key generation for signature / verification step 2;
  • 21 is a conceptual diagram showing signature step 4 signature generation.
  • 22 is a conceptual view showing acceptance / rejection of a verification step 4 verification message.
  • 23 is a structural diagram of a cryptographic system of a signed message.
  • 24 is a structural diagram of a decrypter system for a signed message.
  • 25 is a conceptual diagram showing encryption of a signed message.
  • 26 is a flowchart of a procedure for encrypting and decrypting a signed message.
  • 27 is a conceptual diagram showing decryption of a signed ciphertext.
  • Implementation objects may have a physically distinct structure, or may be functionally separated.
  • the control unit may include an API that performs a specific function in a distributed application environment such as a single system or a cloud service, a module that performs a specific function, hardware such as a component, a chip, a terminal, or software such as an application or program. Can be.
  • Information to send through a computer or communication system has various forms such as numbers, letters, pictures, videos, software, etc., but is handled in binary, that is, byte units composed of bits. This is converted into a code form such as ASCII, UNICODE, and is recognized by an application program in the system, and through this, people are sent back in the form of information such as numbers, letters, and pictures.
  • a message refers to information that people want to deliver to a counterpart through a computer or communication system, which is treated as a message unit in the system, such as bytes, as mentioned above in the system, and all information in the system. Is converted to a column of message units in one processable system.
  • a message set M is a list of cases in which a message to be delivered can be expressed by a message unit and can be expressed by a message unit.
  • M ⁇ 0,1 ⁇
  • the message can be expressed as a column of message unit, such as 00110101.
  • M ⁇ 0,1,... 255 ⁇ (expressed in decimal representation) and the message can be expressed as 64 68 72 82.
  • the element of M is m i , 1 ⁇ i ⁇ n
  • the number of elements of the set M can be expressed as
  • n.
  • the index set of the message is expressed as I M : I ⁇ M, and it is said that there is a morphism from the index set I to the message set M.
  • the shear function F X ⁇ Y from domain X to codomain Y represents the correspondence between X and Y, and in the meaning of the set, the order of the arrangement of the elements of any set Indicates.
  • the permutation of any set of n elements can also be said to be a permutation of n numbers or characters, and the same applies to the aforementioned message set M.
  • a permutaion group is a set consisting of elements in all cases of premutation in any set.
  • Permutation group G ⁇
  • the permutation group of all permutations of n ⁇ becomes symmetric group Sym (M) (all shear functions are symmetric groups)
  • M ⁇ 1,2,... , n ⁇ , Sym (M) for n characters is represented by S n .
  • permutation group G permutation group
  • Group Action refers to how each element (P: permutation) of the permutation group G arranges the elements of the set (S) and acts as a kind of function.
  • P permutation
  • Group Action when applying the permutation group (Group Action) of the permutation P to the elements of the set S, it means that the elements of the set S are rearranged by the permutation P.
  • the operation to change the order of the element array of the set S is called a group action.
  • G Permutation Group
  • M non-empty set
  • the group action of permutation group G for set M is a function f: G ⁇ M ⁇ M that satisfies the following three properties.
  • the degree of G is the number of elements of the set M constituting G
  • PRNG Physical Random Number Generator
  • PRF Physical Random Function
  • This is a function derived based on PRNG, and receives a random input value and always generates a pseudorandom sequence. (Similar random number function) This is the following function F: K ⁇ X ⁇ Y over (k, X, Y).
  • PRP Physical Random Permutaion: Generates a pseudorandom sequence in a similar manner to PRF, but there is always a one-to-one mapping acting in the same domain and an efficient inverse function D (k, X). If the sequence generated from PRP cannot be distinguished from random numbers generated from PRNG, it is called secure PRP. In addition, a secure PRP defined in sufficiently large X is a secure PRF. (Similar random number permutation)
  • TDF Trapdoor Function
  • the trapdoor function is a type of one-way function. In general, it is difficult to find the inverse of a function like a one-way function, but it is a function that can easily find the inverse if there is special information called trapdoor.
  • the trapdoor function is defined mathematically as follows. Since there is some secret value y, it is difficult to find f (x) when there is no y for a certain value of x, but if you can easily find the value of x in f (x) given y, the function f is a trapdoor function.
  • the cipher consists of three algorithms (functions): G, E, and D. Each represents the following abbreviation.
  • MKG Magnetic Key Generator
  • MKG Magnetic Key Generator
  • MKG Magnetic Key Generator
  • MKG is a cryptographic key generator that refers to a key management device that handles user identification and registration, key generation, distribution, etc., required for encryption / decryption. It may be installed in a system such as an encryptor or a decoder, or may be installed and interlocked with another third system. Access to MKG ensures a secure information channel through user authentication so that only allowed participants can access it.
  • the secret function group SPG (Secret Permutation Group) refers to a subset of all permutation groups G on the message set M, and each permutation forming this subset is called secret function candidate SPC (Secret Permutation Candidates). At this time, one candidate specifically designated among secret function candidates is called secret function SP (Secret Permutation). 3 shows an example of SPG and SP.
  • FIG. 4 is a conceptual diagram showing an embodiment of the invention system.
  • This system includes a communication channel that transmits an encrypted text and two terminals connected to it, and each terminal has an encryption key K e and a decryption key K d related to encryption and decryption.
  • the communication channel includes an ordinary transmission cable and a transmission device, and FIG. 4 shows an example of one-way communication, but it is also possible to operate in the opposite direction in the same way to enable two-way communication.
  • Each terminal of the transmission and reception of FIG. 4 is composed of an encoder (ENC), a decoder (DEC), and an encryption key generator (MKG) as shown in FIG. 5.
  • ENC encoder
  • DEC decoder
  • MKG encryption key generator
  • the encryptor is a GA operator that generates a cipher text through a group action using an input queue for processing message input and a disposable public key through an algorithm according to an embodiment of the present invention, as shown in FIG. And there is an output queue that processes the output of the generated ciphertext.
  • the GA operator receives a symmetric key (Q AB ) of the transmitting / receiving terminal and the public key (G B ) of the receiving terminal from the encryption key generator (MKG) as a message input, and generates a cipher text through permutation (GA operation).
  • the diffusion function F (x) is preprocessed and encrypted through the XOR operator.
  • the group's message queue can receive pre-processed messages and generate cryptograms.
  • the decoder is a GA operator that restores the original message through group action using an input queue that processes ciphertext input and an algorithm according to an embodiment of the present invention, using a disposable private key. And, there is an output queue that processes the output of the restored original text message.
  • the GA operator receives the symmetric key (Q AB ) of the transmitting / receiving terminal and the private key (H B ) of the receiving terminal from the encryption key generator (MKG) as an input of the cipher text to restore the original message through permutation (GA operation).
  • the message restored by the decoder is post-processed through the XOR operator with the same diffusion function F (x) applied to the transmitting terminal. You can restore the message.
  • the cryptographic key generator is a random number generator (PRNG), a permutation generator, and a plurality of key generation modules (MSK_ , MSK_ , MPK, SK, PK), and a GA operator.
  • the random number generator is a key driven function KDF (key driven function) using multiple parameters such as the unique personal identifier (ID), device ID, event, and time of a participant that can be known only by the pre-registered send and receive participants. ) To generate a disposable pseudorandom number.
  • the generated random numbers are provided by a permutation generator and a key generation module, respectively.
  • the permutation generator generates a disposable pseudorandom number sequence (PRP) through a random number generator and a unique key induction function (KDF).
  • PRP pseudorandom number sequence
  • KDF unique key induction function
  • the key generation modules are the master key vector (MSK_), which is a vector function representing the recipient's Secret Permutation Group. Module, master kiss color module (MSK_) that determines the secret function to receive ), A symmetric key module (MPK) that generates a symmetric key shared only by a sender and a receiver, a public key module (PK) and a private key module (SK), which are generated in pairs for each transmission / reception event.
  • the master key module and the symmetric key modules generate different key values each time through a random number generator or permutation generator through a key induction function (KDF) using multiple unique personal identification information as parameters.
  • KDF key induction function
  • the key is stored in the key storage of and the key values generated by the private key module and public key module are distributed to generate the private key and public key. It is also distributed to the encryptor and decryptor of the corresponding terminal requesting the key.
  • the private key module generates a private key.
  • the private key is generated by arranging random values generated from the master key scalar module at a position specified by the master key vector module, and arranging the random number sequences provided by the permutation generator at the remaining positions.
  • the GA operator in the cryptographic key generator plays a role in generating the public key through the symmetric key and the private key, unlike the cryptographic or decryptor permutation operator that performs the operations required to generate the ciphertext and the original message, respectively.
  • the key generated from the private key module SK is called H
  • the key generated from the symmetric key module MPK is called Q
  • the public key generated by the permutation operator is G
  • the public key G calculated as a result of calculation is output to the public key module PK, stored, and distributed to the corresponding encryption or decryptor.
  • the message set M consists of a number from 0 to 9, that is,
  • 10
  • 9 shows that the ciphertext 5301689742 is generated through the encryptor of the user A terminal.
  • permutation group-based message encryption transmission method may be implemented according to the method and procedure shown in FIG. 10.
  • a transmitting / receiving participant In order to transmit a message using the system according to the embodiment, a transmitting / receiving participant must register personal identification information or the like in the system in advance and be approved as an allowed participant.
  • the first step of the transmission method is a setup step, and a user identification factor (phone number, user id, email address etc.), a terminal device to identify a participating object in an encryption key generator (MKG) Personal identification information such as identification factors (device id, MAC address, ip address, faceid, fingerprint etc.), secret permutation generator, etc. are registered, and the cryptographic key generator (MKG) registers the object Create identification numbers, master keys, etc.
  • a user identification factor phone number, user id, email address etc.
  • MKG encryption key generator
  • the master key is a vector function that can identify secret function candidates (SPCs) from the entire permutation group of messages, and this key vector function T is a pair of (tp, tv) vectors and T ⁇ I M ⁇ M.
  • the tp of the master key T is created or registered at the time of setting, and the function value tv of the master key T is determined at the time of encryption execution to designate a specific secret function (SP) among the secret function candidates (SPC) and related participants.
  • SP secret function
  • the second step is a key generation step for encryption in the encryption key generator, and generates symmetric and private key and public key pairs necessary for encryption and decryption.
  • a symmetric key that only the transmitting and receiving parties can know is generated.
  • a secret function SP is designated by assigning a one-time function value to the master key (function) generated in the setting step, and a private key is generated based on the personal identification information previously registered in the setting step.
  • the public key is generated by permutation (GA) of the generated symmetric key and private key.
  • the sender requests and obtains the public key of the receiver, which is the encryption key, through the encryption key generator to generate the encrypted text.
  • the symmetric key is already possessed by each transmitting and receiving terminal in two steps. At this time, the keys of the participating objects are already generated in the second key generation step, and thus can be easily obtained.
  • a cryptographic text is generated by calculating the public key of the receiver and the symmetric key already possessed through the permutation operator. The process is expressed mathematically as follows.
  • D d 1 d 2 ... d k :
  • Message sequence D is when d i is a continuous message string composed of elements of message set M.
  • the receiver obtains the recipient's private key which is the encryption key through the encryption key generator.
  • the symmetric key is already possessed by each transmitting and receiving terminal in two steps. At this time, the keys of the participating objects are already generated in the second key generation step, and thus can be easily obtained.
  • the original message is restored by calculating the recipient's private key and the symmetric key already possessed through the permutation operator.
  • the process is expressed mathematically as follows.
  • 11 to 14 show specific examples of the step-by-step implementation of the message encryption transmission method according to an embodiment of the present invention.
  • the process of restoring the original text message by receiving and receiving the numeric string “4581290367” consisting of 10 numbers from the message set using the numbers from 0 to 9 as an element from the terminal A to the terminal B is generated as a message and receiving it. Step by step, specifically shown in Figure 11 through 14.
  • the ID of the transmitting terminal A and the receiving terminal B is registered in the encryption key generator for transmission and reception in the setting step 1 and the master private key vector functions ⁇ (2, v 1 ), (4, v 2 ), (6) , v 3 ), (8, v 4 ) ⁇ are generated, and the master public key generation function is set.
  • Fig. 12 shows the vector key allocation of the master key vector function as a two-step key generation step and how the private key is generated. It also shows how function values are assigned to symmetric key generation functions through permutation generators and public keys are generated through private and permutation operators.
  • FIG. 13 a specific example of how the operation is performed and the ciphertext is generated through the permutation operation in the GA operator through the encryption keys MPK, SK, and PK generated through the first and second steps in the third step ciphertext generation step. Shows through.
  • the encryption step generated in the first and second stages is the encryption step MPK, SK, and PK in the fourth step ciphertext decryption step, and how the operation is performed through the permutation operation in the GA operator and how the received ciphertext is converted to the original message. Decryption and restoration are shown through specific examples.
  • Each transmitting / receiving terminal of the electronic signature system is functionally the same in the same structure as the encryptor or decoder described in the previous embodiment, but differs in that it operates using different keys and different inputs.
  • Each terminal of the transmission / reception of the signature / verification system includes a signer (SIGN), a verifier (VERIFY), and an encryption key generator (MKG) as shown in FIG. 15.
  • the signer (SIGN) generates a signature through a permutation (Group Action) using a disposable private key through an input queue that processes message input as shown in FIG. 16 and an algorithm according to an embodiment of the present invention.
  • the group's message queue can receive a pre-processed message and generate a signature.
  • the verifier verifies a signature statement through a group action by using a disposable public key through an input queue for receiving and processing a signature and an algorithm according to an embodiment of the present invention.
  • a GA operator that generates the original text message that has been verified and accepted, and an output queue that processes the output of the verified / accepted original message.
  • the GA operator receives the symmetric key (Q AB ) of the transmitting / receiving terminal and the public key (G A ) of the transmitting terminal from the cryptographic key generator (MKG) as the input of the signature, and verifies the signature through permutation (GA operation). Check the acceptance / rejection and verify the original message.
  • the message verified by the verifier is post-processed through the XOR operator with the same diffusion function F (x) applied to the transmitting terminal. Can be restored.
  • the cryptographic key generator (MKG) shown in the signature / verification system of FIG. 15 includes a random number generator (PRNG), a permutation generator, and a plurality of key generation modules (MSK_) as shown in FIG. , MSK_ , MPK, SK, PK) and permutation operators (GA Operators) that provide the same structure and function as in an encryptor or decoder, and work the same.
  • PRNG random number generator
  • MSK_ key generation modules
  • MPK MPK
  • SK SK
  • PK permutation operators
  • G Operators permutation operators
  • a signature / verification method may be performed using a permutation group-based message encryption / decryption algorithm according to the method and procedure shown in FIG. 18.
  • the method of signing and verifying a message according to an embodiment of FIG. 18 may be performed by a procedure of 4 steps, and a method of registering and setting a 1st step sending / receiving participating object and a 2nd step key generation method and procedure are as described above. It performs the same method and procedure described in one embodiment of the encryption / decryption method.
  • the sender requests and obtains the private key of the sender, which is the signature key, through the encryption key generator to generate the signature.
  • the symmetric key is already possessed by each transmitting and receiving terminal in two steps. At this time, the keys of the participating objects are already generated in the second key generation step, and thus can be easily obtained.
  • the sender's private key and the already symmetric key are computed through the permutation operator to generate a signature. The process is expressed mathematically as follows.
  • the recipient obtains the disposable public key of the sender, which is the verification key through the encryption key generator.
  • the symmetric key is already possessed by each transmitting and receiving terminal in two steps. At this time, the keys of the participating objects are already generated in the second key generation step, and thus can be easily obtained.
  • the public key of the sender and the symmetric key already possessed are calculated through the permutation operator to verify the signature and accept or reject the verified original message. The process is expressed mathematically as follows.
  • x x 1 x 2 ... x k
  • 19 to 22 show a specific example of a step-by-step implementation of a method for transmitting a message signature as an embodiment of the present invention.
  • An example is a process of verifying an original message by receiving a message from a set of messages with numbers from 0 to 9 as an element from terminal A to terminal B and generating a signature by sending a number string of “4581290367” as a message. It is shown through Fig. 19 to Fig. 22 specifically for each step.
  • the ID registration of the transmitting terminal A and the receiving terminal B to the encryption key generator for transmission and reception in the first stage setting step and the master key vector functions ⁇ (1, v 1 ), (3, v 2 ), (5, v 3 ), (7, v 4 ) ⁇ are generated, and the symmetric key generation function is set.
  • FIG. 20 a vector value allocation of a master key vector function as a two-step key generation step, and shows how a single-use private key is generated through this. It also shows how function values are assigned to symmetric key generation functions through permutation generators and public keys are generated through private and permutation operators.
  • the three-step signature statement generation step is an encryption key generated through the first and second steps MPK, SK, and PK, and how the operation is performed through the permutation operation in the GA operator and the signature statement is generated. Show through specific examples.
  • the operation is performed and the received signature statement is received through the permutation operation in the GA operator through the encryption keys MPK, SK, and PK generated through the 1st and 2nd steps as the acceptance / rejection step of the 4-step verification message. It shows how to be verified and accepted / rejected by the original message through specific examples.
  • Encryption / decryption system including message signing / verification
  • Each transmission / reception terminal in the encryption system that provides electronic signature and verification has the same structure as the encryptor (ENC), the decoder (DEC), and the encryption key generator (MKG), as shown in FIG. 5, but the encryption (ENC) and decryption
  • the DEC may be changed to include a signer and a verifier as shown in FIGS. 23 and 24, respectively.
  • the encryptor ENC has two structures, such as an input queue for processing message input and a GA operator for generating a cipher text and a GA operator for generating a signature, with a structure in which the signer of FIG. 25 is combined with the encryptor of FIG. Another GA operator is included, and the GA operator for generating a cipher text receives a message from an input queue and receives a signature from the GA operator for generating a signature text, and performs permutation on (Message + Signature) as in the example of FIG. To create a ciphertext.
  • the decoder DEC combines the decrypter of FIG. 6 with the verifier of FIG. 27 to input queues for processing cipher text input and GA operators for message recovery (for decryption) and GA operators for signature verification. Two other GA operators are included, and for message restoration (for decryption), the GA operator receives and decrypts the encrypted text from the input queue to restore (message + signature), where the signature is delivered to the verified GA operator for verification. For the GA operator, a verified message is generated as illustrated in FIG. 27. The message output from two different GA operators determines whether to accept or reject the message through the AND operation.
  • an encryption transmission method for a message signed using a permutation group-based public key may be implemented as shown in FIG. 26.
  • the method for encrypting and transmitting an encrypted message to a signed message may be performed by a six-step procedure, and the first and second registration and setup methods and the second and second key generation methods and procedures are described above.
  • the method and procedure described in one embodiment of the encryption / decryption method of FIG. 10 are performed.
  • the method and procedure for generating the signature in the third step are the same as in the message signing / verifying method in FIG. 18.
  • the message to be transmitted is combined with the signature generated in the third step to encrypt (message + signature) with the recipient's public key.
  • Q AB (M + M s ) C' (K e is the public key of recipient B (G B ))
  • the fifth step restores M + M s by decrypting the received cipher text M 'as illustrated in FIG. 27.
  • V (M s , Kv) Q AB -1 G A
  • Q AB (M s ) M ”(K v is the public key of the sender A (G A ))
  • the signature uses the private key that is generated only once by the signed participant, so no one can create it except the signed participant. Therefore, a sender cannot deny transmission of a message for a message transmitted through a signed message transmission method according to an embodiment.
  • the encryption key used for encryption utilizes elements that make up the message space, such as digits, characters, and images. For example, it is possible to implement a 256 byte encryption system by extending the extended ASCII code with an encryption key space to encrypt characters.
  • the system of the present invention can be implemented in a two-tier structure (2 tier) or a three-tier structure (3 tier).
  • the two-tier structure (2 Tier), it can be applied to a structure that communicates without going through an intermediate medium of encrypted communication between a sender transmitting an encrypted message and a receiver receiving and decrypting the encrypted message.
  • the one-way communication method in which the role between the sender and the receiver that transmits and receives the encrypted message is one-sided, fixed and unchanged, and the two-way (two way) when mutually transmitting / receiving the encrypted message ) All communication can be implemented.
  • both the sender and the receiver can perform both encryption and decryption objects.
  • An example of implementation of such a system may be applied to one-to-one communication, peer-to-peer communication, and one-to-many communication.
  • relaying with other systems such as performing encryption / decryption functions or converting to other communication protocols, or the like, between a sender transmitting an encrypted message and a receiver receiving an encrypted message or plain text, or It can also be applied to a structure that communicates through a gateway that performs interworking functions.
  • the gateway when the gateway sends a message to a receiver designated by the sender, it decrypts itself and transmits the plaintext itself, or converts it into another encryption method or other communication protocol format that the receiver wants. It is possible to send a message in a changed format through a task, or to send an encrypted message sent by the sender to the receiver.
  • IoT network methods such as Sensor-Gateway-Server, Sensor-Gateway-Sensor, and traditional 3-tier or N-tier structures ( It can be applied to a multi-object participation communication system called N-Tier) method.
  • a transmitting terminal or a receiving terminal refers to a terminal connected to enable communication through at least one network, for example, a mobile phone, a smart phone, a laptop computer, and digital broadcasting.
  • Mobile terminals such as terminals, personal digital assistants (PDAs), portable multimedia players (PMPs), slate PCs, tablet PCs, ultrabooks, and fixed terminals such as digital TVs and desktop computers It may be, but is not particularly limited.
  • an asymmetric cryptographic communication system using a permutation group based disposable public key that is safe and applicable to various environments.
  • a disposable public key that uses a public permutation generated for one time and a private key that uses a private permutation generated by the receiving terminal only for one-time use to decrypt the cipher text generated through it. It is possible to implement a cryptographic communication system using asymmetric keys only possible through.
  • both the disposable public key and the disposable private key can be generated only through the master private key of the receiving terminal capable of decrypting the ciphertext, and through a secure method, the disposable public key can implement a system shared with the transmitting terminal. It is implemented with the Trap Door function of cryptography that is difficult to restore or estimate the original text with the disposable public key related information held by the transmitting terminal or the encrypted text generated through it.
  • the public key and private key can be changed automatically or manually during the encrypted communication process at random or after communication for the purpose of improving security, etc., and the creation / change operation is performed only by the user / system / who has the master private key with decryption authority. It is performed by the device. Through these functions, it is possible to implement characteristics that are difficult to estimate through exposure of public and private keys used in cryptographic communication systems, collection of cryptographic texts, and reverse engineering.
  • the permutation key which is an encryption-related key required for the encryption communication system.
  • the public key / private key required in the encryption and decryption process is generated by the receiving terminal, and when generated and changed, the generating terminal (time, space, etc.) and the changing condition have been previously agreed upon by the transmitting terminal and the receiving terminal.
  • Each has its own permutation operator and implements it so that the transmitting terminal can generate the same virtual public key by itself, without performing the step of directly transmitting / receiving the encryption-related key information essential in the encryption communication process.
  • a system such as key cryptography can be constructed.
  • the plaintext with information about it is derived. It is possible to implement an encrypted communication system that is difficult to decrypt or estimate.
  • the public key and the private key are randomly changed every time according to the security policy or system requirements, even after the relevant information has been exposed, the password generated by the malicious user who possessed the previous information can be arbitrarily or unauthorizedly decrypted. Implementation is possible.
  • the present invention uses an asymmetric method on a permutation basis, and can be implemented in various ways depending on the message type because encryption processing can be performed in byte units or message processing units of a desired size.
  • the calculation is performed directly in the application message processing unit, and the message can be encrypted in block units, and thus the processing speed can be significantly increased compared to the conventional technology that must be reconstructed into a form that can be used in the application.
  • the present invention can be implemented in a low-performance CPU device.
  • the present invention can implement both symmetric and asymmetric key methods in a single cryptosystem, can handle all various message types in an application, and can implement flexible functions under 2-Tier and 3-Teir communication structures. It can be applied to both existing systems based on password / PIN, human to machine, or systems that adopt new machine to machine.
  • the system of the present invention can be applied as a single system even under a new iot environment operating under various communication structures based on lightweight / low-capacity devices, and it is also possible to interwork with an existing encryption technology-based system.
  • the method for transmitting a message using a permutation group-based disposable public key may be implemented in the form of program instructions that can be executed through various computer components and recorded in a computer-readable recording medium.
  • the computer-readable recording medium may include program instructions, data files, data structures, or the like alone or in combination.
  • the program instructions recorded on the computer-readable recording medium may be specially designed and configured for the present invention or may be known and available to those skilled in the computer software field.
  • Examples of computer-readable recording media include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical recording media such as CD-ROMs, DVDs, and magneto-optical media such as floptical disks.
  • optical media such as ROM, RAM, flash memory, and the like.
  • program instructions include not only machine language codes produced by a compiler, but also high-level language codes executable by a computer using an interpreter or the like.
  • the hardware device may be configured to operate as one or more software modules to perform processing according to the present invention, and vice versa.
  • the space probability of the present invention system is always the same probability, whereas the space probability decreases for each brute-force attack. Provided, even if the random function that derives the key provides even probability distribution, brute-force attack is probabilistically difficult.
  • the encryption result is obtained because the key space and the crypto space are expanded into a multi-dimensional space using the variable functions included in the permutation group as mentioned above.
  • quantum computers it is difficult to decipher even if cryptography is performed through a computer with improved computing power, so it has quantum resistance.
  • the existing asymmetric key method is vulnerable to a man-in-the-middle, and in order to solve this problem, a certificate of identity is provided to all participants participating in cryptographic communication through a third-party certificate authority. Certificate) and it is necessary to establish an infrastructure to enable cryptographic communication according to the authenticity of this warranty. Therefore, it is necessary to construct an inexpensive infrastructure for cryptographic communication using an asymmetric key method that is safe for man-in-the-middle attacks, and there is a problem in that the encryption process is complicated and the processing time is long due to this infrastructure.
  • the system of the present invention performs encryption / decryption by generating a different key each time, an intermediate attack is impossible, and thus it is possible to safely perform cryptographic communication without the need for a trusted authority (CA) or an identity certificate introduced to solve this problem.
  • CA trusted authority

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Storage Device Security (AREA)

Abstract

본 발명은 메시지를 암호화 하여 송신하는 송신 단말과, 상기 암호화된 메시지를 복호화하는 수신 단말을 포함하며, 상기 송신 단말 및 수신 단말은 순열그룹에 기반하여 순열형태인 대칭키와 비대칭키를 동시에 합성하여 메시지를 암호화 한 후 송수신하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템을 개시한다.

Description

순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법
본 발명은 순열 그룹 기반의 암호 기술(cryptographic technologies)을 이용한 암호화 방법 및 시스템에 관한 것으로, 보다 상세하게는 암호 생성 객체(이하 “송신자”)와 암호 해제 객체(이하 “수신자”)가 메시지를, 원래의 메시지를 구성하는 메시지 공간과는 다른 공간으로, 이동 또는 확장 등을 통해 새로운 공간으로 변경시키는 비밀함수그룹(secret permutations group)을 서로 다르게, 사전에 또는 필요시 동적으로 사전 지정하거나 임의의 횟수나 시간 또는 특정한 통신 시점마다 매번 다르게 사전 약정한 시간 동안 유효하도록 생성한 후, 송신자와 수신자가 사용할 서로 다른 공간이 상호 연결/매핑 할 수 있도록 하는 유일한 비밀 함수(secret permutation)을 매번 다르게 생성하여 상호 연결된 공간을 통해 안전하게 암호문을 생성/전송/복원하기 위한 방법 및 그를 이용한 시스템에 관한 것이다. 이렇게 함으로써 기존 암호 기술이 매번 동일한 메시지 공간과 동일한 특정 값만 사용함에 따른 비밀 정보가 노출되는 보안상 문제점을 해결하고자 한다.
1994년 MIT 응용 수학자인 Peter Shor에 의해 양자 컴퓨팅을 이용한 암호화 알고리즘(이하 양자 기반 알고리즘)을 이용할 경우 소인수분해에 걸리는 시간이 획기적으로 줄어들 수 있다는 것이 증명되자 전세계 보안전문가들은 충격에 빠졌다. Shor 알고리즘에 의하여 현재 지수적 연산을 수행하는 수인수분해 기법과 이산로그문제에 기반한 공개키 암호화가 짧은 시간에 해독이 가능하게 되기 때문이다.
양자 기반 알고리즘에는 위에 언급한 Shor 알고리즘과 Grover 알고리즘이 있다. 대칭키 암호화에 영향을 끼치는 Grover 알고리즘에 따르면 대부분의 대칭키 암호화 방식은 암호키를 두배로 늘리는 것으로 기존과 동일한 수준의 보안이 가능하지만, Shor 알고리즘이 구현된 양자컴퓨터가 개발되면 현재 사용하는 공개키 암호화 방식은 더 이상 사용할 수 없게 된다.
지금껏 대부분의 비밀은 비대칭 암호화의 형태로 보호되어왔다. 1976년 위트필드 디피(Whitfield Diffie), 마크 헬만(Mark Hellman), 랄프 메클(Ralph Merkle)이 '암호의 새로운 방향'(New Directions in Cryptography)이라는 세미나 논문에서 해당 개념을 공개한 이후의 이야기다. RSA, SSL, TLS, HTTPS를 생각해 보자. 대부분의 웹사이트, 전자 서명 다운로드, 온라인 금융 거래, VPN, 스마트카드, 대부분의 무선 네트워크에 이 개념이 적용된다. 현대의 보안 통신은 전통적인 디지털 컴퓨터가 큰 소수를 포함해 다인자 수식을 쉽게 처리할 수 없다는 점에 기초한다. 그러나 양자 컴퓨팅의 도입으로 이런 보호 장치로 암호화된 비밀이 모두 무효화되게 된다. 실제로 세계의 주요 국가들이 추후에 복호화를 하기 위해 암호화된 네트워크 트래픽을 상당 부분을 기록 및 저장하고 있으며 그 날이 오기만을 기다리고 있다는 주장도 있다.
아래 표 1은 현재 많이 사용되고 있는 암호화 기법에 대하여 미치는 영향을 정리하였다.
암호알고리즘 형태 목적 양자 컴퓨터의 영향
AES-256 Symmetric key Encryption Secure
SHA-256, SHA-3 - Hash functions Secure
RSA Public key 전자서명, 키설정 No longer secure
ECDSA, ECDH(타원암호) Public key 전자서명, 키교환 No longer secure
DSA(finite field Cryptography) Public key 전자서명, 키교환 No longer secure
아래 표 2는 현재 사용하는 암호기법에 대하여 양자컴퓨팅 환경에서 보안수준이 어떻게 변하는 지 비교하여 보여준다.
암호기법 키사이즈 효과적인 키강도/보안수준(bits)
기존 컴퓨팅 퀀텀 컴퓨팅
RSA-1024 1024 80 0
RSA-2048 2048 112 0
ECC-256 256 128 0
ECC-384 384 256 0
AES-128 128 128 64
AES-256 256 256 128
다가오는 양자컴퓨팅 시대에 더이상 안전하지 않은 공개키 암호화 기법으로 인해 발생할 혼란을 대비하기 위해서도 양자컴퓨터가 풀 수 없는 양자내성 암호화 기법이 필요한 실정이다. 따라서 이러한 문제를 해결하고자 본 발명에서는 현재 컴퓨팅 환경에서도 효율적으로 작동하고 양자컴퓨팅 환경에서도 안전하게 데이타를 보호하는 양자내성(post-quantum) 암호화 기법 및 시스템을 제안한다.
제안되는 양자저항(post quantum) 암호화 기법은 양자컴퓨팅 환경으로 인해 더이상 안전하지 않은 공개키 암호화 기법을 대체해야 하는 만큼 성능, 보안성, 사용성 면에서 기존의 공개키 방법보다 개선되어야 하며, 양자컴퓨터 뿐아니라 현재 사용하는 컴퓨팅환경에도 적합하여야 한다.
따라서 본 발명에서는 첫째, 양자 기반 알고리즘으로 해독되는 기존의 복잡한 수학연산에 기반한 방법을 사용하지 않고 순열그룹(permutation group)에 기반하여 각각 순열형태인 대칭키와 비대칭키를 동시에 합성(composition)하는 연산 방식을 사용하고 키배열 변환 방식으로 다차원 확장을 통해 복잡한 수학연산을 사용하지 않고 키공간을 확장하여 복잡도를 높이고 복잡한 수학연산을 수행하지 않고 대칭키 암호화 기법의 SPN(substitution-permutation-network)에서 처리하는 방식과 같은 값의 대치, 변환 등 연산을 수행하여 빠른 암호화 처리를 가능하게 하였다.
둘째, 기존 방식이 도 1과 같이 한 번 생성된 키값을 사용하여 고정된 키함수의 수학연산을 하는 방식을 사용하는데 비해 본 발명에서는 송신자가 메시지를 전송할 때마다 도 3과 같이 수신자가 선택한 다차원 공간의 키함수들을 사용하여 매번 다른 공간의 키함수들을 통해 매번 다른 키값들을 생성하여 사용하므로 양자컴퓨터와 같은 컴퓨팅 파워의 향상 등 계산능력이 향상된다 하더라도 안전한 보안성을 제공한다.
셋째, 아래 표 3과 같이 RSA 등 기존의 공개키에 비하여 더 작은 키사이즈로 높은 보안성을 보여준다. 따라서 기존의 컴퓨터에 사용하는 공개키를 무리없이 대체 가능하다.
키사이즈(bits) 효과적인키강도/보안수준(bits)
기존 컴퓨팅 양자 컴퓨팅
256(|M|=32) 128(AES) 64
512(|M|=64) 256(AES) 128
1024(|M|=128) 768(AES) 384
2048(|M|=256) 1536(AES) 768
본 발명은 메시지를 암호화 하는 암호화 수행객체와, 상기 암호화된 메시지를 복호화하는 복호화 수행객체를 포함하며, 상기 암호화 수행객체 및 복호화 수행객체는 순열그룹에 기반하여 순열형태인 대칭키와 비대칭키 중 공개키를 동시에 합성하여 메시지를 암호화 한 후 이를 다시 복호화 시에는 순열 그룹에 기반하여 순열 형태인 대칭키와 비대칭키 중 개인키를 사용하여 원문을 복호화하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템을 개시한다.
본 발명의 일 실시예에 따르면, 상기 암호화 수행객체 및 복호화 수행객체는 암호화키(K e)를 이용하여 메시지를 암호화 하는 암호화기(ENC)와, 메시지를 복호화키(K d)를 이용하여 복호화 하는 복호화기(DEC)와, 암호키생성기(MKG)를 포함한다.
본 발명의 일 실시예에 따르면, 상기 암호화기는 메시지 입력을 처리하는 입력큐와, 일회용 공개키를 이용하여 순열연산을 통해 암호문을 생성하는 GA 연산기와, 상기 생성된 암호문의 출력을 처리하는 출력큐를 포함한다.
본 발명의 일 실시예에 따르면, 상기 GA 연산기는 상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 복호화 수행객체의 공개키(G B)를 제공받아 순열연산을 통해 암호문을 생성한다.
본 발명의 일 실시예에 따르면, 상기 순열연산은 Q AB -1G BQ AB(M) = C 수식에 의하여 이루어지며, Q AB는 암호화 수행객체와 복호화 수행객체의 대칭키, G B 는 복호화 수행객체의 공개키, M은 메시지 공간, C는 암호문 공간인 것을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 복호화기는 암호문 입력을 처리하는 입력큐와, 일회용개인키를 이용하여 순열연산을 통해 원문메시지를 복원하는 GA 연산기와, 상기 복원된 원문메시지의 출력을 처리하는 출력큐를 포함한다.
본 발명의 일 실시예에 따르면, 상기 GA 연산기는 상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 복호화 수행객체의 개인키(H B)를 제공받아 순열연산을 통해 원문 메시지를 복원한다.
본 발명의 일 실시예에 따르면, 상기 순열연산은 H BQ ABQ AB(C) = M 수식에 의하여 이루어지며, Q AB는 암호화 수행객체와 복호화 수행객체의 대칭키, H B 는 복호화 수행객체의 개인키, M은 메시지 공간, C는 암호문 공간인 것을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 암호키생성기는 복수의 매개변수를 사용한 키유도함수 KDF(key derivation function)를 통해 일회용 유사난수를 생성하는 난수생성기(PRNG)와, 상기 키유도함수(KDF)를 통해 일회용 유사난수순열(PRP)를 생성하여 키생성모듈에 제공하는 순열생성기를 포함한다.
본 발명의 일 실시예에 따르면, 상기 키생성모듈은 복호화 수행객체의 비밀함수그룹(secret permutation group)을 나타내는 벡터함수인 마스터키벡터(MSK_
Figure PCTKR2019015346-appb-img-000001
) 모듈과, 복호화 단계에 사용될 비밀함수(secret permutation)를 결정하는 마스터키스칼라모듈(MSK_
Figure PCTKR2019015346-appb-img-000002
)과, 암호화 수행객체와 복호화 수행객체 간 공유하는 대칭키를 생성하는 대칭키모듈(MPK)과, 메시지 암호화와 복호화 시 사용되는 공개키와 개인키를 함께 생성되는 공개키모듈(PK)과 개인키모듈(SK)을 포함한다.
본 발명의 일 실시예에 따르면, 상기 마스터키벡터(MSK_
Figure PCTKR2019015346-appb-img-000003
) 모듈, 마스터키스칼라모듈(MSK_
Figure PCTKR2019015346-appb-img-000004
) 및 대칭키모듈(MPK)은 복수의 고유 개인 식별정보를 매개변수로 하여 키유도함수(KDF)를 통해 같은 값이나 상호 약정한 방식에 따라 다른 키 값들을 생성한다.
또한, 본 발명은 암호키생성기가 식별인자를 이용하여 마스터키를 생성하는 단계와, 암호키생성기에서 암호화와 복호화에 필요한 대칭키, 개인키 및 공개키 쌍을 생성하는 단계와, 암호화 수행객체가 대킹키와 암호화키인 복호화 수행객체의 공개키를 수신하여 암호문을 생성하는 단계와, 복호화 수행객체가 암호키생성기를 통해 대칭키와 복호화 수행객체의 개인키를 통해 생성된 암호문을 복원하는 단계를 포함하는 암호화 및 복호화 방법을 개시한다.
본 발명의 일 실시예에 따르면, 상기 식별인자는 사용자의 개인정보를 포함하는 사용자 식별인자, 사용자 단말 정보를 포함하는 단말장치 식별인자 및 비밀함수 생성인자 중 적어도 하나를 포함한다.
본 발명의 일 실시예에 따르면, 상기 암호문은 상기 생성된 대칭키 및 복호화 수행객체의 공개키를 이용하여 GA 연산기에 연산시켜 생성한다.
본 발명의 일 실시예에 따르면, 상기 암호문(C)은 암호화 함수(E)에 암호화키(K e)를 대입하여 순열연산(M × K → C)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
E (M, K e) = Q -1GQ(M) = C
여기서 Q -1GQ 는 순열함수 G, Q의 순열연산(left multiplication)이고, 메시지 M = (m 1
Figure PCTKR2019015346-appb-img-000005
m n), 키 K = (k 1
Figure PCTKR2019015346-appb-img-000006
k n), 암호문 C = (c 1
Figure PCTKR2019015346-appb-img-000007
c n)는 메시지집합 M = {m 1
Figure PCTKR2019015346-appb-img-000008
m n} 상에서의 순열그룹 G의 원소인 것(M,K,C ∈ G)을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 암호문의 복원은 복호화 함수(D)에 복호화키(K d)를 대입하여 순열연산(C × K → M)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
D (C, K d) = HQQ(C) = M
여기서 HQQ 는 순열함수 H, Q의 순열연산(left multiplication)이고, 메시지 M = (m 1
Figure PCTKR2019015346-appb-img-000009
m n), 키 K = (k 1
Figure PCTKR2019015346-appb-img-000010
k n), 암호문 C = (c 1
Figure PCTKR2019015346-appb-img-000011
c n)는 메시지집합 M = {m 1
Figure PCTKR2019015346-appb-img-000012
m n} 상에서의 순열그룹 G의 원소인 것(M,K,C ∈ G )을 특징으로 한다.
또한, 본 발명은 암호문 작성시 서명문을 생성하는 서명 수행객체과, 상기 암호문을 원문 메시지로 복호화 하기 위하여 상기 서명문을 검증하도록 형성되는 검증 수행객체를 포함하며, 순열 그룹에 기반하여 순열 형태인 대칭키와 비대칭키를 이용하여 서명문을 생성하고 검증하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 서명 검증 시스템을 제공한다.
본 발명의 일 실시예에 따르면, 상기 서명 수행객체 및 검증 수행객체는 순열연산을 통해 서명문을 생성하는 서명기와, 순열연산을 통해 상기 서명문을 검증하는 검증기와, 암호키생성기(MKG)를 포함한다.
본 발명의 일 실시예에 따르면, 상기 서명기는 메시지 입력을 처리하는 입력큐와, 일회용개인키를 이용하여 순열연산을 통해 서명문을 생성하는 GA 연산기와, 상기 생성된 서명문의 출력을 처리하는 출력큐를 포함한다.
본 발명의 일 실시예에 따르면, 상기 서명기의 GA연산기는 상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 서명 수행객체의 개인키(H A)를 제공받아 순열연산을 통해 서명문을 생성한다.
본 발명의 일 실시예에 따르면, 상기 서명기의 순열연산은 Q AB -1H AQ AB(M) = M s 수식에 의하여 이루어지며, Q AB는 서명 수행객체와 검증 수행객체의 대칭키, H A는 서명 수행객체의 개인키, M은 메시지(m 1
Figure PCTKR2019015346-appb-img-000013
m n), M S는 서명문(s 1
Figure PCTKR2019015346-appb-img-000014
s n)인 것을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 검증기는 서명문을 입력받아 처리하는 입력큐와, 일회용공개키를 이용하여 순열연산을 통해 서명문을 검증하여 수락된 원문메시지를 생성하는 GA 연산기와, 상기 수락된 원문메시지의 출력을 처리하는 출력큐를 포함한다.
본 발명의 일 실시예에 따르면, 상기 검증기의 GA연산기는 상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 서명 수행객체의 공개키(G A)를 제공받아 순열연산을 통해 서명문을 검증하고 수락 또는 거절 여부를 확인한다.
본 발명의 일 실시예에 따르면, 상기 검증기의 순열연산은 G AQ ABQ AB(M s) = M 수식에 의하여 이루어지며, Q AB는 서명 수행객체와 검증 수행객체의 대칭키, G A는 서명 수행객체의 공개키, M은 메시지(m 1
Figure PCTKR2019015346-appb-img-000015
m n), M S는 서명문(s 1
Figure PCTKR2019015346-appb-img-000016
s n)인 것을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 암호키생성기는 복수의 매개변수를 사용한 키유도함수 KDF(key derivation function)를 통해 일회용 유사난수를 생성하는 난수생성기(PRNG)와, 상기 키유도함수(KDF)를 통해 일회용 유사난수순열(PRP)를 생성하여 키생성모듈에 제공하는 순열생성기를 포함한다.
본 발명의 일 실시예에 따르면, 상기 키생성모듈은 서명 수행객체의 비밀함수그룹(secret permutation group)을 나타내는 벡터함수인 마스터키벡터(MSK_
Figure PCTKR2019015346-appb-img-000017
) 모듈과, 복호화할 때 사용될 비밀함수(secret permutation)를 결정하는 마스터키스칼라모듈(MSK_
Figure PCTKR2019015346-appb-img-000018
)과, 서명 수행객체와 검증 수행객체 간 공유하는 대칭키를 생성하는 대칭키모듈(MPK)과, 메시지 암호화와 복호화 시 사용되는 복호화 수행객체의 한 쌍의 비대칭키인 공개키와 개인키를 함께 생성되는 공개키모듈(PK)과 개인키모듈(SK)을 포함한다.
본 발명의 일 실시예에 따르면, 상기 마스터키벡터(MSK_
Figure PCTKR2019015346-appb-img-000019
) 모듈, 마스터키스칼라모듈(MSK_
Figure PCTKR2019015346-appb-img-000020
) 및 대칭키모듈(MPK)은 객체들을 상호 구분할 수 있는 하나 이상의 식별정보를 매개변수로 하여 키유도함수(KDF)를 통해 키 값들을 생성한다.
또한, 본 발명은 암호키생성기가 식별인자를 이용하여 마스터키를 생성하는 단계와, 암호키생성기에서 암호화와 복호화에 필요한 대칭키, 개인키 및 공개키 쌍을 생성하는 단계와, 서명 수행객체가 상기 생성된 대칭키와 서명키인 검증 수행객체의 개인키를 수신하여 서명문을 생성하는 단계와, 검증 수행객체가 상기 대칭키와 검증키인 서명 수행객체의 일회용공개키를 수신하여 서명 수행객체를 통해 생성된 서명문을 검증하고 상기 검증 결과에 따라 원문메시지를 수락하거나 거절하는 단계를 포함하는 암호문 서명 및 검증 방법을 개시한다.
본 발명의 일 실시예에 따르면, 상기 식별인자는 사용자의 개인정보를 포함하는 사용자 식별인자, 사용자 단말 정보를 포함하는 단말장치 식별인자 및 비밀함수 생성인자 중 적어도 하나를 포함한다.
본 발명의 일 실시예에 따르면, 상기 서명문(M S)은 서명 함수(S)에 서명키(K S)를 대입하여 순열연산(M ×K →S)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
S(M, K S) = Q -1HQ(M) = M s
여기서 Q -1HQ는 순열함수 H, Q의 순열연산(left multiplication)이고, 메시지 M = (m 1
Figure PCTKR2019015346-appb-img-000021
m n), 키 K = (k 1
Figure PCTKR2019015346-appb-img-000022
k n), 서명문 M s = (s 1
Figure PCTKR2019015346-appb-img-000023
s n) 는 각각 메시지집합 M={m 1
Figure PCTKR2019015346-appb-img-000024
m n} 상에서의 순열그룹 G의 원소인 것(M,K,S ∈ G)을 특징으로 한다.
본 발명의 일 실시예에 따르면, 상기 서명문의 검증은 검증 함수(V)에 검증키(K V)를 대입하여 순열연산(S ×K → S)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
V(S, K v) = GQQ(M s) = M
여기서 GQQ는 순열함수 G, Q의 순열연산(left multiplication)이고, 메시지 M = (m 1
Figure PCTKR2019015346-appb-img-000025
m n), 키 K = (k 1
Figure PCTKR2019015346-appb-img-000026
k n), 서명문 M s = (s 1
Figure PCTKR2019015346-appb-img-000027
s n) 는 각각 메시지집합 M={m 1
Figure PCTKR2019015346-appb-img-000028
m n} 상에서의 순열그룹 G의 원소인 것(M,K,S ∈ G)을 특징으로 한다.
본 발명에서 제시한 방법은 양자 컴퓨팅 환경하에서 안전하지 않은 문제로 더이상 사용하지 못하는 수학적 기반의 공개키 암호 시스템을 대체 가능하게 하여 도래하는 양자컴퓨팅 시대에 데이타 보안 문제로 야기되는 혼란을 예방할 수 있도록 한다.
본 발명에 따르면, 수신자의 개인키와 대칭키는 송수신 접속이 있을 경우에 한 번만 생성하는 일회용 키이므로 허가받지 않은 참여자가 관련정보를 탈취한다 하더라도 같은 키를 생성할 수가 없으므로 탈취한 암호문에 대해 복화화가 불가능하고, 중간자 공격 등 해킹공격에도 안전하다.
또한, 본 발명에 따른 서명 알고리즘을 통해, 생성된 암호문을 악의적인 공격자가 탈취하여 조작하였는지 여부를 판단할 수 있고 또한 자신이 보낸 메시지를 부인하지 못하게 하는 부인방지(non-repudiation) 기능을 제공한다.
한편, 현재 컴퓨팅 환경하에서도 복잡한 수학처리 과정을 거치지 않고, 수학적인 암호화 시스템 대비 충분히 안전하고 큰 암호화 키공간의 확보가 가능한 치환방식(S-box) 방식의 대칭키 장점을 승계하면서도, 기존의 치환기반(S-box) 대칭키 암호화 시스템이 가지던 키교환 문제점과 암호문 유출로 인한 보안의 문제점 들을 상기에서 제시한 발명의 효과들을 통해 해결함으로서, 기존 시스템은 물론 저용량/저속/저렴한 운영이라는 요건들을 충족해야 하는 사물인터넷 기기(IoT Devices)나 Cloud와 같은 새로운 컴퓨팅환경하에서 효율적이고 안전한 암호화 시스템 및 암호 통신 시스템의 구축할 수 있다.
도 1은 RSA 암호시스템의 cipher(K, E, C) space 예시를 보여주는 개념도.
도 2는 순열연산(group action) 예시를 보여주는 개념도.
도 3은 발명시스템의 cipher(K, E, C) space 예시를 보여주는 개념도.
도 4는 암호 통신시스템의 개념도.
도 5는 암호/복호를 위한 시스템의 구조도.
도 6은 암호화기의 구조도.
도 7은 복호화기의 구조도.
도 8은 암호키 생성기의 개념도.
도 9는 암호 연산 예시를 보여주는 개념도.
도 10은 암호/복호화 절차 흐름도.
도 11은 암호/복호화 단계 1 설정 예시를 보여주는 개념도.
도 12는 암호화/복호화 단계 2 키 생성 예시를 보여주는 개념도.
도 13은 암호화 단계 3 암호문 생성을 보여주는 개념도.
도 14는 복호화 단계 3 메시지 생성을 보여주는 개념도.
도 15는 서명/검증을 위한 시스템의 구조도.
도 16은 서명기의 구조도.
도 17은 검증기의 구조도.
도 18는 서명/검증 절차 흐름도.
도 19은 서명/검증 단계 1 설정 예시를 보여주는 개념도.
도 20은 서명/검증 단계 2 키생성을 보여주는 개념도.
도 21는 서명 단계 4 서명(signature) 생성을 보여주는 개념도.
도 22은 검증 단계 4 검증 메시지 수락/거절을 보여주는 개념도.
도 23는 서명된 메시지의 암호화기시스템의 구조도.
도 24는 서명된 메시지의 복호화기시스템의 구조도.
도 25은 서명된 메시지의 암호화를 보여주는 개념도.
도 26은 서명된 메시지의 암복호화 및 검증 절차 흐름도.
도 27은 서명된 암호문의 복호화를 보여주는 개념도.
이하, 첨부된 도면을 참조하여 본 명세서에 개시된 실시 예를 상세히 설명하되, 도면 부호에 관계없이 동일하거나 유사한 구성요소는 동일한 참조 번호를 부여하고 이에 대한 중복되는 설명은 생략하기로 한다.
이하의 설명에서 사용되는 구성 요소에 대한 접미사 "모듈" 및 "부"는 명세서 작성의 용이함만이 고려되어 부여되거나 혼용되는 것으로서, 그 자체로 서로 구별되는 의미 또는 역할을 갖는 것은 아니다.
또한, 본 명세서에 개시된 실시 예를 설명함에 있어서 관련된 공지 기술에 대한 구체적인 설명이 본 명세서에 개시된 실시 예의 요지를 흐릴 수 있다고 판단되는 경우 그 상세한 설명을 생략한다.
또한, 첨부된 도면은 본 명세서에 개시된 실시 예를 쉽게 이해할 수 있도록 하기 위한 것일 뿐, 첨부된 도면에 의해 본 명세서에 개시된 기술적 사상이 제한되지 않으며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.
제1, 제2 등과 같이 서수를 포함하는 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되지는 않는다.
상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다.
어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다.
단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다.
본 명세서에서, "포함한다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.
본 명세서에서 설명하는 수행 객체들(암호화 수행객체, 복호화 수행객체, 서명 수행객체, 검증 수행객체 등)과 수행객체를 구성하는 구성요소들(암호화기, 복호화기, 서명기, 검증기, 암호키생성기 등)은 각각 물리적으로 구분되는 구조를 가질 수도 있고 기능적으로만 구분되어 있을 수 있다.
기능적으로만 구분되는 경우, 이러한 수행 객체들과 구성요소들은 하나의 제어부에 포함될 수 있다.
상기 제어부는 단일 시스템이나 클라우드 서비스와 같은 분산 응용 프로그램 환경 내 특정 기능을 수행하는 API, 특정 기능을 수행하는 모듈, 컴포넌트(component), 칩, 단말 등의 하드웨어 또는 어플리케이션, 프로그램 등의 소프트웨어를 포함할 수 있다.
I. 용어의 정의
a) 정보의 표현 및 처리 방법
컴퓨터 또는 통신시스템을 통해 보내고자 하는 정보는 숫자, 문자, 그림, 동영상, 소프트웨어 등 다양한 형태를 띄고 있으나 시스템 내에서는 binary, 즉 bit로 구성된 byte단위로 다루어진다. 이것은 ASCII, UNICODE 등 코드 형태로 변환되어 시스템 내의 응용프로그램이 인식하게 되고 이를 통해 사람들은 다시 숫자, 문자, 그림 등 정보의 형태로 전달 받는다.
통상적으로 메시지라 함은 사람들이 컴퓨터 또는 통신시스템을 통해 상대방에게 전달하고자 하는 정보를 말하며, 이는 시스템에서는 앞서 언급한 바와 같이 byte 등 시스템 내 메시지단위(message unit)로 다루어지고, 시스템 내에서 모든 정보는 처리 가능한 하나의 시스템 내 메시지단위(message unit)의 열로 변환된다.
즉, 전달하고자 하는 메시지는 메시지단위(message unit)에 의해 표현할 수 있고 메시지 단위에 의해 표현 가능한 경우를 나열한 것을 메시지 집합 M이라 한다.
예를 들어, 메시지 단위가 bit인 경우 M = {0,1}이 되고 메시지는 00110101와 같이 메시지단위의 열로 표현될 수 있고, 메시지 단위가 byte인 경우 M = {0,1, … 255} 이고(십진수 표현으로 나타내면) 메시지는 64 68 72 82와 같이 나타낼 수 있다.
이 때 이를 수학적으로 표현하면, 메시지 집합 M은 M = {m 1,…, m i,…, m n} 과 같이 나타내며, M의 원소는 m i이고, 1≤i ≤n이며, 집합 M의 원소의 갯수는 |M|= n과 같이 나타낼 수 있다.
메시지 집합 M의 각 원소를 순서대로 나열하고 그 순서에 따라 나열된 원소의 인덱스를 집합으로 나타내면 I M = { 1, …, i, …, n } 이 되고 이를 메시지 집합 M에 대한 인덱스 집합이라 말하며, 인덱스 집합의 i번째 원소는 I M(i) = m i 과 같다.
이 때 메시지의 인덱스 집합은 I M : I → M 과 같이 표현하고 인덱스 집합 I에서 메시지 집합 M으로 가는 사상(morphism)이 존재한다고 말한다.
순열(permutation) P = (p 1, …, p i, …, p n) 는 n개의 자연수(Z)로 이루어진 집합 S = {1, 2, …, n}의 permutation(순열)이라 하며, 1≤p i≤n 이다.
예를 들면, 순열
Figure PCTKR2019015346-appb-img-000029
와 같이 표현할 수 있고, 이는 집합 S= {1, 2, 3, 4, 5}의 permutation으로 σ : S → S 과 같이 전단사 함수(bijection)에 의해 표현되며, 즉 함수이다.
다시 말하면, σ(1)=3,σ(2)=4,…, σ(5)=1 과 같으며, 일반적으로 집합 S = {x 1,x 2,…,x n} 의 permutation은
Figure PCTKR2019015346-appb-img-000030
와 같이 표현된다.
순열은 함수적으로 표현하면, 도메인 X에서 코도메인 Y로 가는 전단사 함수 F : X → Y 에서 X와 Y의 대응관계를 나타내며, 집합의 의미로 표현하면, 임의의 집합의 원소에 대한 배열순서를 나타낸다.
n개의 원소로 이루어진 임의의 집합의 순열(permutation)은 n개의 숫자 또는 문자의 순열(permutation)이라고도 말할 수 있으며 앞서 언급한 메시지 집합 M에 대해서도 마찬가지로 적용된다.
따라서 모든 메시지는 메시지 집합 M의 순열에 의해 표현가능하다.
순열(permutation)은 임의의 집합의 각 원소들의 배열에 따라 다른 순열(permutaion)이 되고, 이 모든 경우의 순열들이 모여 순열그룹(Group)을 형성한다. 즉 순열그룹(Permutaion Group)은 임의의 집합의 모든 경우의 순열(premutation)을 원소로 이루어진 집합이다.
순열그룹(permutation group ) G = {σ|σ: S → S , σ는 S = {x 1,x 2,…,x n}의 permutation }이며, 집합 M = {1,2,…n}의 모든 순열들의 순열그룹(permutation group)은 symmetric group Sym(M)이 된다.(모든 전단사 함수는 symmetric group임)
즉, M = {1,2, …,n} 이면, n개의 문자에 대한 Sym(M)은 S n 으로 나타낸다.
순열 σ,π∈ G(순열그룹) 일 때, 그룹연산(composition of permutation)의 결과 또한 순열이 되고 결과의 순열 역시 G의 원소가 된다. 즉, 순열그룹 G는 그룹연산에 대하여 닫혀 있다.
G를 구성하는 순열(permutation)의 수는 |G| = n! 개 이다.
순열연산(Group Action)은 순열그룹(permutation group) G의 각 원소(P: permutation)들이 집합(S)의 원소들을 배열하는 방법을 말하며, 일종의 함수와 같이 작용한다. 다시 말하면, 집합 S의 원소에 순열 P의 순열연산(Group Action)를 적용하면 집합 S의 원소가 순열 P에 의해 재배열되는 것을 의미한다. 즉, 집합 S의 원소 배열 순서를 바꾸는 연산을 순열연산(group action)이라고 한다.
(즉, 집합 S에 대해 순열 P의 방법에 의해 S의 원소를 재배열한다는 것이고 즉 S의 인덱스 집합 I S이 바뀐다)
G : Permutation Group, M : non-empty set 일 때, 집합 M에 대한 순열그룹 G의 순열연산(group action)은 아래의 3가지 성질을 만족하는 함수 f : G × M → M 이다.
＊ 집합 M에 속하는 모든 원소 x에 대하여 f(1, x) = x (group G의 항등원은 1)
＊ f(x, y) = 1을 만족하는 y = x -1, x, y ∈ G인 x의 역원이 존재
＊ G에 속하는 모든 permutation g, h와 M에 있는 모든 원소 x에 대하여f(g, f(h, x)) = f(gh, x) (결합법칙 성립, left multiplication)
도 2에서 순열 연산의 예시를 보여준다.
G의 degree 는 G를 구성하는 집합 M의 원소의 갯수 |M|이고, G의 order는 G의 원소의 갯수(cardinality)는 |G| 이다. 즉, n개의 원소로 된 집합 M에 대한 degree of group G 는 n 이고, order of group G 는 n! 이다.
b) 암호학 및 발명시스템
PRNG(Pseudo Random Number Generator) : 난수를 흉내내기 위해　알고리즘을 통해 생성하는 난수 값을 유사난수라 하고, 이때 유사난수를 생성하는 알고리즘을　유사난수 생성기(pseudorandom number generator,　PRNG)라고 한다. 이는 다음과 같은 함수 F : X → Y over (X,Y)와 같이 표현할 수 있다. 임의의 입력 값 X에 대해서 임의의 유사난수값 Y가 발생한다.
PRF(Pseudo Random Function) : PRNG를 기반으로 유도된 함수로 임의의 입력값을 받아 항상 유사난수 수열을 발생한다.(유사난수 함수) 이는 다음과 같은 함수 F : K × X → Y over (k,X,Y)와 같이 표현한다.
PRP(Pseudo Random Permutaion) : PRF와 유사한 방식으로 유사난수 수열을 생성하나 항상 같은 도메인으로 작용하는 일대일 사상이 존재하고 효율적인 역함수 D(k,X)가 존재한다. PRNG로부터 생성된 난수로부터 PRP로 부터 생성된 수열을 구별할 수 없으면 secure PRP라고 한다. 또한, 충분히 큰 X에서 정의된 secure PRP는 secure PRF이다. (유사난수 순열)
이는 다음과 같은 함수 E : K × X → X over (k,X) 와 같이 표현한다.
TDF(Trapdoor Function) : 트랩도어 함수(trapdoor function, 비밀통로 일방향함수)는　일방향함수의 한 종류이다. 보통 일방향함수처럼 함수의 역을 구하는 것은 어렵지만,　트랩도어라고 부르는 특수한 정보가 있으면 쉽게 역을 구할 수 있는 함수이다. 트랩도어 함수를 수학적으로 정의하면 다음과 같다. 어떤 비밀값　y가 있어서, 어떤　x에 대해서　y가 없을 때는　f(x)를 구하기 어렵지만　y가 주어진다면　f(x)에서　x　값을 쉽게 찾을 수 있다면 함수　f는 트랩도어 함수이다.
암호(Cipher) = (G, E, D), 암호공간(cipher space)= (k, M, C) : 암호(cipher)는 암호화 및 복호화를 수행하는 알고리즘이며 암호공간(K, M, C)상에서 작용하는 일종의 함수와 같다. 암호(cipher)는 G, E, D 등 세개의 알고리즘(함수)으로 구성되어 있다. 각각은 다음과 같은 약어를 나타낸다.
G : 키생성 함수
E : 암호화(Encryption) 함수
D : 복호화(Decryption) 함수
K : 키공간(Key Space)
M : 메시지공간(Message Space)
C : 암호문공간(Ciphertext Space)
MKG(Magic Key Generator)는 암호키생성기로 사용자가 암호화/복호화를 위해 필요한 사용자 식별 및 등록, 키생성, 배포 등을 처리하기 위한 키관리 장치를 말한다. 암호화기나 복호화기와 같은 시스템 내에 설치할 수도 있고 다른 제 3의 시스템에 설치하여 연동할 수도 있다. MKG에 대한 접속은 허용된 참여자만이 할 수 있도록 사용자 인증을 통해 안전한 정보채널을 보장한다.
비밀함수그룹 SPG(Secret Permutation Group)는 메시지 집합 M상의 모든 순열그룹(permutation group) G의 subset을 말하며, 이 subset을 형성하는 각 순열(permutation)들을 비밀함수후보 SPC(Secret Permutation Candidates)라 부르며, 이 때 비밀함수후보중에서 특별히 지정된 한 개의 후보를 비밀함수 SP(Secret Permutation)라 한다. 도 3에서 SPG, SP에 대한 예시를 보여준다.
II. 시스템 구조
도 4는 발명시스템의 일 실시예를 보여주는 개념도이다. 이 시스템은 암호문을 전송하는 통신채널과 이에 연결된 두개의 단말을 포함하고 각 단말은 암복호화에 관련된 암호화키 K e, 복호화키 K d를 갖고 있다. 통신채널은 통상적인 전송케이블과 전송장치를 포함하고 도 4에서는 일방향 통신의 예를 보여주나 같은 방법으로 반대방향으로도 작동 가능하여 양방향통신이 가능하다.
1. 암호/복호 시스템
도 4의 송신 및 수신의 각 단말은 도 5와 같이 암호화기(ENC), 복호화기(DEC) 그리고 암호키생성기(MKG)로 구성되어 있다.
암호화기(ENC)는 도 6과 같이 메시지 입력을 처리하는 입력큐와 본 발명의 일 실시예에 따른 알고리즘을 통해 일회용 공개키를 이용하여 순열연산(Group Action)을 통해 암호문을 생성하는 GA 연산기, 그리고 생성된 암호문의 출력을 처리하는 출력큐가 있다.
GA 연산기는 메시지를 입력으로 암호키생성기(MKG)로 부터 송수신 단말의 대칭키(Q AB)와 수신 단말의 공개키(G B)를 제공받아 순열연산(GA 연산)을 통해 암호문을 생성한다. GA 연산기에서 처리하는 순열연산은 Q AB -1G BQ AB(M) = C 이다.
한편, 다른 일 실시예에서 암호복잡도에는 큰 영향은 없으나 송신단말에 입력된 메시지가 중복된 문자열을 포함하는 경우를 제거하기 위해 확산함수(diffusion function) F(x)를 XOR 연산기를 통해 전처리하고 암호화기의 메시지큐는 전처리된 메시지를 입력받아 암호문을 생성할 수 있다.
복호화기(DEC)는 도 7과 같이 암호문 입력을 처리하는 입력큐와 본 발명의 일 실시예에 따른 알고리즘을 통해 일회용개인키를 이용하여 순열연산(Group Action)을 통해 원문메시지를 복원하는 GA 연산기, 그리고 복원된 원문메시지의 출력을 처리하는 출력큐가 있다.
GA 연산기는 암호문을 입력으로 암호키생성기(MKG)로 부터 송수신 단말의 대칭키(Q AB)와 수신단말의 개인키(H B)를 제공받아 순열연산(GA 연산)을 통해 원문메시지을 복원한다.
GA 연산기에서 처리하는 순열연산은 H BQ ABQ AB (C) = M 이다.
한편, 다른 일 실시예에서는 송신단말에 확산함수(diffusion function)을 적용한 경우 복호화기에서 복원된 메시지를 송신단말에 적용된 동일한 확산함수(diffusion function) F(x)를 XOR 연산기를 통해 후처리하여 원문메시지를 복원할 수 있다.
암호키생성기(MKG)는 도 8에서 보는 바와 같이 난수생성기(PRNG), 순열생성기(permutation generator), 복수의 키생성모듈들(MSK_
Figure PCTKR2019015346-appb-img-000031
, MSK_
Figure PCTKR2019015346-appb-img-000032
, MPK, SK, PK) 그리고 순열연산기(GA Operator) 등으로 구성된다.
난수생성기(PRNG)는 사전에 등록된 송수신 참여자만이 알 수 있는 참여자 고유의 개인식별자(ID), device ID, 이벤트, 시간 등 복수의 매개변수(parameter)를 사용한 키유도함수 KDF(key driven function)를 통해 일회용 유사난수를 생성한다. 생성한 난수는 각각 순열생성기와 키생성모듈로 제공된다.
순열생성기(permutation generator)는 난수생성기와 고유의 키유도함수(KDF)를 통해 일회용 유사난수순열(PRP)를 생성한다. 생성한 난수수열은 각 키생성모듈로 제공된다.
키생성모듈들은 수신자의 비밀함수그룹(Secret Permutation Group)을 나타내는 벡터함수인 마스터키벡터(MSK_
Figure PCTKR2019015346-appb-img-000033
)모듈, 수신할 비밀함수(Secret Permutation)를 결정하는 마스터키스칼라모듈(MSK_
Figure PCTKR2019015346-appb-img-000034
), 송신자 및 수신자만이 공유하는 대칭키를 생성하는 대칭키모듈(MPK), 송수신 이벤트마다 쌍으로 생성하는 공개키모듈(PK) 및 개인키모듈(SK) 등이 있다. 또한, 키생성모듈중 마스터 키모듈과 대칭키모듈들은 복수(multiple)의 고유 개인식별 정보를 매개변수로 키유도함수(KDF)를 통해 난수발생기 또는 순열생성기를 통해 매번 다른 키 값들을 생성하고 내부의 키보관소에 키를 보관하고 개인키 및 공개키 생성을 위해 개인키모듈과 공개키모듈로 생성된 키값을 배포한다. 또한 키를 요청하는 해당 단말의 암호화기와 복호화기에 배포한다.
개인키모듈은 개인키를 생성한다. 개인키는 마스터키 스칼라모듈로 부터 생성된 난수값들을 마스터키벡터모듈이 지정한 위치에 먼저 배열하고 순열생성기에서 제공된 난수수열 들을 나머지 위치에 배열하여 생성한다.
암호키생성기내의 순열연산기(GA Operator)는 암호화기 또는 복호화기의 순열연산기가 각각 암호문과 원문메시지 생성에 필요한 연산을 수행하는 것과 달리 대칭키와 개인키를 통해 공개키를 생성하는 역할을 한다. 개인키모듈 SK로 부터 생성되는 키를 H라 하고, 대칭키모듈 MPK로 부터 생성되는 키를 Q라 하고 순열연산기에서 연산되어 생성되는 공개키를 G라 하면, 순열연산기에서 연산되는 순열연산은 G = Q -1H -1Q -1 이 되고, 연산결과 산출되는 공개키 G는 공개키모듈 PK로 출력되어 보관되고 해당 암호화기 또는 복호화기로 배포된다.
이제 도 9를 통해 암호화기의 작동에 대한 일 실시예를 살펴보고자 한다.
메시지 집합 M이 0~9의 숫자로 구성된 경우, 즉 |M| = 10일 때, 사용자 A에서 사용자 B로 4581290367의 10개의 숫자메시지를 전송하고자 한다. 도 9는 사용자 A 단말의 암호화기를 통해 암호문 5301689742가 생성되는 것을 보여준다.
2. 암호화/복호화 방법 및 절차
본 발명의 상기 실시예에 따라 도 10에서 보여주는 방법 및 절차에 따라 순열그룹 기반의 메시지 암호화 전송방법을 구현할 수 있다.
실시예에 따른 시스템을 이용하여 메시지 전송을 하기 위해서는 송수신 참여자는 사전에 시스템에 개인식별 정보 등을 등록하여 허용된 참여자로 승인받아야 한다.
따라서 실시예에 따른 전송방법의 제 1단계는 설정(setup)단계로서 암호키생성기(MKG)에 참여객체를 식별할 수 있도록 사용자 식별인자(phone number, user id, email address etc.), 단말장치 식별인자(device id, MAC address, ip address, faceid, fingerprint etc.), 비밀함수(Secret Permutation) 생성인자 등과 같은 개인식별 정보를 등록하고 암호키생성기(MKG)는 이 정보에 따라 등록하는 객체의 식별번호, 마스터키 등을 생성한다.
마스터키는 메시지 전체 순열그룹중에서 비밀함수후보(SPC)들을 특정할 수 있는 벡터함수이며 이러한 키벡터함수 T는 (tp,tv) 벡터쌍을 이루며 T ⊂ I M × M 이다. 마스터키 T의 tp는 설정시에 생성 또는 등록되고, 마스터키 T의 함수값 tv는 암호화 실행시에 결정되어 비밀함수후보(SPC)중에서 특정 비밀함수(SP)를 지정하고 이와 관련하여 해당 참여객체의 개인키를 생성하게 한다.
제 2단계는 암호키생성기에서 암호화를 위한 키생성단계로 암호화와 복호화에 필요한 대칭키와 개인키 및 공개키 쌍을 생성한다. 송수신 참여객체만의 사전등록 정보를 통해 송수신 양자만이 알 수 있는 대칭키를 생성한다. 또한 설정단계에서 생성한 마스터키(함수)에 일회용 함수값을 할당하여 비밀함수(SP)를 지정하고 이와 함께 설정단계에서 사전에 등록된 개인식별 정보를 바탕으로 개인키를 생성한다. 공개키는 생성된 대칭키와 개인키의 순열연산(GA)에 의해 생성된다.
제 3단계에서는 암호문 생성을 위해 송신자가 암호키생성기를 통해 암호화 키인 수신자의 공개키를 요청하여 얻는다. 대칭키는 각 송수신 단말은 2단계를 통해 이미 보유하고 있다. 이 때 해당 참여객체들의 키들은 제 2단계인 키생성단계에서 이미 생성되어 있으므로 쉽게 획득가능하다. 수신자의 공개키와 이미 갖고 있는 대칭키를 순열연산기를 통해 연산하여 암호문을 생성한다. 이 과정을 수학적으로 표현하면 다음과 같다.
메시지 M = (m 1 … m n), 키 K = (k 1 … k n), 암호문(ciphertext) C = (c 1 … c n)는 각각 메시지집합 M={m 1 … m n} 상에서의 순열로 순열그룹 G의 원소이며, E : M ×K → C, M, K, C ∈ G 와 같으며, 암호화키 K e는 (MPK, PK) 쌍이고 순열함수쌍 (Q, G)로 나타낸다. 즉 K e=(Q, G) 이다. 암호화 함수 E는 K e를 구성하는 순열함수 Q, G의 순열연산(Group Action)인 left multiplication에 의해 E=Q -1GQ 와 같이 나타낼 수 있다. 따라서 E(M, K e) = Q -1GQ(M) = C 와 같다.
D = d 1d 2 …d k: 메시지 시퀀스 D는 d i가 메시지 집합 M의 원소로 구성된 연속된 메시지 문자열이라 할 때, 결과 암호문열이 x = x 1x 2 … x k 라고 하면,
이 때 E(d i, K e) = Q -1GQM((d i)) = x i이다. R = Q -1라 하면,
Figure PCTKR2019015346-appb-img-000035
,
Figure PCTKR2019015346-appb-img-000036
,
Figure PCTKR2019015346-appb-img-000037
,
Figure PCTKR2019015346-appb-img-000038
일 때,
Figure PCTKR2019015346-appb-img-000039
와 같으며 E는 left multiplication에 의해 계산된다.
제 4단계에는 수신된 암호문을 복원하기 위해 수신자가 암호키생성기를 통해 암호화키인 수신자의 개인키를 얻는다. 대칭키는 각 송수신 단말은 2단계를 통해 이미 보유하고 있다. 이 때 해당 참여객체들의 키들은 제 2단계인 키생성단계에서 이미 생성되어 있으므로 쉽게 획득가능하다. 수신자의 개인키와 이미 갖고 있는 대칭키를 순열연산기를 통해 연산하여 원문메시지를 복원한다. 이 과정을 수학적으로 표현하면 다음과 같다.
메시지 M = (m 1 … m n), 키 K = (k 1 … k n), 암호문(ciphertext) C = (c 1 …c n)는 각각 메시지집합 M={m 1 … m n} 상에서의 순열로 순열그룹 G의 원소이며, D : C ×K → M, M, K, C ∈ G 와 같으며, 복호화키 K d는 (MPK, SK) 쌍이고 순열함수쌍 (Q, H)로 나타낸다. 즉 K d=(Q, H) 이다.
복호화 함수 D는 K d를 구성하는 순열 Q, H의 순열연산(Group Action)인 left multiplication에 의해 D=HQQ 와 같이 나타낼 수 있다. 따라서 D(C, K d) = HQQ(C) = M 가 된다.
X = x 1x 2 …x k 암호문 시퀀스 X는 x i가 암호문 집합 C의 원소로 구성된 연속된 암호문 문자열이라 하고, D=d 1d 2…d k : 메시지 시퀀스 D는 d i가 메시지 집합 M의 원소로 구성된 연속된 메시지 문자열이라 할 때 D(x i, K d) = HQQ(C(x i)) = d i 이다.
Figure PCTKR2019015346-appb-img-000040
,
Figure PCTKR2019015346-appb-img-000041
,
Figure PCTKR2019015346-appb-img-000042
일 때,
Figure PCTKR2019015346-appb-img-000043
와 같으며 D는 left multiplication에 의해 계산된다.
3. 메시지 암호화/복호화 전송방법 실시예
도 11내지 도 14에서는 본 발명의 일 실시예로 메시지 암호화 전송방법의 단계별 구현에 대한 구체적인 예시를 보여준다.
예시는 단말 A에서 단말 B로 0~9의 숫자를 원소로 하는 메시지 집합에서 숫자 10개로 구성된 숫자열 “4581290367”을 메시지로 입력받아 암호문 생성하여 전송하고 이를 수신하여 원문 메시지를 복원하는 과정을 수행 단계별로 구체적으로 도 11에서 도 14를 통해 보여준다.
도 11에서는 1단계 설정단계에서 송수신을 위해 암호키생성기에 송신단말 A와 수신단말 B의 ID 등록과 이를 통해 마스터개인키 벡터함수 {(2, v 1), (4, v 2), (6, v 3), (8, v 4)}가 생성되고, 마스터공개키 생성함수가 설정되는 것을 보여준다.
도 12에서는 2단계 키생성단계로 마스터키 벡터함수의 벡터값 할당과 이를 통해 어떻게 개인키가 생성되는지 보여준다. 또한 순열생성기를 통해 대칭키 생성함수에 함수값이 어떻게 할당되는 지와 이와 함께 개인키와 순열연산기를 통해 공개키가 생성되는 것을 보여준다.
도 13에서는 3단계 암호문 생성단계로 1, 2단계를 통해 생성된 암호화키 MPK, SK, PK를 통해 순열연산기(GA Operator)에서 순열연산을 통해 어떻게 연산이 이루어지고 암호문이 어떻게 생성되는 지 구체적인 예시를 통해 보여준다.
도 14에서는 4단계 암호문 복호화 단계로 1, 2단계를 통해 생성된 암호화키 MPK, SK, PK를 통해 순열연산기(GA Operator)에서 순열연산을 통해 어떻게 연산이 이루어지고 수신된 암호문이 어떻게 원문메시지로 복호화되어 복원되는 지 구체적인 예시를 통해 보여준다.
4. 서명/검증 시스템
전자서명 시스템의 각 송수신 단말은 기능적으로는 앞서 일 실시예에서 설명한 암호화기나 복호화기와 동일한 구조로 동일하게 작동하지만 다른 키와 다른 입력을 사용하여 작동하는 점이 다르다. 서명/검증 시스템의 송신 및 수신의 각 단말은 도 15와 같이 서명기(SIGN), 검증기(VERIFY) 그리고 암호키생성기(MKG)로 구성되어 있다.
서명기(SIGN)는 도 16과 같이 메시지 입력을 처리하는 입력큐와 본 발명의 일 실시예에 따른 알고리즘을 통해 일회용개인키를 이용하여 순열연산(Group Action)을 통해 서명문(signature)을 생성하는 GA 연산기, 그리고 생성된 서명문(signature)의 출력을 처리하는 출력큐가 있다.
GA 연산기는 메시지를 입력으로 암호키생성기(MKG)로 부터 송수신 단말의 대칭키(Q AB)와 송신단말의 개인키(H A)를 제공받아 순열연산(GA 연산)을 통해 서명문(signature)을 생성한다. GA 연산기에서 처리하는 순열연산은 Q AB -1H AQ AB(M) = M s 이다.
한편, 다른 일 실시예에서 암호복잡도에는 큰 영향은 없으나 송신단말에 입력된 메시지가 중복된 문자열을 포함하는 경우를 제거하기 위해 확산함수(diffusion function) F(x)를 XOR 연산기를 통해 전처리하고 서명기의 메시지큐는 전처리된 메시지를 입력받아 서명문을 생성할 수 있다.
검증기(VERIFY)는 도 17과 같이 서명문(signature)을 입력받아 처리하는 입력큐와 본 발명의 일 실시예에 따른 알고리즘을 통해 일회용공개키를 이용하여 순열연산(Group Action)을 통해 서명문을 검증하여 수락된 원문메시지를 생성하는 GA 연산기, 그리고 검증/수락된 원문메시지의 출력을 처리하는 출력큐가 있다.
GA 연산기는 서명문를 입력으로 암호키생성기(MKG)로 부터 송수신 단말의 대칭키(Q AB)와 송신단말의 공개키(G A)를 제공받아 순열연산(GA 연산)을 통해 서명문을 검증하고 수락/거절여부를 확인하여 원문메시지를 검증한다.
GA 연산기에서 처리하는 순열연산은 G AQ ABQ AB(M s) = M 이다.
한편, 다른 일 실시예에서는 송신단말에 확산함수(diffusion function)을 적용한 경우 검증기에서 검증된 메시지를 송신단말에 적용된 동일한 확산함수(diffusion function) F(x)를 XOR 연산기를 통해 후처리하여 원문메시지를 복원할 수 있다.
도 15의 서명/검증시스템에 나타나는 암호키생성기(MKG)는 도 8에서 보는 바와 같이 난수생성기(PRNG), 순열생성기(permutation generator), 복수의 키생성모듈들(MSK_
Figure PCTKR2019015346-appb-img-000044
, MSK_
Figure PCTKR2019015346-appb-img-000045
, MPK, SK, PK) 그리고 순열연산기(GA Operator) 등으로 암호화기나 복호화기에서와 같은 구조와 기능을 제공하고 동일하게 작동한다.
5. 서명/검증 방법 및 절차
본 발명의 상기 실시예에 따라 도 18에서 보여주는 방법 및 절차에 따라 순열그룹 기반의 메시지 암복호화 알고리즘을 이용하여 서명/검증 방법을 수행할 수 있다.
도 18의 일 실시예에 따른 메시지에 대한 서명 및 검증 방법은 4단계의 절차에 의해 수행될 수 있으며, 제 1단계 송수신 참여객체에 대한 등록 및 설정 방법과 제 2단계 키생성 방법 및 절차는 상기 암복호화 방법의 일 실시예에서 설명한 방법과 절차와 동일하게 수행한다.
제 3단계에서는 서명문 생성을 위해 송신자가 암호키생성기를 통해 서명키인 송신자의 개인키를 요청하여 얻는다. 대칭키는 각 송수신 단말은 2단계를 통해 이미 보유하고 있다. 이 때 해당 참여객체들의 키들은 제 2단계인 키생성단계에서 이미 생성되어 있으므로 쉽게 획득가능하다. 송신자의 개인키와 이미 갖고 있는 대칭키를 순열연산기를 통해 연산하여 서명문을 생성한다. 이 과정을 수학적으로 표현하면 다음과 같다.
메시지 M = (m 1 … m n), 키 K = (k 1 … k n), 서명문(signature) M s = (s 1 … s n) 는 각각 메시지집합 M={m 1 … m n} 상에서의 순열로 순열그룹 G의 원소이며, S : M ×K → S, M,K,S ∈ G 와 같으며, 서명키 K s는 (MPK, SK) 쌍이고 순열함수쌍 (Q, H)로 나타낸다. 즉 K s=(Q, H) 이다. 서명 함수 S는 K s를 구성하는 순열함수 Q, H의 순열연산(Group Action)인 left multiplication에 의해 S=Q -1HQ 와 같이 나타낼 수 있다. 따라서 S(M, K S) = Q -1HQ(M) = M s 와 같다.
D = d 1d 2 …d k: 메시지 시퀀스 D는 d i가 메시지 집합 M의 원소로 구성된 연속된 메시지 문자열이라 할 때, 결과 서명문열이 x = x 1x 2 …x k 라고 하면,
이 때 S=(d i, K s) = Q -1HQM((d i)) = x i이다. R=Q -1라 하면,
Figure PCTKR2019015346-appb-img-000046
,
Figure PCTKR2019015346-appb-img-000047
,
Figure PCTKR2019015346-appb-img-000048
,
Figure PCTKR2019015346-appb-img-000049
일 때,
Figure PCTKR2019015346-appb-img-000050
와 같으며 S는 left multiplication에 의해 계산된다.
제 4단계에는 수신된 서명문을 검증하기 위해 수신자가 암호키생성기를 통해 검증키인 송신자의 일회용공개키를 얻는다. 대칭키는 각 송수신 단말은 2단계를 통해 이미 보유하고 있다. 이 때 해당 참여객체들의 키들은 제 2단계인 키생성단계에서 이미 생성되어 있으므로 쉽게 획득가능하다. 송신자의 공개키와 이미 갖고 있는 대칭키를 순열연산기를 통해 연산하여 서명문을 검증하고 검증된 원문메시지를 수락 또는 거절한다. 이 과정을 수학적으로 표현하면 다음과 같다.
메시지 M = (m 1 … m n), 키 K = (k 1 … k n), 서명문(signature) M s = (s1 … s n)는 각각 메시지집합 M={m 1 … m n} 상에서의 순열로 순열그룹 G의 원소이며, V : S ×K → S, M, K, S ∈ G 와 같으며, 검증키 K v는 (MPK, PK) 쌍이고 순열함수쌍 (Q, G)로 나타낸다. 즉 K v=(Q, V) 이다.
검증 함수 V는 K v를 구성하는 순열 Q, G의 순열연산(Group Action)인 left multiplication에 의해 V=GQQ 와 같이 나타낼 수 있다. 따라서 V(S, K v) = GQQ(M s) = M 가 된다.
x = x 1x 2 …x k 서명문 시퀀스 X는 x i가 서명문 집합 M s의 원소로 구성된 연속된 서명문 문자열이라 하고 결과 메시지 문자열이 D=d 1d 2…d k 라 할 때 V(x i, K v) = GQQ(M s(x i)) = d i 이다.
Figure PCTKR2019015346-appb-img-000051
,
Figure PCTKR2019015346-appb-img-000052
,
Figure PCTKR2019015346-appb-img-000053
일 때,
Figure PCTKR2019015346-appb-img-000054
와 같으며 E는 left multiplication에 의해 계산된다.
6. 메시지 서명/검증 전송 방법 예시
도 19 내지 도 22에서는 본 발명의 일 실시예로 메시지 서명문 전송방법의 단계별 구현에 대한 구체적인 예시를 보여준다.
예시는 단말 A에서 단말 B로 0~9의 숫자를 원소로 하는 메시지 집합에서 숫자 10개로 구성된 숫자열 “4581290367”을 메시지로 입력받아 서명문 생성하여 전송하고 이를 수신하여 원문 메시지를 검증하는 과정을 수행 단계별로 구체적으로 도 19에서 도 22을 통해 보여준다.
도 19에서는 1단계 설정단계에서 송수신을 위해 암호키생성기에 송신단말 A와 수신단말 B의 ID 등록과 이를 통해 마스터키 벡터함수 {(1, v 1), (3, v 2), (5, v 3), (7, v 4)}가 생성되고, 대칭키 생성함수가 설정되는 것을 보여준다.
도 20에서는 2단계 키생성단계로 마스터키 벡터함수의 벡터값 할당과 이를 통해 어떻게 일회용개인키가 생성되는지 보여준다. 또한 순열생성기를 통해 대칭키 생성함수에 함수값이 어떻게 할당되는 지와 이와 함께 개인키와 순열연산기를 통해 공개키가 생성되는 것을 보여준다.
도 21에서는 3단계 서명문 생성단계로 1, 2단계를 통해 생성된 암호화키 MPK, SK, PK를 통해 순열연산기(GA Operator)에서 순열연산을 통해 어떻게 연산이 이루어지고 서명문이 어떻게 생성되는 지 구체적인 예시를 통해 보여준다.
도 22에서는 4단계 검증 메시지 수락/거절 단계로 1, 2단계를 통해 생성된 암호화키 MPK, SK, PK를 통해 순열연산기(GA Operator)에서 순열연산을 통해 어떻게 연산이 이루어지고 수신된 서명문이 어떻게 원문메시지로 검증되고 수락/거절되는 지 구체적인 예시를 통해 보여준다.
7. 메시지의 서명/검증을 포함한 암호화/복호화 시스템
전자서명 및 검증을 제공하는 암호시스템에서의 각 송수신 단말은 도 5과 같이 암호화기(ENC), 복호화기(DEC) 그리고 암호키생성기(MKG) 등 동일한 구조를 가지나, 암호화기(ENC)와 복호화기(DEC)는 각각 도 23과 도 24와 같이 서명기와 검증기를 포함하도록 변경될 수 있다.
여기에서 암호화기(ENC)는 도 23에서 보는 바와 같이 도 6의 암호화기에 도 25의 서명기를 결합한 구조로 메시지 입력을 처리하는 입력큐와 암호문 생성용 GA연산기와 서명문 생성용 GA 연산기 등 2개의 다른 GA연산기가 포함되고 암호문 생성용 GA연산기는 입력큐로부터 메시지를 전달받고 서명문 생성용 GA연산기로 부터 서명문을 전달받아 도 25의 예시와 같이 (메시지+서명문) 에 대하여 순열연산을 수행하여 암호문을 생성한다.
한편 복호화기(DEC)는 도 24에서 보는 바와 같이 도 6의 복호화기에 도 27의 검증기를 결합한 구조로 암호문 입력을 처리하는 입력큐와 메시지 복원용 (복호화용) GA연산기와 서명문 검증용 GA 연산기 등 2개의 다른 GA연산기가 포함되고 메시지 복원용(복호화용) GA연산기는 입력큐로부터 암호문을 전달받아 복호화하여 (메시지+서명문)을 복원하고 여기에서 서명문은 검증용 GA연산기로 전달하고 검증용 GA연산기는 도 27의 예시와 같이 검증된 메시지를 생성한다. 각각 다른 두개의 GA연산기로 부터 출력된 메시지는 AND 연산을 통해 메시지 수락 또는 거절 여부를 결정한다.
8. 서명된 메시지의 암호화 전송 및 복호화/검증 방법
본 발명의 일 실시예에 따라 순열그룹 기반의 공개키를 이용하여 서명된 메시지에 대한 암호화 전송방법을 도 26과 같이 구현할 수 있다.
도 26의 일 실시예에 따른 서명된 메시지에 암호화 전송방법은 6단계의 절차에 의해 수행될 수 있으며, 제 1단계 송수신 참여객체에 대한 등록 및 설정 방법과 제 2단계 키생성 방법 및 절차는 상기 도 10의 암복호화 방법의 일 실시예에서 설명한 방법과 절차와 동일하게 수행한다.
제 3단계의 서명문 생성 방법 및 절차는 도 18의 메시지 서명/검증 방법에서와 같다.
제 4단계는 도 25의 예시와 같이 전송하고자 하는 메시지와 제 3단계에서 생성된 서명문을 결합하여 수신자의 공개키로 (메시지+서명문)을 암호화한다.
즉, E(M’, K e) = E((M+M s), K e) = Q AB -1G BQ AB(M+M s) = C’ (K e는 수신자 B의 공개키(G B)) 제 5단계는 수신된 암호문 M'를 도 27의 예시와 같이 복호화하여 M+M s를 복원한다.
즉, D(C’, K d) = H BQ ABQ AB(C') = M’ (K d는 수신자 B의 개인키(H B)), M’=M+M s
제 6단계는 서명문 M s를 V(M s, Kv) = Q AB -1G AQ AB(M s) = M” (K v는 송신자 A의 공개키(G A)) 과 같이 검증하여 검증된 메시지 M”을 얻고 5단계에서 복원한 원문메시지 M과 검증된 메시지 M”이 일치하는 지 여부를 확인하여 메시지를 수락 또는 거절할 지 결정한다. 이 서명된 메시지 전송방법을 통해 메시지의 위조 또는 변조 여부를 판단하고 위변조되지 않은 메시지만 수신하여 무결성을 보장할 수 있다. 또한 서명은 서명한 참여자의 유일하게 한번 생성되는 개인키를 사용하므로 서명한 참여자를 제외한 누구도 생성할 수 없다. 따라서 일 실시예에 따라 서명한 메시지 전송방법을 통해 전송한 메시지에 대하여는 송신자는 메시지 송신을 부인(repudiation)할 수 없다.
9. 기타 구현 및 적용 예시
암호화에 사용하는 암호화 키는 Digit, Character, Images 등 메시지 스페이스를 구성하는 요소를 활용한다. 예를 들어, 문자를 암호화하기 위해서 확장 아스키코드(extended ASCII Code)를 암호화 키 스페이스로 확장해 256 byte 암호화 시스템을 구현하는 것이 가능하다.
본 발명 시스템은 2단 구조(2 tier) 또는 3단 구조(3 tier)로 구현될 수 있다.
2단 구조(2 Tier)에서는 암호화 메시지를 전송하는 전송자(Sender) 와 암호화 메시지를 수신하여 복호화하는 수신자(Receiver) 간에 암호화 통신 중간 매개체를 거치지 않고 통신하는 구조에 적용할 수도 있다.
암호화 메시지를 전송하고 수령하는 전송자(Sender)와 수신자(Receiver) 간의 역할이 일방적이며 고정적이고 변동되지 않을 경우인 단방향(One-way) 통신 방식과 암호화 메시지를 상호 전송/수령하는 경우 양방향(two way) 통신이 모두 구현 가능하며 이경우, 전송자(Sender)와 수신자(Reciever) 모두 암호화 수행객체와 복호화 수행객체 모두가 탑재될 수 있다.
이러한 시스템의 구현 예시는 1대1통신, 또는 피어투피어 통신(Peer to Peer Communication), 일대다수 통신 방식(One to Many Communication) 등에도 적용될 수 있다.
3단 구조(3Tier)에서는 암호화 메시지를 전송하는 전송자(Sender)와 암호화 메시지 메시지 또는 평문을 수신하는 수신자(Reciever) 간에 암/복호화 기능 수행 또는 다른 통신 프로토콜로의 변환 등과 같은 타시스템과의 중계 또는연동 기능을 수행하는 게이트웨이(Gateway) 를 통해 통신하는 구조에 적용할 수도 있다.
이때 게이트웨이(Gateway)는 송신자(Sender) 가 지정한 수신자(Receiver)에게 메시지를 전송할 때 자체 복호화를 실행하여 평문 자체를 전송하거나, 이를 수신자(Receiver) 가 원하는 다른 암호화 방식 또는 다른 통신 프로토콜 형식으로의 변환 작업을 통해 변경된 형식의 메시지를 전송하거나, 송신자(Sender)가 보낸 암호화된 메시지 자체를 수신자(Receiver)에게 전송할 수도 있다.
이러한 시스템은 센서-게이트웨이-서버(Sensor-Gateway-Server), 센서-게이트웨이-센서(Sensor-Gateway-Sensor) 등과 같은 IoT 네트워크 방식이나, 전통적인 3단 구조(3-Tier) 방식이나 N단 구조(N-Tier) 방식이라 칭하는 다중 객체 참여 통신 시스템에 적용될 수 있다.
한편, 본 명세서에서 사용하는 용어 중 송신 단말이나 수신 단말은 적어도 하나의 네트워크를 통해 통신 가능하도록 연결된 단말기를 가리키며, 일 예로, 휴대폰, 스마트 폰(smart phone), 노트북 컴퓨터(laptop computer), 디지털방송용 단말기, PDA(personal digital assistants), PMP(portable multimedia player), 슬레이트 PC(slate PC), 태블릿 PC(tablet PC), 울트라북(ultrabook) 등과 같은 이동 단말기나, 디지털 TV, 데스크탑 컴퓨터 등과 같은 고정 단말기일 수 있으나, 특별히 한정하는 것은 아니다.
본 발명의 일 실시예에 따르면, 안전하고 다양한 환경에 적용 가능한 순열그룹기반 일회용공개키를 이용하는 비대칭방식의 암호통신시스템을 구축할 수 있다.
메시지를 암호화하는 키로서 일회용으로 생성되는 공개순열(Public Permutation)을 이용하는 일회용공개키와 이를 통해 생성된 암호문을 평문으로 복호화하기 위해서는 오직 수신단말이 일회용으로 생성한 개인순열(Private Permutation)을 이용하는 개인키를 통해서만 가능한 비대칭 키를 사용하는 암호 통신 시스템이 구현 가능케 된다.
이 때 일회용공개키와 일회용개인키는 모두 암호문을 복호화할 수 있는 수신 단말의 마스터개인키를 통해서만 생성가능하며, 안전한 방법을 통해 일회용공개키는 송신 단말에게 공유되는 시스템의 구현이 가능하다. 송신 단말이 보유한 일회용공개키 관련정보나 이를 통해 생성된 암호문을 가지고 원문을 복원 또는 추정하기 어려운 암호학의 Trap Door function을 가지고 구현된다.
공개키와 개인키는 보안성 향상 등을 목적으로 매번 랜덤으로 암호화 통신 과정 중 또는 통신 이후에도 자동적 또는 수동적으로 변경 가능하며, 이러한 생성 변경 작업은 오직 복호화 권한을 가진 마스터개인키를 보유한 사용자/시스템/기기에 의해 수행된다. 이러한 기능을 통해 암호 통신 시스템 내 사용된 공개키 및 개인키의 노출 및 암호문의 수집 및 역추적 공학(Reverse Engineering) 등을 통한 추정이 어려운 특성의 구현이 가능하다.
키교환 없는 대칭키 암호통신
또한, 암호화 통신 시스템에 필요한 암호관련 키인 순열키(Permutation Key)를 직접 전송하지 않는 방식으로 구현이 가능하다. 예를 들면 암호화과정과 복호화 과정에서 필요한 공개키/개인키는 수신 단말에 의해 생성된 이후, 생성 및 변경 발생시 해당 생성 조건(시간, 공간 등) 및 변경 조건을 사전 약정한 송신 단말과 수신 단말이 각각 자체 순열연산기를 포함하도록 하고 이를 통해 송신 단말 스스로 동일한 가상의 공개키를 생성할 수 있도록 구현함으로서 암호화 통신과정에서 필수적인 암호화 관련 키 정보를 직접 송/수신하는 단계를 수행하지 않고 마치 키교환 없는 대칭키 암호통신을 하는 것과 같은 시스템을 구축할 수 있다.
암호화에 사용된 공개키를 통해 전송되는 값은 실제 값의 추정이 어려운 수신자만이 가지고 있는 마스터개인키 내 정보 중 일부 정보만을 이용하여 생성하는 개인키를 통해 유도되어지기 때문에 이에 대한 정보를 가지고 평문을 복호화하거나 추정하기는 어려운 암호화 통신 시스템의 구현이 가능하다.
키노출에도 안전유지
공개키와 개인키는 보안 정책 또는 시스템 요건에 따라 매번 랜덤하게 변경되기 때문에 관련 정보가 노출된 이후에도 이전 정보를 소유한 악의적 사용자가 탈취한 이후 생성된 암호문을 임의로 또는 무단으로 복호할 수 없는 시스템의 구현이 가능하다.
상기에서 살펴본 바와 같이 본원발명은 순열기반으로 비대칭 방식을 이용하고 암호화 처리를 byte 단위 또는 원하는 크기의 메시지처리단위로 할 수 있으므로 메시지 유형에 따라 다양한 방식으로 구현이 가능하다.
또한, 본원발명에 따르면 어플리케이션 메시지 처리 단위에서 바로 연산이 이루어져, 메시지를 블록 단위로 암호화 한 후 이를 어플리케이션에서 사용할 수 있는 형태로 재구성하여야 하는 종래 기술에 비해 처리 속도를 비약적으로 빠르게 할 수 있다. 이를 통해 본원발명은 저성능의 CPU 기기에도 구현이 가능해진다.
또한, 본원발명은 단일 암호시스템 내 대칭키/비대칭키 방식 구현이 모두 가능하고, 응용 어플리케이션내 다양한 메시지 형태를 모두 처리 가능하며, 2-Tier 및 3-Teir 통신 구조하에서 유연한 기능 구현이 가능하고, 패스워드/PIN을 기반으로 하는 Human to Machine 방식의 기존 시스템 또는 새로운 Machine to Machine 방식을 채택한 시스템에 모두 적용할 수 있다.
즉, 본원발명의 시스템은 경량화/저용량 기기를 기반으로 다양한 통신 구조하에 동작하는 새로운 iot 환경하에서도 단일 시스템으로 적용하는 것이 가능하고, 또한 기존 암호화 기술 기반 시스템과 연동하는 것이 가능하다.
컴퓨터 판독 가능한 기록매체
이상 설명된 본 발명의 일 실시예에 따른 순열그룹기반 일회용공개키를 이용한 메시지 전송 방법은 다양한 컴퓨터 구성요소를 통하여 수행될 수 있는 프로그램 명령어의 형태로 구현되어 컴퓨터 판독 가능한 기록 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능한 기록 매체는 프로그램 명령어, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 컴퓨터 판독 가능한 기록 매체에 기록되는 프로그램 명령어는 본 발명을 위하여 특별히 설계되고 구성된 것들이나 컴퓨터 소프트웨어 분야의 당 업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능한 기록 매체의 예에는, 하드 디스크, 플로피 디스크, 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광기록 매체, 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 ROM, RAM, 플래시 메모리 등과 같은 프로그램 명령어를 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령어의 예에는, 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드도 포함된다. 상기 하드웨어 장치는 본 발명에 따른 처리를 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
III. 발명의 효과 등
매번 바뀌는 키로 인해 키공간 및 암호공간이 매번 다른 공간을 제공하여 다차원 공간으로 확장되므로 기존 방식이 brute-force 공격에 대해 시도마다 공간확률이 줄어들어 취약한데 반해 본 발명시스템의 공간확률은 항상 동일한 확률을 제공하므로 키를 유도하는 랜덤함수가 even한 확률분포를 제공한다면 brute-force 공격이 확률적으로 어렵다.
또한 복잡한 수학연산을 통해 암호화하지 않으며, 기존 방식과 같이 고정된 함수값을 사용하지 않아 앞서 언급한 바와 같이 순열그룹에 포함된 변동함수를 사용하여 키공간과 암호공간이 다차원 공간으로 확장되므로 암호화 결과에 대하여 양자컴퓨터 등 컴퓨팅 파워가 향상된 컴퓨터를 통해 암호해독을 수행하여도 해독이 어려워 양자저항성(quantum resistant)을 갖는다.
또한 기존의 비대칭키 방식의 경우 중간자공격(Man-in-the-Middle)에 취약하여 이러한 문제를 해결하기 위해 제3의 신뢰기관(Certificate Authority)을 통해 암호통신에 참여하는 모든 참여자에게 신원보증서(Certificate)를 발급하고 이 보증서의 진위여부에 따라 암호통신이 가능하도록 인프라를 구축하는 것이 필요하다. 따라서 중간자공격에 안전한 비대칭키 방식의 암호통신을 위해 막대한 비용의 인프라구축이 필요하고 이러한 인프라로 인해 암호화 수행과정이 복잡하고 처리시간이 오래 걸리는 문제점이 있다. 본 발명의 시스템은 매번 다른 키를 생성하여 암복호화를 수행하므로 중간자공격이 불가능하고 따라서 이러한 문제를 해결하느라 도입된 신뢰기관(CA)이나 신원보증서가 필요없이 안전하게 암호통신하는 것이 가능하다.
이상으로 본 발명의 바람직한 실시예를 도면을 참고하여 상세하게 설명하였다. 본 발명의 설명은 예시를 위한 것이며, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다.
따라서, 본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미, 범위 및 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

Claims (31)

  1. 메시지를 암호화하는 암호화 수행객체; 및
    상기 암호문을 원문 메시지로 복호화 하는 복호화 수행객체를 포함하며,
    상기 암호화 수행객체 및 복호화 수행객체는 순열 그룹에 기반하여 순열 형태인 대칭키와 비대칭키를 동시에 합성하여 메시지를 암복호화하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  2. 제1항에 있어서,
    상기 암호화 수행객체 및 복호화 수행객체는,
    암호화키(K e)를 이용하여 메시지를 암호문으로 암호화 하는 암호화기(ENC)와, 암호화된 암호문을 복호화키(K d)를 이용하여 복호화 하는 복호화기(DEC)와, 암호키생성기(MKG)를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  3. 제2항에 있어서,
    상기 암호화기(ENC)는,
    메시지 입력을 처리하는 입력큐;
    대칭키와 복호화 수행객체의 비대칭키를 이용하여 순열연산을 통해 암호문을 생성하는 GA 연산기; 및
    상기 생성된 암호문의 출력을 처리하는 출력큐를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  4. 제3항에 있어서,
    상기 GA 연산기는,
    상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 복호화 수행객체의 비대칭키 쌍 중 공개키(G B)를 제공받아 순열연산을 통해 암호문을 생성하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  5. 제4항에 있어서,
    상기 순열연산은 Q AB -1G BQ AB(M) = C 수식에 의하여 이루어지며, Q AB는 암호화 수행객체와 복호화 수행객체의 대칭키, G B 는 복호화 수행객체의 공개키, M은 메시지 공간, C는 암호문 공간인 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  6. 제2항에 있어서,
    상기 복호화기(DEC)는,
    암호문 입력을 처리하는 입력큐;
    대칭키와 복호화 수행객체의 비대칭키를 이용하여 순열연산을 통해 원문메시지를 복원하는 GA 연산기; 및
    상기 복원된 원문메시지의 출력을 처리하는 출력큐를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  7. 제6항에 있어서,
    상기 GA 연산기는,
    상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 복호화 수행객체의 비대칭키 쌍 중 개인키(H B)를 제공받아 순열연산을 통해 원문 메시지를 복원하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  8. 제7항에 있어서,
    상기 순열연산은 H BQ ABQ AB(C) = M 수식에 의하여 이루어지며, Q AB는 암호화 수행객체와 복호화 수행객체의 대칭키, H B 는 복호화 수행객체의 비대칭키 쌍 중의 개인키, M은 메시지 공간, C는 암호문 공간인 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  9. 제2항에 있어서,
    상기 암호키생성기는,
    복수의 매개변수를 사용한 키유도함수 KDF(key derivation function)를 통해 일회용 유사난수를 생성하는 난수생성기(PRNG); 및
    상기 키유도함수(KDF)를 통해 일회용 유사난수순열(PRP)를 생성하여 키생성모듈에 제공하는 순열생성기를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  10. 제9항에 있어서,
    상기 키생성모듈은,
    복호화 수행객체의 비밀함수그룹(secret permutation group)을 나타내는 벡터함수인 마스터키벡터(MSK_
    Figure PCTKR2019015346-appb-img-000055
    ) 모듈;
    복호화할 때 사용될 비밀함수(secret permutation)를 결정하는 마스터키스칼라모듈(MSK_
    Figure PCTKR2019015346-appb-img-000056
    );
    암호화 수행객체와 복호화 수행객체 간 공유하는 대칭키를 생성하는 대칭키모듈(MPK); 및
    메시지 암호화와 복호화 시 사용되는 복호화 수행객체의 한 쌍의 비대칭키인 공개키와 개인키를 함께 생성되는 공개키모듈(PK)과 개인키모듈(SK)을 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  11. 제10항에 있어서,
    상기 마스터키벡터(MSK_
    Figure PCTKR2019015346-appb-img-000057
    ) 모듈, 마스터키스칼라모듈(MSK_
    Figure PCTKR2019015346-appb-img-000058
    ) 및 대칭키모듈(MPK)은 객체들을 상호 구분할 수 있는 하나 이상의 식별정보를 매개변수로 하여 키유도함수(KDF)를 통해 키 값들을 생성하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  12. 암호키생성기가 식별인자를 이용하여 마스터키를 생성하는 단계;
    암호키생성기에서 암호화와 복호화에 필요한 대칭키, 개인키 및 공개키 쌍을 생성하는 단계;
    암호화 수행객체가 암호화키인 대칭키와 복호화 수행객체가 생성한 공개키를 수신하여 암호문을 생성하는 단계; 및
    복호화 수행객체가 암호키생성기를 통해 생성된 대칭키와 비대칭키 중 자신의 개인키를 통해 암호화 수행객체를 통해 생성된 암호문을 복원하는 단계를 포함하는 것을 특징으로 하는 암호화 및 복호화 방법.
  13. 제12항에 있어서,
    상기 식별인자는,
    사용자의 개인정보를 포함하는 사용자 식별인자, 사용자 단말 정보를 포함하는 단말장치 식별인자 및 비밀함수 생성인자 중 적어도 하나를 포함하는 것을 특징으로 하는 암호화 및 복호화 방법.
  14. 제13항에 있어서,
    상기 암호문은 상기 생성된 대칭키 및 복호화 수행객체의 공개키를 이용하여 GA 연산기에 연산시켜 생성하는 것을 특징으로 하는 암호화 및 복호화 방법.
  15. 제14항에 있어서,
    상기 암호문(C)은 암호화 함수(E)에 암호화키(K e)를 대입하여 순열연산(M × K → C)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
    E (M, K e) = Q -1GQ(M) = C
    여기서 Q -1GQ 는 순열함수 G, Q의 순열연산(left multiplication)이고,
    메시지 M = (m 1
    Figure PCTKR2019015346-appb-img-000059
    m n), 키 K = (k 1
    Figure PCTKR2019015346-appb-img-000060
    k n), 암호문 C = (c 1
    Figure PCTKR2019015346-appb-img-000061
    c n)는 메시지집합 M = {m 1
    Figure PCTKR2019015346-appb-img-000062
    m n} 상에서의 순열그룹 G의 원소인 것(M,K,C ∈ G)을 특징으로 하는 암호화 및 복호화 방법.
  16. 제12항에 있어서,
    상기 암호문의 복원은 복호화 함수(D)에 복호화키(K d)를 대입하여 순열연산(C × K → M)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
    D (C, K d) = HQQ(C) = M
    여기서 HQQ 는 순열함수 H, Q의 순열연산(left multiplication)이고,
    메시지 M = (m 1
    Figure PCTKR2019015346-appb-img-000063
    m n), 키 K = (k 1
    Figure PCTKR2019015346-appb-img-000064
    k n), 암호문 C = (c 1
    Figure PCTKR2019015346-appb-img-000065
    c n)는 메시지집합 M = {m 1
    Figure PCTKR2019015346-appb-img-000066
    m n} 상에서의 순열그룹 G의 원소인 것(M,K,C ∈ G )을 특징으로 하는 암호화 및 복호화 방법.
  17. 암호문 작성시 서명문을 생성하는 서명 수행객체; 및
    상기 암호문을 원문 메시지로 복호화 하기 위하여 상기 서명문을 검증하도록 형성되는 검증 수행객체를 포함하며,
    순열 그룹에 기반하여 순열 형태인 대칭키와 비대칭키를 이용하여 서명문을 생성하고 검증하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 서명 검증 시스템.
  18. 제17항에 있어서,
    상기 서명 수행객체 및 검증 수행객체는,
    순열연산을 통해 서명문을 생성하는 서명기와, 순열연산을 통해 상기 서명문을 검증하는 검증기와, 암호키생성기(MKG)를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 서명 검증 시스템.
  19. 제18항에 있어서,
    상기 서명기는,
    메시지 입력을 처리하는 입력큐;
    일회용개인키를 이용하여 순열연산을 통해 서명문을 생성하는 GA 연산기; 및
    상기 생성된 서명문의 출력을 처리하는 출력큐를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  20. 제19항에 있어서,
    상기 서명기의 GA연산기는,
    상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 서명 수행객체의 개인키(H A)를 제공받아 순열연산을 통해 서명문을 생성하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  21. 제20항에 있어서,
    상기 서명기의 순열연산은 Q AB -1H AQ AB(M) = M s 수식에 의하여 이루어지며, Q AB는 서명 수행객체와 검증 수행객체의 대칭키, H A는 서명 수행객체의 개인키, M은 메시지(m 1
    Figure PCTKR2019015346-appb-img-000067
    m n), M S는 서명문(s 1
    Figure PCTKR2019015346-appb-img-000068
    s n)인 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  22. 제21항에 있어서,
    상기 검증기는,
    서명문을 입력받아 처리하는 입력큐;
    일회용공개키를 이용하여 순열연산을 통해 서명문을 검증하여 수락된 원문메시지를 생성하는 GA 연산기; 및
    상기 수락된 원문메시지의 출력을 처리하는 출력큐를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  23. 제22항에 있어서,
    상기 검증기의 GA연산기는,
    상기 암호키생성기(MKG)로부터 대칭키(Q AB)와 서명 수행객체의 공개키(G A)를 제공받아 순열연산을 통해 서명문을 검증하고 수락 또는 거절 여부를 확인하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  24. 제23항에 있어서,
    상기 검증기의 순열연산은 G AQ ABQ AB(M s) = M 수식에 의하여 이루어지며, Q AB는 서명 수행객체와 검증 수행객체의 대칭키, G A는 서명 수행객체의 공개키, M은 메시지(m 1
    Figure PCTKR2019015346-appb-img-000069
    m n), M S는 서명문(s 1
    Figure PCTKR2019015346-appb-img-000070
    s n)인 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  25. 제18항에 있어서,
    상기 암호키생성기는,
    복수의 매개변수를 사용한 키유도함수 KDF(key derivation function)를 통해 일회용 유사난수를 생성하는 난수생성기(PRNG); 및
    상기 키유도함수(KDF)를 통해 일회용 유사난수순열(PRP)를 생성하여 키생성모듈에 제공하는 순열생성기를 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  26. 제25항에 있어서,
    상기 키생성모듈은,
    서명 수행객체의 비밀함수그룹(secret permutation group)을 나타내는 벡터함수인 마스터키벡터(MSK_
    Figure PCTKR2019015346-appb-img-000071
    ) 모듈;
    복호화할 때 사용될 비밀함수(secret permutation)를 결정하는 마스터키스칼라모듈(MSK_
    Figure PCTKR2019015346-appb-img-000072
    );
    서명 수행객체와 검증 수행객체 간 공유하는 대칭키를 생성하는 대칭키모듈(MPK); 및
    메시지 암호화와 복호화 시 사용되는 복호화 수행객체의 한 쌍의 비대칭키인 공개키와 개인키를 함께 생성되는 공개키모듈(PK)과 개인키모듈(SK)을 포함하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  27. 제26항에 있어서,
    상기 마스터키벡터(MSK_
    Figure PCTKR2019015346-appb-img-000073
    ) 모듈, 마스터키스칼라모듈(MSK_
    Figure PCTKR2019015346-appb-img-000074
    ) 및 대칭키모듈(MPK)은 객체들을 상호 구분할 수 있는 하나 이상의 식별정보를 매개변수로 하여 키유도함수(KDF)를 통해 키 값들을 생성하는 것을 특징으로 하는 순열그룹 기반의 암호화 기술을 적용한 암호화시스템.
  28. 암호키생성기가 식별인자를 이용하여 마스터키를 생성하는 단계;
    암호키생성기에서 암호화와 복호화에 필요한 대칭키, 개인키 및 공개키 쌍을 생성하는 단계;
    서명 수행객체가 상기 생성된 대칭키와 서명키인 검증 수행객체의 개인키를 수신하여 서명문을 생성하는 단계; 및
    검증 수행객체가 상기 대칭키와 검증키인 서명 수행객체의 일회용공개키를 수신하여 서명 수행객체를 통해 생성된 서명문을 검증하고 상기 검증 결과에 따라 원문메시지를 수락하거나 거절하는 단계를 포함하는 것을 특징으로 하는 암호문 서명 및 검증 방법.
  29. 제28항에 있어서,
    상기 식별인자는,
    사용자의 개인정보를 포함하는 사용자 식별인자, 사용자 단말 정보를 포함하는 단말장치 식별인자 및 비밀함수 생성인자 중 적어도 하나를 포함하는 것을 특징으로 하는 암호문 서명 및 검증 방법.
  30. 제28항에 있어서,
    상기 서명문(M S)은 서명 함수(S)에 서명키(K S)를 대입하여 순열연산(M×K →S)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
    S(M, K S) = Q -1HQ(M) = M s
    여기서 Q -1HQ는 순열함수 H, Q의 순열연산(left multiplication)이고,
    메시지 M = (m 1
    Figure PCTKR2019015346-appb-img-000075
    m n), 키 K = (k 1
    Figure PCTKR2019015346-appb-img-000076
    k n), 서명문 M s = (s 1
    Figure PCTKR2019015346-appb-img-000077
    s n) 는 각각 메시지집합 M={m 1
    Figure PCTKR2019015346-appb-img-000078
    m n} 상에서의 순열그룹 G의 원소인 것(M,K,S ∈G)을 특징으로 하는 암호문 서명 및 검증 방법.
  31. 제28항에 있어서,
    상기 서명문의 검증은 검증 함수(V)에 검증키(K V)를 대입하여 순열연산(S ×K → S)에 의해 아래 수식과 같이 생성되는 것을 특징으로 하고,
    V(S, K v) = GQQ(M s) = M
    여기서 GQQ는 순열함수 G, Q의 순열연산(left multiplication)이고,
    메시지 M = (m 1
    Figure PCTKR2019015346-appb-img-000079
    m n), 키 K = (k 1
    Figure PCTKR2019015346-appb-img-000080
    k n), 서명문 M s = (s 1
    Figure PCTKR2019015346-appb-img-000081
    s n) 는 각각 메시지집합 M={m 1
    Figure PCTKR2019015346-appb-img-000082
    m n} 상에서의 순열그룹 G의 원소인 것(M,K,S ∈G)을 특징으로 하는 암호문 서명 및 검증 방법.
PCT/KR2019/015346 2018-11-13 2019-11-12 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법 WO2020101325A1 (ko)

Priority Applications (4)

Application Number Priority Date Filing Date Title
CN201980088769.4A CN113330712A (zh) 2018-11-13 2019-11-12 采用基于排列群的加密技术的加密系统及方法
US17/293,613 US20220069984A1 (en) 2018-11-13 2019-11-12 Encryption system and method employing permutation group-based cryptographic technology
EP19884666.9A EP3883178A4 (en) 2018-11-13 2019-11-12 ENCRYPTION SYSTEM AND METHOD USING PERMUTATION GROUP BASED ENCRYPTION TECHNOLOGY
AU2019381522A AU2019381522A1 (en) 2018-11-13 2019-11-12 Encryption system and method employing permutation group-based encryption technology

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
KR10-2018-0138716 2018-11-13
KR20180138716 2018-11-13
KR10-2019-0144235 2019-11-12
KR1020190144235A KR102304831B1 (ko) 2018-11-13 2019-11-12 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법

Publications (1)

Publication Number Publication Date
WO2020101325A1 true WO2020101325A1 (ko) 2020-05-22

Family

ID=70731641

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR2019/015346 WO2020101325A1 (ko) 2018-11-13 2019-11-12 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법

Country Status (1)

Country Link
WO (1) WO2020101325A1 (ko)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111884805A (zh) * 2020-06-24 2020-11-03 易联众信息技术股份有限公司 基于区块链及分布式身份的数据托管方法及系统
CN112291057A (zh) * 2020-11-20 2021-01-29 天津市城市规划设计研究总院有限公司 城市规划领域提高智能物联网安全性的方法系统可读介质
CN112910630A (zh) * 2021-02-02 2021-06-04 浙江大华技术股份有限公司 扩展密钥的置换方法及装置
CN113098860A (zh) * 2021-03-30 2021-07-09 三一汽车起重机械有限公司 一种can总线加密方法、装置、工程机械和存储介质
CN114021173A (zh) * 2021-11-15 2022-02-08 日晷科技(上海)有限公司 基于sm9密钥交换的量子密钥扩展方法、系统、介质及终端
CN114615392A (zh) * 2022-03-18 2022-06-10 东北大学 一种基于比特联动的图像加密方法
CN114697122A (zh) * 2022-04-08 2022-07-01 中国电信股份有限公司 数据传输方法、装置、电子设备及存储介质
CN117411728A (zh) * 2023-12-14 2024-01-16 成都极数链科技有限公司 一种人员简历私有化管理方法、计算机设备及存储介质

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6212279B1 (en) 1998-06-26 2001-04-03 The United States Of America As Represented By The United States National Security Agency Method of elliptic curve cryptographic key exchange using reduced base tau expansion in non-adjacent form
US6243467B1 (en) 1998-07-23 2001-06-05 The United States Of America As Represented By The National Security Agency Method of elliptic curve cryptographic digital signature generation and verification using reduced base tau expansion in non-adjacent form
KR100406139B1 (ko) * 2001-11-28 2003-11-14 한국전자통신연구원 대칭 및 비대칭키 암호 연산 처리 시스템 및 그 처리 방법
US6782100B1 (en) 1997-01-29 2004-08-24 Certicom Corp. Accelerated finite field operations on an elliptic curve
JP2009128792A (ja) * 2007-11-27 2009-06-11 Nippon Telegr & Teleph Corp <Ntt> 公開鍵暗号システム、公開鍵暗号方法、暗号化装置、復号化装置、暗号化プログラム及び復号化プログラム
US7822200B2 (en) * 2005-03-07 2010-10-26 Microsoft Corporation Method and system for asymmetric key security
US20170118024A1 (en) * 2014-01-31 2017-04-27 Cryptometry Limited System and method for performing secure communications
KR20180060588A (ko) * 2016-11-29 2018-06-07 서울대학교산학협력단 데이터 보안이 강화된 전자 서명 장치 및 방법

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6782100B1 (en) 1997-01-29 2004-08-24 Certicom Corp. Accelerated finite field operations on an elliptic curve
US6212279B1 (en) 1998-06-26 2001-04-03 The United States Of America As Represented By The United States National Security Agency Method of elliptic curve cryptographic key exchange using reduced base tau expansion in non-adjacent form
US6243467B1 (en) 1998-07-23 2001-06-05 The United States Of America As Represented By The National Security Agency Method of elliptic curve cryptographic digital signature generation and verification using reduced base tau expansion in non-adjacent form
KR100406139B1 (ko) * 2001-11-28 2003-11-14 한국전자통신연구원 대칭 및 비대칭키 암호 연산 처리 시스템 및 그 처리 방법
US7822200B2 (en) * 2005-03-07 2010-10-26 Microsoft Corporation Method and system for asymmetric key security
JP2009128792A (ja) * 2007-11-27 2009-06-11 Nippon Telegr & Teleph Corp <Ntt> 公開鍵暗号システム、公開鍵暗号方法、暗号化装置、復号化装置、暗号化プログラム及び復号化プログラム
US20170118024A1 (en) * 2014-01-31 2017-04-27 Cryptometry Limited System and method for performing secure communications
KR20180060588A (ko) * 2016-11-29 2018-06-07 서울대학교산학협력단 데이터 보안이 강화된 전자 서명 장치 및 방법

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111884805A (zh) * 2020-06-24 2020-11-03 易联众信息技术股份有限公司 基于区块链及分布式身份的数据托管方法及系统
CN111884805B (zh) * 2020-06-24 2023-08-01 易联众信息技术股份有限公司 基于区块链及分布式身份的数据托管方法及系统
CN112291057A (zh) * 2020-11-20 2021-01-29 天津市城市规划设计研究总院有限公司 城市规划领域提高智能物联网安全性的方法系统可读介质
CN112910630B (zh) * 2021-02-02 2022-12-06 浙江大华技术股份有限公司 扩展密钥的置换方法及装置
CN112910630A (zh) * 2021-02-02 2021-06-04 浙江大华技术股份有限公司 扩展密钥的置换方法及装置
CN113098860A (zh) * 2021-03-30 2021-07-09 三一汽车起重机械有限公司 一种can总线加密方法、装置、工程机械和存储介质
CN113098860B (zh) * 2021-03-30 2023-04-07 三一汽车起重机械有限公司 一种can总线加密方法、装置、工程机械和存储介质
CN114021173A (zh) * 2021-11-15 2022-02-08 日晷科技(上海)有限公司 基于sm9密钥交换的量子密钥扩展方法、系统、介质及终端
CN114615392A (zh) * 2022-03-18 2022-06-10 东北大学 一种基于比特联动的图像加密方法
CN114697122A (zh) * 2022-04-08 2022-07-01 中国电信股份有限公司 数据传输方法、装置、电子设备及存储介质
CN114697122B (zh) * 2022-04-08 2023-11-07 中国电信股份有限公司 数据传输方法、装置、电子设备及存储介质
CN117411728A (zh) * 2023-12-14 2024-01-16 成都极数链科技有限公司 一种人员简历私有化管理方法、计算机设备及存储介质
CN117411728B (zh) * 2023-12-14 2024-02-13 成都极数链科技有限公司 一种人员简历私有化管理方法、计算机设备及存储介质

Similar Documents

Publication Publication Date Title
WO2020101325A1 (ko) 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법
WO2020235782A1 (ko) 분산 환경에서의 신원 인증 방법
JP2693348B2 (ja) 暗号化システム
WO2014139344A1 (zh) 密钥下载方法、管理方法、下载管理方法及装置和系统
WO2019223583A1 (zh) 数据加密传输方法、终端设备及超晶格混沌器件的使用方法
WO2014069783A1 (ko) 패스워드 기반 인증 방법 및 이를 수행하기 위한 장치
WO2014139342A1 (zh) 密钥下载方法、管理方法、下载管理方法及装置和系统
US20240143796A1 (en) Protecting data from brute force attack
CN110932851B (zh) 一种基于pki的多方协同运算的密钥保护方法
WO2021075867A1 (ko) 블록체인 기반 시스템을 위한 키의 저장 및 복구 방법과 그 장치
EP3167569B1 (en) Method and system for providing a secure update of code on a memory-constrained device
WO2015158038A1 (zh) 可抵御差分功耗分析攻击的加密处理装置及方法
US11438316B2 (en) Sharing encrypted items with participants verification
WO2019223624A1 (zh) 密钥分发方法及终端设备
Garg et al. Comparison of asymmetric algorithms in cryptography
WO2015030553A1 (ko) 래티스 기반 인증서 비사용 서명 시스템 및 방법
Patgiri et al. Stealth: A highly secured end-to-end symmetric communication protocol
WO2020218708A1 (ko) 홈 재활 서비스를 제공하기 위한 처방 정보를 암호화 및 복호화하는 방법 및 의사 단말
WO2023054857A1 (ko) 네트워크 내의 장치
KR102304831B1 (ko) 순열그룹 기반의 암호화 기술을 적용한 암호화시스템 및 방법
US6233337B1 (en) Methods and apparatus for enhanced security expansion of a secret key into a lookup table for improved security for wireless telephone messages
WO2021133074A2 (ko) 경량 기기 전용 개체 또는 메시지 인증 방법 및 이를 수행하는 장치들
CN116248316A (zh) 文件加密方法、文件解密方法、装置及存储介质
WO2021054619A1 (ko) 확장함수를 이용한 복수의 묵시적 인증서 발급 시스템 및 그 발급 방법
Balogun et al. Multiple Caesar cypher encryption algorithm

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19884666

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2019884666

Country of ref document: EP

Effective date: 20210614

ENP Entry into the national phase

Ref document number: 2019381522

Country of ref document: AU

Date of ref document: 20191112

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: JP