Public-key cryptographic systems are often implemented on top of an existing problem. For example, RSA is built on top of integers and the difficulty of factoring. ECDSA/ECIES are built on top of elliptic curves and the difficulty of the discrete logarithm.
My question is, what are, mathematically speaking, the exact primitives needed to implement public-key based signature and encryption cryptography in a generic way?
Unfortunately there is no real answer to this. We know that one-way trapdoor permutations suffice, but this is really just an abstraction of factoring. ECDSA/ECIES/ElGamal don't work via any trapdoor permutation, and neither do lattice-based public-key encryption schemes.
In the private-key world, we know that one-way functions are necessary and sufficient. However, we have no analogous primitive that is both necessary and sufficient for public-key encryption, beyond itself. (That is, of course, public key encryption is both sufficient and necessary for public-key encryption, but this is a very annoying answer that means nothing.)
Note, that one-way functions are sufficient for building digital signatures, and so the question of what is necessary is really only for public-key encryption.
It depends of course what you require for your cryptosystem, but for just encryption and signature generation (which is also used for authentication, not just for non-repudiation) you just require RSA or ECC.
For RSA the key pair generation is identical for signature generation and encryption. Even the modular exponentiation is about the same. Signature generation is largely identical to decryption and signature verification is largely identical to encryption. The main difference is the padding scheme used for encryption and the signature.
For ECC the key pair generation is also identical for signature generation and encryption. There are some differences between ECDH and ECDSA, but the calculations can still be performed within a largely overlapping set of calculations. ECDH can be used as input for ECIES, which is the encryption method commonly used for ECC cryptography.
There is however not a generic requirement for primitives within a signature generation or encryption scheme, as there is no common construction for signature generation or encryption schemes. Both RSA signature generation and ECDSA are quite different, and the same goes for RSA OAEP and ECIES with, for instance, AES-CBC.
Note that signature generation usually also requires a secure hash algorithm and that encryption schemes usually also require a symmetric cipher, unless they are used for a very small amount of data.
[EDIT] And all schemes rely on a (well seeded, pseudo) random number generator, certainly when it comes to key pair generation.
