본 논문은 비트코인 채굴에 필요한 SHA-256 암호 해시 값(n)을 구성하는 2개의 소수(p,q)를 빠르게 해독하는 소인수분해법을 다룬다. 본 논문에서는 Pollard's Rho 소인수분해 알고리즘의 수행횟수를 월등히 감소시킨 알고리즘을 제안하였다. Rho (${\rho}$) 알고리즘은 $(x_0,y_0)=(2,2)$ 초기치에 대해 $x_i=x^2_{i-1}+1(mod\;n)$과 $y_i=[(y^2_{i-1}+1)^2+1](mod\;n)$을 계산하여 1 < $gcd({\mid}x_i-y_i{\mid},n)$ < n으로 소인수를 구한다. 이 알고리즘은 특정 합성수에 대해서는 소인수 분해에 실패할 수 있다. 제안된 알고리즘은 Pollard Rho 알고리즘에 $(x_0,y_0)=(2^k,2^k)$와 ($2^k,2$), $2{\leq}k{\leq}10$을 적용하였다. 그 결과 모든 합성수에 대해 소인수분해를 할 수 있었으며, Pollard Rho 알고리즘의 수행횟수를 67.94% 감소시켰다.
본 논문은 비트코인 채굴에 필요한 SHA-256 암호 해시 값(n)을 구성하는 2개의 소수(p,q)를 빠르게 해독하는 소인수분해법을 다룬다. 본 논문에서는 Pollard's Rho 소인수분해 알고리즘의 수행횟수를 월등히 감소시킨 알고리즘을 제안하였다. Rho (${\rho}$) 알고리즘은 $(x_0,y_0)=(2,2)$ 초기치에 대해 $x_i=x^2_{i-1}+1(mod\;n)$과 $y_i=[(y^2_{i-1}+1)^2+1](mod\;n)$을 계산하여 1 < $gcd({\mid}x_i-y_i{\mid},n)$ < n으로 소인수를 구한다. 이 알고리즘은 특정 합성수에 대해서는 소인수 분해에 실패할 수 있다. 제안된 알고리즘은 Pollard Rho 알고리즘에 $(x_0,y_0)=(2^k,2^k)$와 ($2^k,2$), $2{\leq}k{\leq}10$을 적용하였다. 그 결과 모든 합성수에 대해 소인수분해를 할 수 있었으며, Pollard Rho 알고리즘의 수행횟수를 67.94% 감소시켰다.
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(${\rho}$) algorithm computes $x_i=x^2_{i-1}+...
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(${\rho}$) algorithm computes $x_i=x^2_{i-1}+1(mod\;n)$ and $y_i=[(y^2_{i-1}+1)^2+1](mod\;n)$ for intial values $(x_0,y_0)=(2,2)$ to find the factor 1 < $gcd({\mid}x_i-y_i{\mid},n)$ < n. It however fails to factorize some particular composite numbers. The algorithm proposed in this paper applies multiple initial values $(x_0,y_0)=(2^k,2^k)$ and ($2^k,2$), $2{\leq}k{\leq}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 67.94%.
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(${\rho}$) algorithm computes $x_i=x^2_{i-1}+1(mod\;n)$ and $y_i=[(y^2_{i-1}+1)^2+1](mod\;n)$ for intial values $(x_0,y_0)=(2,2)$ to find the factor 1 < $gcd({\mid}x_i-y_i{\mid},n)$ < n. It however fails to factorize some particular composite numbers. The algorithm proposed in this paper applies multiple initial values $(x_0,y_0)=(2^k,2^k)$ and ($2^k,2$), $2{\leq}k{\leq}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 67.94%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 Pollard의 Rho 알고리즘의 수행횟수를 약 68%감소시키면서 모든 합성수에 대해 소인수분해를 할 수 있는 알고리즘을 제안한다.
본 논문에서는 초기치를 다중으로 설정하여 Pollard Rho 알고리즘을 빠르게 수행하는 방법을 제안한다. 따라서 제안된 알고리즘은 Lee[8]의 알고리즘과는 차별성이 있으며, Pollard rho 알고리즘이 소인수 분해를 실패하는 반소수에 대해서도 소인수분해를 할 수 있는 장점을 갖고 있음을 보인다.
본 논문은 소인수분해에 탁월한 성능을 갖춘 Pollard의 Rho 알고리즘이 특정 합성수에 대해서는 소인수분해에 실패하는 문제점을 해결함과 더불어 수행횟수도 획기적으로 감소시킨 알고리즘을 제안하였다.
이러한 이유로 인해 비트코인 채굴시간을 보다 단축시키기 위해서는 암호를 해독하는 소인수분해 방법을 개선할 필요성이 대두되었다. 이러한 필요성에 의해 본 논문에서는 기존에 알려진 암호해독의 소인수분해법을 개선한 방법을 제안한다.
제안 방법
Pollard의 Rho 알고리즘은 초기치에 따라 알고리즘 수행횟수에 커다란 변화를 보여 다른 2가지 방식의 알고리즘도 추가로 실험을 수행하였다. 첫 번째는 x0를 n의 MSB에서 LSB로 1자리, 2자리, 순으로 선택하는 xLR = MSB →LSB로 선택하면서 Pollard의 Rho 알고리즘을 수행하는 방식이다.
본 장에서는 Pollard의 Rho 알고리즘과 제안된 다중-Pollard Rho 알고리즘의 성능을 비교분석하여 본다. 실험에는 l(p) = l(q) = 2,3,4 각 10개, l(p) = 2,l(q) = 3 10개, l(p) = 3, l(q) = 4 10개의 반소수 50개 데이터를 선택하였다.
제안된 알고리즘은 초기치를 (x0,y0) = (2,2) 대신 (2k,2k) 와 (2k,2), 2 ≤ k ≤10를 적용하여 Pollard의 Rho 알고리즘을 수행하는 방식이다.
대상 데이터
본 장에서는 Pollard의 Rho 알고리즘과 제안된 다중-Pollard Rho 알고리즘의 성능을 비교분석하여 본다. 실험에는 l(p) = l(q) = 2,3,4 각 10개, l(p) = 2,l(q) = 3 10개, l(p) = 3, l(q) = 4 10개의 반소수 50개 데이터를 선택하였다. 표 2의 Pollard의 Rho 알고리즘으로 소인수분해를 실패한 사례에 대해 제안된 알고리즘을 수행한 결과는 표 3에 제시되어 있다.
성능/효과
[7] Pollard의 Rho 알고리즘은 제곱합동법이나 나눗셈시행법에 비해 월등히 빠르게 소인수를 찾을 수 있지만 특정 합성수에 대해서는 찾지 못하는 단점이 있다.
또한, 이 방법은 n의 자리수가 커짐에 따라 초기치 개수가 따라서 증가하는 단점이 있다. 두 번째 방법은 Pollard의 Rho 알고리즘 수행횟수에 비해 20.04%만 수행하여 가장 좋은 성능을 보였다. 그러나 이 방법은 첫 번째 방법과 동일하게 초기치 개수가 증가 함과 더불어 최대공약수 계산 횟수도 많음을 알 수 있다.
그러나 이 방법은 첫 번째 방법과 동일하게 초기치 개수가 증가 함과 더불어 최대공약수 계산 횟수도 많음을 알 수 있다. 따라서 제안된 (2k,2k) 초기치 방법이 Pollard의 Rho 알고리즘의 단점을 해소할 수 있는 최선의 방법임을 알 수 있다.
본 논문에서는 초기치를 다중으로 설정하여 Pollard Rho 알고리즘을 빠르게 수행하는 방법을 제안한다. 따라서 제안된 알고리즘은 Lee[8]의 알고리즘과는 차별성이 있으며, Pollard rho 알고리즘이 소인수 분해를 실패하는 반소수에 대해서도 소인수분해를 할 수 있는 장점을 갖고 있음을 보인다.
제안된 알고리즘은 l(n) = 4의 반소수들 중에서 Pollard Rho 알고리즘으로 소인수분해에 실패한 15개 데이터들에 대해서도 4회 이내에 소인수분해를 할 수 있는 능력을 갖고 있을 뿐 아니라, 전반적으로 Pollard Rho 알고리즘의 수행횟수를 67.94% 감소시켰다.
첫 번째 방식의 알고리즘은 Pollard의 Rho 알고리즘에 비해 32.97%를 수행하여 제안된 (2k,2k) 초기치 방식보다 약간 성능이 떨어진다. 또한, 이 방법은 n의 자리수가 커짐에 따라 초기치 개수가 따라서 증가하는 단점이 있다.
표에서 n = 1943의 경우 c = 1인 Pollard Rho 알고리즘으로 소인수 분해에 실패하여 c = 2를 적용한 수행횟수를 표기하였다. 표 4에서 제안된 알고리즘을 수행한 결과 Pollard Rho 알고리즘의 수행횟수를 67.94% 감소시켰음을 알 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
본 연구에서 초기치를 다중으로 설정하여 Pollard Rho 알고리즘의 어떤 장점을 확인하려 하는가?
본 논문에서는 초기치를 다중으로 설정하여 Pollard Rho 알고리즘을 빠르게 수행하는 방법을 제안한다. 따라서 제안된 알고리즘은 Lee[8]의 알고리즘과는 차별성이 있으며, Pollard rho 알고리즘이 소인수 분해를 실패하는 반소수에 대해서도 소인수분해를 할 수 있는 장점을 갖고 있음을 보인다.
비트코인의 채굴과정과 비트코인은 무엇으로 구성되어 있는가?
요즘 인터넷을 활용한 전자화폐 채굴로 각광 받고 있는 비트코인(Bit coin) 채굴과정은 컴퓨터가 암호를 푸는 과정이라 할 수 있으며, 이는 간단한 암호원리와 SHA-256(256비트 이진수, 32 byte 16진수, RSA-2048)로 구성된 해시함수(hash function)로 이루어져 있다. RSA- 2048은 현재까지 소인수분해 값(두 개의 소수)이 알려져 있지 않다.
소인수분해 방법의 종류는 무엇이 있는가?
소인수분해 방법에는 나눗셈시행법 (Trial division), 제곱합동법 (Congruence of squares), Pollard's Rho, Quadratic Sieve (Q Sieve), General Number Field Sieve(GNFS) 등 다양하게 존재하고 있다.[3] 나눗셈 시행법은 O(#latex구현필요) 복잡도로 n/p, 3 ≤p < #latex구현필요, (p = odd) 으로 거의 사용하지 않는다.
참고문헌 (8)
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms, Section 31.7 The RSA Public-key Cryptosystem," 2nd Ed., MIT Press and McGraw-Hill. pp. 881-887, 2001. ISBN: 9780262533058
D. R. Stinson, "Cryptography: Theory and Practice," 3rd ed., London, CRC Press, 2005. ISBN: 97815848850852006
C. Barnes, "Integer Factorization Algorithms," Department of Physics, Oregon State University, 2004.
J. M. Pollard, "A Monte Carlo Method for Factorization," Bit Numerical Mathematics (BIT), Vol. 15, No. 3, pp. 331-334, Sep. 1975. doi:10.1007/BF01933667
K. Rosen, "Discrete Mathematics and It's Applications," 6th Ed., McGrew-Hill, 2011. ISBN-10: 0072899050
R. Montenegro, "Lecture Notes on Pollard's Rho", http://ravimontenegro.com/92.360/PollardRho.pdf, 2011.
R. P. Brent, "An Improved Monte Carlo Factorization Algorithm," Bit Numerical Mathematics (BIT), Vol. 20, No. 2, pp. 176-184, Jun. 1980. doi:10.1007/BF01933190
S. U. Lee, "Multiple Parallel-Pollard's Rho Discrete Logarithm Algorithm," Journal of The Korea Society of Computer and Information (KSCI), Vol. 20 No. 8, pp. 29-33, Aug. 2015. doi:10.9708/jksci.2015.20.8.029
※ AI-Helper는 부적절한 답변을 할 수 있습니다.