2
$\begingroup$

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$).

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 25, 2020 at 17:09
  • $\begingroup$ @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$. $\endgroup$
    – poncho
    Mar 25, 2020 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.