Asymmetric encryption (RSA) in Computer Networks - Time & Space Complexity

Time Complexity: Asymmetric encryption (RSA)

O(k)

Understanding Time Complexity

When using RSA encryption, it is important to understand how the time to encrypt or decrypt data changes as the size of the input grows.

We want to know how the number of steps needed grows when the message or key size increases.

Scenario Under Consideration

Analyze the time complexity of the RSA encryption process shown below.

function rsaEncrypt(message, publicKey) {
  let encrypted = 1n;
  let base = BigInt(message);
  let exponent = BigInt(publicKey.e);
  let modulus = BigInt(publicKey.n);

  while (exponent > 0n) {
    if (exponent % 2n === 1n) {
      encrypted = (encrypted * base) % modulus;
    }
    base = (base * base) % modulus;
    exponent = exponent / 2n;
  }
  return encrypted;
}
    

This code encrypts a message by repeatedly squaring and multiplying modulo a large number, using the public key exponent.

Identify Repeating Operations

Look at what repeats in the code:

• Primary operation: The while loop that does repeated squaring and multiplication.
• How many times: The loop runs roughly as many times as the number of bits in the exponent.

How Execution Grows With Input

The number of loop steps grows with the size of the exponent, which depends on the key size.

Input Size (bits in exponent)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps increase roughly in a logarithmic scale as the exponent size grows.

Final Time Complexity

Time Complexity: O(k)

This means the time to encrypt grows linearly with the number of bits in the key exponent.

Common Mistake

[X] Wrong: "RSA encryption time depends only on the message size."

[OK] Correct: The main factor is the key size (exponent length), not the message length, because the math works on big numbers related to the key.

Interview Connect

Understanding how RSA's encryption time grows helps you explain real-world security trade-offs clearly and confidently.

Self-Check

"What if we changed the exponent to a fixed small number? How would the time complexity change?"