安全文件共享與凱萊圖——譯自MFO奧伯沃爾法赫現代數學簡報

★置頂zzllrr小樂公眾號（主頁右上角）數學科普不迷路！

你是否曾好奇，電腦是如何判斷哪些下載內容可信、哪些不可信的？本篇簡報將介紹文件共享中的一些安全問題，以及一種利用代數學解決這些問題的方法。我們會看到一種巧妙的方法——借助代數學中一個極具難度的問題實現安全保障，并探討該方法的若干重要性質。

作者：Eilidh McKemmie（美國基恩大學數學助理教授）2026-2-23

譯者：zzllrr小樂（數學科普公眾號）2026-3-15

1 文件共享

試想你正從網上下載一個大文件，而你的對手伊芙一心想要破壞這次下載。由于文件體積較大，它會被拆分成多個名為數據包（packet）的部分，這種情況在點對點文件共享中十分常見。如果伊芙篡改其中部分數據包，整個文件都會被破壞，她甚至還能植入病毒。你需要在拼接數據包、打開文件前，發現數據包被篡改的問題。

你可以使用哈希函數（hash function），它能為任意數據包生成一個簡短的數字標識，即哈希值（hash）。你會通過獨立的信道收到每個數據包對應的哈希值，只需對下載的數據包應用該哈希函數，將得到的結果與收到的哈希值比對即可。若實際生成的哈希值與收到的不一致，就說明該數據包已被篡改，你可丟棄該數據包并重新下載。

接下來，我們將運用數學知識構造一款適用于文件共享、且具備優良性質的哈希函數。

2 理想的函數性質

我們假設伊芙能夠篡改數據包，卻無法篡改哈希值。如果哈希值的體積遠小于數據包，我們就可以使用僅能傳輸少量數據的安全信道——體積小巧的哈希值能通過該信道傳輸，而大容量的數據包則無法通過。

但這一做法也帶來了新問題：可能的數據包數量遠多于可能的哈希值數量，因此一個哈希值并非某個數據包的專屬標識。這意味著伊芙可以找到另一個偽造的數據包，使其生成的哈希值與原數據包一致，進而依舊能篡改你的文件。因此，我們希望哈希函數具備原像抵抗性（pre-image resistant），即伊芙很難找到一個能生成指定哈希值的數據包。

從下載的數據包還原原始文件有多種方法，在某些情況下，只需將若干數據包進行“相乘”操作即可實現。根據數據包的實際類型，這里的“相乘”既可以指算術乘法，也可以只是將所有數據包拼接在一起。例如，點對點文件共享中會使用噴泉碼（fountain codes）將文件拆分為數據包，即便丟失少量數據包，你仍能還原出原始文件[6]。如果數據包的哈希值可以通過相乘得到整個文件的哈希值，我們就能同時對多個數據包計算哈希值，再將結果相乘，大幅提升哈希計算的效率。當數據包乘積的哈希值等于哈希值的乘積時，這個哈希函數就被稱為同態哈希函數（homomorphic hash function）。

使用同態哈希函數，意味著我們只需通過安全信道傳輸整個文件的哈希值即可。無需先拼接還原文件，再檢查其是否被篡改；相反，我們可以在每個數據包到達時計算其哈希值，最后將所有哈希值相乘，再與文件的預期哈希值比對。

至此，我們明確了目標：尋找一個將數據包映射為哈希值的函數，且該函數需具備以下性質：

1. 壓縮性（Compression）：哈希值的體積遠小于數據包；

2. 同態性（Homomorphism）：乘積的哈希值等于哈希值的乘積；

3. 原像抵抗性（Pre-image resistance）：伊芙難以找到能生成指定哈希值的數據包。

還有一個潛在問題：伊芙可以植入一個哈希值為1的數據包，這一操作不會改變哈希值的乘積，卻會篡改原始文件。因此，我們還要求哈希函數具備抗碰撞性（collision resistance）：

4. 抗碰撞性（Collision resistance）：伊芙難以找到哈希值為1的數據包。而這一性質，實際上等價于“難以找到兩個不同的數據包，使其生成相同的哈希值”。

綜上，我們要尋找的哈希函數需同時滿足壓縮性、同態性、原像抵抗性和抗碰撞性。接下來，我們將介紹如何利用矩陣乘法（matrix multiplication）構造這樣的哈希函數。

3 矩陣乘法

當一個數字無法承載足夠的信息時，你可以使用矩陣（matrix）——一種由數字構成的陣列。以下是幾個元素為整數的矩陣示例：

矩陣是數學和諸多科學領域的實用工具，想要深入了解矩陣，可參閱2019年第5期奧伯沃爾法赫現代數學簡報[3]。

