Suppose that Alice Bob and participate in an signature schem

Suppose that Alice, Bob and participate in an signature scheme. They all use the prime p = 1154299 and primitive element alpha = 3. The public keys (i.e., value of beta, where beta identical alpha^a (mod p), and a is secret) are: Alice: 569948 Bob: 813528 Carol: 935267. suppose that the massage m = 9528s has been signed by one of Alice, Bob or Carol. The signature is (925720, 1054736). Determine which of the three signed the message. And why it is that person.

Solution

Assume that Alice has an El-Gamal key for which the public part is (g, b, P),
and the private part is the number a. Recall:
• P is a prime number.
• 1 < g < P is a primitive root of P.
• b = ga mod P.
Typically there would also be a hash-function H involved in digitally sign-
ing a message M with an El-Gamal signature. One would first compute H(M),
the hash of the message, and then digitally sign the hash. For purposes of ex-
position, we may denote the quantity (whether it be the hash or just the raw
message) which will be signed also by M. The M we sign must be less than P.
We describe here how a message M would be signed, assuming that M < P.
Signature algorithm
• Select randomly a number r < P 1 such that gcd(r, P 1) = 1.
• Compute y = gr mod P.
• Compute s = (M ay)(r1) mod (P 1).
Alice’s El-Gamal signature on M is (y, s).
Verification algorithm
The verifier knows the following things: Alice’s public key (g, b, P), the message
M and presented signature (y, s). The verifier does NOT know Alice’s private
key A and the random number r chosen by Alice.
The verifier now computes:
• V1 = ys · by P.
• V2 = gM mod P.
If V1 = V2, and if y, s < P, then the signature (y, s) is accepted as Alice’s;
otherwise, the signature is not accepted.