What is an RSA key? Public Key Cryptographic Algorithms and Their Uses

Below the cut are examples of choosing “bad” RSA cipher parameters.

“It should be emphasized that care must be taken in selecting the RSA module (number n) for each of the network correspondents. In this regard, the following can be said. The reader can independently verify that knowing one of the three quantities p, q or φ(n), you can easily find the RSA private key...".

Let's add to this text. If the choice of the RSA cipher module is unsuccessful, as was done in the example of the manual given below, you can decrypt the text without the presence of a secret key, i.e. without knowing any of the three named quantities.

To do this, it is enough to have the ciphertext specified by the cipher module n, public key e cipher and perform just three steps of a keyless read attack. After the fourth attack step, it is established that the source text was obtained at the previous step and can be read. Let's show how easy it is to do.

First, let's give the example itself from pp. 313-315 from the said manual.

Example

Encryption short initial text message: RSA.
The recipient sets the cipher with the characteristics n=pq=527, Where p=17, q=31 And φ(n)=(р –1)(q – 1)=480. As a public key e a number is chosen that is coprime to φ(n), e=7. Integers are found for this number using the extended Euclidean algorithm u And v, satisfying the relation e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Because –137≡343(mod480), That d=343.

Examination: 7∙343=2401≡1(mod480).

The text message is presented as a sequence of numbers contained in the interval . Letters for this R, S And A are encoded in five digits binary numbers. Used serial numbers these letters in the English alphabet in their binary representation:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Then RSA=(100101001100001) 2. Breaking the text into blocks of limited length produces a two-block presentation: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Blocks of source text are encrypted sequentially M 1 =297, M 2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Here we used the fact that:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

The ciphertext, like the original one, is obtained in the form of two blocks: y 1 =474; y 2 =407.

Decoding seems to be a sequence of actions D k (y i)=(y i) d =(y i) 343 (mod 527), i=1.2.

Exponentiation calculations d it is more convenient to carry out by first representing the exponent as the sum of powers of the number 2 , namely: 343=256+64+16+4+2+1 .

Using this exponent representation d=343, we get:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
and finally 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

The value is calculated similarly 407 343 (mod527)=33.

Switching to the literal representation of the decrypted message gives: RSA.

After looking at the example, the manual discusses the robustness of the RSA system. The need for caution in choosing the RSA cipher module (numbers) is emphasized. n) for each of the network correspondents. It is indicated that it is inadmissible to ignore the requirements for the selected characteristics of the encryption system. Among these requirements, unfortunately, the violation of which is illustrated by the given example is not indicated.

Attack on RSA cipher

Let's look at an example of an attack on the RSA cipher. Let's use the example data given on pages 313-315 in textbook“Fundamentals of Cryptography” by A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Moscow. "Helios ARV", 2001.

The failure (inadmissibility) of the selected system parameters in this example is easily shown by calculations that implement an attack on keyless reading of the source text. The essence of such an attack is as follows. The RSA cipher public key is specified ( e=7, n=527) and ciphertext. In the example, the ciphertext is represented in two blocks
y=(y 1 =474, y 2 =407).

Each encrypted block is attacked individually, first we attack y 1 =474, after decrypting it, we attack another block y 2 =407.

Next, a sequence of numeric values ​​is formed by repeated encryption, storing the results of two successive steps of the attack algorithm, and using a public key. y i, y 1 =y available ciphertext.

In the ciphertext attack algorithm, the following step number is determined: j, for which y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. From the last relation we see that when raised to a power e values (y i e j–1 (mod n)) the initial ciphertext is obtained y i = y 1.

But this means that at this step the plaintext was encrypted. By direct calculations (there are very few of them) using an on-screen calculator, we find that value j, at which the encryption cycle ends with the value y 1, from which the cycle began.

Attack on the first block y 1 =474 ciphertext.
Step 1:  474 7 (mod527)=382;
Step 2:  382 7 (mod527)=423;
Step 3:  423 7 (mod527)=297;
Step 4:   at this step the already found source text is encrypted, but it must be done since the attacker does not know the source text. A sign of completion of the attack is the coincidence of the initial ciphertext value ( 474 ) and the result of the 4th encryption step. This is exactly the coincidence that takes place.

