Am I missing something or is the fix a little computer in the fob to cryptographically sign a one-time challenge sent by the car? I mean, RSA isn't that hard, is it?

Here's how I see it: the car broadcasts a (short duration) challenge message on short range (10 meters, say), the key fob, once in range, signs the challenge message, transmits it, the car checks the signature with the fob's known public key, and Bob's your uncle. If the fob can compute a signature of the challenge in 500ms, the window doesn't need to be much longer. Sure, people will likely be able to pull private keys from the fob with some effort, and duplicate it that way, but that's no worse than today. Reprogramming the car wouldn't significantly harder than it is today either.

If we want convenience and security, it seems fine to make the key fob a little more complicated and beefy.

I feel like this is by no means a new idea and maybe I'm missing something.

edit: I was missing something.