Golang big.Int类(方法)实例源码

// Precompute performs some calculations that speed up private key operations
// in the future.
func (priv *PrivateKey) Precompute() {
	if priv.Precomputed.Dp != nil {
		return
	}

	priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
	priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)

	priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
	priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)

	priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])

	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
	priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
	for i := 2; i < len(priv.Primes); i++ {
		prime := priv.Primes[i]
		values := &priv.Precomputed.CRTValues[i-2]

		values.Exp = new(big.Int).Sub(prime, bigOne)
		values.Exp.Mod(priv.D, values.Exp)

		values.R = new(big.Int).Set(r)
		values.Coeff = new(big.Int).ModInverse(r, prime)

		r.Mul(r, prime)
	}
}

// number = int_lit [ "p" int_lit ] .
//
func (p *gcParser) parseNumber() Const {
	// mantissa
	sign, val := p.parseInt()
	mant, ok := new(big.Int).SetString(sign+val, 10)
	assert(ok)

	if p.lit == "p" {
		// exponent (base 2)
		p.next()
		sign, val = p.parseInt()
		exp, err := strconv.Atoui(val)
		if err != nil {
			p.error(err)
		}
		if sign == "-" {
			denom := big.NewInt(1)
			denom.Lsh(denom, exp)
			return Const{new(big.Rat).SetFrac(mant, denom)}
		}
		if exp > 0 {
			mant.Lsh(mant, exp)
		}
		return Const{new(big.Rat).SetInt(mant)}
	}

	return Const{mant}
}

func bitwise_arithmetic_shift_left(x, y Obj) Obj {
	xfx := (uintptr(unsafe.Pointer(x)) & fixnum_mask) == fixnum_tag
	yfx := (uintptr(unsafe.Pointer(y)) & fixnum_mask) == fixnum_tag
	if !yfx {
		panic("bad shift amount")
	}
	amount := uint(uintptr(unsafe.Pointer(y)) >> fixnum_shift)
	if xfx && amount < 32-fixnum_shift {
		i := int64(int(uintptr(unsafe.Pointer(x)) >> fixnum_shift))
		r := i << amount
		if r >= int64(fixnum_min) && r <= int64(fixnum_max) {
			return Obj(unsafe.Pointer(uintptr((r << fixnum_shift) | fixnum_tag)))
		} else {
			return wrap(big.NewInt(r))
		}
	} else if xfx {
		x = wrap(big.NewInt(int64(fixnum_to_int(x))))
	} else if (uintptr(unsafe.Pointer(x)) & heap_mask) != heap_tag {
		panic("bad type")
	}

	switch vx := (*x).(type) {
	case *big.Int:
		var z *big.Int = big.NewInt(0)
		return wrap(z.Lsh(vx, amount))
	}
	panic("bad type")
}

// TODO: handle flonums, compnums, ratnums, etc
func _string_to_number(_str Obj, _radix Obj) Obj {
	if is_immediate(_str) {
		panic("bad type")
	}
	str := string((*_str).([]int))

	radix := number_to_int(_radix)
	switch {
	case strings.HasPrefix(str, "#b"):
		radix = 2
		str = str[2:]
	case strings.HasPrefix(str, "#o"):
		radix = 8
		str = str[2:]
	case strings.HasPrefix(str, "#d"):
		radix = 10
		str = str[2:]
	case strings.HasPrefix(str, "#x"):
		radix = 16
		str = str[2:]
	}

	var v big.Int
	z, s := v.SetString(str, radix)
	if !s {
		return False
	}
	if z.Cmp(fixnum_max_Int) < 1 && z.Cmp(fixnum_min_Int) > -1 {
		return Make_fixnum(int(z.Int64()))
	}
	return wrap(z)
}

