c - Shamir secret 共享的 OpenSSL 实现

Question

我正在尝试使用 OpenSSL 实现 Shamir secret 共享。我在解密消息时遇到了很多麻烦!

我尝试了几种解密实现，这两种都是: http://www.cs.cornell.edu/courses/cs754/2001fa/307.pdf

还有这个(引用了上面的论文，但使用了不同的方法):

(请注意，我知道计算 u2 时存在拼写错误)

我相信我的问题可能是在使用 BIGNUM 值表示关键数字对 ik/(ik-ij) 进行拉格朗日插值时出现精度损失。我编写了一个小函数，用于将 int(如关键数字)转换为 BIGNUM 值。

我不会为您提供 key 生成代码，因为我非常确定它可以正常工作。以下是我链接的 JPEG(不是 PDF)的实现:

int i;
for (i = 0; i < 3; i++) {
    aij[i] = BN_new();
    BN_mod_exp(aij[i], c.c1, key[i].key, p, ctx);
}


BIGNUM *ik = BN_new();
BIGNUM *ij = BN_new();
BIGNUM *denomTmp = BN_new();
BIGNUM *numTmp = BN_new();
BIGNUM *divTmp = BN_new();
BIGNUM *accum = BN_new();

int j, k;

/* Lagrange Interpolation */
for (j = 0; j < 3; j++) {
    BN_one(accum);
    for (k = 0; k < 3; k++) {
        if(j == k) continue;
        else {
            ik = int2BN(key[k].keynum); //int2BN is my function for converting ints to BNs
            ij = int2BN(key[j].keynum);

            BN_sub(denomTmp, ik, ij);

            BN_div(divTmp, NULL, ik, denomTmp, ctx);
            BN_mul(accum, accum, divTmp, ctx);
        }
    }
    cij[j] = BN_new();
    BN_mod(cij[j], accum, q, ctx); // accum % q = cij[j]
}

// Now for the second half...
int a;
u1 = BN_new();
BIGNUM *u1tmp = BN_new();
BN_one(u1);
for (a = 0; a < 3; a++) {
    BN_mod_exp(u1tmp, aij[a], cij[a], p, ctx);
    BN_mod_mul(u1, u1, u1tmp, p, ctx);
}

当我在 cij[] 中输出计算值时，使用键 [2, 4, 5] 时我得到:2, -5, 0。根据我手工计算的结果，它实际上应该是 10/3、5 和 8/3。有什么办法可以解决这个问题吗？

您发现我的代码还存在其他问题吗？提前致谢。

Answer 1

当你进行 sub、div、mul 时，你需要进行模运算。即 BN_mod_sub、分母上的 BN_mod_inverse 和 BN_mod_mul。