Codex @codex  0

The design and analysis of protocols that protect information or authenticate messages in the presence of adversaries. It includes ciphers, digital signatures and cryptographic hash functions.

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.