In the basic EIGamal and RSA signature schemes, it is easy to create valid messa

Question

In the basic EIGamal and RSA signature schemes, it is easy to create valid message-signature pairs provided we do not need to specify the message ahead of time. By incorporating a hash function, we can prevent this type of forgery: the goal of this problem is to explore how. Suppose Alice has an RSA public signature key (N, e). If Eve chooses a random z modulo N, show that if omega equivalence z^e (mod N) then z is a valid signature on the message omega. Now suppose Alice instead uses a hash function H and signs H(m) rather than m itself: thus, the signature s on the message m instead satisfies s^e equivalence H(m) (mod N). Explain why Eve's procedure from part (a) is no longer effective at producing a forged signature. Suppose Alice has an EIGamal public signature key (p, a. b). If Eve chooses random units x and y modulo p - 1, sets r = a^xb^y (mod p), and s = -ry^-1 (mod p - 1), show that the pair (r, s) is a valid signature on the message omega equivalence sx (mod p - 1). Now suppose Alice instead uses a hash function H and signs H(m) rather than m itself: thus, the signature (r, s) on the message m instead must satisfy b^rr^s equivalence a^H(m) (mod p). Explain why Eve's procedure from part (c) is no longer effective at producing a forged signature.

Explanation / Answer

Alice’s changes are in no way sufficient to secure the system; anything encrypted with a key selected in this way can be decrypted in a matter of minutes. This is because the SHA-1 hash is computed over only four bytes, resulting in only about four billion possible keys. The most straightforward way to attack this system is to try each of the 232 possible values for x in turn, each time using SHA-1 to hash x then attempting decryption with that key. This is possible regardless of how Alice has set her computer’s clock or how it chooses process ID’s. If an attacker can somehow derive or narrow down the possible settings for Alice’s clock (e.g., using a separate protocol from the one being attacked), they could speed up the attack somewhat, but it may not be worth bothering since the set of possible keys is so small already

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.