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 in 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 are encrypted sequentially source text 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 public key of the RSA cipher 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 =y 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.

Depending on the structure of the keys used, encryption methods are divided into:

• symmetric: outsiders may know the encryption algorithm, but a small portion is unknown classified information- a key that is the same for the sender and recipient of the message; Examples: DES, 3DES, AES, Blowfish, Twofish, GOST 28147-89
• asymmetric encryption: outsiders may know the encryption algorithm, and possibly the public key, but not the private key, known only to the recipient. Public key cryptographic systems are currently widely used in various network protocols, in particular, in the TLS protocols and its predecessor SSL (underlying HTTPS), as well as SSH, PGP, S/MIME, etc. The Russian standard using asymmetric encryption is .

On this moment asymmetric public key encryption RSA (stands for Rivest, Shamir and Aldeman - the creators of the algorithm) is used by most products on the information security market.

Its cryptographic strength is based on the difficulty of factoring large numbers, namely, on the exceptional difficulty of the task of determining a secret key based on a public key, since this would require solving the problem of the existence of divisors of an integer. The most secure systems use 1024-bit and larger numbers.

Let's look at the RSA algorithm from a practical point of view.

First you need to generate public and private keys:

• Let's take two large prime numbers p and q.
• Let's define n as the result of multiplying p on q (n= p*q).
• Let's choose a random number, which we'll call d. This number must be relatively prime (have no common divisor other than 1) with the result of multiplication (p-1)*(q-1).
• Let us define a number e for which the following relation (e*d) mod ((p-1)*(q-1))=1 is true.
• Let's call the public key the numbers e and n, and the secret key the numbers d and n.

In order to encrypt data using a public key (e,n), you need the following:

• split the encrypted text into blocks, each of which can be represented as a number M(i)=0,1,2..., n-1 (i.e. only up to n-1).
• encrypt the text, considered as a sequence of numbers M(i) using the formula C(i)=(M(I)^e)mod n.

To decrypt this data using the secret key (d,n), the following calculations must be performed: M(i) = (C(i)^d) mod n. As a result, a set of numbers M(i) will be obtained, which represent the original text.

The following example clearly demonstrates the RSA encryption algorithm:

Let's encrypt and decrypt the "CAB" message using the RSA algorithm. For simplicity, let's take small numbers - this will shorten our calculations.

• Let's choose p=3 and q=11.
• Let's define n= 3*11=33.
• Let's find (p-1)*(q-1)=20. Therefore, d will be equal to, for example, 3: (d=3).
• Let's choose the number e using the following formula: (e*3) mod 20=1. This means e will be equal to, for example, 7: (e=7).
• Let's imagine the encrypted message as a sequence of numbers in the range from 0 to 32 (remember that it ends in n-1). Letter A =1, B=2, C=3.

Now let's encrypt the message using the public key (7.33)

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Now let's decrypt the data using the private key (3.33).

M1=(9^3) mod 33 =729 mod 33 = 3(C);
M2=(1^3) mod 33 =1 mod 33 = 1(A);
M3=(29^3) mod 33 = 24389 mod 33 = 2(B);

Data decrypted!

Introduction 3

Main part 5

1History of creation 5

2Description of algorithm 5

2.1Creating keys 6

2.2 Encryption and decryption 6

2.3Use example 7

Conclusion 9

List of sources used 10

Introduction

Cryptography is a special system for changing ordinary writing, used to make text understandable only to a limited number of people who know this system.

Cryptography is the science of protecting information using mathematical methods.

Modern cryptography includes:

symmetric cryptosystems;

asymmetric cryptosystems;

electronic digital signature (EDS) systems;

hash functions;

key management;

obtaining hidden information;

quantum cryptography.

Symmetric encryption - symmetric algorithms are those in which the same secret key (known only to the sender and recipient) is used for encryption and decryption.

Common symmetric encryption algorithms:

AES (Advanced Encryption Standard) - American encryption standard;

GOST 28147-89 - domestic data encryption standard;

DES (Data Encryption Standard) - data encryption standard in the USA up to AES;

3DES (Triple-DES, triple DES);

IDEA (International Data Encryption Algorithm);

SEED - Korean data encryption standard;

Camellia is a cipher certified for use in Japan;

XTEA is the easiest algorithm to implement.

Asymmetric cryptoalgorithms are designed primarily to eliminate the main disadvantage of symmetric cryptosystems - the complexity of managing and distributing keys.

The basis of all asymmetric cryptographic algorithms is the high computational complexity of recovering plaintext without knowledge private key.

Examples of asymmetric crypto algorithms:

Diffie-Hellmann;

RSA - Rivest, Shamir, Adelman - is based on the complexity of the problem of factoring large numbers in a short time;

DSA – Digital Signature algorithm, US standard;

GOST R 34.10 – 94, 2001, Russian Federation standards.

In this abstract, we will consider in detail the asymmetric cryptographic encryption algorithm - the RSA algorithm.

Main part

The RSA algorithm (an acronym for Rivest, Shamir, and Adleman) is a public key cryptographic algorithm that takes advantage of the computational complexity of the problem of factoring large integers. The RSA cryptosystem was the first system suitable for both encryption and digital signing.

History of creation

