Ask HN: Are OTPs never prime?

#1

Post by shreshthmohan » Tue, Jun 09, 2015, 3:03 PM UTC

Indian banks use one-time password for two-factor authentication. Prashant (https://twitter.com/pacificleo/status/600132236730441728) is saying that he has never seen an OTP that is prime. Which makes him ask if this is intentional.

- Is this true? If yes, why?

PS: this is my first submission to HN. Thanks.

Re: Ask HN: Are OTPs never prime?

#2

Post by shreshthmohan » Tue, Jun 09, 2015, 3:05 PM UTC

I think that this is just probability in play. OTPs are usually 4 or 6 digits. Probability of seeing a prime number is little because of prime number theorem. I might be wrong though.

Re: Ask HN: Are OTPs never prime?

#3

Post by kylc » Tue, Jun 09, 2015, 5:26 PM UTC

shreshthmohan wrote: post #2

I think that this is just probability in play. OTPs are usually 4 or 6 digits. Probability of seeing a prime number is little because of prime number theorem. I might be wrong though.

Some digging reveals that a common method for generating OTPs is through repeated hash function applications. A good hash function should produce uniformly distributed outputs.

There are 78,498 primes less than 10^6 (so, primes less than 6 digits), meaning that there is about a 7.9% chance of independently seeing a prime OTP if the OTPs are uniformly distributed. That seems pretty high. The expected value for seeing a prime OTP after multiple trials is just 15.

So I wonder if your friend is just unlucky or if his OTP provider is using another method for OTP generation.