C ECC 双加

Question

我目前正在使用 Double-And-Add 算法编写 Elliptic Curve Crypto 的 C 代码。我正面临一个我不明白的段错误问题。我希望你们中的某个人可能有想法。

#include "lib/include/gmp.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <openssl/sha.h>

typedef struct{
    mpz_t p;
    mpz_t a;
    mpz_t b;
    mpz_t gx;
    mpz_t gy;
} ECC;

static mpz_t *inverse_y1, *inverse_y2, *tx, *ty;
ECC secp256k1;

/*
 * Initializes the secp256k1 curve.
 */
void initSECP256K1(){
    mpz_set_str(secp256k1.p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
    mpz_init(secp256k1.a);
    mpz_set_str(secp256k1.b, "7", 10);
    mpz_set_str(secp256k1.gx, "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
    mpz_set_str(secp256k1.gy, "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16);
    inverse_y1 = malloc(sizeof(mpz_t));
    inverse_y2 = malloc(sizeof(mpz_t));
    mpz_set_str(*inverse_y1, "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16);
    mpz_set_str(*inverse_y2, "b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777", 16);
}

/*
 * Calculates the s value for ecc point and doubling.
 * s = (y2 - y1) / (x2 - x1) mod p if P != Q
 * s = (3 * x1 ^ 2 + a) / (2 * y1) mod p if P = Q
 * 5 parameters. First one is mpz_t pointer to save the result.
 * The other 4 are of type pointer, representing the coordinates.
 */
void calculate_s(mpz_t *s, mpz_t *x1, mpz_t *y1, mpz_t *x2, mpz_t *y2){
    mpz_t *s1 = malloc(sizeof(mpz_t));
    mpz_init(*s1);
    //Point Addition
    if(mpz_cmp(*x1, *x2) != 0 || mpz_cmp(*y1, *y2) != 0){
        mpz_sub(*s, *y2, *y1);
        mpz_sub(*s1, *x2, *x1);
    }else{
    //Point doubling
        mpz_powm_ui(*s, *x1, 2, secp256k1.p);
        mpz_mul_si(*s, *s, 3);
        mpz_mul_si(*s1, *y1, 2);
    }
    mpz_invert(*s1, *s1, secp256k1.p);
    mpz_mul(*s, *s, *s1);
    mpz_clear(*s1);
}



/*
 * ECC - Point add and Point double
 * It takes 6 parameters, each of type mpz_t pointer.
 * The result is stored in the first two pointers.
 * The third and forth pointer represent the first coordinate.
 * The last two pointer are the second coordinate.
 * It calculates the new coordinates as follows:
 * x3 = s ^ 2 - x1 - x2 mod p
 * y3 = s * (x1 - x3) - y1 mod p
 */
int ecc_papd(mpz_t *x3, mpz_t *y3, mpz_t *x1, mpz_t *y1, mpz_t *x2, mpz_t *y2){
    mpz_t *s = malloc(sizeof(mpz_t));
    mpz_init(*s);
    //calculates s value
    calculate_s(s, x1, y1, x2, y2);
    //x3 = s^2 - x1 - x2 mpd p
    mpz_powm_ui(*x3, *s, 2, secp256k1.p);
    mpz_sub(*x3, *x3, *x1);
    mpz_sub(*x3, *x3, *x2);
    mpz_mod(*x3, *x3, secp256k1.p);
    //y3 = s * (x1 - x3) - y1 mod p
    mpz_sub(*y3, *x1, *x3);
    mpz_mul(*y3, *y3, *s);
    mpz_sub(*y3, *y3, *y1);
    mpz_mod(*y3, *y3, secp256k1.p);
    mpz_clear(*s);
    //check if the result is the infinity point
    if(mpz_cmp(*x1, *x2) == 0){
        if((mpz_cmp(*y1, *inverse_y1) == 0 && mpz_cmp(*y2, *inverse_y2) == 0) ||
               (mpz_cmp(*y2, *inverse_y1) == 0 && mpz_cmp(*y1, *inverse_y2) == 0)){
            //printf("INFINITY");
            return 1;
        }
    }
    return 0;
}


void ecc_double_add(mpz_t *rx, mpz_t *ry, mpz_t *x, mpz_t *y, mpz_t d){
    mpz_t *tx = malloc(sizeof(mpz_t));
    mpz_t *ty = malloc(sizeof(mpz_t));
    mpz_set(*tx, *x);
    mpz_set(*ty, *y);
    //returns the amount of bits the number has
    //sub 2 because it starts to count from 1 and we remove the msb, too.
    int bits = (int) mpz_sizeinbase(d, 2) - 2;
    int bit, infinity = 0;
    //check if bits is -1, (case d=1). If yes, set the base point as solution
    if(bits < 0){
        mpz_set(*rx, *x);
        mpz_set(*ry, *y);
    }
    for(; bits >= 0; bits--){
        bit = mpz_tstbit(d, bits);
        if(infinity == 0){
            infinity = ecc_papd(rx, ry, tx, ty, tx, ty);
            mpz_set(*tx, *rx);
            mpz_set(*ty, *ry);
        }
        //point addition
        if(bit == 1){
            if(infinity == 0){
                infinity = ecc_papd(rx, ry, tx, ty, x, y);
                mpz_set(*tx, *rx);
                mpz_set(*ty, *ry);
            }else{
                mpz_set(*tx, *x);
                mpz_set(*ty, *y);
                infinity = 0;
            }
        }
    }
    free(tx);
    free(ty);
}

int main(){
    initSECP256K1();
    mpz_t *rx = malloc(sizeof(mpz_t));
    mpz_t *ry = malloc(sizeof(mpz_t));
    //tx = malloc(sizeof(mpz_t));
    //ty = malloc(sizeof(mpz_t));
    mpz_t d;
    mpz_init(*rx);
    mpz_init(*ry);
    mpz_init(d);

    int i = 0;
    for(; i < 2; i++){
        gmp_printf ("d %Zd\n", d);
        ecc_double_add(rx, ry, &secp256k1.gx, &secp256k1.gy, d);
        gmp_printf ("R.x %Zx\n", rx);
        gmp_printf ("R.y %Zx\n", ry);
        printf("\n");
        mpz_add_ui(d, d, 1);
    }
    //mpz_clear(*tx);
    //mpz_clear(*ty);
    mpz_clear(*rx);
    mpz_clear(*ry);

    return 0;
}

问题出在 ecc_double_add 函数中，使用 mpz_t *tx 和 mpz_t *ty 变量。当我是运行代码时，我遇到了段错误。因此，我在函数外初始化了变量（在main函数中注释掉）。只要我这样做，它就会起作用。我很困惑，不知道为什么会收到段错误。我的 C 知识不是很好，我正在努力变得更好。感谢您的帮助:)

*编辑：我正在使用 GNU MP 库来完成这项任务，它在这里：https://gmplib.org/

Answer 1

我一直在修修补补，发现是 gmp_printf 函数导致了问题。一旦我将它从 for 循环中删除，代码就可以工作了。我用不带参数的 printf 和 gmp_printf 替换了它，代码开始工作。我不确定为什么 gmp_printf 会出现问题，但我发现了这个：https://gmplib.org/list-archives/gmp-bugs/2011-July/002304.html

我用

替换了 gmp_printf

printf("Result: %s\n", mpz_get_str(NULL, 16, *rx));

这不是一个很好的解决方案，但对于测试来说应该足够了。

C ECC 双加

C ECC Double-And-Add

c

segmentation-fault

elliptic-curve