// Zjisti a0, b0, z tak aby: a0*x + b0*y = z (mod n)
func Euklid(x, y, n *big.Int) (a0, b0, z *big.Int) {
	a0 = big1
	a := big0
	b0 = big0
	b := big1
	g := new(big.Int)
	t := new(big.Int) // tmp

	if x.Cmp(y) < 0 {
		x, y = y, x
		a0, a, b0, b = b0, b, a0, a
	}

	for {
		z = y
		_, y = g.Div(x, y)
		x = z

		a0, a = a, _Euklid_sub(a0, t.Mul(a, g), n)
		b0, b = b, _Euklid_sub(b0, t.Mul(b, g), n)

		if y.Cmp(big0) == 0 {
			break
		}
	}
	return
}

func bitwise_and(x, y Obj) Obj {
	xfx := (uintptr(unsafe.Pointer(x)) & fixnum_mask) == fixnum_tag
	yfx := (uintptr(unsafe.Pointer(y)) & fixnum_mask) == fixnum_tag
	if xfx && yfx {
		i1 := uintptr(unsafe.Pointer(x))
		i2 := uintptr(unsafe.Pointer(y))
		return Obj(unsafe.Pointer(uintptr(i1 & i2)))
	}

	if (!xfx && (uintptr(unsafe.Pointer(x))&heap_mask) != heap_tag) ||
		(!yfx && (uintptr(unsafe.Pointer(y))&heap_mask) != heap_tag) {
		panic("bad type")
	}

	if xfx {
		return bitwise_and(y, x)
	}

	switch vx := (*x).(type) {
	case *big.Int:
		var z *big.Int = big.NewInt(0)
		if yfx {
			vy := big.NewInt(int64(fixnum_to_int(y)))
			return wrap(z.And(vx, vy))
		}
		switch vy := (*y).(type) {
		case *big.Int:
			return wrap(z.And(vx, vy))
		default:
			panic("bad type")
		}
	}
	panic("bad type")
}

/* Returns the appropriate base-two padded
bytes (assuming the underlying big representation
remains b2c) */
func BigBytes(i *big.Int) (buff []byte) {
	ib := i.Bytes()
	shift := 0
	shiftbyte := byte(0)
	switch i.Cmp(big.NewInt(0)) {
	case 1:
		// Positive must be padded if high-bit is 1
		if ib[0]&0x80 == 0x80 {
			shift = 1
		}
	case -1:
		// Negative numbers with a leading high-bit will also need
		// to be padded, but with a single bit tagging its 'negativity'
		if ib[0]&0x80 == 0x80 {
			shift = 1
			shiftbyte = 0x80

		}
	}
	buff = make([]byte, len(ib)+shift)
	if shift == 1 {
		buff[0] = shiftbyte
	}
	copy(buff[shift:], ib)

	return
}

// EncryptOAEP encrypts the given message with RSA-OAEP.
// The message must be no longer than the length of the public modulus less
// twice the hash length plus 2.
func EncryptOAEP(hash hash.Hash, rand io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err os.Error) {
	hash.Reset()
	k := (pub.N.Len() + 7) / 8
	if len(msg) > k-2*hash.Size()-2 {
		err = MessageTooLongError{}
		return
	}

	hash.Write(label)
	lHash := hash.Sum()
	hash.Reset()

	em := make([]byte, k)
	seed := em[1 : 1+hash.Size()]
	db := em[1+hash.Size():]

	copy(db[0:hash.Size()], lHash)
	db[len(db)-len(msg)-1] = 1
	copy(db[len(db)-len(msg):], msg)

	_, err = io.ReadFull(rand, seed)
	if err != nil {
		return
	}

	mgf1XOR(db, hash, seed)
	mgf1XOR(seed, hash, db)

	m := new(big.Int)
	m.SetBytes(em)
	c := encrypt(new(big.Int), pub, m)
	out = c.Bytes()
	return
}

