Introduction to Cryptography with Coding Theory, 3rd Edition

13.7 Computer Problems

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

   $(809\text{,}18357\text{,}1042)\text{ (= hi) and }(22505\text{,}18357\text{,}26272)\text{ (= bye).}$

   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)$.

2. Alice and Bob have the following RSA parameters:

   $$\begin{array}{ccc}{n}_A& =& 171024704183616109700818066925197841516671277\text{,}\\ n_B& =& 839073542734369359260871355939062622747633109\text{,}\\ \begin{array}{cc}\begin{array}{ccc}{e}_A& =& 1571\text{,}\end{array}& \begin{array}{ccc}{e}_B& =& 87697.\end{array}\end{array}\end{array}$$

   Bob knows that

   $p_B=98763457697834568934613\text{,}{q}_B=8495789457893457345793$

   (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 ...