All You Need to Know About RSA

RSA. It was created in 1978 by Ron Rivest, Adi Shamir, and Len Adleman of the Massachusetts Institute of Technology (short for MIT according to abbreviationfinder); the letters RSA are the initials of their surnames, and it is the best known and most used asymmetric cryptographic system. These gentlemen were based on the Diffie-Hellman article on public key systems.

Characteristics

The RSA public key algorithm was created in 1978 by Ron Rivest, Adi Shamir, and Len Adleman of the Massachusetts Institute of Technology(MIT); the letters RSA are the initials of their surnames, and it is the best known and most used asymmetric cryptographic system. These gentlemen were based on the Diffie-Hellman article on public key systems.

These keys are calculated secretly on the computer where the private key is to be stored, and once it is generated, it should be protected using a symmetric cryptographic algorithm.

specs

Regarding key lengths, the RSA system allows variable lengths, being currently advisable to use keys of no less than 1024 bits (keys of up to 512 bits have been broken, although it took more than 5 months and almost 300 computers working together to do it).

Security

RSA bases its security on being a computationally safe function, since although performing modular exponentiation is easy, its inverse operation, the extraction of roots of modulus Ø is not feasible unless the factorization of e is known, the system’s private key.. RSA is the best known and most widely used of the public key systems, and also the fastest of them.

Advantage

It has all the advantages of asymmetric systems, including the digital signature, although the use of symmetric systems is more useful when implementing confidentiality, as they are faster. It is also often used in mixed systems to encrypt and send the symmetric key that will be used later in encrypted communication.

RSA algorithm

The algorithm consists of three steps: key generation, encryption, and decryption.

Padding schemes

RSA must be combined with some version of the padding scheme, otherwise the value of M can lead to insecure ciphertext. RSA used without padding scheme could suffer many problems.

The value m = 0 or m = 1 always produces the same ciphertext for 0 or 1 respectively, due to properties of the exponents.
When we code with small exponents (e = 3) and small values of m, the result of m could be strictly less than the modulus of n. In this case, the ciphertext could be easily decrypted, taking the e-th root of the ciphertext regardless of the module.
Since RSA encryption is a deterministic algorithm (it has no random components) an attacker can successfully launch a chosen text attack against the cryptosystem, building a dictionary of probable texts with the public key, and storing the encrypted result. By observing the encrypted texts in a communication channel, the attacker can use this dictionary to decrypt the content of the message.

In practice, the first of the two problems could arise when we send small ASCII messages where m is the concatenation of one or more ASCII encoded character / s. A message consisting of a single ASCII NUL character (whose value is 0) would be encoded as m = 0, producing a ciphertext of 0 no matter what values of e and N are used. Probably a single ASCII SOH (whose value is 1) would always produce a ciphertext of 1. For conventional systems using small values of e, such as 3, a single ASCII character message encoded using this scheme would be insecure, since the maximum value of m would be 255, and 255³ is less than any reasonable modulus. In this way the clear texts could be recovered simply by taking the cube root of the ciphertext. To EVITED these problems, the practical implementation of RSA is helped by some structures, use of randomized padding within the value of m before encryption. This technique ensures that m will not fall into the range of insecure clear texts, and that given a message, once it is filled in, it will encrypt one of the large numbers of the possible encrypted texts. The last feature is the increase in the dictionary, making it intractable when carrying out an attack.

The RSA-padding scheme must be carefully designed to prevent sophisticated attacks which could be facilitated by the predictability of the message structure. Examples of fill scheme used with RSA:

RSA-OAEP (Optimal Asymetric Encryption Padding) or its modified version RSA-OAEP +. This type of padding is used for example in PKCS # 1 and in the TOR anonymity network
RSA-SAEP + (Simplified Asymmetric Encryption Padding)
RSA-REACT
RSA-PSS (Probabilistic Signature Scheme). Used for example in PKCS # 1

Message authentication

RSA can also be used to authenticate a message. Suppose Alice wants to send an authenticated message to Bob. She produces a hash value of the message, raises it to the power of d≡ mod n (as she does when decrypting messages), and attaches it to the message as a “signature.” When Bob receives the authenticated message, he uses the same hashing algorithm in conjunction with Alice’s public key. Raises the received signature to the power of e≡ mod n (as it does when encrypting messages), and compares the hash result obtained with the hash value of the message. If the two match, he knows that the author of the message was in possession of Alicia’s secret key, and that the message has not been tampered with (it has not suffered attacks).

It should be noted that the security of padding-schemes such as RSA-PSS are essential for both signature security and message encryption, and that the same key should never be used for encryption and authentication purposes.