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.

I have thought up a method for generating random numbers between a client and a server which I hope is fair:

  • The client and server decide on a range in advance, $0$ trough $n-1$.

  • The server generates a $256$ bit random number $m$ (in the range $0$ to $\operatorname{floor}(\frac{2^{256} }{ n}) · n$) and hashes it with SHA-256 to give $m'$. $m'$ is then sent to the client.

  • The client generates a $256$ bit random number $o$ (as above) and sends it to the server.

  • The server can now calculate a fair random number $p = m + o \pmod n$.

  • The server sends $m$ and $p$ to the client.

  • The client can now check $\operatorname{SHA256}(m) = m'$ and $p = o + m \pmod n$.

Am I overlooking anything?

share|improve this question
    
I think technically the server only needs to send $p$ to the client, since $m$ can be derived (although as stated, the protocol could easily be extended to three or more collaborating parties) –  Stephen Touset Apr 25 '13 at 20:13
    
@StephenTouset, the original poster is correct that you need to send $m$ to the client. $p$ is a number in the range $0\ldots n-1$, so it only reveals the value of $m \bmod n$; it does not reveal the full value of $m$. Thus, you need to send the full $m$ as well. In practice, it is enough to send just $m$ (there is no need to send $p$ too, since the client can re-derive it), but that's probably not a big deal in practice. –  D.W. Apr 27 '13 at 19:41
    
When the client knows $n$, $o$, and $p$ I don't see how the client can't easily reconstruct $m$ when given $p\equiv m + o \pmod{n}$ and $m < n - 1$ –  Stephen Touset Apr 28 '13 at 2:42
add comment

1 Answer 1

up vote 5 down vote accepted

Yes, your scheme is fine.

Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$). Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).

This problem is known as secure coin flipping, and it has been studied in great depth before. For solutions and analysis, look at the following questions on this site:

share|improve this answer
    
In retrospect a salt seems much easier. Thanks. –  tm1rbrt Apr 25 '13 at 7:22
    
@DavidSchwartz Do you mean $m$? I'm not sure I follow. –  Stephen Touset Apr 25 '13 at 20:18
    
@DavidSchwartz, I think the original poster took care of this by choosing $m$ uniformly at random from between 0 and one less than a multiple of $n$. –  D.W. Apr 25 '13 at 20:52
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.