RSA cryptosystem

For $N=pq$, choose $e$ coprime to $\varphi (N)$ and a private exponent $d$ with $ed\equiv 1(\mathrm{mod}\varphi (N))$. Encryption and decryption are

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.

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.

An attack exploiting a known relation between plaintexts encrypted using one textbook RSA cryptosystem key. For public exponent three and a known nonzero additive difference, two cubic equations can yield a linear relation recovering a plaintext. A small unknown difference can be enumerated.

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.

If the same invertible message $m$ is sent under one RSA modulus with coprime public exponents $e_1,e_2$, choose integers $a,b$ with $a{e}_1+b{e}_2=1$. From $c_i=m^{e_i}(\mathrm{mod}N)$ one recoversusing modular inverses for negative exponents.

Knowledge of a valid public and private exponent gives $ed-1$, a nonzero multiple of $\lambda (N)$. Writing it as $2^{s}t$ with $t$ odd and testing random bases produces a nontrivial square root of one modulo $N$ with high probability; a greatest common divisor then factors $N$. Thus one customer's private key under a shared semiprime modulus compromises every exponent using that modulus.

An RSA fixed point satisfies $m^e\equiv m(\mathrm{mod}N)$. Since every valid public exponent $e$ is odd, $(-m{)}^e\equiv -m^e\equiv -m(\mathrm{mod}N)$; therefore $N-m$ is a fixed point whenever $m$ is.