Most effective algorithms for each step of the basic RSA-Algorithm

Question

I can't seem to find a detailed complexity/runtime analysis of the basic RSA-algorithm from Volker Heun's Book "Fundamentale Algorithmen" on page 275 or any other books which describe it similarly:

1. Choose two large primes $p\neq q$ (We can use random number generators with the help of primality tests)
2. Compute $n=pq$ and $\varphi = (p-1)(q-1)$
3. Chose $e\in\mathbb{N}$ so that $\texttt{gcd}(e,\varphi(n))=1$ and $1< e <\varphi (n)$
4. Compute $d=e^{-1} \bmod \varphi(n)$ (Ext. Euclidean Algorithm)
5. Make $(e,n)$ public and keep $(d,p,q)$ secret. (prob. not a real step/operation)
6. Encryption of message $N$ with $M:=N^e \bmod n$ (Square-And-Multiply?)
7. Decryption of message $M$ with $M^d \bmod n$ (Square-And-Mulitply?)

Edit3: Can you tell me the fastest algorithm for each step in terms of the computational complexity given in Big-O-Notation for the number of bit-operations?

(Ignore the bounty-message, I know that my first question was unrealistic because you'll will need to find and analyse every single algorithm in order to make an assumption about the whole RSA-Algorithm's complexity. That's why I changed it to an easier one. I will award whoever can provide the fastest known algorithms for each step with its current complexity given in Big-O-Notation corresponding to the number of bit-operations. If the source does contain evidence only for arithmetic operations I'm fine with that too.)

Thank you in advance!

Answer 1

I'll try to address your steps. Let $N=pq,$ have bitlength $n$.

1. Choose two large primes $p\neq q$ (We can use random number generators with the help of primality tests)

You want to choose large pseudoprimes which are not too close together say within 10 bits of each other in bitlength. You can pick a random odd integer with bitlength $n/2$ in $O(n)$ steps and if you test roughly $\log N=n,$ such numbers you will hit a prime.

These steps have overall complexity $O(n^2)=O(\log^2 N).$ But there is the primality testing, which has complexity something like $O(\log^3 N)$ for Miller-Rabin, say.

Step 1 ends up taking $O(k \log^4 N),$ since we repeat Miller-Rabin $\log N$ times and do $k$ iterations for lowering the probability of error to $1-2^{-2k}.$

2. Compute $N=pq$ and $\varphi = (p-1)(q-1)$

$O((\frac{n}{2})^{1.58})=O(n^{1.58})=O(\log^{1.58}N)$ by Karatsuba algorithm. The Harvey-Hoegen algorithm seems to be not practical, as in the comment by Peter Kosinar.

3. Chose $e\in\mathbb{N}$ so that $\texttt{gcd}(e,\varphi(n))=1$ and $1< e <\varphi (N)$

Choose $e$ randomly (complexity $O(\log N)$) and check GCD. Success after a constant number of trials. Since you use extended Euclidean, complexity is $O(\log N).$

4. Compute $d=e^{-1} \bmod \varphi(N)$ (Ext. Euclidean Algorithm)

You can use CRT and then extended Euclidean mod $p-1$ and mod $q-1$ to get $e^{-1} \bmod{p-1}$ and $e^{-1} \bmod{q-1}$ and then multiply. This is a real saving in practice but still $O(\log N).$

5. Make $(e,n)$ public and keep $(d,p,q)$ secret. (prob. not a real step/operation)

Constant complexity.

6. Encryption of message $M$ with $C:=M^e \bmod N$ (Square-And-Multiply?)

Yes, but now without the factorisation of $N$ available to the sender. So $O(\log N)$.

7. Decryption of ciphertext $C$ with $C^d \bmod N$ (Square-And-Multiply?)

Yes, but with the factorisation available to recipient via CRT. Again $O(\log N).$