Question

If there are functional limit to the size of primes we can use, but how and why is there a functional limit? more detail on how primes are used in RSA.please type

Answer 1

● If you choose p and q very large, say each of 512 bits, then computer will not be able to factorize n=pq(which is of 1024 bit) in a limited suitable time. Thats why there is a functional limit.

● The algorithm for RSA as follows:

Person1's secret key generation:-

1. Choose two primes p and q

2. Compute n= pq and g= phi(n)= (p-1)(q-1)

3. Choose an integer 1<e<g which is coprime to g

4. By Euclid algo find 1<d<g such that ed≡1(mod g)

5. Make n and e public & keep p,q,d secret.

Person2's encryption:-

1. Get the public key (n,e)

2. Use the message M as an integer from the set {0,1,...,n-1}

3. Compute C≡M^e (mod n)

4. Send C to person1.

Decryption by person1:-

To decrypt the message he has to compute M≡C^d( mod n).

■ The fact that ensures the safety of RSA is- a large number is very difficult to factorize. Thats why inspite of knowing n adversory cannot be able to know p and q easily.