Earticle

초록

영어

When the public key e and the composite number n=pq are disclosed but not the private key d in an asymmetric-key RSA, message decryption is carried out by obtaining ∅(n)=(p-1)(q-1)=n+1-(p+q) and subsequently computing d=e^{-1} (mod ∅(n)). The most commonly used decryption algorithm is integer factorization of n/p=q or a^{2}≡b^{2} (mod n), a=(p+q)/ 2, b=(q-p)/2. But many of the RSA numbers remain unfactorable. This paper therefore applies baby-step giant-step discrete logarithm and 2^{k}-ary modular exponentiation to directly obtain ∅(n). The proposed algorithm performs a reverse baby-step and 2^{k}-ary adult-step. As a results, it reduces the execution time of basic adult-step to 1/2^{k} times and the memory m=⌊sqrt {n}⌋ to l, a^{l} >n, hence obtaining ∅(n) by executing within l times.

한국어

비대칭키 RSA의 공개키 e와 합성수 n=pq 은 알고 있고 개인키 d를 모를 때, ∅(n)=(p-1)(q-1)=n+1-(p+q) 을 구하여 d=e^{-1} (mod ∅(n))으로 개인키 d를 해독한다. 암호해독은 일반적으로 n/p=q 또는 a^{2}≡b^{2} (mod n), a=(p+q)/ 2, b=(q-p)/2 를 구하는 소인수 분해법이 널리 적용되고 있다. 그러나 아직까지도 많은 RSA 수들이 해독되지 않고 있다. 본 논문은 ∅(n)을 직접 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 이산대수의 아기걸음-거인걸음법과 모듈러 지수연산의 2^{k}-ary법을 적용하였다. 이 알고리즘은 역-아기걸음과 2^{k}-ary 성인걸음법을 적용하여 기본적인 성인걸음법 수행횟수를 1/2^{k} 로 줄이고, m=⌊sqrt {n}⌋의 저장 메모리 용량도 l, a^{l} >n로 감소시켜 ∅(n)을 l회 이내로 구하였다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 이산대수 알고리즘
 Ⅲ. 역 아기걸음 - 2k - ary 성인걸음 알고리즘
 Ⅳ. 실험 및 결과 분석
 Ⅴ. 결론
 References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380