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

Practice

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

easy

A. To encrypt the entire message content for privacy

B. To speed up the transmission of data over the internet

C. To create a backup of the message on a secure server

D. To verify the sender's identity and ensure the message was not altered

Solution

1. Step 1: Understand the role of digital signatures

   Digital signatures are used to confirm who sent a message and that it has not been changed.

2. Step 2: Differentiate from encryption and other functions

   Encryption protects privacy, but digital signatures focus on authenticity and integrity.

3. Final Answer:

   To verify the sender's identity and ensure the message was not altered -> Option D

4. Quick Check:

   Digital signature = sender identity + message integrity [OK]

Hint: Digital signatures prove identity and message unchanged [OK]

Common Mistakes:

• Confusing digital signatures with encryption
• Thinking digital signatures speed up data transfer
• Believing digital signatures create message backups

2. Which of the following correctly describes the process of creating a digital signature?

easy

A. Hash the message, then encrypt the hash with the sender's private key

B. Encrypt the entire message with the sender's public key

C. Hash the message and send the hash without encryption

D. Encrypt the message with the receiver's private key

Solution

1. Step 1: Identify the digital signature creation steps

   The message is hashed to create a fixed-size summary, then this hash is encrypted with the sender's private key.

2. Step 2: Eliminate incorrect options

   Encrypting the entire message or using the receiver's private key is incorrect for digital signatures.

3. Final Answer:

   Hash the message, then encrypt the hash with the sender's private key -> Option A

4. Quick Check:

   Digital signature = hash + sender's private key encryption [OK]

Hint: Hash first, then encrypt with private key for signature [OK]

Common Mistakes:

• Encrypting the whole message instead of the hash
• Using the receiver's key instead of sender's private key
• Skipping encryption of the hash

3. Consider this simplified Python code for verifying a digital signature:

def verify_signature(message, signature, public_key):
    hashed = hash_function(message)
    decrypted_hash = decrypt(signature, public_key)
    return hashed == decrypted_hash

message = "Hello"
signature = encrypt(hash_function(message), private_key)
result = verify_signature(message, signature, public_key)
print(result)

What will be the output of this code?

medium

A. RuntimeError

B. False

C. True

D. SyntaxError

Solution

1. Step 1: Understand the verification process

   The signature is decrypted with the public key to get the original hash. The message is hashed again and compared.

2. Step 2: Check if hashes match

   Since the signature was created by encrypting the hash with the private key, decrypting with the public key returns the same hash, so the comparison is True.

3. Final Answer:

   True -> Option C

4. Quick Check:

   Verification returns True if hashes match [OK]

Hint: Decrypted signature hash matches message hash means True [OK]

Common Mistakes:

• Confusing encryption and decryption keys
• Assuming the output is False without checking hash equality
• Expecting syntax or runtime errors from correct code

4. A developer wrote this code snippet to create a digital signature:

def create_signature(message, private_key):
    encrypted_message = encrypt(message, private_key)
    return encrypted_message

What is the main problem with this approach?

medium

A. Using the private key instead of the public key for encryption

B. Encrypting the whole message instead of hashing it first

C. Not decrypting the message before signing

D. Hashing the message twice before encryption

Solution

1. Step 1: Identify correct digital signature steps

   Digital signatures require hashing the message first, then encrypting the hash with the private key.

2. Step 2: Analyze the code's mistake

   The code encrypts the entire message directly, which is inefficient and incorrect for digital signatures.

3. Final Answer:

   Encrypting the whole message instead of hashing it first -> Option B

4. Quick Check:

   Signature = encrypt(hash(message)) not encrypt(message) [OK]

Hint: Sign hash, not whole message, to create digital signature [OK]

Common Mistakes:

• Thinking encrypting whole message is correct for signature
• Confusing private and public key roles
• Ignoring the need to hash before encryption

5. A company wants to ensure that their legal documents are authentic and unchanged after signing digitally. Which combination of technologies should they use to achieve this?

hard

A. Hashing the document and encrypting the hash with the sender's private key

B. Encrypting the entire document with the sender's public key

C. Hashing the document and sending the hash without encryption

D. Encrypting the document with the receiver's private key

Solution

1. Step 1: Understand the goal of authenticity and integrity

   The document must be proven to come from the sender and remain unchanged.

2. Step 2: Apply digital signature method

   Hashing the document creates a unique summary, and encrypting this hash with the sender's private key creates a digital signature.

3. Step 3: Eliminate incorrect options

   Encrypting the whole document or using the receiver's private key does not provide signature authenticity.

4. Final Answer:

   Hashing the document and encrypting the hash with the sender's private key -> Option A

5. Quick Check:

   Digital signature = hash + sender's private key encryption [OK]

Hint: Sign hash with private key for legal document authenticity [OK]

Common Mistakes:

• Encrypting whole document instead of signing hash
• Using receiver's key for signing
• Sending hash without encryption