Golang Cryptographic Shuffle

Question

I'm trying to implement a string shuffle function in Go that uses crypto/rand instead of math/rand. The Fisher-Yates Shuffle requires random integers so I've tried to implement that functionality, without having to use crypto/rand Int which relies on math/big. Below is the best I've come up with so far but is there a better method? The fact that I can't find existing examples leads me to wonder if there's a good reason why nobody does this!

package main

import "crypto/rand"
import "fmt"
import "encoding/binary"

func randomInt(max int) int {
    var n uint16
    binary.Read(rand.Reader, binary.LittleEndian, &n)
    return int(n) % max
}

func shuffle(s *[]string) {
        slice := *s
        for i := range slice {
                j := randomInt(i + 1)
                slice[i], slice[j] = slice[j], slice[i]
        }
        *s = slice
    }

func main() {
        slice := []string{"a", "b", "c", "d", "e", "f", "h", "i", "j", "k"}
        shuffle(&slice)
        fmt.Println(slice)
}

Jason Mooberry · Accepted Answer · 2016-02-04 19:21:23Z

9

Go's math/rand library has good facilities for producing random numerical primitives from a Source.

// A Source represents a source of uniformly-distributed 
// pseudo-random int64 values in the range [0, 1<<63).

type Source interface {
    Int63() int64
    Seed(seed int64)
}

NewSource(seed int64) returns the builtin, deterministic PRNG, but New(source Source) will allow anything that satisfies the Source interface.

Here is an example of a Source that is backed by crypto/rand.

type CryptoRandSource struct{}

func NewCryptoRandSource() CryptoRandSource {
    return CryptoRandSource{}
}

func (_ CryptoRandSource) Int63() int64 {
    var b [8]byte
    rand.Read(b[:])
    // mask off sign bit to ensure positive number
    return int64(binary.LittleEndian.Uint64(b[:]) & (1<<63 - 1))
}

func (_ CryptoRandSource) Seed(_ int64) {}

You can use it like this:

r := rand.New(NewCryptoRandSource())

for i := 0; i < 10; i++ {
    fmt.Println(r.Int())
}

The math/rand library has a properly implemented Intn() method which ensures a uniform distribution.

func (r *Rand) Intn(n int) int {
    if n <= 0 {
        panic("invalid argument to Intn")
    }
    if n <= 1<<31-1 {
        return int(r.Int31n(int32(n)))
    }
    return int(r.Int63n(int64(n)))
}

func (r *Rand) Int31n(n int32) int32 {
    if n <= 0 {
        panic("invalid argument to Int31n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int31() & (n - 1)
    }
    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    v := r.Int31()
    for v > max {
        v = r.Int31()
    }
    return v % n
}

func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int63() & (n - 1)
    }
    max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
    v := r.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}

Cryptographic hash functions also can be wrapped as a Source for alternate means of randomness.

edited Feb 4, 2016 at 19:21

answered Feb 4, 2016 at 18:20

Jason Mooberry

1063 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mr_Pink Over a year ago

I think you want int64(binary.LittleEndian.Uint64(b[:]) & (1<<63 - 1)) to ensure you have a positive number

Jason Mooberry Over a year ago

Good catch @JimB. Updated the example. Thanks.

Steve Crook Over a year ago

Thats nice, thanks. Worth adding that stackoverflow.com/questions/10408646/… explains how to import crypt/rand and math/rand.

Ferdinand Beyer Over a year ago

Instead of & (1<<63 - 1)), you also just shift right by one place: int64(binary.LittleEndian.Uint64(b[:]) >> 1)

peterSO · Accepted Answer · 2016-02-04 14:53:57Z

1

The numbers from n % max are not distributed uniformly. For example,

package main

import (
    "fmt"
    "math"
)

func main() {
    max := 7
    size := math.MaxUint8
    count := make([]int, size)
    for i := 0; i < size; i++ {
        count[i%max]++
    }
    fmt.Println(count[:max])
}

Output:

[37 37 37 36 36 36 36]

answered Feb 4, 2016 at 14:53

peterSO

168k32 gold badges305 silver badges294 bronze badges

Comments

Steve Crook · Accepted Answer · 2016-02-04 17:00:43Z

-1

Based on the comments received, I think I can improve on the example in my question by adding a uniformInt function, populating a uint32 instead of a uint16 and removing the pointer to the slice.

package main

import "crypto/rand"
import "fmt"
import "encoding/binary"

func randomInt() int {
        var n uint32
        binary.Read(rand.Reader, binary.LittleEndian, &n)
        return int(n)
}

func uniformInt(max int) (r int) {
        divisor := 4294967295 / max // Max Uint32
        for {
                r = randomInt() / divisor
                if r <= max {
                        break
                }
        }
        return
}

func shuffle(slice []string) {
        for i := range slice {
                j := uniformInt(i + 1)
                slice[i], slice[j] = slice[j], slice[i]
        }
}

func main() {
        slice := []string{"a", "b", "c", "d", "e", "f", "h", "i", "j", "k"}
        shuffle(slice)
        fmt.Println(slice)
}

answered Feb 4, 2016 at 17:00

Steve Crook

1,0553 gold badges14 silver badges24 bronze badges

1 Comment

Mr_Pink Over a year ago

Or you could just use the algorithm from Rand.Intn, Rand.Int31n and Rand.Int63n (or use math/rand with a crypto/rand source). Your uniformInt can return a negative value on systems with a 32 bit int, and I'm fairly certain your integer division adds some bias to the output, but I don't need worry about doing the math correctly if I take a known good algorithm.

Collectives™ on Stack Overflow

Golang Cryptographic Shuffle

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related