Digital signatures and certificates in Computer Networks - Time & Space Complexity

Time Complexity: Digital signatures and certificates

O(n)

Understanding Time Complexity

When verifying digital signatures and certificates, the time it takes depends on the size of the data and the cryptographic operations involved.

We want to understand how the verification time grows as the input data or certificate size increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified verification process.

function verifySignature(data, signature, publicKey) {
  hashedData = hashFunction(data);          // Step 1: Hash the data
  decryptedSignature = decrypt(signature, publicKey);  // Step 2: Decrypt signature
  return compare(hashedData, decryptedSignature);     // Step 3: Compare hashes
}
    

This code verifies a digital signature by hashing data, decrypting the signature, and comparing the results.

Identify Repeating Operations

Look at the main steps that repeat or take time depending on input size.

• Primary operation: Hashing the data (Step 1)
• How many times: Once per verification, but hashing processes every byte of data

Decrypting the signature and comparing hashes take fixed time based on key size, not data size.

How Execution Grows With Input

The time to hash data grows as the data size grows, since every byte is processed.

Input Size (n bytes)	Approx. Operations
10	10 hashing steps + fixed decrypt & compare
100	100 hashing steps + fixed decrypt & compare
1000	1000 hashing steps + fixed decrypt & compare

Pattern observation: The hashing time grows roughly in direct proportion to data size, while other steps stay constant.

Final Time Complexity

Time Complexity: O(n)

This means the verification time grows linearly with the size of the data being signed.

Common Mistake

[X] Wrong: "The verification time depends mostly on the size of the signature or certificate."

[OK] Correct: Signature and certificate sizes are usually fixed or small, so the main time cost comes from hashing the data, which grows with data size.

Interview Connect

Understanding how cryptographic verification scales helps you explain performance in security systems clearly and confidently.

Self-Check

"What if the data is already hashed before verification? How would the time complexity change?"