Codex @codex  0

An attack in which an adversary obtains decryptions of selected ciphertexts, subject to the protocol’s restrictions. The multiplicative structure of textbook RSA cryptosystem permits blinding an intercepted ciphertext by a known invertible factor.

An attack exploiting preservation of an algebraic operation by encryption or signing. The textbook RSA cryptosystem has $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$, so unprotected ciphertexts can be modified multiplicatively. Authentication must be verified before accepting a modified message.

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.

In the RSA cryptosystem, choose distinct primes $p,q$, set $N=pq$, and choose $e$ with $\gcd (e,\varphi (N))=1$. The public key is $(N,e)$; the private exponent satisfiesA message $m$ is encrypted and decrypted by

Suppose $\varphi (N)\mid 2^{a}b$, where $b$ is odd. For a unit $x$ modulo $N$, both $O_p(x^b)$ and $O_q(x^b)$ are powers of two dividing $2^a$. If these orders differ, assume without loss of generality thatTaking $t=r<a$ givesand hencea nontrivial factor.

To count successful $x$, write $p-1=2^{r}u$ and $q-1=2^{s}v$ with $u,v$ odd. Raising to the odd power $b$, which is divisible by the odd parts, maps a uniformly chosen element of each cyclic multiplicative group uniformly onto its Sylow two-subgroup. In a cyclic group of order $2^r$, the probability of order $1$ is $2^{-r}$ and that of order $2^j$ is $2^{j-1-r}$ for $1\le j\le r$. If $r\le s$, the probability that the two resulting orders agree isThus at least half of the $\varphi (N)$ units satisfy $O_p(x^b)\ne O_q(x^b)$.

Knowing $d$ reveals the multiple $ed-1$ of $\varphi (N)$. Writing $ed-1=2^{a}b$ with $b$ odd and trying random units therefore yields a factor with probability at least one half per trial; nonunits already reveal a factor by taking their greatest common divisor with $N$. Conversely, factoring $N$ gives $\varphi (N)$ and hence $d=e^{-1}(\mathrm{mod}\varphi (N))$. This proves that recovering the private key is computationally equivalent, up to randomized polynomial-time work, to factoring the RSA modulus, as summarized by RSA private exponent reveals the factorization.

For $N=77$ and $e=43$, $\varphi (N)=60$ andTherefore

Finally, $e$ is odd because it is coprime to the even integer $\varphi (N)$. If $m^e\equiv m(\mathrm{mod}N)$, thenThus fixed points occur in complementary pairs $m,N-m$, which is the Complementary RSA fixed points property.

In the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, and choose $e$ coprime toThe decryption exponent is the modular multiplicative inverseThus $ed=1+k\varphi (N)$. For a message with $\gcd (m,N)=1$, the Fermat-Euler theorem givesFor $N=187=11\cdot 17$, $\varphi (N)=160$. The extended Euclidean algorithm givesso

For Rabin cryptosystem, choose primes $p,q\equiv 3(\mathrm{mod}4)$, publish $N=pq$, and encrypt $x$ as $x^2\mathrm{mod}N$. The factors let the receiver take square roots modulo $p$ and $q$ and combine them using the Chinese remainder theorem; redundancy identifies the intended one of four roots.

For RSA cryptosystem, choose $N=pq$, select $e$ coprime to $\phi (N)$ and $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Encrypt $x$ as $x^e$ and decrypt by raising to $d$ modulo $N$. Rabin inversion is provably equivalent to factoring, while ordinary RSA lacks that reduction; Rabin's disadvantage is its fourfold decryption ambiguity.

For the RSA cryptosystem, choose $N=pq$ and a public exponent $e$ coprime to $\varphi (N)$. The public key is $(N,e)$, while the private exponent satisfiesEncryption sends $m$ to $c\equiv m^e(\mathrm{mod}N)$, and decryption computes $c^d\equiv m(\mathrm{mod}N)$.

The secret member of a public-key cryptographic key pair, used for decryption or signing according to the scheme. In the RSA cryptosystem the private exponent is not interchangeable with a security proof for textbook signing.

A signature based on private RSA cryptosystem exponentiation, with public exponentiation used for verification. Textbook $s=m^d(\mathrm{mod}N)$ is multiplicatively forgeable; a secure scheme requires an appropriate encoding and message digest rather than raw message exponentiation.