铜锁支持大数运算硬件加速机制

背景

密码学中的很多算法，如 RSA、Paillier、ECC、EC-ElGamal、Diffie-Hellman 密钥交换等，都涉及大数运算，大素数生成、大数乘法、大数模幂等在加密和解密过程中都是必不可少的运算。加密货币和区块链技术中的密码学算法都依赖于大数运算。我们知道，数字越大，运算速度也越慢，但数字越小就越不安全。所以，RSA 为了安全性，位数要求 2048 位以上，Paillier 与 RSA 类似，推荐位数也是 2048 位以上，随着计算技术的进步和密码学攻击的发展，随着时间的推移，这个推荐位数可能会增加，性能也会受到挑战。

目前硬件的发展速度很快，比如 FPGA、GPU 这些定制的硬件可以用来解决目前大数运算慢的问题，这些硬件有专门的大数运算专用处理器、专用集成电路或者专用的指令集可以加速大数的运算，解放 CPU 的算力，提高整体计算效率。所以铜锁为了支持这些定制的加速硬件提供了加速的机制，在 engine 机制基础上，支持了大数运算相关接口的 hook 机制，让上层应用在能使用铜锁相关算法的时候也能绑定硬件来加速算法的运行速度，提高其业务性能。

实现

核心思想是在BIGNUM相关运算 API 中加入 method 函数，或者称为 hook 函数，如果设置了这些 hook 函数则调用到这些 hook 函数，在这些 hook 函数中可以实现加速逻辑（比如调用硬件 API），需要注意的是，由于这些 method 函数是加在 BN_CTX 上，所以该功能仅对含有BN_CTX参数的 API 有效。

这个机制依靠底层的 engine 框架，只要新增一种类型即可，下面是数据结构的核心改动（主要是宏 OPENSSL_NO_BN_METHOD包起来的部分）：

/* The opaque BN_CTX type */
struct bignum_ctx {
    /* The bignum bundles */
    BN_POOL pool;
    /* The "stack frames", if you will */
    BN_STACK stack;
    /* The number of bignums currently assigned */
    unsigned int used;
    /* Depth of stack overflow */
    int err_stack;
    /* Block "gets" until an "end" (compatibility behaviour) */
    int too_many;
    /* Flags. */
    int flags;
    /* The library context */
    OSSL_LIB_CTX *libctx;
# ifndef OPENSSL_NO_BN_METHOD
    ENGINE *engine;
    const BN_METHOD *bn_meth;
# endif
};

# ifndef OPENSSL_NO_BN_METHOD
/* 用户可以在自己 engine 中设置下面支持的 hook 函数 */
struct bn_method_st {
    char *name;
    /* 模加 */
    int (*mod_add)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
    /* 模减 */
    int (*mod_sub)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
    /* 模乘 */
    int (*mod_mul)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
    /* 模幂 */
    int (*mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx);
    /* 模平方 */
    int (*mod_sqr)(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx);
    /* 模开根号 */
    BIGNUM *(*mod_sqrt)(BIGNUM *r, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
    /* 模逆 */
    BIGNUM *(*mod_inverse)(BIGNUM *r, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
    /* 除法 */
    int (*div)(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx);
};
# endif

通过如下 API 可以给 BN_CTX设置 engine 和 method：

/* 创建 method */
BN_METHOD *BN_METHOD_new(const char *name);
/* 释放 method */
void BN_METHOD_free(BN_METHOD *meth);

/* 给 BN_CTX 设置 engine */
int BN_CTX_set_engine(BN_CTX *ctx, ENGINE *engine);
/* 给 BN_CTX 设置 method */
int BN_CTX_set_method(BN_CTX *ctx, const BN_METHOD *method);

/* 绑定 engine 和 method，一般是在 engine 模块中调用 */
int ENGINE_set_bn_meth(ENGINE *e, const BN_METHOD *bn_meth);

通过如下 API 可以设置 hook 函数：

void BN_METHOD_set_add(BN_METHOD *meth,
                       int (*mod_add)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                                      const BIGNUM *m, BN_CTX *ctx));

void BN_METHOD_set_sub(BN_METHOD *meth,
                       int (*mod_sub)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                                      const BIGNUM *m, BN_CTX *ctx));

void BN_METHOD_set_mul(BN_METHOD *meth,
                       int (*mod_mul)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                                      const BIGNUM *m, BN_CTX *ctx));

