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?