RSA is a public key cryptographic system that provides security mechanisms such as encryption and digital signature (authentication - authentication). The RSA cryptosystem was developed in 1977 and named after its developers Ronald Rivest, Adi Shamir and Leonard Adleman. The RSA algorithm works as follows: two sufficiently large primes p and q are taken and their product is calculated n = p * q; n is called a module. Then the number e is chosen that satisfies the condition

1
e - open (public) indicator
d - private (private) indicator
(n; e) - public (public) key
(n; d) - private key.

The dividers (factors) of p and q can either be destroyed or saved along with the private key. If there were effective methods for factoring (factoring), then, by expanding n into factors (factors) p and q, one could obtain a private key d. Thus, the reliability of the RSA cryptosystem is based on the difficult-to-practically-insoluble-problem of decomposing n into factors (that is, the impossibility of factoring n), since at present there is no effective way to search for factors. The following describes the use of RSA to encrypt information and create digital signatures (practical use is slightly different).


Encryption
Suppose Alice wants to send M. a message to M. Alice creates an encrypted text C, raising the message M to the power e and multiplying by the module n: C = M ** e * (mod n), where e and n is Bob’s public key . Then Alice sends C (encrypted text) to Bob. To decrypt the resulting text, Bob raises the received ciphertext C to the power of d and multiplies by the module n:

M = c ** d * (mod n); the relationship between e and d ensures that Bob calculates M correctly. Since only Bob knows d, only he has the ability to decrypt the received message.


Digital signature
Suppose Alice wants to send M a message to Bob, in such a way that Bob is sure that the message was not hacked and that the author of the message is indeed Alice. Alice creates a digital signature S by raising M to power d and multiplying by the module n:
S = M ** d * (mod n), where d and n is Alice's private key. She sends M and S to Bob.
To verify the signature, Bob raises S to power e and multiplies by the module n: M = S ** e * (mod n), where e and n are Alice’s public key. Thus, the author of the message is encrypted and authenticated without transferring private keys: both correspondents use only the public key of their correspondent or their own private key. Anyone can send an encrypted message and verify the signed message, but only the owner of the corresponding private key can decrypt or sign the message.


RSA algorithm speed
Both when encrypting and decrypting, and when creating and verifying a signature, the RSA algorithm essentially consists of exponentiation, which is performed as a series of multiplications. In practical applications, a relatively small indicator is usually chosen for a public key, and often groups of users use the same public indicator, but each with a different module. If the open indicator is unchanged, then some restrictions are imposed on the main factors (factors) of the module. At the same time, data encryption is faster than decryption, and signature verification is faster than signing.

If k is the number of bits in a module, then in the algorithms commonly used for RSA, the number of steps required to perform a public key operation is proportional to the second degree k, the number of steps for private key operations is the third degree k, the number of steps for the key creation operation is fourth degrees k.

The methods of “fast multiplication” (for example, methods based on the Fast Fourier Transform (FFT)) are performed in a much smaller number of steps. However, they are not widely used because of the complexity of the software implementation, and also because they are actually slower with common key sizes. However, the performance and efficiency of applications and equipment implementing the RSA algorithm are increasing rapidly. The RSA algorithm is much slower than DES and other block encryption algorithms. The software implementation of DES is faster, at least 100 times faster, and from 1,000 to 10,000 in hardware implementation (depending on the specific device). Thanks to the ongoing development, the speed of the RSA algorithm is likely to increase, but at the same time the work of block encryption algorithms will accelerate.


Application of the RSA algorithm in practice

In practice, an RSA cryptosystem is often used with a DES-type secret key encryption system to encrypt a message with an RSA key using a digital envelope.
Suppose Alice sends an encrypted message to Bob. First, she encrypts the message using the DES algorithm, using a randomly selected DES key, and then encrypts the DES key with a public (public) RSA Bob key. The encrypted message with the DES key and the DES key encrypted in turn with the RSA key together form the RSA digital envelope and are sent to Bob. After receiving a digital envelope, Bob decrypts the DES key with his private key and then uses the DES key to decrypt the message itself.


