Seems possible.
- Use some hardware random number generator (will speed up things and improve security a lot)
Use a fast (33MHZ?) '51 clone
- Write (or get from somewhere) some arbitrary precision (or fixed high precision) math library (say, 128-byte integers)
- Apply the standard RSA algorithm.
- Debug.
- Enjoy.

If you're in masochist mood, go for ASM.
If you feel rich or pressed for speed, go, look for dedicated hardware alternatives.