View source for RSA algorithm

{{simple}}

'''RSA (Rivest–Shamir–Adleman)''' is an [[algorithm]] used by modern computers to [[encryption|encrypt]] and decrypt messages. It is an asymmetric [[Cryptography|cryptographic]] [[algorithm]]. Asymmetric means that there are two different [[Key (cryptography)|keys]]. This is also called [[Public-key cryptography|public key cryptography]], because one of the keys can be given to anyone. The other key must be kept private. The algorithm is based on the fact that finding the [[Factorization|factors]] of a large [[composite number]] is difficult: when the factors are [[prime number]]s, the problem is called [[prime factorization]]. It is also a key pair (public and private key) generator.

RSA involves a public key and private key. The public key can be known to everyone- it is used to encrypt messages. Messages encrypted using the public key can only be decrypted with the private key. The private key needs to be kept secret. Calculating the private key from the public key is very difficult.

== Concepts used ==
RSA uses these concepts from cryptography:
* A [[one-way function]] that is easy to compute; but finding a way to [[Inverse function|reverse]] it, or computing the reverse is very hard.
* A [[discrete logarithm]], which works much like the normal [[logarithm]], but only whole numbers are used, and in general, a modulus (a math operation that finds the [[remainder]] of a number when divided by another number) is used. As an example, a<sup>x</sup>=b, modulo n. The discrete logarithm is about finding the smallest number x that makes this equation true, when a, b and n are known.
* It is potentially solved quickly by [[Shor's algorithm]].

== Generating keys ==
The keys for the RSA algorithm are generated the following way:

# Choose two different large random [[prime number]]s <math>p</math> and <math>q</math>. This should be kept secret.
# Calculate <math>n = p q</math>.
#* <math>n</math> is the modulus for the public key and the private keys.
# Calculate the [[totient]]: <math>\phi (n) = (p-1)(q-1)</math>.
# Choose an [[integer]] <math>e</math> such that <math>1 < e < \phi(n)</math>, and <math>e</math> is [[Coprime|co-prime]] to <math>\phi(n)</math>. <br>'''i.e.:''' <math>e</math> and <math>\phi (n)</math> share no factors other than <math>1</math>: <math>\gcd(e, \phi(n)) = 1</math>; See [[greatest common divisor]].
#* <math>e</math> is released as the public key exponent.
# Compute <math>d</math> to satisfy the [[Modular arithmetic#Congruence|congruence relation]] <math>d e \equiv 1 \!\!\!\!\pmod{\phi(n)}</math>. <br>'''i.e.:''' <math>de = 1 + x\cdot\phi(n)</math> for some integer <math>x</math>. (Simply to say: Calculate <math>d = (1 + x\cdot\phi(n))/e</math> to be an integer)
#* <math>d</math> is kept as the private key exponent.

Notes on the above steps:<!-- NB: This numbering is correct -->
* Step 1: Numbers can be [[Primality test#Probabilistic tests|probabilistically tested]] for primality.
* Step 3: changed in [[PKCS 1|PKCS#1]] v2.0 to <math>\lambda(n) = {\rm lcm}(p-1, q-1)</math> instead of <math>\phi(n) = (p-1)(q-1)</math>.
* Step 4: A popular choice for the public exponents is <math>e = 2^{16} + 1 = 65537</math>. Some applications choose smaller values such as <math>e = 3</math>, <math>5</math>, or <math>35</math> instead. This is done to make encryption and signature verification faster on small devices like smart cards but small public exponents may lead to greater security risks.
* Steps 4 and 5 can be performed with the {{ill|extended Euclidean algorithm|en}}; see [[modular arithmetic]].
<br>
The '''public key''' is made of the modulus <math>n\,</math> and the public (or encryption) exponent <math>e\,</math>.<br>
The '''personal key''' is made of p,q and the private (or decryption) exponent <math>d\,</math> which must be kept secret.
* For efficiency a different form of the '''private key''' can be stored:
** <math>p</math> and <math>q</math>: the primes from the [[key generation]];
** <math>d\bmod(p - 1)</math> and <math>d\bmod(q - 1)</math>: often called ''dmp1'' and ''dmq1'';
** <math>q^{-1}\bmod{p}</math>: often called ''iqmp''.
* All parts of the private key must be kept secret in this form. <math>p\,</math> and <math>q\,</math> are sensitive since they are the factors of <math>n\,</math>, and allow computation of <math>d\,</math> given <math>e\,</math>. If <math>p\,</math> and <math>q\,</math> are not stored in this form of the private key then they are securely deleted along with other intermediate values from key generation.
* Although this form allows faster decryption and signing by using the [[Chinese remainder theorem|Chinese Remainder Theorem (CRT)]] it is considerably less secure since it enables {{ill|Side-channel attack|lt=side channel attacks|en}}. This is a particular problem if implemented on [[smart card]]s, which benefit most from the improved efficiency. <br>(Start with <math>y \equiv x^e \!\!\!\!\pmod{n}</math>, and let the card decrypt that. So it computes <math>(y^d \bmod{p})</math> or <math>(y^d \bmod{q})</math>, whose results give some value <math>z</math>. Now, induce an error in one of the computations. Then <math>\gcd(z-x,n)</math> will reveal <math>p</math> or <math>q</math>.)

== Encrypting message ==
Alice gives her public key <math>(n, e)</math> to Bob and keeps her private key secret. Bob wants to send message <math>M</math> to Alice.

First he turns <math>M</math> into a number <math>m</math> smaller than <math>n</math> by using an agreed-upon reversible protocol known as a [[#Padding schemes|padding scheme]]. He then computes the [[ciphertext]] <math>c\,</math> corresponding to:

: <math> c = m^e \mod{n}</math>

This can be done quickly using the method of [[exponentiation by squaring]]. Bob then sends <math>c\,</math> to Alice.

== Decrypting message ==
Alice can recover <math>m\,</math> from <math>c\,</math> by using her private key <math>d\,</math> in the following procedure:

Given <math>m\,</math>, she can recover the original distinct prime numbers, applying the [[Chinese remainder theorem]] to these two congruences yields

: <math>m^{ed} \equiv m \bmod{pq}</math>.

Thus,

: <math>c^d \equiv m \bmod{n}</math>.

Therefore:

: <math>m = c^d\ mod\ n</math>

===A working example===
Here is an example of RSA encryption and decryption. The prime numbers used here are too small to let us securely encrypt anything. You can [[wikibooks:Cryptography/Generate a keypair using OpenSSL|use OpenSSL to generate and examine a real keypair]].

:1. Choose two random prime numbers <math>p</math> and <math>q \,</math>:
::  <math>p = 61</math> and <math>q = 53 \,</math>;
:2. Compute <math>n = p q \,</math>:
::  <math>n = 61 \times 53 = 3233 \!</math>;
:3. Compute the totient <math>\phi(n) = (p-1)(q-1)</math>:
::  <math>\phi(n) = (61 - 1)(53 - 1) = 3120 \!</math>;
:4. Choose <math>e>1</math> coprime to <math>3120 \,</math>:
::  <math>e = 17 \,</math>;
:5. Choose <math>d\,</math> to satisfy <math>e d \equiv 1 \bmod{\phi(n)}</math>:
::  <math>d = 2753 \,</math>, with <math>17 \times 2753 = 46801 = 1 + 15 \times 3120</math>.

<br>The '''public key''' is (<math>n=3233</math>, <math>e=17</math>). For a padded message <math>m\,</math>the encryption function <math>c = m^e \bmod{n}</math> becomes:

:<math>c = m^{17} \bmod 3233\,</math>

The '''private key''' is (<math>n=3233</math>, <math>d=2753</math>). The decryption function <math>m = c^d \bmod{n}</math> becomes:

:<math>m = c^{2753} \bmod 3233\,</math>

<br>For example, to encrypt <math>m=123</math>, we calculate

:<math>c = 123^{17} \bmod 3233 = 855</math>

To decrypt <math>c = 855</math>, we calculate

:<math>m = 855^{2753} \bmod 3233 = 123</math>

Both of these calculations can be computed fast and easily using the [[Binary exponentiation|square-and-multiply algorithm]] for [[modular exponentiation]].

== Deriving RSA equation from Euler's theorem ==
RSA can easily be derived using [[Euler's totient theorem|Euler's theorem]] and [[Euler's totient function]].

Starting with Euler's theorem,<blockquote><math>m^{\phi (n)} \equiv 1 \pmod{n}</math></blockquote>we must show that decrypting an encrypted message, with the correct key, will give the original message.

Given a padded message ''m'', the ciphertext ''c'', is calculated by<blockquote><math>c \equiv m^e \pmod n</math></blockquote>Substituting into the decryption algorithm, we have<blockquote><math>c^d \equiv (m^e)^d \equiv m^{ed} \pmod n</math></blockquote>We want to show this value is also congruent to ''m''.

The values of ''e'' and ''d'' were chosen to satisfy,<blockquote><math>ed \equiv 1 \pmod {\phi (n)}</math></blockquote>Which is to say, there exists some integer ''k'', such that<blockquote><math>ed = k\times \phi(n) + 1</math></blockquote>Now we substitute into the encrypted then decrypted message,<blockquote><math>\begin{align}
  m^{ed} &\equiv m^{k \phi(n) + 1} \\
         &\equiv m \times m^{k\phi(n)} \\
         &\equiv m \times \left(m^{\phi(n)}\right)^k \pmod n
\end{align}</math></blockquote>We apply [[Euler's totient theorem|Euler's theorem]], and achieve the result.<blockquote><math>m\times (1)^k \equiv m \pmod n</math></blockquote>

==Padding schemes==
When used in practice, RSA must be combined with some form of [[padding (cryptography)|padding scheme]], so that no values of ''M'' result in insecure ciphertexts. RSA used without padding may have some problems:
* The values ''m'' = 0 or ''m'' = 1 always produce ciphertexts equal to 0 or 1 respectively, due to the properties of exponentiation.
* When encrypting with small encryption exponents (e.g., ''e'' = 3) and small values of the ''m'', the (non-modular) result of <math>m^e</math> may be strictly less than the modulus ''n''. In this case, ciphertexts may be easily decrypted by taking the ''e''th root of the ciphertext with no regard to the modulus.
* RSA encryption is a [[deterministic]] encryption algorithm. It has no random component. Therefore, an attacker can successfully launch a [[Chosen-plaintext attack|chosen plaintext attack]] against the [[cryptosystem]]. They can make a [[dictionary attack|dictionary]] by encrypting likely plaintexts under the public key, and storing the resulting ciphertexts. The attacker can then observe the communication channel. As soon as they see ciphertexts that match the ones in their dictionary, the attackers can then use this dictionary in order to learn the content of the message.

In practice, the first two problems can arise when short [[ASCII]] messages are sent. In such messages, ''m'' might be the concatenation of one or more ASCII-encoded character(s). A message consisting of a single ASCII <code>NUL</code> character (whose numeric value is 0) would be encoded as ''m'' = 0, which produces a ciphertext of 0 no matter which values of ''e'' and ''N'' are used. Likewise, a single ASCII <code>SOH</code> (whose numeric value is 1) would always produce a ciphertext of 1. For systems which conventionally use small values of ''e'', such as 3, all single character ASCII messages encoded using this scheme would be insecure, since the largest ''m'' would have a value of 255, and 255<sup>3</sup> is less than any reasonable modulus. Such plaintexts could be recovered by simply taking the cube root of the ciphertext.

To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value ''m'' before encrypting it. This padding ensures that ''m'' does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts. The latter property can increase the cost of a dictionary attack beyond the capabilities of a reasonable attacker.

Standards such as [[PKCS]] have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext ''m'' with some number of additional bits, the size of the un-padded message ''M'' must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks. This may be made easier by a predictable message structure. Early versions of the PKCS standard used {{broken wikt link|ad-hoc|ad-hoc}} constructions, which were later found vulnerable to a practical [[adaptive chosen ciphertext attack]]. Modern constructions use secure techniques such as [[optimal asymmetric encryption padding]] (OAEP) to protect messages while preventing these attacks. The [[PKCS]] standard also has processing schemes designed to provide additional security for RSA signatures, e.g., the Probabilistic Signature Scheme for RSA ([[RSA-PSS]]).

== Signing messages ==
Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob's public key to send him encrypted messages. So, in order to verify the origin of a message, RSA can also be used to [[digital signature|sign]] a message.

Suppose Alice wishes to send a signed message to Bob. She produces a [[cryptographic hash function|hash value]] of the message, raises it to the power of ''d'' mod ''n'' (just like when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of ''e'' mod ''n'' (just like encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since.

Note that secure padding schemes such as [[RSA-PSS]] are as essential for the security of message signing as they are for message encryption, and that the same key should never be used for both encryption and signing purposes.

==References==
{{reflist}}

==Other websites==
* The Original RSA Patent as filed with the U.S. Patent Office by Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), December 14, 1977, '''{{US patent|4405829}}'''.
* [http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/pkcs-rsa-cryptography-standard.htm PKCS #1: RSA Cryptography Standard] ([[RSA Laboratories]] website)
** The ''[[PKCS]] #1'' [[standardization|standard]] ''"provides recommendations for the implementation of [[public-key cryptography]] based on the '''RSA''' algorithm, covering the following aspects: cryptographic [[Primitive type|primitives]]; [[encryption]] schemes; [[Digital signature|signature]] schemes with appendix; [[ASN.1]] syntax for representing keys and for identifying the schemes"''.
* {{YouTube|vgTtHV04xRI|Explanation of RSA using colored lamps}}
* [http://www.di-mgt.com.au/rsa_alg.html Thorough walk through of RSA]
* [http://www.muppetlabs.com/~breadbox/txt/rsa.html Prime Number Hide-And-Seek: How the RSA Cipher Works] {{Webarchive|url=https://web.archive.org/web/20130725060301/http://www.muppetlabs.com/~breadbox/txt/rsa.html |date=2013-07-25 }}
* [http://eprint.iacr.org/2006/351 Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: ''On the Power of Simple Branch Prediction Analysis'']
* [http://blog.cacert.org/2006/11/193.html A New Vulnerability In RSA Cryptography, CAcert NEWS Blog]
* [http://polarssl.org/source_code Example of an RSA implementation with PKCS#1 padding (GPL source code)] {{Webarchive|url=https://web.archive.org/web/20120722193444/http://polarssl.org/source_code |date=2012-07-22 }}
* [http://www.cryptography.com/resources/whitepapers/TimingAttacks.pdf Kocher's article about timing attacks]
* [http://www.cryptool.org/images/ct1/presentations/RSA/RSA-Flash-en/player.html An animated explanation of RSA with its mathematical background by CrypTool] {{Webarchive|url=https://web.archive.org/web/20180928124928/https://www.cryptool.org/images/ct1/presentations/RSA/RSA-Flash-en/player.html |date=2018-09-28 }}
* [https://rsa.gnos.space/ An interactive walkthrough going through all stages to make small example RSA keys] {{Webarchive|url=https://web.archive.org/web/20200707214322/https://rsa.gnos.space/ |date=2020-07-07 }}
* [http://inventwithpython.com/hacking ''Hacking Secret Ciphers with Python''], [http://inventwithpython.com/hacking/chapter24.html Chapter 24, Public Key Cryptography and the RSA Cipher]
* {{cite web|last=Grime|first=James|title=RSA Encryption|url=http://www.numberphile.com/videos/RSA.html|work=Numberphile|publisher=[[Brady Haran]]|access-date=2019-06-20|archive-date=2018-10-06|archive-url=https://web.archive.org/web/20181006042830/http://www.numberphile.com/videos/RSA.html|url-status=dead}}
* [http://www.gnudeveloper.com/groups/cyber_security/Cryptography_RSA_Key_Exchange_works_in_realtime_using_Keytool_openSSL%20.html How RSA Key used for Encryption in real world]
* [https://www.putorius.net/factor-prime-numbers-encryption.html Prime Numbers, Factorization, and their Relationship with Encryption]

{{Cryptography public-key}}

[[Category:Cryptography]]
[[Category:Algorithms]]