Using RSA Algorithm for Authentication and Digital Signatures
The RSA cryptosystem can also be used to authenticate or identify another person or legal entity. This is possible because each registered user of a cryptosystem has its own unique private key, which (theoretically) is unavailable to anyone else. That is what makes positive and unique identification possible. Suppose Alice wants to send a signed message to Bob. It hashes the message (applies the hash function to the message) to create a message digest, which is the “digital fingerprint” of the message. Then Alice encrypts the message digest with her private key, creating a digital signature that she sends to Bob directly along with the message.

After receiving the message and the signature, Bob decrypts the signature with Alice’s public key, and thus receives a digest of the message. It then processes the message with the same hash function as Alice and compares the result with the message digest obtained when decrypting the signature. If they match exactly, it means a successful verification of the signature and Bob can be sure that the message was indeed sent by Alice. If the results are not the same, it means that either the message did not come from Alice, or was changed during the transfer (that is, after Alice signed it). Alice's signature can be checked by anyone who received or intercepted this message. If Alice wants to keep the contents of the document secret, she signs the document and then encrypts it with the public key of Bob. Bob decrypts the message with his private key and verifies the signature on the recovered message using Alice’s public (public) key. Or - if, for example, it is necessary that the intermediary can confirm the integrity of the message without accessing its contents - instead of a clear text digest, the digest of the encrypted message can be calculated. In practice, the overall indicator of the RSA algorithm is usually much less than the quotient of the private one and therefore the signature verification is faster than signing. This is optimal because the message is signed only once, and the signature verification can be repeated.

To ensure the secrecy of information exchange, it is necessary for the attacker to exclude the possibility of firstly receiving an open message corresponding to the hashed one, and secondly receiving two different hash messages having the same meaning, since in any of these cases the attacker has the ability to attach a false message to Alice’s signature. The MD5 and SHA hash functions have been developed specifically for this, which makes such a comparison impossible. A digital signature may be accompanied by one or more certificates. Certificate - a signed document confirming that a public (public) key belongs to a certain owner, thereby preventing the possibility of imitation of the sender. If you have a certificate, the recipient (or a third party) has the opportunity to verify that the key belongs to the author of the message, that is, the key allows you to verify yourself.


The use of RSA cryptosystem at present
The RSA cryptosystem is used in a wide variety of products, on various platforms and in many industries. Currently, the RSA cryptosystem is embedded in many commercial products, the number of which is constantly increasing. It is also used by Microsoft, Apple, Sun and Novell operating systems. In the RSA hardware version, the algorithm is used in secure phones, on Ethernet network cards, on smart cards, and is widely used in cryptographic equipment. In addition, the algorithm is part of all major protocols for secure Internet communications, including S / MIME, SSL and S / WAN, and is also used in many institutions, for example, in government services, in most corporations, in government laboratories and universities . In the fall of 2000, technologies using the RSA algorithm were licensed by more than 700 companies.
RSA BSAFE encryption technology is used by about 500 million users around the world. Since in most cases the RSA algorithm is used, it can be considered the most common cryptosystem of a common (public) key in the world, and this number has a clear tendency to increase with the growth of the Internet.


Standards with RSA

RSA cryptosystem is part of many standards. The ISO 9796 standard describes RSA as a compatible cryptographic algorithm that complies with ITU-T X.509 security standard. In addition, the RSA cryptosystem is part of the SWIFT, ANSI X9.31 rDSA standards and the draft X9.44 standard for US banks. The Australian Key Management Standard AS2805.6.5.3 also includes the RSA system. The RSA algorithm is used on the Internet, in particular, it is included in such protocols as S / MIME, IPSEC (Internet Protocol Security) and TLS (which is supposed to replace SSL), as well as in the PKCS standard used in important applications.
For application developers using PKCS, the OSI Implementers' Workshop (OIW) organization has released an agreement that specifically deals with the RSA algorithm.

Many other standards currently being developed include either the RSA algorithm itself or its support, or recommend an RSA cryptosystem to ensure secrecy and / or authentication (authentication). For example, include the RSA system recommendations IEEE P1363 and WAP WTLS.