Published in November 1976, Whitfield Diffie and Martin Hellman's paper "New Directions in Cryptography" revolutionized the understanding of cryptographic systems by laying the foundations for public key cryptography. The subsequently developed Diffie-Hellman algorithm allowed two parties to obtain a shared secret key using an insecure communication channel. However, this algorithm did not solve the authentication problem. Without additional tools, users could not be sure with whom they generated the shared secret key.

After studying this article, three scientists Ronald Linn Rivest, Adi Shamir and Leonard Adleman from the Massachusetts Institute of Technology (MIT) began searching for a mathematical function that would allow implementing a model of a public key cryptographic system formulated by Whitfield Diffie and Martin Hellman. After working on over 40 possible options, they managed to find an algorithm based on the difference in how easy it is to find large prime numbers and how difficult it is to factor the product of two large prime numbers, which later became known as RSA. The system was named after the first letters of the last names of its creators.

Description of the algorithm

The first step in any asymmetric algorithm is to create a pair of keys - public and private - and distribute the public key "throughout the world."

Creating Keys

For the RSA algorithm, the key creation stage consists of the following operations:

The number is called the open exponent

Encryption and decryption

Let's say the sender wants to send a message to the recipient.

Messages are integers in the range from 0 to , i.e. . Figure 1 shows a diagram of the RSA algorithm.

Figure 1 – RSA algorithm diagram

Sender Algorithm:

Recipient Algorithm:

Equations (1) and (2), on which the RSA scheme is based, determine the mutually inverse transformations of the set.

Usage example

Table 1 shows an example of using the RSA algorithm. The sender sent an encrypted message "111111" and the recipient, using his private key, decrypted it.

Table 1 – Step-by-step execution of the RSA algorithm

	Operation description	Result of the operation
Key generation	Choose two prime numbers
	Calculate modulus
	Calculate Euler function
	Select open exponent
	Calculate secret exponent
Encryption	Select text to encrypt
	Compute ciphertext
Decoding	Compute original message

Conclusion

In this abstract, the asymmetric encryption algorithm RSA was discussed in detail. The history of its creation was described, algorithms for creating keys, encryption and decryption were described. An example of the practical use of the RSA algorithm is also presented.

List of sources used

Semenov Yu.A. Internet protocols// M.: Prospekt, 2011. – 114 p.

Belyaev A.V. Methods and means of information security // Black Branch of St. Petersburg State Technical University, 2010. – 142 p.

Venbo M. Modern cryptography. Theory and practice // M.: Williams, 2005. - 768 p.

Schneier B. Applied cryptography. Protocols, algorithms, source texts // M.: Triumph, 2002. - 816 p.

RSA algorithm // Internet resource: http://ru.wikipedia.org/wiki/Rsa

At each encryption cycle, the RSA cryptosystem transforms a binary block of plaintext m of length size(n), considered as an integer, in accordance with the formula: c = m e (mod n).

In this case n = pq , where p and q are large-width random prime numbers that are destroyed after the module and keys are formed. The public key consists of a pair of numbers e and n . Subkey e is selected as sufficient big number from range 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Further, solving the equation xe + yφ(n) = 1 in integers x, y, we assume d = x, i.e. ed = 1(j(n)). In this case, for all m the following relation holds: m ed = m(n) , therefore, knowledge of d allows one to decipher cryptograms.

To guarantee reliable protection information, the following two requirements are imposed on public key systems.

1. Transformation of the source text must exclude its restoration based on the public key.

2. Determining a private key based on a public key must also be computationally infeasible. In this case, an exact lower bound for the complexity (number of operations) of breaking the cipher is desirable.

Public key encryption algorithms are widely used in modern information systems.

Let's look at the construction of the RSA cryptosystem using a simple example.

1. Choose p = 3 and q = 11.

2. Define n = 3 ∙ 11 = 33.

3. Find j(n) = (p – 1)(q – 1) = 20.

5. Choose a number d that satisfies 7d = 1(mod 20).

It is easy to see that d = 3(mod 20).

Let's imagine the encrypted message as a sequence of integers using the correspondence: A = 1, B = 2, C = 3, ..., Z = 26. Since size(n) = 6 , then our cryptosystem is able to encrypt letters of the Latin alphabet, considered as blocks. Let us publish the public key (e, n) = (7, 33) and invite other participants in the secret communication system to encrypt messages sent to us using it. Let such a message be CAB , which in our chosen encoding takes the form (3, 1, 2). The sender must encrypt each block and send the encrypted message to our address:

RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).

Having received the encrypted message (9, 1, 29), we can decrypt it based on the secret key (d, n) = (3, 33), raising each block to the power d = 3:

9 3 = 729 = 3(mod 33);
1 3 = 1(mod 33);
29 3 = 24389 = 2(mod 33).

For our example, it is easy to find the secret key by brute force. In practice this is impossible, because For practical use, the following values ​​of size(n) are currently recommended: :

· 512–768 bits - for individuals;

· 1024 bits - for commercial information;

· 2048 bit - for classified information.

An example of the implementation of the RSA algorithm is presented in Listings 18.1 and 18.2 (compilers - Delphi, FreePascal).

Listing 18.1. An example of the implementation of the RSA algorithm in Pascal language

program Rsa;
($APPTYPE CONSOLE)
($IFDEF FPC)
($MODE DELPHI)
($ENDIF)

uses SysUtils, uBigNumber;

//Generator random numbers

var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn("Enter some text to initialize the generator
random numbers (up to 256 characters):");
ReadLn(s);
i:= 1;
while (i<=255) and (i<=Length(s)) do