Is it safe to encrypt a part of the message with RSA and the rest with AES? The structure can be the following:


A signature (on the sha-256 of everything else).
RSA-encrypted random AES key (or none) and as much data as it fits into an RSA block.
AES-encrypted blocks with the rest of the data (or none at all).


The point is that an RSA block can hold a lot. Seems like a waste of space.

Is it worse than this?:


A signature (on the sha-256 of everything else)
RSA-encrypted random AES key
AES-encrypted blocks with the data
You can put in as much data into RSA as it can hold, bar the padding. The padding is required to keep RSA (provably) secure - presuming that RSA is secure itself of course.

So yes, what you are supposing is perfectly possible. It actually has a name: encryption with partial message recovery.

I found one paper that claimed that the security is may not be be provable secure, so beware that you're threading on largely uncovered ground here; there aren't any standardized schemes out there.



It may not be optimal to use current padding techniques as you would about double the randomness in the encryption scheme: once for the secure padding itself and once for the AES key. On the other hand, this is the best you can do with standardized functions libraries.

That said, the overhead of RSA-OAEP is only about 42 bytes, so for a 2048 bit RSA key and a 128 bit AES key (about the minimum key size) there would only be a static overhead of 42 + 16 = 58 bytes, leaving 256 - 58 = 198 bytes for the message itself.

If you require protection against active attacks that may alter the ciphertext you may need to include an authentication tag over the rest of the message, adding another 8 to 16 bytes for e.g. AES-GCM.



I'd propose a scheme such as this:

R = M | RSA-PSS-SHA256(Sk, M)
K = Rand(k)
r1 = s / 8 - 42 - k / 8
R1 = Sub(R, 0, r1)
R2 = Sub(R, r1)
C = RSA-OAEP(Pk, K | R1) | AES-GCM(K, R2)


Where:


M is the message
R is the signed message (using the sender's private key)
K is an AES key of length k bits
Rand is a cryptographically secure random number generator (or key generator operating in bits)
s is the receivers key length in bits
o is the OAEP overhead in bytes (using SHA-1 for the underlying MGF1)
r1 is the size of R1, r2 is the size of R2
R1 is the partial message encrypted using RSA-OAEP
R2 is the partial message encrypted using AES-GCM
Sub takes a substring of the given array and offset, and optional end offset
C is the resulting ciphertext, including the AES-GCM tag


The IV for AES-GCM can be left at 12 zero bytes (as the AES key gets regenerated each time anyway).



Notes:


if you use normal PKCS#1 signing that you leak information about the message that you encrypt. So you should use PSS padding or you should encrypt the signature as well. Above scheme uses a combination of both;
while you're at it you might want to look for RSA-PSS-R, which is a scheme for signatures giving message recovery, defined here and in IEEE P1363a;
to show a more efficient scheme, try this if you're academically inclined - it also includes a proof of security;
it is also possible to use RSA-PKCS#1 and AES-CBCbut beware that those are not IND_CCA secure and that you should not allow padding oracle attacks.