RSA algorithm

**RSA (Rivest–Shamir–Adleman)** stops people from understanding messages they are not allowed to read. A message only some people can understand is called an encrypted message. Any message can become an encrypted message. An encrypted message can be given to anyone because they will not understand what it says. To understand the encrypted message a person must first get the original message back. This is called decryption.

RSA uses two special numbers. One number is called the public key and allows anyone to write an encrypted message. The second number is called a private key and allows understanding the encrypted message (decryption). Both numbers belong together. They are a pair. RSA gives everyone a different pair of numbers to use.

Reading and writing encrypted messages is called cryptography. There are different kinds of cryptography. Cryptography that uses two numbers (keys), like RSA, is called asymmetric cryptography and public key cryptography.

Usually only reading encrypted messages is important. Anyone may write them. This is why the public key can be given to everyone and is called public. The private key needs to be kept secret.

RSA uses math that is easy to do but hard to undo. Someone who does not have the private key must do a lot of work to find it. Reading an encrypted message with the private key is easy.

The math takes a large number and finds numbers that can be multiplied to equal the large number. The smaller numbers are called factors. If a number has no factors it is called a prime number otherwise it is called a composite number. Finding the smallest factors for a large number is called prime factorization.

## Concepts used

RSA uses these concepts from cryptography:
- A one-way function that is easy to compute; but finding a way to 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:

1. Choose two different large random prime numbers  and . This should be kept secret.
1. Calculate .
    - is the modulus for the public key and the private keys.
1. Calculate the totient: .
1. Choose an integer  such that , and  is co-prime to .
**i.e.:**  and  share no factors other than : ; See greatest common divisor.
    - is released as the public key exponent.
1. Compute  to satisfy the congruence relation .
**i.e.:**  for some integer . (Simply to say: Calculate  to be an integer)
    - is kept as the private key exponent.

Notes on the above steps:
- Step 1: Numbers can be probabilistically tested for primality.
- Step 3: changed in PKCS#1 v2.0 to  instead of .
- Step 4: A popular choice for the public exponents is . Some applications choose smaller values such as , , or  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 ; see modular arithmetic.

The **public key** is made of the modulus  and the public (or encryption) exponent .

The **personal key** is made of p,q and the private (or decryption) exponent  which must be kept secret.
- For efficiency a different form of the **private key** can be stored:
    - and : the primes from the key generation;
    - and : often called _dmp1_ and _dmq1_;
    - : often called _iqmp_.
- All parts of the private key must be kept secret in this form.  and  are sensitive since they are the factors of , and allow computation of  given . If  and  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 (CRT) it is considerably less secure since it enables . This is a particular problem if implemented on smart cards, which benefit most from the improved efficiency.
(Start with , and let the card decrypt that. So it computes  or , whose results give some value . Now, induce an error in one of the computations. Then  will reveal  or .)

## Encrypting message

Alice gives her public key  to Bob and keeps her private key secret. Bob wants to send message  to Alice.

First he turns  into a number  smaller than  by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext  corresponding to:

This can be done quickly using the method of exponentiation by squaring. Bob then sends  to Alice.

## Decrypting message

Alice can recover  from  by using her private key  in the following procedure:

Given , she can recover the original distinct prime numbers, applying the Chinese remainder theorem to these two congruences yields

- .

Thus,

- .

Therefore:

### 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 use OpenSSL to generate and examine a real keypair.

- 1. Choose two random prime numbers  and :
    - and ;
- 2. Compute :
    - ;
- 3. Compute the totient :
    - ;
- 4. Choose  coprime to :
    - ;
- 5. Choose  to satisfy :
    - , with .

The **public key** is (, ). For a padded message the encryption function  becomes:

The **private key** is (, ). The decryption function  becomes:

For example, to encrypt , we calculate

To decrypt , we calculate

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

## Deriving RSA equation from Euler's theorem

RSA can easily be derived using Euler's theorem and Euler's totient function.

Starting with Euler's theorem,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 bySubstituting into the decryption algorithm, we haveWe want to show this value is also congruent to _m_.

The values of _e_ and _d_ were chosen to satisfy,Which is to say, there exists some integer _k_, such thatNow we substitute into the encrypted then decrypted message,We apply Euler's theorem, and achieve the result.

## Padding schemes

When used in practice, RSA must be combined with some form of 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  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 against the cryptosystem. They can make a 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 `NUL` 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 `SOH` (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  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 sign a message.

Suppose Alice wishes to send a signed message to Bob. She produces a 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.

## 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, ****.
- PKCS #1: RSA Cryptography Standard (RSA Laboratories website)
    - The _PKCS #1_ standard _"provides recommendations for the implementation of public-key cryptography based on the **RSA** algorithm, covering the following aspects: cryptographic primitives; encryption schemes; signature schemes with appendix; ASN.1 syntax for representing keys and for identifying the schemes"_.
- Thorough walk through of RSA
- Prime Number Hide-And-Seek: How the RSA Cipher Works
- Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: _On the Power of Simple Branch Prediction Analysis_
- A New Vulnerability In RSA Cryptography, CAcert NEWS Blog
- Example of an RSA implementation with PKCS#1 padding (GPL source code)
- Kocher's article about timing attacks
- An animated explanation of RSA with its mathematical background by CrypTool
- An interactive walkthrough going through all stages to make small example RSA keys
- _Cracking Codes with Python_, Chapter 24, Programming the Public Key Cipher
- How RSA Key used for Encryption in real world
- Prime Numbers, Factorization, and their Relationship with Encryption