Exam practice

• Modulus: the number you divide by in modular arithmetic; only the remainder is kept (in 17 mod 5 = 2, the modulus is 5).
• Inverse mod n: the number that, multiplied by a given number, gives 1 mod n; multiplying by it undoes multiplying by the first (7 × 23 = 161 ≡ 1 mod 40, so 23 is the inverse of 7 mod 40).
• Key pair: two keys made together, a public key given to everyone and a private key kept by its owner; what one does, only the other undoes.
• Padding: fresh random data mixed with a message before it is encrypted, so the same message never gives the same ciphertext.
• Discrete logarithm: finding a from gᵃ mod p; no fast method is known for large primes, which keeps key exchange safe.
• Digital signature: a value made from a message’s hash with a private key, which anyone can check with the public key; it proves who signed and that the message is unchanged.
• Certificate: a message saying “this public key belongs to this name”, signed by a certificate authority.
• Hash chain: records in blocks, each holding the hash of the block before, so a change to any record breaks the link after it.

13 = 8 + 4 + 1, so 3¹³ = 3⁸ × 3⁴ × 3¹.

• 3¹ ≡ 3
• 3² = 9 ≡ 2
• 3⁴ ≡ 2² = 4
• 3⁸ ≡ 4² = 16 ≡ 2

3¹³ ≡ 2 × 4 × 3 = 24 ≡ 3 (mod 7). (Check: 3¹³ = 1,594,323 = 227,760 × 7 + 3.)

• n = 5 × 11 = 55; φ(n) = 4 × 10 = 40.
• e = 3 shares no factor with 40. d is the inverse of 3 mod 40: 3 × 27 = 81 = 2 × 40 + 1, so d = 27.
• Public key (55, 3); private key (55, 27).
• Encrypt: c = 8³ mod 55 = 512 mod 55. 9 × 55 = 495, so c = 17.
• Decrypt: 17²⁷ mod 55. Squaring: 17² = 289 ≡ 14; 17⁴ ≡ 14² = 196 ≡ 31; 17⁸ ≡ 31² = 961 ≡ 26; 17¹⁶ ≡ 26² = 676 ≡ 16. 27 = 16 + 8 + 2 + 1, so 17²⁷ ≡ 16 × 26 × 14 × 17. 16 × 26 = 416 ≡ 31; 31 × 14 = 434 ≡ 49; 49 × 17 = 833 ≡ 8. The message comes back.

• Sita sends A = 5⁶ mod 23. 5² = 25 ≡ 2; 5⁴ ≡ 4; 5⁶ = 5⁴ × 5² ≡ 4 × 2 = 8.
• Ram sends B = 5¹⁵ mod 23. 5⁸ ≡ 4² = 16; 5¹⁵ = 5⁸ × 5⁴ × 5² × 5 ≡ 16 × 4 × 2 × 5 = 640 = 27 × 23 + 19, so B = 19.
• Sita: Bᵃ = 19⁶ mod 23. 19 ≡ −4; (−4)⁶ = 4,096 = 178 × 23 + 2, so 2.
• Ram: Aᵇ = 8¹⁵ mod 23. 8 = 2³, so 8¹⁵ = 2⁴⁵; 2¹¹ = 2,048 = 89 × 23 + 1, so 2⁴⁵ = (2¹¹)⁴ × 2 ≡ 2. Both get the shared key 2.

Eve sees 23, 5, 8 and 19. She must find a secret, for example the a with 5ᵃ ≡ 8 (mod 23), by trying powers of 5 (the discrete logarithm problem), then work out 19ᵃ. With p = 23 that takes at most 22 tries; with a prime hundreds of digits long it is out of reach.

