Public key encryption system rsa algorithm. RSA cryptographic system. Digital signature and public key

The mechanism for distributing rights in operating systems, developed back in the 70s of the last century, turned out to be so successful that it is still used in UNIX systems, that is, for more than forty years.

Permissions 777 - what is it?

The basic principle of the method of distributing access includes the existence of mandatory attributes, such as the names of system users, as well as their groups. It is almost obvious that in Linux each user can have only one name, which must be unique within this system. Using a nickname, the user logs into the system, that is, undergoes authorization. In addition, the operating system contains a finite number of user groups. Each of them can be part of one or more groups. Superuser - root - can edit properties, create and delete groups. Members of different groups have different rights to operate in the system. For example, an administrator has more rights than a guest.

The inode (which every file has) contains the owner's login and the name of the user group that has rights to the file.

When a file is created, its owner becomes the user on whose behalf the process is running. The group of the newly created file is also determined using the group identifier of the current process. During further work, all these values can be changed using console commands, which will be discussed later.

How to change permissions

The chmod command can change the user access mode of a file. Only its owner or superuser is allowed to change these rights in any way. In Unix systems, the code is usually specified as a number in octal form, or using special mnemonic signs (letters). Using each method has its advantages and disadvantages. So, with the help of digital indication of access rights, the system administrator will be able to quickly configure the desired type of access, and with the help of mnemonic codes, he will be able to do this more precisely - for example, add or remove the write right, or deny the read right.

The first argument of the chmod console command is a specification of user permissions, and this is a mnemonic notation, or an octal number. The second and next arguments are the names of the files to which we are trying to change access rights. When setting rights in the form of three numbers, the first digit determines the rights for the owner, the 2nd for the group, and the third for all other users.

Access rights mnemonics

Access to files in the rights system has the following variations:

r - access to read the file;
w - the right to edit data (but not delete);
x - the ability to launch a file for execution.

The following system of rights applies to directories:

r - the user can read any files in the directory;
w - with these rights you can create and delete files in a folder, even if some of them in the directory belong to another user;
x - indicates the right to enter the directory. If you have w rights to a subfolder but do not have rights to a folder at a higher level, then you will not be able to get through to your folder.

A total of 8 different combinations are possible, which are shown in the figure below.

Using the table below, you can understand how to implement complex permission assignments, as well as how to set 777 permissions using the chmod mnemonic specification.

How to set permissions to 777 via SSH

Here are some examples of using the chmod command:

chmod 711 file_name.txt.

Using this file distribution scenario will result in the owner having full rights to the file, and all other user groups will only be able to execute it.

When using code 775, we will provide the owner and his entire group with a full list of rights. Other users will not be able to make changes to the file. It must be said that to specify a file only by its own name, it must be in the directory where this file is located. Otherwise, you can move to this directory with the command cd directory_name/subdirectory_name or use the following structure:

chmod 775 /var/bin/file_name.txt.

To recursively change the permissions of all files in a directory and all subfolders, you need to add the -R switch to the chmod command. The resulting command will look like this:

chmod -R 711 file_name.

As a result, how to set access rights to 777 for a file or directory will not be a problem - you just need to log in to your web server via SSH and run the command:

chmod 777 filename.

How to set access rights to 777 in the server control panel

You can also implement a similar procedure through the visual interface of the FileZilla FTP client or the WinSCP SFTP client. To do this, you will need to authorize on your server in one of these programs, select your file or folder in the visual interface, then right-click and check the boxes next to the required rights.

Sometimes, in case of urgent need, you may not have access to the Windows client, so you can change access rights through the web server control panel. To do this, using the file manager of your control panel, select the necessary files and click on the Change Permissions button. Next, you will also need to check all the boxes, and now the question of how to set 777 access rights to a folder will no longer be difficult for you.

Public key encryption algorithm RSA was one of the first proposed in the late 70s of the twentieth century. Its name is made up of the first letters of the authors' surnames: R. Rivest, A. Shamir and L. Adleman. The RSA algorithm is probably the most popular and widely used asymmetric algorithm in cryptographic systems.

The algorithm is based on the fact that the problem of factoring a large number into prime factors is difficult. The RSA cryptographic system is based on the following two facts from number theory:

the task of checking a number for primality is relatively easy;
the problem of decomposing numbers of the form n = pq (p and q are prime numbers); factoring is very difficult if we only know n and p and q are large numbers (this is the so-called factorization problem, for more details see "Fundamentals of number theory used in public key cryptography").

The RSA algorithm is a block encryption algorithm where encrypted and unencrypted data must be represented as integers between 0 and n -1 for some n.

Encryption

So, let's look at the algorithm itself. Let subscriber A want to send an encrypted message to subscriber B. In this case, subscriber B must prepare a pair (public key; private key) and send his public key to user A.

