Public key, hash, MAC, signature, PKI and TLS

The previous page left the big problem of symmetric encryption: how do we share the key? This page gives the answer and puts together all the parts that make up a secure Internet connection. The exam almost certainly has an RSA or Diffie-Hellman calculation; also “which key is used?” and “which mechanism provides what?” questions. Golden rules:

1. For confidentiality the receiver’s public key, for a signature the sender’s private key.
2. When doing modular exponentiation, take the mod after every multiplication. The numbers stay small.
3. In RSA, $e$ must be coprime to $\varphi(n)$. Otherwise $d$ does not exist.
4. A hash is keyless, a MAC uses a shared key, a signature uses a private key. Only the signature gives non-repudiation.
5. You verify a certificate with the public key of whoever signed it.

Public-key cryptography

In a public-key (asymmetric) system everyone has a key pair: the public key is distributed to everyone, and the private key stays with the owner. What is done with one can be undone only by the other. Security rests on mathematical problems that are easy in one direction but very hard in the reverse: factoring a large number (RSA) and the discrete logarithm (Diffie-Hellman).

Asymmetric operations are hundreds of times slower than symmetric ones. That is why hybrid use is the practice: the public key is used to establish a session key or to sign, and the data is encrypted with AES.

RSA

Key generation:

1. Choose two primes: $p$, $q$.
2. $n = pq$ and $\varphi(n) = (p-1)(q-1)$.
3. Choose an $e$ with $\gcd(e, \varphi(n)) = 1$.
4. $d = e^{-1} \bmod \varphi(n)$, that is $ed \equiv 1 \pmod{\varphi(n)}$.
5. Public key $(e, n)$, private key $(d, n)$.

Encryption is $c = m^e \bmod n$, decryption is $m = c^d \bmod n$ ($m < n$).

Worked example. $p = 13$, $q = 17$.

n    = 13 × 17 = 221
φ(n) = 12 × 16 = 192
e    = 3 won't do (3 divides 192); choose e = 5 (gcd(5,192) = 1)
d    : 192 = 38·5 + 2,  5 = 2·2 + 1
       1 = 5 − 2·2 = 5 − 2·(192 − 38·5) = 77·5 − 2·192
       d = 77     check: 5 × 77 = 385 = 2·192 + 1

Encrypt $m = 42$: $c = 42^5 \bmod 221$, step by step:

42^1 = 42
42^2 = 1764 mod 221 = 217
42^3 = 217·42 = 9114 mod 221 = 53
42^4 = 53·42  = 2226 mod 221 = 16
42^5 = 16·42  = 672  mod 221 = 9      → c = 9

Decrypt $9^{77} \bmod 221$. Instead of doing 77 multiplications, use square-and-multiply: $77 = 64 + 8 + 4 + 1$.

9^1  = 9         9^2  = 81        9^4  = 81^2 mod 221 = 152
9^8  = 152^2 mod 221 = 120        9^16 = 35     9^32 = 120    9^64 = 35
9^77 = 9^1 · 9^4 · 9^8 · 9^64
     = 9 · 152 = 1368 mod 221 = 42
       42 · 120 = 5040 mod 221 = 178
       178 · 35 = 6230 mod 221 = 42      → m = 42

The message came back. If an attacker can factor $n = 221$, they find $\varphi(n)$ and $d$. In real RSA $n$ is 2048 bits or more; factoring it is practically impossible with today’s computers.

PITFALL · computing $d$ mod $n$. The inverse is taken mod $\varphi(n)$: $ed \equiv 1 \pmod{\varphi(n)}$. A $d$ computed with $\bmod\ n$ comes out wrong. Encryption and decryption, on the other hand, are done with $\bmod\ n$.

Diffie-Hellman key exchange

Two parties produce a shared secret key over an open channel, without sharing any secret beforehand. Public to everyone: a prime $p$ and a generator $g$. Alice chooses a secret $a$, Bob chooses a secret $b$.

$A = g^a \bmod p, \quad B = g^b \bmod p, \quad K = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p$

Worked example. $p = 29$, $g = 2$, $a = 6$, $b = 11$.

