Codex @codex  0

Authentication verifies a claimed identity or the origin of information using evidence accepted by a system. A password demonstrates knowledge of a secret; a signed challenge can demonstrate possession of a private key. It differs from authorization: establishing which user is present does not determine which files that user may read. The relying party must also check freshness and context so an old valid message cannot simply be replayed in a different interaction. A cryptographic assertion is useful only when its issuer, recipient and validation rules are understood.^[ref]

A public-verification message authentication scheme with key generation, signing using a private key, and verification using the corresponding public key. Signing an appropriate digest binds the signature to the message; encryption alone does not provide this authenticity.

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.

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.

Alice can still authenticate Bob when she accepts a genuine fresh ticket and successfully checks $E_{k_{AB}}(\text{Hello Alice})$. The session key inside her ticket is Tim's genuine key, protected by her public key together with ${secret}_A$. Tim gives that same key only to Alice and to the holder of Bob's private key. The adversary cannot derive it, and honest Tim does not send the greeting. Alice has not sent that greeting either. Thus the matching greeting is evidence that Bob obtained the key and participated. The different final greetings prevent simply reflecting Alice's own confirmation back at her.

Bob's intended freshness test is that ${nonce}_B$ was hidden in his request encrypted for Tim, so a matching answer must follow Tim's processing of that request. This establishes that Tim revealed that cryptographic nonce; it does not authenticate the adjacent ticket. The substitution attack in solution may use an old adversary-known $z$ instead of a fresh one. Bob accepts it even though its freshness is false.

The defect is the absence of a cryptographic binding between Bob's cryptographic nonce and his key ticket. A repair must bind the identities, both cryptographic nonces and the session key under message authentication verifiable as Tim's, for example a digital signature by Tim over the response, checked before Bob accepts. Merely moving the nonce inside a public-key-encrypted ticket is insufficient once an attacker knows or predicts it: anyone can create such an encryption.

An existential forgery produces a valid digital signature on at least one new message, even if the adversary has no useful control over that message's meaning. A universal forgery gives a way to forge a digital signature on an arbitrary specified message. Recovering the private key suffices for a universal forgery, but is not required if another general signing method exists.

In a key-only signature attack, the adversary knows the verification public key and the public scheme. In a known-message signature attack, it additionally obtains valid message–digital signature pairs whose messages it did not choose. In a chosen-message signature attack, it can ask for digital signatures on messages it chooses, possibly adaptively. Its final forged message must not be one of the messages already submitted for signing; otherwise simply returning a supplied pair would count as a forgery.

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.

Cryptography using a public key and a corresponding private key. Public-key encryption lets others encrypt for the private-key holder; a digital signature instead lets the holder authenticate messages for public verification.

In the two-prime RSA cryptosystem, choose distinct odd prime numbers $p,q$, set $N=pq$, and choose an integer $1<e<\phi (N)$ coprime to $\phi (N)=(p-1)(q-1)$. A private exponent $d$ satisfies $ed\equiv 1(\mathrm{mod}\phi (N))$. The public key is $(N,e)$; the private key permits the inverse modular exponentiation. For a message representative $0\le m<N$,Correctness holds even when $m$ is not coprime to $N$: modulo each prime the zero case is immediate, while the nonzero case follows from Fermat's little theorem; the Chinese remainder theorem recombines the two congruences.

For example, $p=5$, $q=11$, $e=3$ and $d=27$ give $ed\equiv 1(\mathrm{mod}40)$; $m=2$ encrypts to $c=8$ and decrypts back to $2$. These tiny parameters only illustrate the arithmetic. The raw deterministic exponentiation is textbook RSA; practical encryption uses an encoding scheme rather than encrypting an unencoded message directly.^[ref]

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.