나눗셈 테이블을 이용한 소수 및 안전소수 생성법의 확률적 분석

국문 초록 (Abstract)

공개키 암호시스템에서는 보안성을 높이기 위해 매우 큰 소수나 안전소수를 사용한다. 하지만 큰 소수를 생성하기 위해서는 많은 시간이 걸리기 때문에 소수를 빠르게 생성하는 연구가 중요하다. 나눗셈 테이블 순차난수 생성법은 나눗셈 테이블의 길이에 따라 소수 생성 시간이 달라지기 때문에 최적의 테이블 길이를 찾는 것이 필요하다. 현재는 모든 길이의 테이블에 대해서 실제로 소수를 생성해 본 후 그 중에서 최적의 테이블 길이를 선택하는 매우 비효율적 인 방법이 사용되고 있다. 본 논문에서는 나눗셈 테이블 순차난수 생성법의 (안전)소수 생성 시간을 예측하는 확률 적 모델을 제안한다. 이 확률 모델은 나눗셈 테이블의 길이가 인자로 주어졌을 때 (안전)소수 생성알고리즘의 수행 시간을 예측하는 모델이다. 본 연구의 실험에 따르면 이 예측 모델은 오차가 약 4% 정도로 거의 정확하게 실제 수 행시간을 예측한다. 따라서 이 예측 모델을 사용하면 실제로 소수를 생성하지 않고도 수행시간을 예측하고 거의 정 확하게 최적의 테이블 길이를 찾을 수 있다.

다국어 초록 (Multilingual Abstract)

Public-key cryptosystems use big prime numbers and safe prime numbers for strong security. However, generating big (safe) primes takes a very long time and thus a research for fast generating (safe) primes is important. When incremental search on division tables are used, it is necessary to find the optimal size of division table since the running time of (safe) prime generation depends on the size of division table. However, there is no efficient way to find the optimal size of division table without actual prime generation. In this paper, we propose a probabilistic analysis model to expect the running time of (safe) primes when incremental search on division table are used. Our model predicts the expected running time of generating (safe) primes when the size of division table is given as a parameter. Our experimental results show our model expects actual running time accurately with 4% error. Therefore, with our model, one can predicts the expected running time and the optimal table size very accurately without any actual (safe) prime generation.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 기존 소수생성법
• 2.1 TD-MR검사법을 이용한 소수 및 안전소수생성
• 2.2 DT-MR검사법을 이용한 소수 및 안전소수생성
• 3. 연구내용
• 3.1 DT-MR검사법 수행시간의 확률적 분석
• 3.2 DT-MR-MR검사법 수행시간의 확률적분석
• 4. 실험 및 분석
• 4.1 DT-MR의 실험환경 및 결과
• 4.2 DT-MR-MR의 실험환경 및 결과
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 김진복, "스마트폰 사용자를 위한 단계별 복합 인증" 한국차세대컴퓨팅학회 7 (7): 4-12, 2011

2 KISA, "스마트폰 보안을 위한 국산 암호알고리즘 적용방안 연구"

3 조호성, "나눗셈 테이블을 이용하는 순차 난수 생성법의 확률적 분석" 1330-1332, 2013

4 박미옥, "‘모바일 디바이스 환경에서의 사용자 익명성을 위한 원격 사용자 인증기법’에 대한 취약점 분석" 한국차세대컴퓨팅학회 10 (10): 6-13, 2014

5 Miller, G. L., "Riemann’s Hypothesis and Tests for Primality" 13 (13): 300-317, 1976

6 Richardson, C., "Professional Java JDK" John Wiley & Sons 2007

7 PARK, H. J., "Probabilistic Analysis on the Optimal Combination of Trial Division and Probabilistic Primality Tests for Safe Prime Generation" E94-D (E94-D): 1210-1215, 2011

8 McCombs, B., "Microsoft windows 7" 15 (15): 75-77, 2010

9 박희진, "JPV 소수 생성 알고리즘의 확률적 분석 및 성능 개선" 한국정보과학회 35 (35): 75-83, 2008

10 Cormen T. H., "Introduction to Algorithms" MIT press 2009

11 Kruglinski, D. J., "Inside Visual C++" Microsoft press 1997

12 Menezes, A. J., "Handbook of Applied Cryptography" CRC Press 1996

13 Maurer, U. M., "Fast generation of prime numbers and secure public-key cryptographic parameters" 8 (8): 123-155, 1995

14 박기웅, "Design & Implementation of Mutually Verifiable Billing System for Cloud Computing Environment" 한국차세대컴퓨팅학회 5 (5): 4-17, 2009

15 Stallings, W., "Cryptography and Network Security Principles and Practices" Prentice Hall 2005

16 Kurniawan, B., "Android Application Development:A Beginner's Tutorial:"

17 Ateniese, G., "A practical and provably secure coalition-resistant group signature scheme" 255-270, 2000

18 Rivest, R. L., "A method for obtaining digital signatures and public-key cryptosystems" 21 (21): 120-126, 1978

19 ElGamal, T., "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" IT-31 (IT-31): 469-472, 1985