【零依赖实现国密算法C语言版】国密算法补充之点的压缩与解压缩

约 902 字大约 3 分钟

2023-05-13

点压缩

根据规范文档可知，64字节的点经过压缩后，变成33字节。其组成由原来的x||y变成yTile||x，其中yTile为y最右边的一个比特。

那么点压缩的实现就很简单了，只要计算y最右边的一个比特即可。

/**
 * 点压缩算法，当需要压缩时，压缩结果表示为：
 * 0x02 + yTile || x
 * 当不需要压缩时，结果为：
 * 0x04 || x || y
 * @param p 待压缩的点
 * @param out 压缩后存储数据的缓存区，压缩时大小为33字节，不压缩时大小为65字节
 * @param compressed 1为需要压缩，非1表示不需要压缩
 */
void gm_point_encode(const gm_point_t *p, uint8_t * out, int compressed);

接下来看实现后的代码：

void gm_point_encode(const gm_point_t *p, uint8_t * out, int compressed) {
    if(compressed) {
        gm_bn_t x, y;
        gm_point_get_xy(p, x, y);

        out[0] = 0x02 + (y[0] & 0x01);
        gm_bn_to_bytes(x, out + 1);
    } else {
        out[0] = 0x04;
        gm_point_to_bytes(p, out + 1);
    }
}

点解压缩

计算方法是

计算 $α=(x ^ 3 + ax + b) \pmod {p}$
计算α的平方根β，若“不存在平方根”，则报错
若β的最右边比特等于yTile，则置y=β; 否则置y = p − β

规范文档中，平方根的计算，我没看懂，看懂的伙伴可以交互交流一下，我参照mbedTLS的公式来实现，公式为：

$β = sqrt(x^3 + ax + b) = (x^3 + ax + b) ^ {(P + 1) / 4} \pmod {p}$

有的公式，代码实现起来也就简单了，就直接套公式上代码了

// 蒙哥马利域, SM2 A
static const gm_bn_t GM_BN_MONT_A = {
    0xFFFFFFFC, 0xFFFFFFFF, 0x00000003, 0xFFFFFFFC,
    0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFB
};

// 蒙哥马利域, SM2 B
static const gm_bn_t GM_BN_MONT_B = {
    0x2BC0DD42, 0x90D23063, 0xE9B537AB, 0x71CF379A, 
    0x5EA51C3C, 0x52798150, 0xBA20E2C8, 0x240FE188
};

/**
 * 点解压缩
 * @param p 用于存储结果
 * @param in 未压缩的点（65字节）或压缩的点（33字节）
 */
void gm_point_decode(const gm_point_t *p, uint8_t * in) {
    if(in[0] == 0x04) {
        // 未压缩点，直接转化
        gm_point_from_bytes(p, in + 1);
    }else if(in[0] == 0x02 || in[0] == 0x03) {
        int yTile = in[0] - 0x02;
        gm_bn_t x, r;

        // 预计算的 (P + 1) / 4
        gm_bn_t padd1shit2 = {
            0x00000000, 0x40000000, 0xC0000000, 0xFFFFFFFF,
            0xFFFFFFFF, 0xFFFFFFFF, 0xBFFFFFFF, 0x3FFFFFFF
        };

        gm_bn_from_bytes(x, in + 1);
        gm_bn_to_mont(x, x, GM_BN_P);

        // r = x ^ 2
        gm_bn_sqr(r, x, GM_BN_P);

        // r = x^2 + a
        gm_bn_add(r, r, GM_BN_MONT_A, GM_BN_P);

        // r = x^3 + ax
        gm_bn_mont_mul(r, r, x, GM_BN_P);

        // r = x^3 + ax + b
        gm_bn_add(r, r, GM_BN_MONT_B, GM_BN_P);

        // r = sqrt(x^3 + ax + b) = (x^3 + ax + b) ^ ((P + 1) / 4) (mod P)
        gm_bn_exp(r, r, padd1shit2, GM_BN_P);

        gm_bn_from_mont(padd1shit2, r, GM_BN_P);
        if((padd1shit2[0] & 0x01) != yTile) {
            gm_bn_sub(r, GM_BN_P, padd1shit2, GM_BN_P);
            gm_bn_to_mont(r, r, GM_BN_P);
        }

        gm_bn_copy(p->X, x);
        gm_bn_copy(p->Y, r);
        gm_bn_set_mont_one(p->Z);
    }
}

单元测试

