不平衡數字Feistel網路實現

讀完一篇綜合論文後$$ 1 $$涵蓋各種廣義的 Feistel 網路，我嘗試實現不平衡數字 Feistel變體，它依賴於模運算將整數拆分和連接成兩個較小的部分。

鑑於這種密碼的範例實現稀缺，我必須自己找出一些不明確的細節才能提出下面的算法。因此，我想提出一些問題來澄清我剩餘的疑問：

• 下面的實現是否準確地遵循所描述的網路泛化？如果不是，哪些操作是錯誤的，執行它們的正確方法是什麼？
• 除了在解密函式上使用模減法⊟之外，還有什麼方法可以反轉加密函式上的模加法⊞？給定兩個整數 $ a $ 和 $ b $ 從一個有限的長度域 $ x $ , 操作 $ (-a-b) \bmod x $ 將以與按位異或類似的方式可逆，但（顯然）密文與通過目前操作獲得的密文不同。
• 動態計算的含義是什麼 $ first $ 和 $ second $ 所以 $ first \cdot second $ 有限域嚴格等於輸入 $ data $ ?

算法

給定兩個有限長度域 $ first $ 和 $ second $ 比…更棒 $ 2 $ , 若干 $ rounds $ 比…更棒 $ 2 $ , 一個正整數 $ data $ 在長度的有限域上 $ first \cdot second $ 和一個正整數 $ key $ :

請注意，由於 MathJax 格式的技術限制，上面的 LaTeX 程式碼作為圖像插入。此問題的降價源包含一個註釋掉的塊，其中包含用於呈現它的程式碼。

測試

（可用於測試所描述算法的Python實現）。

import random


class NumericFeistel:

   def __init__(self, key: int, rounds: int, first: int, second: int):
       assert all(number >= 2 for number in (rounds, first, second))
       self.first, self.second = first, second
       self.key, self.rounds = key, rounds

   def function(self, data: int, round: int) -> int:
       globals().update(self.__dict__)
       random.seed(data + key + round)
       return random.choice(range(first))

   def encrypt(self, data: int) -> int:
       globals().update(self.__dict__)
       assert data < first * second
       for round in range(rounds):
           left, right = data // second, data % second
           left += self.function(right, round)
           data = first * (right % second) + (left % first)
       return data

   def decrypt(self, data: int) -> int:
       globals().update(self.__dict__)
       assert data < first * second
       for round in reversed(range(rounds)):
           left, right = data % first, data // first
           left -= self.function(right, round)
           data = second * (left % first) + (right % second)
       return data


for test in range(1000):
   random.seed()
   feistel = NumericFeistel(
       rounds = 2 + random.choice(range(1000)),
       first = 2 + random.choice(range(1000)),
       second = 2 + random.choice(range(1000)),
       key = 42
       )
   data = random.choice(range(feistel.first * feistel.second))
   assert feistel.decrypt(feistel.encrypt(data)) == data

弱點

使用和濫用該random模組來生成偽隨機數並實現單向循環函式可能是一個非常糟糕的主意，但此程式碼旨在盡可能地具有可讀性，並且其假設的不安全性是一個小問題。

請注意，這只是一項娛樂活動，除了展示目的之外，沒有人打算將其用於任何目的。這不是另一個推出我自己的加密貨幣問題。

參考書目

1. Hoang VT, Rogaway P. (2010) 關於廣義 Feistel 網路。在：Rabin T. (eds) Advances in Cryptology – CRYPTO 2010。CRYPTO 2010。電腦科學講義，第 6223 卷。Springer，柏林，海德堡。https://doi.org/10.1007/978-3-642-14623-7_33

實現是否準確地遵循所描述的網路泛化？

**沒有。**論文中分析的 Feistel 網路假設了獨立的輪函式，但程式碼沒有給出。

問題在於程式碼讀取的位置random.seed(input + key + round)。相應的虛擬碼要麼具有相同的問題，要麼至少與 $$ \text{return }\mathit{hash}(\mathit{data}+\mathit{key}+\mathit{round}) $$ 也許這意味著 $$ \text{return }\mathit{hash}(\widehat{\mathit{data}}\mathbin|\widehat{\mathit{key}}\mathbin|\widehat{\mathit{round}}) $$ 在哪裡 $ \widehat x $ 是整數的表示 $ x $ 每個（比如說）大端二進制，在一個固定寬度的位串上選擇足夠大以獲得最大可能值。

如果我們在每一輪使用相同的散列，則希望輸入 $ \mathit{hash} $ 對任何三重奏都是獨一無二的 $ (\mathit{data},\mathit{key},\mathit{round}) $ . 我們可以只用數字來做到這一點，因為 $$ \text{return }\mathit{hash}(\mathit{data}+(\mathit{key}\cdot\mathit{nbrounds}+\mathit{round})\cdot\mathit{second}) $$

目前命題的問題是：不同輪次的輪次函式差異很小。對於一個固定 $ \mathit{key} $ , 如果我們注意到 $ F $ 功能 $ x\mapsto\mathit{hash}(\mathit{key}+x) $ ，然後是Feistel輪函式 $ F_i $ 在回合 $ i $ 是 $ x\mapsto F_i(x)=F(i+x) $ ，這與獨立功能相去甚遠。

這是滑動攻擊的一個很好的上下文，當 $ \mathit{first}=\mathit{second} $ 這些都很小（也就是說， $ 2^\mathit{first} $ 是可列舉的）。至少相關密鑰攻擊有效：無論多少輪，我們都可以查詢兩個實現密碼的黑匣子，並判斷它們的密鑰是否偏移了一個。並且因為添加了 round 函式的結果，這與 $ i+x $ 在輸入操作 $ F $ ，我認為它可以擴展到單個隨機密鑰設置中的區分攻擊；甚至可能是一種製表方式 $ F $ 功能並恢復密鑰的功能等價物，大大少於 $ 4^\mathit{first} $ 查詢。

---

除了在解密函式上使用模減法⊟之外，還有什麼方法可以反轉加密函式上的模加法⊞？

我沒有看到更簡單的工作。

---

動態計算的安全隱患是什麼 $ \mathit{first} $ 和 $ \mathit{second} $ 作為 $ \mathit{first}\cdot\mathit{second} $ 有限域嚴格等於輸入 $ \mathit{data} $ ?

照原樣，與 $ \mathit{data} $ 輸入塊，這不起作用。這意味著密文的最大值是 $ \mathit{data} $ . 因此，通過歸納，密碼要麼是同一性的（它不可能完全存在），要麼它不是單射的，因此是不可破譯的。

因此，我們至少離不開另一個輸入，即 $ \mathit{top} $ 範圍的 $ [0,\mathit{top}) $ 為了 $ \mathit{data} $ . 然後我們有一個嚴重的問題，當 $ \mathit{top} $ 是素數。

在Format Preserving Encryption（問題研究的學術名稱）中，一個標準的解決方案是騎自行車，這基本上增加了 $ \mathit{top} $ 一點點直到找到 $ \mathit{top’}=\mathit{first}\cdot\mathit{second} $ 和 $ \min(\mathit{first},\mathit{second}) $ 高於一些合理門檻值，然後當密文在範圍內時通過再次加密來修復加密 $ [\mathit{top},\mathit{top’}) $ . 當解密的明文在範圍內時，通過再次解密來補償解密 $ [\mathit{top},\mathit{top’}) $ .

---

我還沒有接觸過側通道攻擊，無論如何這些攻擊都嚴重依賴於語言。

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