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

  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Apr 21 '20 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.