A key information issuing device (1, 1A, 1B) issuing key information to a key information retaining device (2, 2A, 2B) includes an authentication module (14, 3) authenticating an issuer of the key information, an output module (13) outputting the key information to the key information retaining unit, and a recording module (11) recording a mapping of the issued key information to the key information retaining unit. The key information is issued in response to an indication of the authenticated issuer.