297 7 (mod527)=474 received the initial (first) block of ciphertext. The attack on the first block was completed successfully y 1 =474. The previous result of step 3 is equal to plaintext M 1 =297.

n=527 r=297 modulo n=527. It's written like this y i =у 1 =297. Forming power residues
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Attack on the second block y 2 =407 ciphertext.
Step 1:  407 7 (mod527)=16;
Step 2:  16 7 (mod527)=101;
Step 3:  101 7 (mod527)=33;
Step 4:  33 7 (mod527)=407.

Again, in the third step, a block of source text was obtained ( M 2 =33), but the attacker does not know this, and he performs the next (fourth step), the result of which is ( 407 ) matches the initial ciphertext y 2 =407.

Essentially in the ring of modulo residues n=527 a short deduction processing cycle was implemented r=33 modulo n=527. It's written like this y i =y 2 =33.
Forming power residues ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Result of the attack (source text M 1 =297, M 2 =33) is obtained by encrypting the given ciphertext three times. It's hard to imagine a greater success for a ciphertext attacker.

Continuing the discussion of the choice of module and other cipher parameters, we can add that the cipher module ( n=527) some source texts cannot be encrypted at all. In this case, the choice of the value of the public key does not play a big role. There are source text values ​​that are generally impossible to encrypt with the selected cipher with the modulus n=527.

None of the given ones can encrypt source texts represented by numbers
187 , 341 , 154 And 373 .

Example (inability to encrypt the values ​​of some source texts)

Let the source texts be represented by four blocks y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Exhibitor e the public key of the cipher can be any coprime number with the Euler function φ(n)=φ(527)=480. However, for the case under consideration, the public key e can be set arbitrarily. Indeed, let e=2, 4, 7, 9, 17, 111 Then:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

A simple conclusion follows from the example considered. Indeed, the choice of parameters for the encryption process must be approached very carefully and a thorough preliminary analysis of such parameters must be carried out. How to do this is a separate issue, and is not considered within the scope of this work.

In the second part we will look at the popular RSA algorithm, where a public key is used for encryption. But first I want to warn you again. The code presented in this article is for educational purposes only. Cryptography is a very broad and complex field, and to avoid any problems, I do not recommend encrypting information using my hack.

In the second part we will look at the popular RSA algorithm, where a public key is used for encryption. But first I want to warn you again. The code presented in this article is for educational purposes only. Cryptography is a very broad and complex field, and to avoid any problems, I do not recommend encrypting information using my hack.

RSA algorithm

Encryption using a public key

Public key encryption is used everywhere. If you've paid for something online at least once, you've already used this method (I hope!). The question immediately arises as to how this protection works. If I enter my number credit card in order to buy something, why can’t anyone except the addressee spy on this information? Let me give you a metaphor. To open a safe, you need a key (or a hammer, but fortunately safes and locks are resistant to these types of people). In public key encryption, much the same thing happens. You show the lock for everyone to see, but only a select few have the key to this lock, and it is almost impossible to open the door using other methods.

RSA is one of the algorithms that implements the above scheme. In addition, we can use this algorithm to verify the authenticity of our identity. If you send an encrypted message to someone using a private key, the recipient can decrypt your message using the public key. This technology allows messages to be signed, thereby confirming the identity of the sender.

Demo program based on the RSA algorithm

RSA encryption is one of the first practical public key cryptosystems and is widely used for secure data transmission. Its main difference from similar services is that the encryption key is public and differs from the decryption key, which is kept secret. RSA technology is based on the practical difficulty of factoring two large prime numbers (the factoring problem).

History of creation

The name RSA is made up of the initial letters of the surnames of Rivest, Shamir and Adleman, the scientists who first publicly described these in 1977. Clifford Cox, an English mathematician who worked for the British intelligence services, first developed an 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. must be kept secret. Anyone can use a public key to encrypt a message, but if it is large enough, then only someone with knowledge of prime numbers can decode the message. Breaking RSA encryption is known to be a major problem: today there is an open debate about how secure the mechanism is.

RSA is a relatively slow algorithm, which is why it is not widely used by the direct user. The most common use of this method is to transmit encrypted shared keys for a symmetric encryption key, which in turn can perform bulk encryption and decryption operations at much higher speeds.

