common

Documentation

Index

• Constants
• Variables
• func Close(o io.Closer)
• func Crt(a *big.Int, pa *big.Int, b *big.Int, pb *big.Int) *big.Int
• func Decompose(r int64) (int64, int64)
• func FastRandomBigInt(limit *big.Int) *big.Int
• func GetHashNumber(a *big.Int, b *big.Int, index int, bitlen uint) *big.Int
• func H(msg []byte, length int) []byte
• func HashCommit(values []*big.Int, issig bool) *big.Int
• func IntHashSha256(input []byte) *big.Int
• func LegendreSymbol(a, p *big.Int) int
• func Max(a, b int) int
• func Min(a, b int) int
• func ModInverse(a, n *big.Int) (ia *big.Int, ok bool)
• func ModPow(x, y, m *big.Int) (*big.Int, error)
• func ModSqrt(a *big.Int, factors []*big.Int) (*big.Int, bool)
• func PackFes(fes []int64) []byte
• func PackFesInt(fes []int) []byte
• func PrimeSqrt(a *big.Int, pa *big.Int) (*big.Int, bool)
• func RandomBigInt(numBits uint) (*big.Int, error)
• func RandomPrimeInRange(rand io.Reader, start, length uint) (p *big.Int, err error)
• func RandomQR(n *big.Int) *big.Int
• func RepresentToBases(bases, exps []*big.Int, modulus *big.Int, maxMessageLength uint) *big.Int
• func SumFourSquares(n *big.Int) (*big.Int, *big.Int, *big.Int, *big.Int)
• func UnpackFes(bs []byte, Q int64) []int64
• func UnpackFes22Bit(bs []byte) []int
• func UnpackFesInt(bs []byte, Q int) []int
• func UnpackFesLoose(bs []byte) []int
• func XOF128(seed []byte, nonce int) *bytes.Reader
• func XOF256(seed []byte, nonce int) *bytes.Reader
• type CPRNG
  • func NewCPRNG(seed *[32]byte) (*CPRNG, error)
  • func (c *CPRNG) Read(buf []byte) (n int, err error)
• type FastMod
  • func (m *FastMod) Mod(ret, x *big.Int) *big.Int
  • func (m *FastMod) Set(p *big.Int)

Constants

const ETA = 2

const GAMMA1 = 131072

const GAMMA2 = 65536

const INV2 = 3670017

const K = 4

const L = 4

const N = 256

const POLY_LE_GAMMA1_SIZE = 576

const Q = 7340033

Variables

var ErrNoModInverse = errors.New("modular inverse does not exist")

var INVZETAS = []int64{} /* 256 elements not displayed */

var SmallPrimes = []uint8{
	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
}

SmallPrimes is a list of small prime numbers that allows us to rapidly exclude some fraction of composite candidates when searching for a random prime. This list is truncated at the point where SmallPrimesProduct exceeds a uint64. It does not include two because we ensure that the candidates are odd by construction.

var SmallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)

SmallPrimesProduct is the product of the values in SmallPrimes and allows us to reduce a candidate prime by this number and then determine whether it's coprime with all the elements of SmallPrimes without further big.Int operations.

var ZETAS = []int64{} /* 256 elements not displayed */

Functions

func Close

func Close(o io.Closer)

Close is a helper function for absorbing errors in the `defer x.Close()` pattern

func Crt

func Crt(a *big.Int, pa *big.Int, b *big.Int, pb *big.Int) *big.Int

Crt finds a number x (mod pa*pb) such that x = a (mod pa) and x = b (mod pb)

func Decompose

func Decompose(r int64) (int64, int64)

func FastRandomBigInt

func FastRandomBigInt(limit *big.Int) *big.Int

FastRandomBigInt derives a random number uniformly chosen below the given limit from a random 256 bit seed generated when the application starts.

func GetHashNumber

func GetHashNumber(a *big.Int, b *big.Int, index int, bitlen uint) *big.Int

GetHashNumber uses a hash to generate random numbers of a given bit-length in the fiat-shamir heuristic

func H

func H(msg []byte, length int) []byte

func HashCommit

func HashCommit(values []*big.Int, issig bool) *big.Int

