Security
According to abbreviationfinder, 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 polynomial-time method has been found for factoring long integers. See integer factoring for a discussion of this problem.
The factoring 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 no 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 TWIRL described 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. Furthermore, 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 1950 table of random numbers 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 unpadded 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 usually 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 Alice nor Bob have detected Eve’s presence. Against the defense of attacks some are based on digital certificates or other infrastructure components of the public key.
