How NIST's ECC curves (P256 alias secp256r1 and friends) have been generated is public: that's in SEC2v1 (with reference to the "verifiably random" method of ANSI X9.62-1998, a draft of which is here), including the seed of the SHA-1-based PRNG used; however, how that seed was chosen is not public, and it's anyone's guess if that's just lost or if something nefarious was done (yet notably: we know no method to do something nefarious).
How Brainpool's ECC curves have been generated is public, and based on a nothing-up-my-sleeve number. All the details where formerly online there (pages 8 to 10), with copy at the Web Archive.
Disclaimer: I do not know who actually checked that the numbers match the methods listed above.
Bernstein's Curve25519 matches more security criteria (see there) and is designed to be easier to protect against side channel attacks, all things equal. But on the other hand:
- It is not known any practical attack taking advantage of characteristics of Brainpool (or NIST) curves for ECDSA signature, and as far as I know for proper implementation of ECIES encryption.
- Single-chip tamper-proof devices (including all those with a Common Criteria certification that I am aware of) currently tend to have a hardware accelerator that does not directly support Curve25519; thus secure implementations of Curve25519 on said devices would be slow, or at least not security evaluated. That's the argument given by nitrokey's support:
Curve 25519 isn’t supported by the smart card chip we are using
The question echoes a common opinion:
ECC seems more future-oriented than RSA
to which there are several counterarguments:
- With key sizes giving comparable security against today's attacks, ECC might well turn out to be what gives the worst protection against hypothetical future quantum computers usable for cryptanalysis, because the current guess is that the larger keys would require quantum computers with about proportionally more coherent qubit, and scalability of that currently is the major hurdle in quantum computing.
- For tasks using a securely generated private key (signing in particular), ECC is typically much more vulnerable than RSA is to failure of the random number generator, and that's a very practical line of attack.
- For tasks performed with the public key (verification and encryption), RSA is faster, and simpler (thus safer) than ECC is.
Thus if we stick to what's available on secure hardware, target longer term security, do not dismiss quantum computers usable for cryptanalysis within a lifetime as pipedream, and RSA-4096 gives acceptable signature generation and decryption speed, it might be a good choice. See this for applications where RSA makes a lot sense.
Personally I'm far from paranoid on key size or imminent cryptopocalyse by quantum computers (on the grounds that practical attacks tend to be far more mundane, like penetration of the machine where the Smart Card stands, which might not allows private key extraction but allows rogue signature/decryption; side channel attacks; fault attacks), and I'd be happy with 256-bit ECC (or better) if RSA is unacceptably slow, as happens a lot on Smart Card CPUs at 3072-bit level or more: work for secret-key operation increases about with the cube of the key size for both RSA and ECC, and the smaller multiplicative constant for RSA far from offsets it all.