There is provided a cryptographic communication apparatus for conducting a key exchange procedure with another cryptographic communication apparatus that shares a password. The apparatus includes a first encryption unit that encrypts information that is based on a first random number using a public key of the another apparatus, a second encryption unit that encrypts the information that is based on the first random number encrypted by the first encryption unit using the password, a third encryption unit that encrypts information that is based on a second random number using the first random number, and transmits a first signal and a second signal to the another apparatus, the first signal including the information that is based on the first random number encrypted by the second encryption unit, and the second signal including information that is based on the second random number encrypted by the third encryption unit.