Insecure primitive elements in an ElGamal signature protocol
This work addresses a security flaw in cryptographic protocols, specifically for users of ElGamal signatures, by demonstrating an incremental extension to a known attack.
The authors tackled the vulnerability of the classical ElGamal digital signature scheme by proving that if a natural integer i can be computed such that α^i mod p is smooth and divides p-1, then an attacker can sign any document without the secret key, extending and reinforcing Bleichenbacher's attack from Eurocrypt'96.
Consider the classical ElGamal digital signature scheme based on the modular relation $α^m\equiv y^r\, r^s\ [p]$. In this work, we prove that if we can compute a natural integer $i$ such that $α^i\ mod\ p$ is smooth and divides $p-1$, then it is possible to sign any given document without knowing the secret key. Therefore we extend and reinforce Bleichenbacher's attack presented at Eurocrypt'96.