思享工具箱

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

摘要：
有限域上的椭圆曲线这里，省略了诸如有限域和射影几何之类的数学背景。首先，给出了实数域空间中椭圆曲线的一般形式：[y^2z+Axyz+a3yz^2=x^3+a2x^2z+a_4xz^2+a_6z^3]在上述公式中，（x，y，z）是变量。如果（z＝1），我们可以得到平面上的椭圆曲线（Ep（x，y））。将平面上椭圆曲线上的点P、Q、R和关于x轴对称的点P’、Q’、R’相加：[Add:P+Q=R’]

有限域上的椭圆曲线

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

[y^2z + a_1xyz + a_3yz^2 = x^3 + a_2x^2z + a_4xz^2 + a_6z^3 ]

以上式子中，(x,y,z)均为变元。而令(z=1), 则可以得到平面上的椭圆曲线(Ep(x,y))。

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

[Add : P+Q = R' ]

image

从几何上看点的加法：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)(mod p) ]

[4a^3 + 27b^2 ot= 0 (mod p) ]

通常p是一个大素数。不同于实数域上点的运算有直观的几何形象，有限域中点P(x, y)的运算在等号两侧都需要取模（mod p）。此外一个显而易见的性质是：由于曲线的各个参数定义在有限域上，符合Abel群，因此上述乘法的因子也满足Abel群中的交换律和结合律：

[n_1*(n_2*P) = n_2*(n_1*P) = (n_1*n_2)P ]

[(n_1*n_2)*n_3*P = n_1*(n_2*n_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+r*k_A*G))，同时将点R也发送给Alice
  • Alice收到密文C后，根据公开的点R和自己的私钥k_A进行解密：

[M'=C-k_A*R=M+r*k_A*R-k_A*r*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*(rB*G));B计算得出(PKB=rB*(rA*G))
  • 根据Abel乘法运算的结合律，当基点G相同时，PKA=PKB。D-H交换通过。

ECDH密钥交换过程如下图所示
image
最终，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双方:
image

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_AG)
  2. Alice随机选取一个整数(k)，计算与基点的乘积(K=kG)
  3. K的横坐标为(K_x)，取其相对于曲线阶order的模结果r，即(r=K_x(mod order))
  4. 计算k基于曲线阶order的乘法逆元(k^{-1}(mod order))
  5. Alice对消息(m)进行Hash得到摘要(h)
  6. 最终的签名为{(r,s)}，(r)在第2步已经给出；而Alice根据自己的私钥(k_A)，得到(s)如下

[s = k^{-1}(h+k_Ar)(mod order) ]

根据模的乘法逆元性质，上式左右各乘以k，可得：

[sk= (h+k_Ar）(mod 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_AG))，得到点(P= u_1G+u_2k_A*G)，展开得：

[P=h's^{-1}G+rs^{-1}k_AG=(h'+k_Ar)s^{-1}G(mod order) ]

  1. 当Bob收到的消息未被篡改时，h'=h，则有:

[P=s^{-1}(h+k_Ar)G=s^{-1}(sk)G=kG(mod order) ]

  1. 取点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#公钥算法#对称密钥#const#ec | 浏览：748 | 发布日期：

免责声明：文章转载自《椭圆曲线密码学在OpenSSL中的实现》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇接口中转stream传输 request/response【Unity3D与23种设计模式】桥接模式（Bridge）下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

es6常用方法

一、let 和 constlet 声明变量，只在所在的块区有效，不存在变量提升；var 存在变 量提升const 声明常量，只在所在块区有效 二、变量的解构赋值1.数组的解构赋值let [a, b, c] = [1, 2, 3];// a=1;b=2;c=3 2.对象的解构赋值let { foo, bar } = { foo: "aaa", bar: "b...

互动直播中的前端技术——即时通讯

前言 在疫情期间，上班族开启了远程办公，体验了各种远程办公软件。老师做起了主播，学生们感受到了被钉钉支配的恐惧，歌手们开启了在线演唱会，许多综艺节目也变成了在线直播。在这全民互动直播的时期，我们来聊聊互动直播中的即时通讯技术在前端中的使用。 即时通讯技术 即时通讯（Instant Messaging，简称IM）是一个实时通信系统，允许两人或多人使用网络实时...

C#窗体如何通过keybd_event()函数模拟键盘按键（组合键）产生事件

如何模拟键盘按键触发产生的事件，比如模拟按下Alt + F4 关闭当前程序，Ctrl+Shift 切换输入法等 可以通过win32api 键盘事件 keybd_event() 来实现 1、定义键盘按键对应得键码 #region bVk参数 常量定义 public const byte vbKeyLButton = 0x1;...

CFileFind类的详解以及应用实例

CFileFind类在afx.h头文件中声明。功能：执行本地文件的查找,支持通配符。类的成员函数：1、查找操作类： 1 //搜索目录下指定的文件，成功返回非0。第二个参数不必理会2 virtual BOOL FindFile(LPCTSTR pstrName = NULL,DWORD dwUnused = 0); 3 virtual BOOL F...

INNO Setup 使用笔记

INNO Setup 使用笔记[Setup] AppName={#MyAppName} AppVerName={#MyAppVerName} AppPublisher={#MyAppPublisher} AppPublisherURL={#MyAppURL} AppSupportURL={#MyAppURL} AppUpdatesURL={#MyAppUR...

c# wpf 条状刻度线，仪表盘的做法

网上看到 https://www.cnblogs.com/congqiandehoulai/p/12733245.html  照着例子做，一直不行，最后发现了问题。 1 需要添加两个引用 Microsoft.Expression.ControlsMicrosoft.Expression.Drawing 这两个dll需要引用到项目里，可以在自己的电脑里查到...

最新文章

随机推荐

思享工具箱导航