Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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