멀티코어 CPU 환경을 이용한 소프트웨어 기반의 빠른 소수 생성 방법

손하림, 장재찬, 이윤호 · 정보과학회논문지 : 정보통신 · 2013

본 논문은 RSA 알고리즘에서 키 생성 등에 필요한 소수를 효율적으로 생성하는 방법에 대해 논의한다. 본 연구는 현재의 PC 및 스마트폰 환경이 다수의 코어를 갖는 환경인 것을 이용한다. 이를 바탕으로 현재까지 Miller-Rabin test등 확률적인 소수 테스트를 기반으로 하는 방법들 중 가장 효율적이라고 알려진 Bit-array 방법에 대한 병렬화를 시도한다. 제안 방법에서는 Bit-array 알고리즘 수행 도중에 작은 소수를 이용하여 나누어 보는 기본 테스트 과정을 통과한, 즉 Miller-Rabin test 의 수행을 통해 소수인지 아닌지 검증해야할 후보 소수들을 다수의 코어들을 통해 한꺼번에 테스트 한다. 구현을 통해 제안 방법의 성능 향상을 검증하였으며, 일반적인 Desktop 환경에서 1024bit 소수 생성 알고리즘 구현 시 2개의 코어를 사용 시 단일 코어 사용의 경우에 비해 약 110%, 4개의 코어를 사용 시 약 265% 의 성능 향상이 있었다. 본 연구의 결과는 권한 위임을 위해 공개키를 임시키로 사용하는 대리 인증서 환경[14]에서 권한 위임의 효율성을 향상시킬 때 공헌할 것으로 기대한다.

Cited by 3 works.

Authors

References