如何在公司聊天軟體討論祕密 (Secure Communications over Insecure Channels)

22 Sep, 2026

密碼學的傳統典範中，通常有這個假設：

雙方必須先透過安全管道傳送加密用的金鑰，之後才能在不安全的管道上加密溝通。

Merkle 在 1978 年的 Secure Communications over Insecure Channels 演示了「公開管道上的金鑰建立」在概念上是可能的。

日常類比

想像這個場景：你跟一個同事 Y 只能透過公司的聊天軟體 Chat 傳訊息，但是透過 Chat 傳送的全部內容都會被 IT 部門監控。在這個情況下在你有辦法讓同事 Y 知道你等一下午餐要吃什麼，但 IT 部門要花很大的力氣（或資源）才能知道嗎？（假設 IT 部門只監控 Chat 的內容而不會監控你的螢幕，並且 IT 部門不能假裝成你或同事送假訊息）

下面試著給出一種作法：

包裝金鑰

大家應該遇過有加密的壓縮檔，也就是要先輸入密碼才能看到裡面的內容。

想像你準備好一百萬個加密的壓縮檔（每個壓縮檔的密碼不一樣，但都是 8 位純數字），每個壓縮檔都放了兩個檔案：編號跟一個長長的金鑰。例如

• 1.zip（密碼 44280328）：編號 1，金鑰 sg!6ljQu9.NFV^6.]u4++T-gnv...
• 2.zip（密碼 59203422）：編號 2，金鑰 aa6Z0w|6u#yCBA-fxS8j.ALmyE...
• ...
• 525924.zip（密碼 42180374）：編號 525924，金鑰 fB\Dt3tKqecEoM0:%c$r93x}6...（這一組等一下的範例會用到）
• ...

你自己先把每個編號對應的金鑰紀錄起來，接者把每個檔案的檔名都改成亂數：

• cdw_c6Pb.zip
• 3Db1-naC.zip
• ...
• 1bCgP4-1Q.zip
• ...

傳送包裝過的金鑰

再把這一百萬個壓縮檔按照隨機順序透過 Chat 傳給同事 Y（用隨機順序是因為我們不想讓 IT 可以從傳送順序猜出壓縮檔裡面的編號）。

暴力破解其中一包

你的同事 Y 收到這一百萬個檔案後，隨機選一個出來（例如 1bCgP4-1Q.zip）並嘗試所有 ${10}^8$ 種 8 位數的密碼。解開後會得到例如：

• 編號 525924，金鑰 fB\Dt3tKqecEoM0:%c$r93x}6...

回傳編號

這時候 Y 透過 Chat 傳給你 "編號 525924"。

你可以查詢編號 525924 的壓縮檔金鑰是多少（因為在"包裝金鑰"的步驟已經把編號跟金鑰的對應記起來了）。

現在你跟 Y 有一個共享的金鑰（fB\Dt3tKqecEoM0:%c$r93x}6...）

加密溝通

接下來你就可以用這個共享的金鑰當作密碼，把午餐要吃什麼的資訊放進一個加密過的壓縮檔，然後把壓縮檔透過 Chat 傳給 Y；因為 Y 也知道這個金鑰，他可以順利的解開壓縮檔。

分析

IT 部門看得到哪些資訊呢？

• 一百萬個壓縮檔
• 被 Y 選到的壓縮檔編號
• 包含午餐資訊的壓縮檔

IT 部門有兩個選擇

1. 破解一百萬個 8 位數字密碼的壓縮檔，找出 Y 選到的金鑰拿去解密午餐資訊。
2. 破解一個密碼超長的壓縮檔，直接解出午餐資訊。

這兩個選擇都需要大量的資源。

以上是日常生活的類比，下面是比較貼近原始文章的順序。

背景設定

1. 通信的雙方稱為 X 跟 Y，此外還有竊聽者 Z 想知道 X 跟 Y 的通信內容。
2. X 跟 Y 之間有兩種傳送訊息的管道：normal channel 跟 key channel。
   • normal channel 拿來傳送加密過的訊息。
   • key channel 是昂貴且不方便的，傳統密碼學用 key channel 安全地傳送金鑰。

傳統密碼學對 key channel 有兩個假設：

