cryptography - Shamir secret 共享和拉格朗日插值 (OpenSSL BIGNUM)

Question

我以前发过类似的问题，所以我提前道歉，但我无法找到我在这里出错的地方。

我正在使用 C 中的 OpenSSL 的 BIGNUM 库实现 Shamir secret 共享。

在我做了一轮拉格朗日插值后，我乘以 key * numerator 然后我需要除以分母。

因为没有 BN_mod_div 函数，我改为在分母上使用 BN_mod_inverse()，然后乘法，如下所示:

(键 * 分子) * (分母的倒数)

我注意到，如果我使用 BN_mod_inverse(denom, denom, q, ctx);，那么应该反转的值保持不变:

Round Key: 2E
Numerator: 14
Denominator: 6  **<---- ORIGINAL DENOMINATOR**
Multiply key with numerator: 398 (POSITIVE)
Invert Denominator: 6 (POSITIVE) **<---------- INVERSE IS THE SAME???**
(Key*Numerator)*inv.Denom: 3FC (POSITIVE)

Round Key: 562
Numerator: A
Denominator: -2
Multiply key with numerator: 118 (POSITIVE)
Invert Denominator: -2 (NEGATIVE)
(Key*Numerator)*inv.Denom: 3AC (POSITIVE)

Round Key: 5D1
Numerator: 8
Denominator: 3
Multiply key with numerator: 584 (POSITIVE)
Invert Denominator: 3 (POSITIVE)
(Key*Numerator)*inv.Denom: 4D4 (POSITIVE)
Recovered Key: C4 (POSITIVE)
Key should = 4D2

如果我将其更改为 BN_mod_inverse(newBN, denom, q, ctx); 它就会变成零:

Round Key: 2E
Numerator: 14
Denominator: 6 **<---- ORIGINAL DENOMINATOR**
Multiply key with numerator: 398 (POSITIVE)
Invert Denominator: 0 (NEGATIVE)  **<------------ DENOMINATOR IS NOW ZERO??**
(Key*Numerator)*inv.Denom: 0 (NEGATIVE)

Round Key: 562
Numerator: A
Denominator: -2
Multiply key with numerator: 118 (POSITIVE)
Invert Denominator: 0 (NEGATIVE)
(Key*Numerator)*inv.Denom: 0 (NEGATIVE)

Round Key: 5D1
Numerator: 8
Denominator: 3
Multiply key with numerator: 584 (POSITIVE)
Invert Denominator: 0 (NEGATIVE)
(Key*Numerator)*inv.Denom: 0 (NEGATIVE)
Recovered Key: 0 (NEGATIVE)
Key should = 4D2

无论哪种情况，组合键都是错误的。这里发生了什么？有解决方法吗？

这是我的代码:

BIGNUM *int2BN(int i)
{   
    BIGNUM *tmp = BN_new();
    BN_zero(tmp);

    int g;
    if(i < 0) { //If 'i' is negative
        for (g = 0; g > i; g--) {
            BN_sub(tmp, tmp, one);
        }
    } else { //If 'i' is positive
        for (g = 0; g < i; g++) {
            BN_add(tmp, tmp, one);
        }
    }
    return(tmp);
}   

static void
blah() {
int denomTmp, numTmp, numAccum, denomAccum;
int s, j;   
BIGNUM *accum[3], *bnNum, *bnDenom;
bnNum = BN_new();
bnDenom = BN_new();

/* Lagrange Interpolation */
for (s = 0; s < 3; s++) {
    numAccum = 1;
    denomAccum = 1;
    for (j = 0; j < 3; j++) {
        if(s == j) continue;
        else {
            /* 0 - i[k] = numTmp */
            numTmp = 0 - key[j].keynum;

            /* share - i[k] = denomTmp */
            denomTmp = key[s].keynum - key[j].keynum;

            /* Numerator accumulation: */
            numAccum *= numTmp;

            /* Denominator accumulation: */
            denomAccum *= denomTmp;
        }
    }
    accum[s] = BN_new();
    bnNum = int2BN(numAccum);
    bnDenom = int2BN(denomAccum);

    /* Multiply result by share */
    BN_mod_mul(accum[s], key[s].key, bnNum, q, ctx);

    /* Invert denominator */
    BN_mod_inverse(bnDenom, bnDenom, q, ctx);

    /* Multiply by inverted denominator */
    BN_mod_mul(accum[s], accum[s], bnDenom, q, ctx);

}

int a;
BIGNUM *total = BN_new();
BN_zero(total);
for(a = 0; a < 3; a++) { 
    BN_mod_add(total, total, accum[a], q, ctx);
}   

}

Answer 1

使用 BN_div。余数是模数。即，rem = a % d。

int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx);

BN_div() divides a by d and places the result in dv and the remainder in rem
(dv=a/d, rem=a%d). Either of dv and rem may be NULL, in which case the respective
value is not returned. The result is rounded towards zero; thus if a is negative,
the remainder will be zero or negative. For division by powers of 2, use
BN_rshift(3).