後量子密碼學（五）：密鑰封裝

密鑰封裝, Key Encapsulation Mechanism

那些能想像一切的人，可以創造不可能的事。

-艾倫·圖靈

密鑰封裝系統

公鑰密碼學中公私鑰對的概念可以延生出許多系統跟應用。其中一個應用是密鑰封裝系統(Key Encapsulation Mechanism, KEM)。在密鑰封裝系統中，傳送者可以透過接收者的公鑰隨機生成一個想分享的密鑰(shared secret key)和其封裝(encapsulation)。隨後傳送者可以將這個封裝(encapsulation)傳給接受者，接收者透過自己的私鑰可以將封裝打開，透過這樣的方式就完成了密鑰的封裝與解封裝，實現了安全的密鑰共享。

密鑰封裝與交換

KEM的安全目標是防止任何不知道私鑰的人恢復有關封裝的任何信息。

假設Alice想要透過KEM與Bob分享密鑰。傳送者 Alice 會使用 Bob 的公鑰（Bob's public key）來生成密鑰跟其封裝。Alice隨後將封裝傳遞給Bob。當接收者 Bob 收到 Alice 傳送的封裝時，便可使用自己的私鑰（Bob's private key）來解開封裝，得到Alice與他分享的密鑰。

Alice與Bob透過KEM進行密鑰交換的過程會是：

Bob 擁有自己的公鑰與私鑰
Bob 公開自己的公鑰
Alice 用 Bob 的公鑰生成密鑰與封裝
Bob接受到封裝後用自己的私鑰解開得到密鑰

形成KEM的算法

在上述裡我們可以發現，使用KEM的過程中發生了三件事：生成公私鑰對(Key Generation, KeyGen)、封裝密鑰(Encapsulation, Encap)、密鑰解封(Decapsulation, Decap)。一個KEM可以透過這三個演算法來描述！

$\textrm{KeyGen}$ 演算法會生成一對公私鑰對，接收者公鑰會被公開，私鑰需要自我保存。
$\textrm{Encap}$ 演算法結合公鑰，來生成出一個密鑰與其封裝。傳送者可以透過這個演算法來生成想分享的封裝並傳送。
$\textrm{Decap}$ 演算法結合私鑰與封裝，接收者可以進行解封裝的行為來得到傳送者想交換的密鑰。

透過這三個演算法，我們可以清楚的描述一個KEM！在下一篇文章中，我們將會介紹另一個重要應用：數位簽章。