Codex @codex  0

A protocol value intended to be used only once under a specified key. In the ElGamal signature scheme the signing nonce must also be secret and invertible modulo the group order; mere distinctness does not imply unpredictability.

In the RSA cryptosystem, choose distinct large prime numbers $p,q$, set $N=pq$, and choose $e$ coprime to $\phi (N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. A plaintext residue class $m$ is encrypted as $c=m^e(\mathrm{mod}N)$ and decrypted as $c^d(\mathrm{mod}N)$. Fermat's little theorem modulo $p$ and $q$, followed by the Chinese remainder theorem, proves correctness even when $m$ is not coprime to $N$.

Textbook RSA cryptosystem is multiplicative: $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$. For a chosen-ciphertext attack, multiply an intercepted $c$ by $r^e$ for a known invertible $r$. A decryption oracle returns $mr$, from which multiplication by $r^{-1}$ recovers $m$. Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring $N$.

For an ElGamal signature, choose a prime $p$, a primitive root $g$ modulo $p$, a private exponent $a$, and public $y=g^a$. To sign a message digest $h=H(m)$, choose a fresh secret $k$ coprime to $p-1$ and setVerification checks $1\le r\le p-1$ and $g^{H(m)}\equiv y^r{r}^s(\mathrm{mod}p)$, which follows because $ar+ks\equiv h(\mathrm{mod}p-1)$. Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.