RSA encryption algorithm program. RSA, is it really that simple? When did the cryptosystem appear in its modern form?

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 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 the plaintext was encrypted at this step. 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.

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

General scheme

Scheme electronic signature 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 this 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 you can create a correct signature only 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 in specific hashing or signature algorithms, or errors 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. Centralized certificate systems (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 - open (public) and secret (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 selected 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

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 .

· 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 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. IN currently An RSA-based encryption system is considered strong starting with size N of 1024 bits.

Application of RSA

The RSA system is used to protect software 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 selected from the windows certificate store.

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

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

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

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.

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 the 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 inverse of the modulo 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, as a result of decoding each block of the encrypted message, the corresponding block of the original one is restored. 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. In addition, 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 in the proof of 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 natural number modulo invertible Let's look closely at what can be done to crack RSA if all we know is the pair

To decode a block encrypted with RSA, we need to 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 effective method definitions directly by In fact, this is just a disguised way of decomposition 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, deciding simple system linear equations, we 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 system programmer needs effective method good choice of prime numbers.

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 very little, we can take the value to be 0 and get a reasonable estimate of the difference. So, the number of primes between is approximately equal. Naturally, the estimate is more accurate, the larger x and the smaller For more detailed acquaintance with such an assessment, 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.

Let's consider the operation of an asymmetric RSA . It was proposed by three mathematicians Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) and Leonard Adleman ( L. Adleman) in 1978.

Under prime number We will understand a number that is divisible only by 1 and itself. Euclid in his Elements showed that for every prime number there is a greater prime number, that is, the number of prime numbers is infinite.

Proof. Suppose there is a greatest prime number p, we define the product of all prime numbers P=2∙3∙5∙7∙…∙p.

Consider the number P+1. It is either itself a large prime number p or the product of prime numbers that are greater P. We have come to a contradiction, which means that the number of prime numbers is infinite.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Mutually prime numbers we will name those numbers that do not have a single common divisor except 1 .

Finally, under the result of the operation i mod j we will calculate the remainder of an integer division i on j. To use the RSA algorithm, you must first generate a public and private key by completing the following steps.

1. Choose two very large prime numbers R And q.

2. Let's define n as a result of multiplication R on q (n=p·q).

3. Let's choose a big one random number, which we'll call d. This number must be coprime to the result of multiplication (p – 1) · (q – 1).

4. Let's define such a number e, for which the following relation is true (e d) mod ((p – 1) (q – 1)) = 1.

5. Let's call the public key numbers e And n, and the secret key is numbers d And n.

Now, to encrypt data using a known key ( e, n), you need to do the following:

– split the encrypted text into blocks, each of which can be represented as a number M(i);

– encrypt text considered as a sequence of numbers M(i) according to the formula С(i) = (M(i) e) mod n. To decrypt this data using the secret key (d, n), you need to perform the following calculations: M(i)=(C(i) d) mod n. The result will be a lot of numbers M(i), which represent the source text.

Algorithm RSA based on one of Euler's proven theorems, special case which states that if the number n representable as two prime numbers p And q, then for any x there is equality

x (p-1)(q-1) mod n = 1.

To decrypt RSA messages we will use this formula. To do this, we raise both of its parts to a power (- y):

(x (- y)(p-1)(q-1)) mod n= 1 (- y) = 1.

Now let's multiply both sides by x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Let us now remember how the public and private keys were created. We picked d such that

e d+(p-1)(q-1) y = 1,

e·d = (-y)(p-1)(q-1)+1.

Therefore, in the last expression of the previous paragraph we can replace the exponent with a number (e·d). We get (x e d) mod n = x. To read the message c i = ((m i) e)mod n it is enough to raise it to a power d modulo m:

((c i) d)mod n = ((m i) e · d) mod n = m i .

Here's a simple example of using the RSA method to encrypt a "CAB" message. For simplicity, we will use very small numbers (in practice, large numbers are used).

1. Let's choose p= 3i q= 11.

2. Let's define n= 3· 11=33.

3. Let's find (p–1) (q–1)= 20. As d choose any number that is coprime to 20, for example d= 3.

4. Choose a number e. Any number for which the relation is satisfied can be taken as such a number (e· 3) mod 20 = 1,
for example 7.

5. Imagine the encrypted message as a sequence of integers in the range 0...32. Let the letter A represented by the number 1, letter IN– the number 2, and the letter WITH– the number 3. Then the message can be represented as a sequence of numbers 312. Let’s encrypt the message using the key (7, 33):

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

C(Z) = (2 7) mod 33 = 128 mod 33 = 29.

6. Let's try to decrypt the message (9, 1, 29), obtained as a result of encryption using a known key, based on the secret key (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

M(2) = (1 3) mod 33 = 1 mod 33 = 1,

M(Z) = (29 3) mod 33 = 24389 mod 33 = 2.

Thus, as a result of decrypting the message, the original message “CAB” was received.

The cryptographic strength of the RSA algorithm is based on the assumption that it is extremely difficult to determine the secret key from a known public key, since this requires solving the problem of the existence of integer divisors. This task does not currently admit an effective (polynomial) solution. In this regard, for keys consisting of 200 binary digits (and these are the numbers that are recommended to be used), traditional methods for finding divisors require performing a huge number of operations (about 10 23).

The RSA cryptosystem is used across a wide variety of platforms and industries. It is built into many commercial products, the number of which is constantly growing. She's being used OS Microsoft, Apple, Sun and Novell. In hardware implementation, the RSA algorithm is used in secure phones, on network cards Ethernet, on smart cards, is widely used in cryptographic equipment from Zaxus (Rasal). In addition, the algorithm is included in all major protocols for secure Internet communications, including S/MIME, SSL and S/WAN, and is also used in many institutions, such as government agencies, most corporations, government laboratories and universities .

RSA BSAFE encryption technology is used by more than 500 million users worldwide. Since in most cases the RSA algorithm is used, it can be considered the most common cryptosystem shared key in the world, and this number has a clear tendency to increase as Internet users grow.

Popular

How to number pages in OpenOffice

« From: Belgorod Registered: 2015.03.18 Posts: 550 Likes: 81 Topic: Open Document How to number pages Page numbers in a text... »

The largest public pages on VKontakte Cook it!

« 1. Collections of movies, Public films with those “save them on your wall so you don’t forget to watch them.” For convenience, in publications along with lists... »

Samsung Galaxy A9 Star Pro: the first smartphone with a quad camera Information about the type of speakers and audio technologies supported by the device

« The Koreans presented the world's first smartphone with four cameras - Samsung Galaxy A9 (2018). The price at the start of sales is 39,990 rubles. Someday this... »