椭圆曲线密码学OpenSSL示例

有限域上的椭圆曲线

这里略去有限域、射影几何等数学背景介绍。先给出实数域空间上椭圆曲线的一般形式：

y^2z + a_1xyz + a3yz^2 = x^3 + a2x^2z + a4xz^2 + a6z^3
以上式子中，x,y,z均为变元。而令z=1, 则可以得到平面上的椭圆曲线Ep(x,y)。

对平面上椭圆曲线上的点 P, Q, R ，以及关于x轴对称的点 P', Q', R' , 定义点的加法:

Add : P+Q = R'

从几何上看点的加法：P点和Q点之和R'，是P、Q两点连线与曲线的交点R关于x轴的对称点。当P、Q点重合时，二者的连线即点的切线。此外，图中点 0 即原点/无穷远点。

加法定义完毕后，乘法和逆运算呼之欲出：
Mul : P + P + ... P = nP

Inverse : P + (-P) = O
这样，椭圆曲线上点的加法、乘法、求逆等运算，就等同于平面上求直线与曲线交点、曲线上点的切线等初等解析几何问题，计算过程是简单的。

密码学需要使用离散点，因此要将椭圆曲线上的点限定在一个有限域内，即参数(a,b,c)和变元(x,y)取值在有限域中。椭圆曲线主要使用的有限域有GF(p)素数域，以及GF(2^m)二元域。其中，素数域的椭圆曲线形式如下：

y^2 = (x^3 + ax + b)( \bmod p)

4(a^3) + 27(b^2) \not= 0 ( \bmod p)
通常p是一个大素数。不同于实数域上点的运算有直观的几何形象，有限域中点P(x, y)的运算在等号两侧都需要取模（mod p）。此外一个显而易见的性质是：由于曲线的各个参数定义在有限域上，符合Abel群，因此上述乘法的因子也满足Abel群中的交换律和结合律：
n1*(n2P) = n_2(n1*P) = (n1n_2)P
(n_1n2)*n3P = n_1(n2*n3)*P

椭圆曲线之所以能用于公钥密码体系，是基于所谓 椭圆曲线难题 :
Q = k*P

• 已知点 P ，和因子 k ，求点的乘积 Q ，在运算上是简单的（无非是求交点、取模运算等）；
• 反之，若已知点 P , Q ，求乘法因子k，在计算上是困难的，目前还没有多项式时间的解法。

这种 单向门陷函数(Trapdoor function) 特性，与RSA一样，可以用于公钥密码体系。可以将{P, kP}公开作为公钥，乘法因子k作为私钥。

由于参数和变元都定义在有限域中，在运算过程中都对大素数p取模，因此有限域中椭圆曲线上点的个数是有限的。对于点 P 进行乘法运算，乘数因子从0至p：

P_0 = 0
P_1 = P
P_2 = 2*P
P_i = i*P
P_p = p*P

在上述运算中产生了p+1个点，如果某个因子n满足：
Pn = n*P = 0
这样自n+1起之后的点都会和之前的重合。
P_{n+i }= 0 + Pi =P_i
近世代数已经证明，对于有限域椭圆曲线，这样的n必然是存在的。使n*P = 0的最小的n，称之为椭圆曲线的 阶（Order） ，相应的点P称之为 基点(Genrator) 。这样 Order 可以视作为曲线上对点P运算的 周期 。此外，曲线上点的个数与基点阶的比值称之为 co-factor 。

OpenSSL中的椭圆曲线表示

再来看看素数域椭圆曲线——以 secp256k1 为例，描述这个曲线的参数包括：
- p : 大素数
- a : 曲线方程系数
- b : 曲线方程系数
- x : 基点Generator的x坐标
- y : 基点Generator的y坐标
- order : 曲线的阶Order

取值如下：

/* no seed */
/* p */
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F,
/* a */
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
/* b */
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07,
/* x */
0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95,
0xCE, 0x87, 0x0B, 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9,
0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98,
/* y */
0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc,
0x0e, 0x11, 0x08, 0xa8, 0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19,
0x9c, 0x47, 0xd0, 0x8f, 0xfb, 0x10, 0xd4, 0xb8,
/* order */
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,
0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41

椭圆曲线密码学中所使用的秘钥结构体 ec_key_st 如下：包含公钥、私钥、有限域、点运算函数等

struct ec_key_st {
    const EC_KEY_METHOD *meth;//计算函数
    ENGINE *engine;
    int version;
    EC_GROUP *group;//群
    EC_POINT *pub_key;//公钥
    BIGNUM *priv_key;//私钥
    unsigned int enc_flag;
    point_conversion_form_t conv_form;
    CRYPTO_REF_COUNT references;
    int flags;
    CRYPTO_EX_DATA ex_data;
    CRYPTO_RWLOCK *lock;
};

