Correct method to encrypt data so that it can be decrypted only by Alice and Bob I need to build a system that stores encrypted transactions. Transaction involves always two parties. Payer and payee. Both must be able to download encrypted transaction from server and decrypt it using their own private key. And likewise issuing transaction must be possible by either one just by knowing both's public keys.

Is it safe to encrypt exactly same message twice (using different public keys), first by Alices public key and then by Bobs public key?(and make both 'versions' available) That way Alice can decrypt the first one and Bob the second one using their private keys. If attacker knows that two encrypted messages are actually the same, can that information help him crack the encryption?

Or is there a smarter way? And what algorithm do you recommend? I was thinking of RSA
The traditional way to go about this would be to generate a symmetric key and use AES to encrypt the transaction using that symmetric key. You would then encrypt that symmetric key with Alice's public key and publish that. Then encrypt the symmetric key with Bob's public key and publish that. You also publish the AES encrypted version of the transaction.

I say that is the traditional way is you could, theoretically encrypt the transaction directly with RSA (though it is typically not recommended). The transaction would have to fit size constraints (see my comment).

Now, there is one additonal requirement that you might not be aware of. I'm assuming that you wouldn't want anyone to be able to modify any of these messages that will be uploaded to a server without being detected (think a hacker breaking into the server). Therefore, you will have to digitally sign the copies of the encrypted symmetric keys and compute a MAC on the AES encrypted transaction. The MAC could be a traditional HMAC or by using an authenticated encryption mode such as GCM.