HashCommit computes the sha256 hash over the asn1 representation of a slice of big integers and returns a positive big integer that can be represented with that hash.

func IntHashSha256

func IntHashSha256(input []byte) *big.Int

IntHashSha256 is a utility function which computes the sha256 hash over a byte array and returns this hash as a big.Int.

func LegendreSymbol

func LegendreSymbol(a, p *big.Int) int

LegendreSymbol calculates the Legendre symbol (a/p).

func Max

func Max(a, b int) int

Helper functions

func Min

func Min(a, b int) int

func ModInverse

func ModInverse(a, n *big.Int) (ia *big.Int, ok bool)

ModInverse returns ia, the inverse of a in the multiplicative group of prime order n. It requires that a be a member of the group (i.e. less than n). This function was taken from Go's RSA implementation

func ModPow

func ModPow(x, y, m *big.Int) (*big.Int, error)

ModPow computes x^y mod m. The exponent (y) can be negative, in which case it uses the modular inverse to compute the result (in contrast to Go's Exp function).

func ModSqrt

func ModSqrt(a *big.Int, factors []*big.Int) (*big.Int, bool)

ModSqrt calculates Sqrt modulo a number with given prime factors. Also allows 4 as a factor All factors should be relatively prime to each other!

func PackFes

func PackFes(fes []int64) []byte

func PackFesInt

func PackFesInt(fes []int) []byte

packFes packs a slice of integers into a byte array TODO Ugly, code redundancy...

func PrimeSqrt

func PrimeSqrt(a *big.Int, pa *big.Int) (*big.Int, bool)

PrimeSqrt calculates sqrt modulo a prime

func RandomBigInt

func RandomBigInt(numBits uint) (*big.Int, error)

RandomBigInt returns a random big integer value in the range [0,(2^numBits)-1], inclusive.

func RandomPrimeInRange

func RandomPrimeInRange(rand io.Reader, start, length uint) (p *big.Int, err error)

RandomPrimeInRange returns a random probable prime in the range [2^start, 2^start + 2^length] This code is an adaption of Go's own Prime function in rand/util.go

func RandomQR

func RandomQR(n *big.Int) *big.Int

func RepresentToBases

func RepresentToBases(bases, exps []*big.Int, modulus *big.Int, maxMessageLength uint) *big.Int

RepresentToBases returns a representation of the given exponents in terms of the R bases from the public key. For example given exponents exps[1],...,exps[k] this function returns

R[1]^{exps[1]}*...*R[k]^{exps[k]} (mod N)

with R and N coming from the public key. The exponents are hashed if their length exceeds the maximum message length from the public key.

func SumFourSquares

func SumFourSquares(n *big.Int) (*big.Int, *big.Int, *big.Int, *big.Int)

SumFourSquares expresses a number as sum of four squares algorithm from "Randomized algorithms in number theory" by M. Rabin and J. Shallit

func UnpackFes

func UnpackFes(bs []byte, Q int64) []int64

unpackFes unpacks a byte array into a slice of integers

func UnpackFes22Bit

func UnpackFes22Bit(bs []byte) []int

func UnpackFesInt

func UnpackFesInt(bs []byte, Q int) []int

TODO meh

func UnpackFesLoose

func UnpackFesLoose(bs []byte) []int

unpackFesLoose processes the byte slice `bs` by adding 1 to each byte and combining pairs into integers.

func XOF128

func XOF128(seed []byte, nonce int) *bytes.Reader

func XOF256

func XOF256(seed []byte, nonce int) *bytes.Reader

Types

type CPRNG

type CPRNG struct {
	// contains filtered or unexported fields
}

CPRNG is a simple thread-safe cryptographically secure pseudo-random number generator. Implemented with AES in counter mode with the seed as key and an atomic uint64 as counter.

func NewCPRNG

func NewCPRNG(seed *[32]byte) (*CPRNG, error)

func (*CPRNG) Read

func (c *CPRNG) Read(buf []byte) (n int, err error)

type FastMod

type FastMod struct {
	// contains filtered or unexported fields
}

func (*FastMod) Mod

func (m *FastMod) Mod(ret, x *big.Int) *big.Int

func (*FastMod) Set

func (m *FastMod) Set(p *big.Int)