Key-based authentication in Linux CLI - Time & Space Complexity

Time Complexity: Key-based authentication

O(n)

Understanding Time Complexity

We want to understand how the time needed to connect using key-based authentication changes as we try to connect to more servers.

How does the process time grow when the number of servers increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for server in $server_list; do
  ssh -i ~/.ssh/id_rsa user@${server} "uptime"
done

This script connects to each server in a list using key-based authentication and runs a simple command.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The ssh connection command inside the loop.
• How many times: Once for each server in the list.

How Execution Grows With Input

Each additional server adds one more ssh connection and command execution.

Input Size (n)	Approx. Operations
10	10 ssh connections and commands
100	100 ssh connections and commands
1000	1000 ssh connections and commands

Pattern observation: The total time grows directly with the number of servers.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete all connections grows in a straight line as you add more servers.

Common Mistake

[X] Wrong: "Connecting to multiple servers at once will take the same time as connecting to one."

[OK] Correct: Each connection takes its own time, so more servers mean more total time.

Interview Connect

Understanding how connection time grows helps you plan scripts that manage many servers efficiently and shows you think about scaling real tasks.

Self-Check

"What if we run ssh connections in parallel instead of one after another? How would the time complexity change?"

Practice

1. What is the main purpose of key-based authentication in SSH?

easy

A. To encrypt files on the local computer

B. To allow secure login without typing a password every time

C. To speed up the internet connection

D. To create a backup of the server data

Solution

1. Step 1: Understand key-based authentication

   Key-based authentication uses a pair of keys to allow login without passwords.

2. Step 2: Identify the main benefit

   This method lets users connect securely without typing passwords each time.

3. Final Answer:

   To allow secure login without typing a password every time -> Option B

4. Quick Check:

   Key-based authentication = passwordless secure login [OK]

Hint: Key-based auth means no password typing needed [OK]

Common Mistakes:

• Confusing key-based auth with file encryption
• Thinking it speeds up internet
• Believing it backs up data

2. Which command correctly generates a new SSH key pair?

easy

A. ssh-keygen

B. ssh-copy-id

C. ssh-add

D. ssh-connect

Solution

1. Step 1: Identify the key generation command

   The command ssh-keygen creates a new SSH key pair.

2. Step 2: Differentiate from other commands

   ssh-copy-id copies keys, ssh-add adds keys to agent, ssh-connect is invalid.

3. Final Answer:

   ssh-keygen -> Option A

4. Quick Check:

   Generate keys = ssh-keygen [OK]

Hint: ssh-keygen always creates keys [OK]

Common Mistakes:

• Using ssh-copy-id to generate keys
• Confusing ssh-add with key creation
• Typing a non-existent ssh-connect command

3. What will happen if you run ssh-copy-id user@server after generating your SSH keys?

medium

A. The SSH service on the server restarts

B. Your private key is copied to the server

C. The server's keys are copied to your local machine

D. Your public key is copied to the server for passwordless login

Solution

1. Step 1: Understand ssh-copy-id purpose

   This command copies your public key to the server's authorized keys file.

2. Step 2: Identify what is copied

   Only the public key is copied, enabling passwordless login; private keys stay local.

3. Final Answer:

   Your public key is copied to the server for passwordless login -> Option D

4. Quick Check:

   ssh-copy-id copies public key to server [OK]

Hint: ssh-copy-id copies public key, not private [OK]

Common Mistakes:

• Thinking private key is copied
• Believing server keys copy locally
• Assuming ssh-copy-id restarts SSH

4. You tried to connect with SSH key authentication but still get a password prompt. Which is the most likely cause?

medium

A. The public key was not copied to the server

B. The private key file is missing on the server

C. The SSH server is turned off

D. The username is incorrect

Solution

1. Step 1: Check key placement

   If the public key is not on the server, SSH cannot authenticate without a password.

2. Step 2: Understand private key location

   The private key stays on the client, so missing it on the server is irrelevant.

3. Final Answer:

   The public key was not copied to the server -> Option A

4. Quick Check:

   Missing public key on server = password prompt [OK]

Hint: Public key must be on server for key login [OK]

Common Mistakes:

• Looking for private key on server
• Assuming SSH server off causes password prompt
• Blaming wrong username without checking keys

5. You want to automate SSH login to multiple servers without passwords. Which sequence of commands is correct?

hard

A. ssh user@server -> ssh-copy-id user@server -> ssh-keygen

B. ssh-copy-id user@server -> ssh-keygen -> ssh user@server

C. ssh-keygen -> ssh-copy-id user@server -> ssh user@server

D. ssh user@server -> ssh-keygen -> ssh-copy-id user@server

Solution

1. Step 1: Generate SSH keys first

   Use ssh-keygen to create your key pair locally.

2. Step 2: Copy public key to server

   Use ssh-copy-id user@server to add your public key to the server.

3. Step 3: Connect without password

   Now ssh user@server logs in using the key without asking for a password.

4. Final Answer:

   ssh-keygen -> ssh-copy-id user@server -> ssh user@server -> Option C

5. Quick Check:

   Generate keys, copy key, then connect [OK]

Hint: Generate keys first, then copy, then connect [OK]

Common Mistakes:

• Copying keys before generating them
• Trying to connect before copying keys
• Mixing command order