RSA cryptosystem in the world
At the beginning of 2001, the RSA cryptosystem was the most widely used asymmetric cryptosystem (public key) and is often called the de facto standard. Regardless of official standards, the existence of such a standard is extremely important for the development of e-commerce and the economy in general. A single public key system allows for the exchange of documents with digital signatures between users in different countries using different software on different platforms; This opportunity is essential for the development of e-commerce. The proliferation of the RSA system has reached such an extent that it is taken into account when creating new standards. When developing standards for digital signatures, first of all, in 1997, ANSI X9.30 was developed, supporting Digital Signature Standard (Digital Signature Standard). A year later, ANSI X9.31 was introduced, which focused on digital signatures RSA, which corresponds to the actual situation in particular for financial institutions.

The disadvantages of secure authentication (authentication) were the main obstacle to replacing paper documents with electronic ones; almost everywhere contracts, checks, official letters, legal documents are still executed on paper. It is this — the need for paperwork elements — that did not allow for a complete transition to electronic transactions. The digital signature offered by RSA is a tool that will allow transferring the most significant paper document flows to a digital form. Thanks to digital signatures, many documents - passports, ballots, wills, lease agreements - can now exist in electronic form, and any paper version will be in this case only a copy of the electronic original. All this was made possible thanks to the RSA digital signature standard.

RSA illustration of an example

There are many misunderstandings and hoaxes around encryption algorithms with public and private keys. Here I would like to show how this works very briefly and clearly, with specific numbers and a minimum of formulas.

I don’t go into theory (it’s not very clear what level of reader’s training should be expected), but I’m sure that reading this short illustration will make it easier for anyone to understand the formulas and rigorous evidence.

So. Suppose I want to get some data from you. You and I do not want anyone other than us to know this data. And we have no confidence in the reliability of the data channel. Let's get started.

Step one. Key preparation

I have to do the preliminary steps: generate a public and private key.

• I choose two prime numbers. Let it be p=3 and q=7 .
• We calculate the module - the product of our p and q : n=p×q=3×7=21 .
• We calculate the Euler function : φ=(p-1)×(q-1)=2×6=12 .
• Choose a number e that meets the following criteria: (i) it must be simple, (ii) it must be less than φ - there are options: 3, 5, 7, 11, (iii) it must be coprime with φ ; options 5, 7, 11 remain. Choose e=5 . This is the so-called open exhibitor .

Now the pair of numbers {e, n} is my public key. I am sending it to you to encrypt your message. But for me that's not all. I have to get the private key.

I need to calculate the number d , the inverse of е modulo φ . That is, the remainder of the division modulo φ product d×e should be equal to 1. We write this in the notation adopted in many programming languages: (d×е)%φ=1 . Or (d×5)%12=1 . d may be equal to 5 ( (5×5)%12=25%12=1 ), but so that it does not get confused with e in the subsequent narration, let's take it equal to 17. You can check for yourself that (17×5)%12 really equal to 1 ( 17×5-12×7=1 ). So d=17 . The pair {d, n} is the secret key; I keep it for myself. It must not be shared with anyone. Only the owner of the private key can decrypt what has been encrypted with the public key.

Step Two Encryption

Now it's your turn to encrypt your message. Suppose your message is 19. Let us designate it P=19 . Besides it, you already have my public key: {e, n} = {5, 21} . Encryption is performed according to the following algorithm:

• Raise your message to the power of e modulo n . That is, you calculate 19 to the power of 5 (2476099) and take the remainder of dividing by 21. It turns out 10 - this is your encoded data.

Strictly speaking, you do not need to calculate the huge number “19 to the power of 5”. At each multiplication, it’s enough to calculate not the complete product, but only the remainder of the division by 21. But these are the details of the implementation of the calculations, let's not go into them.

Received data E=10 , you send to me.

It should be noted here that the message P=19 should not be greater than n=21 . otherwise it will fail.

Step Three Decryption

I received your data ( E=10 ), and I have a private key {d, n} = {17, 21} .

Note that the public key cannot decrypt the message. And I didn’t tell anyone the private key. This is the beauty of asymmetric encryption.

We begin to decode:

• I am doing an operation very similar to yours but using d instead of e . I raise E to the power of d : I get 10 to the power of 17 (let me, I will not write one with seventeen zeros). I calculate the remainder of dividing by 21 and get 19 - your message.

Note that no one except me (even you!) Can decrypt your message ( E=10 ), since no one has a private key.

What is the guarantee of strong encryption