When did the cryptosystem appear in its modern form?

The idea of ​​an asymmetric key cryptosystem is attributed to Diffie and Hellman, who published the concept in 1976, introducing digital signatures and attempting to apply number theory. Their formulation uses a shared secret key created from the exponent of some number modulo a prime number. However, they left open the problem of implementing this function, since the principles of factoring were not well understood at that time.

Rivest, Adi Shamir, and Adleman at MIT made several attempts over the course of a year to create a one-way function that is difficult to decode. Rivest and Shamir (as computer scientists) proposed many potential functions, while Adleman (as a mathematician) searched for the algorithm's weaknesses. They took many approaches and eventually developed the final system in April 1977, today known as RSA.

Digital signature and public key

An electronic digital signature, or EDS, is component electronic documents. It is formed by a certain cryptographic change in data. Using this attribute, it is possible to check the integrity of a document, its confidentiality, and also determine who its owner is. Essentially, this is an alternative to the usual standard signature.

This cryptosystem (RSA encryption) offers a public key, which differs from symmetric ones. The principle of its operation is that two different keys are used - private (encrypted) and public. The first is used to generate an electronic signature and subsequently be able to decrypt the text. The second is for the actual encryption and verification of the digital signature.

Using a signature allows us to better understand RSA encryption, an example of which can be given as an ordinary classified “closed from prying eyes” document.

What is the essence of the algorithm?

The RSA algorithm consists of four stages: key generation, key distribution, encryption and decryption. As already stated, RSA encryption includes a public key and a private key. Open can be known to everyone and is used to encrypt messages. Its essence is that messages encrypted using a public key can only be decrypted within a certain period of time using a secret key.

To be safe, the integers should be randomly selected and be the same in size, but vary in length by a few digits to make factoring more difficult. Identical numbers can be effectively found using a test for their primality, so encryption of information must necessarily become more complicated.

A public key consists of a modulus and a public exponent. Private consists of a module and a private indicator that must be kept secret.

RSA file encryption and weaknesses

However, there are a number of mechanisms for breaking simple RSA. When encrypting with low rates and small numbers, the cipher can be easily broken if you find the root of the ciphertext over the integers.

Because RSA encryption is a deterministic algorithm (i.e., it has no random component), an attacker can successfully launch a chosen plaintext attack against a cryptosystem by encrypting plausible plaintexts under the public key and checking to see if they are equal to the ciphertext. A cryptosystem is said to be semantically secure if an attacker cannot distinguish two encryptions from each other, even if he knows the corresponding texts in cleared form. As described above, RSA, without complementing it with other services, is not semantically secure.

Additional encryption and security algorithms

To avoid the above problems, when practical implementation RSA typically embeds some form of structured, randomized padding before encryption. This ensures that the content does not fall within the range of insecure plaintext and that the message cannot be compromised by chance.

The security of the RSA cryptosystem and the encryption of information are based on two mathematical problems: the problem of factoring large numbers and the RSA problem itself. Full disclosure of ciphertext and digital signature in RSA is considered unacceptable on the assumption that both of these problems cannot be solved together.

However, thanks to the ability to recover prime factors, an attacker can calculate the secret exponent from the public key and then decrypt the text using a standard procedure. Although no existing method has been found today for factoring large numbers on a classical computer, it has not been proven that it does not exist.

Automation

A tool called Yafu can be used to streamline this process. Automation in 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, allowing Yafu to take full advantage of multi or many (including SNFS, SIQS and ECM). First of all, it is a managed tool command line. Time spent searching for encryption factor using Yafu on regular computer, can be reduced to 103.1746 seconds. The tool produces processing capacity of 320 bits or more. This is very complex software that requires a certain amount of technical skill to install and configure. Thus, RSA C encryption may be vulnerable.

Hacking attempts in modern times

In 2009, Benjamin Moody, using an RSA-512 bit key, worked to decrypt cryptotext for 73 days using only common software (GGNFS) and an average desktop computer (dual-core Athlon64 at 1900 MHz). As this experience showed, it took a little less than 5 gigabytes of disk and about 2.5 gigabytes RAM for the "sifting" process.

