08 Go 密码学（五）非对称加密之椭圆曲线算法

椭圆曲线密码学（Elliptic curve cryptography），简称ECC，其和RAS类似属于公开秘钥的加密算法体系。ECC被公认为在给定密钥长度下最安全的加密算法。近年来由于比特币以太币等区块链应用ECC加密算法，业界也普遍看好ECC。

我们说过现代密码学是基于数学难题构建的，如RSA基于大数分解，ECC则基于椭圆曲线的椭圆曲线上的离散对数问题。

椭圆曲线是代数几何中一类重要的曲线，至今已有 100 多年的研究历史。而应用于密码学中的椭圆曲线是基于有限域上的，通过引入无穷远点，将椭圆曲线上的所有点和无穷远点组成一个集合，并在该集合上定义一个运算，从而该集合和运算构成了群。在有限域上的椭圆曲线群有两种，分别基于GF(p)以及GF(2m)，它们各自有不同的群元素和群运算，然而对于群上的 ECDLP 问题，都认为是一个指数级的困难问题。基于这个困难问题，构建了ECC算法，包括==公钥加密、私钥解密、数字签名、签名验证、DH交换==等。

ECDSA 算法是目前使用最为广泛的标准算法，它是以 ECDLP 困难问题为基础，采用ELGamal体制构建的一个签名算法，它包含一个签名算法和一个验证算法。ECDSA算法如下：

首先选择好系统参数，如有限域类型和表示方法，曲线参数a，b，以及一个曲线上的基点G以及G的阶n，要求n必须为一个大素数（相关的系统参数的选择可见文献[23]）。

参数确定以后，ECDSA 算法分为如下 3 个模块分别执行不同的功能，即密钥产生模块、数字签名模块以及签名验证模块。另外介绍一个基于ECC的Diffie－Hellman交换型算法以及公钥加密算法。

密钥产生：
1.在区间[1,n−1]上随机产生一个整数d（当然d不能太小）。
2.计算标量乘法Q=dG。
3.公开Q为公钥，保留d为私钥。

数字签名：
1.使用安全散列函数H对需要签名的消息M进行杂凑计算e=H(M)。
2.随机生成一个区间[1,n−1]上的本地秘密随机数k，并计算kG=(x1,y1)。
3.计算r=x1 mod n。
4.计算s=k−1(e+dr)mod n。
5.则数据r||s即为ECDSA算法下对消息M的签名（其中||表示两个比特串的串接）。

签名验证：
1.使用与签名一样的散列算法H计算e=H(M)。
2.计算c=s−1 mod n。
3.计算u1=ec mod n，u2=rc mod n。
4.计算(x1,y1)＝u1G+uQ2。
5.计算v=x1mod n。若v=r，则为一个合法签名，否则验证不通过。

DH交换：
1.A随机生成一个区间[1,n−1]上的本地秘密随机数k，计算并发送kG到B。
2.B随机生成一个区间[1,n−1]上的本地秘密随机数l，计算并发送lG到A。
3.最后A计算k(lG)同时B计算l(kG)作为双方的共享密钥。

公钥加密算法：
1.公钥加密：随机生成一个区间[1,n－1]上的本地秘密随机数k，并计算，对需要加密的消息M。计算的密文C=kG||kQ+M（其中+为XOR运算）。
2.私钥解密：M=(kQ+M)−d(kG)。

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"time"

	"crypto/x509"
	"encoding/pem"
	"errors"
	mathRand "math/rand"
	"os"
	"strings"
)

const (
	PRIVATEFILE = "src/cryptography/myECDSA/privateKey.pem"
	PUBLICFILE  = "src/cryptography/myECDSA/publicKey.pem"
)

//生成指定math/rand字节长度的随机字符串
func GetRandomString(length int) string {
	str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~!@#$%^&*()_+?=-"
	bytes := []byte(str)
	result := []byte{}

	r := mathRand.New(mathRand.NewSource(time.Now().UnixNano()))
	for i := 0; i < length; i++ {
		result = append(result, bytes[r.Intn(len(bytes))])
	}
	return string(result)
}

