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

摘要

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 e-commerce. 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'=M~e (mod n). Bob can decrypt M' by computing M"=(M~e)~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.