I'm reading about OAEP / PKCS padding used for PGP to turn deterministic algorithms like RSA from deterministic encryption to probabilistic encryption (randomness in the resulting output). That way the same input encrypted with RSA should produce a different output each time.
However, the wikipedia page for probabilistic encryption addresses a seeming simple solution but doesn't give any details what is wrong with it:
An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes. Techniques such as Optimal Asymmetric Encryption Padding (OAEP) integrate random padding in a manner that is secure using any trapdoor permutation.
Can someone explain (to a beginner) what is insecure about random padding being added?
In addition, for PGP encryption using RSA, my understanding is that a random nounce / AES key is generated and encrypted using RSA. Then that AES key is actually used to encrypt the source text.
So, if the whole AES key is random to begin with (and required to know anything about the encrypted text) - what exactly is OAEP adding?