// Int returns a uniform random value in [0, max).
func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
	k := (max.BitLen() + 7) / 8

	// b is the number of bits in the most significant byte of max.
	b := uint(max.BitLen() % 8)
	if b == 0 {
		b = 8
	}

	bytes := make([]byte, k)
	n = new(big.Int)

	for {
		_, err = io.ReadFull(rand, bytes)
		if err != nil {
			return nil, err
		}

		// Clear bits in the first byte to increase the probability
		// that the candidate is < max.
		bytes[0] &= uint8(int(1<<b) - 1)

		n.SetBytes(bytes)
		if n.Cmp(max) < 0 {
			return
		}
	}

	return
}

// randomSafePrime returns a number, p, of the given size, such that p and
// (p-1)/2 are both prime with high probability.
func randomSafePrime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
	if bits < 1 {
		err = os.EINVAL
	}

	bytes := make([]byte, (bits+7)/8)
	p = new(big.Int)
	p2 := new(big.Int)

	for {
		_, err = io.ReadFull(rand, bytes)
		if err != nil {
			return
		}

		// Don't let the value be too small.
		bytes[0] |= 0x80
		// Make the value odd since an even number this large certainly isn't prime.
		bytes[len(bytes)-1] |= 1

		p.SetBytes(bytes)
		if big.ProbablyPrime(p, 20) {
			p2.Rsh(p, 1) // p2 = (p - 1)/2
			if big.ProbablyPrime(p2, 20) {
				return
			}
		}
	}

	return
}

// MakeConst makes an ideal constant from a literal
// token and the corresponding literal string.
func MakeConst(tok token.Token, lit string) Const {
	switch tok {
	case token.INT:
		var x big.Int
		_, ok := x.SetString(lit, 0)
		assert(ok)
		return Const{&x}
	case token.FLOAT:
		var y big.Rat
		_, ok := y.SetString(lit)
		assert(ok)
		return Const{&y}
	case token.IMAG:
		assert(lit[len(lit)-1] == 'i')
		var im big.Rat
		_, ok := im.SetString(lit[0 : len(lit)-1])
		assert(ok)
		return Const{cmplx{big.NewRat(0, 1), &im}}
	case token.CHAR:
		assert(lit[0] == '\'' && lit[len(lit)-1] == '\'')
		code, _, _, err := strconv.UnquoteChar(lit[1:len(lit)-1], '\'')
		assert(err == nil)
		return Const{big.NewInt(int64(code))}
	case token.STRING:
		s, err := strconv.Unquote(lit)
		assert(err == nil)
		return Const{s}
	}
	panic("unreachable")
}

func (curve *Curve) Multiply(n *big.Int, p *Point) *Point {
	if p == nil {
		//fmt.Printf("p == nil!?wtfbbq\n")
		return p
	}

	bytes := n.Bytes()
	length := len(bytes)
	bitlength := length * 8

	fmt.Printf("length = %d\n", bitlength)

	var rightmost uint = 0x01
	//fmt.Printf("leftmost = %d\n", leftmost)
	p2 := p
	last_i := bitlength - 1
	var ptotal *Point
	ptotal = nil
	for i := bitlength - 1; i >= 0; i-- {
		//fmt.Printf("\n(i mod 8) = %d \n", 7-(i%8))
		if uint(rightmost<<uint(7-(i%8)))&uint(bytes[i/8]) != 0 {
			for j := last_i; j > i; j-- {
				//fmt.Printf("Doubling! i=%d\n",i)
				p2 = curve.double(p2)
			}
			last_i = i
			fmt.Printf("last_i = %d\n", last_i)
			ptotal = curve.Add(p2, ptotal)
		}
	}
	return ptotal
}

// randomNumber returns a uniform random value in [0, max).
func randomNumber(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) {
	k := (max.Len() + 7) / 8

	// r is the number of bits in the used in the most significant byte of
	// max.
	r := uint(max.Len() % 8)
	if r == 0 {
		r = 8
	}

	bytes := make([]byte, k)
	n = new(big.Int)

	for {
		_, err = io.ReadFull(rand, bytes)
		if err != nil {
			return
		}

		// Clear bits in the first byte to increase the probability
		// that the candidate is < max.
		bytes[0] &= uint8(int(1<<r) - 1)

		n.SetBytes(bytes)
		if n.Cmp(max) < 0 {
			return
		}
	}

	return
}

