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?
  • Would your scheme work if you used a MAC instead of a signature? (The key to the keyed hash can be random bits. Unlike the key to the public key (RSA) signature scheme.) – StackzOfZtuff Jun 20 '17 at 11:56
  • RSA keys are actually not usually prime numbers, even if the RSA cryptosystem makes use of the integer factorization problem for security. The private key traditionally contains the multiplicative modular inverse of the public exponent, modulo the least common multiple of each prime, minus one. For all intents and purposes, the RSA private key is just raw data. – forest Apr 7 '19 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.