The key distribution system comprises a terminal and a server which establish encrypted communication with each other by use of a common key cryptography using a communication secret key. To issue a new communication secret key, the terminal generates a secret value and encrypts it with a public key and sends the encrypted secret value to the server. The server decrypts the encrypted secret value with a private key paired with the public key. The server issues the new communication secret key, and encrypts it with a common key cryptography using the secret value, and sends the encrypted new communication secret key to the terminal. The terminal decrypts the encrypted new communication secret key with the secret value, thereby obtaining the new communication secret key. Thereafter, the terminal and the server use the new communication secret key.