code review 35870043: crypto/rand: it's an error for bits < 6 in Prime()

crypto/rand: support generation of 2-5 bit primes, also document the error return for Prime
Fixes issue 6849.
Fixes issue 6867.

[minux1, 2013-12-02 06:55:37]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[minux1, 2013-12-02 07:00:24]

https://codereview.appspot.com/35870043/diff/40001/src/pkg/crypto/rand/util.go
File src/pkg/crypto/rand/util.go (right):

https://codereview.appspot.com/35870043/diff/40001/src/pkg/crypto/rand/util.g...
src/pkg/crypto/rand/util.go:32: if bits < 1 {
alternatively, we can modify this condition to be
  if bits < 6
and modify the error message accordingly.

(actually, I like this alternative better than adding documentation)

https://codereview.appspot.com/35870043/diff/40001/src/pkg/crypto/rand/util.g...
src/pkg/crypto/rand/util.go:33: err = errors.New("crypto/rand: prime size must
be positive")
why not return here?

[minux1, 2013-12-02 07:05:31]

PTAL. Switched to the error approach.

[agl1, 2013-12-02 18:43:25]

LGTM

[minux1, 2013-12-02 18:48:08]

On 2013/12/02 07:05:31, minux wrote:
> PTAL. Switched to the error approach.
Yet another fix is to allow generation of 2-5 bits primes, also a trivial fix:
diff -r 7326da92ff4d src/pkg/crypto/rand/util.go
--- a/src/pkg/crypto/rand/util.go	Mon Dec 02 09:06:41 2013 +1100
+++ b/src/pkg/crypto/rand/util.go	Mon Dec 02 13:43:09 2013 -0500
@@ -79,7 +81,7 @@
 		for delta := uint64(0); delta < 1<<20; delta += 2 {
 			m := mod + delta
 			for _, prime := range smallPrimes {
-				if m%uint64(prime) == 0 {
+				if m%uint64(prime) == 0 && (bits >= 6 || uint64(prime) != m) {
 					continue NextDelta
 				}
 			}


If we choose to go this route, we need to add new tests.
However, I think generation of 2-5 bits prime is not that important for
crypto/rand.

[agl1, 2013-12-02 18:52:52]

On 2013/12/02 18:48:08, minux wrote:
> If we choose to go this route, we need to add new tests.
> However, I think generation of 2-5 bits prime is not that important for
> crypto/rand.

Ah, I see. On second thoughts, I might weakly prefer fixing the generation
rather than rejecting the parameter.

[minux1, 2013-12-02 19:10:42]

On Mon, Dec 2, 2013 at 1:52 PM, <agl@golang.org> wrote:

> On 2013/12/02 18:48:08, minux wrote:
>
>> If we choose to go this route, we need to add new tests.
>> However, I think generation of 2-5 bits prime is not that important
>>
> for
>
>> crypto/rand.
>>
>
> Ah, I see. On second thoughts, I might weakly prefer fixing the
> generation rather than rejecting the parameter.
>
OK, I will update the patch with a fix to the generation problem
(and make bits < 2 to be an error), along with tests.

[minux1, 2013-12-02 19:39:52]

PTAL.

[minux1, 2013-12-02 19:42:02]

Note: generation of 2-5 bit prime is biased, because we insist that top 2-bit
are set for each one.

[agl1, 2013-12-03 15:37:27]

LGTM

https://codereview.appspot.com/35870043/diff/140001/src/pkg/crypto/rand/util_...
File src/pkg/crypto/rand/util_test.go (right):

https://codereview.appspot.com/35870043/diff/140001/src/pkg/crypto/rand/util_...
src/pkg/crypto/rand/util_test.go:22: if !p.ProbablyPrime(100) {
s/100/32/ should be fine. (False positive probability of 2^-128.)

[minux1, 2013-12-10 04:25:53]

*** Submitted as https://code.google.com/p/go/source/detail?r=ec7c0e25938c ***

crypto/rand: support generation of 2-5 bit primes, also document the error
return for Prime
Fixes issue 6849.
Fixes issue 6867.

R=golang-dev, agl
CC=golang-dev
https://codereview.appspot.com/35870043