Introduction to Cryptography with Coding Theory, 3rd Edition

13.6 Exercises

1. Show that if someone discovers the value of $k$ used in the ElGamal signature scheme, then $a$ can also be determined if $gcd(r\text{,}p-1)$ is small.

2. Alice signs the hash of a message. Suppose her hash function satisfies $h(x)\equiv 2^x(\mathrm{m}\mathrm{o}\mathrm{d}101)$ and $1\le h(x)\le 100$ for all $x$. Suppose $m$ is a valid signed message from Alice. Give another message $m_1$ for which the same signature is also valid.

3. Alice says that she is willing to sign a petition to save koala bears. Alice’s signing algorithm uses a hash function that has an output of 60 bits (and she signs the hash of the document). Describe how Eve can trick Alice into signing a statement allowing Eve unlimited withdrawals from Alice’s bank account.

4. Alice uses RSA signatures (without a hash function).