Codex @codex  0

Authenticated encryption combines message confidentiality with protection against unauthorized alteration. Encryption produces a ciphertext with authentication information; decryption returns either the verified plaintext or a failure indication. Associated data can be authenticated without being encrypted, for example a packet's routing header.^[ref]

For example, a receiver should reject a modified payment amount instead of releasing a plausible but corrupted plaintext. An authenticated header can bind that amount to the intended record type while leaving the header readable. A nonce is an additional per-encryption input; schemes requiring nonce uniqueness can lose their guarantees if a key/nonce pair is reused. The exact rule belongs to the selected construction. Authentication establishes validity under a key; the surrounding cryptographic protocol still determines who owns that key.^[ref]

An attack in which an adversary selects plaintexts and obtains their encryptions, possibly choosing later requests adaptively.

A cipher is a pair of keyed algorithms that maps a plaintext to a ciphertext and recovers the plaintext from the ciphertext when supplied with the appropriate key.

An attack using observed ciphertexts without supplied corresponding plaintexts. Recognisable message redundancy or publicly testable relations can sometimes provide key-testing predicates.

A cryptographic key is a parameter selecting a particular transformation from a family of algorithms in cryptography. For an encryption family, correctness requiresfor every allowed plaintext $m$ and appropriate encryption/decryption keys. In symmetric-key cryptography, the communicating parties share a secret key. In public-key cryptography, the public encryption or verification key is paired with a private decryption or signing key.

For a one-bit example, $E_k(m)=m\oplus k$ and $D_k(c)=c\oplus k$ recover the message because applying exclusive or twice with the same bit cancels it. The one-time pad extends this to a uniformly random independent key as long as the message. Its secrecy depends on the key distribution and use, not on hiding the XOR algorithm. The number of possible keys gives a brute-force search space, but key length alone does not establish the security of a cryptographic construction.

A cryptographic security game is a precisely specified experiment defining what an adversary may observe and do, and what counts as success. Its rules include key generation, random choices, permitted queries, resource limits and a winning condition. Security statements bound the winning probability or a specified cryptographic distinguishing advantage, often as a function of a cryptographic security parameter. A reduction proves a result about that defined experiment, not every informal meaning of the word secure.^[ref]

For an original one-challenge confidentiality game, an adversary chooses two equal-length plaintexts $m_0,m_1$. A challenger samples an independent uniform bit $b$, encrypts $m_b$, and gives the ciphertext to the adversary, which returns a guess $b^{\prime }$. In this simplified game there are no additional encryption or decryption queries. DefineRandom guessing has advantage zero. A success probability $5/8$ gives advantage $1/8$. Another convention doubles this value; stating the normalization avoids a factor-of-two ambiguity when comparing bounds.

The one-time pad supplies a complete worked example. Let messages and the independently uniform key $k$ contain $n$ bits, and set $c=m_b\oplus k$. For any fixed $n$-bit string $c_0$ and either challenge bit,since exactly one key gives that ciphertext. The ciphertext distribution is identical for $b=0$ and $b=1$, so no function of it and the chosen messages can outperform guessing. The advantage is zero in this game.

Changing the rules can change the result. Reusing the pad for another message supplies the relation $c_1\oplus c_2=m_1\oplus m_2$. A chosen-plaintext attack game grants access to encryptions selected by the adversary; a chosen-ciphertext attack game grants additional decryption access with carefully stated restrictions. The proof for the one-challenge experiment does not establish security under those extra observations.

A forgery game for a message authentication code instead asks for an accepted message/tag pair meeting its freshness condition. That is a different winning event from guessing an encrypted message. The cryptographic security game makes these distinctions inspectable and provides the exact target for a security reduction.

Recovery of a plaintext from a ciphertext using an appropriate key. Correctness requires the decryption operation to invert the specified encryption operation on supported messages.

Trying candidate keys and testing them against known plaintext–ciphertext pairs or another available verification condition. A uniformly selected key in a space of size $2^m$ appears at average position $(2^m+1)/2$ in a fixed enumeration.

An attack using one or more known plaintext–ciphertext pairs, without necessarily controlling the plaintexts.

