有限域 GF(2^8) 的拉格朗日插值，用於秘密重建

我正在使用拉格朗日插值技術從一組點對 (x,y) 中重建秘密。

由於我只需要秘密，而不是整個多項式，因此我將重建過程簡化如下：

讓秘密 $ D = 10 $ ，我們使用 3 分之三的秘密共享方案，該方案生成 3 個密鑰對

，所有這些都是重建秘密所必需的。我們選擇兩個隨機數作為係數。這給了我們多項式 $ 5x^2 + 2x + 10 $ . 從多項式生成 3 個點： $ (1, 17) $ , $ (2, 34) $ , $ (3, 61) $ 得到秘密 $ D $ ，我們只需要處理拉格朗日多項式的常數部分。

$$ \it{l}{0} = \dfrac{(x-2)(x-3)}{(1-2)(1-3)} = \dfrac{(x-2)(x-3)}{2} $$ $$ \it{l}{1} = \dfrac{(x-1)(x-3)}{(2-1)(2-3)} = \dfrac{(x-1)(x-3)}{-1} $$ $$ \it{l}_{2} = \dfrac{(x-1)(x-2)}{(3-1)(3-2)} = \dfrac{(x-1)(x-2)}{2} $$ 通過只考慮拉格朗日多項式的常數部分（忽略 $ x $ es)，我們可以計算秘密 $ D $ :

$$ D = 17 \dfrac{(-2)(-3)}{2} + 34 \dfrac{(-1)(-3)}{-1} + 61 \dfrac{(-1)(-2)}{2} = 10 $$ 這是我們的秘密。

現在同樣的方法應該適用於有限域 GF(2^8)，只要將算術替換為有限域算術。然而，這種情況並非如此：

unsigned int decodeByte(vector<pair<unsigned int, unsigned int>> keys) {
   int numKeys = keys.size();
   //extract the x's and y's from the vector
   vector<int> x;
   vector<int> y;
   for (int i = 0; i < numKeys; i++) {
       x.push_back(keys[i].first); //extract x
       y.push_back(keys[i].second); //extract y
   }

   GF256elm result(0);
   for (int i = 0; i < numKeys; ++i) {
       //calculate the constant term of lagrange interpolation polynomial
       GF256elm l(1);
       for (int j = 0; j < numKeys; ++j) {
           if (i == j)
               continue;
           GF256elm nxj = GF256elm(x[j]); 
           GF256elm xi = GF256elm(x[i]); //xj
           GF256elm xj = GF256elm(x[j]); //xj
           GF256elm ximxj = xi - xj;  //xi - xj
           GF256elm prod = nxj / ximxj; // (-xj)/(xi-xj)
           l *= prod;
       }
       GF256elm product = GF256elm(y[i]) * l;
       result += product;
   }
   return result.getVal();
}

基本上我在這裡做的是我在計算 $ \dfrac{-2}{1-2} $ , 然後乘以 $ \dfrac{-3}{1-3} $ ，然後將所有內容乘以 17，（這是從第一個點開始的 y 值 $ (1, 17) $ ）。這是上述 D 等式中的第一項。然後我繼續計算其他兩項。

問題是，我的答案不是 10，而是 14。

我的問題

1. 在有限域算術中，否定 x ( $ -x $ ） 是真的 $ 0 - x $ , 這實際上是 $ 0 \oplus x $ （XOR），它最終是 $ x $ 本身，我說的對嗎？
2. 我尋找秘密的方法有什麼問題嗎 $ D $ ?

附加資訊：

我的除法和乘法是使用查表實現的。這部分程式碼已經過測試，其結果與其他來源相同。

GF256elm& GF256elm::operator*=(const GF256elm& other) {
   int temp = (_logTable[val] + _logTable[other.val]) % 255;
   val = _expTable[temp];
   return *this;
}

GF256elm& GF256elm::operator/=(const GF256elm& other) {
   int t = _logTable[val] - _logTable[other.val];
   int temp =  ((t % 255) + 255) % 255;
   val = _expTable[temp];
   return *this;
}

我現在看到了你的問題；它比我之前的回答假設的更為基本。你說：

現在同樣的方法應該適用於有限域 GF(2^8)，只要將算術替換為有限域算術。然而，這種情況並非如此

您將“應該工作”解釋為“提出完全相同的答案”。

事實上，事實並非如此。您的原始範例似乎是在無限領域中設計的 $ Q $ （或一些超領域）；然後您使用完全相同的共享，將它們重新解釋為 $ GF(2^8) $ 點（以某種未指定的表示形式），然後感到困惑的是，您得到的答案並不完全相同。

$ Q $ 和 $ GF(2^8) $ 都是領域，但它們與領域所能獲得的不同。例如：

$ 2+2=4 $ （在該領域 $ Q $ )

$ 2+2=0 $ （在該領域 $ GF(2^8) $ )

$ 3 \times 3 = 9 $ （在該領域 $ Q $ )

$ 3 \times 3 = 5 $ （在該領域 $ GF(2^8) $ ，在最常見的表示中）

您的原始股份 $ (1, 17) $ , $ (2, 34) $ , $ (3, 61) $ 計算在 $ Q $ ; 如果它們被計算在 $ GF(2^8) $ ，他們會有不同的價值觀。因此，如果你在一個欄位中重建它們而不是計算它們，你會得到一個不同的答案也就不足為奇了。我使用原始多項式重新計算了您的份額（假設多項式表示為 $ GF(2^8) $ )，並提出了值 $ (1, 13) $ , $ (2, 26) $ , $ (3, 29) $

要測試您的程式碼，您需要提出自己的共享，在您用於重構的領域中進行計算。

（你還需要修正你的乘法邏輯，以防其中一個份額恰好是值 0）

引用自：https://crypto.stackexchange.com/questions/9982