The first step is to generate public and private keys. To do this, first select two large prime numbers P and Q. Then the product N is calculated:

After this, the auxiliary number f is determined:

f = (P - l)(Q - 1).

Then the number d is randomly selected< f и взаимно простое с f .

The numbers d and N will be the user's public key, and the value e will be the private key.

So at this point the user should have the information listed in the following table:

Since user B wants to receive an encrypted message from user A, then user B must send his public key (d, N) to user A. The numbers P and Q are no longer needed, but they cannot be shared with anyone; It's best to forget them altogether.

At this point, the key preparation stage is completed and the main RSA protocol can be used to encrypt data.

Second stage – data encryption. If subscriber A wants to send some data to subscriber B, he must represent his message in digital form and break it into blocks m 1, m 2, m 3, ..., where m i< N . The encrypted message will consist of blocks with i .

Subscriber A encrypts each block of his message using the formula

c i = m i d mod N

using public parameters user B, and sends the encrypted message C=(c 1, c 2, c 3, ...) over an open line.

Subscriber B, who received an encrypted message, decrypts all blocks of the received message using the formula

All decrypted blocks will be exactly the same as those coming from user A.

An attacker who intercepts all messages and knows all public information will not be able to find the original message for large values of P and Q.

Example of algorithm calculations

Let user A want to send a message to user B. In this case, user B must first prepare public and private keys. Let them select, for example, the following parameters:

P = 3, Q = 11, N = 3x11 = 33.

Then f = (P - l)(Q - 1) = (3-1)(11-1) = 20.

Then user B chooses any number d that does not have common divisors with f (this is necessary so that the encrypted message can then be uniquely recovered). Let d = 13. This number will be one of the components of the public key.

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 the –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 as five-bit binary numbers. The serial numbers of these letters in the English alphabet are used 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 took advantage of 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 data from the example given on pages 313-315 in the 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 precisely 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.

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

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

Example

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 the –137≡343(mod480), That d=343.

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

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 took advantage of 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:

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

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

Attack on RSA cipher

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

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.

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.

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)

Finally, the time has come to start describing the RSA cryptosystem. In addition to explaining how it works, we must discuss its safety in detail; in other words, why is it so difficult to break a message encrypted with the RSA cryptosystem?

§ 12.1. About the beginning and the end

To implement a single-user RSA encryption system, you must select two different prime numbers p and q and calculate their product. The primes p and q are kept secret while the number becomes part of the public key. In § 12.5 we discuss in detail the method for selecting key primes and how this choice relates to the reliability of the system.

A message (which can be considered an integer) is encrypted by raising it to some power modulo. Therefore, first we must find a way to represent the text of the message as a list of modulo classes. This is, in fact, not yet the encryption process, but only preparing the message so that it could be encrypted.

For simplicity, let's assume that the message text contains only words written in capital letters. So the message is ultimately a sequence of letters and spaces. The first step is to replace each letter of the message with a number that is selected from the following table:

(see scan)

The space between the words is replaced with the number 99. Having done this procedure, we will get a number, possibly very large if the message was long. However, this is not the final number we are striving for, but just a set of modulo classes. And now we need to break the numerical representation of the message into pieces, each of which is a natural number not exceeding These pieces are usually called message blocks.

For example, the numerical representation of the motto “KNOW YOURSELF” looks like this:

By choosing simple ones, we get the product. Therefore, the numerical representation of the message written out above must be divided into blocks smaller than 23,393. Let us present one of such divisions.

Of course, the choice of blocks is not unambiguous, but it is not entirely arbitrary either. For example, to avoid ambiguities at the stage

decryption should not highlight blocks starting with zero.

When decrypting a message encrypted with the RSA encryption system, a sequence of blocks is obtained. They are then connected together to produce a numerical representation of the message. And only after replacing the numbers with letters in accordance with the table above will it be possible to read the original message.

Please note that each letter in the table is coded with a two-digit number. This is done to prevent confusion. Suppose we numbered the letters in order, starting with 1, i.e. A corresponds to 1, B to 2, and so on. In this case, we will not be able to say for sure whether block 12 represents a pair of letters or just one letter, the twelfth letter of the alphabet. Of course, for the numerical representation of a message, you can use any one-to-one correspondence between letters and numbers, for example, -encoding, in which the translation of the message into digital form is automatically performed by a computer.

§ 12.2. Encryption and decryption

A message prepared for encryption using the method of § 12.1 consists of a sequence of blocks, each of which is a number less than Now let's discuss how each block is encrypted. To do this, we need a number equal to the product of primes and a natural number, modulo invertible, i.e. number that satisfies the condition

Let us recall that from known p and q the number can be easily calculated. Really,

