# RSA The RSA algorithm (Rivest-Shamir-Adleman) is a public key cryptosystem that uses a pair of keys to secure digital communication and transactions over insecure networks, such as the internet. Fundamental concept: **Asymetric cryptography**. One key encrypts, the other decrypts. ## How does the RSA algorithm work? Use of the RSA algorithm typically consists of four stages: - **Key generation.** Two large prime numbers are selected and used to generate the public and private keys. - **Key distribution.** The public key can be shared with anyone who needs to send encrypted messages to the recipient. The private key is kept secure and only known to the recipient. - **Encryption.** To encrypt a message, the sender uses the recipient's *public key* to transform the message into *ciphertext*. - **Decryption.** The recipient uses their *private key* to decrypt the ciphertext back into the original message. ## The algorithm* 1. Choose large prime numbers $p,q$ (with additional properties). 2. Let the *modulus* be $n=p \cdot q$ . 3. Find (in a specific way we'll not describe) very large numbers $d,e$ satisfying: $ \forall m < n \ ( m^{d \cdot e} \equiv m \mod n ) $ 4. $d$ is the *private key exponent* and is kept secret. 5. $e$ is the *public key exponent* and is released along with the modulus $n$. 6. Given a message (coded as an integer) $m<n$, encrypt $m$ using $e,n$ by finding a *ciphertext* $c$ which satisfies $c \equiv m^{e} \mod n.$ 7. Given a ciphertext $c$, decrypt it using $d$ by computing: $c^{d} \equiv (m^{e})^{d} \equiv m \mod n.$ $\ast$ I suppress some details regarding the choice of $p,q$ and the way $d,e$ are computed using $p,q$. More details in [wikipedia](https://en.wikipedia.org/wiki/RSA_cryptosystem). ## Security >[!info] Definition >**The RSA problem:** Given integers $n,e,c$, find an integer $n$ such that $c \equiv m^{e} \mod n.$ Solving the RSA problem means cracking the encryption. The most efficient method known to solve the RSA problem is by first factoring the modulus $n$ into its prime factors $p,q$, then using them to calculate the private key $d$ and use it to retrieve $m$. So breaking RSA is reduced to the problem of *prime factorization*, which is suspected to be impossible in [[P (complexity)|polynomial time]] using classical computers (but no proof has been provided yet), and hence impractical for large $n$. [[Shor's algorithm]] is a method of factoring into primes by a [[Quantum computing|quantum computer]] in polynomial time, hence in theory quantum computers could be used to break RSA. ## Links https://en.wikipedia.org/wiki/P_(complexity) https://en.wikipedia.org/wiki/RSA_cryptosystem https://www.techtarget.com/searchsecurity/definition/RSA