反轉計算 (x^2) 中間位的函式有多難？
我正在設計一個函式 f ，它應該在現代 CPU 中很難反轉並且非常快速地評估。該函式將用於工作量證明函式。
我讀過乘法的中間位是更難獲得的位，所以我懷疑它們是最難反轉的。
讓 $ f(x) = ((x^2) >> 16) $ 在哪裡[Math Processing Error] $ x $ 是32 位和 $ f(x) $ 被截斷為 32 位，並且乘法是在 64 位架構上進行的。
（或者可以使用[Math Processing Error] $ f(x) = ((2^{32}-x-1)*x) >> 16 ) $
假設，因為[Math Processing Error] $ f $ 可能不是雙射的，任何原像（如果存在）都可以接受。還假設沒有足夠的記憶體或時間來預先計算[Math Processing Error] $ f^{-1} $ 盡一切可能 $ f(x) $ 值（儘管可能需要一些記憶體/時間來預先計算一個小得多的表）
同樣，這不是一個嚴格的加密問題。在這種情況下，“硬”並不意味著密碼學上的硬。我在問它的難度，以標準電腦（使用標準指令集）的指令數量來衡量。任何操作的數量限制都會很大。
我在這裡發帖是因為這個問題不適合理論電腦科學而不是程式堆棧交換。
也許有一篇論文描述了這一點？
對於工作量證明，這可能不夠安全。我將概述一些攻擊，增加複雜性/複雜性和增加有效性（減少執行時間）。
蠻力
明顯的攻擊是蠻力：列舉所有[Math Processing Error] $ 2^{32} $ 可能的輸入並檢查以找到產生所需輸出的第一個。這需要[Math Processing Error] $ 2^{32} $ 時間。我確定您已經知道這種攻擊，並且根據您的問題，這聽起來在您的應用程序中是可以接受的。
時空權衡
您可以使用 Hellman 的時空權衡（或彩虹表，其大肆宣傳的版本）來解決原像。你必須做一個[Math Processing Error] $ 2^{32} $ - 步驟預計算以建立表。桌子的大小約為[Math Processing Error] $ 2^{22} $ . 建立表格後，您可以找到 $ f(x) $ 大約[Math Processing Error] $ 2^{22} $ 計算步驟。
因此，在可能需要幾分鐘或最多幾小時的一次性預計算之後，您可以在幾秒鐘內反轉函式，使用幾十兆字節的儲存空間。
猜測高位並在整數中取平方根
有一個更聰明的攻擊，它會找到最多使用的原像[Math Processing Error] $ 2^{16} $ 簡單的算術步驟（通常要快一些）。這可能會在不到一秒的時間內執行，可能只需幾毫秒即可找到原像。
我們可以寫成任何 64 位整數的形式[Math Processing Error] $ \alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma $ ， 在哪裡[Math Processing Error] $ \alpha $ 是一個 16 位整數，[Math Processing Error] $ \beta $ 一個 32 位整數，以及[Math Processing Error] $ \gamma $ 一個 16 位整數（即，[Math Processing Error] $ 0 \le \alpha,\gamma < 2^{16} $ 和[Math Processing Error] $ 0 \le \beta < 2^{32} $ ）。現在我們不知道[Math Processing Error] $ x^2 $ ， 但[Math Processing Error] $ x^2 $ 是一個 64 位整數，我們知道它的中間位，所以我們可以把它寫成形式
[Math Processing Error]$$ x^2 = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma $$ 我們知道的地方[Math Processing Error] $ \beta $ ([Math Processing Error] $ \beta $ 只是你的雜湊函式的輸出）但我們不知道 $ \alpha,\gamma $ .
現在遍歷所有可能的值[Math Processing Error] $ \alpha $ . 對於每個猜測 $ \alpha $ , 形成值
[Math Processing Error]$$ y = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + 2^{16}-1, $$ 取平方根[Math Processing Error] $ y $ 在整數中，並向下舍入為整數。讓[Math Processing Error] $ x’ $ 表示結果，即[Math Processing Error] $ x’ = \lfloor \sqrt{y} \rfloor $ . 然後檢查是否[Math Processing Error] $ x’ $ 是期望的原像，即是否 $ f(x’) = \beta $ .
我聲稱這種攻擊最多需要[Math Processing Error] $ 2^{16} $ 腳步。只有 $ 2^{16} $ 的可能值 $ \alpha $ , 所以我們最多做 $ 2^{16} $ 迭代。此外，在我們猜測的值的迭代中[Math Processing Error] $ \alpha $ 正確，我聲稱我們將成功恢復原像[Math Processing Error] $ x $ . 讓我解釋一下為什麼。一、64位整數[Math Processing Error] $ y $ 將非常接近 64 位整數[Math Processing Error] $ x^2 $ : $ y - x^2 < 2^{16} $ . 因此，當你取平方根時， $ \sqrt{y} $ 將非常接近[Math Processing Error] $ \sqrt{x^2}=x $ . 多近？嗯，請注意 $ (x+1)^2 \approx x^2 + 2x + 1 $ ，因此對於 32 位值[Math Processing Error] $ x $ , 連續的正方形大約是[Math Processing Error] $ 2^{32} $ 彼此分開。這比兩者之間的差距大得多[Math Processing Error] $ y $ 和[Math Processing Error] $ x^2 $ ， 所以 $ y $ 會更接近 $ x^2 $ 比 $ (x-1)^2 $ 或者 $ (x+1)^2 $ . 因此，取平方根[Math Processing Error] $ y $ 並四捨五入到最接近的整數將返回[Math Processing Error] $ x $ ， 不是 $ x-1 $ 或者 $ x+1 $ 或其他任何東西（除非 $ x $ 非常小，比如說 $ x < 2^{14} $ ，它的機率非常低，因此可以忽略）。
這意味著此攻擊最多可以保證成功 $ 2^{16} $ 迭代。
事實證明，並不是所有的值 $ \alpha $ 同樣可能；什麼時候 $ x $ 是均勻分佈的，高 16 位 $ x^2 $ 偏向於小的值。因此，如果您遍歷所有值 $ \alpha $ 在序列中 $ 0,1,2,3,\dots,2^{16}-1 $ ，你極有可能提前成功。直到成功的平均迭代次數為 $ 2^{16}/3 $ , 所以攻擊是關於 $ 3\times $ 根據最壞情況分析，速度比您預期的要快。