GF(2^(n)) 상의 병렬 멱승 연산의 라운드 수 향상 알고리즘 = An Algorithm For Reducing Round Bound of Parallel Exponentiation in GF(2^(n))

국문 초록 (Abstract)

GF(2^(n))상의 멱승 (exponentiation) 연산은 암호 관련 응용에서 널리 사용되고 있으며, 안전성을 위해 의 n값을 크게 설정하여 이용하고 있다. 그런데, n의 값이 커짐에 따라 수행해야 하는 곱셈의 횟수도 따라서 증가하게 되고, 결과적으로 속도가 빠른 연산 알고리즘의 개발이 중요한 문제로 대두되고 있다. 본 논문에서는 정규 기저 표현(normal bases representation)을 갖는 GF(2^(n))상의 병렬 멱승 연산에 있어서, 프로세서 수가 고정된 경우에 라운드 수를 개선할 수 있는 알고리즘을 제안하고 이의 성능분석을 수행한다. 제안하는 방안은 지수(exponent)를 특정 비트 수로 나누어 멱승을 수행하는 윈도우 방법 (window method)를 이용하는 것으로, 윈도우 값 계산 단계에서 휴지 프로세서들로 하여금 윈도우들 간의 곱을 계산하도록 함으로써, 전체 라운드 수를 줄이는 효과를 갖는다.

다국어 초록 (Multilingual Abstract)

Exponentiation in GF(2^(n)) is widely used in practical applications related with cryptography, and as the discrete log is easily solved in case of a low exponent , n_(I) a large exponent n is needed for a more secure system. However, since the time complexity for exponentiation algorithm increases in proportion to the figure, the development of an exponentiation algorithm that can quickly process the results is becoming a crucial problem. In this paper, we propose a parallel exponentiation algorithm which can reduce the number of rounds with a fixed number of processors, where the field elements are in GF(2^(n)), and also analyzed the round bound of the proposed algorithm. The proposed method uses window method which divides the exponent in a particular bit length and make idle processors in window value computation phase to multiply some terms of windows where the values are already computed. By this way, the proposed method has improved round bound.