As of 2010, the largest factored RSA number was 768 bits long (232 decimal digits, or RSA-768). Its deployment lasted two years on several hundred computers simultaneously.

In practice, RSA keys are longer - usually from 1024 to 4096 bits. Some experts believe that 1024-bit keys may become insecure in the near future, or may even already be cracked by a reasonably well-funded attacker. However, few would argue that 4096-bit keys can also be revealed in the foreseeable future.

Prospects

Therefore, RSA is generally assumed to be secure if the numbers are large enough. If the main number is 300 bits or shorter, the ciphertext and digital signature can be decomposed within a few hours into personal computer using software, already available in the public domain. 512-bit keys were proven to be crackable as early as 1999 using several hundred computers. These days this is possible within a few weeks using a publicly available hardware. Thus, it is quite possible that in the future RSA encryption will be easily broken on the fingers, and the system will become hopelessly outdated.

Officially, in 2003, the security of 1024-bit keys was questioned. Currently it is recommended to be at least 2048 bits long.

Electronic digital signature (EDS) - details electronic document, designed to verify the source of the data and protect this electronic document from forgery.

General scheme

An electronic signature scheme usually includes:

• algorithm for generating user key pairs;
• signature calculation function;
• signature verification function.

The function of calculating a signature based on the document and the user's secret key calculates the signature itself. Depending on the algorithm, the signature calculation function can be deterministic or probabilistic. Deterministic functions always compute the same signature from the same input data. Probabilistic functions introduce an element of randomness into the signature, which enhances the cryptographic strength of digital signature algorithms. However, probabilistic circuits require a reliable source of randomness (either a hardware noise generator or a cryptographically secure pseudo-random bit generator), which complicates implementation.

Currently, deterministic schemes are practically not used.

The signature verification function checks whether a given signature matches the given document and the user's public key. The user's public key is publicly available, so anyone can verify the signature on a given document.

Since the documents being signed are of variable (and quite large) length, in digital signature schemes the signature is often placed not on the document itself, but on its hash. Cryptographic hash functions are used to calculate the hash, which ensures that changes to the document are detected when the signature is verified. Hash functions are not part of the digital signature algorithm, so any reliable hash function can be used in the scheme.

Security

A digital signature provides:

• Identification of the source of the document. Depending on the details of the document definition, fields such as “author”, “changes made”, “time stamp”, etc. may be signed.
• Protection against document changes. Any accidental or intentional change to the document (or signature) will change the hash and therefore invalidate the signature.
• Impossibility of relinquishing authorship. Since a correct signature can only be created by knowing the private key, and it is known only to the owner, the owner cannot refuse his signature on the document.

The following digital signature threats are possible:

• An attacker may try to forge a signature for a document of his choice.
• An attacker may try to match a document to a given signature so that the signature matches it.
• An attacker may try to forge a signature for a document.

When using a reliable hash function, it is computationally difficult to create a counterfeit document with the same hash as the genuine one. However, these threats can be realized due to weaknesses specific algorithms hashing, signature, or bugs in their implementations.

However, the following threats to digital signature systems are also possible:

• An attacker who steals a private key can sign any document on behalf of the key owner.
• An attacker can trick the owner into signing a document, for example using a blind signature protocol.
• An attacker can replace the owner's public key (see key management) with his own, impersonating him.

Digital signature algorithms

• American electronic digital signature standards: DSA, ECDSA

• Russian standards for electronic digital signature: GOST R 34.10-94 (currently not valid), GOST R 34.10-2001
• Ukrainian standard for electronic digital signature: DSTU 4145-2002
• The PKCS#1 standard describes, in particular, an electronic digital signature scheme based on the RSA algorithm

Key management

An important problem in all public key cryptography, including digital signature systems, is public key management. It is necessary to ensure that any user has access to the true public key of any other user, protect these keys from being replaced by an attacker, and also organize the revocation of the key if it is compromised.

The problem of protecting keys from substitution is solved with the help of certificates. The certificate allows you to certify the data contained in it about the owner and his public key with the signature of any trusted person. IN centralized systems certificates (such as PKI) use certificate authorities maintained by trusted organizations. In decentralized systems (for example PGP), by cross-signing certificates of familiar and trusted people, each user builds a network of trust.

