find $a$ and $k$ for a given el gamal cryptosystem

Question

I am given this question:

Suppose Alice is using the ElGamal Signature scheme with parameters

$p = 31847$, $\alpha = 5$, and $\beta = 25703$

Assuming that we have received signed messages

$(x_1,(\gamma_1,\space \delta_1)) = (8990, (23972,\space 31396))$

and

$(x_2,(\gamma_2,\space \delta_2)) = (31415,(23972,\space 20481))$

determine integers $k$ and $a$ that Alice has used without solving any instance of discrete logarithm problem.

I also know from my lecture slides that the following equations are true

1. $\beta = a^\alpha \bmod p$

2. $\gamma = a^k \bmod p$

3. $a\gamma + k\delta = x \bmod p-1$

Since the question specifies not to use the discrete log problem, we can only use equation 3

so we have a system of two equations:

1. $a\gamma_1 + k\delta_1 = x_1 \bmod p-1 \rightarrow a(23972) + k(31396) = 8890 \bmod (31846)$

2. $a\gamma_2 + k\delta_2 = x_2 \bmod p-1 \rightarrow a(23972) + k(20481) = 31415 \bmod (31846)$

solving for $k$ is simple enough, just take 1. - 2. as equation 3. below:

3. $k(10915) = -22425 \bmod(31846) = 9421 \bmod(31846)$

and solve for $k$:

$k = 1165 \bmod(31846)$

Now here's where I'm getting stuck, by plugging in $k$ to equation 2. we get:

$a(23972) + (1165)(20481) = 31415 \bmod 31846 \rightarrow a(23972) = (23704) \bmod 31846$

but we can't isolate $a$ because the $\text{gcd}(23972, 31846) > 1$ so there is no inverse of $23972 \bmod 31846$

note plugging $k$ into equation 3. gets a similar result.

This question is from my textbook so it should be solvable, but the math is telling me that it's not solvable.

Could someone please explain if there is some work around to finding $a$ when it is multiplied by a non-invertable number?

Answer 1

I found the answer after getting a hint from my professor

basically if we have an equation in to form

$$m*x = (m*y) mod (m*z)$$
we can factor out m such that:
$$x = (y) mod (z)$$

but... the only caveat is that there are m solutions for x: $$ x, x+z, x+2*z, ..., x+(m-1)z = (m*y) mod (m*z) $$ using this we can solve the equation in the question $$a(23972)=(23704) mod (31846)$$
even though 23972 is not invertable mod 31846.

start by factoring out 2 from everything
$$2a(11986) = 2(11852) mod 2(15923)$$

this gives:
$$ a(11986) = 11852 mod 15923 $$

solving for a: $$ a = (11852)(11986)^{-1} mod 15923 = (11852)(182) mod 15923 = 7459 mod 15923 $$ now the multiple solution part:

where $$m = 2$$ and $$z = 15923$$ in our case

a = 7459 mod mz and 7459 + z mod mz

so $$a = (7459) mod (31846), (23382) mod (31846)$$ and $$k = (1162) mod (31846)$$