Situation: within a mobile application, we're generating and storing a private key (RSA or ECC) which we use to sign miscellaneous requests with (to authenticate using the mobile as a 2nd factor, or to sign transactions).
We now want to securely store that private key on the mobile device, protected with PIN (and other) credentials.
We have a similar situation where we store OAuth2 bearer tokens (refresh token), there we use key derivation to encrypt the tokens using the PIN entered by the user. For a 6-digit PIN, there's 1'000'000 possible outcomes when decrypting the tokens, of which only one is the correct token. An attacker cannot perform a offline bruteforce attack, as the token needs to be submitted to the server to check if it's the correct one (and we will lock the device after ~3 unsuccessful attempts).
When using the same mechanism to encrypt an RSA key (boils down to a prime number) using a PIN, we get 1'000'000 possible outcomes for a 6 digit PIN, only this time some outcomes can easily be ruled out as they are not prime.
A test showed that ~99.7% of those outcomes can be easily defined as prime, leaving us with about 0.3% of the possible outcomes which are probable prime. An attacker can now boil down the number of possible PINs quickly from one million to about 3'000.
- Is this a known problem (encrypting prime numbers), and is there a well known solution (couldn't find something useful on google).
- Should we forget about RSA keys and use ECC (elliptic curve) keys instead, and can an ECC private key be securely stored without discarding the wrong outcomes when decrypting with the wrong PIN?