Finite-Field

為什麼有限域在密碼學中如此重要?

  • June 22, 2021

我剛剛進入密碼學領域,目前正在通過嘗試實現一些加密算法來學習。

目前正在實施 Shamir 秘密共享算法,我注意到有限域不斷出現。

我只是不明白為什麼它們是相關的。

我看到的一件事是他們可以確保你的結果都不是小數,所以沒有捨入錯誤,但我強烈懷疑這就是它們如此重要的原因。如果有人可以讓我直覺地了解為什麼需要它們,那就太好了。

此外,它們是有限的事實是否會損害安全性?

這個問題的一個特別重要的話題是編碼大小。這來自以下“微不足道的事實”:

對於無限集 $ A $ , 不存在一些 $ s\in \mathbb{N} $ 這樣每一個 $ a\in A $ 可以描述為 $ s $ 位。

人們可以通過使用可變長度編碼來解決這個問題,但這很容易導致安全問題——被動地獲取一些關於某些編碼元素大小的資訊可能有點容易。如果這給出了對什麼元素進行編碼的一些指示,那就太糟糕了。因此,如果您希望密碼系統中的對象具有一些統一大小的編碼,那麼您將被有限的對象所困。

在有限結構中工作的一個(較小的)好處是存在均勻分佈。這是:

  • 集合上的最大熵分佈

  • 雙射下不變

    • 這包括,對於一組 $ G\ni g $ , 雙射 $ x\mapsto x+g $ ,這是非常常見的。

這些屬性足以顯示一次性便箋簿的安全性,這是相當基本的,並且人們經常想要吸引它(通常在用理想化的對象替換“真實”對象之後,例如用隨機函式替換 PRG)。

對於某些無限組,可以得到具有相似屬性的分佈,特別是Haar 度量。但它在技術上要復雜得多,因此均勻分佈如此簡單(同時具有很好的特性)這一事實絕對是有利於有限域的一點,儘管在我看來不如固定編碼大小點重要。

這些都不能回答為什麼有限,而不僅僅是有限代數結構。但通常有限域僅用作有限群的來源,例如 $ \mathbb{F}_p^\times $ . 有人可能會爭論為什麼要組而不是更弱的代數結構,但我對這個話題只有模糊的觀點。

也許最後一點是“為什麼不是有限結構”——比如 $ (\mathbb{Z}/pq\mathbb{Z})^\times $ 為了 $ p, q $ 的 $ \approx 1024 $ bits 大得離譜,雖然它在技術上不是無限的,但它“基本上”是這樣的——例如,大約有 $ 2^{270} $ 宇宙中的原子, $ 2^{2048} $ ,所以在某種意義上它“比我們的宇宙大”(當然仍然是有限的)。雖然像 $ \mathbb{R} $ 是無限的,如果一個導致舍入誤差(正如你提到的)你可能正在使用浮點近似值,通常最多使用 $ 128 $ 位,因此實際上(隱式)使用比密碼學家使用的更小的有限集。

引用自:https://crypto.stackexchange.com/questions/91659