The pair is called the public, or encoding, key of the RSA cryptosystem we are describing. Let the message block, that is, an integer that satisfies the inequality We will use the symbol to denote the block of the encrypted message corresponding to It is calculated according to the following rule:

Note that each message block is encrypted separately. Therefore, an encrypted message actually consists of separate encrypted blocks. Moreover, we cannot combine these blocks into one large number, since this will make it impossible to decrypt the message. We will soon see the reason for this.

Let's return to the example that we began to consider in the first paragraph. We have fixed so that Now we need to choose a number Recall that it must be coprime with The smallest prime number that does not divide 23088 is equal to 5. Let us set To encode the first block of the message from § 12.1, we have to determine the subtraction of the number 25245 modulo 23393. With Using a symbolic calculation program (or a calculator, if you have the patience) we get that the required deduction is 22,752. So, the encrypted message is represented by the following sequence of blocks:

Let's see how blocks of an encrypted message are decoded. To begin decryption, we need to know the inverse element to modulo The last of them is a natural number, which we will denote by The pair is called the secret, or decoding key of the RSA encryption system. If a is a block of an encrypted message, then its corresponding decryption

The result of the operation is:

Before returning to the example, some comments are necessary. Firstly, it is very easy to calculate if you know Indeed, the secret key is determined using the extended Euclidean algorithm. Secondly, if the block is the original message, then we have the right to expect equality. In other words, when decoding a block of an encrypted message, we hope to find out the corresponding block of the original one. The fact that this will be the case does not follow directly from the algorithm described above, but we will discuss everything in detail in the next paragraph.

Finally, as we argued in the introduction and throughout the book, to break an RSA cryptosystem you need to factorize it because you need to know to decrypt the message. However, once the workings of the system are described in detail, it is clear that the latter statement is not entirely accurate. To read the encryption, in addition to the element itself, you only need to know the modulo inverse of the element. Therefore, to hack the system, it is enough to calculate with known It turns out that this calculation is equivalent to factoring a number, as we will see in § 12.4.

In the example under discussion, we apply the extended Euclidean algorithm to the numbers and 5 to determine.

(see scan)

Thus, Therefore, the inverse of 5 modulo would be -9235 and

The smallest natural number comparable to -9235 modulo So, to decode a block of an encrypted message, we must raise it to the power of 13,853 modulo 23,393. In our example, the first encoded block is 22,752. Calculating the subtraction of the number 22 75213853 modulo 23,393 , we get Note that even with such small numbers, the requirements for operating the RSA cryptosystem exceed the capabilities of most pocket calculators.

§ 12.3. Why does it work?

As we noted earlier, the steps described above lead to a working cryptosystem only if decoding each block of the encrypted message will restore the corresponding block of the original one. Let us assume that we are dealing with an RSA system that has a public key and a private key. Using the notation of § 12.2, we need to show that for any integer satisfying the inequality the identity holds

In fact, it is enough to prove that

Indeed, both 6 and non-negative integers are smaller. Therefore, they are comparable in absolute value if and only if they are equal. This, in particular, explains why we break the numerical representation of the message into smaller blocks. Moreover, it can be seen from this that blocks

The encoded message must be written down separately: otherwise our reasoning will not work.

From the encryption and decryption recipes it follows that

Since the elements are mutually inverse in modulus, there is a natural k such that Moreover, by condition, the numbers are greater. Therefore, substituting instead of the product in equation (3.1), we obtain

Now let's use Euler's theorem, which states that Hence, i.e.

and we would have completely obtained the proof if a small error had not crept into it.

If you carefully review our reasoning again, you will notice that we did not take into account the conditions of Euler’s theorem. In fact, before applying the theorem, it is necessary to make sure that the numbers are mutually prime. This, it would seem, needs to be monitored when preparing a message for encryption, i.e. When dividing the numerical representation of a message into blocks, you need to ensure that all the resulting blocks are coprime to. Fortunately, this is not necessary, because in fact the comparison is made for any block. And the error lies not in the result that we want to prove, but only in the proof itself. The correct approach is based on the reasoning used to prove Corcelt's theorem in Chapter 7.

Recall that where are different prime numbers. Let us define the residues of a number modulo Since

the calculations for both prime numbers are similar, we will only work out the case in detail. So, we have already seen that

for some integer Therefore,

We would now like to apply Fermat's theorem, but we have the right to do this only if it does not divide Let this requirement be satisfied. Then we get that

By replacing Fermat's theorem with Euler's theorem, we did not solve the problem that arose: the comparison is valid only for some, but not for all blocks. However, now the blocks for which the reasoning does not work must be divided by Further, if it divides then both 6 and are comparable to 0 in modulus and therefore comparable to each other. Thus, the comparison being proved is valid in this case as well. Therefore, the comparison is true for any integer. Note that we don't. could have used similar reasoning when applying Euler's theorem to Indeed, inequality does not mean comparison because the number is composite.

