Client authentication on limited hardware I'm developing a authentication and authorization protocol for a Bluetooth device. The device should communicate with an Android app and needs to be able to authenticate the app during the connection phase. Some kind of secret or asymmetric pair  is therefore needed to be shared by the app and the Bluetooth device. As apps can be reverse-engineered we need to be able to update this secret.

RSA was the first solution that came to mind. The device can store the public key of some root certificate and then verify the signature of the app certificate like during TLS. The device keeps a list of valid certificate fingerprints.

However, the Bluetooth device is too weak to implement RSA. I need something (much) cheaper. Is there any such protocol?
I'd suggest that you clearly define which kind of Bluetooth device you are using, more specifically what its capabilities are with respect to processing power, etc. Another question, can you enter a number on a bluetooth device (e.g., for a PIN-based authentication, for example)? From what you're writing, I'd assume that RSA won't be a plausible solution, since the smallest key length the constrained bluetooth device will have to deal with is 1024 bit (2048 is actually recommended). ECC is likely to prove unsuitable as well, since despite the fact that the key length is much smaller, the device has to be able to deal with ECC algorithm which may be quite inefficient without the proper hardware support of even not supported by the device at all. In my experience, using ECC instead of RSA on Android platform does not necessarily entail a performance gain, see the discussion here. 
Another important conceptual question is: what are the security goals/requirements in your specific case and against which attacker the system has to be secure (the so-called attacker model)?
Taking into account what you've written in your question, I would assume that authentication using one-time PIN may be a better option than using full-fledged certificate-based authentication based on RSA (or on ECC).