尤其在數據分析和圖像壓縮中，矩陣常被用于存儲數據，這類應用要求計算機能高效執行矩陣的乘法、加法等運算。我們將重點研究n階方陣（n×n matrix）的乘法，即擁有n行n列的正方形矩陣。上述第一個例子是3階方陣，第三個是2階方陣。對于固定的正整數n，任意兩個n階方陣都可以相乘，就像普通數字的乘法一樣。

兩個n階方陣A和B的乘法規則如下：新矩陣的每個元素，都由A中某一行的元素與B中對應列的元素按位相乘后求和得到。即便對于高階矩陣，計算機也能高效完成這一運算。兩個n階方陣相乘的結果仍為n階方陣，矩陣的規模不會變大，這一性質將幫助我們實現第一個目標——讓哈希值保持小巧的體積。

矩陣乘法與普通數字的乘法有諸多相似之處。存在一種特殊的矩陣I，其作用類似于數字1：任意矩陣A與I相乘，結果仍為A。該矩陣的主對角線（從左上到右下的對角線）元素均為1，其余元素均為0，被稱為單位矩陣（identity matrix）。此外，部分矩陣還能實現類似“除法”的操作：要對矩陣A做“除法”，只需找到其逆矩陣（inverse matrix）A?1，再與該逆矩陣相乘即可。需注意的是，許多矩陣不存在逆矩陣，這類矩陣類似于數字0——無法對其做除法運算。

但矩陣乘法比普通數字的乘法更復雜。例如，我們知道2·3=6=3·2，但對于矩陣A和B，通常有AB≠BA（矩陣乘法中，乘號可省略）。例如：

事實證明，矩陣乘法的這一性質，將為我們構造哈希函數提供極大幫助。

在構造哈希函數前，還有一點需要說明：我們將對矩陣的所有元素取素數p模。即預先選定一個素數p，將矩陣中的每個元素替換為其除以p后的余數。這一操作能進一步壓縮哈希值的體積，因為矩陣的每個元素僅有p種可能的取值。例如，若p=3，則數字3會被替換為0，4會被替換為1，以此類推。且這一操作不會影響矩陣的乘法運算，上述例子取3模后的結果為：

我們構造哈希函數所用的矩陣，均來自一個特殊的集合——SL?(p)，即素數p模下的n階特殊線性群，該集合中的所有n階方陣均存在逆矩陣。上述例子中的矩陣，均來自SL?(3)。

4 凱萊哈希函數

構造凱萊哈希函數（Cayley hash function），首先需要選取兩個矩陣A和B，并確保AB≠BA。我們以SL?(3)中的如下兩個矩陣為例：

這組矩陣是Gilles Zémor在提出首個凱萊哈希函數時所使用的[11]。

我們將任意長度的0-1序列定義為一個數據包，哈希函數會將序列中的每個1替換為矩陣B，每個0替換為矩陣A，再將所有替換后的矩陣按順序相乘，得到的結果即為該數據包的哈希值。我們將這個哈希函數記為h。例如，使用Zémor選取的A和B，可得：

由于我們選取的素數p=3，該哈希函數的輸出始終是元素為0、1或2的2階方陣。事實上，SL?(3)中僅有24個不同的矩陣，這意味著該哈希函數僅有24種可能的哈希值。如果我們將這些矩陣用1到24的數字標記，并將該數字作為最終的哈希值，那么無論數據包的體積多大，哈希值最多只有兩位（若用二進制表示，僅為4比特）。至此，我們構造出的哈希函數已滿足第一個理想性質：哈希值的體積遠小于數據包。

同時，該函數也滿足同態性。因為數據包的“相乘”操作即為簡單的拼接，例如：

h(010)h(110)=ABABBA=h(010110)

需要注意的是，由于AB≠BA，一般情況下，打亂數據包中的0和1的順序，得到的哈希值也會改變。這一性質意味著，打亂數據包順序的操作不會破壞哈希函數的抗碰撞性。想要更深入地理解原像抵抗性和抗碰撞性，我們需要先弄清：為何這類哈希函數以“凱萊”命名。

5 凱萊圖

凱萊圖（Cayley graph）是直觀展現凱萊哈希函數原像抵抗性和抗碰撞性的工具。數學家Arthur Cayley（1821–1895）于1878年首次提出了凱萊圖的概念，Max Dehn（1878–1952）則在20世紀初完善了凱萊圖的基礎理論。凱萊圖最初被用于研究數學中的對稱性，即群論（group theory）。2019年第16期奧伯沃爾法赫現代數學簡報[7]探討了凱萊圖的一些有趣性質，其中部分性質將在本文后續內容中用到。

本文僅聚焦于凱萊圖在分析凱萊哈希函數原像抵抗性和抗碰撞性中的應用。這兩個性質的實現與驗證，遠比壓縮性和同態性困難，因此我們需要這一工具的輔助。

給定SL?(p)中的兩個矩陣A和B，我們這樣定義對應的凱萊圖：