The security of encryption is ensured by the fact that it is very difficult for a third party (trying to crack the cipher) to calculate the private key from the public one. Both keys are calculated from one pair of primes ( p and q ). That is, the keys are interconnected. But to establish this connection is very difficult. The main catch is the decomposition of the module n into simple factors p and q . If a number is the product of two very large primes, then it is very difficult to factor it.

I will try to show this with an example. Let's factor the number 360:

• immediately clear. that it is divided into two (got 2)
• the remaining 180 is also obviously even (2 more)
• 90 - also even (another two)
• 45 is not divided by 2, but the next attempt is successful - it is divided into three (got 3)
• 15 is also divided by 3
• 5 is simple.

We at every step, practically without exhaustive search, received more and more multipliers, easily obtaining the complete decomposition 360 = 2 × 2 × 2 × 3 × 3 × 5

Let's take the number 361. Now we have to suffer.

• it is not even
• three - no, not divided
• five (let's say we act smartly and iterate over only primes, although, in practice, finding large primes, in itself, is a difficult task) - does not fit
• seven? - not.
• ...
• and only 19 will give us the answer: 361 = 19 × 19.

When using large numbers, the task becomes very difficult. This allows us to hope that the cracker simply does not have enough computing resources to break your cipher in the foreseeable time.

How does this all work in practice?

Many readers ask how all this is applied in practice. Let's look at a slightly closer to life example. We will encrypt and decrypt the word “MOLE”, proposed by one of the readers. And at the same time, let's quickly look at what problems are encountered and how they are solved.

First, we will generate keys with slightly larger numbers. They are not so obvious, but they will allow us to encrypt not only numbers from zero to 20.

Let's start with a pair of primes {p, q} = {17, 19} . Let our public key be {e, n} = {5, 323} , and the private {d, n} = {173, 323} .

We are ready for encryption. We translate our word into digital representation. We can take just the numbers of letters in the alphabet. We get a sequence of numbers: 11, 17, 15, 19.

We can encrypt each of these numbers with the public key {e, n} = {5, 323} and get the encryption 197, 272, 2, 304. These numbers can be transmitted to the recipient with the private key {d, n} = {173, 323} and he will decrypt everything.

A little bit about the difficulties

In fact, the encryption method outlined is very weak and is never used. The reason is simple - spell encryption. The same letter will be encrypted with the same number. If an attacker intercepts a sufficiently large message, he will be able to guess its contents. First, he will pay attention to the frequent codes of spaces and divide the encryption into words. Then he will notice the one-letter words and guess how the letters “a”, “and”, “o”, “b”, “k” are encoded ... By a short search, he will calculate additional letters from short words, such as “but”, “not ", "by". And according to longer words, it will easily restore all the remaining letters.

Thus, an attacker does not have to guess your secret keys. He will crack your message without knowing them.

To prevent this from happening, special additional algorithms are used, the essence of which is that each previous part of the message begins to affect the next.

Simplified, it looks like this. Before encryption, we apply the rule to the message: b := (b + a) % n . Where a is the previous part of the message and b is the next. That is, our message (11, 17, 15, 19) is changing. 11 remains unchanged. 17 turns into (11 + 17) % 323 = 28 . 15 becomes (15 + 28) % 323 = 43 . A 19 turns into 62.

The sequence (11, 28, 43, 62) is “confusing”. All letters in it are sort of mixed, in the sense that each code is affected not by one letter, but by all the previous ones.

Anyone who receives your message will have to do the opposite operation, with a minus sign: b := (b - a) % n . And only then will he receive letter codes.

In practice, random and meaningless letters to the beginning are specially added to the original message. So that even by the first code it was impossible to understand anything. The recipient simply discards the start of the message.

That is, we can add a random number to the beginning and get (299, 11, 17, 15, 19). After mixing, it will turn out: 299, 310, 4, 19, 38. After encryption, it will be impossible to guess where the letter was.

In real life, it’s still a bit more complicated. Blocks on which a message beats longer than one letter. Therefore, first, alignment algorithms are applied, then blocking algorithms with entanglement, and only then RSA encryption itself is applied.

The recipient does everything in the reverse order: decrypts, “unravels” the blocks and discards unnecessary information added simply for alignment (so that the message can be split into an integer number of blocks).