Key management is handled by certificate distribution centers. By contacting such a center, the user can obtain a certificate for a user, and also check whether a particular public key has not yet been revoked.

Description of the RSA algorithm

RSA- public key cryptographic algorithm. RSA was the first algorithm of its type, suitable for both encryption and digital signature. The algorithm is used in a large number of cryptographic applications.

Story

British mathematician Clifford Cocks, working at the UK Government Communications Center (GCHQ), described a similar system in 1973 in internal GCHQ documents, but this work was not disclosed until 1977 and Rivest, Shamir and Adleman developed RSA independently of the work Cox.

US Patent 4,405,829 was issued to MIT in 1983 and expired on September 21, 2000.

Description of the algorithm

The security of the RSA algorithm is based on the difficulty of the factorization problem. The algorithm uses two keys - public and private; together the public and corresponding secret keys form a key pair (keypair). The public key does not need to be kept secret; it is used to encrypt the data. If a message was encrypted with a public key, it can only be decrypted with the corresponding private key.

Key generation

To generate a key pair, perform the following steps:

1. Two large prime numbers are selected and

2. Their product is calculated

3. The Euler Function is calculated

4. An integer is chosen such that and coprime with

5. Using the extended Euclidean algorithm, a number is found such that

The number is used as ciphertext. To decrypt, you need to calculate

It is easy to see that when decrypting we will restore the original message:

From the condition

it follows that

for some integer, therefore

According to Euler's theorem:

Some features of the algorithm

Generating Prime Numbers

To find two large prime numbers and , when generating a key, probabilistic primality tests are usually used to quickly identify and discard composite numbers.

· with a small value of the open indicator (, for example), a situation is possible when it turns out that . Then, the intruder can easily restore the original message by calculating the root of the degree of .

· since RSA is a deterministic algorithm, i.e. does not use random values ​​during operation, an attacker can use a chosen plaintext attack.

To solve these problems, messages are supplemented before each encryption with some random value - a salt. The padding is done in such a way as to ensure that , and . In addition, since the message is supplemented with random data, when encrypting the same plaintext we will receive a different ciphertext value each time, which makes a chosen plaintext attack impossible.

Selecting an open indicator value

RSA is significantly slower than symmetric algorithms. To increase encryption speed, the open exponent is chosen to be small, usually 3, 17 or 65537. These numbers in binary form contain only two ones, which reduces the number of necessary multiplication operations when raising to a power. For example, to raise a number to the power of 17, you need to perform only 5 multiplication operations:

should be big enough. In 1990, Michael J. Wiener showed that if you choose small, it turns out to be large enough and there is no problem.

Key length

Number n must be at least 512 bits in size. Currently, the RSA-based encryption system is considered strong starting with size N of 1024 bits.

Application of RSA

The RSA system is used for software security and in digital signature schemes. It is also used in open system PGP encryption.

Due to the low encryption speed (about 30 kbps with a 512-bit key on a 2 GHz processor), messages are usually encrypted using higher-performance symmetric random key algorithms ( session key), and using RSA they encrypt only this key.

II. Implementation

As an example, a program was implemented for digitally signing files and verifying signatures. The RSA algorithm and X.509 certificates were used. The user certificate is retrieved from the store windows certificates.

Digital signatures are saved in xml file with name<имя исходного файла>.sig.xml

Code snippets

public class Signature

private X509Certificate2 certificate;

private DateTime date;

private byte signedHash;

public X509Certificate2 Certificate

get(return certificate;)

set (certificate = value; )

public DateTime Date

get(return date;)

set( date = value; )

public void Sign(string input, X509Certificate2 cert)

this.certificate = new X509Certificate2(cert);

date = DateTime.Now;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider());

public bool IsValid(string input)

string stringToEncrypt = input + date.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider(), signedHash);

public byte SignedHash

get(return signedHash;)

set ( signedHash = value; )

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach (Signature signaure in fileSignatures.Signaures)

string row = "";

row+= signaure.Certificate.Subject;

row+=" "+signaure.Date.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool valid = signaure.IsValid(hash);

row = "v " + row;

row = "x " + row;

signatureListTextBox.Text += row+"\r\n";

