TY - THES AU - 조호성 DA - 2007/02 PY - 2007 UR - https://repository.hanyang.ac.kr/handle/20.500.11754/149447 UR - http://hanyang.dcollection.net/common/orgView/200000405433 AB - 소수의 특성을 이용한 RSA 암호시스템이나 DSS 서명 시스템은 큰 소수를 사용하여 보안성을 높인다. 하지만, 소수를 생성하는 과정은 높은 연산 비용을 요구하기 때문에 큰 소수를 사용하는 것은 시스템에 부담이 된다. 따라서 효율적인 소수 생성 알고리즘을 개발하는 것은 암호학에서 중요한 연구 주제이다. 효율적인 소수 생성 알고리즘은 소수 판단 검사의 속도에 좌우된다. 왜냐하면, 소수 판단 검사가 소수 생성 알고리즘의 수행시간의 대부분을 차지하기 때문이다. 따라서 많은 종류의 소수 판단 검사가 개발 되었으며, 그 중 가장 널리 쓰이는 검사는 trial division과 Fermat 검사를 조합한 소수 판단 검사(이하 조합 소수 판단 검사)이다. 이 검사는 지금까지 널리 사용되어 왔기 때문에 이 검사의 수행시간을 확률적 분석을 통해 예측하는 모델도 개발되었다. 2000년 Joye와 연구자들은 기존의 조합 소수 판단 검사에서 trial division 과정을 제거한 새로운 소수 생성 알고리즘(이하 JPV 알고리즘)을 제시하였다. 이들의 주장에 따르면 JPV 알고리즘이 조합 소수 생성 알고리즘에 비해 30~40%정도 빠른 것으로 나타났다. 하지만 이 비교는 Fermat 검사의 호출횟수만을 비교한 것으로 전체 수행시간이 아닌 일부 수행시간만을 비교했기 때문에 정확한 비교라고 하기 어렵다. 이와 같이 전체 수행시간을 비교할 수 없었던 이유는 JPV 알고리즘을 확률적으로 분석하여 수행 시간을 예측할 수 있는 모델이 없었기 때문이다. 본 논문에서는 먼저 JPV 알고리즘을 확률적으로 분석하여 수행시간 예측 모델을 제시하였고, 이 모델을 이용하여 JPV 알고리즘과 조합 소수 생성 알고리즘의 전체 수행시간을 비교하였다. 그 결과, 펜티엄4 시스템에서 512bit의 소수를 생성할 때, 두 알고리즘의 수행시간을 예측해보면, 기존의 조합 소수 생성 알고리즘이 JPV 알고리즘보다 더 좋다는 결론을 얻을 수 있었다. 실제 실험에서도 예측 값과 유사한 결과를 얻었다. 끝으로 JPV 알고리즘의 일부분을 변경하여 성능 개선을 시도하였으며, 그 결과 두 알고리즘이 동일한 공간을 사용할 경우, 개선한 JPV 알고리즘이 조합 소수 생성 알고리즘과 비슷한 성능을 보임을 확인하였다.; RSA cryptosystems or DSS signature schemes, using the properties of prime numbers, enhance their securities by using large primes. However, generating primes needs the high computation cost, so using large primes will be the problem on the systems. Thus, developing the efficient prime number generation is important in cryptography. Efficient prime number generation depends on the speed of the primality test because the primality test consumes most of the running time of prime number generation. Thus, many kinds of primality test are developed. Among them, the most popular primality test is combining trial division and Fermat test, called the combined primality test. Also there is a probabilistic analyses on the expected running time of combined primality test because this test has been used widely until now. In 2000, Joye et al. introduced the new prime number generation, called JPV algorithm, removed the trial division of the combined prime number generation sequence. According to them, the JPV algorithm is 30% ~ 40% faster than the combined prime number generation. However, this comparison is comparing the number of calls for Fermat test, not the total running time, but a part of running time. The reason why Joye et al. couldn't compare the total running time is that there is no probabilistic analyses on the total expected running time for JPV algorithm. In this paper, at first we do probabilistic analyses on the JPV algorithm and propose a model to expect the running time. With this model, we compare the total running time of JPV algorithm and the combined prime number generation. When 512 bits primes are generated in the Pentium4 system, our comparison results of the expected running time, based on the probabilistic analyses, show that the combined prime number generation is faster than the JPV algorithm. The experimental result is also similar to the expected running time result. Futhermore, we tried to improve the JPV algorithm when 2 algorithms are using the same size of space. The result of our try is that the performance of the proposed JPV algorithm is similar to the performance of the combined prime number generation. PB - 한양대학교 TI - JPV 알고리즘의 확률적 분석 및 성능향상 기법연구 TT - Probabilistic Analysis and Improvement of JPV Prime Number Generation TA - Jo, Ho-Sung ER -