RSA . It 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 drew on the Diffie-Hellman article on public key systems .
Summary
[ hide ]
- 1 Features
- 1 Specifications
- 2 Safety
- 3 Advantages
- 4 RSA algorithm
- 5 Padding schemes
- 6 Authentication of messages
- 7 Safety
- 8 Practical considerations
- 1 Key generation
- 2 Speed
- 9 Key distribution
- 10 Source
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 drew 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 has been generated, it should be protected using a symmetric cryptographic algorithm.
specs
Regarding key lengths, the RSA system allows variable lengths, currently being 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 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 unencrypted 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 possible ciphertext. The last feature is the increase in the dictionary, making it intractable when attacking.
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 # 1and 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 the security of the signature and the encryption of messages, and that the same key should never be used for encryption and authentication purposes.
Security
The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem . Full decryption of an RSA ciphertext is computationally intractable, an efficient algorithm has not yet been found for both problems. Providing security against partial decryption might require the addition of a security padding scheme.
The RSA problem is defined as the task of taking roots eth module to compose n: retrieving a value m such that me = c ≡mod n, where (e, n) is an RSA public key and c is the RSA encrypted text. Currently the approximation to solve the RSA problem is the factor of modulus n. With the ability to retrieve prime factors, an attacker can compute the secret exponent d from a public key (e, n), then decrypt c using standard procedure. To achieve this, an attacker factors n into p and q, and computes (p-1) (q-1) allowing it to determine d and e. No method in polynomial time has been found for factoring long integers. See integer factoring for a discussion of this problem.
The factorization of large numbers usually propose methods being 663 bits long using advanced distributed methods. RSA keys are normally between 1024-2048 bits in length. Some experts believe that 1024-bit keys could become weak in a short time; with 4096-bit keys they could be broken in the future. Therefore, if n is large enough the RSA algorithm is safe. If n has 256 bits or less, it can be factored in a few hours with a personal computer, using free software . If n is 512 bits or less, it can be factored by several hundred computers as in 1999. A theoretical hardware device called TWIRLdescribed by Shamir and Tromer in 2003 questioned the security of 1024-bit keys. It is currently recommended that n be at least 2048 bits long.
In 1993, Peter Shor published his algorithm, showing that a quantum computer could in principle improve factoring in polynomial time, showing RSA as an outdated algorithm. However, quantum computers are not expected to finish their development for many years.
Practical considerations
Key generation
Searching for large primes p and q by the randomness test and performing probabilistic primality tests which eliminate virtually all non-primes (efficiently).
The numbers p and q should not be close enough for the Fermat factorization for n to be successful. Also, if any p-1 or q-1 has only small prime factors, n can be factored quickly, so these p or q values must be discarded.
One should not employ a prime search method with which to give any information about the primes to the attacker. In particular, a good random prime number generator for the beginning of the value used. Note that the requirement is both ‘random’ and ‘unpredictable’. These are not the same criteria; a number could have been chosen by a random process, but if it is predictable in any way (or partially predictable), the method used will be of low security. For example: Rand Corp’s table of random numbers in 1950 could very well be truly random, but it has been published and can be accessed by the attacker. If the attacker can guess half the digits of poq, he could quickly compute the other half.
It is important that the secret key d is very large. Wiener showed in 1990 that if p is between q and 2q (typical) and d <n1 / 4/3, then d can be efficiently computed from n and e. Although values of e are low as 3 have been used in the past, small exponents in RSA are currently deprecated, for reasons including the unpadded of the clear text, vulnerability listed above 65537 is normally used for the value of e, considered too much large to avoid small exponentiation attacks, in fact has enough hamming weight to facilitate efficient exponentiation
Speed
RSA is much slower than DES and other symmetric cryptosystems. In practice, Bob normally encrypts messages with symmetric algorithms, encrypts the symmetric key with RSA, and transmits to both the RSA-encrypted symmetric key (that is, he transmits it encrypted with RSA) and the symmetrically-encrypted message to Alice.
This also raises additional security problems, for example it is of great importance to use a strong random generator for symmetric keys, because otherwise Eve (an attacker who wants to find out the content of the message) could bypass RSA’s asymmetric key by guessing. of the symmetric key.
Key distribution
Like all encryption, it is important how the RSA public keys are distributed. The distribution of the key must be secure against an attacker who is about to spy on the channel to make a replay attack. Suppose Eve (attacker) has some way of arbitrarily giving Bob keys and making him believe they came from Alice. Suppose Eve can intercept transmissions between Alice and Bob. Eve sends Bob her own public key, as Bob thinks it is from Alice. Eve can then intercept any ciphertext sent by Bob, decrypt it with her own secret key, save a copy of the message, encrypt the message with Alice’s public key, and send the new ciphertext to Alice. In principle, neither Alicia nor Bob have detected Eve’s presence. Some are based on digital certificates or other infrastructure components of the public key against the defense of attacks.
