Cryptography and Trust

Remainders

A clock counts 1, 2, 3, up to 12, and then starts again. If it is 10 o’clock now, in 5 hours it will be 3 o’clock, not 15 o’clock. You add as usual, then throw away whole rounds of 12. Days of the week work the same way, in rounds of 7.

When you divide one whole number by another, what is left over is the remainder. 15 ÷ 12 is 1, remainder 3. Working only with remainders is called modular arithmetic, or clock arithmetic, and the number you divide by is the modulus. We write “15 mod 12 = 3”, and Python writes 15 % 12.

days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]today = 6                      # Saturdayprint(days[(today + 100) % 7]) # 100 days from nowprint(17 % 5, 23 % 5, -1 % 5)

Monday2 3 4

100 days is 14 whole weeks and 2 days more, so 100 days after a Saturday is 2 days after a Saturday: a Monday. (Python’s % always gives a remainder from 0 up to one less than the modulus, so −1 % 5 is 4: one step back from 0 on a clock of 5 is 4.)

Two numbers with the same remainder behave the same on the clock. 17 and 2 both leave 2 when divided by 5; we say 17 is congruent to 2, mod 5, and write 17 ≡ 2 (mod 5).

One rule makes modular arithmetic quick: you may take the remainder at any step, and the answer at the end is the same. To find (17 × 23) mod 5, you could multiply first, 391 mod 5 = 1, or reduce first, 2 × 3 = 6, and 6 mod 5 = 1. Same answer. A computer uses this to keep its numbers small: however long the sum, it never needs a number much bigger than the modulus.

Powers, with remainders

The mathematics of this unit uses powers: 65¹⁷ mod 3233, for example. 65¹⁷ is a number 31 digits long, and real keys use powers hundreds of digits long, far too big to work out and then divide. But with the rule above, you never have to. A computer finds a power by repeated squaring: work out a, a², a⁴, a⁸, a¹⁶ … by squaring the last one each time, taking the remainder each time, and multiply together the ones it needs. 17 = 16 + 1, so 65¹⁷ = 65¹⁶ × 65¹.

def power_mod(a, k, n):    """a to the power k, mod n, by squaring: also counts the multiplications."""    result, square, steps = 1, a % n, 0    while k > 0:        if k % 2 == 1:                       # this bit of k is 1            result = result * square % n            steps = steps + 1        square = square * square % n         # a², a⁴, a⁸, a¹⁶, …        steps = steps + 1        k = k // 2    return result, steps print(power_mod(65, 17, 3233))print(power_mod(2790, 2753, 3233))print(pow(2790, 2753, 3233))                 # Python's own does the samebig = 2 ** 2048 - 1                          # a power over 600 digits longprint(power_mod(7, big, 3233)[1], "multiplications")

(2790, 7)(65, 17)654096 multiplications

The loop goes once for each bit of k (line 10 halves it), so a power with a 2,048-bit exponent, a number over 600 digits long, takes at most about 4,000 multiplications, not a number of multiplications with 600 digits. Python’s built-in pow(a, k, n) does the same thing, faster.

A pattern in the powers

Here is a picture of every power from a¹ to a²⁴ of every number a from 0 to 32, mod 33. Each row is one number a; each column is one power; each remainder from 0 to 32 has its own color.

import colorsysfrom pixels import show_grid n = 33                       # 3 × 11colors = []                  # one color for each remainder, 0 to 32for v in range(n):           # hues spread round the color wheel, so neighbors differ    r, g, b = colorsys.hsv_to_rgb(v * 0.618 % 1, 0.65, 0.95)    colors.append((r * 255, g * 255, b * 255)) rows = []for a in range(n):           # a row for each number a    rows.append([pow(a, k, n) for k in range(1, 25)])   # a¹ to a²⁴, mod 33print("a = 2:", rows[2])print("a = 7:", rows[7])show_grid(rows, colors) # green where the power is back at the row's own number aback = [["seagreen" if rows[a][k] == a else "gainsboro" for k in range(24)] for a in range(n)]show_grid(back)

a = 2: [2, 4, 8, 16, 32, 31, 29, 25, 17, 1, 2, 4, 8, 16, 32, 31, 29, 25, 17, 1, 2, 4, 8, 16]a = 7: [7, 16, 13, 25, 10, 4, 28, 31, 19, 1, 7, 16, 13, 25, 10, 4, 28, 31, 19, 1, 7, 16, 13, 25]

