3

以前にも同様の質問を投稿したことがありますので、あらかじめお詫び申し上げますが、ここでどこが間違っているのかを見つけることができません。

OpenSSL の BIGNUM ライブラリを C で使用して Shamir シークレット シェアリングを実装しています。

ラグランジュ補間のラウンドを実行した後、乗算key * numeratorしてから、分母で除算する必要があります。

BN_mod_div関数がないため、代わりBN_mod_inverse()に分母を使用してから、次のように乗算します。

(key * numerator) * (inverse of denominator)

私が気づいたのは、使用する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);
}   

}
4

1 に答える 1

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).
于 2013-10-02T09:17:01.480 に答える