# Hash to prime numbers?

Is there some provably secure hash function to prime numbers?
Say, a function $$H: \{0, 1\}^* \rightarrow \{e: e \in \{0, 1\}^\lambda \land e$$ is prime$$\}$$

I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).

• Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^{128}$ or $2^{512}$ or ... prime numbers. and, link to free version of the article? – kelalaka Oct 10 '18 at 11:37
• Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice? – SEJPM Oct 10 '18 at 12:59
• What's not fulfilled by taking a standard hash $H'$ with $\lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved. – fgrieu Oct 10 '18 at 13:02
• @fgrieu In general I can construct collision resistant hah functions where it's easy to find inputs that map to "close" images, say differing only in the least significant bit. Those would trivially lead to collisions with high probability in your approach. (It might be fine assuming a random oracle, but it's definitely not assuming collision resistance.) – Maeher Oct 10 '18 at 17:51

You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).

The usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.

Generally the method of generating the prime value is available separately in math or crypto libraries that come with the runtime. For instance, Java has the BigInteger(int bitLength, int certainty, Random rnd) constructor.

Beware that the time it takes to find a prime is unknown in advance. The generation may take a long time (and in the case of Java may also take a ridiculous number of bytes from the DRBG - just tested this).

• Note : java isProbablePrime(int certainty): may return composite number. The AKS algorithm may needed – kelalaka Oct 10 '18 at 20:03
• @Maarten_Bodewes I feel like the consequtive hash values will find the same prime number due to the prime number gap. Could you elobarate this point? – kelalaka Oct 10 '18 at 20:07
• Generally a difference in seed to a PRNG will result in a completely different random stream. So I'm not sure what you mean with comment #2. As for comment #1, yes, the Java example uses Rabin-Miller and Lucas-Lehmer to test if a number probable prime. If a more conclusive test is needed for a specific problem then a different test method should be used. – Maarten Bodewes Oct 10 '18 at 21:02
• Ah, hash -> CSPRNG -> prime number generator. Ok. thanks. – kelalaka Oct 10 '18 at 21:07
• Note that Java does a non-strong Lucas test, not a Lucas-Lehmer test. The code comments and internal function names have been wrong since at least 2002, though this doesn't impact the results. [The Lucas test as noted in the 1980 BPSW papers is a different test than the Lucas-Lehmer test which only applies to Mersenne numbers] – DanaJ Oct 12 '18 at 0:36

I think what makes this difficult is the definition of "secure." Clearly $$H(m)=2$$ always outputs a prime number, but it is not considered secure.

For it to be "secure," one would expect every prime number to have an equal probability of being chosen, given a random input. Since you can enumerate the prime numbers below a certain value, the problem is isomorphic to a "normal" hash which generates an integer from 0..$$\pi(2^\lambda)$$ where $$\pi$$ is a function which counts the number of primes up to a certain value. If you can demonstrate that your normal hash generates unpredictable results with a uniform distribution, then your proof is complete.

However, finding a function for the first $$\pi(2^\lambda)$$ primes is tricky, especially if $$\lambda$$ is large.

Potentially of interest is a paper by Jones, Sato, Wada, and Weins from 1976. In it, they produced a fascinating polynomial of degree 25 in 26 variables which yields a prime number, 1, or a negative number for all non-negative integers. Interestingly, it also generates every prime number, so it is guaranteed to contain all $$\pi(2^\lambda)$$ primes you want.

Of course, that is a 26 variable function, and it makes no guarantees about repeating prime numbers in a non-uniform distribution. But you could in theory find a loop through these numbers which generates every prime number you want. If you could do some massaging to get it into the form of a cyclic group, you could rapidly index through it and generate such numbers efficiently.

However, I do believe that, even if creating such a cyclic group is possible, it would likely require an amount of initial effort proportional to $$\pi(2^\lambda)$$ at the least. The result might be nice and compact, but generating it would be abysmal.

Generating prime numbers by an equation is fascinatingly difficult. While there is, in theory, a polynomial time solution to your problem, it's not clear how to efficiently determine what that is.

• The equation by Jones, Sato, Wada, and Weins, while interesting from a theoretic point of view, is unusable to the problem for searching for prime numbers, as almost all input variable settings will result in a negative number – poncho Oct 10 '18 at 21:06
• @poncho True. The challenge would be finding a loop through it which doesn't have negative numbers. I do think the reality is that this isn't a practical task, but what I liked about those equations is they at least showed that, in theory, some of these issues are bounded by polynomials. – Cort Ammon Oct 10 '18 at 23:32
• I'm very interested whether this diophantine representation was ever used actually. Maybe I should fork a separate question for this. Idea is having a witness in the form of two 26-tuples for an RSA modulus, that could be proven. – Vadym Fedyukovych Oct 13 '18 at 17:04