Signing (Ram): hash the message (SHA-256) and turn the hash into a number h below n; work out s = hᵈ mod n = h²⁷⁵³ mod 3233 with the private key; send the message with s.
Checking (Sita): hash the message she received the same way, giving h′; work out sᵉ mod n = s¹⁷ mod 3233 with Ram’s public key; the signature is good if this equals h′.
A good result proves that the message was signed with the private key matching (3233, 17), and that not one character has changed since. It doesn’t prove that Ram himself holds that key (a certificate or a meeting in person ties the key to Ram), that the key wasn’t stolen, that the message is true, or that this isn’t an old message sent again.

1. The server sends its certificate chain: its own certificate (its name and public key, signed by an issuing authority) and the authority’s certificate (signed by a root).
2. The app checks each signature up the chain to a root in its trusted list, that the name is the wallet’s name, and that the dates are right. Needed so that the public key really belongs to the wallet.
3. App and server do a key exchange with fresh secret numbers. Needed to agree on a shared key that nobody listening can work out, and fresh each time for forward secrecy.
4. The server signs its key-exchange number with the private key matching its certificate, and the app checks it. Needed to stop a man in the middle, who could otherwise do the key exchange in the server’s place.
5. Everything after is encrypted with a fast symmetric cipher using the shared key, with a check that each message hasn’t been changed. Needed because public-key operations are too slow for all the data.

It would help with: records can’t be changed quietly after they are entered (each change would break the chain, and many copies hold the old hashes); and there is a clear, checkable history of every transfer.
It wouldn’t help with: a false or mistaken record entered in the first place (by a corrupt or careless official, or with forged papers) stays forever; it can’t check who really occupies the land; it makes honest corrections harder; and if the keys used to approve transfers are stolen, the thief’s transfers are just as permanent.
Advice: the municipality is already the trusted keeper, so a well-run database with signed entries, backups in several places, audit logs, and the latest hash published regularly (on its website and in a newspaper) gives the same protection against quiet changes, far more cheaply. The real fraud risks are at the counter, where documents are checked, and need better procedures there. (Answers that recommend a blockchain must say who keeps the copies and why the parties can’t trust one keeper.)

Line 3 accepts any notice that comes with no signature at all. The signature check on line 4 is only ever reached when a signature is sent, so a forger doesn’t need to beat it: a fake “School closed tomorrow” sent without a signature is shown as if it came from the office. A check that can be skipped by leaving something out is no check. Fix: refuse what isn’t signed (and have the office sign the older notices again, or show them marked “not signed”).

import hashlib N, E, D = 3233, 17, 2753                     # the office's key pair (from 61 and 53) def digest(text):    return int(hashlib.sha256(text.encode()).hexdigest(), 16) % N def accept(notice, signature):    if signature is None:        return False         # no signature, no trust    return pow(signature, E, N) == digest(notice) notice = "Exams start on Magh 10."print(accept(notice, pow(digest(notice), D, N)))   # signed by the officeprint(accept("School closed tomorrow.", None))      # not signed

TrueFalse

A good answer also says that the signed text should include the date, so that an old notice can’t be sent again (a replay).

Textbook RSA always turns the same message into the same ciphertext. Nobody can decrypt, but anyone can see which ciphertexts are equal, and anyone can encrypt a guess with the public key and compare. In the picture, every sky square encrypted to 1,096 and every snow square to the same number, so the encrypted picture still showed the mountain. Padding mixes fresh random data with each message before encrypting (here 16r + m with a random r), so equal messages give different ciphertexts and the encrypted picture became noise; the owner removes the padding after decrypting (here, the remainder by 16).

• i.End-to-end encryption protects messages from everyone between the two phones, including the company; the cost is that a lost phone without a backup loses the messages, and the company can’t help recover them or check them for abuse.
• ii.Passkeys protect against phishing and stolen password lists; the cost is needing a device that supports them, and a recovery plan if it is lost.
• iii.Proof of work protects a shared record from being rewritten; the cost is a great deal of electricity and slow confirmation.
• iv.An offline root key in an HSM protects the key every certificate depends on; the cost is money, slowness (each use needs people present), and trust in those people.