One thing I was surprised to learn about AES is that random padding can be added to the message to make it a multiple of block size. What I can not wrap my head around is how this random padding can reliably be removed from the message upon decryption, given that if it is generated by a truly random process, the recipient has no information about it.
- What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?
- Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?