So, we have proven that Comparison is similarly proven. In other words, divides both by and But are different prime numbers, so that Thus, the lemma from § 3.6 guarantees us that divides A since we have for any integer In other words, As we noted at the beginning of the paragraph, this is enough to prove the equality since both of its parts are non-negative integers smaller than To summarize, we can say that

the algorithm of the previous paragraph leads to a practical cryptosystem. Now you need to make sure it is reliable.

§ 12.4. Why is the system reliable?

Recall that RSA is an encryption system with a public key consisting of the product of various prime numbers and a modulo invertible natural number. Let's look carefully at what can be done to crack RSA if all that is known is a pair

To decode a block encrypted with RSA, we must know the inverse of modulo k. The problem is that virtually the only known way to do this is based on applying the extended Euclidean algorithm to However, to calculate using the formula from § 9.4, we need to know what confirms the original statement : Breaking RSA requires factorization. And since the decomposition difficulties are fundamental, the RSA system is safe.

One can, of course, assume that someday someone will discover an algorithm that calculates without information about the factors of a number. What, for example, will happen if someone comes up with an effective way to determine directly by In fact, this is just a disguised method of expansion More precisely, if

are known, then we can easily calculate Indeed,

so the sum of the required prime divisors is known. Further,

therefore the difference is also known. Now, by solving a simple system of linear equations, we can easily find factorization.

This means that the algorithm that calculates actually decomposes the number into factors, so it’s a bird of a feather. But it’s too early to calm down. You can go further in your fantasies and assume that someone has invented an algorithm that determines directly by But So, if we know, then we know the number that is a multiple of it. It turns out that such information is also sufficient for decomposition. A probabilistic algorithm leading to such decomposition can be found V . Exercise 7 shows a similar (but simpler) decomposition algorithm under the assumption that the Rabin cryptosystem can be broken. It will give you an idea of the probabilistic algorithm from .

There remains the last possibility for hacking: an attempt to restore the block directly by modulo residue. If it is large enough, then a systematic search of all possible candidates for the search is the only way out. Nobody has yet come up with anything better. We have listed the main arguments explaining why breaking the RSA cryptosystem is considered tantamount to factorization, although there is no rigorous proof of this statement yet.

§ 12.5. Selecting simple ones

From the previous discussion it follows that for the security of the RSA cryptosystem it is important to choose the right prime numbers. Naturally, if they are small, the system is easily hacked. However, it is not enough to choose large ones. Indeed, even if p and q are huge, but the difference is small, their product can be easily factorized using Fermat's algorithm (see § 3.4).

This is not idle talk. In 1995, two students at an American university cracked a public version of RSA. This became possible due to the poor choice of prime factors of the system.

On the other hand, RSA has been used for a long time and, if the prime factors are chosen carefully, the system actually turns out to be quite reliable. Thus, any RSA encryption programmer needs an effective method for choosing prime numbers successfully.

Suppose we want to create an RSA cryptosystem with a public key in which the integer has about digits. First, let's choose a prime number whose number of characters lies between, let's take it close to. Currently, the key size recommended for personal use is 768 bits, i.e. should be approximately 231 digits long. To construct such a number, we need two simple ones, say, of 104 and 127 digits. Please note that the primes chosen in this way are quite far from each other, i.e. Using Fermat's algorithm for decomposition in this situation is impractical. In addition, we need to make sure that not only small factors, but also large ones are involved in factoring numbers into prime factors. Indeed, otherwise, the number becomes easy prey for some well-known decomposition algorithms (see). Let us now consider a method by which prime numbers are found that satisfy the listed conditions.

First we need one simple result about the distribution of prime numbers. Let us recall what denotes the number of primes not exceeding x. Given the prime number theorem, we see that for large x the number is approximately equal to where is the natural logarithm

on the basis (see § 4.5). Let it be a very large, some positive number. We want to estimate the number of prime numbers lying between and estimate the difference. Thanks to the prime number theorem and the properties of the logarithm, the difference is approximately equal to

Assuming that it is very small, we can assume the value is equal to 0 and get a reasonable estimate of the difference. So, the number of primes enclosed between is approximately equal. Naturally, the estimate is more accurate, the larger x is and the smaller. For a more detailed introduction to such an estimate, see ([D. 10]).

Suppose we need to choose a prime number in the neighborhood of an integer x. For definiteness, we will assume that x is of order , and we are looking for a prime in the interval from x to. It would be useful to know in advance how many prime numbers are in this interval. To estimate the number of primes, you can use the result just obtained. In our example, the value is of a very small order of magnitude: Therefore, using the formula written above, we conclude that the interval between lies approximately

prime numbers. At the end of the second paragraph of Chapter 11, we formulated a strategy designed to prove the primeness of a given odd number. It consists of three steps.