Transcription
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.org242A New Factorization Method to Factorize RSA Public KeyEncryptionB R Ambedkar1 and S S Bedi21Department of CS and IT, MJP Rohilkhand UniversityBareilly, Uttar Pradesh 243006, India2Department of CS and IT, MJP Rohilkhand UniversityBareilly, Uttar Pradesh 243006, IndiaAbstractThe security of public key encryption such as RSA scheme reliedon the integer factoring problem. The security of RSA algorithmis based on positive integer N, because each transmitting nodegenerates pair of keys such as public and private. Encryption anddecryption of any message depends on N. Where, N is theproduct of two prime numbers and pair of key generation isdependent on these prime numbers. The factorization of N is veryintricate. In this paper a New Factorization method is proposedto obtain the factor of positive integer N. The proposed workfocuses on factorization of all trivial and nontrivial integernumbers and requires fewer steps for factorization process ofRSA modulus N. The New Factorization method is based onPollard rho factorization method. Experimental results shownthat factorization speed is fast as compare existing methods.Keywords: Attacks, Pollard rho method, Public KeyCryptography, RSA Algorithm.1. IntroductionPublic key cryptography is one of the mathematicalapplications that are valuable in sending information viainsecure channel. RSA algorithm is a public keyencryption algorithm. RSA has become most popularcryptosystem in the world because of its simplicity.According to number theory, it is easy to finds two bigprime number, but the factorization of the product of twobig prime numbers is very difficult. The difficulty ofcomputing the roots N, where N is the product of two largeunknown primes, it is widely believed to be secure forlarge enough N. Since RSA can also be broken byfactoring N, the security of RSA is often based on theinteger factorization problem [1]. The integer factorizationproblem is a well-known topic of research within bothacademia and industry. It consists of finding the primefactors for any given large modulus. Currently, the bestfactoring algorithm is the general number field sieve orGNFS for short. On December 12, 2009 a small group ofscientists used the previously mentioned approach to factora RSA-768 bit modulus, that is, a composite number with232 decimal digits. Their achievement required more thantwo years of collaborative work and used many hundredsof computing machines. Hence, factoring large primes is alaborious and complex task [2]. A method for factoringalgorithm (specially designed) for semi primes based onnew mathematical ideas. Since this method is relativelysimple and scalable, it can be suitable for parallelprocessing [2]. A new algorithm which attacks the RSAscheme. But the main condition of this algorithm is that tobreak RSA modulus firstly we should have public key andmodulus N. On the basis of this public key (e, N) proposedalgorithm disclose the private key [3]. An attacker hasaccess to the public key e and N and the attacker wants theprivate key d. To get d, N needs to be factored (which willyield p and q, which can then be used to calculate d).Factoring n is the best known attack against RSA to date.(Attacking RSA by trying to deduce (p-1) (q-1) is no easierthan factoring N, and executing an exhaustive search forvalues of d is harder than factoring N.) Some of thealgorithms used for factoring are as follows [12]: Trialdivision oldest and least efficient Exponential runningtime. Try all the prime numbers less than sqrt (N).Quadratic Sieve (QS): The fastest algorithm for numberssmaller than 110 digits. Multiple Polynomial QuadraticSieve (MPQS): Faster version of QS. Double Large PrimeVariation of the MPQS Faster still. Number Field Sieve(NFS) Currently the fastest algorithm known for numberslarger than 110 digits. Was used to factor the ninth Fermatnumber. These algorithms [12] represent the state of the artin warfare against large composite numbers against RSA.We can identify many approaches to attacking RSAmathematically, factor N into two prime factors. A lot ofalgorithm has been proposed regarding factorization, thePollard rho algorithm [7], and the Pollard (p-1) algorithm
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.org[8], Brent's method [9], are probabilistic, and may notfinish, for small values of N, Trial division algorithm [12]and Fermat method can finish [11]. In this paper we areproposing New Factorization (NF) method which is basedon Pollard rho Factorization (PRF) method [7]. By usingNF method we can factorize quickly all integer number. Itis very suitable for factorization against RSA algorithms,because that have a product of two prime number, so thereis no more than two factors, NF method factorize allnumbers with minimum elapsed time shown in Fig. 1.MATLAB environment is used for various analyses.2. AttacksThe security of the RSA cryptosystem is not perfect. Anattacker can resort to different approaches to attack RSAalgorithm. Among them, Brute force, Mathematical attacks,Timing attacks and Chosen Cipher text attacks aredescribed in following:243determine d by calculating the time it takes to computeCd (mod N) for a given cipher text C [13].2.4 Factorization AttackThe security of RAS is based on the idea that the modulusis so large that is infeasible to factor it in reasonable time.Bob selects P and Q and calculate N P Q. Although N ispublic, P and Q are secret. If Eve can factor N and obtainP and Q, Eve then can calculate d e-1 mod φ(N) becausee is public. The private exponent d is the trapdoor that Eveuses to decrypt any encrypted message.The factorization attack is a extremely giant dispute forsecurity of RSA algorithm. Some existing factorizationalgorithms can be generating public and private key ofRSA algorithm, by factorization of modulus N. But theyare taking huge time for factorization of N, in case of Pand Q very large. We are focusing on factorization speedand proposing new factorization method to enhance thespeed of factorization. Related works for factorization ofmodulus N are following.2.1 Brute Force Attacks on RSABrute force attacks, involves trying all possible public andprivate keys. The attacker tries all possible combinations toguess the private key. RSA with short secret key is proveninsecure against brute force attack [13]. This attack can beeasily circumvented by choosing large key. However, thelarger key will make the encryption and decryption processlittle slow as it will require greater computations in keygeneration as well as in encryption/decryption algorithm.The key length used in the encryption determines thepractical feasibility of performing a brute-force attack,with longer keys exponentially more difficult to crack thanshorter ones. Brute-force attacks can be made less effectiveby obfuscating the data to be encoded, something thatmakes it more difficult for an attacker to recognize whenhe/she has cracked the code. One of the measures of thestrength of an encryption system is how long it wouldtheoretically take an attacker to mount a successful bruteforce attack against it.3. Related WorkThe RSA Factoring Challenge was started in March 1991by RSA Data Security to keep abreast of the state of the artin factoring. Since its inception, well over a thousandnumbers have been factored, with the factories returningvaluable information on the methods they used to completethe factorizations. The Factoring Challenge provides oneof the largest test-beds for factoring implementations andprovides one of the largest collections of factoring resultsfrom many different experts worldwide. In short, this vastpool of information gives us an excellent opportunity tocompare the effectiveness of different factoring techniquesas they are implemented and used in practice. Since thesecurity of the RSA public-key cryptosystem relies on theinability to factor large numbers of a special type, thecryptographic significance of these results is self-evident.Some factorization methods are explored in followingparagraphs:2.2 Mathematical Attacks on RSAMathematical attacks focus on attacking the underlyingstructure of RSA function. The first intuitive attack is theattempt to factor the modulus N. There are severalapproaches, all equivalent to in effect to factoring theproduct of two primes N. Our objective is to provide RSAattacks that decrypts message by factoring N.2.3 Timing AttackIn RSA, the attacker can exploit the timing variation of themodular exponentiation implementations and able toJ. Carlos et al [2] proposed a method for factoringalgorithm is: gcd [N, (k . Ň) ] and gcd [N, (k . Ň) – ]result in nontrivial factors of N for different values of where Ň is the reverse of N and k is a positive integerranging from one to infinity.Sattar J Aboud [3] was introducing a method that breakingthe RSA scheme based on the knowing public key (e, N).This method will work efficiently if the decryption key d issmall. It possible therefore, to factor the modulus N.
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.orgL. Scripcariu, M.D. Frunze [4] was commencing someweak points of RSA algorithm and proposed a method forsecure public key. The main concept of this paper is forencryption (e, N) change every time public key forencryption.In 1978, RSA developed a public key cryptosystem that isbased on the difficulty of integer factoring. The RSApublic key encryption scheme is the first example of aprovable secure public key encryption scheme againstchosen message chosen attacks [5].The RSA scheme is asfollows [6]:Key generation algorithm, to generate the keys entityA must do the following:1. Randomly and secretly select two large primenumbers p and q.2. Compute the N p*q.3. Compute (φ) phi (N) (p-1) (q-1).4. Select random integer e, 1 e N, where gcd (e, φ) 1.5. Compute the secret exponent d, 1 d phi, suchthate*d 1(mod (phi)).6. The public key is (N, e) and the private key is (N,d). Keep all the values d, p, q and phi secret.Public key encryption algorithm, entity A encrypt amessage m for entity B which entity decrypt.Encryption: Entity B should do the following:Obtain entity A’s public key (N,e), represent themessage M as an integer in the interval [0 .N-1].Compute C Me mod N.Send the encrypted message e toentity A.Decryption: To recover the message m from thecipher text c. Entity A do the following: Obtain the ciphertext c from entity B. Recover the message M Cd mod N.Fermat Factorization [11] was discovered bymathematician Pierre de Fermat in the 1600s. Fermatfactorization rewrites a composite number N as thedifference of squares as follows: N x2 – y2, this differenceof squares leads immediately to the factorization of N:N (x y)(x-y), Assume that s and t are nontrivial oddfactors of N such that st N and s t. We can find x andy such that s (x - y) and t (x y)Example 1:Let N 95{Product of any two prime numbers.}Decimal digits: 2 Bits: 7Let factors : P,QCompute X : 10Compute Y : 2.236 (is not integer number)(Go to step 4)244X : 11Y: 5.09 (is not integer number)(Go to step 4)X : 12Y: 7 (is an integer number)P: 5Q: 19EndExample 2:Let N 2320869986411928544793Decimal digits: 22 Bits: 73Let factors : P,QCompute X : 48175408524Compute Y : 219488.97 (is not integer number)(Go to step 4)X : X 1, ,X 17073029192103X: 17121204600627Y: 17121136822844 (is an integer number)P: 67777783Q: 34242341423471End4. Pollard Rho FactorizationPollard rho Factorization [7] method is a probabilisticmethod for factoring a composite number N by iterating apolynomial modulo N. The method was published by J.M.Pollard in 1975. Suppose we construct the sequence: X 0 2 mod N, X n 1 X2 n 1(mod N). This sequence willeventually become periodic. It can be shown that thelength of the cycle is less than or equal to N by a proof bycontradiction: assume that the length L of the cycle isgreater than N, however we have only N distinct xn valuesin our cycle of length L N, so there must exist two xnvalues are congruent, and these can be identified asthe .starting points. of a cycle with length less than or equalto N. Probabilistic arguments show that the expected timefor this sequence (mod N) to fall into a cycle and expectedlength of the cycle are both proportional to N , for almostall N [8]. Other initial values and iterative functions oftenhave similar behavior under iteration, but the function f(N) (X2 n 1) has been found to work well in practice forfactorization. Assume that s and t are nontrivial factors ofN such that st N and s t. Now suppose that we havefound nonnegative integers i, j with i j such that X i X j(mod s) but X i X j (mod N). Since s (X i – X j ), and s N, we have that s gcd (X i – X j, N). By assumption s 2,thus gcd (X i – X j, N) 2. By definition we know that gcd(X i – X j, N) N. However, we have that N (X i – X j ), andthus that gcd (X i – X j, N) N. So we have that N gcd (X i – X j,
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.orgN), gcd (X i – X j, N) 1, and gcd (X i – X j, N) N. Thereforegcd (X i – X j, N) is a nontrivial factor of N.Example 3:Consider the Pollard rho algorithm for N 21 7*3.The sequence of Xn values generated by the algorithm is:X 0 2, X 1 5, X 2 5, , for n 1,If n 1, X 2n - X n 0.The algorithm at each step for n 1,2, Compute gcd (X 2n – X n ,N) gcd (0, , 21) 21We are showing this example, the Pollard rho algorithm isa probabilistic, and may not finish, even for small values ofN.5. New Factorization MethodThe new factorization method (NF) based on Pollard rhomethod and square root of N. The NF method is focusingon Mathematical and Factorization Attacks on RSA.Shown in e.g. 3, the Pollard rho factorization method maynot finish small value of N. We are using RSA algorithmfor public key cryptography, it is asymmetric encryptiontechnique, by using this technique we cannot encrypt anddecrypt message by same key. The generation of publicand private key is dependent on the factorization of N. Byusing Pollard rho factorization method, we can’t factorizeall integer numbers N see e.g. 3. By using NF method wefactorize all integer numbers N. The NF method is aindependent of periodic sequence and probabilistic method.For factorization of all integer number, we are proposingto Pollard rho factorization method to modifying andremoving the concept of periodic sequence. NF method asfollows:1. Let any positive integer is N.2. Compute the square root of N.3. Take ceiling function of step two.4. Decrement by one in square of step three.5. Compute the greatest Common divisor of stepthree and step number one.6. If step five is grater than one.7. Step five is a factor of step one.8. Compute other factor of N divided by step seven.9. Otherwise increment the value of steps three byone and continues step three to eight, till step fouris grater than one.By using these steps we factorize any positive integer asfollows:Example 4:Let N 21S 5P gcd(24,21) 3 1Q 21/3 7P and Q is factor of N.Example5:245Let N 999962000357Decimal digits 12 Bits 40S 999981P gcd (999962000360, 999962000357) 1P gcd (999964000323, 999962000357) 999983 1Q 999962000357/999983 999979P and Q is a factor of N.6. Simulation and ResultsWe are factorized all trivial and nontrivial number shownin e.g. 4. The NF method is a appropriate and essential forfactorization of product of any two prime numbers becausethat have only two factors as shown in simulated result Fig.1, factors of 14 decimal digit by using NF method elapsedtime is 94ms shown in Fig. 1. That domino effectsimulated by MATLAB version 7.0 and Intel(R),Core(TM)2 Quad CPU 2.66GHz, 3.24 GB of RAM. Asper the results shows factorization becomes more rapidlyby NF method.Fig. 1 Factors of 80964686104403 by using NF method ( Elapsed timein sec. 0.094) simulation shows.The elapsed time for prime factorization shown in Fig. 2with respect digits and Fig. 3 with respect bits processelapsed times is awfully tiny as compare to existingmethod.
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.org24654.54.544Elapsed Time (in second) yElapsed time(in sec.) yElapsed time (in sec.) vs Digits in Prime Factors53.532.521.532.521.5110.50.50123456789 10 11Decimal Digits in Prime Factors x12132114Fig. 2 NF method(Elapsed time vs Decimal digits in prime factors)6543Decimal Digits in Prime Factorsx7Fig. 4 Pollard rho method (Elapsed time vs Decimal digits in primefactors)Table 1 shows a comparison of some factorization methodsvs NF method, The trial division, Fermat factorizationmethod and NF method always terminate, and upperbounds can be derived for the running times of thesealgorithms in terms of N, the number to be factored. ThePollard rho algorithm, Brent's method, and the Pollard p1algorithm are probabilistic, and may not finish, even forsmall values of N.Elapsed time in second vs Number bits of prime factors54.54Elapsed Time (in second) y3.53.532.5Table 1: Comparison of few factorization methods vs MPRF method21.51FactorizationMethodFor allnumbersTechnique usedTrialCan factorizeDivision basedFermatCan factorizeN x2-y2Pollard RhoCan’t factorizePeriodic sequencesPollard (p-1)Can’t factorize(ak! -1) mod nBrent'sCan‘t factorizeNFFactorizeX n 1 X n 2 2(modN) basedSquare root0.551015202530Number of bitsx35404550Fig. 3 NF method(Elapsed time vs Total number of Bits of prime factors)Shown in Fig. 4, a plot of time elapsed and number ofdigits for given number by using traditional existingPollard rho, the factorization of 7 digit decimal numberelapsed time is 0.5s.The shown in Fig. 5 comparison between existingalgorithms and NF method. The factorization of 7 digitdecimal number by NF method the elapsed time is 0.032s.NF method produced all factors of any integer number.The algorithm was executed using MATLAB tool.
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011ISSN (Online): 1694-0814www.IJCSI.orgEllapsed time (in sec.) vs Number ofdigits in prime factorsElapsed time (in sec.)1000Trial Division100FermatFactorization10Pollard rho method11234560.17N F method0.01Number of digitsFig. 5 Number of digits vs. Elapsed time in Prime Factors7. ConclusionsIn this paper New Factorization method is proposed forRSA modulus N factorization. During simulation, Pollardrho factorization method is found not suitable to factor alltrivial numbers as shown in example 3. Although NFmethod factorizes all the integer numbers as described inexample 4. The elapsed time with respect to decimal digitsin prime factors is found less as compared to consideredexisting methods. The speed to compute the prime factorsis also found more as compare to existing methods.Therefore the proposed method is relatively simple, fastand scalable as compare to existing methods.References[1] Hung-Min Sun, Mu-En Wu, Wei-Chi Ting, and M. JasonHinek, “Dual RSA and Its Security Analysis”, IEEETransactions on Information Theory, Vol. 53, No. 8, Aug.2007.[2] Joao Carlos Leandro da Silva, “Factoring Semi primes andPossible Implications”, IEEE in Israel, 26th Convention, pp.182-183, Nov. 2010.[3] Sattar J Aboud, “An efficient method for attack RSAscheme”, ICADIWT Second International Conference, pp587-591,4-6 Aug 2009.[4] L. Scripcariu, M.D. Frunza, "A New Character EncryptionAlgorithm", ICMCS 2005, pp. 83 - 86, Sept., 2005.[5] Hongwei Si et al, “An Improved RSA Signature Algorithmbased on Complex Numeric Operation Function”,International Conference on Challenges in Environmental247Science and Computer Engineering , vol. 2, pp. 397-400,2010.[6] B. Schneier, Applied cryptography, second edition, NY: JohnWiley & Sons, Inc., 1996.[7] J. Pollard, "Monte Carlo methods for index computation(mod p)",Math. Comp., Vol. 32, pp.918-924, 1978.[8] J. Pollard, "Theorems on factorization and primality testing",Proc. Cambridge Philos.Soc., Vol. 76, pp.521-528, 1974.[9] R. P. Brent, “An improved Monte Carlo factorizationalgorithm”, BIT 20 (1980), 176-184. MR 82a:10007, Zbl439.65001. rpb051.[10] R. Rivest, A. Shamir, L. Adleman, "A Method for ObtainingDigital for Signatures and Public-Key Cryptosystems",Communications of the ACM, vol. 21 (2), pp. 120-126,1978.[11] Bell, E. T., “The Prince of Amateurs: Fermat.” New York:Simon and Schuster, pp. 56-72, 1986.[12] Ms. Divya Bansal, Ajay Goel, “Interrelation Among RSASecurity, Strong Primes, and Factoring”[13] M. Wiener, “Cryptanalysis of short rsa secretexponents”,IEEE Transactions on Information Theory,160:553–558, March 1990.Bhagwant Ram Ambedkar received the B.Tech. Degree in Electronics Engineering fromInstitute of Engineering and Technology Lucknow,India in 2001 and M. Tech. with specialization inWireless Communication and Computing fromIndian Institute of Information Technology,Allahabad, India in 2004. Presently he is workingas Assistant Professor in Department of ComputerScience and Information Technology, MJPRohilkhand University Bareilly, Uttar Pradesh,India.Dr. Sarabjeet Singh Bedi received the M.E.degree in Computer Science and Engineering fromThapar Institute of Engineering and Technology,Punjab, India in 2002. He has received his Ph.D.from Indian Institute of Information Technologyand Management, Gwalior, India. He has teachingand research experience of 16 years. His researchinterest is Network Management and Security.Currently He is teaching at M.J.P. RohilkhnadUniversity, Bareilly, India. He is involved invarious academic and research activities. He ismember of selection, advisor, governing andtechnical committees of various Universities andTechnical Institution bodies. Dr. S. S. Bedireceived Institute Medal from TIET, Punjab, India,2002, Rastriya Shikshak Ratan Award fromAIBDA, New Delhi in 2002 and Best Paper awardat World Congress on Engineering at London,2008.
in factoring. Since its inception, well over a thousand numbers have been factored, with the factories returning valuable information on the methods they used to complete the factorizations. The Factoring Challenge provides one of the largest testbeds for factoring implementations and - provides one of the
