Research Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Bi-Quadratic Analysis of Pollard’s Rho Method of Integer Factorization in Context of Cryptography


Affiliations
1 Department of Mathematics Govt P.G. College Kullu Distt. Kullu (H. P) Pin -175101, India
2 Department of Mathematics & Statistics, H.P. University, Shimla -171005, India
     

   Subscribe/Renew Journal


Cryptography is an important building block of e-commerce systems. In particular, public key cryptography can be used for ensuring the confidentiality, authenticity, and integrity of information in an organization. To protect the sensitive information in an organization, encryption can be applied to conceal sensitive data so that the encrypted data is completely meaningless except to the authorized individuals with the correct decryption key. To preserve the authenticity and integrity of data, digital signature can be performed on the data such that other people can neither impersonate the correct signer nor modify the signed data without being detected.RSA is one of the most popular public key cryptographic algorithms in used in ecommerce. Suppose Alice wants to send an encrypted message to Bob. Let the public key of Bob be and the private key of Bob be where n is the product of two prime numbers p and q (with ed=1 (mod (p-1)(q-1)). In this scenario, is accessible to anyone (e.g. Alice) who wants to send encrypted messages to Bob while d is kept secretly by Bob.To encrypt a message M for Bob, Alice has to compute M=Me (mod n). Bob can decrypt M by computing M=(Me)d=M (mod n). No one except Bob can decrypt M since d is only known to Bob. To calculate d from e, it is required to factor n to get p and q. With p and q, it is possible to calculate (p-1)(q-1). By reversing the key generation procedure, d can be calculated by computing e-1(mod (p-1)(q-1)). The security of RSA depends on the difficulty in factoring n into p and q if n is sufficiently large. Therefore, the size of n should be chosen such that the time and cost for performing the factorization exceeds the value of the encrypted information. If we are able to factor any number in to product of two primes then this show that the system is not secure. And if we are not able to factor the number in product of two prime then this show that system is secure. Our’s objective to show that how to make any type of system insecure by Pollard’s Rho algorithm with respect to various type of algorithms & analysis of Pollards Rho algorithm
Subscription Login to verify subscription
User
Notifications
Font Size


  • Factorization of 512-bit RSA key using the general number field sieve.

  • Arjen K. Lenstra , Integer Factoring, Designs, Codes and Cryptography, 19(2000), 101–128.

  • Quadratic Sieve Factoring Algorithm.

  • Factoring—From MathWorld.

  • Finding the Prime Factors of a Number.

  • Mathew E. Briggs, An introduction to the General Number Field Sieve, a master thesis submitted to the Faculty of the Virginia Polytechnic Institute and State University.

  • Neal Koblitz, A course in number theory and Cryptography, Second Edition, Springer, 1994.

  • Hans Riesel, Prime numbers and computer methods for factorization, Second Edition, Birkhauser, 1994..

  • Richard A. Mollin, Fundamental Number theory with applications, CRC Press, 1997.

  • Song Y. Yan, Number Theory for Computing, Second edition, Springer, 2000.


Abstract Views: 767

PDF Views: 0




  • Bi-Quadratic Analysis of Pollard’s Rho Method of Integer Factorization in Context of Cryptography

Abstract Views: 767  |  PDF Views: 0

Authors

Satish Kumar
Department of Mathematics Govt P.G. College Kullu Distt. Kullu (H. P) Pin -175101, India
P.L. Sharma
Department of Mathematics & Statistics, H.P. University, Shimla -171005, India

Abstract


Cryptography is an important building block of e-commerce systems. In particular, public key cryptography can be used for ensuring the confidentiality, authenticity, and integrity of information in an organization. To protect the sensitive information in an organization, encryption can be applied to conceal sensitive data so that the encrypted data is completely meaningless except to the authorized individuals with the correct decryption key. To preserve the authenticity and integrity of data, digital signature can be performed on the data such that other people can neither impersonate the correct signer nor modify the signed data without being detected.RSA is one of the most popular public key cryptographic algorithms in used in ecommerce. Suppose Alice wants to send an encrypted message to Bob. Let the public key of Bob be and the private key of Bob be where n is the product of two prime numbers p and q (with ed=1 (mod (p-1)(q-1)). In this scenario, is accessible to anyone (e.g. Alice) who wants to send encrypted messages to Bob while d is kept secretly by Bob.To encrypt a message M for Bob, Alice has to compute M=Me (mod n). Bob can decrypt M by computing M=(Me)d=M (mod n). No one except Bob can decrypt M since d is only known to Bob. To calculate d from e, it is required to factor n to get p and q. With p and q, it is possible to calculate (p-1)(q-1). By reversing the key generation procedure, d can be calculated by computing e-1(mod (p-1)(q-1)). The security of RSA depends on the difficulty in factoring n into p and q if n is sufficiently large. Therefore, the size of n should be chosen such that the time and cost for performing the factorization exceeds the value of the encrypted information. If we are able to factor any number in to product of two primes then this show that the system is not secure. And if we are not able to factor the number in product of two prime then this show that system is secure. Our’s objective to show that how to make any type of system insecure by Pollard’s Rho algorithm with respect to various type of algorithms & analysis of Pollards Rho algorithm

References