RSA encryption is one of the first practical public key cryptosystems that is widely used for secure data transfer. Its main difference from similar services is that the encryption key is public and different from the decryption key, which is kept secret. In RSA technology, this asymmetry is based on the practical difficulty of factoring two large primes (factoring problem).
History of creation
The RSA name consists of the initial letters of the names Rivest, Shamir and Adleman, scientists who first publicly described similar encryption algorithms in 1977. Clifford Cox, an English mathematician who worked for the UK special services, first developed the equivalent system in 1973, but it was not declassified until 1997.
The RSA user creates and then publishes a public key based on two large prime numbers along with an auxiliary value. Prime numbers must be kept confidential. Anyone can use the public key to encrypt the message, but if it is large enough, then only someone with knowledge of primes can decode the message. The disclosure of RSA encryption is known as the main problem: today there remains an open discussion about how reliable this mechanism is.
RSA is a relatively slow algorithm, which is why it is not so widely used to directly encrypt user data . Most often, this method is used to transmit encrypted shared keys for a symmetric encryption key, which, in turn, can perform bulk encryption and decryption operations at a much higher speed.
When did the cryptosystem appear in its modern form?
The idea of an asymmetric cryptosystem key is attributed to Diffie and Hellman, who published the concept in 1976, presenting digital signatures and trying to apply number theory. Their formulation uses a common secret key created from the exponentiality of a certain number modulo a prime number. However, they left open the problem of implementing this function, since the principles of factoring were not well studied at that time.
Rivest, Adi Shamir and Adleman at the Massachusetts Institute of Technology made several attempts throughout the year to create a one-way function that is difficult to decode. Rivest and Shamir (as computer scientists) offered many potential functions, while Adleman (as a mathematician) searched for the “weak points” of the algorithm. They used many approaches and eventually in April 1977 developed the final system, today known as RSA.
EDS and public key
An electronic digital signature, or EDS, is an integral part of electronic type documents. It is formed with a certain cryptographic change in data. Using this attribute, it is possible to verify the integrity of the document, its confidentiality, as well as establish who owns it. In fact, this is an alternative to a standard standard signature.
This cryptosystem (RSA-encryption) offers a public key, which differs from symmetric ones. The principle of its operation is that they use two different keys - a private (encrypted), as well as an open one. The first is used in order to generate digital signature and subsequently get the ability to decrypt the text. The second is for actually encrypting and verifying EDS.
Using a signature allows you to better understand RSA encryption, an example of which can be cited as a regular classified "closed from prying eyes" document.
What is the essence of the algorithm?
The RSA algorithm consists of four stages: key generation, distribution, encryption and decryption. As already mentioned, RSA encryption includes a public key and a private key. Open can be known to everyone and is used to encrypt messages. Its essence lies in the fact that messages encrypted using the public key can only be decrypted in a certain period of time using a secret key.
For security reasons, integers should be randomly selected and the same in magnitude, but vary in length by a few digits to make factoring more difficult. The same numbers can be effectively found using a test for their simplicity, so encryption of information must necessarily be complicated.
The public key consists of a module and a public exponent. Closed consists of a module and a private indicator, which should be kept secret.
RSA File Encryption and Weaknesses
However, there are a number of mechanisms for hacking a simple RSA. When encrypting with low numbers and low numbers, the cipher can be easily revealed by choosing the root of the ciphertext over integers.
Since RSA encryption is a deterministic algorithm (i.e., it does not have a random component), an attacker can successfully launch the selected plaintext attack against the cryptosystem by encrypting the likely plaintexts under the public key and checking whether they are equal to the encryption text. A cryptosystem is called semantically secure if an attacker cannot distinguish between two encryptions from each other, even if he knows the corresponding texts in an open form. As described above, RSA without the addition of other services is not semantically secure.
Additional encryption and security algorithms
To avoid the above problems, in the practical implementation of RSA, they usually embed some form of structured, randomized padding before encryption. This ensures that the content does not fall into the range of unsafe plaintexts and that this message cannot be disclosed by random selection.
RSA cryptosystem security and information encryption are based on two mathematical problems: the problems of factoring large numbers and the problems of RSA itself. Full disclosure of ciphertext and EDS in RSA is considered unacceptable on the assumption that both of these problems cannot be resolved together.
However, due to the ability to recover simple factors, an attacker can calculate the secret metric from the public key, and then decrypt the text using the standard procedure. Despite the fact that today no existing method for factorizing large numbers on a classical computer has been found, it has not been proved that it does not exist.
Automation
A tool called Yafu can be used to optimize this process. Automation at YAFU is a state-of-the-art feature that combines factorization algorithms in an intelligent and adaptive methodology that minimizes the time to find factors of arbitrary input numbers. Most implementations of the algorithm are multi-threaded, which allows Yafu to fully utilize multi- or multi-core processors (including SNFS, SIQS, and ECM). First of all, it is a managed command line tool. The time taken to find the encryption factor using Yafu on a regular computer can be reduced to 103.1746 seconds. The tool processes binary files with a capacity of 320 bits or more. This is a very complex software that requires a certain amount of technical skills to install and configure. Therefore, C RSA encryption may be vulnerable.
Modern hacking attempts
In 2009, Benjamin Moody, using the RSA-512 bit key, worked on decrypting crypto text for 73 days using only well-known software (GGNFS) and an average desktop computer (dual-core Athlon64 at 1900 MHz). As shown by this experience, it took a little less than 5 gigabytes of disk and about 2.5 gigabytes of RAM for the process of "sifting."
As of 2010, the largest factorized RSA number was 768 bits long (232 decimal digits, or RSA-768). Its disclosure lasted two years on several hundred computers simultaneously.
In practice, RSA keys are long - usually from 1024 to 4096 bits. Some experts believe that 1024-bit keys may become unreliable in the near future or may even be cracked by a fairly well-funded attacker. However, few will argue that 4096-bit keys can also be revealed in the foreseeable future.
Prospects
Therefore, it is generally assumed that RSA is safe if the numbers are large enough. If the main number is 300 bits or shorter, the ciphertext and EDS can be decomposed for several hours on a personal computer using software that is already freely available. The 512-bit keys, as was proved, could be opened in 1999 using several hundred computers. These days, this is possible for several weeks using publicly available hardware. Thus, it is quite possible that in the future RSA encryption on the fingers will be easily revealed, and the system will become hopelessly outdated.
Officially in 2003, the security of 1024-bit keys was called into question. It is currently recommended that you have a length of at least 2048 bits.