// Sign signs an arbitrary length hash (which should be the result of hashing a
// larger message) using the private key, priv. It returns the signature as a
// pair of integers. The security of the private key depends on the entropy of
// rand.
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err os.Error) {
	// See [NSA] 3.4.1
	c := priv.PublicKey.Curve

	var k, kInv *big.Int
	for {
		for {
			k, err = randFieldElement(c, rand)
			if err != nil {
				r = nil
				return
			}

			kInv = new(big.Int).ModInverse(k, c.N)
			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
			r.Mod(r, priv.Curve.N)
			if r.Sign() != 0 {
				break
			}
		}

		e := hashToInt(hash, c)
		s = new(big.Int).Mul(priv.D, r)
		s.Add(s, e)
		s.Mul(s, kInv)
		s.Mod(s, priv.PublicKey.Curve.N)
		if s.Sign() != 0 {
			break
		}
	}

	return
}

// Encrypt encrypts the given message to the given public key. The result is a
// pair of integers. Errors can result from reading random, or because msg is
// too large to be encrypted to the public key.
func Encrypt(random io.Reader, pub *PublicKey, msg []byte) (c1, c2 *big.Int, err error) {
	pLen := (pub.P.BitLen() + 7) / 8
	if len(msg) > pLen-11 {
		err = errors.New("elgamal: message too long")
		return
	}

	// EM = 0x02 || PS || 0x00 || M
	em := make([]byte, pLen-1)
	em[0] = 2
	ps, mm := em[1:len(em)-len(msg)-1], em[len(em)-len(msg):]
	err = nonZeroRandomBytes(ps, random)
	if err != nil {
		return
	}
	em[len(em)-len(msg)-1] = 0
	copy(mm, msg)

	m := new(big.Int).SetBytes(em)

	k, err := rand.Int(random, pub.P)
	if err != nil {
		return
	}

	c1 = new(big.Int).Exp(pub.G, k, pub.P)
	s := new(big.Int).Exp(pub.Y, k, pub.P)
	c2 = s.Mul(s, m)
	c2.Mod(c2, pub.P)

	return
}

func digitSum(num *big.Int) (sum int) {
	sum = 0
	str := num.String()
	for _, v := range str {
		sum += v - 48
	}
	return
}

func (b Base58) Base582Big() *big.Int {
	answer := new(big.Int)
	for i := 0; i < len(b); i++ {
		answer.Mul(answer, big.NewInt(58))                              //multiply current value by 58
		answer.Add(answer, big.NewInt(int64(revalp[string(b[i:i+1])]))) //add value of the current letter
	}
	return answer
}

func SaveKeys(n, e, d, p, q *big.Int) {
	pu := strings.Bytes(n.String() + "\n" + e.String() + "\n")
	pr := strings.Bytes(p.String() + "\n" + q.String() + "\n" + d.String() + "\n")

	if ioutil.WriteFile(*publicKeyFile, pu, 0600) != nil ||
		ioutil.WriteFile(*privateKeyFile, pr, 0600) != nil {
		panic("Writing problems")
	}
}

// printNumber outputs the given big.Int and also appends a ".5" if there is an
// apple that was divided in half.
func (calc *Calculator) printNumber(number *big.Int) {
	fmt.Print(number.String())

	if calc.odd {
		fmt.Print(".5")
	}

	fmt.Println()
}

// Vygeneruje "nahodne" nenulove cislo mensi nez n
func RandNumSmaller(n *big.Int) (r *big.Int) {
	r = big.NewInt(0)
	for r.Cmp(big0) == 0 {
		bytes := randBytes(len(n.Bytes()) * 8)
		r.SetBytes(bytes)
		r.Mod(r, n)
	}
	return
}