shuffler/src/util/elliptic_util.go

// Copyright 2017 The Fuchsia Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package util

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/x509"
	"encoding/pem"
	"fmt"
	"math/big"
)

// The elliptic curve we are using.
var ellipticCurve elliptic.Curve

// The number of bytes used in the serialized representation of a point on
// the elliptic curve.
var ecSerializationSize int

// The maximum number of bytes needed to store a representation of an element of
// the field over which the elliptic curve group is defined. (Currently this
// will be 32 bytes.)
var ecFieldElementSize int

func init() {
	// If the choice of curve changes we must change the numerical constants
	// above.
	ellipticCurve = elliptic.P256()

	// 32 bytes if we are using P256.
	ecFieldElementSize = (ellipticCurve.Params().BitSize + 7) >> 3

	// We use the "compressed" form in which a point is represented by its
	// x-coordinate (32 bytes, big-endian) with a leading byte indicating
	// which of the two square roots to use for the y-coordinate.
	ecSerializationSize = ecFieldElementSize + 1
}

// Routines for working with Elliptic curves.
//
// The code in this file was largely cribbed from some code written by Bryan Ford
// in https://go-review.googlesource.com/c/1883/.

// Use the curve equation to calculate y² given x
func ySquared(curve *elliptic.CurveParams, x *big.Int) *big.Int {

	// y² = x³ - 3x + b
	x3 := new(big.Int).Mul(x, x)
	x3.Mul(x3, x)

	threeX := new(big.Int).Lsh(x, 1)
	threeX.Add(threeX, x)

	x3.Sub(x3, threeX)
	x3.Add(x3, curve.B)
	x3.Mod(x3, curve.P)
	return x3
}

// MarshalCompressed returns the X9.62 compressed serialization of the point
// (x, y), which must be a point on the given |curve|. Returns nil on failure.
func MarshalCompressed(curve elliptic.Curve, x, y *big.Int) []byte {
	ret := make([]byte, ecSerializationSize)
	ret[0] = 2 // compressed point

	xBytes := x.Bytes()
	if len(xBytes) > ecFieldElementSize {
		return nil
	}
	copy(ret[ecSerializationSize-len(xBytes):], xBytes)
	// The first byte of the encoding indicates which square root of y² y is.
	ret[0] += byte(y.Bit(0))
	return ret
}

// Unmarshal returns the point (x, y) on the given |curve| that is encoded
// by |data|, which must be either the compressed or uncompressed X9.62
// serialization of a point on the curve. Returns nil on failure.
func Unmarshal(curve elliptic.Curve, data []byte) (x, y *big.Int) {
	// If the data is uncompressed just invoke elliptic.Unmarshal.
	x, y = elliptic.Unmarshal(curve, data)
	if x != nil && y != nil {
		return
	}
	x = nil
	y = nil
	byteLen := (curve.Params().BitSize + 7) >> 3
	if len(data) != 1+byteLen {
		return
	}
	if (data[0] &^ 1) != 2 {
		return // unrecognized point encoding
	}

	// Based on Routine 2.2.4 in NIST Mathematical Routines paper
	params := curve.Params()
	tx := new(big.Int).SetBytes(data[1 : 1+byteLen])
	y2 := ySquared(params, tx)

	// Compute the square root of y2.
	ty := new(big.Int).ModSqrt(y2, params.P)
	if ty == nil {
		return // y2 is not a quadratic residue: invalid point
	}

	// data[0] encodes which of the two square roots of y2 we want.
	if ty.Bit(0) != uint(data[0]&1) {
		ty.Sub(params.P, ty)
	}

	x, y = tx, ty // valid point: return it
	return
}

// computeSharedKey returns the ECDH shared key corresponding to the given
// public and private keys.
//
// If the public key is g^alpha and the private key is beta then the shared key is
// g^{alpha*beta}.
//
// Since elliptic curve groups use additive notion this will be a scalar
// multiplication instead of an exponentiation. Thus if the public key is
// alpha*g and the private key is beta then the shared key is beta*alpha*g.
//
// More precisely, let (x, y) be the affine coordinates of beta*alpha*g. So
// x and y are elements of the underlying field and so they are integers in
// the range [0, ecFieldElementSize). The shared key is the big-endian bytes
// of x, padded with leading zeroes so as to have length ecFieldElementSize.
func computeSharedKey(publicX, publicY *big.Int, privateKey []byte) []byte {
	xCoord, _ := ellipticCurve.ScalarMult(publicX, publicY, privateKey)
	sharedKey, err := padFieldElement(xCoord.Bytes())
	if err != nil {
		panic(fmt.Sprintf("Cannot compute sharedKey: %v", err))
	}
	return sharedKey
}

// padFieldElement pads |fieldElement| with leading zeroes to a length of
// ecFieldElementSize. Returns the padded value or an error if len(fieldElement)
// is greater than ecFieldElementSize.
func padFieldElement(fieldElement []byte) ([]byte, error) {
	// Pad with leading zeroes to ecFieldElementSize.
	if len(fieldElement) == ecFieldElementSize {
		return fieldElement, nil
	}
	if len(fieldElement) > ecFieldElementSize {
		return nil, fmt.Errorf("len(fieldElement)=%d", len(fieldElement))
	}
	fieldElementPadded := make([]byte, ecFieldElementSize)
	copy(fieldElementPadded[ecFieldElementSize-len(fieldElement):], fieldElement)
	return fieldElementPadded, nil
}

// ParseECPrivateKeyPem parses a PEM encoded private EC key. The PEM should contain
// an unencrypted PKCS#8 (see RFC 5208) private key of type ECDSA (see RFC 5480).
func ParseECPrivateKeyPem(privateKeyPem string) (privateKey []byte, err error) {
	block, _ := pem.Decode([]byte(privateKeyPem))
	if block == nil {
		err = fmt.Errorf("Private key PEM could not be parsed.")
		return
	}
	result, err2 := x509.ParsePKCS8PrivateKey(block.Bytes)
	if err2 != nil {
		err = err2
		return
	}
	ecPrivateKey, ok := result.(*ecdsa.PrivateKey)
	if !ok {
		err = fmt.Errorf("The private key PEM file did not contain an EC private key but rather a %T.", result)
		return
	}
	privateKey, err = padFieldElement(ecPrivateKey.D.Bytes())
	if err != nil {
		err = fmt.Errorf("Cannot parse hybrid cipher private key PEM: %d.", err)
		return
	}
	return
}

// ParseECPublicKeyPem parses a PEM encoded public EC key. The PEM should contain a
// PKCS#8 public key of type ECDSA.
func ParseECPublicKeyPem(publicKeyPEM string) (publicKey []byte, err error) {
	block, _ := pem.Decode([]byte(publicKeyPEM))
	if block == nil {
		err = fmt.Errorf("Public key PEM could not be parsed.")
		return
	}
	result, err2 := x509.ParsePKIXPublicKey(block.Bytes)
	if err2 != nil {
		err = err2
		return
	}
	ecPublicKey, ok := result.(*ecdsa.PublicKey)
	if !ok {
		err = fmt.Errorf("The public key PEM file did not contain an EC public key but rather a %T.", result)
		return
	}
	if ecPublicKey.Curve != ellipticCurve {
		err = fmt.Errorf("The public key PEM contained an EC public key for the wrong curve: %v", ecPublicKey.Curve)
		return
	}
	return elliptic.Marshal(ecPublicKey.Curve, ecPublicKey.X, ecPublicKey.Y), nil
}