Provided are a method for automatically generating an address in the IPv6-based Internet when a sender having a pair of a public key and a private key establishes a network connection, and a data format thereof. The method includes generating a CGA address and a CGA option based on the public key and a predetermined parameter, generating a signature option for verifying the CGA option, additionally generating a timestamp option in a case where a unidirectional message is transmitted to the network, and additionally generating a nonce option containing random numbers in a case where a bidirectional message is transmitted to the network, and adding the signature option, the timestamp option and the nonce option to a Neighbor Discovery (ND) option field to form an ND message, and transmitting the ND message to the network. When a host enters the network in a Zero Configuration over the IPv6-based Internet, the host can securely generate its own address without using a manual key. The method can also be applied to general IPv6 packet authentication or position authentication of a mobile node.