To solve the key exchange and digital signature problems of conventional cryptosystems, Diffie and Hellman proposed a new concept public key cryptography in 1976[1]. In a public-key cryptosystem, each user has a pair of keys, and publicize one element of them and this is called a public key. If another user wants to secretly sends a message to that user (say A), he encrypts the message with A's public key and sends the ciphertext to A. Then A can decrypt the ciphertext with his private key, which is the other element of the key pair. In this scenario, there is no need for a secure channel. Furthermore, the inverse procedure of the above process acts as a digital signature scheme [1-4]. This new concept is an innovation in the cryptographic society, and allows the current electronic commerce and secure communication and authentication on the insecure network, such as Internet or wireless network.
However, the public-key cryptosystem is very slow compared to the conventional symmetric cryptosystem. The main reason of the poor performance of the public-key cryptosystem is as follows. First of all, the public-key concept is based on the existence of trap-door one-way functions, and the known such functions require very large numbers that cannot be efficiently performed on the current computers. Furthermore, as public-key infrastructure is being constructed and electronic commerce is being widespread, the needs for massive authentication and secure communication increase. Also, there must be very efficient computation algorithms for embedding the public-key cryptosystem in the devices which have poor computing power such as smartcards or mobile handsets.
In this thesis, we investigate fast computation algorithms and protocols of public-key cryptographic operations. Especially, we focus on the efficient computation methods in the environment that the computing power of the device is too weak to perform the cryptographic operations in the reason able time, or the environment that the overall performance of the system is dependent on the computation time of the cryptographic operations. The research topics of this thesis is composed of three subjects.
First, we propose a new approach to SASC protocols, The previous approach is that the client splits the secret information of the client into many pieces of informations, and then sends some of them to the server (from now we will call this approach splitting-based one). This splitting-based approach has some shortcomings that cannot be overcome. First of all, a secret computation causes the large amount of communication and requires very heavy computation of the server. Although the server's computing power is predominant over the client's one, a lot of modular exponentiation requires considerable computation time and there can be some environments that the server is heavy loaded or the computing power gap between the server and the client is not very large. Moreover, the previous approach makes SASC protocols be vulnerable to various attacks due to the many informations generated by the client and computed by the server.
The proposed approach dose not use the decomposition. The basic idea is as follows: the client blinds the secret information by using a series of random numbers to conceal the secret from the server before transferring it to the server, instead of decomposing it. The proposed protocol is secure against all known active and passive attacks including probabilistic active attack. The number of modular multiplications required at the client in the proposed protocol is about half of those in the previous ones, furthermore the time required at the server and the amount of communication are very small and irrespective of security parameters. Consequently, the total time required to generate RSA signature by using the proposed protocols in any environment.
second, we propose new applications that use SASC protocols. The current computing environments have become various because of the development of wired and wireless internet. For example, mobile stations can connect to the internet, PDAs (personal digital assistants) are widely used, and the usage of notebook computers is various. These various computing environments have newly arisen security requirements, so there must be efficient cryptographic computation software. In this thesis, we show that SASC protocols are good candidates in some environments, and give a guideline to apply SASC protocols to such environments. We focus two environments. One is a mobile handset in mobile communication, and the other is an authentication server that must perform massive signature generation operations. (For example, payment gateway in electronic commerce, a broker system in a micro payment system, and etc.)
Third, we propose an efficient scalar multiplication method on elliptic curves. An elliptic curve cryptosystem is a special case of publick-key cryptosystems, which is focused as a next generation cryptosystem because shorter key length is enough for providing the same cryptographic strength compared to other public-key cryptosystems. The core operation of the elliptic curve cryptosystems is the scalar multiplication on elliptic curves. Because this is composed of repeated point additions, there is an analogy with modular exponentiation. So the previous method and techniques that were used in accelerating modular exponentiations can be used in scalar multiplication on curves. However, it is possible to accelerate the elliptic curve operations by using curve characteristics. In this thesis, we use Frobenius map to perform scalar multiplications over elliptic curves, especially defined over higher characteristics finite field. Although the previous methods also use Frobenius map, we propose another approach to apply Frobenius map for even further accelerating the computation by changing the computation sequence. The proposed computing sequence make it possible to use memory efficiently, and resultantly the number of point additions for a scalar multiplication is reduced. Another proposal is about reducing the multiplication and squaring time on higer characteristic finite fields.
현대의 공개키 암호시스템은 키전달을 효과적으로 해결할 수 있고, 전자서명을 해결해 줄 수 있는 장점으로 인해 많은 관심을 받고 연구되고 있다. 그러나, 공개키 암호시스템은 필요한 안전도를 확보하기 위해 매우 큰 수들을 다루기 때문에, 구현시에 원하는 속도를 얻기가 어렵다. 따라서, 공개키 암호시스템을 효율적으로 구현하기 위한 많은 연구들이 있어왔다.
본 논문에서는 공개키 암호 시스템의 핵심 연산을 빠르게 계산하는 알고리즘 및 프로토콜들에 대해 살펴본다. 특히, 공개키 암호 연산을 수행하기에 무리가 될 정도로 컴퓨팅 파워가 떨어지는 플랫폼에서, 혹은 공개키 암호 연산이 시스템의 성능을 좌우하는 인증서버와 같은 환경에서 효율적으로 계산할 수 있는 방법들에 초점을 둔다. 처음 공개키 암호 시스템이 제안될 당시에는 컴퓨터의 성능이 문제가 되어, 일반적인 컴퓨팅 환경에서 조차 전자서명이나 공개키 암호화를 수행하기에 문제가 있었다. 그러나, 현재의 컴퓨터 시스템들은 성능이 월등히 좋아져서, 처음 공개키 암호시스템들이 제안 될 당시의 문제점들은 없어졌다. 즉, 일반적으로 널리 사용되는 개인용 컴퓨터나 웍스테이션들에서 암호화나 전자서명을 수행하는데 1초 이내에 수행될 수 있다. 그러나, 앞에서 언급한 특수한 환경들에서는 공개키 암호시스템을 채택하기에 여전히 문제가 있으며, 현재의 인터넷 환경에서 전자상거래가 활성화가 되는 것을 둔화시키고 있다. (예를들면, SET 프로토콜이 사회 전반에 정착되지 못함으로써, 개인정보와 신용카드 정보들이 보호되고 있지 못하는 현재의 상황 및 무선 환경에서 공개키 암호 시스템을 채택하지 못함으로써 부인방지 및 전자서명과 같은 기능을 제공하지 못하는 상황, 그리고 스마트 카드 시스템의 활성화가 지연되는 상황 등)
본 논문의 연구는 크게 세 가지로 나뉜다. 첫째, SASC 프로토콜에 대한 새로운 접근 방법을 제안한다. 서버의 도움을 받는 비밀 계산 프로토콜에 관한 연구이다. 기존의 SASC 프로토콜들은 클라이언트의 비밀정보를 여러 조각으로 분리해서, 그 중의 일부를 서버에 전달함으로써 많은 계산을 서버가 수행하도록 하는 방법을 취해 왔다. (앞으로 Splitting-based approach 라고 부른다) 그러나, 기존의 연구들에서 알 수 있듯이 이러한 접근 방법은 극복하기 어려운 몇 가지 단점을 가진다. 우선, 한 번의 비밀 계산을 위해 많은 정보들이 서버와 클라이언트 사이에서 교환되어야 하기 때문에, 통신량이 많아진다. 또한, 서버는 클라이언트가 전달한 모든 정보들에 대해(필요 없는 연산까지 포함하는) 연산을 수행해야 하는데, 그 양이 매우 많아 전체 시스템의 성능을 떨어트리게 된다. 게다가, 서버에게 전달된 많은 정보들로 인해, 공격자에게 많은 힌트를 주게 된다. 본 논문에서는 이러한 단점을 극복하기 위해 SASC 프로토콜에 대한 새로운 접근 방법을 제안한다. 제안하는 접근 방법은 클라이언트의 비밀정보를 여러 조각으로 나누는 대신, 다른 정보들로 감싸서 새로운 형태의 정보로 변형시켜 서버에 전달한다. (앞으로 Blinding-based approach라고 부른다) 따라서, 서버에 전달할 데이터양이 적어서 통신량, 서버의 계산량이 줄어들고, 공격자가 엿볼 수 있는 Hint가 없어진다.
둘째, 본 논문에서는 SASC 프로토콜의 새로운 응용 분야에 대해 제안한다. 인터넷과 무선 인터넷의 발전으로 인해 현재의 컴퓨팅 환경은 과거와 다르게 매우 다양해졌다. 예를 들면, 이동통신 단말기에서 인터넷 접속이 가능해지고, 개인정보 단말기(PDA: Personal Data Assistant)가 보편화되며, 노트북 컴퓨터들의 활용이 다양해지고 있다. 또한, 휴대가 간편하고, 보안 기능이 좋아 스마트 카드도 점차 응용 분야를 넓혀가고 있다. 이러한 다양한 컴퓨팅 환경은 계속해서 변화하는 보안 요구사항을 가지게 되고, 근본적으로 정보를 보호하는 암호 연산이 보다 가볍고 효율적으로 구현되기를 요구한다. 본 논문에서는 이러한 환경에서 SASC 프로토콜이 좋은 대안이 될 수 있음을 보이고, SASC 프로토콜을 안전하고 효율적으로 적용할 수 있는 가이드라인을 제공한다. 본 논문에서 목표로 하는 환경은 크게 두 가지이다. 하나는 이동통신 단말기에서 공개키 암호 연산을 수행해야 하는 환경이고, 다른 한 가지는 전자서명을 과도하게 수행해야 하는 인증서버 환경이다. (예를 들면, 전자상거래에서의 지불 게이트웨이, 소액지불 시스템에서의 중개 시스템 등이 있다.)
마지막으로, 본 논문에서는 타원곡선 암호 연산을 효율적인 계산 방법을 제안한다. 타원곡선 암호 시스템은 공개키 암호 연산의 특수한 한 형태로서, 짧은 키 길이로 기존의 암호시스템과 같은 안전도를 제공하는 장점으로 인해 미래의 암호시스템으로 주목받고 있는 암호 시스템이다. 타원곡선 암호 시스템은 기존의 유한체나 링 위에서의 연산을 타원곡선 그룹 위에서의 연산으로 변환함으로써 공격을 어렵게 만들어 짧은 키 길이를 유도한다. 따라서, 핵심이 되는 연산은 타원곡선 위에서의 한 점에 대한 상수배 연산이고, 본 논문의 목표도 이 연산을 빠르게 수행하는 것이다. 타원곡선 위에서의 상수배 연산은 유한체 위에서의 모듈라 멱승 연산과 일대일 대응이 가능한 연산으로 이루어져 있어서, 기존의 모듈라 멱승 연산에 사용되는 기법들이 대부분 적용 가능하다. 그러나, 타원곡선 자체의 특성을 이용하면 보다 효율적인 연산이 가능하다. 본 논문에서 타원곡선 연산을 빠르게 하기 위해 적용하는 기법은 두 가지이다. 하나는 최적 확장체 위에서 정의된 타원곡선 위에서, 상수배 연산을 위해 프로비니어스 맵을 효과적으로 이용함으로써, 상수배 연산에 필요한 덧셈 연산의 회수를 줄이는 방법이다. 하는 하나는, 최적 확장체 위에서의 곱셈과 제곱 연산을 효율적으로 수행하는 방법이다.