Earticle

본 논문은 비트코인 채굴에 필요한 SHA-256 암호 해시 값(n)을 구성하는 2개의 소수(p,q)를 빠르게 해독하는 소인수분해법을 다룬다. 본 논문에서는 Pollard's Rho 소인수분해 알고리즘의 수행횟수를 월등히 감소시킨 알고리즘을 제안하였다. Rho(p) 알고리즘은 (Xo,Yo)=(2,2) 초기치에 대해 Xi=X²-1+1(modᥒ)과 y²i-+1](modᥒ)을 계산하여 1<gcd(|Xi-Yi|,n)<n으로 소인수를 구한다. 이 알고리즘은 특정 합성수에 대해서는 소인수 분해에 실패할 수 있다. 제안된 알고리즘은 Pollard Rho 알고리즘에 (Xo,Yo)=(2k,2k)와 (2k,2),2≤k≤10을 적용하였다. 그 결과 모든 합성수에 대해 소인수분해를 할 수 있었으며, Pollard Rho 알고리즘의 수행횟수를 감소시켰다.

This paper deals with integer factorization of two prime p,q of SHA-256 secure hash value n for Bit coin mining. This paper proposes an algorithm that greatly reduces the execution time of Pollard's rho integer factorization algorithm. Rho(p) algorithm computes Xi=X²-1+1(modᥒ) and y²i-+1](modᥒ) for intial values (Xo,Yo)=(2,2) to find the factor 1<gcd(|Xi-Yi|,n)<n. It however fails to factorize some particular composite numbers. The algorithm proposed in this paper applies multiple initial values (Xo,Yo)=(2k,2k) and (2k,2),2≤k≤10 to the existing Pollard's Rho algorithm. As a results, the proposed algorithm achieves both the factorization of all the composite numbers and the reduction of the execution time of Pollard's Rho by .

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

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.

큰 반소수 n = pq의 소인수 p,q를 나눗셈 시행법으로 직접 찾는 것은 현실적으로 거의 불가능하다. 따라서 대 부분의 소인수분해 알고리즘은 a2 ≡b2(mod n)의 제곱합동을 찾아 p = GCD(a-b,n), q=GCD(a+b,n)의 소인수를 찾는 간접 방법을 적용하고 있다. n = pq에 대해 p와 q를 선택한 영역은 l(p) = l(q) = l( ) = 0.5l(n)의 [10 ⋯ 01, 99 ⋯ 9] 범위에서  을 기준으로 10 ⋯ 00<p< 과 <q<99 ⋯ 9]에 존재한다는 사실만이 밝혀 졌다. 본 논문은 n으로 부터 획득한 정보를 이용하여 p의 범위를 보다 축소시키는 방법을 제안한다. 제안 방법은 n = nLR + nRL, l(nLR) = l(nRL) = L( )으로 분할하여 pmin = nLR, qmin = nRL로 설정하는 방법을 적 용하였다. 본 논문에서 제안한 n의 정보 로 p의 범위를 축소하는 방법은  의 정보로 p의 범위 축소 방법에 비해 최소 17.79%에서 최대 90.17%의 범위 축소 효과를 얻었다.

