馬可利斯公鑰密碼系統之三分法反應攻擊

Abstract

馬可利斯公鑰密碼系統是第一個結合了代數編碼領域及密碼領域的公鑰密碼系統。 Hall 等三位學者於 1999 年提出了第一個對於馬可利斯公鑰密碼系統的反應攻擊。 相較於選擇密文攻擊而言，反應攻擊可行性較高，但需要較多的詢問次數。 在這篇論文當中，我們提出一個三分法反應模型。 該模型假設解密者對於一個不合法的密文，將判斷是否仍可解密同時明文正確， 據此給予兩種程度不同的警告回應，並對於合法的密文，給予確認回應。 我們證明若存在一個演算法解決比較型偽硬幣問題，則對於符合三分法反應模型的馬可利斯公鑰密碼系統實作， 其相對應的攻擊演算法亦存在。更進一步地，我們提出一個有效率的演算法解決比較型偽硬幣問題。 結合前述的結論，我們得到一個三分法反應攻擊演算法，能花費較少的詢問次數，便得以從密文還原明文。

McEliece public-key cryptosystem is the first system combining cryptography and algebraic coding theory. In 1999, Hall et al. introduced the reaction attack on McEliece's and two other cryptosystems. Compared with chosen-ciphertext attacks, the reaction attack has higher feasibility. However, it requires more queries. In this thesis, we propose a trichotomy reaction oracle model. In this model, the key-owner is assumed that when a illegal ciphertext is received, he determines if the ciphtext is still decryptable and the plaintext is correct, then replies two different warning responses according to the judgement. And he replies an acknowledgement response when a legal ciphertext is received. We prove that if there is an algorithm which solves the comparative counterfeit coins problem, then there is an attack algorithm on the improper implementation which matches the trichotomy reaction oracle model. Furthermore, we design an efficient algorithm to solve the comparative counterfeit coins problem. Combined with the previous conclusion, a trichotomy reaction attack algorithm with fewer queries requirement is induced.