We have discussed two related cryptographic protocols in class: ElGamal encryption and ElGamal digital signatures. Both systems use the same type of public key, consisting of three numbers (g,y,p), where p is a prime number, g is a primitive root modulo p, and y is some number between 1 and p-1, inclusive. Call the owner of this public key Alice. Alice also knows a secret number a such that ga≡y mod p. The security of both systems (encryption and signing) depend on the fact that it is computationally difficult to solve the discrete logarithm problem, and therefore to reconstruct the value of a from the values of g and y (as long as p is sufficiently large). This problem demonstrates a potential security flaw in ElGamal signatures (if implemented poorly) that can all an eavesdropper to determine a, and hence crack any documents encrypted with Alice's public key.
In each test case, you will receive Alice's public key, as well as two signed messages from Alice. Each signed message consists of three integers (m,r,s). These three values obey the congruence gm ≡ yr rs mod p (the integrity of ElGamal signatures rests on the fact that it appears to be difficult to construct such numbers r,s for a fixed number m without knowledge of the secret number a). However, Alice has made a critical mistake while signing these two messages: she has used the same value of r in both signatures, rather than randomly generating a new one. There are some other restrictions on these values (described under "limits") that rule out certain special cases.
The last part of each test case will be an encrypted message (c_1,c_2) intended for Alice and encrypted by ElGamal encryption using her public key. This means that the sender, Bob, has taken his message D (intended for Alice), then chosen an "ephermal key" b at random and computed numbers c_1,c_2 such that c_1 ≡ gb mod p and c_2 ≡ yb D mod p.
Your task is to decrypt Bob's encrypted message and determine the original message D.
The first line gives the number of test cases, T. T test cases follow. Each case consists of four lines, of the following form.
g y p
m_1 r s_1
m_2 r s_2
c_1 c_2
The first line is Alice's public key. The next two lines are two signed messages from Alice (note that they use the same value of r). The last line is an encrypted message intended for Alice.
For each test case, print a single line of the form Case #X: D, where X is the number of the test case and D is the original document that was encrypted by Alice's public key to obtain c_1,c_2.
Small dataset:
p ≤ 106
Large dataset:
p ≤ 1018
| Input | Output |
|
4 2 3 11 9 7 9 0 7 2 3 4 2 14 19 17 5 0 9 5 13 2 11 3 6 7 2 5 1 1 5 2 5 2 126790149156457136 378226232119944922 670047060771582503 161454713220583839 163319352577255097 214573064171043578 324219902194752697 163319352577255097 163882212182317851 551173770507958840 593354389584354105 |
Case #1: 3 Case #2: 13 Case #3: 5 Case #4: 155949289230828270 |
It is possible to solve the small input without using the signed messages at all -- simply determine the exponent a by trial and error, and then follow the procedure from the homework to decrypt the message D from it.
To solve the large input, you will need to use the signed messages from Alice. One good method is to let e be a number such that ge ≡ r mod p. Using the fact that g is a primitive root, you can write down two congruences modulo p-1, involving both of the exponents a and e. You can manipulate these congruences in order to determine both of the values a and e (follow a similar method to when you solve a pair of linear equations). Then you can descrypt the message using the number a.