//生成ECC算法的公钥和私钥文件
//根据随机字符串生成，randKey至少36位
func GenerateKey(randKey string) error {

	var err error
	var privateKey *ecdsa.PrivateKey
	var publicKey ecdsa.PublicKey
	var curve elliptic.Curve

	//一、生成私钥文件

	//根据随机字符串长度设置curve曲线
	length := len(randKey)
	//elliptic包实现了几条覆盖素数有限域的标准椭圆曲线,Curve代表一个短格式的Weierstrass椭圆曲线，其中a=-3
	if length < 224/8 {
		err = errors.New("私钥长度太短，至少为36位！")
		return err
	}

	if length >= 521/8+8 {
		//长度大于73字节，返回一个实现了P-512的曲线
		curve = elliptic.P521()
	} else if length >= 384/8+8 {
		//长度大于56字节，返回一个实现了P-384的曲线
		curve = elliptic.P384()
	} else if length >= 256/8+8 {
		//长度大于40字节，返回一个实现了P-256的曲线
		curve = elliptic.P256()
	} else if length >= 224/8+8 {
		//长度大于36字节，返回一个实现了P-224的曲线
		curve = elliptic.P224()
	}

	//GenerateKey方法生成私钥
	privateKey, err = ecdsa.GenerateKey(curve, strings.NewReader(randKey))
	if err != nil {
		return err
	}
	//通过x509标准将得到的ecc私钥序列化为ASN.1的DER编码字符串
	privateBytes, err := x509.MarshalECPrivateKey(privateKey)
	if err != nil {
		return err
	}
	//将私钥字符串设置到pem格式块中
	privateBlock := pem.Block{
		Type:  "ecc private key",
		Bytes: privateBytes,
	}

	//通过pem将设置好的数据进行编码，并写入磁盘文件
	privateFile, err := os.Create(PRIVATEFILE)
	if err != nil {
		return err
	}
	defer privateFile.Close()
	err = pem.Encode(privateFile, &privateBlock)
	if err != nil {
		return err
	}

	//二、生成公钥文件
	//从得到的私钥对象中将公钥信息取出
	publicKey = privateKey.PublicKey

	//通过x509标准将得到的ecc公钥序列化为ASN.1的DER编码字符串
	publicBytes, err := x509.MarshalPKIXPublicKey(&publicKey)
	if err != nil {
		return err
	}
	//将公钥字符串设置到pem格式块中
	publicBlock := pem.Block{
		Type:  "ecc public key",
		Bytes: publicBytes,
	}

	//通过pem将设置好的数据进行编码，并写入磁盘文件
	publicFile, err := os.Create(PUBLICFILE)
	if err != nil {
		return err
	}
	err = pem.Encode(publicFile, &publicBlock)
	if err != nil {
		return err
	}

	return nil
}

import (
	"bytes"
	"compress/gzip"
	"crypto/ecdsa"
	"encoding/hex"
	"errors"
	"math/big"
	"strings"
)

//使用ECC算法加密签名，返回签名数据
func CryptSignByEcc(input, priKeyFile, randSign string) (output string, err error) {
	//获取私钥
	privateKey, err := GetPrivateKeyByPemFile(priKeyFile)
	if err != nil {
		return "", err
	}

	//ecc私钥和随机签字符串数据得到哈希
	r, s, err := ecdsa.Sign(strings.NewReader(randSign), privateKey, []byte(input))
	if err != nil {
		return "", err
	}

	rt, err := r.MarshalText()
	if err != nil {
		return "", err
	}

	st, err := s.MarshalText()
	if err != nil {
		return "", err
	}

	//拼接两个椭圆曲线参数哈希
	var b bytes.Buffer
	writer := gzip.NewWriter(&b)
	defer writer.Close()

	_, err = writer.Write([]byte(string(rt) + "+" + string(st)))
	if err != nil {
		return "", err
	}
	writer.Flush()

	return hex.EncodeToString(b.Bytes()), nil
}

//使用ECC算法,对密文和明文进行匹配校验
func VerifyCryptEcc(srcStr, cryptStr string) (bool, error) {

	decodeBytes, err := hex.DecodeString(cryptStr)
	if err != nil {
		return false, err
	}

	//解密签名信息，返回椭圆曲线参数：两个大整数
	rint, sint, err := UnSignCryptEcc(decodeBytes)

	//获取公钥验证数据
	publicKey, err := GetPublicKeyByPemFile(PUBLICFILE)
	if err != nil {
		return false, err
	}
	//使用公钥、原文、以及签名信息解密后的两个椭圆曲线的大整数参数进行校验
	verify := ecdsa.Verify(publicKey, []byte(srcStr), &rint, &sint)

	return verify, nil
}