Another (naive) solution:

Take you favourite (cryptographic) hash function $$H$$. For an element $$x \in \{0,1\}^*$$, define $$H'(x)$$ as the first prime number in the $$H$$-orbit of $$x$$. That is,

\begin{align*} & n_x := \min \{n:\ H^{(n)}(x) \text{ is prime} \} ; \\ & H' (x) := H^{(n_x)}(x), \end{align*} where $$H^{(n)}(x)$$ is the $$n$$-fold iteration $$(H\circ ... \circ H)(x)$$. The function $$H'$$ is collision and pre-image resistant assuming $$H$$ is, and it attains prime values. However, it is not very efficiently computable.

Runtime analysis (in the random oracle model): by the Prime number theorem, the expectation of $$n_x$$ (regardless of x) is the number of bits. That is, if you are using SHA-256, then in expectation it would take you 256 guesses to find a prime number. To check primality, you can use the probabilistic Miller-Rabin that runs in $$\log^2(x)$$, or the deterministic AKS algorithm that (conjecturely) runs in $$\log^6(x)$$.

• Note that your runtime analysis is only for the expected runtime in the ROM. As soon as the function is fixed ( whether as an efficiently computable function or by the random choice of a function) your hash function is not only not guaranteed to run in polynomial time but may in fact not terminate at all for some or all inputs. – Maeher Jan 3 at 13:20
• True, although (again, in the ROM), the number of attempts until hitting a prime is distributed geometrically, and while it will not terminate for sure, it will terminate with probability 1. – Chipotle Jan 3 at 15:02
• No, it will not terminate with probability 1. $H$ has a fixed length output say $H : \{0,1\}^* \to \{0,1\}^\lambda$. For an unfortunate choice of $H$ (which will happen with small but non-zero probability) the function $H$ restricted to the domain $\{0,1\}^*$ could only map to non-primes. For any such function there will be a large number of inputs such that $H^{(n)}$ will not terminate with high probability. – Maeher Jan 3 at 15:08
• If the $H$-orbit of some element $x$ keeps missing a set of positive measure, wouldn't that contradict the definition of a random oracle assumption? – Chipotle Jan 3 at 15:16

This answer updated since new foundings

Let $$H$$ be a (provably) secure hash function $$H:\{0,1\}^* \rightarrow \{2^h\}$$, where $$h$$ is the output size of the $$H$$.

Now, using this $$H$$, we will construct a (provably) secure hash function to primes $$H'$$ as follows;

• let $$P$$ be Oracle of Mathematica Prime[n] function.
• given message $$m$$ output;

$$H'(m) := \text{Prime}[H(m)]$$

Since this is just a bijection, $$H'$$ is a (provably) secure hash function.

Note: I looked for the theory of this Prime[n] function but couldn't. The Mathematica find the $$n-th$$ prime very quickly. Try $$\text{Prime}[2^{512}]$$ at WolframAlpha.

• One may want to note that this is ver much unpractical because of the list of size $2^{h}$ especially if $h$ should have cryptographically interesting values such as $h=256$. – SEJPM Oct 10 '18 at 12:37
• @SEJPM Exactly, – kelalaka Oct 10 '18 at 12:38
• This answer assumes you can find a provably secure hash function. Nobody have found such a hash function yet. – kasperd Oct 10 '18 at 16:36
• @kasperd, I wrote as if you gave me one, I can convert it. Martin solved my solution's weak point. – kelalaka Oct 10 '18 at 19:16
• It seems Mathematica's Prime[n] function stops giving exact results around 310e9. Using primecount or Perl/ntheory one can go significantly farther, but still nowhere near far enough, and 2^512 is completely infeasible. For the methods used, see for example math.stackexchange.com/a/775314/117584. The method used by the two mentioned packages is as described there: get a good estimate, get an exact prime count, then sieve the relatively small difference. One could iterate the process but our initial estimate is pretty good and sieving is pretty fast. – DanaJ Oct 12 '18 at 0:19

Relatively prime polynomials are as good as prime numbers sometimes*. In such a case, $$(1 + ex) \in Z[X]$$ are prime for just different $$e$$ produced with the hash function (collision resistance).

[*] Set equality testing is an obvious example: just compare two products of polynomials accumulating set elements. Efficient polynomial equality test is crucial, resulting in a nice proof of having a solution to specific sudoku puzzle. Polynomial graph representation and isomorphism testing is another example.