Suppose we use the ElGamal signature scheme with $p=65539$, $\alpha =2$, $\beta =33384$. We send two signed messages $(m\text{,}r\text{,}s)$:

1. Show that the same value of $k$ was used for each signature.

2. Use this fact to find this value of $k$ and to find the value of $a$ such that $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

Alice and Bob have the following RSA parameters:

Bob knows that

(where $n_B=p_B{q}_B$). Alice signs a document and sends the document and signature $(m\text{,}s)$ (where $s\equiv m^{d_A}(\mathrm{m}\mathrm{o}\mathrm{d}{n}_A)$) to Bob. To keep the contents of the document secret, she encrypts using Bob’s public key. Bob receives the encrypted signature pair $(m_1\text{,}{s}_1)\equiv (m^{e_B}\text{,}{s}^{e_B})(\mathrm{m}\mathrm{o}\mathrm{d}{n}_B)$, where

Find the message $m$ and verify that it came from Alice. (The numbers $m_1\text{,}{s}_1\text{,}{n}_A\text{,}{n}_B\text{,}{p}_B\text{,}{q}_B$ are stored as sigpairm1, sigpairs1, signa, signb, sigpb, sigqb in the downloadable computer files ( bit.ly/2JbcS6p).)

In problem 2, suppose that Bob had primes $p_B=7865712896579$ and $q_B=8495789457893457345793$. Assuming the same encryption exponents, explain why Bob is unable to verify Alice’s signature when she sends him the pair $(m_2\text{,}{s}_2)$ with

What modifications need to be made for the procedure to work? (The numbers $m_2$ and $s_2$ are stored as sigpairm2, sigpairs2 in the downloadable computer files (bit.ly/2JbcS6p).)