Key generation method for self-configuration
A key generation method for self-configuration is provided which includes selecting existing nodes as many as a predefined reference number t from nodes which configure a network; transmitting a partial key request message to the selected existing nodes; and generating a node key based on randomized partial keys received in response to the partial key request. Accordingly, when a new node intends to join the network, the existing nodes forming the network can allocate a node key to the new node by themselves. Also, whether the node key of the new node is compromised or not can be verified using the error-checking witness.
1. A key generation method, comprising:
selecting existing nodes as many as a predefined reference number t from nodes which configure a network;
transmitting a partial key request message to the selected existing nodes; and
generating a node key based on randomized partial keys received in response to the partial key request, wherein:
the randomized partial keys are randomized by the existing nodes using shuffled random numbers,
each shuffled random number, Rj, is generated based on the equation:
R
j
=
∑
k
=
1
,
k
≠
j
t
sign
(
ID
j
-
ID
k
)
(
r
j
+
r
k
)
mod
q
where
{
sign
(
x
)
=
1
if
x
>
0
sign
(
x
)
=
-
1
if
x
<
0
,
and
ID j denotes the identification of the node generating the partial key, r j denotes the random number of the node generating the partial key, ID k denotes the identification of the k th existing node, and r k denotes the random number of the k th existing node.
2. The key generation method of claim 1 , wherein the node key is generated by summing all of the randomized partial keys as many as the reference number.
3. The key generation method of claim 1 , further comprising verifying whether the node key is correct.
4. The key generation method of claim 3 , wherein:
the verifying operation determines that the node key is correct when a product of values acquired by raising t error-checking witnesses generated at the network initialization to the power of a new node ID is equal to a value acquired by raising a generator generated at initialization to the power of a node key of the new node; and
the verifying operation determines that the node key is incorrect when the two values are not equal to each other.
5. The key generation method of claim 1 , wherein the node key is generated based on a Shamir's secret sharing algorithm.
6. The key generation method of claim 1 , wherein the selecting operation:
receives response messages in reply to a join message requesting joining to the network; and
selects the existing nodes as many as the predefined reference number t from the nodes which transmit the response messages.
7. A partial key generation method, comprising:
generating, in response to receiving a partial key request message, a partial key of a node which transmits the partial key request message;
randomizing the generated partial key; and
transmitting the randomized partial key to the node which transmits the partial key request message, wherein:
the randomized partial keys are randomized by the existing nodes using shuffled random numbers,
each shuffled random number, Rj, is generated based on the equation:
R
j
=
∑
k
=
1
,
k
≠
j
t
sign
(
ID
j
-
ID
k
)
(
r
j
+
r
k
)
mod
q
where
{
sign
(
x
)
=
1
if
x
>
0
sign
(
x
)
=
-
1
if
x
<
0
,
and
ID denotes the identification of the node generating the partial key, r j denotes the random number of the node generating the partial key, ID k denotes the identification of the k th existing node, and r k denotes the random number of the k th existing node.
8. The partial key generation method of claim 7 , wherein the generating operation comprises:
receiving:
an ID ID n+1 of the node which transmits the partial key request message; and
IDs ID k of nodes, excluding itself, selected by the node transmitting the partial key request message;
calculating a Lagrangian coefficient of the node transmitting the partial key request message using the ID ID n+1 of the node transmitting the partial key request message, the IDs ID k of the nodes, and its ID ID j ; and
generating the partial key by multiplying the calculated Lagrangian coefficient by its node key K j .
9. The partial key generation method of claim 8 , wherein the randomizing operation comprises:
generating a random number r j ;
transmitting the generated random number r j to the nodes, excluding itself, selected by the node transmitting the partial key request message;
receiving random numbers r k from the nodes;
generating a shuffled random number R j using the IDs ID k of the nodes received in the generating operation, the random numbers r k received in the receiving operation, the random number r j generated in the transmitting operation, and the ID ID j ; and
randomizing the partial key by summing the shuffled random number and the partial key.
10. The partial key generation method of claim 7 , wherein the partial key is generated based on a Shamir's secret sharing algorithm.
11. A non-transitory computer-readable storage medium storing a program to control nodes associated with a network, comprising instructions to cause a computer to:
control a new node to select existing nodes as many as a predefined reference number t from nodes which configure a network;
control the new node to transmit a partial key request message to the selected existing nodes; and
control the selected existing nodes to generate a node key based on randomized partial keys received in response to the partial key request, wherein:
the randomized partial keys are randomized by the existing nodes using shuffled random numbers,
each shuffled random number, Rj, is generated based on the equation:
R
j
=
∑
k
=
1
,
k
≠
j
t
sign
(
ID
j
-
ID
k
)
(
r
j
+
r
k
)
mod
q
where
{
sign
(
x
)
=
1
if
x
>
0
sign
(
x
)
=
-
1
if
x
<
0
,
and
ID j denotes the identification of the node generating the partial key, r j denotes the random number of the node generating the partial key, ID k denotes the identification of the k th existing node, and r k denotes the random number of the k th existing node.
12. The non-transitory computer readable storage medium of claim 11 , wherein the controlling of the selected existing nodes to generate a node key comprises controlling the selected existing nodes to sum all of the randomized partial keys as many as the reference number.
13. The non-transitory computer readable storage medium of claim 11 , further comprising controlling an existing node to verify whether the node key is correct.
14. The non-transitory computer readable storage medium of claim 13 , wherein controlling of the existing node to verify whether the node key is correct comprises:
controlling the existing node to determine that the node key is correct when a product of values acquired by raising t error-checking witnesses generated at the network initialization to the power of a new node ID is equal to a value acquired by raising a generator generated at initialization to the power of a node key of the new node; and
controlling the existing node to determine that the node key is incorrect when the two values are not equal to each other.
15. The non-transitory computer readable storage medium of claim 11 , wherein the controlling of the selected existing nodes to generate a node key comprises controlling the selected existing nodes to generate the node key based on a Shamir's secret sharing algorithm.
16. The non-transitory computer readable storage medium of claim 11 , wherein the controlling of the new node to select existing nodes comprises controlling the new node to:
receive response messages in reply to a join message requesting joining to the network; and
select the existing nodes as many as the predefined reference number t from the nodes which transmit the response messages.
17. A non-transitory computer-readable storage medium storing a program to control nodes associated with a network, comprising instructions to cause a computer to:
control existing nodes to generate, when receiving a partial key request message, a partial key of a node which transmits the partial key request message;
control an existing node to randomize the generated partial key; and
control the existing node to transmit the randomized partial key to the node which transmits the partial key request message, wherein:
the randomized partial keys are randomized by the existing nodes using shuffled random numbers,
each shuffled random number, Rj, is generated based on the equation:
R
j
=
∑
k
=
1
,
k
≠
j
t
sign
(
ID
j
-
ID
k
)
(
r
j
+
r
k
)
mod
q
where
{
sign
(
x
)
=
1
if
x
>
0
sign
(
x
)
=
-
1
if
x
<
0
,
and
ID j denotes the identification of the node generating the partial key, r j denotes the random number of the node generating the partial key, ID k denotes the identification of the k th existing node, and r k denotes the random number of the k th existing node.
18. The non-transitory computer readable storage medium of claim 17 , wherein the controlling of the existing nodes to generate a partial key comprises:
controlling the existing nodes to receiving:
an ID ID n+1 of the node which transmits the partial key request message; and
IDs ID k of nodes, excluding itself, selected by the node transmitting the partial key request message; and
controlling the existing nodes to:
calculate a Lagrangian coefficient of the node transmitting the partial key request message using the ID ID n+1 of the node transmitting the partial key request message, the IDs ID k of the nodes, and its ID ID j ; and
generate the partial key by multiplying the calculated Lagrangian coefficient by its node key K j .
19. The non-transitory computer readable storage medium of claim 18 , wherein the controlling of the existing node to randomize the generated partial key comprises:
controlling the existing node to:
generate a random number r j ; and
transmit the generated random number r j to the nodes, excluding itself, selected by the node transmitting the partial key request message;
controlling the existing node to receive random numbers r k from the nodes;
controlling the existing node to generate a shuffled random number R j using the IDs ID k of the nodes received in the generating operation, the random numbers r k received in the receiving operation, the random number r j generated in the transmitting operation, and the ID ID j ; and
controlling the existing node to randomize the partial key by summing the shuffled random number and the partial key.
20. The non-transitory computer readable storage medium of claim 17 , wherein the controlling of the existing nodes to generate a partial key comprises controlling the existing nodes to generate the partial key based on a Shamir's secret sharing algorithm.
21. The key generation method of claim 1 , wherein the one existing node among the existing nodes, upon generating the partial key, generates a random number and transmits the generated random number to the existing nodes.
22. The partial key generation method of claim 7 , wherein the one existing node among the existing nodes, upon generating the partial key, generates a random number and transmits the generated random number to the existing nodes.
23. The key generation method of claim 1 , wherein the identification of each of the existing nodes comprises at least one of an e-mail address, a unique number of a mobile device, an internet protocol (IP) address, a media access control (MAC) address, and a public key certificate.