Public key cryptosystems often involve raising elements of some group (e.g., $\mathbb{Z}$/N$\mathbb{Z}$, $\mathbb{F}_{2^n}$, or elliptic curves) to large powers. Such exponentiation can be time-consuming and is often the dominant part of modern cryptographic algorithms for encryption, key exchange, digital signatures, and authentication. An important question is how fast this exponentiation can be done, which often determines whether a given system is practical especially in resource-limited environments. The best method for exponentiation depends strongly on the group being used, the hardware the system is implemented on, and whether one element is being raised repeatedly to different powers, different elements are raised to a fixed power, or both powers and group elements vary. In this thesis, we focus on the ways to reduce effectively the number of group operations needed to perform exponentiation in the case that both powers and group elements vary.
In some algebraic structures, the computation of a large exponentiation can be reduced to a product of small exponentiations. If an abelian group $G$ admits an appropriate endomorphism $\phi$ then the single exponentiation $x^E$ can be transformed into $x^{E_0} \cdot \phi (x)^{E_1} \cdots \phi^{d-1}(x)^{E_{d-1}}$ for suitable integers $E_0,E_1 \cdots, E_{d-1}$ which in many practical instances have size $O(E^{\frac{1}{d}})$. Fortunately, elliptic curves provide various efficient endomorphisms such as the Frobenius endomorphism. The endomorphism used in exponent-folding techniques is a special case. Instead of computing each exponentiation separately and then multiplying them, computing them in a batch or simultaneously shows very good performance. Base-$\phi$ expansion methods based on the Frobenius endomorphism is known to be the most efficient approach in terms of reducing the elliptic curve operations.
In this thesis, we propose three efficient exponentiation algorithms. The first two modular exponentiation algorithms are developed in multiplicative groups $\mathbb{Z}$/N$\mathbb{Z}$, and the last scalar multiplication algorithm in additive elliptic curve groups.
First, we propose an improved batch exponentiation algorithm that enhances the combination method of the M'Ra$\ddot{i}$hi and Naccache algorithm. Our basic approach is based on the decremental combination strategy that reduces the problem size at each stage but increases the total potential gains, which contributes to reducing the combination cost. We then extend the batch exponentiation algorithm to increase the amortization effect of squarings. Moreover, we further speed up batch exponentiation in combination with the common-multiplicand multiplications technique. Our analytical results show that the proposed algorithm accelerates batch exponentiation about 25% ~ 30% over the M'Ra$\ddot{i}$hi and Naccache algorithm. In addition, the extended batch exponentiation presents a remarkable time-storage tradeoff under storage constraints.
Second, we propose a fast exponentiation algorithm that combines an enhanced exponent-folding technique with Ha-Moon\\`s common-multiplicand Montgomery multiplications method. For the enhanced exponent-folding technique, we make use of the results from our studies on batch exponentiation. For the $l$-bit exponent $E$ and modulus $N$ (e.g., $l$ = 1024), the proposed algorithm requires 1.117 $l$ + 21.5 modular multiplications on average, while it requires 1.125 $l$ + 21.5 modular multiplications in the worst case. The comparison results show that our algorithm outperforms all existing modular exponentiation methods that do not consider signed representations of the exponent.
Third, we propose fast scalar multiplication algorithms on Koblitz curves. For this we propose an improved base-$\phi$ expansion method in which the bit-length of coefficients is shorter and the number of coefficients is smaller than in Kobayashi et al.\\`s expansion method. The proposed method meshes well with efficient multi-exponentiation techniques. In addition, we present two efficient algorithms based on the proposed expansion method, named $\phi$-$w$NAF and $\phi$-SJSF, which significantly reduce the computational effort involved in online precomputation by using the property of the Frobenius endomorphism. The proposed algorithms significantly accelerate computation of a scalar multiplication on Koblitz curves over OEFs. In particular, for OEFs where the characteristic is close to 32 bits or 64 bits, the required number of elliptic curve operations is reduced by about 30\% in comparison with Kobayashi\\`s base-$\phi$ scalar multiplication algorithm. Moreover, we propose a fast and memory-efficient algorithm that performs with a very small reference table at the expense of slightly more computation. This method enables a scalar multiplication to be performed with a reference table of less than 10 precomputed points.
공개키 암호 시스템은 보통 대수 군의 한 원소에 큰 지수승을 하는 멱승 연산을 포함한다. 이러한 멱승 연산은 암호화/복호화, 키 교환, 디지털 서명, 인증 등의 다양한 암호 프로토콜에서 성능상의 지배적인 역할을 하며, 상당한 계산 시간을 요한다. 따라서 암호 시스템 구현에 있어서 가장 중요한 질문 중의 하나는 이러한 멱승 연산을 얼마나 빨리 처리할 수 있는가이며, 이는 특히 가용 자원이 제약된 환경에서 해당 시스템이 얼마나 실용적인가를 결정하는 척도가 된다. 최선의 멱승 연산 방법은 여러가지 주어진 조건에 따라 달라질수 있다. 이러한 요인으로는 암호 시스템의 기반으로 사용하는 대수 군, 멱승 연산을 처리하는 하드웨어, 그리고 밑수가 고정되어 있는지, 지수가 고정되어 있는지, 아니면 밑수와 지수 모두가 가변적인지 등을 들 수 있다. 본 학위 논문에서는 밑수와 지수가 모두 가변적인 멱승 연산을 최소 횟수의 군 연산으로 처리할 수 있는 방법에 관심을 갖는다.
어떤 대수 구조체에서는 하나의 큰 멱수 연산을 여러 개의 작은 멱승 연산으로 바꿀 수 있는 방법을 제공한다. 가환군 $G$에서 자기준동형 사상 $\phi$를 제공한다면, 하나의 멱승 $x^E$는 다음과 같은 여러 멱승 연산의 전개식으로 변형될 수 있다. 즉, $x^{E_0} \cdot \phi (x)^{E_1} \cdots \phi^{d-1}(x)^{E_{d-1}}$, 여기서 $E_0,E_1 \cdots, E_{d-1}$은 보통 $O(E^{\frac{1}{d}})$ 크기의 값을 갖는다. 타원곡선 군에서는 다행이도 효율적인 여러가지 자기준동형 사상을 제공하며, 프로베니우스 사상을 대표적인 예로 들 수 있다. 한편, Lou-Chang 등의 지수접기 방식은 이러한 자기준동형 사상의 특수한 예라 할 수 있다. 위의 전개식에서 각각의 멱승 연산을 독립적으로 처리한 다음 결과를 곱하는 방법보다 여러 개의 멱승연산을 묶어서 일괄 또는 다중 연산 방법으로 처리하면 훨씬 효과적으로 수행할 수 있다. 특히, 프로베니우스 사상을 이용한 base-$\phi$ 전개방식은 타원곡선 연산 수를 줄이는 데 있어 가장 효율적인 방법으로 알려져 있다.
본 학위 논문에서는 다음과 같은 세 가지 효율적인 멱승 연산 알고리즘을 제안한다. 처음 두 가지는 곱셈군 $\mathbb{Z}/N\mathbb{Z}$에서 효율적인 모듈라 멱승 연산 알고리즘이며, 나머지 하나는 타원곡선 덧셈군에서 효율적인 상수배 연산 알고리즘이다.
첫째, M'Ra$\ddot{i}$hi-Naccache 방식을 개선한 효율적인 일괄 멱승연산 알고리즘을 제안한다. 기본적인 접근 방법으로 단계 마다 문제 크기를 줄이면서 전체적인 잠재적 이득을 키우는 감소적 결합 전략을 취하였으며, 이는 결과적으로 결합 비용을 줄이는 효과를 가져온다. 이러한 알고리즘 기반위에서 제곱연산의 추렴효과를 증대하기 위해 확장된 일괄 멱승방법을 제시하였으며, 또한 멱승연산의 속도를 더욱 향상하기 위해 공통 피승수 곱셈방법과 결합하였다. 이는 기존의 M'Ra$\ddot{i}$hi-Naccache 방식과 비교했을 때, 25% 내지 30% 정도의 성능향상 효과를 가져오며, 또한 뛰어난 시간과 저장공간 사이의 절충관계를 제공한다.
둘째, 개선된 지수접기 방식과 Ha-Moon의 공통 피승수 몽고메리 곱셈 알고리즘을 결합한 효율적인 모듈라 멱승 알고리즘을 제안한다. 개선된 지수접기 방식은 앞서 일괄 멱승연산에서 개선한 결과를 이용하여 모듈라 멱승연산 알고리즘에 적합하도록 변형하였다. 한편, Ha-Moon의 공통 피승수 몽고메리 곱셈 알고리즘은 두개의 몽고메리 곱셈을 1.5번 정도의 계산량으로 처리할 수 있도록 해준다. $l$ 비트의 지수 $E$와 모듈라 $N$를 고려했을 때, $l$이 1024 비트 정도인 경우에 제안 알고리즘은 평균적으로 1.117 $l$ + 21.5번의 몽고메리 모듈라 곱셈을 수행하며, 최악의 경우는 1.125 $l$ + 21.5번의 몽고메리 모듈라 곱셈을 수행한다. 이는 지수표현에 음수를 고려하지 않는 기존의 모든 모듈라 멱승연산 알고리즘을 능가하는 성능이다.
셋째, Koblitz 타원곡선에서의 고속 상수배 알고리즘을 제안한다. 이를 위해, Kobayashi 등의 전개식보다 계수의 비트 길이가 짧고, 또한 전개식의 길이가 짧은 효율적인 base-$\phi$ 전개방식을 제안한다. 제안한 전개방식은 가장 효율적이라 알려진 다중 멱승연산 방식과 결합되었을 때 최적의 효과를 발휘한다. 또한, 본 논문에서는 "$\phi$-$w$NAF"와 "$\phi$-SJSF"라 명명한 효율적인 두 알고리즘을 제안한다. 이들 알고리즘은 제안한 base-$\phi$ 전개방식과 가장 효율적인 $w$NAF와 SJSF 다중 멱승 알고리즘, 그리고 사전계산 단계에서 Frobenius 자기준동형 사상을 이용하여 계산량을 획기적으로 줄일 수 있는 방법을 결합하였다. 제안한 두 알고리즘은 특히 32비트와 64비트에 가까운 특성계수를 갖는 최적 확장체상의 타원곡선에서 상수배 연산을 수행하는 데 주목할 만한 속도 향상을 가져온다. Kobayashi의 base-$\phi$ 상수배 알고리즘과 비교했을 때, 타원곡선 연산 수를 대략 30% 정도 줄여준다. 마지막으로, 상수배 연산을 수행하는 데 필요로 하는 참조 테이블의 크기를 획기적으로 줄일 수 있는 방법을 제안한다. 이는 단지 약간의 속도를 희생하는 대신 10개 이하의 타원곡선 점을 저장하는 참조 테이블로 상수배 연산을 수행할 수 있도록 해준다.
본 학위 논문의 연구는 서버나 개인 PC에서 부터 계산능력이나 대역폭, 메모리가 제한된 스마트카드, 무선 단말기, 내장형 시스템 등에 이르기까지 다양한 환경에서 공개키 암호를 효과적으로 수행하는 데 기여할 것으로 기대된다.