經典 Shamir 秘密共享計劃中的溢出
我已經實現了經典的 Shamir 秘密共享方案，如下所示：
- 獲取密碼作為輸入（任意長度）
- 將密碼文本轉換為大整數
- 生成多項式係數（an … a1）
- 生成分割 - 對 (xi, yi) 具有給定的門檻值
它工作得很好，這就是產生更多秘密份額的方式：
- 獲取份額和門檻值作為輸入
- 用高斯找到係數（所以我知道原始多項式）
- 尋找秘密值<–這就是問題
- 生成更多共享 - 使用時間戳作為 xi
一切正常，但是當我在重建秘密值時使用長密碼（10 個字元或更多）時，它可能會失敗，因為它失去了高數字的精度。
那麼如何克服這個經典的方法呢？應該對方案進行哪些更改以使其對秘密文本長度不敏感？
應該對方案進行哪些更改以使其對秘密文本長度不敏感？
好吧，Vadym 已經提到 Shamir 秘密共享應該在有限域中進行；但是它並沒有解決您的問題。
使用 Shamir 的方案，單個實例可以在它們之間共享任何值 $ 0 $ 和 $ p^k - 1 $ （在哪裡 $ p^k $ 是您使用的有限域的大小
$$ 1 $$）。而且，對於 Shamir，各種有限域之間沒有安全差異，因此我們可以根據實際問題（例如，您希望能夠發布的秘密數量、秘密的大小、實施的難易程度）選擇一個。各種有限域運算）。 但是，您要做的是共享密碼作為秘密；該密碼相當長，並且長度可變。好吧，有兩個明顯的選擇：
- 選擇一個 $ p^k $ （或素數 $ p $ 如果你和 $ k-1 $ ) 大到足以容納您想要共享的任何密碼；例如，如果您使用 $ p=2^{521}-1 $ （這是主要的），您可以共享最長 65 個字元的密碼。這可行，但缺點是需要使用 bignum 庫處理這麼大的值。如果您使用的是內置 bignum 庫的語言（例如 Python），這不是問題——如果不是，採用第二個想法可能會更容易。
有了這個想法，如果我們有密碼“letmein”（ASCII 中的 0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e），我們可以將其編碼為整數 0x6c65746d65696e = 30510848210725230。
- 將密碼拆分為多個秘密，並分別共享每個秘密。例如，對於 14 個字元的密碼，我們可以將其分成 14 個單獨的秘密（每個秘密是密碼中的一個字元），並使用共享每個字元 $ p=257 $ 和 $ k=1 $ （所以每一方將獲得總共 14 份，14 個字元中的每人一份）。有了這個想法，對一方獲得的所有股份使用相同的標識符是安全的；然而，重要的是每個秘密都是使用獨立隨機性生成的（即，14 個隨機多項式中的每一個都是單獨生成的）。
有了這個想法，我們將密碼“letmein”編碼為 8 個獨立的秘密 0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e
有了第二個想法，如果您不想洩露秘密的長度，您可以做的是始終共享固定數量的秘密（這將是您可以共享的最大密碼長度，例如 32），並且對於比這更短的密碼，用真實密碼中不可能出現的值填寫額外的秘密字元（例如 $ p=257 $ ，明顯的使用價值是 $ 256 $ ).
$$ 1 $$: 對於任何素數 $ p $ 和任何整數 $ k $ , 有一個有限的大小域 $ p^k $ . 開始使用欄位可能會更容易 $ k=1 $ 和 $ p $ 一個適當大小的素數 - 這使得加法、減法和乘法運算更接近您熟悉的標準算法（除法仍然很不穩定）。
從給出的描述中，有人可能會建議十進制數和浮點運算將是一種直接的解決方案。有限域沒有溢出和精度問題。
請考慮算術模一些素數，重新定義標準 c++ 加、減、乘和除。選擇一本你可以閱讀的教科書。這是一條很長的路。祝你好運。