以SL?(p)中的每個矩陣為一個頂點（dot）；若頂點N可由頂點M左乘A得到（即N=MA），則用紅色箭頭連接M→N；若N可由M左乘B得到（即N=MB），則用藍色箭頭連接M→N。

這意味著，從單位矩陣I出發，通過不斷右乘A或B的“行走”操作，就能畫出整個凱萊圖。圖1展示了上述Zémor選取的矩陣A、B時，對應的SL?(3)凱萊圖。

圖1 由GeoGebra繪制

圖中箭頭的顏色對應不同矩陣：紅色代表A，藍色代表B；單位矩陣用紅點標記，便于識別。

可以看到，凱萊圖中存在大量重復的圖案，但想要在圖中找到特定的路徑卻并不容易。例如，圖中的三角形圖案表明AAA=I=BBB；還能從圖中發現AAB=BAABA這類規律——因為不同的路徑最終會到達同一個頂點。

現在，我們從凱萊圖的角度理解原像抵抗性：原像抵抗性即“難以找到生成指定哈希值的數據包”，而數據包的哈希值，就是其對應的路徑在凱萊圖中的終點。因此，原像抵抗性可重新表述為：難以在凱萊圖中找到從單位矩陣I到指定頂點的路徑。

而抗碰撞性，則等價于“難以在凱萊圖中找到環路（loop）”——因為環路本質上對應一個哈希值為單位矩陣I的數據包。沿著凱萊圖中的環路行走，最終會回到出發時的頂點，這意味著構成該環路的所有矩陣相乘，結果為單位矩陣I。從另一個角度看，環路代表到達同一頂點的兩條不同路徑，即兩個不同的數據包生成了相同的哈希值。

在我們的例子中，凱萊圖的規模很小：能看到僅由3步構成的環路，這說明該哈希函數不具備抗碰撞性；此外，從單位矩陣到任意矩陣的路徑最多僅有5步，因此該哈希函數也不具備原像抵抗性——對于任意給定的矩陣M，伊芙只需讓計算機遍歷所有長度為5的路徑，檢查M是否為路徑的終點即可。即便不使用任何優化技巧，她也只需檢查2?=32條路徑，因為路徑的每一步都僅有兩種選擇（乘A或乘B）。

解決這一問題的方法是：選取足夠大的素數p。通常，我們會選取與RSA[4]等數據安全系統中同級別的大素數，即大于22???≈3.2×10?1?的素數。此時，SL?(p)中的矩陣數量會變得極其龐大，對應的路徑數量也會數不勝數，伊芙必須借助復雜的數學技巧，才有可能破解哈希函數的原像抵抗性。

6 選取合適的矩陣A和B

此前，我們并未深究矩陣A和B的選取問題。所有凱萊哈希函數都天然具備壓縮性和同態性，但原像抵抗性和抗碰撞性，則完全取決于A和B的選取。

一般來說，證明一個問題對計算機而言是“難解的”，是一件非常困難的事。這意味著，證明一個哈希函數不具備原像/抗碰撞性，遠比證明它具備該性質容易。因此，在無法給出嚴格證明的情況下，我們會接受那些能充分證明哈希函數具備原像/抗碰撞性的證據。

Tillich和Zémor已證明，上文所述的凱萊哈希函數構造方法并不具備抗碰撞性[10]，許多其他選取A和B的方案也已被破解。據筆者所知，目前僅有兩種方案尚未被破解[2,8]，而這兩種方案具備原像抵抗性和抗碰撞性的證據，來自其對應的凱萊圖的圍長（girth）和自由性（freeness）性質。

6.1 圍長

Babai提出過一個著名的猜想：當素數p足夠大時，在凱萊圖中，任意兩個矩陣之間的路徑長度最多約為log p。對于SL?(p)，該猜想已被相關研究證實[5,1,9]。

為了讓凱萊哈希函數的抗碰撞性和原像抵抗性難以被破解，我們要求凱萊圖中任意兩個矩陣之間的路徑長度至少約為log p，這意味著凱萊圖的圍長應盡可能大。

嚴格來說，凱萊圖的圍長（girth）是指圖中最短的有向環路的長度，而這一參數，正是我們在上一節中指出的、影響哈希函數抗碰撞性的關鍵因素。

因此，在選取矩陣A和B時，我們希望其對應的凱萊圖擁有大圍長。事實上，許多類別的矩陣都能滿足這一要求，例如擴展圖（expander graphs）的諸多子類（相關內容可參閱2019年第16期奧伯沃爾法赫現代數學簡報[7]）。

6.2 自由性

我們對矩陣元素取素數p模，是為了讓哈希值保持小巧的體積。如果拋開取模操作，直接在整數域上進行矩陣運算，會發生什么？這一操作被稱為提升至整數域（lifting to the integers）。

