= Solution
In the <RSA cryptosystem>, choose distinct large <prime numbers> $p,q$, set $N=pq$, and choose $e$ <coprime> to $\varphi(N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv1\pmod{\varphi(N)}$. A plaintext <residue class> $m$ is encrypted as $c=m^e\pmod N$ and decrypted as $c^d\pmod 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_1m_2)=E(m_1)E(m_2)\pmod 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 set
$$
\boxed{r=g^k\pmod p,\qquad s=k^{-1}(h-ar)\pmod{p-1}.}
$$
Verification checks $1\leq r\leq p-1$ and $g^{H(m)}\equiv y^r r^s\pmod p$, which follows because $ar+ks\equiv h\pmod{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.
Back to article page
