ElGamal Digital Signature Scheme question

Question

Use the ElGamal Digital Signature Scheme in the group $G$ = $F^{×}_{p}$ = <g> where $p$ = $479$ is prime and $g$ = $13$. Your secret signing key is $x = 300$. If you choose an ephemeral key k = 11, what is the signature of your message m = 379?

I followed these steps and thought I had done nothing wrong but when I checked my answer by trying to verify, it was wrong.

First of all, I worked out $r ≡ g^{k}$ (mod $p$) by fast modular exponentiation to get $r ≡ 237$.

Next, I worked out $m ≡ xr + ks$ (mod $p-1$) and plugged in numbers to get
$379 ≡ 300 * 237 + 11s$ (mod $478$), which rearranged to
$11s ≡ 23$ (mod $478$)

I used Euclid's Algorithm to find the inverse of $11$, which I got as $89$, which meant
$s ≡ 89 * 23 ≡ 135$ (mod $478$) was the signature, or I thought was the signature.

When I went to verify my answer by working out $g^{m}$ (mod $p$) and $y^{r} * r^{s}$ (mod $p$),
(I had already worked out the public key $y ≡ g^{x}$ (mod $479$) before and it was $168$)
I expected to get the same number however I got $13^{379} ≡ 370$ (mod $479$) and $168^{237}$ * $237^{135} ≡ 357$ (mod $479$), which meant my signature was wrong.

Can anyone see an error I made?

Answer 1

The value of $s$ that satisfies $$ 379 = 300\cdot 237 + 11\cdot s\mod 478 $$ is $s=89$, as computed. (And not $89\cdot 23$.)

Using the wiki terminology we now have: $$ \begin{aligned} p &= 479 &&\text{chosen prime}\\ F &= \Bbb F_p &&\text{associated field for algebraic computations}\\ G &= \Bbb F_p^\times &&\text{associated group for algebraic computations}\\ A &= \Bbb Z/(p-1) &&\text{additive group with same structure as $G$}\\ &&& \text{via }A\to G\ ,\ a\to g^a\text{ isomorphism}\\ |F| &= p = 479\\ |G| &= p-1 = 478\\ x &= 300\in \Bbb Z &&\text{chosen private key, we may see $x\in A$}\\ y &= g^x=168\in G\subset F &&\text{resulted public key}\\ m &= 379\in\Bbb Z &&\text{message}\\ H(m) &= 379\in A &&\text{message $m$ seen in $A=\Bbb Z/(p-1)$, by using the} \\ &&&\text{cryptographic hash $H$, passing modulo $(p-1)$}\\ k &= 11\in\Bbb Z &&\text{chosen random ephemeral, we may see $k\in A$}\\\\ r &= g^k=237\in G\subset F &&\text{and we must chose a lift}\\ r &= 237\in\Bbb Z\\ s &= (H(m) -xr)k^{-1}&&=89\in A\\ (r,s)&=(237, \ 89)\in\Bbb Z\times A&&\text{the final signature} \end{aligned} $$ To verify the signature, we have to check the relation: $$ g^{H(m)} = y^r\; r^s\qquad\text{ in }G\subset F=\Bbb F_p\ . $$ And in our case, working in the field $F=\Bbb F_p$ we have

• $g^{H(m)}=g^m=13^{379}=370\in G\subset F$,
• $y^r\; r^s=168^{237}\cdot 237^{89}=233\cdot 201 =370\in G\subset F$ .