What well-known algorithms are suited for the following task?
I need system A (and only system A) to be able to encrypt some data, with system B being able to decrypt it. At system B, I want to be sure the ciphertext wasn't tempered with. And I want to pre-share system A's public key (store it at system B).
I'm new to cryptography and after some digging I assumed I need a public-key encryption algorithm with MAC. I think RSA is just for this task, but not sure.
I believe you need both a general and a specific answer: general to provide a big-picture understanding of the solution and specific to guide you to particular tools. Let's start with the big picture.
What you are describing is a signed and encrypted message which is accomplished with public key encryption. The message is encrypted using the recipient's public key which ensures that only the recipient, using their private key, can decrypt it. The message is signed using the sender's private key so the recipient can be sure that the message was sent by the sender. The signature also contains a cryptographic hash of the message (encrypted with the sender's public key) at the time of the signing, which ensures the recipient that it has not been changed since the sender signed it. If required, a trusted timestamp server can be used to add a timestamp to the message hash and encrypt the combination with its private key prior to the sender encrypting the signature so the recipient also knows when the message was signed by the sender.
NOTE: I provided a longer and somewhat clearer explanation of this process in another answer yesterday.
As far as algorithms, to code this at a low level you would need to use an asymmetric key algorithm (aka public key) of which RSA is certainly the best known, but you will need more to complete the process. You need a hash algorithm [I recommend SHA-3.] But you also need a higher level protocol that standardizes how the pieces are put together to ensure consistency and reliability. These exist in a number of forms for various use cases, S/MIME, x509 and TLS are examples.
As you mentioned, you need an infrastructure to generate public-private key pairs and distribute them in a secure manner, referred to as Public Key Infrastructure (PKI). There are a number of approaches to this that apply to different use cases. For use inside a single organization, the Microsoft Active Directory system includes a certificate service that can issue certificates (which include the key pairs and have an expiration and a defined owner) and confirm their validity and ownership for other users. In the public Internet environment, public certificate services are available from firms such as VeriSign, DigiCert, Entrust and many others.
Exactly how these pieces are put together is somewhat non-trivial. If you are looking to code a solution, I urge you to research off-the-self encryption solutions that will provide the functionality you need. Reliably building encryption code is not easy and it isn't necessary in almost all cases. Robust solutions, both commercial and open source are quite common.
You will need to choose a hash algorithm. I recommend the recently published SHA3 if at all possible. Several other widely used ones have been cracked or at least shown to be weak in recent years, so it would be wise to use the newest.
