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]

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 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.

CRYSTALS-Kyber is a key encapsulation mechanism based on module learning with errors. Its underlying encryption uses polynomial-vector arithmetic with small secret and error coefficients; a transformation around that encryption supplies resistance to chosen-ciphertext attacks. Encapsulation produces a fresh shared secret and the ciphertext needed by the decapsulating party.^[ref]

Using a module structure reduces representation and computation costs compared with a fully unstructured matrix description. The security claim concerns the difficulty of the resulting noisy algebraic problem; the word lattice does not by itself prove resistance to every attack. ML-KEM standardizes a descendant of Kyber with exact algorithms and encodings. Applications must name the chosen version rather than treating Kyber and ML-KEM as byte-for-byte synonyms.

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.

A key encapsulation mechanism consists of key generation, encapsulation and decapsulation algorithms. Given a public encapsulation key $pk$, encapsulation produces $(K,c)$: a shared secret $K$ and an encapsulation ciphertext $c$. Given the secret key $sk$ and $c$, decapsulation produces the same $K$, except for any explicitly bounded correctness failure.^[ref]

For example, a sender can encapsulate $K$, derive a session encryption key from $K$ and agreed context, then use authenticated encryption for a long message. The ciphertext $c$ carries the encapsulated secret, while the separate encrypted payload carries the message. Chosen-ciphertext security considers an attacker who can request decapsulation of other ciphertexts; correctness alone does not provide that protection. Authentication and binding the public key to the intended recipient remain responsibilities of the surrounding cryptographic protocol.

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

ML-KEM is the module-lattice key encapsulation mechanism standardized in FIPS203 in2024, derived from CRYSTALS-Kyber. Key generation supplies an encapsulation key and a decapsulation key. Encapsulation returns both a ciphertext and a shared secret; decapsulation uses the secret key to recover the shared secret from that ciphertext.^[ref]

The mechanism is built on noisy module-linear equations and a chosen-ciphertext-secure transformation. Decapsulation performs an internal consistency check and uses an alternate secret-derived result for invalid ciphertexts rather than exposing a simple decryption-failure response. ML-KEM-512,768 and1024 are separate standardized parameter sets. Establishing a secret this way does not authenticate the peer by itself: an unauthenticated exchange remains vulnerable to public-key substitution. A surrounding cryptographic protocol supplies identities and transcript binding.

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 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.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.

Take the positive integer $k$ whose existence is allowed by the question and writeModulo $p$, if $c=0$ then $c^{3^k}=c$ directly. Otherwise Fermat's little theorem applies, since $3^k-1$ is a multiple of $p-1$. Hence $c^{3^k}=c(\mathrm{mod}p)$. The same two-case argument works modulo $q$. By the Chinese remainder theorem,soThis also covers a ciphertext that is not coprime to $n$; applying Euler's theorem without checking that hypothesis would miss this detail. Equivalently, repeated application of a permutation on a finite set eventually returns to the starting point, although the arithmetic argument gives the requested sufficient exponent.

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.

Repeatedly apply the public RSA cryptosystem encryption map to a ciphertext. A return to that ciphertext reveals its preceding iterate as the plaintext. A nontrivial greatest common divisor between an iterate-minus-start and the modulus instead enables integer factorization. Eventual return alone supplies no useful running-time bound.

Recover a plaintext from an RSA cryptosystem ciphertext and the public key, without a supplied private key. Integer factorization of the modulus suffices; the existence of an efficient general reduction in the reverse direction is not known.