對於分佈式下載組件雜湊計算，CRC32 是否有更好的替代方案？
給定具有下載恢復功能（字節範圍）的伺服器，我們可以逐塊下載文件。多人將下載文件的不同部分。
如果文件
A.jpg有塊1, 2, 3, 4, 5, 6。以下是獲得區塊的人
Alice - 1, 2 Bob - 3, 6 John - 4, 5
A.jpg假設 Alice、Bob 和 John 只能分別對每個塊進行散列，可以使用哪種散列算法來計算散列？假設每個塊的散列位於 Alice、Bob 和 John 可以訪問的地方。他們可以隨意組合它們。
我發現：不能使用將兩個 sha512 雜湊組合成一個雜湊。
我也發現可以用CRC32，還有算法嗎？
期望的結果
每個人都應該能夠生成相同的最終雜湊，這應該比 CRC32 更強大，以防止衝突。最後，我想加入塊以獲得最終文件。這樣 Alice、Bob 和 John 擁有相同的文件。
我假設我們想要一個在隨機 Oracle 模型中提供安全性的加密雜湊；接下來是抗碰撞和抗原像。無論大小如何，僅碰撞阻力就排除了 CRC。
標準技術是將文件拆分為塊，將它們與索引一起分發給參與者，參與者對每個塊進行雜湊處理；然後散列以增加索引的順序連接的散列，或使用Merkle 樹，形成整個文件的散列。但是，由於區塊以隨機方式分佈（如問題所示），大多數區塊雜湊需要交換，這可能會變得相當大；並且最終雜湊的分佈式計算有點難以組織。
相反，我們可以使用與順序無關的雜湊對區塊雜湊（取決於它們的索引）進行分組，每個參與者在他/他負責的區塊的所有雜湊上使用該雜湊，然後再次獲得最終雜湊。這簡化了組織，並在每個參與者有多個塊時節省頻寬：如以下簡單範例中的 8 使用 $ \Bbb Z_p^* $ ，但我推測使用橢圓曲線組可以使成本可以忽略到每個參與者 1 個塊。
對於 256 位散列，比處理大文件的正常散列略貴，我們將使用：
- 一些 512 位雜湊 $ H $ ，例如 $ H=\operatorname{SHA-512} $ .
- 一些 2048 位素數 $ p $ 使離散對數問題 $ \mathbb Z_p^* $ （推測）困難的；見最後一節。
- 一些公共塊大小 $ b $ 倍數 $ 2^{12} $ 位（512 字節），例如 $ b=2^{23} $ 對於 1 MiB的塊。
- 根據大端約定，從整數到位串的隱式轉換。
散列一個文件 $ s $ 位（與 $ s\le2^{62}b $ ，這綽綽有餘）：
- 將文件拆分為 $ \lceil s/b\rceil $ 塊 $ B_i $ 大小的 $ b $ -bit，除了最後一個可能更小（但非空），與 $ 0\le i<\lceil s/b\rceil $ . 分發塊 $ B_i $ 和索引 $ i $ , 這樣每個參與者 $ j $ 僅分配一次塊。
- 讓每個參與者 $ j $ 履行：
$ f_j\gets1 $
對於每個塊 $ B_i $ 分配給參與者 $ j $
- $ h_i\gets H(B_i) $ . 這是 512 位的位串特徵 $ B_i $ .
- $ g_i\gets H(h_i\mathbin|\widetilde{4i})\mathbin|H(h_i\mathbin|\widetilde{4i+1})|H(h_i\mathbin|\widetilde{4i+2})|H(h_i\mathbin|\widetilde{4i+3}) $ 在哪裡 $ \widetilde{;n;} $ 是整數的表示 $ n $ 作為 64 位位串。
自函式 $ H $ 返回 512 位，4 個雜湊的串聯使得 $ g_i $ 一個 2048 位的位串，其特徵為 $ B_i $ 和 $ i $ .
- $ f_j\gets f_j\cdot g_i\bmod p $ .
$ f_j $ 是一個 2048 位的位串特徵 $ B_i $ 和 $ i $ 分配給參與者 $ j $ .
如果 $ j\ne 0 $ , 傳遞 $ f_j $ 對參與者 $ 0 $ .
- 參與者 $ 0 $ 施行：
- $ f\gets f_o $
- 收貨時 $ f_j $ 和 $ j\ne 0 $
- $ f\gets f\cdot f_j\bmod p $ .
- $ h\gets H(f) $ 截斷為前 256 位，其中 $ f $ 應用時表示為 2048 位的位串 $ H $ .
- 發送 $ h $ 給所有參與者。
沒有消息更改或失去， $ h $ 與塊的分佈方式無關。這是整個文件的 256 位比特串特徵，以分佈式方式計算。的計算 $ f $ 和 $ h $ 也可以分發，但在消息交換中需要支付少量額外費用。
與順序無關的散列是從 Dwaine Clarke、Srinivas Devadas、Marten van Dijk、Blaise Gassend、G. Edward Suh、Incremental Multiset Hash Functions and They Application to Memory Integrity Checking中的乘法散列中藉用的，在AsiaCrypt 2013 的程序中，即鑑於附錄 C 中的安全性降低。整個建築的安全性應遵循。
關於選擇 $ p $ ：我們的要求是DLP的硬度在 $ \Bbb Z_p^* $ ，就像在經典的 Diffie-Hellman 密鑰交換中一樣。我們需要一個 2048 位的安全素數，沒有特殊形式 $ p=2^k\pm s $ 這可以使SNFS更容易。習慣上，它被用作基於一些超越數學常數的比特的無所不能的數字，作為一個足夠好的保證： $ p $ 沒有特殊形式。
那可以是 $ p=\lfloor2^{2046}\pi\rfloor+3617739 $ . 該構造使用二進製表示的前 2048 位 $ \pi $ ，然後遞增直到達到安全素數。十六進制值：
c90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf53ee2f正如 Sqeamish Ossifrage 在評論中指出的那樣，我們可以使用RFC 3526提出的 2048 位 MODP ： $ p=2^{2048}-2^{1984}-1+2^{64}\cdot\lfloor2^{1918}\pi+124476\rfloor $ . 這同樣使用了二進製表示的第一位 $ \pi $ 盡可能，但通過構造具有 66 個高位（包括兩個從 $ \pi\approx 3 $ ) 和 64 個低位設置。高位位簡化了經典方法歐幾里得除法中被除數的選擇，而低位位簡化了蒙哥馬利約簡。這被認為是足夠少的強制位不允許 DLP 的巨大加速。
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff