Crypto Primitives
1. Overview
1.1 Big Picture
Cryptography is built from a small set of primitives (hash, symmetric/asymmetric crypto, signatures, key exchange), organized into layers. These power everything: TLS/HTTPS, git commit signing, code signing, email encryption, certificates.
1.2 Quick Facts
- Primitives split into symmetric (shared key) and asymmetric (key pair); plus hash, MAC, KDF, randomness.
- TLS uses both: asymmetric for key exchange/signatures, symmetric (AES) for the bulk session.
- Layers: primitive → mechanism → format → application.
- A signature always requires the private key; verification uses the public key.
- The private key is protected by password + custody; the certificate vouches for the public key’s identity.
- Signing ≠ encryption — one proves authorship, the other hides content.
- Git delegates signing to GPG/SSH/SMIME (
gpg.program); git itself has no crypto.
1.3 The Layers
Primitive (the math) → mechanism (what it does) → format (how it's stored) → application (how it's used)
hash, AES, key pair, sig → sign / verify / encrypt / → certificate (X.509) → TLS, git signing, code signing
exchange| Layer | Example | Question it answers |
|---|---|---|
| Primitive | SHA-256, AES, RSA, ECDSA, ECDH | What are the raw building blocks? |
| Mechanism | digital signature, key exchange | How do the primitives combine? |
| Format | X.509 certificate | How is the result stored/standardized? |
| Application | HTTPS, git signing, code signing | What real-world tool uses it? |
2. The Core Primitives
2.1 Symmetric vs Asymmetric (the big split)
| Symmetric | Asymmetric | |
|---|---|---|
| Keys | one shared key | key pair (public/private) |
| Speed | fast | slow |
| Used for | bulk data encryption (AES) | key exchange, signatures |
| In TLS | encrypts the actual session | establishes the session key |
2.2 Hash Function
- One-way fingerprint of data:
hash(data) → fixed-length digest - Cannot be reversed; any change to data changes the digest.
- Used everywhere as the base of everything else (signing hashes data first).
Algorithms:
| Family | Examples | Output | Status |
|---|---|---|---|
| SHA-2 | SHA-256, SHA-384, SHA-512 | 256–512 bit | Current standard |
| SHA-3 | SHA3-256, SHA3-512 | 256–512 bit | Current, Keccak-based |
| MD | MD5, SHA-1 | 128 / 160 bit | Broken — don’t use for security |
2.3 Symmetric Encryption
- Encrypt/decrypt with one shared key; fast, for bulk data.
- Without the same key, ciphertext can’t be read.
- Used by TLS to encrypt the actual session data (after asymmetric key exchange).
Algorithms:
| Algorithm | Type | Key size | Notes |
|---|---|---|---|
| AES | block cipher | 128–256 bit | The standard; TLS, disk, file encryption |
| ChaCha20 | stream cipher | 256 bit | Modern, fast on CPUs without AES hw |
| 3DES | block cipher | 168 bit | Deprecated — legacy only |
2.4 Message Authentication Code (MAC) / AEAD
- Authenticates a message with a shared key: proves it wasn’t tampered with.
- AEAD = authenticated encryption (encryption + integrity in one pass).
Algorithms:
| Algorithm | Type | Notes |
|---|---|---|
| HMAC | keyed hash (e.g. HMAC-SHA256) | authentication over a hash |
| AES-GCM | AEAD | AES + auth; TLS 1.3 standard |
| ChaCha20-Poly1305 | AEAD | modern alternative, TLS 1.3 |
2.5 Asymmetric Key Pair
- Public key = lock (share freely). Private key = key (keep secret).
- Generated together; what one encrypts/signs, the other verifies.
- Can’t derive the private key from the public key (the core security property).
Algorithms:
| Algorithm | Type | Key size | Notes |
|---|---|---|---|
| RSA | factorization | 2048–4096 bit | Oldest, most widespread |
| ECDSA | elliptic curve | 256 bit (≈3072 RSA) | Smaller keys, faster |
| Ed25519 | Edwards curve | 256 bit | Modern, fast, GPG default |
2.6 Asymmetric Encryption
- Encrypt with public key, decrypt with private key.
- Slow — used for key exchange/small data, not bulk.
Algorithms: RSA-OAEP, ECIES, and (in modern TLS) ephemeral ECDH instead of direct public-key encryption.
2.7 Digital Signature
- Signer:
sign(privkey, hash(data)) → signature - Verifier:
verify(pubkey, data, signature) → true/false - Proves authenticity (who signed), integrity (not altered), non-repudiation (can’t deny).
- Signing requires the private key; only its holder can produce a valid signature.
Algorithms: RSA-PSS, ECDSA, EdDSA (Ed25519) — same math as the key pair, applied to the digest.
2.8 Key Exchange
- Two parties agree a shared secret without sending it.
- Used by TLS to establish the encrypted session key.
Algorithms:
| Algorithm | Type | Notes |
|---|---|---|
| Diffie–Hellman (DH) | classic | shared secret over public channel |
| ECDH | elliptic curve | DH on EC, used by TLS |
| RSA key exchange | classic | older TLS, being deprecated |
2.9 Key Derivation (KDF) & Randomness
- KDF: derive a key from a password or base key (HKDF for TLS, PBKDF2/Argon2 for passwords).
- CSPRNG: cryptographically secure random source for keys/nonces (
/dev/urandom, DRBG) — every key starts here.
3. The Chain: How Primitives Combine
data → hash → digest → sign(privkey) → signature
│
verify: digest' == hash(data) AND verify(pubkey, digest', signature)TLS adds key exchange on top: certificates (signed identities) → ECDH → shared session key → encrypted channel.
4. Signing vs Encryption
| Digital Signature | Encryption | |
|---|---|---|
| Proves | authorship / integrity | confidentiality |
| Uses | private to sign, public to verify | public to encrypt, private to decrypt |
| Analogy | wax seal | lockbox |
| Git/TLS use | certs + handshake signature | session encryption |
Signing ≠ encryption — one proves authorship, the other hides content.
5. Applications
5.1 Overview
| Domain | What gets signed/encrypted |
|---|---|
| Git commits / tags | commit data |
| Code signing | executables, mobile apps |
| TLS/HTTPS | certificates (identity) + session (encryption) |
| PGP / S/MIME | |
| Packages | apt / npm / pip repo verification |
| Firmware | secure boot |
| 2FA / one-time codes (HOTP/TOTP) | authentication via HMAC |
5.2 Certificates & PKI (see dedicated note)
Certificates package a public key + identity + CA signature; PKI is the governance system (CAs, trust stores, revocation) around them. Details in Certificates.
Private-key protection: password + custody (see Certificates for password vs certificate).
5.3 Example: Git Commit Signing
Walk through of how the primitives apply in practice — signing a git commit.
Purpose & use cases: prove authorship (only you hold the private key, so a valid signature = the commit came from you); detect tampering (if commit content is edited/rebased/amended, the signature no longer verifies); enterprise/compliance audit trail showing who pushed what, tamper-evident.
Setup (one-time):
gpg --full-generate-key # generate a key pair (e.g. Ed25519)
gpg --list-secret-keys # find the key ID
git config user.signingkey <KEYID> # git uses this key
git config commit.gpgsign true # auto-sign every commit
git config gpg.program "...\gpg.exe"
# publish the PUBLIC key to GitHub (Settings → SSH and GPG keys)
# so GitHub can show "Verified"What happens on git commit:
1. git builds the commit object (tree, parent, message, author, timestamp)
2. git hands the commit bytes to gpg (gpg.program) → gpg hashes them (SHA-256)
3. gpg signs the digest with YOUR PRIVATE key (asks for passphrase to unlock)
4. gpg returns the signature → git stores it in the commit
5. commit written; the signature is part of the commit data commit bytes ─► hash (SHA-256) ─► sign(PRIVATE key) ─► signature
│
verification: hash(commit) == digest AND verify(PUBLIC key) ✓What happens on git log / GitHub (verify): GitHub reads the commit’s signature, looks up your published public key, and checks verify(pubkey, commit, signature). If valid and the key is yours → shows “Verified” ✓.
Why each primitive is used:
| Step | Primitive | Role |
|---|---|---|
| Hash the commit | hash function | sign a small fixed digest, not the whole commit |
| Sign the digest | key pair + signature | prove the private-key holder authored it |
| Store signature in commit | format | so it travels with the commit |
| Verify on GitHub | signature + public key | anyone can check without the private key |
Turning off signing (per repo / global / per commit):
git config --unset commit.gpgsign # stop auto-signing (local config)
git config --global --unset commit.gpgsign # stop auto-signing (all repos)
git config --global commit.gpgsign false # explicitly disable
git commit --no-gpg-sign -m "..." # skip signing for a single commit
git tag --no-sign v1.0.0 # skip signing for a single tagTroubleshooting:
gpg: signing failed: Timeout— gpg-agent waiting for passphrase; restart it:gpgconf --kill gpg-agent && gpgconf --launch gpg-agent- “Unverified” on GitHub — public key not published, or the commit used a different key/identity.
- Verification broken after rebase — rewritten commits have different content → signatures no longer match (expected).
5.4 Example: One-Time Codes (HOTP & TOTP)
Both are hash-based (HMAC) authentication apps for 2FA — proving you know a shared secret, not signing data.
The core in one sentence: the code is HMAC(secret, time) — the client and server both recompute the same value with the same secret and same time, so matching codes prove you hold the secret.
| HOTP | TOTP | |
|---|---|---|
| Full name | HMAC-based OTP | Time-based OTP |
| Input | counter (increments per use) | current time / 30s |
| Called | ”hash-based OTP" | "time-based OTP” |
| One-time-ness | counter advances | time moves forward |
HOTP: HMAC(secret, counter) → 6-digit code
TOTP: HMAC(secret, floor(time/30)) → 6-digit code- TOTP is HOTP with time as the moving factor (RFC 6238 extends HOTP).
- Shared secret key on both authenticator and server (symmetric).
- Underlying primitives: hash (SHA-1), MAC (HMAC), shared key, CSPRNG (secret seed).
Why HOTP is legacy: counter drift. The token and server counters can fall out of sync (“out of sync” errors), requiring resync. TOTP replaced the fragile counter with a universal clock — self-syncing, no drift, auto-refresh every 30s. HOTP survives only where a time source isn’t practical (offline hardware tokens).
How TOTP works (step by step):
1. Setup — server generates a random secret (CSPRNG) → QR → authenticator app
2. Counter — T = floor(utc_time / 30) (moves every 30s)
3. HMAC — HS = HMAC-SHA1(secret, T) (20 bytes)
4. Truncate — offset = HS[19] & 0x0F; take 4 bytes; clear sign bit → 31-bit int
5. Modulo — code = (binary mod 1,000,000) (pad to 6 digits)
6. Verify — server recomputes the same value and compares (accept ±1 window)Primitives used at each step:
| Step | Primitive / Algorithm |
|---|---|
| Generate secret | CSPRNG (randomness) |
| Derive counter | arithmetic (floor(time/30)) |
| HMAC | HMAC-SHA1 (uses SHA-1 hash) |
| Truncate | bit manipulation |
| Modulo | arithmetic |
| Verify | HMAC recompute + compare |
Example flow (TOTP):
1. Setup: server and authenticator app share a secret key (from a QR code)
2. Every 30s: authenticator computes HMAC(secret, time/30) → 6-digit code
3. Login: user enters the code; server recomputes the same HMAC
4. Codes match → user knows the secret → authenticated