Digital signatures in Cybersecurity - Time & Space Complexity

Time Complexity: Digital signatures

O(n)

Understanding Time Complexity

We want to understand how the time needed to create or verify a digital signature changes as the size of the message or key grows.

How does the work increase when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following simplified digital signature verification process.

function verifySignature(message, signature, publicKey) {
  const hash = hashFunction(message); // hash the message
  const decryptedSignature = decryptWithPublicKey(signature, publicKey); // decrypt signature
  return hash === decryptedSignature; // compare hashes
}
    

This code checks if a digital signature is valid by hashing the message, decrypting the signature, and comparing the results.

Identify Repeating Operations

Look for loops or repeated steps inside the functions.

• Primary operation: The hashing function processes each part of the message once.
• How many times: It goes through the entire message data once, so the time depends on message length.

How Execution Grows With Input

The time to verify grows as the message gets longer because hashing reads the whole message.

Input Size (n)	Approx. Operations
10 bytes	About 10 steps to hash
100 bytes	About 100 steps to hash
1000 bytes	About 1000 steps to hash

Pattern observation: The work grows roughly in direct proportion to the message size.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify a digital signature grows linearly with the size of the message.

Common Mistake

[X] Wrong: "Verifying a digital signature takes the same time no matter how big the message is."

[OK] Correct: The hashing step must read the entire message, so bigger messages take more time to process.

Interview Connect

Understanding how digital signature verification time grows helps you explain security checks clearly and shows you grasp practical performance limits.

Self-Check

"What if the hashing algorithm was replaced with one that processes fixed-size chunks in parallel? How would the time complexity change?"