void BN_METHOD_set_exp(BN_METHOD *meth,
                       int (*mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
                                      const BIGNUM *m, BN_CTX *ctx));

void BN_METHOD_set_sqr(BN_METHOD *meth,
                       int (*mod_sqr)(BIGNUM *r, const BIGNUM *a, const BIGNUM *m,
                                      BN_CTX *ctx));

void BN_METHOD_set_sqrt(BN_METHOD *meth,
                        BIGNUM *(*mod_sqrt)(BIGNUM *r, const BIGNUM *a,
                                            const BIGNUM *n, BN_CTX *ctx));

void BN_METHOD_set_inverse(BN_METHOD *meth,
                           BIGNUM *(*mod_inverse)(BIGNUM *r, const BIGNUM *a,
                                                  const BIGNUM *n, BN_CTX *ctx));
void BN_METHOD_set_div(BN_METHOD *meth,
                       int (*div)(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
                                  const BIGNUM *d, BN_CTX *ctx));

例子

engine 例子

下面是一个实现模加、模减、模乘、模幂操作后再加一的例子：

#include <stdio.h>
#include <string.h>

#include <openssl/engine.h>
#include <openssl/crypto.h>
#include <openssl/bn.h>

static const char *engine_bntest_id = "bntest";
static const char *engine_bntest_name = "Tongsuo bn_method engine support";

static BN_METHOD *bn_method = NULL;
static BN_CTX *bn_ctx = NULL;

static int bntest_destroy(ENGINE *e);
static int bntest_init(ENGINE *e);
static int bntest_finish(ENGINE *e);

#ifndef OPENSSL_NO_BN_METHOD
static int bn_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
{
    int ret = 0;
    ret = m ? BN_mod_add(r, a, b, m, bn_ctx) : BN_add(r, a, b);
    BN_add_word(r, 1);
    return ret;
}

static int bn_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
{
    int ret = 0;
    ret = m ? BN_mod_sub(r, a, b, m, bn_ctx) : BN_sub(r, a, b);
    BN_add_word(r, 1);
    return ret;
}

static int bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
{
    int ret = 0;

    ret = m ? BN_mod_mul(r, a, b, m, bn_ctx) : BN_mul(r, a, b, bn_ctx);

    BN_add_word(r, 1);
    return ret;
}

static int bn_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx)
{
    int ret = 0;
    ret = BN_mod_exp(r, a, p, m, bn_ctx);
    BN_add_word(r, 1);
    return ret;
}
#endif

static int bind_bntest(ENGINE *e)
{
    bn_method = BN_METHOD_new("test");
    if (bn_method == NULL)
        return 0;

    bn_ctx = BN_CTX_new();
    if (bn_ctx == NULL)
        return 0;

    if (!ENGINE_set_id(e, engine_bntest_id)
        || !ENGINE_set_name(e, engine_bntest_name)
#ifndef OPENSSL_NO_BN_METHOD
        || !ENGINE_set_bn_meth(e, bn_method)
#endif
        || !ENGINE_set_destroy_function(e, bntest_destroy)
        || !ENGINE_set_init_function(e, bntest_init)
        || !ENGINE_set_finish_function(e, bntest_finish)) {
        return 0;
    }

    return 1;
}

static int bind_helper(ENGINE *e, const char *id)
{
    if (id && (strcmp(id, engine_bntest_id) != 0))
        return 0;
    if (!bind_bntest(e))
        return 0;
    return 1;
}

static int bntest_init(ENGINE *e)
{
#ifndef OPENSSL_NO_BN_METHOD
    BN_METHOD_set_add(bn_method, bn_add);
    BN_METHOD_set_sub(bn_method, bn_sub);
    BN_METHOD_set_mul(bn_method, bn_mul);
    BN_METHOD_set_exp(bn_method, bn_exp);
#endif

    return 1;
}

static int bntest_finish(ENGINE *e)
{
    return 1;
}

static int bntest_destroy(ENGINE *e)
{
    BN_CTX_free(bn_ctx);
    BN_METHOD_free(bn_method);
    return 1;
}

IMPLEMENT_DYNAMIC_CHECK_FN()
IMPLEMENT_DYNAMIC_BIND_FN(bind_helper)

调用例子

/*
 * Copyright 2023 The Tongsuo Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://github.com/Tongsuo-Project/Tongsuo/blob/master/LICENSE.txt
 */

