Golang IP sequence Cyclic Generator

cyclicIterator.go

package cyclic

import (
	"math/big"
  "math/rand"
	//srand "crypto/rand"
)

// Go implementation of ZMap's ip calculation sharding algorithm 
//used to pseudo-randomize an IP address space without performing 
// a precalculation of all IPs and making sure that every IP is 
// returned exactly once.

// Provides an inexpensive approach to iterating over the IPv4 address
// space in a random(-ish) manner such that we connect to every host once in
// a scan execution without having to keep track of the IPs that have been
// scanned or need to be scanned and such that each scan has a different
// ordering. We accomplish this by utilizing a cyclic multiplicative group
// of integers modulo a prime and generating a new primitive root (generator)
// for each scan.

// We know that 3 is a generator of (Z mod 2^32 + 15 - {0}, *)
// and that we have coverage over the entire address space because 2**32 + 15
// is prime and ||(Z mod PRIME - {0}, *)|| == PRIME - 1. Therefore, we
// just need to find a new generator (primitive root) of the cyclic group for
// each scan that we perform.
 
// Because generators map to generators over an isomorphism, we can efficiently
// find random primitive roots of our mult. group by finding random generators
// of the group (Zp-1, +) which is isomorphic to (Zp*, *). Specifically the
// generators of (Zp-1, +) are { s | (s, p-1) == 1 } which implies that
// the generators of (Zp*, *) are { d^s | (s, p-1) == 1 }. where d is a known
// generator of the multiplicative group. We efficiently find
// generators of the additive group by precalculating the psub1_f of
// p - 1 and randomly checking random numbers against the psub1_f until
// we find one that is coprime and map it into Zp*. Because
// totient(totient(p)) ~= 10^9, this should take relatively few
// iterations to find a new generator.

type cyclicGroup struct {
	prime             uint64
	knownPrimitiveRoot uint64
	primeFactors    []uint64
	numPrimeFactors   uint64
}

type cycle struct {
	group     *cyclicGroup
	generator uint64
	order     uint64
	offset    uint32
}

// We will pick the first cyclic group from this list that is
// larger than the number of IPs in our whitelist. E.g. for an
// entire Internet scan, this would be cyclic32
// Note: this list should remain ordered by size (primes) ascending.
var cyclicGroups [5]cyclicGroup
func init() {
	cyclicGroups = [5]cyclicGroup {
		{257, 3, []uint64{2}, 1},                           // 2^8 + 1
		{65537, 3, []uint64{2}, 1},                         // 2^16 + 1
		{16777259, 2, []uint64{2, 23, 103, 3541}, 4},       // 2^24 + 43
		{268435459, 2, []uint64{2, 3, 19, 87211}, 4},       // 2^28 + 3
		{4294967311, 3, []uint64{2, 3, 5, 131, 364289}, 5}} // 2^32 + 15
}

// Check whether an integer is coprime with (p - 1)
func isCoprime(check uint64, group *cyclicGroup) bool {
	for i := uint64(0); i < group.numPrimeFactors; i++ {
		if (group.primeFactors[i] > check) &&
			(group.primeFactors[i]%check == 0) {
			return false
		} else if (group.primeFactors[i] < check) &&
			(check%group.primeFactors[i] == 0) {
			return false
		} else if group.primeFactors[i] == check {
			return false
		}
	}
	return true
}

// Return a (random) number coprime with (p - 1) of the group,
// which is a generator of the additive group mod (p - 1)
func findPrimitiveRoot(group *cyclicGroup, seed int64) uint32 {
	rand.Seed(seed)
	candidate := (rand.Uint64() & 0xFFFFFFFF) % group.prime
	if candidate == 0 {
		candidate++
	}
	for isCoprime(candidate, group) != true {
		candidate++
		if candidate >= group.prime {
			candidate = 1
		}
	}
	return uint32(isomorphism(candidate, group))
}

func isomorphism(additiveElt uint64, multGroup *cyclicGroup) uint64 {
	if !(additiveElt < multGroup.prime) {
		panic("Assertion failed")
	}
	var base, power, prime, primroot big.Int
	base.SetUint64(multGroup.knownPrimitiveRoot)
	power.SetUint64(additiveElt)
	prime.SetUint64(multGroup.prime)
	primroot.Exp(&base, &power, &prime)
	return primroot.Uint64()
}

func getGroup(minSize uint64) *cyclicGroup {
	for i := 0; i < len(cyclicGroups); i++ {
		if cyclicGroups[i].prime > minSize {
			return &cyclicGroups[i]
		}
	}
	panic("No cyclic group found with prime large enough. This is impossible.")
}

func makeCycle(group *cyclicGroup, seed int64) cycle {
	generator := findPrimitiveRoot(group, seed)
	offset := (rand.Uint64() & 0xFFFFFFFF) % group.prime
	return cycle{group, uint64(generator), group.prime - 1, uint32(offset)}
}

func first(c *cycle) uint64 {
	var generator, exponentBegin, prime, start big.Int
	generator.SetUint64(c.generator)
	prime.SetUint64(c.group.prime)
	exponentBegin.SetUint64(c.order)
	start.Exp(&generator, &exponentBegin, &prime)
	return start.Uint64()
}

func next(c *cycle, current *uint64) {
	*current = (*current * c.generator) % c.group.prime
}