ECC 算法原理&JAVA 实现 - Charlie

遗留问题

ECCurve.Fp与ECCurve.F2m区别？

概述

椭圆曲线算法依赖于椭圆曲线，只有椭圆曲线确定之后，才能基于此曲线去做加密、解密，加签、验签。

椭圆曲线算法同样有多种密钥长度，常用的有160bit、192bit、224bit、256bit、320bit、384bit、512bit。

常用的曲线有：secp192r1、secp192k1、secp224r1、secp256r1、secp256k1等

具体椭圆曲线参数名称可见：椭圆曲线名称

数学原理简述

ECC算法基于离散对数数学难题

算法具体过程

① 用户A选定一条椭圆曲线Ep(a , b)，并取椭圆曲线上一点，作为基点G。

② 用户A选择一个私有密钥k，并生成公开密钥K=kG。

③ 用户A将Ep(a , b)和点K，G传给用户B。

④ 用户B接到信息后，将待传输的明文编码到Ep(a , b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）。

⑤ 用户B计算点C1=M+rK；C2=rG。

⑥ 用户B将C1、C2传给用户A。

⑦ 用户A接到信息后，计算C1 - kC2，结果就是点M。C1-kC2=M+rK-k(rG)=M+rK-r(rG)=M

⑧ 再对点M进行解码就可以得到明文。

椭圆曲线相关参数及含义

参数

含义

椭圆曲线从连续变为离散，使其适合用于加密。所以将曲线限制在有限域Fp上，其中p为素数，Fp上只有p个元素

a、b与p共同确定一条曲线。在Fp上，选择小于P的两个素数a、b，使其满足方程 4a^3+27b^2≠0 (mod p) 则满足方程 y^2=x^3+ax^2+b (mod p) 的所有点(x , y)，再加上无穷远点O∞ ，构成一条椭圆曲线我们记为：Ep(a , b)

用户选择Ep(a,b)上的一个G点，作为基点，用于生成公钥、私钥

具体生成公私钥的原理
考虑如下等式：K=kG [其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数]不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。这就是椭圆曲线加密算法采用的难题。我们把点G称为基点，k（k<n，n为基点G的阶）称为私钥，K称为公钥

n为基点G的阶，并且为素数

椭圆曲线上点的阶
如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，则将n称为P的阶，若n不存在，我们说P是无限阶的。事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的（证明，请参考近世代数方面的书）

椭圆曲线上所有点的个数m与n相除的整数部分，h<=4

密钥格式

密钥类型	格式
公钥	公钥是椭圆曲线上的一个点，由 x轴坐标和 y轴坐标组成。 02/03 + x轴坐标：压缩法表示的公钥，02表示y轴坐标为偶数，03表示y轴坐标为奇数 04 + x轴坐标 + y轴坐标：完整公钥表示法
私钥	公式：K=kG，其中k为私钥，G为基点用户选择的私钥k<n（n为点G的阶）曲线选择为多少位，则私钥长度也是多少位

SM2

sm2 曲线名称为：sm2p256v1

JAVA实现

ECC JAVA示例

import com.google.common.collect.Maps;
import com.sankuai.cx.etcp.code.util.HexUtil;
import com.sankuai.cx.etcp.code.util.sm.newer.ASNUtil;
import javafx.print.PageLayout;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.codec.digest.DigestUtils;
import org.bouncycastle.asn1.*;
import org.bouncycastle.jce.provider.JCEECPrivateKey;
import org.bouncycastle.jce.provider.JCEECPublicKey;
import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.math.ec.ECFieldElement;
import sun.security.ec.ECPublicKeyImpl;
import sun.security.util.DerOutputStream;
import sun.security.util.DerValue;

import java.io.ByteArrayInputStream;
import java.math.BigInteger;
import java.security.*;
import java.security.interfaces.ECPrivateKey;
import java.security.interfaces.ECPublicKey;
import java.security.spec.*;
import java.util.Enumeration;
import java.util.Map;

/**
 * @Author:wangchao
 * @Date: 2019/5/29 2:34 PM
 * @Description:
 **/
@Slf4j
public class EccUtil {
    /**
     * 算法名称
     */
    private static final String ALGORITHM = "EC";

    private static final String SHA1WITHECDSA = "SHA1WITHECDSA";

    /**
     * 根据曲线名称生成 keypair
     * @param parameter
     * @return
     * @throws Exception
     */
    public static KeyPair initKey(String parameter) throws Exception{
        //生成密钥
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance(ALGORITHM);
        //指定曲线名称
        ECGenParameterSpec ecGenParameterSpec = new ECGenParameterSpec(parameter);
        //从具体曲线参数生成曲线
        keyPairGenerator.initialize(ecGenParameterSpec);
        return keyPairGenerator.generateKeyPair();
    }

    /**
     * 创建 EC 私钥
     * @param keyPair
     * @return
     */
    public static String createPrivateKey(KeyPair keyPair,Ecc ecc){
        ECPrivateKey ecPrivateKey = (ECPrivateKey) keyPair.getPrivate();
        byte[] b = ASNUtil.bigIntToFixexLengthBytes(ecPrivateKey.getS(),ecc.getKeyLen());
        return HexUtil.byteToHex(b);
    }

    /**
     * 创建公钥 Point
     * @param keyPair
     * @return
     */
    public static ECPoint createPublicKeyPoint(KeyPair keyPair){
        ECPublicKey ecPublicKey = (ECPublicKey) keyPair.getPublic();
        return ecPublicKey.getW();
    }

    /**
     * 创建公钥 pubx + puby
     * @param keyPair
     * @return
     */
    public static String createPublicKey(KeyPair keyPair,Ecc ecc){
        ECPublicKey ecPublicKey = (ECPublicKey) keyPair.getPublic();
        String x = HexUtil.byteToHex(ASNUtil.bigIntToFixexLengthBytes(ecPublicKey.getW().getAffineX(),ecc.getKeyLen()));
        String y = HexUtil.byteToHex(ASNUtil.bigIntToFixexLengthBytes(ecPublicKey.getW().getAffineY(),ecc.getKeyLen()));
        return x + y;
    }

    /**
     * 加载私钥
     * @param privateKey hex
     * @param ecc 曲线参数
     * @return
     * @throws Exception
     */
    public static ECPrivateKey loadPrivateKey(String privateKey,Ecc ecc) throws Exception{
        ECParameterSpec ecParameterSpec = createFromParameterName(ecc);
//        return new ECPrivateKeyImpl(new BigInteger(privateKey,16),ecParameterSpec);
        return new JCEECPrivateKey(ALGORITHM,new ECPrivateKeySpec(new BigInteger(privateKey,16),ecParameterSpec));
    }

    /**
     * 加载公钥
     * @param pubx x 点,hex
     * @param puby y 点,hex
     * @param ecc 曲线参数
     * @return
     * @throws Exception
     */
    public static ECPublicKey loadPublicKey(String pubx,String puby,Ecc ecc) throws Exception{
        ECParameterSpec ecParameterSpec = createFromParameterName(ecc);
//        return new ECPublicKeyImpl(new ECPoint(new BigInteger(pubx,16),new BigInteger(puby,16)),ecParameterSpec);
        return new JCEECPublicKey(ALGORITHM,new ECPublicKeySpec(new ECPoint(new BigInteger(pubx,16),new BigInteger(puby,16)),ecParameterSpec));
    }


    /**
     * 创建曲线参数
     * @param ecc
     * @return
     */
    public static ECParameterSpec createFromParameterName(Ecc ecc){
        BigInteger[] parameter = ecc.getParameter();
        BigInteger P = parameter[0];
        BigInteger A = parameter[1];
        BigInteger B = parameter[2];
        BigInteger X = parameter[3];
        BigInteger Y = parameter[4];
        BigInteger N = parameter[5];
        int H = parameter[6].intValue();
        ECParameterSpec ecParameterSpec = new ECParameterSpec(new EllipticCurve(new ECFieldFp(P),A,B),new ECPoint(X,Y),N,H);
        return ecParameterSpec;
    }

    /**
     * 进行 ecdsa 签名
     * @param source hex
     * @param privateKey hex
     * @param ecc
     * @return
     * @throws Exception
     */
    public static String sign(String source,String privateKey,Ecc ecc) throws Exception{
        ECPrivateKey ecPrivateKey = loadPrivateKey(privateKey,ecc);
        Signature signature = Signature.getInstance(SHA1WITHECDSA);
        signature.initSign(ecPrivateKey);
        signature.update(HexUtil.hexStringToBytes(source));
        byte[] result = signature.sign();

        byte[] plainResult = ASNUtil.rsAsn1ToPlainByteArray(result,ecc.getKeyLen());

        return HexUtil.byteToHex(plainResult);
    }

    /**
     * ecdsa 验签,传入完整公钥
     * @param source hex
     * @param sign hex
     * @param pubx hex
     * @param puby hex
     * @param ecc
     * @return
     * @throws Exception
     */
    public static boolean verify(String source,String sign,String pubx,String puby,Ecc ecc) throws Exception{

        //将签名值按照der格式进行编码
        byte[] sig = HexUtil.hexStringToBytes(sign);
        byte[] encodeSig = ASNUtil.rsPlainByteArrayToAsn1(sig,ecc.getKeyLen());

        ECPublicKey ecPublicKey = loadPublicKey(pubx,puby,ecc);
        Signature signature = Signature.getInstance(SHA1WITHECDSA);
        signature.initVerify(ecPublicKey);
        signature.update(HexUtil.hexStringToBytes(source));
        return signature.verify(encodeSig);
    }

    /**
     * ecdsa 验签,传入压缩公钥
     * @param source hex
     * @param sign hex
     * @param compressedPubkey hex
     * @param ecc
     * @return
     * @throws Exception
     */
    public static boolean verify(String source,String sign,String compressedPubkey,Ecc ecc) throws Exception{
        org.bouncycastle.math.ec.ECPoint publicPoint = decompressPubkey(compressedPubkey,ecc);
        String pubx = HexUtil.byteToHex(publicPoint.getX().toBigInteger().toByteArray());
        String puby = HexUtil.byteToHex(publicPoint.getY().toBigInteger().toByteArray());
        ECPublicKey ecPublicKey = loadPublicKey(pubx,puby,ecc);

        //将签名值按照der格式进行编码
        byte[] sig = HexUtil.hexStringToBytes(sign);
        byte[] encodeSig = ASNUtil.rsPlainByteArrayToAsn1(sig,ecc.getKeyLen());

        Signature signature = Signature.getInstance(SHA1WITHECDSA);
        signature.initVerify(ecPublicKey);
        signature.update(HexUtil.hexStringToBytes(source));
        return signature.verify(encodeSig);
    }

    /**
     * 压缩公钥
     * @param pubx hex
     * @param puby hex
     * @param ecc
     * @return
     */
    public static String compressPubkey(String pubx,String puby,Ecc ecc){
        BigInteger[] paramter = ecc.getParameter();
        BigInteger ecc_p = paramter[0];
        BigInteger ecc_a = paramter[1];
        BigInteger ecc_b = paramter[2];
        ECCurve ecc_curve = new ECCurve.Fp(ecc_p, ecc_a, ecc_b);

        // 构造点
        BigInteger ecc_p1 = new BigInteger(pubx, 16);
        BigInteger ecc_p2 = new BigInteger(puby, 16);
        ECFieldElement aaaecc_gx_fieldelement = new ECFieldElement.Fp(ecc_p, ecc_p1);
        ECFieldElement aaaecc_gy_fieldelement = new ECFieldElement.Fp(ecc_p, ecc_p2);
        org.bouncycastle.math.ec.ECPoint ecPoint = new org.bouncycastle.math.ec.ECPoint.Fp(ecc_curve, aaaecc_gx_fieldelement, aaaecc_gy_fieldelement);
        // 得到压缩后的公钥
        byte[] compKey = ecPoint.getEncoded(true);
        return HexUtil.byteToHex(compKey);
    }

    public static String compress(String x,String y){
        BigInteger by = new BigInteger(y,16);
        if(by.testBit(0)){
            return "03" + x;
        }else {
            return "02" + x;
        }
    }

    /**
     * 解压公钥
     * @param compressedPubkey hex
     * @param ecc
     * @return
     */
    public static org.bouncycastle.math.ec.ECPoint decompressPubkey(String compressedPubkey,Ecc ecc){
        BigInteger[] parameter = ecc.getParameter();
        Map<String,BigInteger> m = Maps.newHashMap();
        BigInteger P = parameter[0];
        BigInteger A = parameter[1];
        BigInteger B = parameter[2];
        ECCurve ecc_curve = new ECCurve.Fp(P, A, B);
        // 根据X恢复点Y，
        return ecc_curve.decodePoint(
                HexUtil.hexStringToBytes(compressedPubkey));
    }

    /**
     * 创建 EC 私钥
     * @param keyPair
     * @return
     */
    public static String createPrivateKey11(KeyPair keyPair,Ecc ecc){
        ECPrivateKey ecPrivateKey = (ECPrivateKey) keyPair.getPrivate();
//        byte[] b = ASNUtil.bigIntToFixexLengthBytes(ecPrivateKey.getS(),ecc.getKeyLen());
        byte[] b = ecPrivateKey.getEncoded();
        ASN1Sequence seq = ASN1Sequence.getInstance(b);
        Enumeration enumeration = seq.getObjects();
        while(enumeration.hasMoreElements()){
            Object o = enumeration.nextElement();
            System.out.println(o);
        }
        return HexUtil.byteToHex(b);
    }

    /**
     * 创建公钥 pubx + puby
     * @param keyPair
     * @return
     */
    public static String createPublicKey11(KeyPair keyPair,Ecc ecc){
        ECPublicKey ecPublicKey = (ECPublicKey) keyPair.getPublic();
//        String x = HexUtil.byteToHex(ASNUtil.bigIntToFixexLengthBytes(ecPublicKey.getW().getAffineX(),ecc.getKeyLen()));
//        String y = HexUtil.byteToHex(ASNUtil.bigIntToFixexLengthBytes(ecPublicKey.getW().getAffineY(),ecc.getKeyLen()));
        System.out.println("pub : format = " + ecPublicKey.getFormat());
        byte[] b = ecPublicKey.getEncoded();
        ASN1Sequence seq = ASN1Sequence.getInstance(b);
//        Enumeration enumeration = seq.getObjects();
//        while(enumeration.hasMoreElements()){
//            Object o = enumeration.nextElement();
//            System.out.println(o);
//        }
        DERBitString derBitString = DERBitString.getInstance(seq.getObjectAt(1));
        ASN1Sequence seq1 = ASN1Sequence.getInstance(derBitString.getOctets());

        return "test";
    }

    public static void main(String[] args) throws Exception{
        Ecc ecc = Ecc.secp256r1;
        String source = "80021630303030303030303030303030303130031148303021000130880000215500002155000003200125B0ADD3791AF08B4A99F5EB05F7372AE473C1C32175CE57C958A29B6502B147203012310120010100F5F3FC7D63E0043CE0A06A559BA3B771C7E277B81B7488AAD4487A19316900E975A13AE7796E653C6D9E11029B1F78A6CF9C388F380D72D51151DAEC79C47AF74DB51CFB";
        KeyPair keyPair = initKey(ecc.getName());
        createPublicKey11(keyPair,ecc);
//        createPrivateKey11(keyPair,ecc);
    }
}

参考资料

https://blog.csdn.net/qq_30866297/article/details/51175305

https://blog.csdn.net/qq_35612816/article/details/78904225