We can use a similar hybrid approach to make digital signatures efficiently This

Question

We can use a similar hybrid approach to make digital signatures efficiently This approach combines RSA with a public collision-resistant hash function h-a function that is easy to compute but for which it is computationally infeasible to find two messages M and M' such that h(M) - h(M'). The value h(M) is a short (say, 256-bit) "fingerprint" of the message M. If Alice wishes to sign a message M, she first applies h to M to obtain the fingerprint h(M), which she then encrypts with her secret key. She sends (M, SA (h(M))) to Bob as her signed version of M. Bob can verify the signature by computing h(M) and verifying that PA applied to SA(h(M)) as received equals h(M). Because no one can create two messages with the same fingerprint, it is computationally infeasible to alter a signed message and preserve the validity of the signature Finally, we note that the use of certificates makes distributing public keys much easier. For example, assume there is a "trusted authority" T whose public key is known by everyone. Alice can obtain from T a signed message (her certificate) stating that "Alice's public key is PA." This certificate is "self-authenticating" since everyone knows Pr. Alice can include her certificate with her signed messages, so that the recipient has Alice's public key immediately available in order to verify her signature. Because her key was signed by T, the recipient knows that Alice's key is really Alice's

Explanation / Answer

A hash function maps bit strings of arbitrary finite length to bit strings of fixed length (n bits) many-to-one mapping - collisions are unavoidable however, finding collisions are difficult - the hash value of a message can serve as a compact representative image of the message (similar to fingerprints).

compression

– by definition ease of computation

– given an input x, the hash value h(x) of x is easy to compute weak collision resistance (2nd preimage resistance)

– given an input x, it is computationally infeasible to find a second input x’ such that h(x’) = h(x)

strong collision resistance (collision resistance)

– it is computationally infeasible to find any two distinct inputs x and x’ such that h(x) = h(x’)

one-way hash function (preimage resistance)

– given a hash value y (for which no preimage is known), it is computationally infeasible to find any input x s.t. h(x) = y

weak collision resistance

– assume that the hash-and-sign paradigm is used

– signed message: ( m, B(h(m)) )

– if an attacker can find m’ such that h(m’) = h(m), then he can forge a signed message ( m’, B(h(m’)) ) = ( m’, B(h(m)) )

strong collision resistance

– the same setup as above but assume that the attacker can choose the message that B signs

– now it is enough to find a collision pair (m, m’)

– the attacker obtains the signature B(h(m)) on m from B and claims that m’ has been signed by presenting ( m’, B(h(m)) )

one-way property

– RSA signature on y is yd mod n

– the attacker chooses a random value z and computes y = ze mod n

– if the attacker can find an x, such that h(x) = y, then he can forge a signed message ( x, (h(x))d mod n ) = ( x, z )

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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