README
¶
shuffle
This golang module should be used to produce a shuffled set using a Feistel network.
The algorithm has the following features:
- Performs the shuffle in a complete stateless form (ie.: there is no need for an input, even neither an out set), as you can traverse a channel with each of the output elements.
- It can run it safely in parallel which is not possible with algorithms that need to perform swap to elements of an array.
- It is keyed so you can provide a seed (in form of a Feistel function and round keys) to recall the shuffle order.
- It is random accessible so if you need very few shuffles elements of a large set you only ask those.
- It is reversible so given a shuffled value you can obtain the original unshuffled value.
Installation
go get github.com/vmunoz82/shuffle
Examples
To shuffle elements of the range [1000, 1020)
package main
import (
"github.com/vmunoz82/shuffle"
"fmt"
)
var keys = []shuffle.FeistelWord{
0xA45CF355C3B1CD88,
0x8B9271CC2FC9365A,
0x33CD458F23C816B1,
0xC026F9D152DE23A9}
/* Function for each round, could be anything don't need to be reversible */
func roundFunction(v, key shuffle.FeistelWord) shuffle.FeistelWord {
return (v * 941083987) ^ (key >> (v & 7) * 104729)
}
func main() {
s, _ := shuffle.Shuffle(1000, 1020, shuffle.NewFeistel(keys, roundFunction))
for v := range s {
fmt.Println(v)
}
}
This will output
1003
1005
1006
1009
1004
1011
1008
1016
1010
1001
1017
1000
1013
1012
1015
1014
1007
1002
1018
1019
In this example it will generate the first shuffled value for the range [0, 1000), that is the value 846, and next we made the inverse operation, given the value 846 asks for which element of the original set produce it.
package main
import (
"fmt"
"github.com/vmunoz82/shuffle"
)
var keys = []shuffle.FeistelWord{
0xA45CF355C3B1CD88,
0x8B9271CC2FC9365A,
0x33CD458F23C816B1,
0xC026F9D152DE23A9}
/* Function for each round, could be anything don't need to be reversible */
func roundFunction(v, key shuffle.FeistelWord) shuffle.FeistelWord {
return (v * 941083987) ^ (key >> (v & 7) * 104729)
}
func main() {
fn := shuffle.NewFeistel(keys, roundFunction)
v, _ := shuffle.RandomIndex(0, 1000, fn)
fmt.Println(v)
v, _ = shuffle.GetIndex(846, 1000, fn)
fmt.Println(v)
}
This example will output
846
0
Documentation
¶
Index ¶
Examples ¶
Constants ¶
const MaxFeistelWord = ^FeistelWord(0)
MaxFeistelWord is the maximum possible value of the FesitelWord type.
Variables ¶
This section is empty.
Functions ¶
func Shuffle ¶
func Shuffle(min, max FeistelWord, cipher *Feistel) (<-chan FeistelWord, error)
Shuffle creates a channel that stream shuffled values from a given minimum and maximum. If max is 0 then max act as the FesitelWord max value +1.
Example ¶
This example will output the shuffled set of range [1000, 1020)
s, _ := Shuffle(1000, 1020, NewFeistel(keys, roundFunction))
for v := range s {
fmt.Println(v)
}
Output: 1003 1005 1006 1009 1004 1011 1008 1016 1010 1001 1017 1000 1013 1012 1015 1014 1007 1002 1018 1019
Types ¶
type Feistel ¶
type Feistel struct {
// contains filtered or unexported fields
}
Feistel is where the state of Feistel network is stored, contains the keys to be applied on each round and a function of type FeistelFunc.
func NewFeistel ¶
func NewFeistel(keys []FeistelWord, f FeistelFunc) *Feistel
NewFeistel constructs a new Feistel context with the given keys and FeistelFunc.
func NewFeistelDefault ¶
func NewFeistelDefault(keys []FeistelWord) *Feistel
NewFeistelDefault constructs a new Feistel context with the given keys and using a default FeistelFunc.
func (*Feistel) Cipher ¶
func (f *Feistel) Cipher(left, right, mask FeistelWord) (FeistelWord, FeistelWord)
Cipher applys the Feistel cipher step to a word described in its left and right parts.
func (*Feistel) Decipher ¶
func (f *Feistel) Decipher(left, right, mask FeistelWord) (FeistelWord, FeistelWord)
Decipher applys the Fesitel decipher step to a word described in its left and right parts.
type FeistelFunc ¶
type FeistelFunc func(FeistelWord, FeistelWord) FeistelWord
A FeistelFunc is the type that define a function to be used in each round of the Feistel application.
type FeistelWord ¶
type FeistelWord uint64
A FeistelWord abstract the underlying unsigned type to represent a word in the Feistel context.
func GetIndex ¶
func GetIndex(permutation, max FeistelWord, cipher *Feistel) (FeistelWord, error)
GetIndex returns the unshuffled index of a given shuffle index and the higher bound of the shuffled set. If max is 0 then max act as the FesitelWord max value +1.
func RandomIndex ¶
func RandomIndex(idx, max FeistelWord, cipher *Feistel) (FeistelWord, error)
RandomIndex returns the shuffled index of a given index and the higher bound of the set to be shuffled. If max is 0 then max act as the FesitelWord max value +1.
Source Files