1. 竊聽者 Z 無法竄改 key channel 傳送的內容（或是竄改會被發現）。
2. 竊聽者 Z 無法知道 key channel 傳送的內容。

Merkle 的這篇文章移除了第二個假設，甚至假設竊聽者 Z 有 key channel 傳送內容的所有資訊。

主要想法

不是讓金鑰無法被竊聽者 Z 知道，而是讓合法的溝通者 X, Y 跟竊聽者 Z 的計算成本不對稱。

方法

文章有一個主要的概念 puzzle

puzzle: 一個設計成能被解開的加密問題。

姑且把 puzzle 翻譯成謎題。

主要流程：

1. X 產生 $N$ 個謎題，每個謎題解開後能得到一個 ID 跟一個金鑰，並且每個 puzzle 的 ID 都各不相同。
   • X 是產生謎題的人，他自己知道每個謎題的 ID 跟金鑰。
2. X 把這 $N$ 個謎題透過 key channel 傳給 Y。
3. Y 隨機選其中一個謎題，透過枚舉所有可能性解開謎題，得到 ID 跟金鑰，並把解出來的 ID 透過 key channel 回傳給 X。
4. X 找到這個 ID 對應的金鑰。
5. X 跟 Y 接下來在 normal channel 上用這個共享的金鑰加密溝通。

分析

1. 竊聽者只知道這 $N$ 個謎題以及 Y 在第三步驟傳的 ID。他並不知道 Y 選到哪個謎題，他必須逐個謎題嘗試才能找到這個 ID 對應的金鑰，平均需要嘗試解 $N/2$ 個謎題。
2. 合法的溝通者 Y 只需要解一個謎題。

限制

1. 竊聽者只要花 $N$ 倍的計算時間依然可以得到金鑰。
2. 需要傳送大量資料（$N$ 個謎題），並且資料量跟計算成本不對稱的程度乘正比。
3. key channel 沒有包含身份認證的機制，因此當 X 收到第三步驟回傳的 ID 時，其實不知道是誰傳過來的。

實作細節

文章中 X 產生謎題的方式是先找一個加密函數 $F$ 把資訊（ID 跟金鑰）加密。為了讓 Y 能暴力破解謎題，加密的時候密碼長度（或是說 key space）要人為限制。注意，不是選一個弱的加密函數。

X 跟 Y 要事前先溝通好

• $N$: 謎題數量。
• $C$: 一個常數。每個謎題的 key space 大小會是 $C\times N$。
• $F$: 加密函數。形式為 $F(key,messag{e}_1,...,messag{e}_k)$，其中第一個參數是加密函數的金鑰，接下來是要加密的訊息。
  • 這邊實作的 $F$ 需要加密三個訊息： Puzzle ID, Puzzle key 跟一個公開的訊息 $CON$。$CON$ 的作用是讓 Y 判斷枚舉到的加密函數金鑰是不是正確的。

X 如何產生 $N$ 個謎題

1. X 私下產生隨機金鑰 $K_1,K_2$ 以及一個隨機數 $CON$，並把 $CON$ 透過 key channel 傳送給 Y。
2. 對於 $i=1,...,N$，
   • $I{D}_i=F(K_1,i)$
   • $KE{Y}_i=F(K_2,I{D}_i)$
   • $RandKe{y}_i=RAND(C\times N)$
   • 謎題 $i$： $Puzzl{e}_i=F(RandKe{y}_i,I{D}_i,KE{Y}_i,CON)$

Y 如何解開謎題

Y 隨機一個 X 送來的謎題 $Puzzle$，枚舉全部 $C\times N$ 種金鑰嘗試解密。

如何判斷某個枚舉到的金鑰 $K$ 對不對？用 $K$ 解密 $Puzzle$ 得到 $I{D}^{\prime }$, $KE{Y}^{\prime }$ 跟 $CO{N}^{\prime }$。如果解出來的 $CO{N}^{\prime }$ 跟隨著謎題發來的 $CON$ 一樣，就代表猜對了金鑰。這時的 $I{D}^{\prime }$ 跟 $KE{Y}^{\prime }$ 就是這個謎題的 ID 跟金鑰。

Reference:

• Ralph C. Merkle. 1978. Secure communications over insecure channels. Commun. ACM 21, 4 (April 1978), 294–299. https://doi.org/10.1145/359460.359473