使用秘密的短消息的快速不可逆轉換/壓縮
我正在尋找一個非常快速的功能 $ f(m, k) $ 需要一個 64 位整數 $ m $ 和一個固定的密鑰 $ k $ 幾乎任何大小（由 CSPRNG 生成）並將它們轉換為 64 位或 32 位整數 $ r $ ，還有一些額外的要求：
- $ r $ 必須依賴於兩者 $ m $ 和 $ k $ 並且分佈合理
- 如果一對 $ m $ 和 $ r $ 是已知的，它應該不可能有效地計算 $ k $ 或生產 $ f(m_1, k) = r_1 $
- $ r $ 將被用作一種與相關聯的鍵或標籤 $ m $ ，但它不必唯一標識 $ m $ （即存在 $ m_1 $ , $ m_2 $ 這樣 $ f(m_1, k) = f(m_2, k) = r $ 完全正常），所以我不太擔心碰撞
IOW，我需要一種方法來快速且不可逆地轉換/壓縮/加擾一個固定大小的整數（可能縮短它）使用一個秘密。
我認為理想情況下，這將通過像 Blake* 或 Siphash 這樣的密鑰加密雜湊函式來解決。例如，Siphash 專門設計用於處理小輸入並保持密鑰保密性，目前在 CPython 中用於雜湊表查找。性能方面的 Siphash-2-4 對於我的案例來說可能是可以忍受的，並且似乎檢查了所有的框，但由於我只需要處理一個 64 位整數，所以感覺有點矯枉過正，我仍然對更多的東西感興趣輕的。
我還查看了幾個非加密雜湊函式，它們的性能非常吸引人，但我擔心它們中的許多將無法滿足我列出的第二個要求（尤其是如果我提供它們 $ k || m $ ，這在 FNV-1A 和 Murmurhash3 的情況下簡化了暴力攻擊）。XXH3明確允許我提供
secret自定義雜湊值，它似乎優於現有的任何其他體面的雜湊函式，但它也明確非加密，所以不幸的是我不確定它是否可以提供與 Siphash 相同級別的安全性，即使是像我這樣簡單的案例。我還嘗試創建自己的混合/壓縮函式（這很可能不安全），並考慮使用現有算法中的混合/壓縮函式（很可能不是設計為與原始算法分開使用）。
我錯過了一種更簡單的方法嗎？
在這個答案的第一部分，我將要求 2 限制為“如果一對 $ (m,r) $ 是已知的…… ”，並假設 $ k $ 是隨機選擇的。當對手知道兩個不同的配對時，我完全無視安全性 $ (m,r) $ , 或者當相關鍵 $ k $ 被使用。
以下構造使用伽羅瓦域 $ (\mathbb F_{2^{64}},\oplus,\otimes) $ ，帶有一些不可約多項式¹：
$$ f:{0,1}^{64}\times{0,1}^{128}\to{0,1}^{64}\ (m,k)\mapsto (k_1\otimes m)\oplus k_0=r\ \text{ where }\ k_1\mathbin|k_0=k\ \text{ and }\ |k_0|=64=|k_1| $$
給定 $ (m,r) $ 和 $ (m_1,r_1) $ 和 $ m\ne m_1 $ ，存在一個唯一的²鍵 $ k $ 和 $ f(m,k)=r $ 和 $ f(m_1,k)=r_1 $ . 因此，無論對手的計算能力如何，該結構都完美地滿足了其安全目標。
注意：對於任何固定 $ k $ 和 $ k_1\ne0 $ ，沒有碰撞。
注意：我們通過從結果中刪除任意數量的位來限制較小的輸出。我們可以相應地縮短密鑰 $ k $ 通過刪除位 $ k $ （在 $ k_0 $ ) 不影響結果。
注：計算 $ f $ 在內置支持二進製欄位算術的 CPU 上簡單高效，包括大多數現代 x86 CPU，它們具有無進位乘法。否則，這種方法沒有什麼意義。
#include <stdint.h> #if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later. #include <immintrin.h> inline uint64_t f(uint64_t m, const uint64_t k[2]) { __m128i u,v; u.m128i_u64[0] = k[1]; u.m128i_u64[1] = 27; // X**64 + x**4 + x**3 + x + 1 v.m128i_u64[0] = m; v = _mm_clmulepi64_si128(u, v, 0); // u.m128i_u64[0] * v.m128i_u64[0] u = _mm_clmulepi64_si128(u, v, 17); // u.m128i_u64[1] * v.m128i_u64[1] return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0]; } #else // no _mm_clmulepi64_si128 #pragma warning(disable : 4146) // silence silly compiler's warning uint64_t f2(uint64_t m, const uint64_t k[2]) { uint64_t a = k[1], x = (m & -(a & 1)) ^ k[0]; a = (a >> 1) | (1ull << 63); // insert sentinel do // 63 times x ^= (m = (27 & -(m >> 63)) ^ (m + m)) & -(a & 1); while ((a >>= 1) != 1); return x; } #endif現在我將要求 2 讀為“如果有一些對 $ (m,r) $ 是已知的…… ”。如果所述數字很大（大於我們願意處理的 64 位密鑰塊），我們就無法再建構一個完全安全的系統。
問題提出的問題可以用 64 位分組密碼很好地解決，但隨之而來的是選擇它的問題。茶？RC5 ? 河豚？太子？西蒙？斑點？輕量級加密候選人之一？任何人都會做。然後我們可以冒險去做一些定制的事情。
¹ 例如 $ x^{64}+x^4+x^3+x+1 $ ，請參閱 Joerg Arndt 的具有最低可能設置位的二進制不可約多項式。該多項式恰好也是原始的，但我們不需要該屬性。
² 證明：即 $ k $ 可以發現為 $ k_1\gets(r\oplus r_1)\oslash (m\oplus m_1) $ , $ k_0\gets(k_1\otimes m)\oplus r $ , $ k\gets k_1\mathbin|k_0 $ .