OpenSSL:获取椭圆曲线上的随机点

Question

我有一个初始化的椭圆曲线 (EC_GROUP)。有没有办法用仿射坐标得到随机点？？

这就是我定义曲线的方式:

BN_CTX *ctx;
EC_GROUP *curve;
BIGNUM *a, *b, *p, *order, *x, *y, *z;
EC_POINT *generator;

/* Binary data for the curve parameters */
unsigned char a_bin[28] =
        {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
        0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,
        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE};
unsigned char b_bin[28] =
        {0xB4,0x05,0x0A,0x85,0x0C,0x04,0xB3,0xAB,0xF5,0x41,
        0x32,0x56,0x50,0x44,0xB0,0xB7,0xD7,0xBF,0xD8,0xBA,
        0x27,0x0B,0x39,0x43,0x23,0x55,0xFF,0xB4};
unsigned char p_bin[28] =
        {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
        0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
        0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01};
unsigned char order_bin[28] =
        {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
        0xFF,0xFF,0xFF,0xFF,0x16,0xA2,0xE0,0xB8,0xF0,0x3E,
        0x13,0xDD,0x29,0x45,0x5C,0x5C,0x2A,0x3D };
unsigned char x_bin[28] =
        {0xB7,0x0E,0x0C,0xBD,0x6B,0xB4,0xBF,0x7F,0x32,0x13,
        0x90,0xB9,0x4A,0x03,0xC1,0xD3,0x56,0xC2,0x11,0x22,
        0x34,0x32,0x80,0xD6,0x11,0x5C,0x1D,0x21};
unsigned char y_bin[28] =
        {0xbd,0x37,0x63,0x88,0xb5,0xf7,0x23,0xfb,0x4c,0x22,
        0xdf,0xe6,0xcd,0x43,0x75,0xa0,0x5a,0x07,0x47,0x64,
        0x44,0xd5,0x81,0x99,0x85,0x00,0x7e,0x34};

unsigned char z_bin[28] = 
        {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
        0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
        0x0,0x0,0x0};

/* Set up the BN_CTX */
if(NULL == (ctx = BN_CTX_new())) handleErrors();

/* Set the values for the various parameters */
if(NULL == (a = BN_bin2bn(a_bin, 28, NULL))) handleErrors();
if(NULL == (b = BN_bin2bn(b_bin, 28, NULL))) handleErrors();
if(NULL == (p = BN_bin2bn(p_bin, 28, NULL))) handleErrors();
if(NULL == (order = BN_bin2bn(order_bin, 28, NULL))) handleErrors();
if(NULL == (x = BN_bin2bn(x_bin, 28, NULL))) handleErrors();
if(NULL == (y = BN_bin2bn(y_bin, 28, NULL))) handleErrors();
if(NULL == (z = BN_bin2bn(z_bin, 28, NULL))) handleErrors();

/* Create the curve */
if(NULL == (curve = EC_GROUP_new_curve_GFp(p, a, b, ctx))) handleErrors();

//if(EC_PO)

/* Create the generator */
if(NULL == (generator = EC_POINT_new(curve))) handleErrors();
if(1 != EC_POINT_set_affine_coordinates_GFp(curve, generator, x, y, ctx))
        handleErrors();

/* Set the generator and the order */
if(1 != EC_GROUP_set_generator(curve, generator, order, NULL))
        handleErrors();

现在我需要这条曲线的一些随机点来实现优化计算，但是我找不到获取随机点的方法。

Answer 1

你要做的是:

1. 初始化一个 EC_POINT P 作为生成器。
2. 找到一个随机 bignum k 使得 0 <k < order (of the group).
3. 做标量乘法得到随机点 R = kP

这是我刚刚编写的一个函数，它将在给定的 EC_GROUP 上获得随机 EC_POINT。结果存储在 EC_POINT r 中。 ctx 可以为 NULL:

int EC_POINT_get_random(const EC_GROUP *group, EC_POINT *r, BN_CTX *ctx) {
    int ok = 0;
    BN_CTX *new_ctx = NULL;
    BIGNUM *k; 

    if (ctx == NULL) {
        ctx = new_ctx = BN_CTX_new();
        if (ctx == NULL)
            return -1; 
    }   
    k = BN_new();

    if (!EC_GROUP_get_order(group, k, ctx)) goto err;
    if (!BN_pseudo_rand(k, BN_num_bits(k), 0, 0)) goto err;
    if (!EC_POINT_mul(group,r,k,NULL,NULL,ctx)) goto err;

    ok = 1;
err:
    if (k) 
        BN_free(k);
    if (new_ctx != NULL)
        BN_CTX_free(new_ctx);
    return ok; 
}   

下面是一个简单的测试主体(写得不好):

int main() {
    BN_CTX *ctx;
    BIGNUM *x, *y; 
    EC_GROUP *group;
    EC_POINT *P; 

    ctx = BN_CTX_new();
    x = BN_new(); y = BN_new();

    group = EC_GROUP_new_by_curve_name(NID_secp521r1); // take curve SN_secp521r1 as sample curve
    P = EC_POINT_new(group);
    EC_POINT_get_random(group,P,ctx);   

    // print (x,y) of P
    if (!EC_POINT_is_on_curve(group,P,ctx)) return -1; 
    if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) return -1; 
    fprintf(stdout, "\nRandom Elliptic Curve Point P:\n     x = 0x");
    BN_print_fp(stdout, x); 
    fprintf(stdout, "\n     y = 0x");
    BN_print_fp(stdout, y); 
    fprintf(stdout, "\n");
return 0;
}