函式的這種實現是否在恆定時間內執行？
假設我們有一個函式 $ n $ 參數，每個大小為一位，並返回一位。在內部，這個函式有一個位串 $ N \in {0, 1}^{2^n} $ 它通過使用 $ n $ 輸入以形成指向位的指針 $ i $ 在 $ N $ ， 在哪裡 $ i $ 等於輸入位被連接並被視為一個整數。
例如，假設我們有 $ F(a, b, c) $ 和 $ N = 01110001_{2} $ . 如果我們有 $ F(1, 0, 1) $ ，然後將通過檢索位找到輸出 $ 101_{2} = 5 $ ，這將是 $ 1 $ （或者 $ 0 $ 如果你想最左邊的位是位 $ 0 $ ).
以這種方式實現功能會在恆定時間內執行嗎？如果它是在硬體中實現的？如果它是在軟體中實現的？
**更新：**我認為這很明顯，但是從 $ N $ 將使用按位移位後跟按位與來實現（值為 $ 1 $ ).
以這種方式實現功能會在恆定時間內執行嗎？
這不是一個實現，它是算法的抽象描述。
您需要以實際的程式語言（或實際的硬體）來實現該功能，以確定它是否在恆定時間內執行。您無法通過抽象算法的描述來確定這一點，因為（通常）有許多不同的可能方法來計算它。
該函式的一個實現範例是一些 C 程式碼。請注意您的描述中沒有運算符或指令 - 如果不處理一系列指令，實現將很難產生結果。
此外，您執行算法的實際平台可能會影響操作是否需要恆定的時間。即使您使用的程式語言也可能使實現常量時間變得具有挑戰性。
另請注意：關於密碼學的恆定時間意味著“所花費的時間與任何秘密數據無關”，而不是“在所有可能的輸入上執行相同的時間”。
如果您對應該保密的數據進行分支，您可能會通過執行操作需要多長時間來洩露有關它的資訊。
你的功能 $ F $ 是，在抽象的方式，一個泛型 $ n\rightarrow 1 $ 功能。正如我所收集的那樣，您建議的實現是為所有可能的輸入（使用 $ n $ 輸入位，有 $ 2^n $ 可能的輸入組合），然後以某種方式“選擇”正確的組合。
有很多方法可以在軟體和硬體中實現這一點，而且並非所有方法都是“恆定時間”。例如，在軟體中，您可以傳播 $ 2^n $ 位到這麼多的數組單元格中，並使用由輸入索引的數組訪問（被視為整數）。由於這將構成依賴於秘密數據的地址的記憶體訪問，因此這不是恆定時間的，並且可能容易受到記憶體定時攻擊。
現在，在像現代 PC 這樣的具體平台上，如果 $ n $ 足夠小，那麼您可以儲存 $ 2^n $ 寄存器中可能的輸出（這顯然只有在 $ 2^n $ 不大於相關機器上的寄存器長度），並使用輸入執行右移（
>>C中的運算符，shrx86彙編中的操作碼）（ $ n $ 位）作為移位計數。通常，這應該是恆定時間，但這取決於確切的 CPU。大多數 CPU 包括一個稱為“桶形移位器”的特定硬體，它在一個時鐘週期內執行移位，而不管移位計數如何。從歷史上看，桶形移位器的存在並不是必然的。特別是 Pentium IV 著名的沒有桶形移位器，也沒有一個可變計數的右移 $ x $ 將花費或多或少與價值成正比的時間 $ x $ . 在這種情況下，“寄存器移位”實施策略將不是恆定時間。在硬體中，這是一個路由問題：您想從 $ 2^n $ 輸出序列；電路需要“觸摸”所有 $ 2^n $ 位。碰巧它可以用多路復用器樹來完成。多路復用器
mux(c,a,b)返回aifc為 0 或bifc為 1。然後您可以執行以下操作：
- 結合所有 $ 2^n $ 位成對，與 $ 2^{n-1} $ 多路復用器，都使用第一個輸入位作為控制（“
c”）位。這產生 $ 2^{n-1} $ 輸出。- 結合所有這些 $ 2^{n-1} $ 成對輸出，與 $ 2^{n-2} $ 多路復用器，都使用第二個輸入位作為控制位。你現在有 $ 2^{n-2} $ 價值觀。
- 迭代。最後，您有一個多路復用器，它使用最後一個輸入位作為控制，並產生您正在尋找的結果。
這種作為多路復用器樹的實現自然是恆定時間的，它是在硬體中製作 S-box 的首選方法（例如，對於 DES 實現）。