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회 이내로 구하였다.