III. Literature

1. S. Burnet, S. Payne: Cryptography. Official RSA Security Guide – M. “Binom”, 2002
2. V. Winter: Security of global network technologies - “BHV-Petersburg”, 2003
3. Wenbo Mao Modern Cryptography: Theory and Practice = Modern Cryptography: Theory and Practice. - M.: "Williams", 2005. - P. 768. ISBN 0-13-066943-1
4. Nils Ferguson, Bruce Schneier Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - M.: "Dialectics", 2004. - P. 432. ISBN 0-471-22357-3
5. Schneier, Bruce. Applied cryptography. Protocols, algorithms, source texts in C language - M.: TRIUMPH Publishing House, 2002 - 816 pp.: ill. ISBN 5-89392-055-4

Good day, dear readers.
Most likely, most of you know what the asymmetric RSA encryption algorithm is. In fact, there are so many articles devoted to this issue throughout the RuNet and on this resource in particular that it is almost impossible to say anything new about it.
Well, by God, you can come up with something else, and everything was clear a long time ago. The recipe is simple:
Two prime numbers P and Q.
Multiply until you get the number N.
Choose an arbitrary E.
Find D=E -1 (mod( P-1)(Q-1)).
To encrypt the message M, we raise it to the power of E modulo N. To decrypt the cryptotext C to the power of D, modulo N. The entire cryptoprimitive is ready. Let's take it and use it, right? Actually, not like that. The point is that this is really nothing more than a crypto-primitive and in the real world everything is a little more complicated.

A little theory

In order to understand why it is highly discouraged to use RSA in its simplest form, we first note the following requirement for asymmetric cryptosystems.
Requirement 1:
A modern asymmetric cryptosystem can (but this is not yet a fact) be considered secure if an attacker, having two plaintexts M 1 and M 2, as well as one ciphertext C b, cannot, with a probability greater than 0.5, determine which of the two plaintexts the ciphertext C corresponds to b.
Let's see if RSA meets this requirement. So, imagine that the attacker Mallory listens to the correspondence between Alice and Bob. One wonderful day for himself, he sees that Bob openly asked Alice a very important question, knowledge of the answer to which will enrich, or at least immensely amuse Malory’s curiosity. Alice answers Bob in monosyllables to this personal question. She encrypts her response with Bob's public key and sends the ciphertext. Malory then intercepts the ciphertext and suspects that it contains either “Yes” or “No.” All he now needs to do in order to find out Alice’s answer is to encrypt the word “Yes” with Bob’s public key and if the received cryptotext matches the intercepted one, then this means that Alice answered “Yes”, otherwise the attacker will understand that the answer is was "No".

As can be seen from this, albeit somewhat far-fetched, but still not so utopian example, RSA is not as reliable as is commonly believed. Yes, of course, we can say that Alice herself is a fool and no one asked her to answer such a serious question for her in monosyllables. So why now ban the use of one-word answers in cryptography? Of course not. Everything is not so bad, it is enough for the algorithm to add some random information to the text that would be impossible to predict and the insidious Mallory will be powerless. After all, in fact, he will not be able to predict that the answer “Yes” after processing by the algorithm will turn into, for example, “Yes4FE6DA54”, and therefore he will not be able to encrypt this message and will have nothing to compare with the intercepted cryptotext.

Thus, we can already say that RSA in all its manifestations, be it PGP or SSL, does not encrypt only the data sent to the input of the encryption function. The algorithm first adds blocks containing a random set of bits to this data. And only after that the resulting result is encrypted. Those. instead of the usual one
C=M E (mod N)
we get closer to reality
C=(M||Rand) E (mod N),
where Rand is a random number.
This technique is called augmentation schemes. Currently, using RSA without padding circuits is not so much bad manners as it is directly a violation of standards.

But that's not all. It is believed that even if a cryptosystem satisfies the requirement formulated above, this does not yet prove its suitability for practical purposes. Let us formulate one more requirement for the security of an asymmetric algorithm.