测试代码

void test_gm_point_codec() {
    const char * pubks[20] = {
        "04B33C4A2A3E448FD7C584142B51208AEC25C261CE6A0D152E59DD0E9E6D7F2C391729A17E5A5BD110B77F4048CE24744F019576B93A9FAB133DFD7CEC9BB0C125",
        "046E751153A9BB24BF0B1E82D97BEE2802BA413B9AB74424C67C60E7ECFAE3986DB1CD5D2EA988552A44476E8A81BDFDF349397A3428CB0E7E043ABB0A53C925C6",
        "04F604E51419128B82496A16A73261A8B8FD558114DED38EC2F473B65951D0E9C4551645373491EF4FEBD3E7F8CF928990A18A4AE8E6C647F1FC50935B0E93DE81",
        "045E750E935779D356DBA0ADFCAB464F32E8599677AA443DEE30D15C694EBE8C2FB1A38C268FE08FC3460C320C626BA979BA67F2C33513A708D7300435F2C09FD6",
        "04C7B8D81A0169C841F8A1E7BE93802C65539CF20119865208DE3240FAED50D069EF58DF6F258C3DEF7FC559DA5B1D92D45F8B0DDB137A83DD780B0A4D0D298008",
        "048FAAF363E7A60B7FF805E8DF54F2D127C77AAA47A5E292A701F478590CB10F59D839707BB29FDC532202FFCA4C8DCEB582435559C7CCFE303646C4B6F4B16F16",
        "042B247178EEDA7C3E0C3CC4B4E371550557A9958B67A7C06D915AA4C2994DE7E3D395C2B49BD0805E2174D99C5EB30C876E18AC752B47D8FEA0D233F79615E554",
        "04227477E7314280A563498C72CA9467753E9E1D675B0BA291D5979D33DA90329D1DA8DC7390E298330430102856EEB2DA19769F2AA1DAFBFE72044676CA40BDE8",
        "04C6DE4E3EEA2A8DD31CB7CD2D4F6C604A7A0B1398B317A14294C56F4262DC4B59E9853EC2DC4F2D8C29316D2D024AEC4FF02BB365BBB9275CBBDA04807F4770BD",
        "04A86CE03238B8E6312B17A1FC1EA72ACF5139C0438AF14BD9D81EF81A7793830751E6DD136966389AB4EB74E38B1A8DC08FB59F4E36D2421C27B7E58341506396",
        "049CD65465831CC9A93A9EC06AC7C74E5B3865E9D98FD5F1F74289147BB1AFB603A5A9279150C5AEA27F4863CC5F03FF319DEDAC0EC9E501222821490C39F6C99D",
        "04A15F6088144E410F591931426C4162D97B62867E01EC58518F1CDD8D56EA744C5B996F88D65B0D8377AF4784449DCE62E2FF583F5FF64BE1716DFDE64C4DE954",
        "04AFC8F02E58C7EC2AD9ED8415EEB074550D93C4A739D902F4678AA10DB515EE553B015517EEA5108195CFF7DB6FE472017CF5C7DA22E0DA65BC8B4659E8159B48",
        "041F356F3D3D002D1F133D5E6718A72AD5EFE1B370E14DDEDF7AF8403C8078AD92377BADEF043B6039B9E1EDDFA503A86C083155AE900D8925718DCA4EBA03214F",
        "047EF7A8592B8058FFA37B760455045A027250C7285800D5C202CD58932246FBD2C0FA144F10B7C0C67B688ECD322A7D62A0947BF306EACD6FD4FC7DF7F5A5DBF6",
        "041352C4274C22B79863BBDD5CE18AD67EDC1BD3ED6723C272E6BD23C6EA22BC1CB0938B6F6693830ABEE380BC5FEDA8B508863E836300F92A5D8B383D173EDDF1",
        "04B6B8F2F865585E397A35AC01FC625002ED4EF34AAB3DC4BF014AB88D067B348A6FF093E492A5D474D6231DD16B252EE0B82BDE8DF05EFC4F67892C16FEA2E521",
        "0446BC59D115B46DCB54F96470E42B2879897268BE2FA525959F29558DD0D2D296955BA4C5C1EB0A8F7AF85B0BE82BF8FABC81142FE45511497D6C725D76EBD91E",
        "040F5049F8335EE7401599E6A97D94481252972879DE02CB3461B648C77DC918C0EED9C57C65CDB005B5D3A43BDDB785770CA859F8D8AC61C2D753C8220D9C4695",
        "0444FBB7B346D70CD8A98954CBE5FC20EE9144731B025CA2E66DCE57501B3B96C785C0376FE94F9AE45D037FEE868449C54345603BCECD6F003DC7D892C5077B2F"
    };

    const char * pubksC[20] = {
        "03B33C4A2A3E448FD7C584142B51208AEC25C261CE6A0D152E59DD0E9E6D7F2C39",
        "026E751153A9BB24BF0B1E82D97BEE2802BA413B9AB74424C67C60E7ECFAE3986D",
        "03F604E51419128B82496A16A73261A8B8FD558114DED38EC2F473B65951D0E9C4",
        "025E750E935779D356DBA0ADFCAB464F32E8599677AA443DEE30D15C694EBE8C2F",
        "02C7B8D81A0169C841F8A1E7BE93802C65539CF20119865208DE3240FAED50D069",
        "028FAAF363E7A60B7FF805E8DF54F2D127C77AAA47A5E292A701F478590CB10F59",
        "022B247178EEDA7C3E0C3CC4B4E371550557A9958B67A7C06D915AA4C2994DE7E3",
        "02227477E7314280A563498C72CA9467753E9E1D675B0BA291D5979D33DA90329D",
        "03C6DE4E3EEA2A8DD31CB7CD2D4F6C604A7A0B1398B317A14294C56F4262DC4B59",
        "02A86CE03238B8E6312B17A1FC1EA72ACF5139C0438AF14BD9D81EF81A77938307",
        "039CD65465831CC9A93A9EC06AC7C74E5B3865E9D98FD5F1F74289147BB1AFB603",
        "02A15F6088144E410F591931426C4162D97B62867E01EC58518F1CDD8D56EA744C",
        "02AFC8F02E58C7EC2AD9ED8415EEB074550D93C4A739D902F4678AA10DB515EE55",
        "031F356F3D3D002D1F133D5E6718A72AD5EFE1B370E14DDEDF7AF8403C8078AD92",
        "027EF7A8592B8058FFA37B760455045A027250C7285800D5C202CD58932246FBD2",
        "031352C4274C22B79863BBDD5CE18AD67EDC1BD3ED6723C272E6BD23C6EA22BC1C",
        "03B6B8F2F865585E397A35AC01FC625002ED4EF34AAB3DC4BF014AB88D067B348A",
        "0246BC59D115B46DCB54F96470E42B2879897268BE2FA525959F29558DD0D2D296",
        "030F5049F8335EE7401599E6A97D94481252972879DE02CB3461B648C77DC918C0",
        "0344FBB7B346D70CD8A98954CBE5FC20EE9144731B025CA2E66DCE57501B3B96C7"
    };
    int i, j;
    unsigned char buf[65] = {0};
    char res[132] = {0};
    gm_point_t p;

    for(i = 0; i < 20; i++) {
        gm_hex2bin(pubks[i], 130, buf);
        gm_point_decode(&p, buf);

        gm_point_encode(&p, buf, 1);
        for (j = 0; j < 33; j++) {
            sprintf(res + j * 2, "%02X", (buf[j] & 0x0FF));
        }
        res[66] = 0;
        if(strcmp(res, pubksC[i]) != 0) {
            break;
        }

        gm_hex2bin(pubksC[i], 66, buf);
        gm_point_decode(&p, buf);

        gm_point_encode(&p, buf, 0);
        for (j = 0; j < 65; j++) {
            sprintf(res + j * 2, "%02X", (buf[j] & 0x0FF));
        }
        res[130] = 0;
        if(strcmp(res, pubks[i]) != 0) {
            break;
        }
    }
    if(i != 20) {
        printf("test result: fail\n");
    }else {
        printf("test result: ok\n");
    }
}

main函数增加：

if(strcmp(argv[1], "gm_point_codec") == 0) {
    test_gm_point_codec();
}

测试结果：

saintdeMacBook-Pro:c saint$ time ./gm_test gm_point_codec
test result: ok

real	0m0.012s
user	0m0.008s
sys	0m0.002s

注意

通过这篇本章可知，验签算法，最好用未压缩的点，要不解压还要计算，损耗性能。

交通部标准二维码中存放的就是压缩后的公钥。

国密SM2

国密SM3

国密SM4

算法补充

【零依赖实现国密算法C语言版】国密算法补充之点的压缩与解压缩

点压缩

点解压缩

单元测试