Method for forming virtual private network based on post-quantum cryptography and virtual private network operating system performing same

1. A method for forming a virtual private network performed by a first device which includes a processor to form the virtual private network with a second device, the method comprising the steps of:

requesting, by the processor, a handshake for forming the virtual private network;

receiving, by the processor, a signature and a public key;

authenticating, by the processor, the second device by using the signature;

generating, by the processor, a symmetric key by using the public key; and

performing, by the processor, virtual private network communication by using the symmetric key,

wherein generating the symmetric key by using the public key comprises the steps of:

generating, by the processor, a key message by using a random number generator;

generating, by the processor, capsule random value by hashing the key message;

generating, by the processor, a key capsule by capsuling the key message and the capsule random value by using the public key;

transmitting, by the processor, the key capsule; and

generating, by the processor, a symmetric key by using the key capsule,

wherein generating the symmetric key by using the key capsule comprises the steps of:

generating, by the processor, a prekey through a hash for the key message and the public key;

generating, by the processor, key hash value by hashing the prekey and the key capsule; and

generating, by the processor, the key hash value as the symmetric key,

wherein the public key includes a key value which is determined by values of a second key vector, which is generated by a lattice-based algorithm, added to values obtained by multiplying a first key vector, which is generated by the lattice-based algorithm, and a key matrix.

2. The method for forming a virtual private network of claim 1 , wherein the signature comprises a signature value and a first hash value, and the authenticating of the second device using the signature comprises the steps of:

calculating, by the processor, a first matrix based on the signature value and the public key;

obtaining, by the processor, upper N (N is a natural number) coefficients of a polynomial ring corresponding to the first matrix as first bits; and

authenticating, by the processor, the second device based on the first bits.

3. The method for forming a virtual private network of claim 2 , wherein the authenticating of the second device based on the first bits comprises the steps of:

receiving, by the processor, an authentication message from the second device;

obtaining, by the processor, the first bits and a second hash value for the authentication message;

determining, by the processor, whether the second hash value is the same to the first hash value; and

determining, by the processor, that the authentication of the second device is successful when the second hash value is the same to the first hash value.

4. A method for forming a virtual private network performed by a second device which includes a processor to form the virtual private network with a first device, the method comprising the steps of:

generating, by the processor, a public key and a private key;

requesting, by the processor, a handshake from the first device;

performing, by the processor, a signature by using an authenticate message;

transmitting, by the processor, the signature and the public key to the first device; and

generating, by the processor, a symmetric key by using a key capsule received from the first device,

wherein the generating the public key and private key comprises the steps of:

defining, by the processor, a key matrix corresponding to a random polynomial ring;

sampling, by the processor, a first key vector generated by a grid-based algorithm and a second key vector having a first distance with the first key vector; and

generating, by the processor, the public key and the private key by using a key value which is determined by values in a second key vector, which is generated by a lattice-based algorithm, added to values obtained by multiplying a first key vector, which is generated by the lattice-based algorithm, and the key matrix,

wherein the generating a symmetric key by using the key capsule received from the first device comprises the steps of:

extracting, by the processor, a key message by opening the key capsule by using the private key;

generating, by the processor, opened random value through hash for the key message;

generating, by the processor, verification capsule by capsuling the key message and the opened random value as the public key;

confirming, by the processor, if the verification capsule and the key capsule are the same;

generating, by the processor, a prekey by hashing the key message and the public key if the verification capsule and the key capsule are the same; and

generating, by the processor, a symmetric key by hashing the key capsule and the prekey.

5. The method for forming a virtual private network of claim 4 , wherein the defining of the key matrix comprises the steps of:

generating, by the processor, a random number using a random number generator;

generating, by the processor, a seed by substituting the random number into a hash function;

generating, by the processor, the random polynomial ring using the seed; and

defining, by the processor, the key matrix corresponding to the random polynomial ring.

6. The method for forming a virtual private network of claim 4 , wherein the performing of the signature comprises the steps of:

obtaining, by the processor, a second bit based on the key matrix;

obtaining, by the processor, the second bit and a second hash value for the authenticate message; and

generating, by the processor, a signature value using the second hash value and a first key vector.

7. The method for forming a virtual private network of claim 6 , wherein the obtaining of the second bit comprises the steps of:

obtaining, by the processor, a signature random number using a random number generator;

calculating, by the processor, a second matrix by multiplying the key matrix by the signature random number; and

acquiring, by the processor, upper N (N is a natural number) coefficients in a polynomial ring corresponding to the second matrix as the second bit.