//使用ECC算法解密,返回加密前的椭圆曲线大整数
func UnSignCryptEcc(cryptBytes []byte) (rint, sint big.Int, err error) {
	reader, err := gzip.NewReader(bytes.NewBuffer(cryptBytes))
	if err != nil {
		err = errors.New("decode error," + err.Error())
	}
	defer reader.Close()

	buf := make([]byte, 1024)
	count, err := reader.Read(buf)
	if err != nil {
		err = errors.New("decode read error," + err.Error())
	}

	rs := strings.Split(string(buf[:count]), "+")
	if len(rs) != 2 {
		err = errors.New("decode fail")
		return
	}
	err = rint.UnmarshalText([]byte(rs[0]))
	if err != nil {
		err = errors.New("decrypt rint fail, " + err.Error())
		return
	}
	err = sint.UnmarshalText([]byte(rs[1]))
	if err != nil {
		err = errors.New("decrypt sint fail, " + err.Error())
		return
	}
	return
}

func GetPrivateKeyByPemFile(priKeyFile string) (*ecdsa.PrivateKey, error) {
	//将私钥文件中的私钥读出，得到使用pem编码的字符串
	file, err := os.Open(priKeyFile)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	fileInfo, err := file.Stat()
	if err != nil {
		return nil, err
	}
	size := fileInfo.Size()
	buffer := make([]byte, size)
	_, err = file.Read(buffer)
	if err != nil {
		return nil, err
	}
	//将得到的字符串解码
	block, _ := pem.Decode(buffer)

	//使用x509将编码之后的私钥解析出来
	privateKey, err := x509.ParseECPrivateKey(block.Bytes)
	if err != nil {
		return nil, err
	}

	return privateKey, nil
}

func GetPublicKeyByPemFile(pubKeyFile string) (*ecdsa.PublicKey, error) {
	var err error
	//从公钥文件获取钥匙字符串
	file, err := os.Open(pubKeyFile)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	fileInfo, err := file.Stat()
	if err != nil {
		return nil, err
	}

	buffer := make([]byte, fileInfo.Size())
	_, err = file.Read(buffer)
	if err != nil {
		return nil, err
	}
	//将得到的字符串解码
	block, _ := pem.Decode(buffer)

	//使用x509将编码之后的公钥解析出来
	pubInner, err := x509.ParsePKIXPublicKey(block.Bytes)
	if err != nil {
		return nil, err
	}

	publicKey := pubInner.(*ecdsa.PublicKey)

	return publicKey, nil
}

func TestECDSA() {
	//生成随机钥字符串长度40字节，用于生产公私钥证书
	randKey := myECDSA.GetRandomString(40)
	//生成随机签名字符串40字节，用于加密数据
	randSign := myECDSA.GetRandomString(40)

	//使用随机钥字符串生成公私钥文件
	e := myECDSA.GenerateKey(randKey)
	if e != nil {
		fmt.Println(e)
	}

	//签名附加信息
	srcInfo := "GO 密码学 —— ECDSA 椭圆曲线实现数字签名"
	fmt.Println("原文：", srcInfo)

	//ECC签名加密
	signByEcc, e := myECDSA.CryptSignByEcc(srcInfo, myECDSA.PRIVATEFILE, randSign)
	if e != nil {
		fmt.Println(e)
	}
	fmt.Println("ECDSA私钥加密签名为：", signByEcc)

	//ECC签名算法校验
	verifyCryptEcc, e := myECDSA.VerifyCryptEcc(srcInfo, signByEcc)
	if e != nil {
		fmt.Println(e)
	}
	fmt.Println("ECDSA公钥解密后验签校验结果：", verifyCryptEcc)

}

//OUTPUT:
原文： GO 密码学 —— ECDSA 椭圆曲线实现数字签名
ECDSA私钥加密签名为： 1f8b08000000000000ff14cbb10d43510c02c081d2609e31b0ff62d16f4fbac1bd3a8666cb598f9f595e208fa950d9e4721457071f85ae9a06d1e37b600dc0f885fa0c37aea7678ac6ce75c4d4e5c386ad446a0fd2adced767ccf70628ac81f60f0000ffff
ECDSA公钥解密后验签校验结果： true

