Is it safe to encrypt a public key alongside a message with AES? If I have a message M and a public key P, and I encrypt them alongside one another:

CIPHER = AES(M + P, aes_key)


Is CIPHER now weakened if someone knows what P is? It seems like if I encrypted only P:

CIPHER = AES(P, aes_key)


that it should be possible to recover aes_key from CIPHER. I realize that this is different than encrypting M + P, but is a weakness introduced?

My goal is to be able to send a signed encrypted message without revealing the originator publicly.
Probably not in this case, although not for the reason you gave.

As @Sadeq points out in the comments, AES is resistant to known-plaintext attacks. This means that by simply knowing M+P or P (the entire plaintext you've encrypted) it should not be possible to recover the AES key.

However, key recovery isn't the only attack and it raises a deeper question: authentication.

This design which sends the signer's public key along with the message seems to imply that the recipient doesn't already know what key the message should be signed by.

If the recipient doesn't know exactly what key the message should be signed by in advance, then he probably shouldn't just accept any random public key for the signature. Even when the AES key is negotiated perfectly securely, the CBC and CTR modes suggested by @sadeq can allow an active attacker to manipulate the decrypted plaintext in well-controlled ways. An attacker could possibly anticipate the signing key and replace it with his own, or selectively corrupt bits of it and observe the recipient's timing and behavior to identify the actual signing key.

It also raises the important question of how the AES key was negotiated securely. How do the sender and recipient know they're not talking to a man-in-the-middle? Maybe you've already addressed that somehow, I don't know.

Of course, there are systems which enable one to securely accept a new public key. For example, if it is signed by a trusted third-party like a certificate authority. But these systems are usually not optimized for anonymity and they raise additional complications for your goal. Address issues of key enrollment, revocation, expiration, etc. from the beginning.

As usual, the strong authentication problem is the harder one here. Solve the authentication and then come back and think about the encryption. It will be much easier to identify and prevent the active attacks that way.