Public key cryptography and digital signature

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.

 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.

 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.