---
title: "Public key cryptography and digital signature"
subject: "Operating System"
chapter: 8
key: "semester_6/operating_system:digital-signature-public-key"
source: https://www.bctengineer.com/q/semester_6/operating_system/digital-signature-public-key
site: BCT Engineering
---

# Public key cryptography and digital signature

Operating System · Chapter 8: Security

- Asked in: year not given
- Video: [What are Digital Signatures? - Computerphile](https://www.youtube.com/watch?v=s22eJ1eVLTU) — Computerphile
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/digital-signature-public-key
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-8

## Question

Explain public key cryptography and digital signature in detail.

## Short answer

Public-key cryptography uses key pairs: encrypt with public key, decrypt with private key (RSA: C=P^e mod n). Digital signatures sign a message hash with the sender's private key; the receiver verifies with the sender's public key, proving authenticity, integrity, and non-repudiation. Certificates bind public keys to identities.

## Answer

#### Public key cryptography
It uses two related keys: a public key (known to all) and a private key (secret). Data encrypted with one can be decrypted only with the other. RSA is the common algorithm: n = p·q, public key (e, n), private key (d, n); encryption C = Pᵉ mod n, decryption P = Cᵈ mod n, where e·d ≡ 1 mod (p−1)(q−1).

- **Confidentiality:** encrypt with the receiver's public key; only the receiver's private key can decrypt.
- **Advantages:** no secret key exchange is needed; supports signatures.
- **Disadvantages:** slow, so usually used only to exchange a symmetric session key.

```text
 Alice --[encrypt with Bob's public key]--> Bob
 Bob decrypts with his own private key
```

#### Digital signature
A **digital signature** is a value computed from a message using the sender's private key, proving **authenticity** (who sent it), **integrity** (not altered) and **non-repudiation** (the sender cannot deny it).

**Signing and verification using a hash**
1. Sender computes a message digest H = hash(M) (e.g. SHA-256).
2. Sender encrypts H with their **private key**: S = D_A(H). This is the signature.
3. Sender sends M together with S.
4. Receiver computes hash(M) again and decrypts S with the sender's **public key**: E_A(S).
5. If both values are equal the signature is valid.

```text
 M --hash--> H --sign (private key)--> S
 Send: M + S
 Receiver: hash(M) =? E_A(S)   -> valid / invalid
```

Using a hash makes signing fast, as only the short digest is encrypted. Public keys are bound to identities by **digital certificates** issued by a Certificate Authority (X.509). Uses: software signing, e-banking, e-governance, secure e-mail.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. With which key is the digest signed?
   A. Sender's public key
   B. Receiver's private key
   C. Sender's private key
   D. Receiver's public key
   Answer: C. Anyone can verify with the sender's public key. (Key point: Sign)

2. What does a digital signature provide?
   A. Only confidentiality
   B. Only speed
   C. Only availability
   D. Authenticity, integrity and non-repudiation
   Answer: D. Sender cannot deny it. (Key point: Properties)

3. How does the receiver verify?
   A. Recompute hash(M) and compare with S decrypted using sender's public key
   B. Decrypt M with own private key
   C. Compare M to S
   D. Re-encrypt M with own public key
   Answer: A. Equal values mean valid. (Key point: Verify)

4. Why sign a hash?
   A. To hide the message
   B. Only the short digest is encrypted, so it is fast
   C. To avoid keys
   D. To make the signature longer
   Answer: B. Certificates bind public keys to identities. (Key point: Why hash)

## Related in Operating System

- [Short note: public key cryptography](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apublic-key-cryptography-note) — Operating System, chapter 8

## Related in other subjects

- [What is public key cryptography](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Apublic-key-cryptography) — Computer Networks and Security, chapter 8
- [Short note: Digital signature](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Adigital-signature-note) — Computer Networks and Security, chapter 8
- [Public speaking and key strategies](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Apublic-speaking-strategies) — Communication English, chapter 4