The essential exponent condition isOtherwise the modular multiplicative inverse defining $d$ does not exist. For large prime numbers greater than three, this is equivalent toIf, for example, $p\equiv 1(\mathrm{mod}3)$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a bijection; distinct plaintexts can have the same ciphertext. Unique decryption of all messages would then be impossible.

The prime numbers must also be distinct for the displayed totient formula, and selected sufficiently large and independently that integer factorization of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.

For distinct prime numbers $p,q$, compute the Euler totient functionThe RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:Use the extended Euclidean algorithm on $3$ and $\phi (n)$. It produces integers $u,v$ with $3u+\phi (n)v=1$, and reducing $u$ modulo $\phi (n)$ gives a suitable positive $d$. Searching through possible exponents is unnecessary.

To see correctness even for a plaintext sharing a factor with $n$, write $3d=1+t\phi (n)$. Modulo $p$, either $m=0$ or Fermat's little theorem gives $m^{3d}=m$; the same holds modulo $q$. The Chinese remainder theorem then gives $c^d=m(\mathrm{mod}n)$. One may alternatively invert $3$ modulo $\mathrm{lcm}(p-1,q-1)$, but inversion modulo $\phi (n)$ is sufficient for this paper.

For each candidate nonzero offset $k\in \{1,\dots ,2^{16}-1\}$, expansion givesConsequently, if $D_k$ is invertible, the candidate isCompute the modular multiplicative inverse using the extended Euclidean algorithm, then verify both $m_k^3\equiv c_1$ and $(m_k+k{)}^3\equiv c_2(\mathrm{mod}n)$. The RSA cryptosystem cubing map is a bijection, so an accepted candidate cannot be a different plaintext with the same first ciphertext. This costs fewer than $2^{16}$ trials, each involving polynomially many operations in the bit length of $n$.

There is a useful way to handle every denominator exception for a correct nonzero $k$. Compute $g=\gcd (D_k,n)$. If $1<g<n$, this greatest common divisor factors $n$, allowing ordinary RSA cryptosystem decryption. If $g=n$, then $D_k=0(\mathrm{mod}n)$. The permitted prime numbers are $2(\mathrm{mod}3)$ and much larger than $k$, so $k$ is invertible modulo each. The equation $m^2+km+k^2=0$ would make $m/k$ a nontrivial cube root of one, impossible in a group of order coprime to three. Thus $g=n$ cannot occur for the correct nonzero offset under these hypotheses.

If the bound in the question is read as also allowing $k=0$, then $c_1=c_2$ and there is no additional information: the problem reduces to inverting a single ordinary RSA cryptosystem ciphertext. The small-offset attack requires a nonzero difference; that is the natural reading of distinct related messages.

All calculations are in modular arithmetic modulo $n$. Expand the two expressions appearing in the proposed quotient:The first is exactly $m$ times the second. Multiplication by the assumed modular multiplicative inverse therefore givesThe representative in $\{0,\dots ,n-1\}$ is the plaintext. This RSA related-message attack uses a relation between messages to turn two cubic equations into a linear equation; it does not recover the private key or factor $n$ in the invertible case.

Avoid constructing the huge integers $c^{3^j}$ explicitly. Maintain $a_0=c$ and $a_j=a_{j-1}^3\mathrm{mod}n$, computing $g_j=\gcd (a_j-c,n)$ after each step.

In case (1), the nontrivial greatest common divisor $g_k$ is one of the prime factors $p,q$. Divide $n$ by it, compute $d$ with the extended Euclidean algorithm, and return $c^d\mathrm{mod}n$.

In case (2), $a_k=c(\mathrm{mod}n)$. The preceding value satisfies $a_{k-1}^3=c(\mathrm{mod}n)$. Cubing is a bijection on the residue classes modulo $n$, so there is only one such cube root, namely the original plaintext $m$. ThereforeFor $k=1$, the preceding value is $a_0=c$; a fixed point is its own plaintext. Keeping the previous iterate makes the recovery immediate once the RSA cycling attack succeeds.