Picture

(pixels is the page’s own small module for showing a grid of colors; on a computer you would use a library such as Pillow or Matplotlib.)

Look at columns 11 and 21 of the first picture. Each is the same as column 1: every number has come back to itself. The second picture marks in green every square where a power is back at its row’s own number: columns 1, 11 and 21 are green all the way down. (So are a few whole rows, such as 0 and 1, which are themselves to every power.) The powers go round and round, and after the 20th power they are always back at the start. Why 20? Because 33 = 3 × 11, and (3 − 1) × (11 − 1) = 2 × 10 = 20. This is true for any two different primes p and q, a fact that goes back to Leonhard Euler in the 1760s:

If n = p × q, then for every number a below n, a raised to the power 1 + (p − 1)(q − 1), or 1 plus any multiple of it, is a again, mod n.

The number (p − 1)(q − 1) is written φ(n) (the Greek letter phi). For 33 it is 20, so a²¹ ≡ a, a⁴¹ ≡ a, and so on. (For some n, like 33, the powers come back even sooner, at column 11; but they always come back at 1 + φ(n).)

That is all RSA needs. If you can split the power 21 into two numbers multiplied together, 21 = 3 × 7, then raising to the power 3 and afterwards to the power 7 is the same as raising to the power 21, and brings every number back to itself. One power scrambles; the other unscrambles.

Multiplying and factoring

Multiplying two primes is quick, by hand or by computer. Going back, from the product to the two primes, is called factoring, and the only simple way is to try dividing by 2, 3, 4 and so on until one goes exactly. Grade 9 asked you to factor 3,233 by hand. Here a program does it for bigger and bigger products, and counts its tries.

