坐标定义

typedef struct {
    gm_bn_t X;
    gm_bn_t Y;
    gm_bn_t Z;
} gm_point_t;

本文采用Jacobian加重射影坐标系表示$F_p$上的一个点。

若z != 0，记$X = x/z^2$，$Y = y/z^3$，则可从Jacobian加重射影坐标表示转化为仿射坐标表示:$Y^2 = X^3 +aX +b$

若z == 0，(1,1,0)对应的仿射坐标系下的点即无穷远点O。

坐标初始化

初始化为无穷远点（蒙哥马利域）

void gm_point_init(gm_point_t *r) {
    memset(r, 0, sizeof(gm_point_t));
    gm_bn_set_mont_one(r->X);
    gm_bn_set_mont_one(r->Y);
}

// 判断是否为无穷远点
int gm_is_at_infinity(const gm_point_t *p) {
    return gm_bn_is_zero(p->Z);
}

坐标转换

set

从仿射坐标转换为Jacobian加重射影坐标，可以将z设置为1（蒙哥马利域），那么转换就变得比较简单，只要将输入转换为蒙哥马利域即可

void gm_point_set_xy(gm_point_t *r, const gm_bn_t x, const gm_bn_t y) {
    gm_bn_to_mont(r->X, x, GM_BN_P);
    gm_bn_to_mont(r->Y, y, GM_BN_P);
    gm_bn_set_mont_one(r->Z);
}

get

由Jacobian加重射影坐标系定义可知，转换公式是：$X = x/z^2$，$Y = y/z^3$

// 停留在蒙哥马利域
static void gm_point_get_xy_mont(const gm_point_t *p, gm_bn_t x, gm_bn_t y) {
    gm_bn_t z_inv;
    if (gm_bn_is_mont_one(p->Z)) {
        if(x) {
            gm_bn_copy(x, p->X);
        }
        if(y) {
            gm_bn_copy(y, p->Y);
        }
    } else {
        // z^{-1}
        gm_bn_inv(z_inv, p->Z, GM_BN_P);
        if (y) {
            gm_bn_mont_mul(y, p->Y, z_inv, GM_BN_P);
        }
        // z^{-2}
        gm_bn_sqr(z_inv, z_inv, GM_BN_P);
        if(x) {
            gm_bn_mont_mul(x, p->X, z_inv, GM_BN_P);
        }
        if (y) {
            gm_bn_mont_mul(y, y, z_inv, GM_BN_P);
        }
    }
}

// 转换为普通大数
void gm_point_get_xy(const gm_point_t *p, gm_bn_t x, gm_bn_t y) {
    gm_point_get_xy_mont(p, x, y);
    if(x) {
        gm_bn_from_mont(x, x, GM_BN_P);
    }
    if(y) {
        gm_bn_from_mont(y, y, GM_BN_P);
    }
}

十六进制

十六进制转换，利用已经实现的大数转换及set函数实现

void gm_point_from_hex(gm_point_t *p, const char hex[128]) {
    gm_bn_t x;
    gm_bn_t y;
    gm_bn_from_hex(x, hex);
    gm_bn_from_hex(y, hex + 64);
    gm_point_set_xy(p, x, y);
}

void gm_point_to_hex(gm_point_t *r, char hex[128]) {
    gm_bn_t x;
    gm_bn_t y;
    gm_point_get_xy(r, x, y);
    gm_bn_to_hex(x, hex);
    gm_bn_to_hex(y, hex + 64);
}

二进制

二进制转换，利用已经实现的大数转换及set函数实现

void gm_point_from_bytes(gm_point_t *r, const uint8_t in[64]) {
    gm_bn_t x;
    gm_bn_t y;
    gm_bn_from_bytes(x, in);
    gm_bn_from_bytes(y, in + 32);
    gm_point_set_xy(r, x, y);
}

void gm_point_to_bytes(const gm_point_t *p, uint8_t out[64]) {
    gm_bn_t x;
    gm_bn_t y;
    gm_point_get_xy(p, x, y);
    gm_bn_to_bytes(x, out);
    gm_bn_to_bytes(y, out + 32);
}

未经本人同意，禁止转载！

上一页大数其它算法

下一页倍点