How can I embed SmartCard/certificate challenge functionality in an embedded project?
These chips are not common, but they exists. There are 'Trusted Platform Modules' which contain many encryption functions, but they are in general hard to use. For your case, you probably want to look at ATECC108A - Atmel CryptoAuthentication chip.
It is SO-8, you talk to it over I2C, and it has PKI engine using elliptic curves (which have much shorter keys than RSA-based systems).
The only big problem with that is that there is no public full datasheet for it. I have no idea how hard is it to obtain it.