Is RSA of a random nonce with no padding safe? Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a message, Alice randomly generates a single-use symmetric key (say, an AES key) $K$, encrypts the message with this symmetric key, and sends this encrypted message alongside with $K$ encrypted with RSA with Bob's public key.

Suppose we use no padding for $\textrm{RSA}_{B_{pub}}(K)$ (in other words, to pad with zero bytes). The obvious (to me) problems with a lack of padding are that an attacker can guess the plaintext (not possible here, it's random) and that encrypting the same plaintext twice gives the same result (again, not happening here). What are the known weaknesses of this scheme (or is it safe)?
If you pad a 128-bit value $K$ with zeroes to the left, and interpret the value numerically with big-endian convention (as happens in PKCS#1 in general), you end up with a value which is no greater than $2^{128}$. If the public exponent is $e = 3$, then the "encrypted value" is no greater than $2^{768}$, and no actual modular reduction takes place. Consequently, a simple cube root extraction on plain integers reveals $K$.

So, that can be quite unsafe.

What is safe is the following:


you generate a random integer $x$, between $0$ and $n-1$ ($n$ is the RSA modulus);
you encrypt $x$ by simply raising it to the power $e$ modulo $n$;
the encryption key you will use with AES is $h(x)$ for some hash function $h$.


It is still relatively limiting, in that this is safe as long as you do one encryption only of $x$. If you want to "send" your symmetric key $K$ to several recipients (a common model, e.g. for email encryption), then the scheme above does not work, and, more generally, you need some per-encryption randomness inserted (as PKCS#1 does for encryption).