The Public Key Infrastructure (PKI) and Wireless PKI(WPKI) are essential to many kinds of electronic businesses through the Internet. A certificate and related mechanism such as the Certificate Revocation List (CRL), and the certificate path validation are important components in PKI and WPKI.
However, because a certificate does not contain its full path, a verifier must check the certificate revocation status and perform the certificate path validation, step by step. Even though a verifier finished to check the certificate revocation status and perform the certificate path validation, a verifier can only know the probabilistic answer about thaget certificate, because a CRL is published in every periodic time.
In this thesis, we will propose two schemes. One is a new approach of X.509v3 certificate for full path validation. Using our proposal scheme, we can reduce the time complexity of the certificate path validation from $\emph{O(n)}$ to $\emph{O(n)}$, when $\emph{n}$ is the size of the certificate full path. In addition, using our proposed scheme, we will show an application, the Online Certificate Verification Protocol(OCVP), which requires neither the CRL mechanism nor a new trusted server. With respect to the computational load, the loads in OCVP is $\emph{2n}$ which the same in the Simple Certificate Validation Protocol (SVCP). However, SCVP uses the CRL mechanism and a new trusted server, and gives us a probabilistic answer. But, OCVP uses all CAs who are located on the certification full path and gives us an exact answer.
The other can be considered as one of alternatives for CRL, a CA live list (write CAL). The point of our proposed concept is that for CA's certificate we manage a live list in the place of a revoked list. In the ordinary case, we must check the certificate revocation status and perform the certificate path validation. However, using CAL, we only check the CA live status. Therefore, in the certificate path validation, we reduce $\emph{n-1}$ times of the signature verification. Using the new concept, CAL, We'll show an application, an efficient online path validation with CAL server. CAL server is a new trusted server which responds to a well formed request. It checks the CA live status and performs the verification of the last end relation < CA, $\emph{user}$ > according to the request message types.
Our proposed two schemes can be applicable th each other. And, our proposed schemes are not considered the policies. For this, we need to study on the applicable usages and the policies.
인터넷이 점점 활성화되면 될수록, M-Commerce, B2B, B2E 같은 인터넷을 통한 사업이 증가하고 있다. 공개키 기반 구조와 무선 공개키 기반 구조는 이러한 인터넷을 통한 사업의 핵심이다. 공개키 기반구조는 인증서, 공인인증기관, 사용자, 인증서 폐지 목록을 위한 저장소, 공개키 암호 시스템이나 서명 같은 암호학적 알고리즘, 그리고 그들의 계산에 사용되는 여러 메카니즘으로 구성되어 있다.
특히, 인증서는 공개키와 그것에 대응하는 비밀키를 지닌 소유자를 묶어 주는 문서로써, 공개키 기반 구조와 무선 공개키 기반 구조에서 그 인증서의 검증은 매우 중요하다.
인증서는 유효기간으로 지니고 있어 그 기간안에서만이 적법성을 가질 수 있다. 그러나, 비밀키의 손실, 바이러스에 대한 오염, 해커에 대한 공격, 이름 변경 등의 이유로 인하여 인증서를 폐지하는 경우가 발생하게 된다. 이러한 경우, 그 인증서를 발행한 해당 공인인증기관은 인증서 폐지 목록을 작성하여 공개하여야만 한다. 이 인증서 폐지목록은 각 공인인증기관에 의하여 주기적으로 갱신된다.
그러므로, 사용자가 인증서를 전달받았을 때, 먼저, 그는 그 받은 인증서가 폐지되었는 지를 확인하여야만 한다. 그러나, 이 인증서 폐지 목록은 그 관리 비용이 다른 공개키 기반 구조의 요소들보다 많이 소요되며, 그 사이즈 또한 절대적으로 크다. 그러나, 이러한 문제점들에도 불구하고 인증서 폐지 목록은 현재 버전 2까지 개발되어 사용중에 있다. 이러한 문제점들을 개선하기 위한 방법들이 지금까지 많이 개발되고 있다.
이러한 노력 중에는 실시간 인증서 상태 프로토콜과 간단한 인증서 검증 프로토콜이 있다. 이 두 프로토콜은 모두 질의/응답 프로토콜이지만, 실시간 인증서 상태 프로토콜은 단순한 인증서 폐지 여부 만을 체크하여 알려주는 프로토콜인데 반하여, 간단한 인증서 검증 프로토콜은 좀 더 다양한 질의에 응답할 수 있도록 설계되어 있다. 그러나, 이 두 프로토콜 모두 새로운 신뢰 기관을 필요로 한다.
인증서의 폐지 여부의 확인 후에, 사용자 또는 사용자가 신뢰하는 제 3의 신뢰 기관은 인증서 경로 검증에 들어가게 된다. 그러나, 현 인증서는 인증서 전체 점증 경로를 포함하지 않기 때문에 검증자는 단계별로 인증서를 검증할 수 밖에 없다. 따라서, 전체 인증 경로의 크기를 n, 검증 시간을 t라고 할 때, 그 시간 복잡도는 $\emph{O(n)}$이다.
이 논문에서 우리는 두 가지를 제안하였다. 그 첫번째는 전체 인증경로를 위한 현 인증서 X.509v3에 대한 새로운 접근방법이다. 이 제안하는 방법을 사용하였을 때, 우리는 인증서 경로를 검증하는 데 필요한 시간 복잡도 $\emph{O(n)}$을 $\emph{O(1)}$로 줄일 수가 있었다. 우리는 우리가 받은 인증서의 일련 번호로부터 전체 인증 경로를 알 수가 있으며, 이로 인하여 우리는 우리가 필요한 인증서 및 인증서 폐지 목록을 한꺼번에 획득할 수가 있고 나아가, 인증서 경로 검증을 병렬적으로 수행할 수가 있기 때문이다.
부과적으로 우리는 제안하는 방법을 사용한 사용 방법, 실시간 인증서 검증 프로토콜을 제시하였다. 실시간 인증서 검증 프로토콜은 인증서 폐지 목록 시스템과 새로운 신뢰 기관을 필요로 하지 않는다. 계산량의 측면에서 보았을 때, 제안하는 프로토콜은 간단한 인증서 검증 프로토콜과 같이 $\emph{2n}$번의 서명 생성 및 검증을 수행한다. 그러나, 실시간 인증서 검증 프로토콜은 인증서 폐지 목록 시스템과 새로운 신뢰기관을 필요로하는 이유로 인하여, 인증서의 상태를 확인하는데 있어서 확률적 응답을 하는데 반하여, 제안하는 프로토콜은 각 공인인증기관에 의하여 수행되므로 정확한 응답을 한다.
다른 하나는 새로운 개념, 공인인증기관 현존 목록이다. 이 제안하는 새로운 개념은 인증서 폐지 목록을 다루기 보다, 살아있는 공인인증기관에 대한 목록을 다루는 것이다. 일반적인 방법에서, 우리는 인증서 폐지 상태를 확인하고 인증서 경로를 검증하여야만 한다. 그러나, 이 공인인증기관 현존 목록을 사용하는 경우, 우리는 오직 이 목록만을 확인함으로써 그 목적을 다 할 수 있다. 그러므로, 인증서 전체 경로 검증에서 우리는 계산량의 측면에서 \emph{n-1}의 계산을 줄일 수가 있었다.
또한, 우리는 제안하는 새로운 개념의 응용 방법을 제시하였다. 공인인증기관 현존 목록 서버는 미리 약속된 질의에 대한 응답을 하는 새로운 신뢰 기관이다. 이는 질의의 종류에 따라, 공인인증기관에 대한 현존 상태 또는 마지막 공인인증기관과 사용자의 관계(<\emph{end CA, user}>), 즉 마지막 공인인증기관이 사용자의 인증서에 서명을 했는지를 확인한다.