其中，字段中有限域EC_GROUP结构体如下：

struct ec_group_st {
    const EC_METHOD *meth;      /* 椭圆曲线运算函数 */
    EC_POINT *generator;        /* optional */
    BIGNUM *order, *cofactor;
    ... ...
    BIGNUM *field;
    int poly[6];
    BIGNUM *a, *b;
};

椭圆曲线的加密算法

从公钥密码学角度来看，基于椭圆曲线难题，私钥为本地生成的大数k，公钥则为点k*G。
在椭圆曲线密码学中的数据通常涉及 字符串、大整数、点 三类，其中，字符串和大整数可以相互转换：

BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) //字符串转换为大整数
int BN_bn2bin(const BIGNUM *a, unsigned char *to) //大整数转换为字符串

而大整数和通常可以映射为曲线上某个点的x坐标：

//获取曲线上点point的x坐标(大整数)
int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group,
                                        const EC_POINT *point, BIGNUM *x,
                                        BIGNUM *y, BN_CTX *ctx)
//大整数映射至曲线上点
int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group,
                                        EC_POINT *point, const BIGNUM *x,
                                        const BIGNUM *y, BN_CTX *ctx)

这里打算只举一个最简单的例子，说明基于椭圆曲线加密过程。Alice的私钥为k A，公钥为k A*G。

• Bob将明文m映射至椭圆曲线上一点M。（如何映射？字符串->BigNum->P点x坐标即可）
• Bob随机选取整数r，计算出点R=r*G
• Bob利用Alice的公钥加密消息发往Alice，消息密文结构为 C=(M+rk_AG) ，同时将点 R 也发送给Alice
• Alice收到密文C后，根据公开的点R和自己的私钥k A进行解密：
  M'=C-kAR=M+rk_AR-k_ArG=M

ECDH： 椭圆曲线Diffie-Hellman密钥交换

所谓D-H交换，即两个用户之间安全地交换彼此的密钥，并在后续的传输中使用该密钥对信息加密。
这里先从实际的应用角度出发，讨论一下D-H交换在通信中的一个典型应用场景—— 密钥协商 ：

由于非对称加解密通常运算量都很大，主要用于低频的密钥交换，所生成的共享密钥通常是长期使用的。比如通信双方先使用ECDH交换， 协商出共享密钥PK ，这种协商密钥的过程只需要一次。然后采用 PK 作为密码，使用运算更快的AES、CR4、DES等传统的对称加密算法，对每次数据报文进行加解密。

回到D-H交换的具体过程中来。在椭圆曲线加密过程中，曲线参数是公开的，包括基点G和阶Order。对于用户A和B：

• A选取一个随机数 rA 作为私钥， rA*G 作为公钥。其中G即曲线的基点。由椭圆曲线难题可知，其他用户很难反求私钥 rA 。
• B同理，其私钥为 rB ，公钥为 rB*G 。
• A、B分别向对方发送公钥。
• A、B收到的对方公钥后，乘以自己的私钥，本地计算出双方的共享密钥对。此时A计算得出PKA=rA (rB G);B计算得出PKB=rB (rA G)
• 根据Abel乘法运算的结合律，当基点G相同时，PKA=PKB。D-H交换通过。

ECDH密钥交换过程如下图所示

最终，A、B双方所生成的共享密钥PK包含彼此的私钥信息，成功交换了密钥信息。A、B之间采用PK作为密钥，使用对称加解密技术发送报文，进行加密传输。

其实D-H交换算法过程很简短，就是私钥之积乘以基点G，来看看共享密钥计算函数的代码：

openssl/crypto/ec/Ecdh_ossl.c

int ecdh_simple_compute_key(unsigned char **pout, size_t *poutlen,
                            const EC_POINT *pub_key, const EC_KEY *ecdh)
{        ... ...
    if (!EC_POINT_mul(group, tmp, NULL, pub_key, priv_key, ctx)) 
        ECerr(EC_F_ECDH_SIMPLE_COMPUTE_KEY, EC_R_POINT_ARITHMETIC_FAILURE);
        goto err;
    ... ...
}

参数说明:

• pout: 输出，即最后的共享密钥字符串
• poutlen: 输出长度
• pub_key: 收到的对端用户公钥
• ecdh: 本方的密钥结构体，包含公钥和私钥、有限域等

针对D-H交换的中间人攻击问题

从私钥保护的目的来看，D-H密钥交换是安全的，整个交换过程中不会泄露用户的私钥。但是D-H交换也存在局限性，比如要求整个交换过程的信道可信，同时交换双方必须在线，以保证消息可达。