It is impossible directly to find a prime number p,q of a large semiprime n = pq using Trial Division method. So the most of the factorization algorithms use the indirection method which finds a prime number of p = GCD(a-b, n), q = GCD(a+b, n); get with a congruence of squares of a2 ≡ b2(mod n). It is just known the fact which the area that selects p and q about n = pq is between 10 ⋯ 00 < p <  and < q < 99 ⋯ 9 based on  in the range, [10 ⋯ 01, 99 ⋯ 9 of l(q) = l() = 0.5(n). This paper proposes the method that reduces the range of p using information obtained from n. The proposed method uses the method that sets to pmin = nLR, qmin = nRL ; divide into nLR + nRL, l(nLR) = l(nRL) = L( ). The proposed method is more effective from minimum 17.79% to maxmimum 90.17% than the method that reduces using  information.

큰 반소수 n=pq의 소인수 p,q를 직접 찾는 것은 현실적으로 거의 불가능하여 대부분의 소인수분해 알고리 즘은 a2≡b2(mod n)의 제곱합동을 찾아 p=GCD(a-b, n), q=GCD(a+b, n)의 소인수를 찾는 간접 방법을 적용하고 있다. 제곱합동 a,b을 찾는 다양한 방법이 제안되었지만 100자리 이상인 RSA 수에 대해서는 적용이 쉽지 않다. 본 논문에서는 xa = ⌈  ⌉ or ⌈ ⌉+ z, z = 1, 2, ⋯ 로 설정하고 (xa)2 ≡ (yb)2 (mod n) 을 찾는 간단한 방법을 제안한 다. 제안된 알고리즘은 19 자리 수 까지는 제곱합동을 빠르게 찾는데 성공하였으나 39 자리 수에 대해서는 실패하였 다.

It is almost impossible to directly find the prime factor, p,q of a large semiprime, n=pq . So Most of the integer factorization algorithms uses a indirect method that find the prime factor of the p= GCD(a-b,n),q = GCD(a+b,n) after getting the congruence of squares of the a2 ≡ b2(mod n) . Many methods of getting the congruence of squares have proposed, but it is not easy to get with RSA number of greater than a 100-digit number. This paper proposes a fast algorithm to get the congruence of squares. The proposed algorithm succeeded in getting the congruence of squares to a 19-digit number.

n=pq인 합성수 n을 크기가 비슷한 p와 q로 소인수분해하는 것은 매우 어려운 문제이다. 대부분의 소인수분해 알고리즘은 a2=b2(mod n)인 제곱 합동이 되는 (a,b)를 소수의 곱 (인자 기준, factor base, B)으로 찾아 a2-b2=(a-b)(a+b) 공식에 의거 유클리드의 최대공약수 공식을 적용하여 p=GCD(a-b,n), q=GCD(a+b,n)으로 구한다. 여기서 (a,b)를 얼마나 빨리 찾는가에 알고리즘들의 차이가 있으며, B를 결정하는 어려움이 있다. 본 논문은 좀 더 효율적인 알고리즘을 제안한다. 제안된 알고리즘에서는 n+1을 3자리 소수까지 소인수분해하여 B를 추출하고 B의 조합 f를 결정한다. 다음으로, a=fxy가 되는 값을 범위에서 구하여 n-2의 소인수분해로 x를 얻고, y=fx/a, y1={1,3,7,9}을 구한다. 제안된 알고리즘을 몇 가지 사례에 적용한 결과 를 순차적으로 찾는 기존의 페르마 알고리즘에 비해 수행 속도를 현격히 단축시키는 효과를 얻었다.

It is very difficult to factorize composite number, to integer factorization, p and q that is almost similar length of digits. Integer factorization algorithms, for the most part, find (a,b) that is congruence of squares (a2=b2(mod n)) with using factoring(factor base, B) and get the result, p=GCD(a-b,n), q=GCD(a+b,n) with taking the greatest common divisor of Euclid based on the formula a2-b2=(a-b)(a+b). The efficiency of these algorithms hangs on finding a(a,b)nd deciding factor base, B. This paper proposes a efficient algorithm. The proposed algorithm extracts B from integer factorization with 3 digits prime numbers of n+1 and decides f, the combination of B. And then it obtains x(this is, a=fxy, ) from integer factorization of n-2 and gets y-fx/a. Our algorithm is much more effective in comparison with the conventional Fermat algorithm that sequentially finds .

인 합성수 을 와 로 소인수분해하는 것은 매우 어려운 문제이다. 대부분의 소인수분해 알고리즘은 인 제곱 합동이 되는 를 찾아 공식에 의거 유클리드의 최대공약수 공식을 적용하여 으로 구한다. 여기서 를 얼마나 빨리 찾는가에 알고리즘들의 차이가 있다. 제곱합동의 기초가 되는 페르마 알고리즘은 을 찾는다. 본 논문은 를 찾는 방법을 제안하였다. 제안된 방법에서 는 의 배수로 또는 가 반드시 한 개는 존재한다고 가정한다. 첫 번째로, 에 대해 와 을 만족하는 을 구하여 를 결정한다. 두 번째로, 이 되는 을 결정한다. 세 번째로, 범위에 속하는 의 범위를 결정하여 값들에 대해 으로 를 구한다. 제안된 알고리즘을 몇 가지 사례에 적용한 결과 페르마 알고리즘에 비해 수행 속도를 현격히 단축시키는 효과를 얻었다.

It is very difficult problem to factorize composite number. Integer factorization algorithms, for the most part, find that is congruence of squares () with using factoring(factor base, B) and get the result, with taking the greatest common divisor of Euclid based on the formula . The efficiency of these algorithms hangs on finding . Fermat's algorithm that is base of congruence of squares finds . This paper proposes the method to find . It is supposed or to be surely, and b is a double number. First, the proposed method decides by getting that satisfies and about . Second, it decides that satisfies . Third, it figures out from about as deciding that is in . The proposed algorithm is much more effective in comparison with the conventional Fermat algorithm.