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?"

Practice

1. What is the main purpose of a digital signature in online communication?

easy

A. To encrypt the entire message content

B. To prove who sent a message and that it was not changed

C. To speed up the internet connection

D. To store passwords securely

Solution

1. Step 1: Understand the role of digital signatures

   Digital signatures are used to verify the sender's identity and ensure the message has not been altered.

2. Step 2: Compare options with this role

   Only To prove who sent a message and that it was not changed correctly describes this purpose; others describe unrelated functions.

3. Final Answer:

   To prove who sent a message and that it was not changed -> Option B

4. Quick Check:

   Digital signature = sender identity + message integrity [OK]

Hint: Digital signatures confirm sender and message unchanged [OK]

Common Mistakes:

• Confusing digital signatures with encryption
• Thinking digital signatures speed up connections
• Believing digital signatures store passwords

2. Which of the following is the correct way to describe a digital certificate?

easy

A. A tool to speed up file downloads

B. A method to hide messages from hackers

C. A document that proves the identity of websites or people online

D. A software to delete viruses

Solution

1. Step 1: Define digital certificate

   A digital certificate is used to prove the identity of websites or people online, ensuring trust.

2. Step 2: Match options to this definition

   A document that proves the identity of websites or people online matches this definition exactly; others describe unrelated tools or functions.

3. Final Answer:

   A document that proves the identity of websites or people online -> Option C

4. Quick Check:

   Digital certificate = identity proof online [OK]

Hint: Certificates prove identity of websites or people [OK]

Common Mistakes:

• Thinking certificates speed up downloads
• Confusing certificates with encryption methods
• Believing certificates remove viruses

3. Consider this scenario: A user receives a message with a digital signature. What does verifying the signature confirm?

medium

A. The message was sent by the claimed sender and was not altered

B. The message is encrypted and unreadable

C. The message is from a trusted website

D. The message contains no viruses

Solution

1. Step 1: Understand digital signature verification

   Verifying a digital signature confirms the sender's identity and that the message was not changed.

2. Step 2: Analyze options

   The message was sent by the claimed sender and was not altered correctly states this; The message is from a trusted website relates to certificates, not signatures; A and B are unrelated.

3. Final Answer:

   The message was sent by the claimed sender and was not altered -> Option A

4. Quick Check:

   Verify signature = confirm sender + message integrity [OK]

Hint: Signature verification confirms sender and message unchanged [OK]

Common Mistakes:

• Confusing signature verification with encryption
• Assuming verification means virus check
• Mixing up certificates and signatures

4. A website's digital certificate is expired, but the user ignores the warning and proceeds. What is the main risk?

medium

A. The website will block the user

B. The website will load faster

C. The user's computer will automatically update the certificate

D. The website's identity cannot be trusted, risking data theft

Solution

1. Step 1: Understand expired certificate implications

   An expired certificate means the website's identity is not verified, so it may be unsafe.

2. Step 2: Identify the risk of ignoring warnings

   Ignoring the warning risks trusting a fake or unsafe site, which can lead to data theft.

3. Final Answer:

   The website's identity cannot be trusted, risking data theft -> Option D

4. Quick Check:

   Expired certificate = identity risk and data theft [OK]

Hint: Expired certificates mean identity can't be trusted [OK]

Common Mistakes:

• Thinking expired certificates speed up loading
• Assuming automatic updates fix expired certificates
• Believing the website will block users ignoring warnings

5. A company wants to ensure both the identity of its website and the integrity of messages sent to clients. Which combination should it use?

hard

A. Digital certificate for website identity and digital signature for message integrity

B. Digital signature for website identity and digital certificate for message integrity

C. Only digital certificates for both identity and integrity

D. Only digital signatures for both identity and integrity

Solution

1. Step 1: Identify roles of certificates and signatures

   Digital certificates prove website or user identity; digital signatures prove message integrity and sender.

2. Step 2: Match roles to company needs

   The company needs certificates to prove website identity and signatures to ensure message integrity.

3. Final Answer:

   Digital certificate for website identity and digital signature for message integrity -> Option A

4. Quick Check:

   Certificate = identity, Signature = integrity [OK]

Hint: Use certificate for identity, signature for message integrity [OK]

Common Mistakes:

• Swapping roles of certificates and signatures
• Thinking one alone covers both identity and integrity
• Confusing message encryption with identity proof