如果將矩陣A和B提升至整數域后，哈希函數的抗碰撞性或原像抵抗性被破壞，那么這一破壞將對所有素數p成立，哈希函數也會被徹底破解。

因此，我們希望：將矩陣A和B提升至整數域后，哈希函數的抗碰撞性和原像抵抗性仍不會被破壞。若滿足這一條件，我們就稱矩陣A和B生成了一個自由結構（free structure）。

參考文獻[2]和[8]中選取的矩陣A和B，既生成了自由結構，其對應的凱萊圖也擁有大圍長——這些證據充分表明，基于這兩組矩陣構造的凱萊哈希函數是安全的。

7 尚未解決的問題

在本篇簡報中，我們了解到凱萊哈希函數是實現安全文件共享的潛力方案，也看到矩陣A和B的選取會影響其對應的凱萊圖，而凱萊圖又決定了哈希函數的原像抵抗性和抗碰撞性。我們認識到，選取安全的矩陣A和B并非易事，而數學家們能基于凱萊圖的圍長和自由性，為部分矩陣選取方案的安全性提供充分證據。

但仍有一個問題尚未解決：凱萊圖的大圍長和自由性，是否足以保證凱萊哈希函數的安全性？

要證明答案為“否”，數學家需要找到這樣的反例：某組矩陣A和B對應的凱萊圖擁有大圍長且生成自由結構，但其構造的哈希函數卻不具備原像抵抗性和抗碰撞性；

而要證明答案為“是”則更為困難，因為研究者需要考慮所有可能的矩陣A和B，并證明所有可能的破解算法，都無法找到哈希函數的原像或碰撞。

原文參考文獻

[1] E. Breuillard, B. Green, and T. Tao, Approximate subgroups of linear groups, Geometric and Functional Analysis 21 (2011), no. 4, 774–819.

[2] L. Bromberg, V. Shpilrain, and A. Vdovina, Navigating in the Cayley graph of SL2(Fp) and applications to hashing, Semigroup Forum 94 (2015), no. 2, 314–324.

[3] A. Detinko, D. Flannery, and A. Hulpke, Algebra, matrices, and computers, Snapshots of modern mathematics from Oberwolfach (2019), no. 05, https://doi.org/10.14760/SNAP-2019-005-EN

[4] M. Gardner, Mathematical games, Scientific American 237 (1977), no. 2, 120–125.

[5] H. A. Helfgott, Growth and generation in SL2(Z/pZ), Annals of Mathematics 167 (2008), no. 2, 601–623.

[6] N. Johnson, Damn cool algorithms: Fountain codes, 2012, http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes , visited on 2025-28-11.

[7] A. Khukhro, Expander graphs and where to find them, Snapshots of modern mathematics from Oberwolfach (2019), no. 16, https://doi.org/10.14760/SNAP-2019-016-EN

[8] C. Le Coz, C. Battarbee, R. Flores, T. Koberda, and D. Kahrobaei, Postquantum hash functions using SLn(Fp), Advances in Mathematics of Communications 19 (2025), no. 3, 996–1009.

[9] L. Pyber and E. Szabó, Growth in finite simple groups of lie type, Journal of the American Mathematical Society 29 (2014), no. 1, 95–146.

[10] J. Tillich and G. Zémor, Group-theoretic hash functions, Algebraic Coding, Springer, 1994, pp. 90–110.

[11] G. Zémor, Hash functions and Cayley graphs, Designs, Codes and Cryptography 4 (1994), no. 3, 381–394.

作者簡介

Eilidh McKemmie，美國基恩大學數學助理教授。

所屬數學領域

代數學與數論

跨學科關聯

計算機科學

版權協議

知識共享署名-相同方式共享4.0協議（Creative Commons BY-SA 4.0）

數字對象標識符

10.14760/SNAP-2026-002-EN

奧伯沃爾法赫現代數學簡報為讀者呈現當代數學研究的精彩洞見，由奧伯沃爾法赫數學研究所（Mathematisches Forschungsinstitut Oberwolfach, MFO）科研項目的參與者撰寫。本簡報項目旨在向全球對數學感興趣的公眾普及現代數學知識，增進大眾對數學研究的理解與認同。所有簡報均與IMAGINARY平臺合作發布，可在以下網址查閱：www.imaginary.org/snapshots 以及 www.mfo.de/snapshots 。

國際標準連續出版物號

ISSN 2626-1995

機構信息

奧伯沃爾法赫數學研究所（Mathematisches Forschungsinstitut Oberwolfach gGmbH）

地址：德國巴登-符騰堡州奧伯沃爾法赫市，黑森林大街9-11號，77709

所長：Gerhard Huisken

合作平臺：IMAGINARY開放式數學平臺

參考資料

https://publications.mfo.de/handle/mfo/4387

小樂數學科普近期文章

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

置頂★加星

數學科普不迷路！