def is_prime(m):    if m < 2:        return False    d = 2    while d * d <= m:        if m % d == 0:            return False        d = d + 1    return True def next_prime(m):    while not is_prime(m):        m = m + 1    return m def factor(n):    """Try dividing by 2, 3, 4, … until one goes exactly. Count the tries."""    d = 2    while n % d != 0:        d = d + 1    return d, d - 1 for digits in [2, 3, 4, 5, 6]:    p = next_prime(10 ** (digits - 1) + 7)    q = next_prime(p * 3 // 2)    n = p * q    found, tries = factor(n)    print(f"n = {n:>14,} ({len(str(n))} digits): {found} found after {tries:,} tries")

n =            493 (3 digits): 17 found after 16 triesn =         17,441 (5 digits): 107 found after 106 triesn =      1,536,707 (7 digits): 1009 found after 1,008 triesn =    150,235,091 (9 digits): 10007 found after 10,006 triesn = 15,006,950,779 (11 digits): 100019 found after 100,018 tries

Every two more digits in n, ten times more tries. An RSA number in use (as of 2026) is at least 2,048 bits, 617 digits long; trying divisions one by one would take about 10³⁰⁸ tries. Mathematicians have far cleverer methods than trying every divisor (the best, the number field sieve, is what broke the records in the box below), but even they grow so fast that a 617-digit product is far out of reach. Multiplying it took a computer a millionth of a second.

That gap is what Unit 2 called the difference between checking and finding. Factoring is in NP (a proposed factor is checked with one division), but no fast method to find the factors is known, and fifty years of effort by very clever people have not found one.

Undoing a multiplication on the clock

RSA needs one more tool: on a clock of 40, which number times 7 gives 1? Try them: 7 × 23 = 161 = 4 × 40 + 1. So 23 is the inverse of 7, mod 40: multiplying by 23 undoes multiplying by 7. An inverse exists only when the number and the modulus share no factor bigger than 1 (their greatest common divisor, gcd, is 1); 4 has no inverse mod 40, because every multiple of 4 is even, and so is 40.

For big numbers you can’t try them all. Euclid’s algorithm, extended a little, finds the inverse in a few steps, about as many as the numbers have digits. Python does it for you: pow(7, -1, 40) gives 23.

Now you have all the pieces. Here is how a key pair is made, with p = 61 and q = 53, the primes you factored by hand in Grade 9.

Making a key pair

1. Choose two different primes, p and q. Here p = 61, q = 53. (Real ones are about 300 digits each, chosen at random.)
2. Multiply them: n = p × q = 3,233. This is the modulus, and it is public.
3. Work out φ(n) = (p − 1)(q − 1) = 60 × 52 = 3,120. This is secret: anyone who knew it could make the private key.
4. Choose a public power e that shares no factor with φ(n). Here e = 17. (Real systems almost always use e = 65,537.)
5. Work out the private power d, the inverse of e, mod φ(n): the number with e × d = 1 + a multiple of 3,120. Here d = 2,753, because 17 × 2,753 = 46,801 = 15 × 3,120 + 1.

The public key is the pair (n, e) = (3233, 17): give it to anyone. The private key is (n, d) = (3233, 2753): it never leaves its owner. Then p, q and φ(n) are thrown away, or kept as securely as d.

Encrypting and decrypting

A message is first turned into a number m smaller than n (text as its bytes, Grade 9’s Unit 2). Then:

• To encrypt, anyone raises m to the public power: c = mᵉ mod n.
• To decrypt, the owner raises c to the private power: m = cᵈ mod n.

It works because of the pattern in the picture. cᵈ = (mᵉ)ᵈ = mᵉˣᵈ, and e × d is 1 plus a multiple of φ(n), so mᵉˣᵈ is m again.

The same thing in Python, with the steps as functions:

import math def make_keys(p, q, e):    n = p * q    phi = (p - 1) * (q - 1)    if math.gcd(e, phi) != 1:        raise ValueError(f"e = {e} shares a factor with {phi}: choose another")    d = pow(e, -1, phi)          # the d with e × d = 1 more than a multiple of phi    return (n, e), (n, d)        # the public key, the private key public, private = make_keys(61, 53, 17)print("public key:", public)print("private key:", private) def encrypt(m, key):    n, e = key    return pow(m, e, n) def decrypt(c, key):    n, d = key    return pow(c, d, n) c = encrypt(65, public)print("65 encrypted:", c)print("decrypted again:", decrypt(c, private))

public key: (3233, 17)private key: (3233, 2753)65 encrypted: 2790decrypted again: 65

Why it is safe, and when it isn’t

Everything an eavesdropper needs to decrypt is d. To work out d, they need φ(n) = (p − 1)(q − 1), and for that they need p and q. All they have is n. So the safety of RSA is the difficulty of factoring n. With n = 3,233 that takes a minute by hand; with 617 digits, nobody knows how.

Using RSA well: the same message, the same ciphertext

The RSA you have just used, called textbook RSA, has a weakness that has nothing to do with factoring. The same message encrypted with the same public key always gives the same ciphertext. So an eavesdropper who can guess what the message might be can encrypt each guess with the public key, which they have, and compare.

See it in a picture. Each square of this small picture of a mountain is one of four colors, numbered 10 to 13. The program encrypts every square on its own, with the key pair from 61 and 53, and shows each ciphertext (0 to 3,232) as a shade of gray.

import randomfrom pixels import show_gridrandom.seed(1)                             # the same numbers every run: see below N, E, D = 3233, 17, 2753                   # the key pair made from 61 and 53picture = ["....................",           "...............OO...",           "......#.......OOOO..",           ".....###.......OO...",           "....##*##...........",           "...##***##...#......",           "..##*****##.###.....",           ".##*******#####*....",           "##*****************.",           "********************"]number = {".": 10, "#": 11, "*": 12, "O": 13}   # sky, snow, rock, suncolors = {10: "skyblue", 11: "white", 12: "dimgray", 13: "gold"} def gray(c):                               # a ciphertext, 0 to 3232, as a gray    return c * 255 // (N - 1) plain, padded, back = [], [], []for row in picture:    p_row, s_row, b_row = [], [], []    for ch in row:        m = number[ch]        p_row.append(gray(pow(m, E, N)))   # 1. each square encrypted as it is        r = random.randrange(200)          # 2. a random number goes in with it        c = pow(16 * r + m, E, N)          #    (16r + m is always below 3233)        s_row.append(gray(c))        b_row.append(pow(c, D, N) % 16)    # 3. decrypted: the remainder by 16 is m    plain.append(p_row)    padded.append(s_row)    back.append(b_row) print("Every sky square encrypts to", pow(10, E, N))show_grid(plain)show_grid(padded)show_grid(back, colors)

Every sky square encrypts to 1096

Picture

The first picture is encrypted, every square of it, and the mountain is still there. Every sky square became 1,096 and every snow square the same number as every other snow square, so the shapes survive. The second time, lines 28 and 29 mix a random number r into each square before encrypting: 16r + m. Now two sky squares get different ciphertexts, and the picture is noise. The owner of the private key decrypts and keeps the remainder by 16, which is m (line 31), and the mountain comes back.

Real RSA does the same. Before encrypting, a message is mixed with fresh random bytes in a carefully designed way called padding (the standard one is called OAEP), so that the same message never gives the same ciphertext twice. (This program uses Python’s random with a fixed starting point, a seed (line 3), only so that its picture is the same every time you run it. That makes its “random” numbers completely predictable, which is exactly what padding must never be: real code takes its random numbers from secrets, as the last section of this unit explains.)

RSA lets anyone send a secret to the owner of a key pair. But two people often want something simpler: one shared key, for a fast cipher like AES, agreed on over a line that anyone can hear. That is key exchange, and the method Whitfield Diffie and Martin Hellman published in 1976 (Grade 9 told their story) still does it in almost every secure connection.

Mixing paint

Picture it with paint first. Sita and Ram agree, out loud, on a common color, yellow. Each also picks a secret color, which they never say. Each mixes the yellow with their own secret color, and sends the mixture across. Then each adds their own secret color to the mixture they received. Both end up with yellow + Sita’s color + Ram’s color: the same paint. Eve, listening, has seen the yellow and both mixtures, but separating a mixture back into its colors is very hard, so she can’t make the final paint.

With numbers

In place of paint, powers mod a prime. Everyone, Eve too, knows a prime p and a number g. Here p = 101 and g = 2.

1. Sita picks a secret number a and sends A = gᵃ mod p.
2. Ram picks a secret number b and sends B = gᵇ mod p.
3. Sita works out Bᵃ mod p. Ram works out Aᵇ mod p.

Both get the same number, because Bᵃ = (gᵇ)ᵃ = gᵇˣᵃ and Aᵇ = (gᵃ)ᵇ = gᵃˣᵇ. That number is their shared key. Neither a nor b was ever sent.

p, g = 101, 2                 # public: everyone knows them, Eve too a = 37                        # Sita's secret, never sentb = 64                        # Ram's secret, never sent A = pow(g, a, p)              # Sita sends thisB = pow(g, b, p)              # Ram sends thisprint("Sent over the open line:", A, "and", B) print("Sita works out", pow(B, a, p))print("Ram works out ", pow(A, b, p)) # Eve has p, g, A and B. She tries every power of g until one gives A.for k in range(1, p):    if pow(g, k, p) == A:        print(f"Eve finds Sita's secret after {k} tries: {k}")        print("so Eve works out", pow(B, k, p))        break

Sent over the open line: 55 and 79Sita works out 52Ram works out  52Eve finds Sita's secret after 37 tries: 37so Eve works out 52

Why powers and not multiplying

Why not just multiply: send g × a mod p? Because multiplying on a clock is easy to undo (multiply by the inverse), but powers are not. Here is a picture of both. In each, row k has a single black square, at the column of 2 × k mod 101 (left) or 2ᵏ mod 101 (right).

from pixels import show_grid p = 101times, powers = [], []for k in range(1, p):    times.append(["black" if x == 2 * k % p else "white" for x in range(p)])    powers.append(["black" if x == pow(2, k, p) else "white" for x in range(p)])show_grid(times)show_grid(powers)

Picture

The multiples lie on straight lines: given a number, you can read off which row it came from. The powers jump about the clock with no pattern anyone has found a fast way to follow. Going back from gᵃ mod p to a is called the discrete logarithm problem, and like factoring, no fast method is known for the large primes used in practice.

A stranger in the middle

Key exchange has one gap. Sita has agreed a key with someone, but with whom? If Eve controls the café’s Wi-Fi router, she can stand in the middle: do one key exchange with Sita, pretending to be Ram, and another with Ram, pretending to be Sita. Then she decrypts everything Sita sends, reads it, encrypts it again with Ram’s key, and passes it on. Neither notices. This is a man-in-the-middle attack, and the numbers alone can’t stop it. Sita needs proof that the B she received really came from Ram. That proof is a signature, the next section.

A fresh key every time

In a secure connection, both sides pick new secret numbers for every visit and forget them afterwards. If a thief records your encrypted traffic today and, years later, steals the server’s long-term private key, the old recordings still can’t be read: the keys that encrypted them no longer exist anywhere. This is called forward secrecy. TLS 1.3, the version of the rules behind HTTPS published in 2018, uses it every time a connection is set up afresh.

A handwritten signature on a cheque says who agreed to pay, and a bank checks it against the one they have on file. But it can be copied, and it doesn’t stop someone changing the amount after you sign. A digital signature does better on both: nobody without the private key can make it, and it fits only the exact message that was signed.

Signing with RSA

The two powers of RSA undo each other in either order. So the owner can raise a number to the private power first, and anyone can undo it with the public power. That is a signature: only the private key could make it, and anyone can check it.

A message is usually longer than n, so it is hashed first (Grade 9’s SHA-256), and the hash is signed:

1. Ram signs: work out h, the hash of the message, as a number below n. The signature is s = hᵈ mod n.
2. Anyone checks: work out h from the message they received, and sᵉ mod n from the signature. If the two are equal, the signature is good.

import hashlib N, E, D = 3233, 17, 2753          # Ram's key pair (from 61 and 53) def digest(message):    """The message's SHA-256 hash, as a number below N (only for these small keys)."""    h = hashlib.sha256(message.encode()).hexdigest()    return int(h, 16) % N def sign(message):                # Ram, with his private key    return pow(digest(message), D, N) def check(message, signature):    # anyone, with Ram's public key    return pow(signature, E, N) == digest(message) note = "Pay Sita Rs 500. Ram"s = sign(note)print("signature:", s)print(check(note, s))print(check("Pay Sita Rs 5000. Ram", s))print(check(note, s + 1))

signature: 1059TrueFalseFalse

Change the message by one character, and its hash is different, so the signature no longer matches. Change the signature, and it no longer undoes to the hash. To make a signature that matches a new message, you need d.

What a signature proves, and what it doesn’t

A good signature proves exactly two things:

• Who: the message was signed with the private key that matches this public key.
• Unchanged: the message is exactly what was signed, to the last character.

It doesn’t prove:

• Which person holds that private key. A public key is just numbers; something else must tie it to a name. (That is what certificates do, in the next section.)
• That the private key wasn’t stolen. Whoever has the key can sign as its owner. That is why private keys are kept on the device, often in a chip made to protect them, and can be withdrawn (revoked) when lost.
• That the message is true or wise. A message saying the earth is flat can carry a perfectly good signature; it is still false.
• When it was signed, or that it is fresh. A signed “Pay Sita Rs 500” could be sent again tomorrow, and the signature would still check. Real systems put a date and a number used only once inside what is signed, so a copy is refused. Sending an old signed message again is called a replay.

Nepal’s Electronic Transactions Act, 2063 (2008), which you met in Grade 9, gives digital signatures legal force, and sets up an office, the Controller of Certification, that licenses the authorities allowed to issue certificates tying keys to people and organizations in Nepal.

Signing in without a password: passkeys

A password is a secret you send to the website every time you sign in, so a fake website can collect it. A passkey is a key pair instead. When you create one, your phone makes a new key pair for that website and gives the website only the public key. To sign in:

1. The website sends a fresh random number, a challenge.
2. Your phone asks you to unlock it (a fingerprint, your face or the phone’s PIN), then signs the challenge, together with the website’s name, with the private key.
3. The website checks the signature with the public key it stored.

The private key never leaves your phone, so there is nothing for a thief to steal from the website’s database (a list of public keys is no use to anyone), and nothing for a fake website to collect. A lookalike website gets a signature for its own name, or nothing, because the phone keeps a different key for every site. The price: if you lose the phone, you need another way in, such as a passkey copied to your other devices or a recovery code kept somewhere safe.

Grade 11 showed what a certificate says (a name, a public key, dates, an issuer) and the three checks a browser makes: the chain leads to a root in its list, the name is the one in the address bar, and the dates are right. Now you can see the mathematics inside. A certificate is a signed message: “this public key belongs to bhakaripay.com.np”, signed with the private key of a certificate authority. Checking it is checking a signature.

That last step closes the gap in key exchange. When your browser connects, the server sends its certificate chain and its key-exchange number B, signed with the private key that matches the public key in its certificate. Eve in the middle can send her own number, but she can’t sign it with the bank’s private key, and a certificate for her own key won’t carry the bank’s name.

Here is the browser’s check, with tiny keys. (Himal Root CA and Himal Issuing CA are made up, like Bhakari Pay.)

import hashlib def digest(text, n):    return int(hashlib.sha256(text.encode()).hexdigest(), 16) % n def sign(text, private):    n, d = private    return pow(digest(text, n), d, n) def signed_by(text, signature, public):    n, e = public    return pow(signature, e, n) == digest(text, n) # The keys (made-up authorities; tiny numbers so you can follow them)root_pub, root_priv = (8633, 17), (8633, 497)      # Himal Root CA, built into the browsermid_pub, mid_priv = (10403, 7), (10403, 8743)      # Himal Issuing CAsite_pub = (3233, 17)                              # bhakaripay.com.np # Each certificate: what it says, and the signature of the one abovemid_cert = "name=Himal Issuing CA; key=10403,7; issuer=Himal Root CA"site_cert = "name=bhakaripay.com.np; key=3233,17; issuer=Himal Issuing CA"chain = [(site_cert, sign(site_cert, mid_priv)), (mid_cert, sign(mid_cert, root_priv))] trusted = {"Himal Root CA": root_pub}               # the browser's own list def field(cert, name):    for part in cert.split("; "):        key, value = part.split("=")        if key == name:            return value def check_chain(chain, address):    if field(chain[0][0], "name") != address:        return "refused: certificate is for another name"    for i, (cert, signature) in enumerate(chain):        issuer = field(cert, "issuer")        if i + 1 < len(chain):                      # the next certificate's key            n, e = field(chain[i + 1][0], "key").split(",")            above = (int(n), int(e))        elif issuer in trusted:                     # or a root the browser knows            above = trusted[issuer]        else:            return f"refused: nobody trusted vouches for {issuer}"        if not signed_by(cert, signature, above):            return f"refused: the signature on {field(cert, 'name')} doesn't match"    return "trusted" print(check_chain(chain, "bhakaripay.com.np"))print(check_chain(chain, "bhakaripay-reward.com"))fake = site_cert.replace("3233,17", "4087,5")       # a certificate with another key in itprint(check_chain([(fake, chain[0][1]), chain[1]], "bhakaripay.com.np"))

trustedrefused: certificate is for another namerefused: the signature on bhakaripay.com.np doesn't match

The third test is Eve’s attempt: she copies the bank’s certificate and puts her own public key in it, so that she could sign the key exchange herself. The issuing authority’s signature was made for the text with the bank’s key, so it no longer matches, and the browser refuses. (A real browser also checks the dates and whether the certificate has been withdrawn; the program leaves those out to stay short.)

When a check fails

The last row is the weak point of the whole system: every authority in the list can sign for any name, so the chain is only as strong as the weakest authority in it. Grade 11 told what happened when DigiNotar was broken into in 2011. Every certificate a trusted authority issues is now (as of 2026) published in public Certificate Transparency logs, so a false one for a bank’s name can be spotted by the bank within hours. Those logs are themselves hash chains of a kind, which the next section explains.

Trust without an authority: comparing fingerprints

End-to-end encrypted chat apps (Grade 9) have no certificate authority. Your phone gets your friend’s public key from the company’s server. What if the server, or someone who broke into it, handed you a different key, and stood in the middle? The defense is to compare the key itself, in person or on a call: not 600 digits, but a short fingerprint, a hash of the key, shown as numbers, a QR code, or a picture. Two keys that differ in a single digit give completely different fingerprints.

import colorsysimport hashlibfrom pixels import show_grid def fingerprint(key):    """A 9 × 9 picture of a key's hash, mirrored left to right like a face."""    bits = bin(int(hashlib.sha256(key.encode()).hexdigest(), 16))[2:].zfill(256)    hue = int(hashlib.sha256(key.encode()).hexdigest()[:4], 16) / 65536    r, g, b = colorsys.hsv_to_rgb(hue, 0.7, 0.6)  # a dark color from the hash too    color = (r * 255, g * 255, b * 255)    rows = []    for r in range(9):        half = [color if bits[r * 5 + c] == "1" else "white" for c in range(5)]        rows.append(half + half[3::-1])          # the left half, then its mirror    return rows ram = "3233,17"            # Ram's real public keyother = "3223,17"          # one digit different: someone else'sshow_grid(fingerprint(ram))show_grid(fingerprint(other))print(hashlib.sha256(ram.encode()).hexdigest()[:20])print(hashlib.sha256(other.encode()).hexdigest()[:20])

5d57ae623cfca6e254db79f7a76c204e3e0e5b3c

Picture

A savings group in a village keeps a notebook: every deposit and loan, one line after another, signed by the treasurer. What stops someone, months later, quietly changing “borrowed Rs 3,000” to “borrowed Rs 300”? In a notebook, perhaps the ink. In a computer file, nothing: a changed record looks like any other.

A chain of hashes

Put each record in a block with the hash of the block before it, and then hash the whole block. Now every block’s hash depends on its own record and, through the previous hash, on every record before it. This is a hash chain.

import hashlib def sha(text):    return hashlib.sha256(text.encode()).hexdigest() def make_chain(records):    chain, prev = [], "0" * 64            # the first block points at nothing    for record in records:        block = {"record": record, "prev": prev}        block["hash"] = sha(block["prev"] + block["record"])        chain.append(block)        prev = block["hash"]    return chain def links_ok(chain):    """For each block: does it match its own hash, and point at the one before?"""    ok, prev = [], "0" * 64    for block in chain:        ok.append(block["prev"] == prev and sha(block["prev"] + block["record"]) == block["hash"])        prev = block["hash"]    return ok book = make_chain(["Baisakh 3: Sita saves Rs 500",                   "Baisakh 9: Hari saves Rs 1,200",                   "Jestha 2: Sita borrows Rs 3,000",                   "Jestha 20: Gita saves Rs 800",                   "Asar 5: Sita repays Rs 1,000",                   "Asar 30: Hari saves Rs 700"])for block in book:    print(block["hash"][:12], block["record"]) book[2]["record"] = "Jestha 2: Sita borrows Rs 300"         # someone changes a recordbook[2]["hash"] = sha(book[2]["prev"] + book[2]["record"])   # and its own hashprint(links_ok(book))

c81adf473de4 Baisakh 3: Sita saves Rs 5006244c0c26750 Baisakh 9: Hari saves Rs 1,200c74cae84538c Jestha 2: Sita borrows Rs 3,000889c6f2b01c1 Jestha 20: Gita saves Rs 800d80e4ed82c09 Asar 5: Sita repays Rs 1,0000751be26a708 Asar 30: Hari saves Rs 700[True, True, True, False, True, True]

The changed block itself looks fine: the forger gave it a new hash to match. The fourth block is the one that fails, because it still points at the old hash of the third. To hide the change, the forger must fix the fourth block’s pointer, which changes its hash, which breaks the fifth, and so on: every block after the changed one must be made again.

Publishing the end

A chain that one person keeps can be rebuilt by that person. The fix is simple: copy the last hash somewhere they can’t change. Anyone who later checks the chain against that published hash will see any change made before it was published.

You have already used a hash chain: every commit in git (Unit 3) holds the hash of the commit before it, so a commit’s id fixes the whole history behind it.

What a blockchain adds

A blockchain is a hash chain with two more things:

1. Many copies, kept by strangers. Thousands of computers around the world each keep the whole chain and check every new block against the rules. Nobody needs to trust any one of them.
2. A rule for who adds the next block. With no owner, someone must decide which new block is accepted. In proof of work (Bitcoin’s rule), a block is accepted only with a number, a nonce, that makes its hash start with many zeros. The only way to find one is to try nonce after nonce, so adding a block costs a lot of computing, and rewriting old blocks would cost all that work again, faster than everyone else adds new ones.

import hashlib def mine(text, zeros):    """Find a number (a nonce) that makes the hash start with this many 0s."""    nonce = 0    while True:        h = hashlib.sha256(f"{nonce}:{text}".encode()).hexdigest()        if h.startswith("0" * zeros):            return nonce, h        nonce = nonce + 1 block = "prev=c74cae84538c; Jestha 20: Gita saves Rs 800"for zeros in range(1, 5):    nonce, h = mine(block, zeros)    print(f"{zeros} zeros: {nonce + 1:>9,} tries  {h[:16]}…") nonce, h = mine(block, 4)check = hashlib.sha256(f"{nonce}:{block}".encode()).hexdigest()print("Checking the answer takes 1 hash:", check.startswith("0000"))

1 zeros:         9 tries  0b186e71b4f9e260…2 zeros:        21 tries  0038dd1a39a50a86…3 zeros:     2,062 tries  000c89171e4c373e…4 zeros:   128,795 tries  000058929ce6adbd…Checking the answer takes 1 hash: True

Each extra zero makes the work about 16 times more on average (one hex digit has 16 values), though luck varies, as the 21 and the 128,795 show. Finding takes thousands of hashes; checking takes one. That is Unit 2’s gap between finding and checking again, used on purpose. Bitcoin sets the number of zeros so that the whole world’s miners, together, find one block about every ten minutes. Other blockchains use proof of stake instead: the next block is chosen from people who have locked up money in the system, which they lose if they cheat. It uses far less electricity.

What a blockchain doesn’t solve

• It can’t tell whether a record is true. A chain keeps a false record as faithfully as a true one. If a land office enters the wrong owner, the blockchain keeps the wrong owner forever.
• Mistakes can’t be undone. A payment to the wrong address, or to a scammer, stays paid. There is no bank to call.
• Whoever has the private key has the money. Lose the key, and the money is gone for good; let a scammer see it, and it is theirs.
• Everything on a public chain is public, forever, which clashes with privacy laws that let people have their data deleted.
• It is slow and costly. Thousands of copies and proof of work cost time and electricity. An ordinary database with signatures, backups and a published hash does most jobs far more cheaply.

So ask: who would we otherwise have to trust? If there is an organization people already trust to keep the record (a bank, a land revenue office, a school), a well-run database is better. A blockchain is worth its cost only when many parties who don’t trust each other must share one record, and no one can be put in charge of it.

In almost every real breach involving encryption, the mathematics held. What failed was how it was used: a key in the wrong place, a random number that wasn’t random, a check skipped. Here are the rules that defenders follow.

1. The method public, only the key secret. A system must stay safe even if the attacker knows exactly how it works; only the key may be secret. This is Kerckhoffs’s principle, which you met in Grade 9, set out in 1883 by Auguste Kerckhoffs, a Dutch-born teacher of languages in France. A “secret method” is found out sooner or later (programs can be read), and then every user is exposed at once; a leaked key can be replaced.
2. Never invent your own. Use a well-tested library (Grade 11 said the same for password hashes). Experts get wrong things that look simple: padding, the order of steps, how long a comparison takes.
3. Random numbers from a generator made for secrets: Python’s secrets, never random, whose numbers can be predicted from enough earlier ones (Grade 11 used secrets for salts and session IDs; the story below shows what bad randomness does to keys).
4. Keys never in the code. A key written into a program is in every copy of it, in every backup, and in the project’s history, often on a public website. Keep it in the server’s settings or a store made for secrets.
5. Check everything, every time: the signature, the certificate, the name, the date. Code that skips a check “for now, while testing” is often shipped that way.
6. Protect the private keys physically too. A root authority’s key is kept offline, in a locked room, inside a hardware security module, a device built to use the key without ever letting it out, and two people must be present to use it. A phone keeps your passkeys in a chip of its own.
7. Plan for change. Keys are replaced, sizes grow, methods are broken (MD5, SHA-1, now RSA by quantum computers in time). A system should be able to switch method without being rebuilt.

Measures and their trade-offs

Every measure in this unit protects something, and every one has a price, paid by the users, the data or the devices.

A school’s notices (exam dates, holidays, fee deadlines) are shared on a messaging group, and every year a fake one goes round: “School closed tomorrow.” Design and build a small fix with this unit’s tools, in Python, on a computer or on this page.

1. Keys. Make an RSA key pair for the school office from two primes you choose (use primes of four digits or more, so that n is bigger than your hashes cut down: say why). Publish the public key.
2. Sign. Write sign_notice(text) that signs a notice with the office’s private key, and check_notice(text, signature) that anyone can run with the public key. Show that changing one word of a notice makes the check fail.
3. Chain. Keep the notices in a hash chain, each block with its date, its text, its signature and the hash of the block before. Write check_board(chain) that reports the first broken link, if any.
4. Test. Run your checker on a good board, a board with one notice changed, a board with a notice signed by the wrong key, a board with an old notice sent again (a replay), and a board rebuilt by a forger. Which does your design catch? Fix the ones it misses (a date inside what is signed; the last hash read out at assembly).
5. Threat model. In half a page, as in Grade 11: what it protects, from whom, what it can’t do (a stolen private key; a true-looking notice from someone the office trusts), and what each defense costs the office and the students.
6. Real tools. Say which real, tested tools you would use instead of your toy keys if the school used it, and why your toy must not be used for real.