可證明安全的公開金鑰密碼系統與通行碼驗證金鑰交換

Abstract

在本篇論文中，我們探討兩個主題：公開金鑰密碼系統與通行碼驗證金鑰交換。

公開金鑰密碼系統：在ElGamal加密系統中，當要加密的明文大於它的模數$p$時，明文必須被切割成數個片段， 使得每一個片段都必須小於$p$，並針對每一個片段進行ElGamal加密。Hwang等人提出一個新的方法稱為ElGamal-like加密系統，目的是在加密較大明文時，具有效率。我們將指出，不論該系統是否運算在二次剩餘下，ElGamal-like加密系統並不符合\textsf{IND-CPA}且在加解密過程中會有機率導致失敗。

為了達到加密較大明文時能較有效率，我們提出一個轉換方式，將符合\textsf{IND-CPA}的ElGamal加密系統轉換成在隨機神諭模式下，符合\textsf{IND-CCA2}，稱為ElGamal-extended加密系統。為了證明不論明文長度為何，在加密過程只產生兩個亂數值是安全的，我們定義一個新的安全符號，稱為\textsf{IND-CPA}$_\textsf{PAIR}$。ElGamal-extended加密系統在加解密過程中，運算複雜度及所需的資料傳輸都比其他的加密系統有效率。

通行碼驗證金鑰交換：允許兩端（如一端為客戶端，另一端為伺服器端）經由人類可記憶的通行碼在非安全的通道上建立會議金鑰，藉由該會議金鑰來建立安全認證的通道。我們首先指出部份提出的通行碼驗證金鑰交換方法，遭受到偽造認證攻擊、離線通行碼猜測攻擊及無法提供完整性順向機密。

我們進一步提出一個簡易的通行碼驗證金鑰交換，其對稱加密是經由一個遮罩產生函式，也就是將要傳遞的訊息乘上通行碼的雜湊結果。此方法的安全證明在Bellare-Pointcheval-Rogaway安全模式底下並假設計算的Diffie-Hellman問題是困難的且雜湊函式為隨機神諭。同時，我們進一步提出一個新的保護通行碼更換協定，在這方法中，允許使用者任意更換其通行碼。

In this thesis, we focus on two topics: public key cryptosystems and password authenticated key exchange protocols. Public Key Cryptosystems. In the ElGamal cryptosystem, when the plaintext is lager than the modulus p, it should be divided into several pieces which are smaller than p and then each piece is applied to ElGamal cryptosystem one by one. Hwang et al. proposed an ElGamal-like cryptosystem for encrypting a large plaintext efficiently. However, we show that their scheme is insecure against IND-CPA whether the cryptosystem is operated in the quadratic residue modulo p or not. Moreover, the encryption and/or decryption in their scheme have the probability to be failed. In order to encrypt a large plaintext efficiently, we present an efficient conversion from IND-CPA secure ElGamal encryption scheme to a IND-CCA2 secure extension of the ElGamal encryption scheme in the random oracle model, called the ElGamal-extension cryptosystem. To demonstrate that the ElGamal-Extension cryptosystem is secure using only two random numbers no matter what the length of a plaintext, a new security notation INDCPAPAIR is constructed. The proposed scheme is more efficient than other cryptosystems in terms of computational complexity and the amount of data transformation. Password Authenticated Key Exchange Protocols. A password authenticated key exchange (PAKE) protocol allows two parties (a client and a server) to establish a session key when the secret key used for authentication is a human-memorable password. We show some (PAKE) schemes are vulnerable to the forged authenticator attacks, off-line password guessing attacks, and do not provide perfect forward secrecy. We present a simple PAKE protocol which was conjectured secure when the symmetric-encryption primitive is instantiated via a mask generation function that is the product of the message with a hash of the password. This protocol is secure in the Ballare-Poincheval-Rogaway security model under the assumption that the computational Diffie-Hellman problem is hard and that the hash functions closely behaves like a random oracle. At the same time, we propose a new protected password change (PPC) protocol. The PPC protocol offers users the freedom of changing passwords at will. Keywords: Adaptive chosen-ciphertext attack, authentication, chosen-plaintext attack, Diffie-Hellman problem, chosen-ciphertext attack, forged authenticator attack, indistinguishable, key exchange, non-malleability, off-line password guessing attack, one-wayness, password, provably secure, public key cryptosystem, random oracle.