Lontar - Template LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 33 A Practical Analysis of the Fermat Factorization and Pollard Rho Method for Factoring Integers Aminudina1, Eko Budi Cahyonoa2 aDepartment of Informatic, University of Muhammadiyah Malang Tlogomas Street 246 Malang, Indonesia 1aminudin2008@umm.ac.id (Corresponding author) 2ekobudi@umm.ac.id Abstract The development of public-key cryptography generation using the factoring method is very important in practical cryptography applications. In cryptographic applications, the urgency of factoring is very risky because factoring can crack public and private keys, even though the strength in cryptographic algorithms is determined mainly by the key strength generated by the algorithm. However, solving the composite number to find the prime factors is still very rarely done. Therefore, this study will compare the Fermat factorization algorithm and Pollard rho by finding the key generator public key algorithm's prime factor value. Based on the series of test and analysis factoring integer algorithm using Fermat's Factorization and Pollards' Rho methods, it could be concluded that both methods could be used to factorize the public key which specifically aimed to identify the prime factors. During the public key factorizing process within 16 bytes – 64 bytes, Pollards' Rho's average duration was significantly faster than Fermat's Factorization. Keywords: Factorization, Fermat's Factorization, Pollard's Rho. 1. Introduction Information security is a major challenge in an era of information flood like today. The cryptology method can be one of the solutions used to secure this information [1]. Cryptology consists of two parts, namely cryptography and cryptanalysis. The main task of cryptography is to hide data using specific algorithms, while cryptanalyst is a method for investigating the security of a cryptographic system by finding weaknesses in codes, ciphers, protocols, or key management schemes.[2]. Usually, cryptanalysis refers to analyzing and solving the keys used to perform the encryption and decryption processes. Therefore, cryptanalysts are needed to test the robustness of the encryption algorithm. There are several mathematical approaches in testing the robustness of cryptographic algorithms, including discrete logarithms and factorization. In this study, the factorization method is used to break numbers into smaller numbers [3]. This factorization method is used for the RSA algorithm to generate public and private keys There are several methods that can be used to factor the composite number into prime numbers, namely Fermat's factorization and Pollard rho. Fermat factorization looks for the factor of an odd number by utilizing the property of an odd number which can be expressed as the difference of 2 squares from another number [4]. In contrast, the pollard rho method integrates a polynomial function in a modulo 𝑛 (the number to be factored) and a seed (generator number) [5]. The importance of the two algorithms is that if they can return two large prime factors of modulus processing, it can be ascertained that the public and private keys can be found [6]. Thus, this integer factorization problem has a significant impact on the security of the public-key cryptography system. The research conducted by Chinniah et al. created a factorization method that aims to find composite number factors resulting from two different prime numbers [7]. Then Li et al. researched the implementation of algorithms with a mathematical model used for factoring integers. The results of this study were a comparison between Pollard's Rho and SpSqAlgorithm based on execution time. [8]. This study aimed to analyze Fermat's Factorization and Pollards' Rho due to vulnerability by factorizing the prime factors. Furthermore, the purpose is to figure out the receiving the factorization attack by comparing the factorization time between both methods. mailto:1aminudin2008@umm.ac.id.com mailto:2ekobudi@umm.ac.id.com LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 34 The ultimate goal of the proposed research is to discover an opportunity to extend the previous study to contribute in the area of cryptanalysis and cryptography. 2. Research Methods 2.1. Fermat's Factorization The following section is the attack method as the technique of factorization. p and q can be easily found using Fermat's Factorization with the following steps [6]: a. π‘˜ = βˆšπ‘› (1) b. π‘˜2 > 𝑛 𝑒𝑙𝑠𝑒 𝑛 + +. (2) c. π‘˜2 βˆ’ 𝑛 = β„Ž2 that is, if (β„Ž == π‘ π‘žπ‘’π‘Žπ‘Ÿπ‘’). (3) d. 𝑝 = (π‘˜ + β„Ž) and π‘ž = (π‘˜ βˆ’ β„Ž) (4) The variable of π‘˜ on equation (1) is the value of square root n. The variable of π‘˜2 on equation (2) is the value of the perfect square. The variable of β„Ž2 on equation (4) is the ultimate value of the perfect square. The variable of 𝑝 and π‘ž on equation (5) is the sought prime. Figure 1 shows the pseudocode of Fermat's factorization. Input : value public key (n) Output: p and q for k from ceil (sqrt (n)) to n h square = k * k-n if p > 1 and p < n do h = sqrt (hSquared) p = k + h q = k – h Figure 1. Flowchart Fermat's Factorization Algorithm The input value of 𝑛 is used to get factorization from values 𝑝 and π‘ž. The 𝑛 value will be checked to include square root or not. After knowing π‘˜ is the square root, it is processed again whether π‘ž is greater than 𝑛. Subsequently, the calculations can be done if the value π‘˜ is greater than the value 𝑛. If it has a greater value, it proceeds by calculating the result of π‘˜ by performing square root. Conversely, the calculation is continued by adding 1 to the value π‘˜. After obtaining the square root value of 𝑛, we find 𝑝 and π‘ž values depicted in equation (8) to get the 𝑝 and π‘ž values. The flowchart of Fermat's Factorization is shown in Figure 2. Figure 2. Flowchart of Fermat's Factorization Algorithm LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 35 Figure 5 represents the factorization steps using Fermat's factorization method that have already been explained through a flow chart. 2.2. Pollard's Rho Pollard's Rho factorization method calculates the factorization 𝑛 with polynomial modulo 𝑛 iteration. This algorithm is based on several mathematical concepts, such as integer factorization[9]. The following procedure explains the steps of Pollard's Rho algorithm as a method of factorization [2]: a. Input a value that are going to be factorized value 𝑛 b. π‘Ž = 2, 𝑏 = 2. (5) c. π‘Ž = π‘Ž2 + 1 (π‘šπ‘œπ‘‘ 𝑛), 𝑏 = 𝑏2 + 1 (π‘šπ‘œπ‘‘ 𝑛) (6) d. 𝑝 = gcd(π‘Ž βˆ’ 𝑏, 𝑛). (7) e. 𝑝 β‰  1 and 𝑝 β‰  𝑛. (8) f. 1 < 𝑝 < 𝑛, π‘ž = 𝑛/𝑝 (9) The π‘Ž and 𝑏 variable on equation (5) is the first step of factorization. The a2 and b2 variable on equation (6) is the value that has been square root from the previous result. The 𝑝 variable on equation (7) is the prime produced by equation gcd (the greatest divisor), and the 𝑛 variable is the prime of the public key. The π‘ž variable on equation (8) is the prime generated from the division of variable 𝑛 and variable π‘ž. Figure 3 shows pseudocode pollard's Rho in detail. Input : value public key (n) Output: p and q values initialization a=2, b=2; while (true) a=(a2 + 1(mod n)) b=(b2 + 1(mod n)) count p = (a - b), gcd (n); print (p) ; loop (a,b); false if (p = n); if p > 1 and p < n than count q = (n/p); print (q); Figure 3. Pollard's Rho Algorithm The first step in the pollards' rho method gets the public key value 𝑛 to be factored into 𝑝 and π‘ž values. The next step is calculating the 𝑝 value, which must fulfill the equation 𝑝 > 1 π‘‘π‘Žπ‘› 𝑝 < 𝑛. If it does not fulfill the equation, it is recalculated from the beginning. If the 𝑝 value has been found, then the π‘ž value can be calculated. Figure 4. Flowchart of Pollard's Rho LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 36 Figure 7 represents the factorization steps using Pollard's Rho method that have already been explained through a flow chart. 2.3. Scenario of Testing The testing scenario was conducted by running the program and inserting the various number of public keys that have been generated and compiled using 𝑛 = 𝑝 < π‘ž < 2𝑝 which finally created the public key n. Then the generated key was factorized by using Fermat's Factorization and Pollard's Rho method for obtaining the p and q values and figuring out the duration of factorization. The public key pairs were created within a range from 16 to 64 bytes complying with the equation 𝑛 = 𝑝 < π‘ž < 2𝑝. 3. Result and Discussion To increase the security in public key so that it can be concluded afterward the characteristic of the strong public key that can withstand the attacks of factorization mainly by using the Fermat's Factorization and Pollard's Rho. The test results of Fermat's factorization method are presented in Table 1 and Table 2, while Pollard's Rho's test results are shown in Tables 3 and 4. The second column shows the public key 𝑛 factorized to obtain the value of 𝑝 and π‘ž. The following columns present the digit length of 𝑛, the found value of 𝑝 and π‘ž, duration of factorization, and success rate of key public factorization. 3.1. Testing Using Fermat's Factorization The experiment of Fermat's Factorization algorithm used the public key 𝑛 that was normally widely distributed. However, this test used the generated public key 𝑛 with the equation 𝑛 = 𝑝 < π‘ž < 2𝑝 to make it difficult to find the value of 𝑝 and π‘ž. Fermat's factorization was used to factorize the public key 𝑛 to find the value of 𝑝 and π‘ž. The test results are illustrated in Table 1 and Table 2 below: Table 1. Testing Result Fermat's Factorization on 16 Untuk 32 Bytes Key Generation No Public Key 𝒏 Length of Public Key 𝒏 𝒑 𝒒 Execution Time (ms) Succes s Rate (%) 1. 2916425411 10 /16 bytes 65357 44623 561 ms 100 % 2. 1175270081425 9 14 343051 7 3425927 2 ms 100 % 3. 1341849068550 433 16 393584 47 3409303 9 18497 ms / 18,497 d 100 % 4. 4172366223726 2923 17 209763 919 1989077 17 13207 ms / 13,207 d 100 % 5. 4325011719545 94013 18 779594 677 5547769 69 1640872 ms / 27,34786667 m 100 % 6. 8763301721976 902561 19 344668 3453 2542531 637 6688088 ms /1,857802222 jam 100 % 7. 4980853165476 5413631 20/ 32 bytes 707853 7649 7036556 719 6162 ms / 6,162 d 100 % In Table 1, Fermat's Factorization method succeeded in finding the value of 𝑝 and π‘ž. This showed the attack's susceptibility caused by Fermat's Factorization method, proven by a 100% success rate. The prime factors of public key 𝑛 were still easily obtained through the test. The test used Fermat's Factorization within 32-64 bytes key generation. LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 37 Table 2. Testing Result Fermat's Factorization on 32 Untuk 64 Bytes Key Generation N o. Public Key 𝒏 Length of Public Key of 𝒏 𝒑 𝒒 Execution Time (ms) Succes s Rate (%) 1. 2936653455160738453027 22 - - 469 m 4 s / 7,81667 h 0 % 2. 52891073208710727120157 23 - - 383 m 34 s / 6,38333 h 0 % 3. 147307994954025982922977 1 25 - - 385 m 40 s / 6,41667 h 0 % 4. 123693524037686594532150 77 26 - - 517 m / 8,61667 h 0 % 5. 268889892902937863375973 328747 30 - - 540 m 5 s / 9 h 0 % 6. 568396900241882051501949 76305169 32 - - 967 m 38 s / 16,1167 h 0 % 7. 205777995053692340932379 163614957396549 38/ 64 bytes - - 30357 s / 5,05 h 0% In Table 2, Fermat's factorization method did not find the value of p and q. This was considered secure from Fermat's Factorization attack, proven by a 0% success rate in which the prime factors of public key 𝑛 were not found. 3.2. Factorization Using Fermat's Factorization Fermat's factorization is used to identify the factors of public key 𝑛 (the value of 𝑝 and π‘ž) by factorizing the value of the public key. The test of Fermat's Factorization algorithm showed a 100% success rate in finding the value of 𝑝 and π‘ž at 16 – 32 bytes key generation, even though the key public generation has fulfilled the equation 𝑛 = 𝑝 < π‘ž < 2𝑝 used to complicate the identification of the prime factors through Fermat's Factorization. Meanwhile, the key generation on variant above 32 – 64 bytes showed a 0% success rate. 3.3. Testing Using Pollard's Rho The second test applied Pollards' Rho method to factorize the public key n to identify the prime factors' values on variant above 32 – 64 bytes. The duration of factorization was also investigated. The test results are presented in Table 3 and Table 4 below : Table 3. Testing Result Pollard's Rho on 16 Until 32 Bytes Key Generation No Public Key n Length of Public Key 𝒏 𝒑 𝒒 Executio n Time (ms) Success Rate (%) 1. 2916425411 10/16 bytes 44623 65357 8892 ms / 8,892 d 100 % 2. 1175270081425 9 14 3425927 3430517 7394 ms / 7,394 d 100 % 3. 1341849068550 433 16 3935844 7 3409303 9 9843 ms / 9,843 d 100 % 4. 4172366223726 2923 17 1989077 17 2097639 19 8564 ms / 8,564 d 100 % 5. 4325011719545 94013 18 5547769 69 7795946 77 5148 ms / 5,148 d 100 % 6. 8763301721976 902561 19 2542531 637 3446683 453 8440 ms / 8,44 d 100 % 7. 4980853165476 5413631 20/ 32 bytes 7078537 649 7036556 719 28704 ms / 28,704 100 % In Table 3, the Pollards' Rho method succeeded in solving the public key 𝑛 so that the prime factors ( 𝑝 and 𝑛 ) were still identifiable. This proved by the 100% of prime factors from the LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 38 established public key 𝑛 using a variant of 16 – 32 bytes. This happened since the method easily factorized the key. If a prime n is the product of two contiguous numbers (𝑝, π‘ž), then 𝑛 = 𝑝. π‘ž with 𝑝 β‰₯ 𝑝 > 0, 𝑝 π‘ž is not really big, and both of 𝑝 and π‘ž) are even, then 𝑝 and π‘ž are easily identified by Pollard's Rho method and eventually accelerate the factorization process. Table 4. Testing Result Pollard's Rho on 32 Until 64 Bytes Key Generation No. Public Key 𝒏 Public Key 𝒑 𝒒 Execution Time (ms) Success Rate (%) 1. 29366534551607384530 27 22 49865 64726 7 58891313 281 27737 ms / 27,737 d 100% 2. 14730799495402598292 29771 25 11043 88782 851 13338418 24921 108280 ms / 1,80466667 m 100% 3. 12369352403768659453 215077 26 34822 18272 409 35521473 48653 224082 ms / 3,7347 m 100% 4. 26888989290293786337 5973328747 30 53122 50579 49433 50616944 5283459 6003859 ms / 1,667738611 h 100% 5. 56839690024188205150 194976305169 32 80319 78041 99680 9 70766739 80804041 24835270 ms / 6,8986861111 h 100% 6. 20577799505369234093 2379163614957396549 38 - - 1,194 m 34 s / 19,9 h 0% In Table 4, the Pollards' Rho method was still able to solve the factors of public key 𝑛 on variants below 64 bytes. Meanwhile, the method could not identify the factors of key public 𝑛 on variant at above 64 bytes. It was proved by the 0% success rate indicating that the value of 𝑝 and π‘ž of the public key prime factors were not found. These test results proved that the success of public key generation fulfilling the equation 𝑛 = 𝑝 < π‘ž < 2𝑝 used above 64 bytes variant was still secured. 3.4. Analysis on Duration Comparison of Fermat's Factorization and Pollard's Rho The analysis on the comparison of public key n factorization duration during the attack using Fermat's Factorization and Pollard's Rho showed varieties of durations and key length. The two methods with the fastest rate in the factorizing public key under 64 bytes can be depicted from the results. The duration comparison using 16 – 64 bytes prime length parameter on each test is presented in Figure 8. Figure 8 shows that along with the public key's growth, the factorization process from both methods spending more time and resources. The highest point for the length of public-key n in Fermat's Factorization reached 32 digits, while the highest point in Pollards' Rho reached 38 digits. In terms of the factorizing the public key n within 16 – 64 bytes, Pollard's Rho generated faster duration (7129203,29 milliseconds or 118,82005483332 minutes or 1,980334247222 hours) than Fermat's Factorization (15871956,36 milliseconds or 264,532606 minutes or 4,4088767666667 hours. More information can be obtained if a higher specification is provided. LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 39 Figure 8. Comparison Duration on the Factorization 4. Conclusion Based on the series of test and analysis factoring integer algorithm using Fermat's Factorization and Pollards' Rho methods, it could be concluded that both methods could be used to factorize the public key which specifically aimed to identify the prime factors (p and q). During the public key n factorizing process within 16 bytes – 64 bytes, Pollards' Rho's average duration was significantly faster than Fermat's Factorization. Pollard's Rho performed factorization only in 7129203,29 milliseconds or 118,82005483332 minutes or 1,980334247222 hours, while Fermat's Factorization was accomplished in 15871956,36 milliseconds or 264,532606 minutes or 4 hours. References [1] A. Aminudin, A. F. Helmi, and S. Arifianto, β€œAnalisa Kombinasi Algoritma Merkle-Hellman Knapscak dan Logaritma Diskrit pada Aplikasi Chat,” Jurnal Teknologi Informasi dan Ilmu Komputer, vol. 5, no. 3, pp. 325–334, 2018. [2] P. P. Thwe, M. Htet, Y. C. City, and I. Technology, "Extended Pollard's Rho Factorization Algorithm For Finding Factors In Composite Number," Journal of Science, Engineering and Education, pp. 232–235, 2020. doi: 10.13140/RG.2.2.34889.16485 [3] A. Aminudin, G. P. Aditya, and S. Arifianto, "RSA algorithm using key generator ESRKGS to encrypt chat messages with TCP/IP protocol," Jurnal Teknologi dan Sistem Komputer, vol. 8, no. 2, pp. 113–120, 2020, doi: 10.14710/jtsiskom.8.2.2020.113-120. [4] K. Chiewchanchairat, P. Bumroongsri, and S. Kheawhom, "Improving Fermat factorization algorithm by dividing modulus into three forms," KKU Engineering Journal, vol. 40, no. March, pp. 131–138, 2016, doi: 10.14456/kkuenj.2016.127. [5] C. L. Duta, L. Gheorghe, and N. Tapus, "Framework for evaluation and comparison of integer factorization algorithms," Proceeding 2016 SAI Computing Conference, pp. 1047–1053, 2016, doi: 10.1109/SAI.2016.7556107. [6] K. Somsuk, "The new integer factorization algorithm based on Fermat's Factorization Algorithm and Euler's theorem," International Journal of Electrical and Computer Engineering, vol. 10, no. 2, pp. 1469–1476, 2020, doi: 10.11591/ijece.v10i2.pp1469-1476. [7] P. Chinniah and A. Ramalingam, "An Integer Factorization Method Equivalent to Fermat Factorization," International Journal of Mathematics And its Applications, vol. 6, no. 2, pp. 107–111, 2018. [8] J. LI, "Algorithm Design and Implementation for a Mathematical Model of Factoring Integers," IOSR Journal of Mathematics, vol. 13, no. 01, pp. 37–41, 2017, doi: 10.9790/5728- 0 10000000 20000000 30000000 40000000 50000000 60000000 70000000 80000000 1 0 b y te s 1 4 b y te s 1 6 b y te s 1 7 b y te s 1 8 b y te s 1 9 b y te s 2 0 b y te s 2 2 b y te s 2 3 b y te s 2 5 b y te s 2 6 b y te s 3 0 b y te s 3 2 d ig it s 3 8 d ig it s T im e ( m s ) Length of Public Key n Comparison of Algorithm Duration Fermat's Factorization Pollards' Rho LONTAR KOMPUTER VOL. 12, NO. 1 APRIL 2021 p-ISSN 2088-1541 DOI : 10.24843/LKJITI.2021.v12.i01.p04 e-ISSN 2541-5832 Accredited Sinta 2 by RISTEKDIKTI Decree No. 30/E/KPT/2018 40 1301063741. [9] S. Sarnaik, R. Bhakkad, and C. Desai, "Comparative study on Integer Factorization algorithm-Pollard's RHO and Pollard's P-1," in 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), 2015, pp. 677–679.