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.

A digital signature lets a holder of a private key authenticate a message while anyone with the public key verifies it. Signing a message digest ties the signature to the message and detects alterations; it does not conceal the message. Authentication also requires a trustworthy association of the public key with its owner.

For the ElGamal signature scheme, choose a large prime $p$ and a generator $g$ of ${\mathbb{F}}_p^{\times }$. The secret is $x$, and the public key is $(p,g,y)$ with $y=g^x\mathrm{mod}p$. To sign a message whose hash is represented by $m\mathrm{mod}(p-1)$, choose a fresh secret nonce $k$ coprime to $p-1$ and setTransmit $(r,s)$ with the message. Verification checks the permitted ranges and $\boxed{g^m\equiv y^r{r}^s(\mathrm{mod}p)}$. Correctness follows from $xr+ks\equiv m(\mathrm{mod}p-1)$. The secret exponent prevents an outsider from directly constructing this relation for an arbitrary hashed message; nonce reuse can expose the exponent through the repeated linear congruences. Hashing is part of the signature scheme, rather than signing arbitrary raw exponents with no message encoding.

A digital signature lets the holder of a private key authenticate a message so that anyone with the corresponding trusted public key can verify its origin and integrity. The signature does not conceal the message. Public-key certification, a suitable message hash and protection of the signing key are needed for that interpretation.

For the ElGamal signature scheme, choose a large prime $p$ and a primitive root $g$ modulo $p$. The secret key is $x$, and the public key is $(p,g,y)$ with $y=g^x\mathrm{mod}p$. Represent the message by a hash $m$ modulo $p-1$. Choose a fresh secret nonce $k$ coprime to $p-1$ and setThe signature is $(r,s)$. After checking the prescribed ranges, the verifier accepts whenA genuine signature passes because $xr+ks\equiv m(\mathrm{mod}p-1)$. The security aim is that someone without $x$ cannot efficiently produce a valid signature on a new authenticated message. Nonce secrecy and freshness matter: reuse gives linear congruences relating two message hashes, the nonce and the secret key. Signing unhashed arbitrary messages also permits algebraic forgeries, so the hash is part of the practical scheme.

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.