椭圆曲线密码学在OpenSSL中的实现

有限域上的椭圆曲线
OpenSSL中的椭圆曲线表示
椭圆曲线的加密算法
ECDH：椭圆曲线Diffie-Hellman密钥交换
针对D-H交换的中间人攻击问题
ECDSA: 椭圆曲线签名算法

有限域上的椭圆曲线

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

y^2z + a_1xyz + a_3yz^2 = x^3 + a_2x^2z + a_4xz^2 + a_6*z^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 = left (x^3 + ax + b)( mod p)

4(a^3) + 27(b^2) != 0 ( mod p) 通常p是一个大素数。不同于实数域上点的运算有直观的几何形象，有限域中点P(x, y)的运算在等号两侧都需要取模（mod p）。此外一个显而易见的性质是：由于曲线的各个参数定义在有限域上，符合Abel群，因此上述乘法的因子也满足Abel群中的交换律和结合律： n_1(n_2P) = n_2(n_1P) = (n_1n_2)P (n_1n_2)n_3P = n_1(n_2n_3)*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满足： P_n = n*P = 0 这样自n+1起之后的点都会和之前的重合。 P_n+1 = 0 + P =P, P_n+i = 0 + P_i =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-k_AR=M+rk_AR-k_Ar*G=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(rBG);B计算得出PKB=rB(rAG)
根据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这边的签名生成过程：

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

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

Bob计算得出s基于曲线阶order的乘法逆元s^(-1)
Bob对所得消息进行Hash，得到h’
计算出u_1=h’*s^(-1)
计算出u_2=r*s^(-1)
根据Alice的公钥(k_AG)，得到点P= u_1G+u_2k_AG，展开得： P=h’s^(-1)G+rs^(-1)k_AG=(h’+k_Ar)s^(-1)G(mod order)
当Bob收到的消息未被篡改时，h’=h，则有: P=s^(-1)(h+k_Ar)G=s^(-1)(sk)G=k*G(mod order)
取点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 */
        do
            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,
                               const BIGNUM *in_kinv, const BIGNUM *in_r,
                               EC_KEY *eckey)

此函数使用ecdsa_sign_setup 中的k^(-1)和r 产生了最终的签名，结构体为：

struct ECDSA_SIG_st {
    BIGNUM *r;
    BIGNUM *s;
};

验证签名的过程在函数

int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len,
                      const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)

与之前分析的一致。值得一提的是对于验证中的点P= u_1G+u_2(k_AG)，需要判断是否为平面上的零点/无穷远点，若是则验证失败，不能进行下一步取横坐标的操作。

椭圆曲线密码学在OpenSSL中的实现

有限域上的椭圆曲线

OpenSSL中的椭圆曲线表示

椭圆曲线的加密算法

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

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

ECDSA: 椭圆曲线签名算法

Similar Posts

Comments

椭圆曲线密码学在OpenSSL中的实现

有限域上的椭圆曲线

OpenSSL中的椭圆曲线表示

椭圆曲线的加密算法

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

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

ECDSA: 椭圆曲线签名算法

Similar Posts

Comments

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