Friday’s lecture (September 25th) is pre-recorded. Watch it before Monday:

• Video: Friday, September 25th lecture
• Notes: part 1 (the quadratic sieve, visually) and part 2 (signatures, RSA signatures, and cryptographic hash functions)
• These are also on the Notes/Videos page and the Archive.

Solutions: solutions to the daily posts due September 14th and 25th are now posted (Sep 14, Sep 25). All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

2.11 (Signature Schemes), 3.6.5 (RSA Signature).

To Do:

1. Watch the Friday, September 25th lecture (notes: part 1, part 2).
2. Fix integers $a$ and $b$ with $\gcd(a,b) = 1$, and suppose you have found integers $x, y$ with $ax + by = 1$ (for example, using the extended Euclidean algorithm). Explain why this single equation gives you both the inverse of $a$ modulo $b$ and the inverse of $b$ modulo $a$ at the same time. (Hint: reduce the equation modulo $b$, and then modulo $a$.)
3. Alice’s RSA key has $n = 3233 = 61 \cdot 53$ and $e = 17$. Find her private exponent $d$, sign the message $m = 65$, and then verify the signature as Bob. (The RSA Tools and other Sage functions may help.)
4. Using only Alice’s public key, pick any $s$ you like (say $s = 100$) and produce a message $m$ for which $s$ verifies as “valid”. Why doesn’t this worry Alice much in practice?
5. Alice has signed $m_1 = 65$ (signature $s_1 = 588$) and $m_2 = 42$ (signature $s_2 = 3065$). Without knowing $d$, produce a valid signature on $m_1 m_2 \bmod n$. Can you think of a way this could be exploited by an attacker? How would signing $h(m)$ instead of $m$ stop this attack?
6. Visit the Hash Tools page and make sure you understand what a hash function is and how to use the tools on this page.
7. Using the Hash Tools page, perform the SHA-256 hash on the string “friend” (try showing the digest both as hex and as bits). Then tick “Compare with a second message” and show the result in bits, change it to “fiend” (remove the r), and compare. Try some other pairs: united/untied, awesome/yuck, loooooooooong/short etc. How many of the 256 bits change? Is that what you’d expect?
8. For the checksum “hash” $h(m) = \sum \text{bits of } m \pmod 2$ from lecture, find a preimage of $0$, and find a collision with $m = 1010$.
9. How about another toy hash which XORs together all the 8-bit blocks of $m$ to produce a single 8-bit digest? Break that one too (preimage and collision). Does this toy hash have the avalanche effect?
10. Suppose you have a hash function that outputs $k$-bit digests. Roughly how many random messages must you hash before you expect two with the same digest (a collision)? (See the Birthday Paradox Demonstration.) What does this give for MD5 (outputs 128 bits) and for SHA-256 (outputs 256 bits)? Does the birthday trick help you find a preimage?