인수분해 공식과 정규기저를 이용한 GF(2m)상의 고속 곱셈 역원 연산 알고리즘

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 30권 / 6호 / 324 ~ 329페이지
· 저자명 : 장용희, 권용진

초록

Diffie-Hellman 키분배 시스템과 타원곡선 암호시스템과 같은 공개키 기반 암호시스템은GF(2m) 상에서 정의된 연산, 즉 덧셈, 뺄셈, 곱셈 및 곱셈 역원 연산을 기반으로 구축되며, 이들 암호시스템을 효율적으로 구현하기 위해서는 위 연산들을 고속으로 계산하는 것이 중요하다. 그 중에서 곱셈 역원이 가장 time-consuming하여 많은 연구 대상이 되고 있다. Fermat 정리에 의해 β∈GF(2m)의 임의의 원소에 대해 곱셈 역원을 고속으로 계산하기 위해서는, 2m - 2을 효율적으로 분해하여 곱셈 횟수를 감소시키는 것이 가장 중요하며, 이와 관련된 알고리즘들이 많이 제안되어 왔다. 이 중 Itoh와 Tsujii가 제안한 알고리즘[2]은 정규기저를 사용해서 필요한 곱셈 횟수를 O(log m)까지 감소시켰으며, 또한 이 알고리즘을 향상시킨 몇몇 알고리즘들이 제안되었지만, 분해과정이 복잡하다는 등의 단점이 있다[3,5]. 본 논문에서는 실제 어플리케이션에서 주로 많이 사용되는 m = 2n 인 경우에, 인수분해 공식
x³- y³= (x - y)(x²+ xy + y²)와 정규기저를 이용해서 곱셈 역원을 고속으로 계산하는 알고리즘을 제안한다. 본 논문의 알고리즘은 곱셈 횟수가 Itoh와 Tsujii가 제안한 알고리즘 보다 적으며, 2m - 2 의 분해가 기존의 알고리즘 보다 간단하다.

참고자료

· 없음