D-H交换最大的局限性在于不能防范 中间人攻击 ，这里仍然可以举一个例子。在不可靠信道上，假设A、B之间存在一个中间人C，可以窃听到A、B之间的信道消息，尽管信道上传输的都是公钥，但C确实能成功欺骗A、B双方:

A、B在D-H交换过程发送的公钥信息被用户C窃听。C分别与A、B交换了私钥并生成共享密钥对PKC_A和PKC_B。这样C就可以与A、B分别进行通信了。A、B对C的窃听一无所知，以为彼此协商出了共享密钥PK=rA*rB*G。而实际上A与C、B与C都分别协商出了PKC A与PKC B。

D-H交换最大的问题，就在于无法鉴别通信的参与方，发送者对信息接受者的身份一无所知。当信道不可靠时，公钥以广播形式在网络中传播，传输路径中的第三方节点可以很容易窃听乃至篡改原有消息。

为克服中间人攻击缺陷，需要引入数字签名和公钥证书机制。

ECDSA: 椭圆曲线签名算法

公钥密码体系中的签名机制是：发送方使用 私钥 对消息进行签名，接收方使用 公钥 验证签名。ECDSA的签名机制比RSA略复杂。这里仍然以消息发送方Alice和接收方Bob为例。

先来看看Alice这边的签名生成过程：

1. Alice的私钥为k A，公钥为k A*G
2. Alice随机选取一个整数k，计算与基点的乘积K=k*G
3. K的横坐标为K x，取其相对于曲线阶order的模结果r，即r=K x(mod order)
4. 计算k基于曲线阶order的乘法逆元k^(-1)
5. Alice对消息m进行Hash得到摘要h
6. 最终的签名为{r,s}，r在第2步已经给出；而Alice根据自己的私钥k A，得到s如下
   s = k^{-1}(h+kAr)(\bmod order)
7. 根据模的乘法逆元性质，上式左右各乘以k，可得：
   sk= (h+k_Ar）(\bmod order)

Bob收到消息m和签名{r,s}后，进行签名验证：

1. Bob计算得出s基于曲线阶order的乘法逆元 s^{-1}
2. Bob对所得消息进行Hash，得到h'
3. 计算出 u_1=h's^{-1}
4. 计算出 u_2=rs^{-1}
5. 根据Alice的公钥(k A*G)，得到点 P= u1G+u_2k_AG ，展开得：
   P=h's^{-1}G+rs^{-1}k_AG=(h'+k_Ar)s^{-1}G(\bmod order)
6. 当Bob收到的消息未被篡改时，h'=h，则有:
   P=s^{-1}(h+k_Ar)G=s^{-1}(sk)G=kG(\bmod order)
7. 取点P的x坐标P x与签名中的r=K x(mod order)相比 ，相等则签名验证通过。

ECDSA的过程略长，但仍然遵循公钥密码体系中的签名原理。Alice生成的签名中包括自己的私钥，Bob验证签名则只需使用签名和公钥即可解开签名内容，验明正身。

OpenSSL中ECDSA的签名生成过程如下.

openssl/crypto/ec/ecdsa_ossl.c

static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
                            BIGNUM **kinvp, BIGNUM **rp,
                            const unsigned char *dgst, int dlen)

此函数根据消息摘要，生成了签名所需的k^(-1)和r。

进函数内看看，首先这里使用了 BN_generate_dsa_nonce 进行伪随机数k生成。

/* get random k */
            if (dgst != NULL) {
                /* 使用dgst和private key，应用于伪随机数生成器PRNG */
                if (!BN_generate_dsa_nonce
                    (k, order, EC_KEY_get0_private_key(eckey), dgst, dlen,
                     ctx)) {
                    ECerr(EC_F_ECDSA_SIGN_SETUP,
                             EC_R_RANDOM_NUMBER_GENERATION_FAILED);
                    goto err;
                }

k^{-1}和r 的生成如下：

if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
            ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
            goto err;
        if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
            NID_X9_62_prime_field) {
            if (!EC_POINT_get_affine_coordinates_GFp
                (group, tmp_point, X, NULL, ctx)) {
                ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
                goto err;
        /* r = X%order */
        if (!BN_nnmod(r, X, order, ctx)) {
            ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
            goto err;
    while (BN_is_zero(r));
    /* compute the inverse of k */
    if (EC_GROUP_get_mont_data(group) != NULL) {
    ... ...
        if (!BN_mod_sub(X, order, X, order, ctx)) {
            ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
            goto err;
        BN_set_flags(X, BN_FLG_CONSTTIME);
       ... ...
        if (!BN_mod_inverse(k, k, order, ctx)) {
            ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
            goto err;
    }

最终，生成签名的接口为：

ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len,