An electronic key management device includes a generator (152, 153) configured to generate at least one of a first execution key and a second execution key for obtaining a permission for transiting to a registration mode for registering an electronic key of a vehicle in an in-vehicle authentication device or to an invalidation mode for invalidating the electronic key registered in the in-vehicle authentication device, in response to a predetermined request, and a communication controller (154) configured to transmit the first execution key generated by the generator to a first terminal device, and transmit the second execution key generated by the generator to a second terminal device that is a terminal device different from the first terminal device and is registered in advance as a terminal device of an authorized owner.