go标准包的ECDSA仅支持数字签名和验签，对数据传输的加解密还未提供，不过以太坊基于crypto/ecdsa实现了ECIES加解密算法，github.com/ethereum/go-ethereum ，感兴趣的可阅读器源码使用，该包声明未经过审核，以下演示仅供个人学习使用：

package myECIES

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"github.com/ethereum/go-ethereum/crypto/ecies"
	"strings"
	"time"

	"crypto/x509"
	"encoding/pem"
	"errors"
	mathRand "math/rand"
	"os"
)

const (
	PRIVATEFILE = "src/cryptography/myECIES/privateKey.pem"
	PUBLICFILE  = "src/cryptography/myECIES/publicKey.pem"
)

//生成指定math/rand字节长度的随机字符串
func GetRandomString(length int) string {
	str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~!@#$%^&*()_+?=-"
	bytes := []byte(str)
	result := []byte{}

	r := mathRand.New(mathRand.NewSource(time.Now().UnixNano()))
	for i := 0; i < length; i++ {
		result = append(result, bytes[r.Intn(len(bytes))])
	}
	return string(result)
}

//生成ECC算法的公钥和私钥文件
//根据随机字符串生成，randKey至少36位
func GenerateKey(randKey string) error {

	var err error
	var privateKey *ecdsa.PrivateKey
	var publicKey ecdsa.PublicKey
	var curve elliptic.Curve

	//一、生成私钥文件

	//根据随机字符串长度设置curve曲线
	length := len(randKey)
	//elliptic包实现了几条覆盖素数有限域的标准椭圆曲线,Curve代表一个短格式的Weierstrass椭圆曲线，其中a=-3
	if length < 224/8 {
		err = errors.New("私钥长度太短，至少为36位！")
		return err
	}

	if length >= 521/8+8 {
		//长度大于73字节，返回一个实现了P-512的曲线
		curve = elliptic.P521()
	} else if length >= 384/8+8 {
		//长度大于56字节，返回一个实现了P-384的曲线
		curve = elliptic.P384()
	} else if length >= 256/8+8 {
		//长度大于40字节，返回一个实现了P-256的曲线
		curve = elliptic.P256()
	} else if length >= 224/8+8 {
		//长度大于36字节，返回一个实现了P-224的曲线
		curve = elliptic.P224()
	}

	//GenerateKey方法生成私钥
	privateKey, err = ecdsa.GenerateKey(curve, strings.NewReader(randKey))
	if err != nil {
		return err
	}
	//通过x509标准将得到的ecc私钥序列化为ASN.1的DER编码字符串
	privateBytes, err := x509.MarshalECPrivateKey(privateKey)
	if err != nil {
		return err
	}
	//将私钥字符串设置到pem格式块中
	privateBlock := pem.Block{
		Type:  "ecc private key",
		Bytes: privateBytes,
	}

	//通过pem将设置好的数据进行编码，并写入磁盘文件
	privateFile, err := os.Create(PRIVATEFILE)
	if err != nil {
		return err
	}
	defer privateFile.Close()
	err = pem.Encode(privateFile, &privateBlock)
	if err != nil {
		return err
	}

	//二、生成公钥文件
	//从得到的私钥对象中将公钥信息取出
	publicKey = privateKey.PublicKey

	//通过x509标准将得到的ecc公钥序列化为ASN.1的DER编码字符串
	publicBytes, err := x509.MarshalPKIXPublicKey(&publicKey)
	if err != nil {
		return err
	}
	//将公钥字符串设置到pem格式块中
	publicBlock := pem.Block{
		Type:  "ecc public key",
		Bytes: publicBytes,
	}

	//通过pem将设置好的数据进行编码，并写入磁盘文件
	publicFile, err := os.Create(PUBLICFILE)
	if err != nil {
		return err
	}
	err = pem.Encode(publicFile, &publicBlock)
	if err != nil {
		return err
	}

	return nil
}

//获取私钥文件里的私钥内容函数
func GetPrivateKeyByPemFile(priKeyFile string) (*ecies.PrivateKey, error) {
	//将私钥文件中的私钥读出，得到使用pem编码的字符串
	file, err := os.Open(priKeyFile)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	fileInfo, err := file.Stat()
	if err != nil {
		return nil, err
	}
	size := fileInfo.Size()
	buffer := make([]byte, size)
	_, err = file.Read(buffer)
	if err != nil {
		return nil, err
	}
	//将得到的字符串解码
	block, _ := pem.Decode(buffer)

	//使用x509将编码之后的私钥解析出来
	privateKey, err := x509.ParseECPrivateKey(block.Bytes)
	if err != nil {
		return nil, err
	}

	//读取文件的ecdsa私钥转化成ecies私钥
	privateKeyForEcies := ecies.ImportECDSA(privateKey)

	return privateKeyForEcies, nil
}

