Integrity of a wirelessly telemetered message communicated between an implantable medical device and an external programmer is authenticated by encoding the message. The message is encrypted based on a random number or time stamp and a secret key. The message is authenticated by encryption and decryption or by executing a hash function.