In the Dolev-Yao model, an adversary controls the network: it can intercept, suppress, delay, replay and redirect messages, impersonate network senders, and construct messages from values it knows. In particular, it can concatenate or split unprotected tuples, and can apply encryption using any known public key or known symmetric key.

Cryptography is idealised. Without the required private key or symmetric key, the adversary cannot recover a protected plaintext or construct an otherwise unavailable protected value. It cannot invent an unknown long-term secret merely because the containing ciphertext is visible. Protocol failures arise from the arrangement of messages even when these cryptographic primitives behave perfectly.

In a ciphertext-only attack, the adversary sees ciphertexts but has no supplied corresponding plaintexts. In a known-plaintext attack, it also knows one or more matching plaintext–ciphertext pairs. In a chosen-plaintext attack, it can select plaintexts and obtain their encryptions, possibly choosing later inputs from earlier results.

The ordinary exhaustive key search is a known-plaintext attack: given $x$ and $c=E_k(x)$, try candidate keys $k^{\prime }$ and compare $E_{k^{\prime }}(x)$ with $c$. A uniformly selected $m$-bit key has average position $(2^m+1)/2$ in any fixed search order, so

This counts testing until the actual key is reached. One known pair may leave false candidate keys when $m$ is large relative to the block length $n$; additional pairs distinguish them. If a plaintext has recognisable redundancy, a ciphertext-only attack can sometimes test keys by that redundancy instead, but this is an additional assumption rather than the standard supplied-pair setting.

Let $s=k\oplus \mathrm{rev}(k)$ be the effective mask. For each position $i$,Thus the mask is always a palindrome, even though $k$ itself is uniformly random. The exclusive or of the ciphertext bits in a mirror pair isbecause the equal mask bits cancel. The observer learns the corresponding plaintext parity exactly. If $n$ is odd, the middle mask bit is also zero, so the middle plaintext bit is exposed directly.

An explicit failure of perfect secrecy works for every $n\ge 1$. Choose $X$ uniformly from $0^n$ and $10^{n-1}$. For $X=0^n$, the ciphertext is a palindrome with probability one. For $X=10^{n-1}$ and $n\ge 2$, toggling just the first bit breaks the mirror equality, so the ciphertext is a palindrome with probability zero. For $n=1$, the effective mask is zero and $C=X$. Observing $C$ therefore distinguishes these two messages perfectly.

There are only $2^{\lfloor n/2\rfloor }$ possible effective masks, each equally likely. Hence even a fresh $n$-bit key supplies at most $\lfloor n/2\rfloor$ independent masking bits in this construction. Choosing a long, uniform, one-use key is insufficient if the encryption transformation collapses its randomness.

Perfect secrecy means that observing the ciphertext changes no probability concerning the plaintext. For every distribution of the message $X$, and every $x,c$ with $\mathrm{Pr}(C=c)>0$,Equivalently, for every pair $x,x^{\prime }$ the conditional probability distributions of the ciphertext are identical:The randomness here comes from independent key generation and any encryption randomness. The claim is information theoretic: unlimited computation cannot extract information about $X$ from $C$ beyond what was known beforehand.

For encrypt-and-authenticate, the transmitted pair is $(E_k(x),s)$ with $s=f(sk,x)$. The recovery map is public, so any observer computesNo symmetric key, exhaustive key search or oracle is needed. Publishing this message-recovery digital signature reveals the entire plaintext and breaks cryptographic confidentiality outright. A digital signature of a suitable digest would have different leakage properties, but the printed construction signs the raw block.

For encrypt-then-authenticate, choose any $n$-bit string $s$ and computeSend $(c,s)$. The receiver's correct check for this composition is $g(pk,s)=c$ before decryption, so it passes by construction. The receiver obtains a plaintext $x=D_k(c)$, although the adversary may not know it.

The finite domains justify the signature relation: $g\circ f$ is the identity on $2^n$ messages, so $f$ is injective and therefore bijective. Hence $g=f^{-1}$ and also $f\circ g$ is the identity. The chosen $s$ is therefore exactly $f(sk,c)$, without the adversary ever evaluating $f$.

This is a key-only signature attack against raw unrestricted trapdoor signing. It does not invert $g$ at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the digital signature first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.