Various steps in RSA(Crypto-system)

The whole mystery lies , you cant efficiently factor a large integer.

Steps for encryption:

Step-1: Choose two large distinct prime numbers p,q

Step-2: Compute n=p*q,product of two prime numbers.

Step-3: Compute Phi(n)=Phi(p)*Phi(q) here Phi(x) is euler toitent function . Phi(x) =number of coprimes less than x .

Step-4: Choose as integer 1<e<Phi(n) such that e and Phi(n) are co-primes

Step-5: Compute d that such that d*e = 1(mod Phi(n)) . That is d is modular multiplicative inverse of e mod (phi(n)) .

Step-6 . Public key is (n,e)

Step-7: Private key is d . Note- with knowledge of n ,one cant calculate Phi(n) or in turn d.

Step-8: Encryption function for text T is C=pow(T,e) mod (n) .

Steps for decryption :

Decrypt the message by applying
T=Pow(C,d) mod n .

Proof of every things :

Proof-1 : Efficient computation of d is possible .
Computation of ax=1 (mod m) is possible by extended euclidean algorithm in O(m^2 ) time .

1..We have to find x such that ax=1 mod (m)

2. Since ax=1(mod m) so ax-1=qm for some integer q. Rearranging ax-qm=1.

3.ax-qm=1 can be solved by euler's algorithm to find x and q. Discard the q and x is  modular multiplicative inverse.

 Proof -2 : Computation of euler toitent function phi(n)  is possible only if u know prime factor of n and finding prime factor of n is NP-hard .

Phi(n) = n*Pi((1-1/p))) for all p here p|n .