Cryptography and security

When Leyla pays in her banking app, the data passes through dozens of strangers' devices, yet none of them can read or change the amount, and the bank is sure the request really came from Leyla. That is cryptography at work. It serves four goals: confidentiality (others cannot read), integrity (changes are detected), authenticity (we know who sent it) and non-repudiation (the sender cannot later say “it wasn't me”).

Symmetric encryption

The modern standard is AES (128-, 192- or 256-bit keys): it is very fast and has hardware support in processors. A 128-bit key has 2¹²⁸ ≈ 3.4 · 10³⁸ possibilities — trying them all is practically impossible. The real problem is different: how do you share the key? Every pair among n people needs its own key — n(n − 1)/2 keys, 499,500 for 1000 users. And the key cannot be sent over an insecure channel the first time.

Asymmetric cryptography: Diffie–Hellman and RSA

In asymmetric cryptography every user has two keys: a public key given to everyone and a private key shown to no one. What is encrypted with the public key can be opened only with the private key. It rests on mathematical operations that are “easy one way, hard to reverse”: multiplying two large primes is easy, but factoring the product is very hard; computing gᵃ mod p is easy, but recovering a (the discrete logarithm) is hard.

p, g = 23, 5
a, b = 6, 15
A, B = pow(g, a, p), pow(g, b, p)
print('DH public:', A, B, '| shared:', pow(B, a, p), pow(A, b, p))

p, q, e = 3, 11, 3
n, phi = p * q, (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = 4
c = pow(m, e, n)
print('RSA n =', n, 'phi =', phi, 'd =', d)
print('encrypt', m, '->', c, '| decrypt ->', pow(c, d, n))
s = pow(m, d, n)
print('signature', s, '| verify ->', pow(s, e, n))

DH public: 8 19 | shared: 2 2
RSA n = 33 phi = 20 d = 7
encrypt 4 -> 31 | decrypt -> 4
signature 16 | verify -> 4

Hash functions and digital signatures

A cryptographic hash (such as SHA-256) turns data of any length into a fixed-length (256-bit) “fingerprint”. Requirements: the same result every time; the data cannot be recovered from the hash (one-wayness); finding two different inputs with the same hash is practically impossible (collision resistance); a one-bit change flips about half the bits of the hash (avalanche effect). A hash is not encryption: it has no key and cannot be reversed.

import hashlib, math

for text in ['Educora', 'educora', 'Educora!']:
    print(text, hashlib.sha256(text.encode()).hexdigest()[:16])

rate = 10 ** 10
for name, n, length in [('8 lowercase', 26, 8), ('12 mixed', 94, 12)]:
    bits = length * math.log2(n)
    seconds = n ** length / rate
    print(name, '|', round(bits, 1), 'bits |', f'{seconds:.3g}', 'seconds')

Educora b3dbb4d80128c71a
educora 48ecb7c2aeec01dc
Educora! 836636e98b18e97a
8 lowercase | 37.6 bits | 20.9 seconds
12 mixed | 78.7 bits | 4.76e+13 seconds

Passwords must never be stored as plain text or with plain SHA-256: the server gives each user a random salt and hashes the password with a deliberately slow function — Argon2, bcrypt, scrypt or PBKDF2. The salt stops equal passwords from producing equal hashes and defeats precomputed tables; the slowness blocks billions of fast guesses. A digital signature works like this: the sender signs the message's hash with their private key, and anyone verifies it with the sender's public key. Who a public key belongs to is confirmed by a certificate — a document signed by a trusted authority (CA).

Attacks and defences

-- the program glues user input into the query:
--   WHERE email = '<input>'
-- the attacker types:  x' OR '1'='1
SELECT COUNT(*) AS leaked_rows
FROM students
WHERE email = 'x' OR '1'='1';

leaked_rows
12