//获取公钥文件里的公钥内容函数
func GetPublicKeyByPemFile(pubKeyFile string) (*ecies.PublicKey, error) {
	var err error
	//从公钥文件获取钥匙字符串
	file, err := os.Open(pubKeyFile)
	if err != nil {
		return nil, err
	}
	defer file.Close()

	fileInfo, err := file.Stat()
	if err != nil {
		return nil, err
	}

	buffer := make([]byte, fileInfo.Size())
	_, err = file.Read(buffer)
	if err != nil {
		return nil, err
	}
	//将得到的字符串解码
	block, _ := pem.Decode(buffer)

	//使用x509将编码之后的公钥解析出来
	pubInner, err := x509.ParsePKIXPublicKey(block.Bytes)
	if err != nil {
		return nil, err
	}

	publicKey := pubInner.(*ecdsa.PublicKey)

	publicKeyForEcies := ecies.ImportECDSAPublic(publicKey)

	return publicKeyForEcies, nil
}

import (
	"crypto/rand"
	"encoding/hex"
	"fmt"
	"github.com/ethereum/go-ethereum/crypto/ecies"
)

//ECIES 公钥数据加密
func EnCryptByEcies(srcData, publicFile string) (cryptData string, err error) {
	//获取公钥数据
	publicKey, err := GetPublicKeyByPemFile(publicFile)
	if err != nil {
		return "", err
	}

	//公钥加密数据
	encryptBytes, err := ecies.Encrypt(rand.Reader, publicKey, []byte(srcData), nil, nil)
	if err != nil {
		return "", err
	}

	cryptData = hex.EncodeToString(encryptBytes)

	return
}

//ECIES 私钥数据解密
func DeCryptByEcies(cryptData, privateFile string) (srcData string, err error) {
	//获取私钥信息
	privateKey, err := GetPrivateKeyByPemFile(privateFile)
	if err != nil {
		return "", err
	}

	//私钥解密数据
	cryptBytes, err := hex.DecodeString(cryptData)
	srcByte, err := privateKey.Decrypt(cryptBytes, nil, nil)
	if err != nil {
		fmt.Println("解密错误：", err)
		return "", err
	}
	srcData = string(srcByte)

	return
}

//测试ECC椭圆曲线实现数据加解密
func TestECIES() {
	//获取随机字符串
	randomKey := myECIES.GetRandomString(40)

	//生成私钥和公钥
	e := myECIES.GenerateKey(randomKey)
	if e != nil {
		fmt.Println(e)
	}

	//加密前源信息
	srcInfo := "GO 密码学 —— ECIES 椭圆曲线实现数据加解密"
	fmt.Println("原文：", srcInfo)

	//加密信息
	cryptData, e := myECIES.EnCryptByEcies(srcInfo, myECIES.PUBLICFILE)
	if e != nil {
		fmt.Println(e)
	}
	fmt.Println("ECIES加密后为：", cryptData)

	//解密信息
	srcData, e := myECIES.DeCryptByEcies(cryptData, myECIES.PRIVATEFILE)
	if e != nil {
		fmt.Println(e)
	}
	fmt.Println("ECIES解密后为：", srcData)

}

//OUTPUT:
原文： GO 密码学 —— ECIES 椭圆曲线实现数据加解密
ECIES加密后为： 0494ba1ad5e9d4606e8360432723727a10fac1206f64063414dd038df359ccb663725a3cd4a17a07330e1ec52f6a40a7ee278ea7491f9c0beace8ef283152555bd86da3f622408503266e1dcadb0efd1d371cedbd874f0b08b3f9a3dbd47da4cf1917e4c0d20d913dbe8851db38895de46377bfd929b4432a07c8d99da89127da5a8a212b400aed12bdb172a8b219d847106bad4f2ea21ac4d758447bc70f798b5d4272088e435ab3804337d
ECIES解密后为： GO 密码学 —— ECIES 椭圆曲线实现数据加解密

至此Go 密码学实践告一段落，其具体实战应该后期会在实战专题展开。