Requirement 2:
Let the attacker have access to the decryption “black box”. Those. Any cryptotext can be decrypted at the request of an attacker. Next, the attacker creates two plaintexts M 1 and M 2 . One of these texts is encrypted and the resulting cryptotext C b is returned to the attacker. The attacker's task is to guess with a probability greater than 0.5 which of the messages M 1 and M 2 corresponds to the cryptotext C b . At the same time, he can ask to decipher any message except C b (otherwise the game makes no sense). They say that a cryptosystem is strong if an attacker, even in such excellent conditions for himself, cannot indicate which source text C b corresponds to with a probability greater than 0.5.

In light of the above, let's see how things are going with this in RSA.
So, the attacker has two messages M 1 and M 2. And also cryptotext
C b =M 1 E (mod N).
He needs to indicate which of the two texts corresponds to C b. To do this, he can do the following. Knowing the public key E, he can create a message
C"=2 E *C b (mod N).
Next, he asks the decrypting “black box” to decrypt message C." And then simple arithmetic to help him. We have:
M"=C" D (mod N)=2 ED *M 1 ED (mod N)=2*M 1 (mod N).
Those. Having calculated M"/2, the attacker will see M 1. This means that he will understand that in our example the message M 1 was encrypted, and therefore we are once again convinced of the unacceptability of using RSA in its naive form in practice.

Addition schemes help eliminate this nuisance. Only now the demand is being put forward to them not only that additional information was completely random and unpredictable. But it is also important that additional blocks help determine whether the ciphertext was obtained as a result of the encryption function or whether it was simulated by an attacker. Moreover, if it is discovered that the ciphertext is simulated instead of the decrypted data, the attacker will receive a message indicating that the data does not correspond to the real cryptotext.

It would seem that the implementation of such an addition scheme is a difficult task, but cryptography already has a ready-made tool for monitoring data integrity. Of course, these are hash functions. All modern addition schemes are based on the idea of ​​using a hash function to check the authenticity of decrypted data.

In RSA, when signing and encrypting data, two various schemes additions. The scheme implemented for signing documents is called RSA-PSS (probabilistic signature scheme) or probabilistic signature scheme. The encryption scheme used is RSA-OAEP (Optimal asymmetric encryption padding) or optimized asymmetric encryption padding, using OAEP as an example, and let’s look at how messages are actually encrypted in RSA.

RSA-OAEP

So, to encrypt absolutely any message in RSA-OAEP, do the following:

1. Two hash functions G(x) and H(x) are selected so that the total length of the hash function results does not exceed the length of the RSA key.
2. A random bit string l is generated. The length of the string must be equal to the length of the hash function result H(x).
3. Message M is divided into blocks of k-bits. Then, (n-k) zeros are added to each received block m. Where n is the length of the hash function G(x).
4. Define the following set of bits: (m||0 (n-k) ⊕G(l))||(l⊕H(m||0 (n-k) ⊕G(l)))
5. The resulting bits are represented as an integer M 1
6. Cryptotext is obtained using the formula: C=M 1 E (mod N)

The decryption process is as follows:

1. Find M 1 using the formula M 1 =C D (mod N)
2. In the resulting set of bits, the left side is cut off. In the sense: the left side is the n left bits of the number M 1 where n is the length of the hash function G(x). Let's denote these bits conventionally as T. And note that T=(m||0 (n-k) ⊕G(l)). All other bits are right-hand side.
3. We find H(T)=H(m||0 (n-k) ⊕G(l))
4. Knowing H(T) we obtain l, since we know l⊕H(T) is the right side of the block.
5. Having calculated l, we find m from T⊕G(l) because T=(m||0 (n-k) ⊕G(l))
6. If m ends with (n-k)-zeros, then the message is encrypted correctly. If not, this means that the ciphertext is incorrect, and therefore it was most likely forged by an attacker.

Conclusion

Those. RSA is not just about exponentiation modulo large number. This is also the addition of redundant data allowing you to implement additional protection your information. You may ask: why is all this necessary? Is it really possible for a situation like this to occur where an attacker gains access to the decryption algorithm? On a completely different occasion, it was once said: if any trouble can happen, it will definitely happen. Only with the use of addition schemes this will no longer be considered a nuisance.

Update: moved cryptography to the blog.
upd2:
Literature and links:
1. N. Fergusson, B. Schneier “Practical cryptography”
2. N. Smart “Cryptography”