The National Bank of Crimea requires all members to conduct business on$-$line, and to

use El$-$Gamal signatures to close transactions. It published the following prime number p

and primitive root $g$ to be used in the signature algorithm:

$p=634404508895808192310313936486634711780110256438029402544697478374579200001$

$g=369453800891893802517289247828810138682703208596756001785976436264055339058$

Alice, one of the clients of National Bank of Crimea, published as her public signature

key the following

$b=206713254758099776851768543289940039539605032684783111021316389446087521630.$

Last Friday Alice received a letter from the bank that unless she pays the $$100$ she

promised to the bank, the bank will repossess her stereo system. Alice, surprised by the

request, asked the bank to provide proof that she owes the bank $$100.$ The bank

presented the following evidence:

Plaintext$=$"I will pay $$100$

$y=5823678520857072221167$

$s=$

$283153022158607625107842056887562165281621743987479476610628619918477927399$

$($a$)$ Determine whether $(y,s)$ is a valid signature for Alice's key. The answer must be

supported with a computational evidence.

A$.$ The signature is valid.

B$.$ The signature is not valid.

$($b$)$ Alice does not recall this promissory note, and decided to investigate further. She

asked her family member who works for the Digital Crimes Federal Bureau of

Investigation for help. This family member reported a few weeks later to Alice the following information: "The bank manager revealed that the discrete

logarithm of $y$ is $r=825693824659243777."$ Show how this information can be used

to generate a valid signature for Alice on the message "I will not pay $$100",$

without knowledge of Alice's private key.

Hint: Note that $M1=1$ will pay $$100$ and $M2=$I will not pay $$100$ are two diflerent messages. Use the

difference of $S1($signature on $M1)$ and $S2($signature on M$2)$ to show that one can generate a valid signature on

the message "I will not pay $$100"$ without knowing the private key.