Well, matter has rest mass, energy doesn't.
Now to your previous statement.
If the hypothetical message can be decrypted, then it exists.
Then you have admitted that something that is not embodied "exists". It is of no consequence whether or not the key "exists" since any message intended for decryption can be decrypted.
It is also relevant that you consider "material" things contingent upon knowledge.