[jongraehl]

The SecureID device S computes S(s,t) without any input from the server the user is authenticating to. t is synchronized time and available to everyone. s is a secret specific to that device. I don't know if it's a shared secret, but the compromise suggests that either it is, or RSA kept the 'private key' part on their servers for convenience.

You're right that a different device S' that received a challenge c from the server and computed S'(c,s,t) could offer more security via public key crypto. But it would take more power (if communicating to the client machine to avoid user transcription of the challenge) or have a more cumbersome UI. I'll bet such devices are already sold.