#include <stdio.h>
#include <string.h>
#include <openssl/bn.h>
#include <openssl/bio.h>

#ifndef OPENSSL_NO_ENGINE
# include <openssl/engine.h>
#endif

#ifndef OPENSSL_NO_ENGINE
static ENGINE *e;
#endif

static const char *hex_numbers[] = {
    "10",
    "02",
    "FF",
};

void bn_print(BIO *bio, const BIGNUM *n, const char *name)
{
    BIO *b = NULL;

    if (bio == NULL) {
        bio = b = BIO_new(BIO_s_file());
        BIO_set_fp(bio, stderr, BIO_NOCLOSE);
    }

    BIO_printf(bio, "%s = 0x", name);
    BN_print(bio, n);
    BIO_printf(bio, "\n");

    BIO_free(b);
}

int main(int argc, char *argv[])
{
    int ret = 0, load_engine = 0;
    BN_CTX *ctx = NULL;
    BIGNUM *a, *b, *m, *r;

	if (argc == 2 && strcmp(argv[1], "1") == 0) {
		load_engine = 1;
	}

#ifndef OPENSSL_NO_ENGINE
    if (load_engine && (e = ENGINE_by_id("bntest")) == NULL) {
        fprintf(stderr, "Can't load bntest engine");
    }
#endif

    ctx = BN_CTX_new();
    if (ctx == NULL) {
        goto err;
    }

    BN_CTX_start(ctx);
    a = BN_CTX_get(ctx);
    b = BN_CTX_get(ctx);
    m = BN_CTX_get(ctx);
    r = BN_CTX_get(ctx);
    if (r == NULL) {
        goto err;
	}

#ifndef OPENSSL_NO_ENGINE
    if (load_engine && !BN_CTX_set_engine(ctx, e)) {
        goto err;
	}
#endif

    BN_hex2bn(&a, hex_numbers[0]);
    BN_hex2bn(&b, hex_numbers[1]);
    BN_hex2bn(&m, hex_numbers[2]);

    bn_print(NULL, a, "a");
    bn_print(NULL, b, "b");
    bn_print(NULL, m, "m");

    BN_mul(r, a, b, ctx);
    bn_print(NULL, r, "a*b");

    BN_exp(r, a, b, ctx);
    bn_print(NULL, r, "a^b");

    BN_mod_add(r, a, b, m, ctx);
    bn_print(NULL, r, "a+b mod m");

    BN_mod_sub(r, a, b, m, ctx);
    bn_print(NULL, r, "a-b mod m");

    BN_mod_mul(r, a, b, m, ctx);
    bn_print(NULL, r, "a*b mod m");

    BN_mod_exp(r, a, b, m, ctx);
    bn_print(NULL, r, "a^b mod m");

    ret = 1;
err:
    BN_CTX_end(ctx);
    BN_CTX_free(ctx);
#ifndef OPENSSL_NO_ENGINE
    ENGINE_free(e);
#endif
    return ret;
}

编译&运行

• 编译 engine

$ gcc -shared -fPIC -o bntest.so ./bntest.c -I/opt/tongsuo-debug/include -L/opt/tongsuo-debug/lib -lcrypto -Wl,-rpath -Wl,/opt/tongsuo-debug/lib

• 编译 test

$ gcc -Wall -g -o test test.c -I/opt/tongsuo-debug/include -L/opt/tongsuo-debug/lib -lcrypto -Wl,-rpath -Wl,/opt/tongsuo-debug/lib

• 运行 test

$ ./test
a = 0x10
b = 0x2
m = 0xFF
a*b = 0x20
a^b = 0x100
a+b mod m = 0x12
a-b mod m = 0xE
a*b mod m = 0x20
a^b mod m = 0x1

$ ./test 1
a = 0x10
b = 0x2
m = 0xFF
a*b = 0x21
a^b = 0x101
a+b mod m = 0x13
a-b mod m = 0xF
a*b mod m = 0x21
a^b mod m = 0x2

从上述运行结果可看出，当不加载 bntest engine 时，a 和 b 的乘、幂、模加、模减、模乘、模幂运算均正确，当加载了 bntest engine 后，这些运算的结果均已自动加了 1，说明 bntest engine 发挥了作用，我们可以通过这种方式在 bntest engine 调用硬件的 api 来实现大数运算的加速。