Show that if someone discovers the value of used in the ElGamal signature scheme, then can also be determined if is small.
Alice signs the hash of a message. Suppose her hash function satisfies and for all . Suppose is a valid signed message from Alice. Give another message for which the same signature is also valid.
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.
Alice uses RSA signatures (without a hash function).
Eve wants to produce Alice’s signature on the document . Why is this difficult? Explain this by saying what difficult cryptographic problem must be solved. (Do not say that it’s because Eve does not know the decryption exponent . Why isn’t there another way to produce the signature?)
Since part (a) is too hard for Eve, she decides to produce Alice’s valid RSA signature on a document so that the signature is (= Alice, when , , etc.). How does Eve find an appropriate message?
Nelson thinks he has a new version of the signature scheme. He chooses RSA parameters , , and . He signs by computing . The verification equation is .
Show that if Nelson correctly follows the signing procedure, or if he doesn’t, then the signature is declared valid.
Show that Eve can forge Nelson’s signature on any document , even though she does not know .
(The point of this exercise is that the verification equation is important. All Eve needs to do is satisfy the verification equation. She does not need to follow the prescribed procedure for producing the signature.)
Alice has a long message . She breaks into blocks of 256 bits: . She regards each block as a number between 0 and , and she signs the sum . This means her signed message is , where sig is the signing function. Is this a good idea? Why or why not?
Suppose that is a message signed with the ElGamal signature scheme. Choose with and let . Let .
Find a message for which is a valid signature.
This method allows Eve to forge a signature on the message . Why is it unlikely that this causes problems?
Let , , , and . Show that . This shows that the order of operations in the DSA is important.
There are many variations to the ElGamal digital signature scheme that can be obtained by altering the signing equation . Here are some variations.
Consider the signing equation . Show that the verification is a valid verification procedure.
Consider the signing equation . Show that the verification is a valid verification procedure.
Consider the signing equation . Show that the verification is a valid verification procedure.
Consider the following variant of the ElGamal Signature Scheme: Alice chooses a large prime , a primitive root , and a secret integer . She computes . The numbers are made public and is kept secret. If , Alice signs as follows: She chooses a random integer and computes , with , and . The signed message is . Bob verifies the signature by checking that . If , she breaks into blocks and signs each block.
Show that if Alice signs correctly then the verification congruence is satisfied.
Suppose Eve has a document and she wants to forge Alice’s signature on . That is, she wants to find and such that is valid. Eve chooses and tries to find a suitable . Why will it probably be hard to find ?
Suppose Alice has a very long message and wants to decrease the size of the signature. How can she use a hash function to do this? Explicitly give the modifications of the above equations that must be done to accomplish this.
The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose such that . Compute and .
Prove the claim that the pair is a valid signature for the message (of course, it is likely that is not a meaningful message).
Suppose a hash function is used and the signature must be valid for instead of for (so we need to have ). Explain how this scheme protects against existential forgery. That is, explain why it is hard to produce a forged, signed message by this procedure.
Alice’s RSA public key is and her private key is . Recall that a document with an RSA signature is valid if . Bob wants Alice to sign a document but he does not want Alice to read the document. Assume . They do the following:
Bob chooses a random integer with . He computes .
Alice signs by computing .
Bob divides by mod to obtain .
Show that is valid.
Why is it assumed that ?
Alice wants to sign a document using the ElGamal signature scheme. Suppose her random number generator is broken, so she uses in the signature scheme. How will Eve notice this and how can Eve determine the values of and (and thus break the system)?
Suppose Alice signs contracts using a 30-bit hash function (and is known to everyone). If is the contract, then is the signed contract (where sig is some public signature function). Eve has a file of fraudulent contracts. She finds a file with contracts with valid signatures (by Alice) on them. Describe how Eve can accomplish her goal of putting Alice’s signature on at least one fraudulent document.
In several cryptographic protocols, one needs to choose a prime such that is also prime. One way to do this is to choose a prime at random and then test for primality. Suppose is chosen to have approximately 300 decimal digits. Assume is a random odd integer of 300 digits. (This is not quite accurate, since cannot be congruent to 1 mod 3, for example. But the assumption is good enough for a rough estimate.) Show that the probability that is prime is approximately (use the prime number theorem, as in Section 9.3). This means that with approximately 345 random choices for the prime , you should be able to find a suitable prime .
In a version of the Digital Signature Algorithm, Alice needs a 256-bit prime and a 2048-bit prime such that . Suppose Alice chooses a random 256-bit prime and a random 1792-bit even number such that has 2048 bits. Show that the probability that is prime is approximately 1/710. This means that Alice can find a suitable and fairly quickly.
Consider the following variation of the ElGamal signature scheme. Alice chooses a large prime and a primitive root . She also chooses a function that, given an integer with , returns an integer with . (For example, for is one such function.) She chooses a secret integer and computes . The numbers and the function are made public.
Alice wants to sign a message :
Alice chooses a random integer with .
She computes .
She computes .
The signed message is .
Bob verifies the signature as follows:
He computes .
He computes .
If , he declares the signature to be valid.
Show that if all procedures are followed correctly, then the verification equation is true.
Suppose Alice is lazy and chooses the constant function satisfying for all . Show that Eve can forge a valid signature on every message (for example, give a value of and of and that will give a valid signature for the message ).
Alice wants to sign a long message that she has broken into blocks . She knows that signing each block individually is wasteful, so she computes and signs . Her signed message is . Suppose Eve has a message that Alice signed. How can Eve put Alice’s signature on fraudulent messages?
In some scenarios, it is necessary to have a digital document signed by multiple participants. For example, a contract issued by a company might need to be signed by both the Issuer and the Supervisor before it is valid. To accomplish this, a trusted entity chooses to be the product of two large, distinct primes and chooses integers with . The pair is given to the Issuer, the pair is given to the Supervisor, and the pair is made public.
Under the assumption that RSA is hard to decrypt, why should it be difficult for someone who knows at most one of to produce such that ?
Devise a procedure where the Issuer signs the contract first and gives the signed contract to the Supervisor, who then signs it in such a way that anyone can verify that the document was signed by both the Issuer and the Supervisor. Use part (a) to show why the verification convinces someone that both parties signed the contract.