A = 2^6  mod 29 = 64 mod 29   = 6
B = 2^11 mod 29 = 2048 mod 29 = 18
Alice: K = 18^6 mod 29.  18^2 = 324 mod 29 = 5,  18^4 = 25,  18^6 = 25·5 = 125 mod 29 = 9
Bob:   K = 6^11 mod 29.  6^2 = 7,  6^4 = 20,  6^8 = 23,  6^11 = 23·7·6 = 966 mod 29 = 9

Both found $K = 9$. An eavesdropper sees only 29, 2, 6 and 18; finding $a$ from $A$ is the discrete logarithm problem.

PITFALL · DH does not authenticate. A man-in-the-middle runs a separate DH with each side. That is why in real protocols the DH values are signed (in TLS, the server certificate and CertificateVerify).

Hash functions

A cryptographic hash function turns input of any size into a fixed-size output. SHA-256 produces 256 bits, that is 64 hexadecimal characters. Three security properties:

SHA-256("abc")     = ba7816bf8f01cfea414140de5dae2223 b00361a396177a9cb410ff61f20015ad
SHA-256("SEN2008") = 7f0f2c908360e1f1...
SHA-256("SEN2009") = 8ef7e4e5e6c5c0bd...   (127 of 256 bits differ)

When one character changes, about half of the bits change (avalanche). Birthday attack: for an $n$-bit hash a collision is found in about $2^{n/2}$ attempts. For SHA-256 that is $2^{128}$. Practical collisions have been found in MD5 and SHA-1, and they are not used in new systems.

MAC and HMAC

A plain hash does not protect integrity: an attacker modifies the message and recomputes the hash. A message authentication code (MAC) uses a shared secret key: $t = \text{MAC}_K(m)$. Whoever doesn’t know the key cannot produce a valid tag. The most common construction is HMAC:

$\text{HMAC}_K(m) = H\big((K \oplus opad) \,\|\, H((K \oplus ipad) \,\|\, m)\big)$

HMAC-SHA256("bau-key", "pay 100") = 0bf39f2a443f4059...
HMAC-SHA256("bau-key", "pay 900") = 5ab3cabd5e34bc43...

A MAC provides integrity and source authentication, but not non-repudiation: both sides have the key.

Digital signature

The sender signs the hash of the message with their private key; anyone verifies with the public key. With RSA: $s = h^d \bmod n$, verification $s^e \bmod n \stackrel{?}{=} h$.

A toy example ($n = 221$, $d = 77$, $e = 5$), hash $h = 30$:

s = 30^77 mod 221 = 166
verify: 166^2 = 152, 166^3 = 38, 166^4 = 120, 166^5 = 30 (mod 221)  → 30 = h, valid

Certificates and PKI

How will you know that a public key really belongs to the claimed person? A certificate (X.509 certificate) binds an identity (a domain name) to a public key and is signed by a certificate authority (CA). It contains: the subject, the public key, the issuer, validity dates, a serial number and the CA’s signature.

Chain of trust: root CA (in the browser’s trust store) → intermediate CA → the server (leaf) certificate. Each certificate is verified with the public key of its issuer; the chain must reach a trusted root. This whole structure is called the public key infrastructure (PKI). A certificate whose private key was stolen is revoked (CRL, OCSP).

The TLS handshake

TLS provides confidentiality, integrity and server authentication over TCP (HTTPS = HTTP + TLS). The TLS 1.3 handshake finishes in one round trip:

Client → ClientHello: supported versions, cipher suites, random value, (EC)DHE key share
Server → ServerHello: chosen suite, its own key share
         (everything after this is encrypted with the handshake keys)
         Certificate          the server certificate chain
         CertificateVerify    signature of the handshake hash with the server's private key
         Finished             MAC over the entire handshake
Client → Finished
Both directions: application data with AES-GCM (or ChaCha20-Poly1305)

The role of the parts: (EC)DHE produces the shared key, the certificate and CertificateVerify prove the server’s identity and prevent MITM, the Finished messages verify that the handshake was not modified, and AES-GCM encrypts the data and protects its integrity. Since a new DH key is used in every session, old recordings cannot be decrypted even if the server’s private key is stolen later (forward secrecy). TLS 1.2 had the option of RSA key transport and lacked this property; 1.3 removed it.

Common mistakes