A first device generates first encrypted data from a second public key corresponding to second ID regarding a second device and a first random number and transmits first ID regarding the first device, second ID, and first encrypted data. The second device generates second encrypted data from a first public key corresponding to the first ID and a second random number, generates second verification data by generating a second shared-key candidate from the second random number, the first encrypted data, and a second private key, and transmits the second encrypted data and second verification data. The first device generates first verification data by generating a first shared-key candidate from the first random number, the second encrypted data, and a first private key and transmits the first verification data. The first and second devices examine the second and first verification data by using the first and second shared-key candidates, respectively.