# Selecting a large NUMS Safe prime

Suppose I want to use the following simple hash function. For a mesage $m$, take some public $a$ and prime $p$ and raise $a^m \bmod p$ (never mind the computational expense of this operation).

This hash function is secure because the discrete log problem is hard, but only if $p-1$ has a large prime factor (to avoid being broken by index calculus). However, I figure if everyone's going to use the same $p$, I might as well choose $p$ so it's largest factor is as large as possible, in other words choose $p$ to be a Safe prime (meaning $\frac{(p-1)}{2}$ is also prime).

So how can I choose p to be a Safe prime, but also make it a Nothing-Up-My-Sleeve number for the purpose of constructing a good cryptographic hash protocol.

Then I'll choose $a$ to be the smallest generator $\bmod p$ (that's easy to check for Safe primes because all I need to do is find the smallest $a$ for which $legendre(a,p)=-1$).

Well, the obvious answer to 'how to find a Safe prime that is also a Nothing-Up-My-Sleeve' number would be to take one of the primes listed in RFC 3526. These primes (which come in several sizes) are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime. Having most of the bits within the modulus be from the binary expansion of $\pi$ would appear to satisfy the Nothing-Up-My-Sleeve property.
Also, I don't know if it is wise to pick a generator; after all, from the hash $a^m \bmod p$, the attacker can deduce the value $m \bmod 2$ if $a$ is a generator. It would seem more prudent to have $a$ be a quadratic residue (and with the RFC 3526, along with any safe prime that is $p \bmod 8 = 7$), $a=2$ is such a quadratic residue, as well as making the exponentiation operation slightly cheaper.
• I think that the condition for $i$ in RFC 3526 really is: $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime, and $2^{(p-1)/2}\bmod p=1$; with the later condition lacking in the answer.
• @fgrieu: the statements "$a=2$ is a quadratic residue" and "$2^{(p-1)/2} \bmod p = 1$" are equivalent (for $p$ prime); both are true if $p \equiv 7 \pmod 8$. Mar 25, 2020 at 17:34