# Elgamal security if same key used twice

Assume that user A sends to user B a message, unencrypted, and signs it with an Elgamal signature.

Can some adversary, call it C, who eavesdrops, learn the private key if user A signed both messages using the same random variable k? if so, how?

to sign the message, as far as i understood, a large prime p along with prime root a are selected, then selects a secret integer, let's call it z(private) so that $$b \equiv a^z(mod p)$$. then she selects some random integer k so that $$GCD(k,p-1)=1$$, and computes $$r \equiv a^k(modp)$$, and uses this to finally compute $$s \equiv k^{-1}(m-zr)(modp-1)$$

user b verifies it using $$v_1,v_2$$ so that $$v_1 \equiv b^rr^s(modp)$$ and $$v_2 \equiv a^m(modp)$$, and it is valid if and only if there's the following relationship: $$v_1 \equiv v_2(modp)$$

not sure on that, because if C eavesdrops he can get the signed message, i.e (m,r,s). now if A used the same random variable k, means that r remains the same. if r is the same, i think that it is problematic since for two messages, $$m_1,m_2$$ and their respective $$s_1,s_2$$: $$s_1k-m_1 \equiv s_2k-m_2mod(p-1) \equiv -zr$$, so if she looks at the following difference: $$m_1-m_2(modp-1) \equiv k(s_1-s_2)$$, but is it enough to know learn and deduct the private key k?

is there any other or smarter way for C to learn private key k?

would really appreciate your assistance with it. thank you very much

• In original ElGamal, the generator $a$ is a primitive root, meaning that $x\mapsto a^x\bmod p$ is a bijection on $[1,p)$; but there's no reason that $a$ is prime, as stated. The notation $b\equiv a^z\pmod p$ does not uniquely define $b$: it only means that $p$ divides $a^z-b$. The different notation $b=a^z\bmod p$ does define $b$, because it additionally means that $0\le b<p$. It would help to fix the question to use proper notation.
– fgrieu
Apr 21 '20 at 20:27